About

Topic: 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).

This tutorial’s goals are to review recent advances providing significant increased capabilities in BCP algorithms design for VRPs, and to introduce VRPSolver,  a highly flexible and generic BCP algorithm for solving VRPs and related problems. The VRPSolver model corresponding to a particular application is coded using Julia language. A typical model has less than 100 lines of code,  enabling users to have a good working algorithm in a short time.

The tutorial will comprise three 90 minute lectures and two 180 minute hands-on tutorial.

Lecturers:

Assistants (hands-on)

  • Eduardo QUEIROGA, Universidade Federal Fluminense
  • João Marcos PEREIRA SILVA, Universidade Federal Fluminense

Program:

  • Lecture 1 (90 minutes): Column generation basics. Presenting (or refreshing for those that are already familiar) the very basic concepts of column generation.
  • Lecture 2 (90 minutes):  Recent advances in exact algorithms for VRP. Survey on the new elements in Branch-Cut-and-Price algorithm introduced in the last 15 years.
  • Lecture 3 (90 minutes): Modeling with VRPSolver. General VRPSolver model and examples.
  • Hands-on tutorial session 1 (180 minutes).
  • Hands-on tutorial session 2 (180 minutes).

Target public audience: Researchers, graduate and advanced undergraduate students. In particular, people interested in mixed-integer programming state-of-the-art BCP techniques

Requisites: Standard linear programming and mixed-integer programming background knowledge.

Important dates:

  • November 23-27: Tutorial sessions.

 

Organizer

Proyecto CONICYT+FONDEF/Concurso IDeA I+D 2018, folio ID18I10250.