Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : Symmetry Breaking in MIP Optimization Problems
CONFÉRENCIER : Raf Jans, HEC Montréal, Canada
DATE et ENDROIT : 28 mars 2013, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Jean-François Cordeau
RÉSUMÉ : This talk will provide an overview of the work I have done on symmetry breaking in Mixed Integer Programming Optimization (MIP) problems in the last years. I will discuss problems related to production planning, job grouping, and joint product ion distribution planning. Standard formulations for these problems contain a lot of symmetry due to the presence of identical machines, clusters or vehicles. Given a feasible solution, alternative solutions with an equal objective function value can be constructed by permuting the numbering of these identical objects. This leads to a lot of duplication in the branch-and-bound tree when the alternative solutions have to be investigated, and hence results in long CPU times. I will discuss how the techniques of symmetry breaking constraints and reformulation can be used to counter this problem.