Scientific Axes

  • Extended formulations
    • Column generation techniques
    • Network-flow reformulations
  • Optimization and uncertainty
    • Robust optimization
    • Risk measures
  • Operations research
    • Vehicle routing problems
    • Scheduling
    • Packing problems
    • Industrial applications

Our research

Context

Nowadays, integer programming based methods are able to solve effectively a large number of classic combinatorial optimization problems (travelling-salesman, knapsack, facility location problems). Dramatic improvements on benchmarks were obtained due to better linear programming solvers, better (re)formulations, new polyhedral results, new efficient algorithms, fine-tuned implementations, and more powerful computers.

Practitioners are now trying to tackle more advanced problems where the degree of complexity of the systems to optimize has increased substantially. In particular, numerous factors should be taken into account in the decision process: ecological impact, new regulations, presence of commercial partners or aggressive competitors, limitation on previously abundant resources, and so forth. Many problems also come with uncertain parameters (energy production, consumer behavior, weather, disasters, resource breakdowns…), and have to be solved in a dynamic environment, where solutions have to be modified/reoptimized on-the-fly to account for last-minute changes.

Objectives

In this new project, our main objective is to propose new mathematical models, algorithms, and efficient implementations of these algorithms to deal with families of integer programming problems arising from these complex systems, which are out-of-reach for the most recent optimization methods. Although universal algorithms able to deal with all types of constraints cannot be achieved in practice, we will seek results that are as broadly applicable as possible by designing so-called generic methods i.e. methods that address abstract mathematical models that can be later specialized for a large number of problems. We will mainly rely on two families of mathematical tools: decomposition techniques and extended formulations.

Decomposition methods are valuable tools to address complex optimization problems. Beyond the obvious advantages of the divide-and-conquer paradigm, they offer a way to produce stronger formulations, effective algorithms applicable to a wide range of problems, and they allow to use the right mathematical tool for each subproblem. Several issues have to be addressed when one wants to tackle modern integrated real-life problems by the means of decomposition methods. An important limitation of these methods is that they are generally efficient only for problems with a specific structure (typically independent subproblems connected by few common constraints). Many problems we address in this new project do not have this decomposable structure, or it is broken by so-called non-robust cuts, which are applied during the resolution process. In this case, new decomposition methods are needed to deal effectively with these connecting constraints. Another issue stems from the large number of different subsystems. A methodological challenge is to find a good trade-off between the quantity of information passed from one subproblem to another and the difficulty to integrate the common information into them.

Extended formulations will also be a focus of our team. The last ten years have seen much progress in this field, which aims at reformulating effectively a problem/polyhedron with the help of (exponentially many) additional variables. In particular, network-flow formulations have received an increasing interest from the community. A considerable dif- ficulty to overcome when dealing with such a formulation is to handle its size. One of the most promising paths is to study so-called aggregation and disaggregation techniques, where the level of detail of the formulation is modified iteratively. Similar approaches are popular in other fields of applied mathematics, where detailed information are only needed in some specific parts of the model. In integer programming, determining the suitable level of precision needed for a given subsystem is a major challenge, since the combinatorial structure of the subproblem preclude techniques based on derivatives. Although preliminary results indicate that one can achieve considerable improvements for some specific problems, there is a lack of a theoretical framework that would allow to develop these techniques for a larger class of polyedral structures.

We will use our methodological tools to address robust optimization, which is an increasingly popular approach to handle the uncertainty arising in mixed-integer linear optimization problems. This optimization paradigm describes the variability of the uncertain parameters through bounded uncertainty sets (and thus replacing the expectation, used in stochastic optimization, with the worst-case objective realization). In particular, we plan to study robust problems with integer recourse. From a theoretical point of view, these problems are known to be Σ2p-complete in general (and thus simply verifying that a solution is feasible is an NP-hard problem). We will work on determining the frontier between tractable and non-tractable problems by studying the structure of specific subsets of robust problems characterized by: their deterministic counterpart; their uncertainty set; and the difficulty of optimizing the recourse subproblem. Our first steps in this direction show that decomposition methods and extended formulations can be instrumental in achieving this objective.

Applications and software

We will keep in mind the fact that our impact will be maximized if we are able to develop high-level modeling tools and solvers, which can be used by colleagues and O.R. scientists in academy and in companies. State-of-the-art optimization methods are indeed often too hard to use, or take too much time to adapt to a new problem, and are not used outside a small community of experts.

Although our methodologies are designed for abstract integer programming models, our impact will more likely be important in some specific application fields, including energy, and supply-chain. In both fields, our objectives are in line with aspirations of modern societies (reducing the pollution, improving the sustainability of human activities, including a better and more robust design of supply-chains). Our optimization tools will be useful to accompany the profound shifts that are needed in these sectors, by taking into account the interconnection between the different problems faced by the companies.

In energy, the main challenges we face are related to the uncertainty of both production and consumption. The uncertainty in production grows with the development of renewable energy production, while uncertainty in consumption remains driven by weather. This leads to robust and/or stochastic optimization problems of large size, which push our methodologies to their limits. A typical problem is to ensure the technical feasibility of some energy transition scenarios where the percentage of nuclear power in the energetic mix decreases, leading to an increasing level of uncertainty.

Supply Chain and logistics are also fertile playgrounds for our research. In particular, successful applications in routing, production planning, inventory control, warehouse optimization, or network design are numerous. Besides, new technologies such as the internet of things or physical internet bring new core optimization problems and the need for new relevant mathematical models and solutions approaches. The main challenges are to deal with integrated problems, including location decisions, inventory, routing, packing, employee timetabling, among others. Current methods tend to take tactical and operational decisions independently despite the fact that they are interrelated problems. Supply chains also have to be robust to uncertain parameters (from regular variations of the system parameters to disaster management).