Datum / čas
Date(s) - 30.03.
15:00 - 17:00

Kategorie ne Kategorie

Christian Artigues: Mixed integer linear programming for resource-constrained scheduling

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 litterature 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.

Watch online: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A/live

More information:https://schedulingseminar.com/