Reformulation and algorithms for Combinatorial Optimization

Decision making today relies increasingly on support from mathematical models. Quantitative modeling is routinely used in both industry and administration to design and operate transportation, distribution, or production systems. Optimization concerns every stage of the decision-making process: investment budgeting, long term planning, the management of scarce resources, or the planning of day-to-day operations. Many optimization problems that arise in decision support applications involve discrete decision variables; the resulting problems can be modeled as linear or non-linear programs with integer variables.

The solution of such problems is essentially based on enumeration techniques and can be notoriously difficult given the huge size of the solution space. A key to success is the development of better problem formulations that provide strong approximations and hence help to prune the enumerative solution scheme. One must also avoid the drawback of enumerating what are essentially symmetric solutions.

Our project aims to develop tight formulations and algorithms for combinatorial optimization problems exploiting the complementarity between the latest reformulation techniques, such as Lagrangian and polyhedral approaches (the generation of columns and cutting planes), non-linear programming tools (quadratic programming, semi-definite, and other convex relaxations), and graph theoretic tools (for induced properties and implicit representations of solutions). Our focus is on deterministic optimization approaches based on mathematical programming, but our experience extends to stochastic programming, constraint programming, and graph theory. Through industrial partnerships, the team targets large scale problems such as those arising in network design, logistic (routing problems), scheduling, cutting and packing problems, production planning and healthcare logistic.

Key words

• Reformulation and decomposition appraoches in Mixed Integer Programming (MIP)
• Polyhedral approaches for MIPs (cut generation),
• Lagrangian approaches for MIPs (column generation),
• Mixed Integer Non-linear programming (MINLP) and quadratic (SDP) approaches,
• Stochastic programming,
• Inputs for graph theory and combinatorial optimization (Polyhedral Combinatorics),
• Inputs from constraint programming,
• Cooperation between techniques,
• Development of generic codes and specific tools: branch-and-price, parallel branch-and-bound