Branch-Price-and-Cut

Springer eBooks, pp. 443–543

Abstract

Abstract Our aim from the very beginning is to solve an integer linear program. Yet, all that we have algorithmically accomplished so far is to solve the linear relaxation of a Dantzig-Wolfe reformulation. When the solution is fractional, we need to cut it, or branch. From a bird’s eye view, all that remains to do is to use the column generation algorithm to solve the relaxation, and possibly strengthen it by additional valid inequalities, in every node of the branch-and-bound tree. Zooming in, we see that some subtleties have to be respected or can even be exploited.

Authors 4

1. Jacques Desrosiers corresponding

   HEC Montréal · Group for Research in Decision Analysis

   Affiliation as printed

   GERAD and Département de sciences de la décision, HEC Montréal, Montréal, Canada

2. Marco E. Lübbecke Aachen GERAD and School of Business and Economics

   RWTH Aachen University

   Affiliation as printed

   GERAD and School of business and economics, RWTH Aachen University, Aachen, Germany

3. Guy Desaulniers

   Group for Research in Decision Analysis · Polytechnique Montréal

   Affiliation as printed

   GERAD and Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal, Canada

4. Jean Bertrand Gauthier
   Affiliation as printed

   Mainz, Germany