Wednesday 13 April 2016 h. 14:30, Room 2BC30

Michele Barbato (LIPN, Univ. Paris 13, France)

"Cheapest Routes with Integer Linear Programming"

Abstract

Combinatorial Optimization deals with the optimization of a function over a finite, but huge, set of elements.

It has a great impact on real life, as several problems arising in logistics, scheduling, facility location, to cite a few, can be stated as Combinatorial Optimization problems. Often problems of this kind can be expressed as Integer Linear Programs (ILP), i.e., problems in which the function to be optimized is linear and so are the constraints that define the feasibility set. In the first part of the talk, we provide an introductory presentation of some well-established methods in Integer Linear Programming. These methods are presented through examples that, in several cases, also motivate theoretical questions (e.g., the polyhedral study). We will consider as initial case of study the Traveling Salesman Problem (TSP). The TSP consists in finding the cheapest route that visits a prescribed set of cities exactly once, before returning to the starting point. As such, the TSP is a prototype of several other problems arising in logistics. In the second part of the presentation we will talk about the Double Traveling Salesman Problem with Multiple Stacks, that combines the construction of a cheapest route with loading constraints. We will reveal links between this problem and the TSP, as well as the limitations that a purely routing-based approach has for this problem.