Presentation

BapCod is a prototype code that solves Mixed Integer Programs (MIP) by application of a Dantzig-Wolfe reformulation technique. The reformulated problem is solved using a branch-and-price (column generation) algorithm. The specificity of this prototype is to offer a "black-box" implementation of the method:

  1. the input is the set of constraints and variables of the MIP in its natural/ compact formulation;
  2. the user specifies which of these constraints and variables define the subsystems on which the decomposition is based (it is handy to test different decompositions);
  3. the reformulation is automatically generated by the code, without any input from the user to define master columns, their reduced cost, pricing problem, or Lagrangian bound;
  4. a default column generation procedure is implemented that relies on an underlying MIP solver to handle master and subproblem but the user can upload a specific subproblem solver;
  5. a branching scheme that preserves the pricing problem structure is offered by default; it runs based on priorities and directives specified by the user on the original variables;
  6. default primal heuristics and preprocessing features are under developments.

Current Developers

Beta users

The software can be made available on special request, primarily for research purposes. It is currently in use for research purposes at:

National:

  • The University Bordeaux 1,
  • Inria Bordeaux Sud-Ouest,
  • Inria Lille (François Clautiaux)
  • Université Paris 6 (Aurélien Questel)
  • Université Paris 13 (Sylvie Borne)
  • Université du Havre (Cédric Joncour, Sophie Michel Loyal)
  • France Telecom Orange Labs (Nancy Perrot)
  • Eurodecision (Frédéric Fabien)

International:

  • University of Brescia, it, (Nicola Bianchessi)
  • Gapso, Brasil (Diego Pecin)
  • PUC, Rio (Marcus Poggi)
  • UFF, Brasil (Artur Pessoa, Eduardo Uchoa)

intranet


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