Section: Overall Objectives

Overall Objectives

Keywords: Reformulation techniques in Mixed Integer Programming (MIP), Polyhedral approaches (cut generation), Robust Optimization, Approximation Algorithms, Extended formulations, Lagrangian Relaxation (Column Generation) based algorithms, Dantzig and Benders Decomposition, Primal Heuristics, Graph Theory, Constraint Programming.

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: long term investment budgeting and activity planning, tactical management of scarce resources, or the control of day-to-day operations. In many optimization problems that arise in decision support applications the most important decisions (control variables) are discrete in nature: such as on/off decision to buy, to invest, to hire, to send a vehicle, to allocate resources, to decide on precedence in operation planning, or to install a connection in network design. Such combinatorial optimization problems can be modeled as linear or nonlinear programs with integer decision variables and extra variables to deal with continuous adjustments. The most widely used modeling tool consists in defining the feasible decision set using linear inequalities with a mix of integer and continuous variables, so-called Mixed Integer Programs (MIP), which already allow a fair description of reality and are also well-suited for global optimization. The solution of such models is essentially based on enumeration techniques and is notoriously difficult given the huge size of the solution space.

Commercial solvers have made significant progress but remain quickly overwhelmed beyond a certain problem size. A key to further progress is the development of better problem formulations that provide strong continuous approximations and hence help to prune the enumerative solution scheme. Effective solution schemes are a complex blend of techniques: cutting planes to better approximate the convex hull of feasible (integer) solutions, extended reformulations (combinatorial relations can be formulated better with extra variables), constraint programming to actively reduce the solution domain through logical implications along variable fixing based on reduced cost, Lagrangian decomposition methods to produce powerful relaxations, and Bender's decomposition to project the formulation, reducing the problem to the important decision variables, and to implement multi-level programming that models a hierarchy of decision levels or recourse decision in the case of data adjustment, primal heuristics and meta-heuristics (greedy, local improvement, or randomized partial search procedures) to produce good candidates at all stage of the solution process, and branch-and-bound or dynamic programming enumeration schemes to find a global optimum, with specific strong strategies for the selection on the sequence of fixings. The real challenge is to integrate the most efficient methods in one global system so as to prune what is essentially an enumeration based solution technique. The progress are measured in terms of the large scale of input data that can now be solved, the integration of many decision levels into planning models, and not least, the account taken for random (or dynamically adjusted) data by way of modeling expectation (stochastic approaches) or worst-case behavior (robust approaches).

Building on complementary expertise, our team's overall goals are threefold:

$\left(i\right)$ Methodologies:

To design tight formulations for specific combinatorial optimization problems and generic models, relying on delayed cut and column generation, decomposition, extended formulations and projection tools for linear and nonlinear mixed integer programming models. To develop generic methods based on such strong formulations by handling their large scale dynamically. To generalize algorithmic features that have proven efficient in enhancing performance of exact optimization approaches. To develop approximation schemes with proven optimality gap and low computational complexity. More broadly, to contribute to theoretical and methodological developments of exact and approximate approaches in combinatorial optimization, while extending the scope of applications and their scale.

$\left(ii\right)$ Problem solving:

To demonstrate the strength of cooperation between complementary exact mathematical optimization techniques, dynamic programming, robust and stochastic optimization, constraint programming, combinatorial algorithms and graph theory, by developing “efficient” algorithms for specific mathematical models. To tackle large-scale real-life applications, providing provably good approximate solutions by combining exact, approximate, and heuristic methods.

$\left(iii\right)$ Software platform & Transfer:

To provide prototypes of modelers and solvers based on generic software tools that build on our research developments, writing code that serves as the proof-of-concept of the genericity and efficiency of our approaches, while transferring our research findings to internal and external users.