AUTUMN SCHOOL ON ADVANCED BCP TOOLS: VRPSolver and Coluna
Paris 21-22 November 2019
Registration, access and schedule:
https://www.lamsade.dauphine.fr/poc/?q=node/64
Branch-Cut-and-Price (BCP) algorithms, based on the combination of
column generation with cut separation, are obtaining the best results on
the exact solution of several combinatorial problems, in particular,
those related to Vehicle Routing Problem (VRP). However, devising and
implementing a state-of-the-art BCP can be a very demanding task,
measured on several work-months of a skilled team.
This school intends to:
- Review the techniques introduced in the last 10 years that
significantly increased the capabilities of BCP algorithms for VRPs:
ng-routes, hierarchical strong branching, route enumeration, advanced
implementation of dynamic programming labeling algorithms for pricing,
fixing by reduced costs and rank-1 cuts with limited memory.
- Introduce VRPSolver, a highly generic BCP algorithm for solving VRPs
and related problems,that already includes all the above mentioned
techniques. The VRPSolver model corresponding to a particular
application is coded using Julia language. A typical model has less than
100 lines of code, so users can already have a good working algorithm in
one day. Additional work on separation routines for problem specific
cuts may be needed for top performance. VRPSolver can be downloaded at
https://vrpsolver.math.u-bordeaux.fr
- Discuss "creative modeling" on VRPSolver. Several problems that are
not standard VRPs can be possibly modeled by using non-trivial
transformations, obtaining quite good performances. Known examples
include Generalized Assignment Problem, Bin Packing and Vector Packing
Problems, Parallel Machine Scheduling and Robust VRP.
- Present to the community the open-source Branch-Cut-and-Price (BCP)
framework Coluna, that is being developed collaboratively in Julia
language and is available under Mozilla Public Licence. VRPSolver
currently uses a private BCP framework. Future versions of VRPSolver
will be based on Coluna, allowing much more user control on the
algorithm strategies. Coluna should also feature support for parallel
computing.
- provide an overview of challenging future applications of VRPs.
- showcase BCPs for Graph Coloring problems.
Public: Researchers and PhD students. In particular, people from
polyhedral combinatorics that may profit from having a practical way of
using their cuts as part of an advanced BCP. A hands-on tutorial will be
given.
Speakers:
Claudia Archettin (ESSEC, Paris, France)
Teobaldo Bulhoes (Universitdade Federal da Paraiba, Brazil)
Fabio Furini (LAMSADE Université Paris-Dauphine, France)
Guillaume Marques (INRIA, Université de Bordeaux, France)
Artur Pessoa (Universidade Federal Fluminense, Brazil)
Marcus Poggi (PUC, Rio de Janeiro, Brazil)
Michael Poss (LIRMM, Université de Montpellier, France)
Roberto Roberti (Vrije Universiteit Amsterdam, Netherlands)
Ruslan Sadykov (INRIA, Université de Bordeaux, France)
Eduardo Uchoa (Universidade Federal Fluminense, Brasil)
François Vandrebeck (AtOptima)
Organizers
Pierre Fouiloux (LIP6 Sorbonne Universite)
Fabio Furini (LAMSADE, University Paris-Dauphine)
Ivana Ljubic (LAMSADE and ESSEC, Paris)
Ridha Mahjoub (LAMSADE, University Paris-Dauphine)
Eduardo Uchoa (Universidade Federal Fluminense)
Sonia Vanier (Universite de Paris1 Panthéon-Sorbonne)
--
A. Ridha Mahjoub
Laboratoire LAMSADE
Université Paris Dauphine
Place du Maréchal de Lattre de Tassigny
75775 Paris Cedex 16
France
Tel: +33 (0)1 44 05 48 96
Fax: +33 (0)1 44 05 40 91
E-mail: mahjoub@lamsade.dauphine.fr
URL: http://www.lamsade.dauphine.fr/~mahjoub
Editor-in-Chief of RAIRO-Operations Research
http://www.rairo-ro.org/action/displayJournal?jid=ROE
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
