Contributed Session Mon.3.H 3012

Monday, 15:15 - 16:45 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Scheduling II


Chair: Alexander Tesch



Monday, 15:15 - 15:40 h, Room: H 3012, Talk 1

Matthew Oster
A branch and cut algorithm for solving capacitated max k-cut with an application in scheduling

Coauthor: Jonathan Eckstein


We model the scheduling of a symmetric multi-track conference as a capacitated version of the combinatorial optimization problem known as Maximum k-Cut (MKC). We solve this NP-hard problem to optimality within a branch-and-bound framework equipped with a semidefinite programming relaxation of MKC, enhanced with triangle and clique cuts, as well as new problem-specific cuts (e.g., what we call star-capacity cuts, total-capacity cuts, etc.). We also introduce a new heuristic for generating feasible solutions at most tree nodes. Test results for small to moderate-sized conferences will be discussed for both serial and parallel implementations of our algorithm.



Monday, 15:45 - 16:10 h, Room: H 3012, Talk 2

Alexander Tesch
Optimization of the ISMP 2012 schedule


Your favourite sessions overlap at the same time, the lecture halls are overcrowded or your talk just wasn't added to a suitable date-slot?
Assignment-problems like that may occur in conference planning like this year's ISMP. To avoid such incidents hopefully we developed a MIP with multi-criteria objective to handle several conflicts like an even offering of different clusters, room-capacity-requirements and prevention of time-dependant-crossovers of popular talks. Therefore we integrated a priority model for the talks to evaluate high visitor rates. We also used an approach to relax the original assignment problem and introduce a heuristic to solve the master problem from the obtained relaxed solution.


  In particular, Texas Payday Loans can cater to the needs of its residents. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.