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

   

  Introduction

  SAMBA is a 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) and was renewed for another three years period (2014-2016) with additional partners at the Operations Research and Complex Systems Group School of Business, Universidad Adolfo Ibanez, Chile, and the LIRMM at the University of Montpellier.

  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 es- sentially based on enumeration techniques, which is notoriously difficult given the huge size ofthe 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.

  Decomposition approaches are primary tools to expand the capabilities of MIP solution techniques. When the application presents a decomposable constraint system, the so-called “Dantzig-Wolfe decomposition” consists in reformulating the problem as a selection of a specific solution for each individual subsystems that together satisfy the linking constraints. In practice, the individual subsystem solutions are brougth in the formulation in the course of the opti- mization if they can lead to improvement in the objective value. On the other hand, “Benders’ decomposition applies when the the application presents a decomposable system of variables, as traditional in stocahstic two-stage optimization models where main decisions are taken prior to knowing the realization ofr random data, while second stage decision are adjusments that can be done once the true value of data is revealed. In this context, one solves the first stage model and check a posteriori the feasibilility of the second stage. In case the second stage is infeasible, a constraint on the first stage variables is induced that aim to account for the cause of second stage infeasibility, and the processus reiterates.

  Both of these decomposition approaches are perceived as requiring an application specific implementation for tractability in scaling-up to real-life applications. Our research aim at developing generic methods for these and algorithmic enhancements to can yield significant speed-ups in practice and have sound theoretical basis. Such research includes methodological developments (such as stabilization techniques for improved convergence, preprocessing rules, dynamic aggregation-and-disagregation), algorithms strategies (such as mutli-column/cut generation strategies, pre-evaluation of enumerated subproblem strategies – so-called strong branching), and efficient implementations (code re-engineering of our software platform BaPCod).

  Beyond the methodological developments, our motivations are to set new benchmarks on standard combinatorial problems and industrial applications. In particular, we proceed to extend our techniques to the context of dynamic optimization. In a stochastic environment, the aim is to build a planning that are robust to perturbations in the sense that it can be adapted dynamically in reaction to the observed changes in the predicted data.

  The project builds on the accumulated experience of both the Brazilian, the Chilean 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 software 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

  Principal investigators (Inria – France)

  • Ruslan Sadykov, research fellow at INRIA
  • François Vanderbeck, professor at University Bordeaux I and

  Principal investigators (Brazil)

  • Artur Alves Pessoa, associate professor at Universidade Federal Fluminense (UFF)
  • Eduardo Uchoa, associate professor at Universidade Federal Fluminense (UFF)
  • Teobaldo Junior, PhD student at Universidade Federal Fluminense (UFF)

  Principal investigators “satellite team 1” (Chile)

  • Marcos Goycoolea (Prof.), Operations Research and Complex Systems Group
  • Eduardo Moreno (Assoc. Prof.), Operations Research and Complex Systems Group
  School of Business, Universidad Adolfo Iba\~nez, Chile

  Principal investigator “satellite team 2” (Brazil)

  • Marcus Poggi de Aragão, professor at PUC-Rio

  Principal investigator “satellite team 3” (France)

  • Michael Poss (CNRS Research Fellow), LIRMM, Universit\’e de Montpellier, France

  Other participants

  • Fabian Castilla (PhD Student), ADT-Lab PUC Rio, Brazil;
  • Francois Clautiaux (Prof), ReAlOpt, Inria & University of Bordeaux;
  • Boris Detienne (Associate Prof), ReAlOpt, Inria & University of Bordeaux;
  • Pierre Pesneau, associate professor at University Bordeaux I and INRIA
  • Diego Pecin, Post-Doc U Montreal
  • Hugo Kramer, PhD Student at UFF
  • Orlando Rivera, PhD Student at Universidad Adolfo Iba\~nez
  • Issam Tahiri (Expert Engineer), ReAlOpt, Inria & University of Bordeaux.

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.
• Francois Vanderbeck visited Marcos Goycoolea at the Universidad Adolfo Ibanez, Chile, for 10 days in November 2013.
• Eduardo Uchoa and Francois Vanderbeck met at the Aussois Workshop for Combinatorial Optimization in January 2014.
• Michael Poss visited us in Bordeaux on the first week of February 2014.
• Marcos Goycoolea visited us in Bordeaux on the first week of September 2014.
• Marcos Goycoolea and Francois Vanderbeck met at the INFORMS meeting (USA) in November 2014.
• Michael Poss visited us in Bordeaux on the last week of November 2014.
• Michael Poss was visting Artur Pessoa and Eduardo Uchoa end of December 2014.
• Eduardo Uchoa and Francois Vanderbeck met at the Aussois Workshop for Combinatorial Optimization in January 2015.
• Eduardo Uchoa visited us in Bordeaux on the third week of January 2015.
• Eduardo Uchoa, Michael Poss, Ruslan Sadykov and Francois Vanderbeck met at the International Math Progr Symposium in Pittsburgh in July 2015.
• Michael Poss visited us in Bordeaux on the first week of May 2015.
• Eduardo Moreno visited us in Bordeaux on November 9-17, 2015.
• Ruslan Sadykov is spending a sabbatical year in Brazil, visiting UFF from Aug 2015 to Jul 2016.

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

• Automation and combination of linear-programming based stabilization techniques in column generation, Pessoa, A; Sadykov, R; Uchoa, E; and Vanderbeck, F. hal-01077984, 2014. Submitted for publication.

• Staged Column Generation Approaches for the Software Clustering Problem, Kramer, Hugo Harry; Fampa, Marcia; Kohler, Viviane; Uchoa, Eduardo; and Vanderbeck, Francois, ROADEF 2014. Submitted for publication.

• Extended formulations for robust maintenance planning at power plants. B. Detienne. PGMO – COPI – 14

• The Prominence of Stabilization Techniques in Column Generation: the case of Freight Transportation R. Sadykov; A. A. Lazarev; A. Pessoa; E. Uchoa; and F. Vanderbeck. Odysseus 2015.

• Nouvelles bornes primales pour le problème d’affectation généralisée Ruslan Sadykov, Arthur Pessoa, Eduardo Uchoa and Francois Vanderbeck. Roadef 2015.