20e séminaire POC

SPOC 20 "Autumn school on Advanced BCP Tools: VRPSolver and Coluna"

en partenariat avec le groupe "Optimisation dans les Réseaux" du GDR RO
et le laboratoire SAMM de l'université Panthéon Sorbonne
et l'ESSEC Business School
avec la collaboration d'Eduardo Uchoa (Universidade Federal Fluminense), Brazil

November 21th and 22th 2019

"Autumn school on Advanced BCP Tools:
VRPSolver and Coluna"

You can find on this website:

The topics of school
The registration and location informations
The two day schedule
A bilbiography

Topics of main page

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.

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.

Registration and location

For security reasons, we must provide to the security service the complete list of people registered.
They will check each participant name with identity card.

The entrance is free.
Registration will be close soon due to the limit on the number of places. If you want to be put in the waiting list, please write to pierre.fouilhoux@lip6.fr.
In case of cancellations, the first people in the waiting list will be called.

You will see here the list of registered participants

The school will take place in Paris1 Panthéon-Sorbonne University,

Centre Panthéon:
There is two entrances:
- 12, place du Panthéon
- 17 rue de Saint Jacques and take the stairs M.

The school will be set in
Salle 6, Escalier M, 3td floor ("Deuxième étage" in France)
Caution: and Salle 1 (instead of Salle 6) on Friday afternoon

Access :
RER B - Station Luxembourg
Bus : Ligne 21, 27, 38, 82, 84, 85, 89

Organizers:

Pierre Fouilhoux (LIP6 Sorbonne Universite)
Fabio Furini (LAMSADE, University Paris-Dauphine)
Ivana Ljubic (ESSEC, Paris)
A. Ridha Mahjoub (LAMSADE, University Paris-Dauphine)
Eduardo Uchoa (Universidade Federal Fluminense)
Sonia Vanier (Universite de Paris1 Panthéon-Sorbonne)

Bibliography:

Pessoa, A., Sadykov, R., Uchoa, E., & Vanderbeck, F. (2019). A Generic Exact Solver for Vehicle Routing and Related Problems. In International Conference on Integer Programming and Combinatorial Optimization, LNCS Vol. 11480, 354-369, Springer. Full version: http://www2.logis.uff.br/wp-

Complementary Bibliography:

Paradiso, R., Roberti, R., Laganà, D. & Dullaert, W. (2019) An Exact Solution Framework for Multi-Trip Vehicle Routing Problems with Time Windows, Operations Research (forthcoming).

Costa, L., Contardo, C., & Desaulniers, G. (2019). Exact Branch-Price-and-Cut Algorithms for Vehicle Routing. Transportation Science, 53(4), 946-985.

Liguori, P., Mahjoub, A.R., Sadykov, R. & Uchoa, E. (2019) A Branch-and-Cut-and-Price Algorithm for the Capacitated Location-Routing Problem, Proceedings of the 10th TRISTAN.

Marques, G., Sadykov, R., Deschamps, J. C., & Dupas, R. (2019). An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Report hal-02112287.

Bulhões, T., Pessoa, A., Protti, F., & Uchoa, E. (2018). On the complete set packing and set partitioning polytopes: Properties and rank 1 facets. Operations Research Letters, 46(4), 389-392.

Sadykov, R., Uchoa, E., & Artur Pessoa. "A bucket graph based labeling algorithm with application to vehicle routing." Cadernos do LOGIS, 7 (2017). http://www2.logis.uff.br/wp-

Pecin, D., Contardo, C., Desaulniers, G., & Uchoa, E. (2017). New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing, 29(3), 489-502.

Pecin, D., Pessoa, A., Poggi, M., & Uchoa, E. (2017). Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation, 9(1), 61-100.

Poggi, M., & Uchoa, E. (2014). Chapter 3: New exact algorithms for the capacitated vehicle routing problem. In Vehicle Routing: Problems, Methods, and Applications, Second Edition (pp. 59-86). Society for Industrial and Applied Mathematics.

Contardo, C., & Martinelli, R. (2014). A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optimization, 12, 129-146.

Baldacci, R., Mingozzi, A., & Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations research, 59(5), 1269-1283.

Vanderbeck, F., & Wolsey, L. A. (2010). Reformulation and decomposition of integer programs. In 50 Years of Integer Programming 1958-2008 (pp. 431-502). Springer, Berlin, Heidelberg.

Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M. P., Reis, M., Uchoa, E., & Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming, 106(3), 491-511.

Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. In Column generation (pp. 33-65). Springer, Boston, MA