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.


  Most online loan lenders allow getting Payday Loans New Jersey without visiting a bank, straight to your bank account. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.