Christian Artigues (LAAS - CNRS) | March 30 | Mixed integer linear programming for resource-constrained scheduling

Dear scheduling researcher, We are delighted to announce the talk given by Christian Artigues (LAAS - CNRS). The title is "Mixed integer linear programming for resource-constrained scheduling". The seminar will take place on Zoom on Wednesday, March 30 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91490324777?pwd=dFV0UjRlL2UyZUg1ZC9ZdGtJb2FqUT09 Meeting ID: 914 9032 4777 Passcode: 848529 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Mixed-Integer linear programming (MILP) is one of the generic modeling and algorithmic solution framework for NP-hard scheduling problems, along with Constraint Programming (CP) and SAT solvers. However, the literature often reports poor results of MILP solvers for resource-constrained scheduling problems compared to CP or SAT-based approaches such as Lazy Clause Generation. However, even if this is partly true because of the powerful dedicated scheduling algorithms embedded in constraint propagators, MILP approaches can reach very good results in terms of primal and dual bounds if the right formulation and specialized MILP components such as valid inequalities and column generation are chosen for the problem at hand. This talk first reviews the standard MILP formulations for resource-constrained scheduling problems and a few recent advances in the field. In particular, we focus on basic polyhedral results, on the relative relaxation strength of compact and extended formulations augmented with valid inequalities. Finally, we provide examples, including industrial ones where MILP, possibly integrated in hybrid CP/SAT/MILP methods, appears as a technique of choice. The next talk in our series will be given by: Pascal Van Hentenryck (Georgia Tech) | April 13 | Constraint Programming for Scheduling For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/
participants (1)
-
Zdeněk Hanzálek