Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE : Optimizing over the first Chvátal closure

CONFÉRENCIER : Andrea Lodi, DEIS, Università di Bologna and IBM T.J. Watson Research Center, Yorktown Heights

DATE et ENDROIT : 6 avril 2005, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE : Jean-François Cordeau (340-6278)

RÉSUMÉ : How difficult is it, in practice, to optimize exactly over the first Chvátal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Does it pay to insist on rank-1 Chvátal-Gomory inequalities until no such inequality is violated, or one should better follow the usual strategy of generating (mixed-integer) Gomory cuts of any rank from the optimal tableau rows? How effective is this general-purpose approach for solving matching problems, where the first Chvátal closure coincides with the integer hull? Can this approach be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give, for the first time, concrete answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvátal-Gmory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvátal closure for a set of ILP problems from MIPLIB 3.0. We also report,for the first time, the optimal solution of a very hard instance from MIPIB 2003, namely `nsrand-ipx', obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure.