SAMBA: Synergies for Ameliorations and Mastering of Branch-and-Price Algorithms

Introduction

SAMBA is research project between the INRIA project team ReAlOpt (Bordeaux, France), the ADT-Lab Pontifícia Universidade Católica do Rio de Janeiro, and the LOGIS at the Universidade Federal Fluminense. The project is supported by INRIA under the "associate team" framework for an initial period of three years (2011-2013).

Description

Quantitative models are important tools for strategic, tactical, and operational decision-making. Many underlying optimization problems are discrete in nature. They are modeled as linear programs with integer variables, so called Mixed Integer Programs (MIP). Their solution is essentially based on enumeration techniques, which is notoriously difficult given the huge size of the solution set. Powerful generic commercial solvers for MIP are available, but despite continuous progress, the existing tools can be overwhelmed when problem complexity or size increases.

The so-called Dantzig-Wolfe decomposition approach is one way to expand the capabilities of MIP solution techniques when the application presents a decomposable constraint system. It consists in reformulating the problem as a selection of a specific solution for each individual subsystems that together satisfy the linking constraints. As the number of solutions for individual subsystems is exponential, the algorithm proceeds by a dynamic generation of those of interest during the solution process -- a technique called column generation which, combined with a branch-and-bound enumeration procedure, give rise to the so-called Branch-and-Price algorithm. Such approach is perceived by the research community as application specific and has not yet made its way into general purpose solvers for Mixed Integer Programming (MIP). Our research aims at making such approach a general purpose technique.

Our project contributes to develop generic algorithmic improvements to derive and enhance a general purpose column generation based method. We focus in particular on

  • preprocessing procedures,
  • warm-starting,
  • stabilization (to improve convergence),
  • strategies for combining cut and column generation,
  • primal heuristics, and
  • alternatives to standard LP based column generation.

The project builds on the accumulated experience of both the Brazilian and the French teams that have done pioneering work in tackling complex applications and deriving generic solution strategies using this decomposition approach.

Software development

The resulting output of our methodological research are proof-of-concept prototype algorithms that contribute to our generic Branch-and-Price-and-Cut platform, BaPCod. (BaPCod was originally developed as a generic Branch-and-Price code by ReAlOpt as a C++ library that is build as a layer above MIP solvers.) This prototype should enable us to achieve new benchmark results on key problems, provide incentive for the use of the method by non experts, and leverage technology transfer to industry.

Contributors

ReAlOpt project team:

LOGIS and ADT-Lab:

Exchanges and stays of researchers between partners

  • François Vanderbeck visited PUC-Rio and UFF for two weeks in March 2011
  • Ruslan Sadykov visited PUC-Rio and UFF for two weeks in April 2011
  • Marcus Poggi spent a short visit in Bordeaux in May 2011.
  • François Vanderbeck, Marcus Poggi, and Eduardo Uchoa attended together Integer Programming Worshop at Newcastle, Australia in July 2011
  • Artur Pessoa visited the University Bordeaux for two weeks in November 2011
  • Eduardo Uchoa visited the University Bordeaux for one week in November 2011
  • François Vanderbeck visited PUC-Rio, UFF, and Gapso for two weeks in March 2012
  • Ruslan Sadykov visited UFF, and Gapso for two weeks in March 2012
  • Marcus Poggi, Diego Peccin and François Vanderbeck met at the Column Generation Workshop in Canada in June 2011.
  • Diego Peccin visited the University Bordeaux for two weeks in July 2012
  • Artur Pessoa visited the University Bordeaux for two weeks in November 2012.
  • François Vanderbeck visited PUC-Rio and UFF for two weeks in March 2013.
  • Ruslan Sadykov visited PUFF for two weeks in March 2013.
  • Eduardo Uchoa visited the University Bordeaux for one month in April 2013.
  • Hugo Kramer is visiting the University Bordeaux for one year in 2013.
  • Eduardo Uchoa is planning a visit at the University Bordeaux in November 2013.
  • François Vanderbeck is planning a visit at PUC-Rio and UFF for two weeks in March 2014.

Joint conference and working paper produced in the realm of the associate team (on Hall)

  • "Column Generation Stabilization using Dual Smoothing: Theory and Practice."

François Vanderbeck ; Jinil Han; Pierre Pesneau; Artur Pessoa; Ruslan Sadykov ; Eduardo Uchoa Informs Annual Meeting: Informatics Rising, Oct 2012, Phoenix, United States.

  • "Primal heuristics for branch-and-price."

François Vanderbeck ; Cedric Joncour; Sophie Michel; Pierre Pesneau; Artur Pessoa; Marcus Poggi ; Ruslan Sadykov ; Eduardo Uchoa. 21th International Symposium on Mathematical Programming (ISMP 2012), Aug 2012, Berlin, Germany.

  • "Column Generation Stabilization using Dual Smoothing: Theory & Practice."

Jinil Han; Pierre Pesneau; Artur Pessoa; Eduardo Uchoa; François Vanderbeck. Column Generation 2012, Jun 2012, Bromont, Canada.

  • "Equipment/Operator task scheduling with BAPCOD."

Marcus Poggi ; Diego Pecin; M. Reis; C. Ferreira; K. Neves; Ruslan Sadykov ; François Vanderbeck. Column Generation 2012, Jun 2012, Bromont, Canada.

  • "Unifying procedures for Cut-Column Generation and Stabilization"

François Vanderbeck ; Jinil Han; Pierre Pesneau; Artur Pessoa; Ruslan Sadykov ; Eduardo Uchoa. Workshop on Integer Programming, Mar 2012, Valparaiso, Chile.

  • "In-Out Separation and Column Generation Stabilization by Dual Price Smoothing."

Artur Pessoa; Ruslan Sadykov ; Eduardo Uchoa; François Vanderbeck. 12th International Symposium on Experimental Algorithms, Jun 2013, Rome, Italy. Sringer, Lecture Notes in Computer Science (LNCS), LNCS 7933, pp. 354-365, June 2013. hal-00750412

  • Stabilization techniques for Column Generation: towards automated schemes.

François Vanderbeck ; Artur Pessoa; Ruslan Sadykov ; Eduardo Uchoa EURO INFORMS 26, Jul 2013, Rome, Italy. http://hal.inria.fr/hal-00845858

  • "Extended formulations, Column Generation, and stabilization: synergies in the benefit of large scale applications", François Vanderbeck, invited semi-plenary talk at EURO INFORMS 26, Jul 2013, Rome, Italy. http://hal.inria.fr/hal-00845318
Last updated: November 12, 2012


Page last modified by May 05, 2005, at 04:34 PM