Curso Dr. Enrico Malaguti

Update:

Integer Linear Programming for Combinatorial Optimization Problems 

The course will present the most effective modeling techniques and solution methods, based on integer linear programming (ILP), for combinatorial optimization problems. Lectures will be based on some very famous examples from the literature, but the aim of the course is to provide the students with some general methods that can be applied to a broad set of theoretical and real-world problems. 

We will start by reviewing basic concepts of linear programming and ILP, which are needed to introduce the most effective solution approaches for ILP. Dantzig-Wolfe reformulation of ILPs and its connection with column generation will be discussed. 

We will then describe three famous families of problems, namely Vertex Coloring problems, Vehicle Routing problems and Cutting problems in one and two dimensions. For these problems we will consider the traditional version and some generalizations. For each problem we will describe alternative models, having polynomial or exponential size, and propose solution approaches based on the Branch and Bound, Branch and Cut and Branch and Price frameworks.  

Course Syllabus

  1. Review of basic concepts and solution methods for LP and ILP. Solution of LPs with exponential formulations: separation and column generation. 
  2. Dantzig-Wolfe reformulation, connection with column generation. 
  3. Models and exact solution methods for Vehicle Routing problems. 
  4. Models and exact solution methods for Vertex Coloring problems. 
  5. Models and exact solution methods for one and two-dimensional Packing problems. 

 

Bibliography

  • Bertsimas, D. and J. N. Tsitsiklis. Introduction to linear optimization, Athena Scientific Series in Optimization and Neural Computation, 6, 1997 
  • Lodi, A., S. Martello, and M. Monaci. Two-dimensional packing problems: a survey. European Journal of Operational Research, 141:241–252, 2002. 
  • A. Lodi and M. Monaci. Integer linear programming models for 2-staged two-dimensional knapsack problems. Mathematical Programming, 94:257–178, 2003. 
  • Gilmore, P.C. and R.E. Gomory. A linear programming approach to the cutting stock problem. Operations Research, 9:849–859, 1961. 
  • Malaguti, E. and P. Toth. A survey on vertex coloring problems, International Transactions in Operational Research, 17: 1-34, 2010. 
  • Martello, S. and P. Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Chichester, 1990. 
  • Mehrotra, A. and M.A. Trick. A column generation approach for graph coloring, INFORMS Journal on Computing, 8:344–354, 1996. 
  • Méndez-Díaz, I. and P. Zabala. A branch-and-cut algorithm for graph coloring, Discrete Applied Mathematics, 154:826–847, 2006. 
  • Vanderbeck, F. and L. Wolsey. Reformulation and decomposition of integer programs, In M. Jünger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, editors, 50 Years of Integer Programming 1958–2008. Springer, Berlin, 2010. 
  • Vigo, D. and P. Toth. The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, 2002.