2025Activity report​​Project-TeamEDGE

3.1 Decomposition​‌ methods

Dantzig-Wolfe decomposition 39​​ is a well-established approach​​​‌ for solving hard and/or​ large-scale combinatorial optimization problems.​‌ Problems that are originally​​ formulated as Mixed-Integer Programming​​​‌ problems (MIPs) are reformulated​ by defining a (generally​‌ exponential) number of variables​​ which correspond to the​​​‌ solutions of subproblem(s) obtained​ by subsets of variables​‌ and constraints of the​​ original MIP formulation. To​​​‌ solve the linear approximation​ of the Dantzig-Wolfe reformulation,​‌ the column generation procedure​​ is employed, which iteratively​​​‌ generates missing variables by​ solving the subproblem(s). Cut​‌ generation is then employed​​ to strengthen the linear​​​‌ approximation, and branching is​ performed to find an​‌ optimal solution to the​​ problem. The overall approach​​​‌ is called the branch-cut-and-price​ (BCP) method 42.​‌ Recent advances, including those​​ developed by our previous​​​‌ project team ReAlOpt, helped​ significantly improve the efficiency​‌ of general-purpose BCP algorithms.​​ To use these algorithms​​​‌ one just has to​ specify the master problem,​‌ and a formulation or​​ an algorithm to solve​​​‌ the column generation subproblem.​ The improvements include stabilization​‌ 65, pre-processing, diving​​ heuristics 73, and​​​‌ strong branching, among others.​ Generic BCP codes implementing​‌ these improvements made the​​ branch-cut-and-price approach more accessible​​​‌ to users.

A major​ limitation of BCP algorithms​‌ is their inefficiency when​​ they face constraints that​​ break the decomposable structure​​​‌ of the problem. Prominent‌ examples are synchronisation and‌​‌ precedence constraints 43.​​ Moreover, it became clear​​​‌ recently that many efficient‌ BCP approaches are "non-robust",‌​‌ i.e., column and​​ cut generation are interdependent.​​​‌ Thus, for every subproblem‌ type, dedicated cut-generation approaches‌​‌ should be considered. Few​​ such approaches are known​​​‌ in the literature 40‌,63. Their‌​‌ development for different families​​ of cutting planes and​​​‌ different subproblem types is‌ a very promising research‌​‌ direction. Devising BCP algorithms​​ for problems that do​​​‌ not have the decomposability‌ property is a difficult‌​‌ and high-risk task. However,​​ in the case of​​​‌ success, the impact on‌ the practice of Operations‌​‌ Research would be significant.​​

Our numerical experience shows​​​‌ that generic BCP approaches‌ 48,49 (in‌​‌ which the subproblems are​​ solved as generic MIPs)​​​‌ are rarely competitive with‌ the traditional branch-and-cut method‌​‌ used in widely available​​ and highly efficient MIP​​​‌ solvers. On the other‌ hand, very efficient BCP‌​‌ approaches specialized for particular​​ problems exist in the​​​‌ scientific literature. In such‌ approaches, subproblems are of‌​‌ a certain type and​​ are solved by fast​​​‌ specialized algorithms. These ad-hoc‌ BCP approaches are however‌​‌ rarely used in practice​​ due to the complexity​​​‌ of their implementation 63‌, 71. An‌​‌ important goal of our​​ project is to propose​​​‌ innovative methods that have‌ the efficiency of the‌​‌ most advanced specialized algorithms​​ in the literature, yet​​​‌ can be applied to‌ many practical cases. This‌​‌ can be done by​​ developing BCP algorithms which​​​‌ are not completely generic‌ (i.e., they‌​‌ cannot be applied to​​ any model obtained by​​​‌ Dantzig-Wolfe reformulation) but can‌ be used for large‌​‌ classes of combinatorial optimization​​ problems. There is a​​​‌ clear need for efficient‌ and reusable semi-generic approaches‌​‌, that can be​​ applied to a large​​​‌ number of problems inside‌ a specific class. We‌​‌ have identified several types​​ of subproblems that are​​​‌ often encountered in practical‌ applications as substructures: resource-constrained‌​‌ paths in graphs 54​​ and hyper-graphs 37,​​​‌ constrained network flows, and‌ decision diagrams 28.‌​‌ Developing efficient algorithms that​​ can be applied to​​​‌ the broadest possible class‌ of such subproblems is‌​‌ a hard task. We​​ will seek the right​​​‌ trade-off between generality and‌ efficiency.

Recently, we have‌​‌ developed the first "semi-generic"​​ BCP solver, VRPSolver, which​​​‌ relies on solving resource‌ constrained shortest path subproblems‌​‌ 64. We have​​ shown that this solver​​​‌ can be successfully applied‌ to many vehicle routing‌​‌ variants and some packing​​ problems. An open question​​​‌ is whether there are‌ other classes of problems‌​‌ which can be efficiently​​ solved by "semi-specialized" BCP​​​‌ solvers. Scheduling and network‌ design problems are good‌​‌ candidates for such classes.​​ Capabilities of current BCP​​​‌ solvers however need to‌ be extended to efficiently‌​‌ handle these problems. One​​ of the drawbacks of​​​‌ our solver is the‌ absence of good embedded‌​‌ heuristics to quickly find​​ feasible solutions. Diving heuristics​​​‌ 73 can in principle‌ be used, but their‌​‌ speed and performance are​​​‌ generally not satisfactory.

Another​ challenge is to design​‌ a modelling paradigm that​​ can produce formulations for​​​‌ "semi-specialized" BCP solvers. In​ this context, defining a​‌ MIP and applying the​​ standard Danzig-Wolfe reformulation technique​​​‌ is cumbersome as the​ subproblems cannot be easily​‌ defined as MIPs. New​​ innovative modelling paradigms should​​​‌ be developed to simplify​ the problem definition and​‌ thus extend the usage​​ of BCP approaches. They​​​‌ should be simple enough​ to attract non-specialists in​‌ the domain, and complex​​ enough to pass the​​​‌ structural information to the​ BCP solver. This is​‌ mandatory to achieve state-of-the-art​​ performance. One can find​​​‌ inspiration in the notion​ of global constraints designed​‌ in the field of​​ Constraint Programming.

Benders' decomposition​​​‌ 27 is also becoming​ increasingly effective for several​‌ benchmark problems. Recent methods​​ based on this reformulation​​​‌ approach involve solving many​ similar subproblems repeatedly, and​‌ make use of sophisticated​​ stabilization techniques. We plan​​​‌ to build on the​ knowledge developed on Dantzig-Wolfe​‌ decomposition to develop techniques​​ to improve Benders' decomposition,​​​‌ which do not use​ any assumption on the​‌ specific structure of the​​ subproblem. A considerable challenge​​​‌ is to find effective​ methods for handling integer​‌ subproblems in a generic​​ manner.

Another way to​​​‌ improve Benders' decomposition tools​ is to use machine​‌ learning techniques. Such algorithms​​ can also be used​​​‌ to parameterize the different​ parts of the method​‌ or discover some information​​ to help the convergence​​​‌ of these algorithms. This​ is a promising path​‌ for solving stochastic programs​​ with a large number​​​‌ of scenarios. Several scientific​ questions have to be​‌ addressed, including the possible​​ adaptation of stabilization techniques​​​‌ that need a complete​ dual information for proving​‌ the convergence.

In line​​ with the challenges highlighted​​​‌ above, one of our​ first objectives is to​‌ improve the genericity of​​ our BCP solver for​​​‌ the resource constrained path​ structure. For the moment,​‌ it supports only models​​ with standard additive resources.​​​‌ We intend also to​ cover the case when​‌ cost and resource consumption​​ of the current arc​​​‌ in the path depends​ not only on the​‌ arc itself, but also​​ on the accumulated resource​​​‌ consumption of previous arcs​ in the path. This​‌ would allow to solve​​ several important classes of​​​‌ problems such as electric​ vehicle routing problems, and​‌ scheduling problems with additive​​ objective functions much more​​​‌ efficiently. This implies improving​ both the algorithms used​‌ and the modelling capabilities​​ of the solver to​​​‌ support more general resources.​

In the longer term,​‌ we plan to develop​​ semi-generic BCP approaches and​​​‌ solvers for problems which​ do not contain the​‌ resource constrained path structure​​ in graphs. Alternative structures​​​‌ which can be considered​ are spanning trees, network-flow​‌ problems in hyper-graphs, context-free​​ grammars (both mentioned in​​​‌ Section 3.2), and​ decision diagrams.

Another interesting​‌ idea to explore in​​ this direction is developing​​​‌ decomposition approaches for multi-stage​ sequential decision-making problems under​‌ uncertainty. Such problems can​​ be modeled as multi-agent​​​‌ Markov Decision Processes (MDP).​ We believe that mathematical​‌ programming decomposition algorithms in​​ which sub-problems are single-agent​​ MDPs solved by dynamic​​​‌ programming constitute a very‌ promising alternative to currently‌​‌ used approaches for multi-agent​​ MDPs. Moreover, there are​​​‌ currently no approaches for‌ such problems which provide‌​‌ exact solutions and non-trivial​​ valid bounds on the​​​‌ optimal value.

3.2 Extended‌ formulations

Many successful extended‌​‌ formulations are based on​​ network-flow models. These​​​‌ models have excellent polyhedral‌ properties, since the constraint‌​‌ matrix of a flow​​ problem is totally unimodular,​​​‌ and thus all extreme-point‌ solutions of the linear‌​‌ program related to this​​ subsystem are integer if​​​‌ the right-hand sides of‌ the constraints are integer.‌​‌ Additional constraints generally break​​ this property, but in​​​‌ many cases, the linear‌ relaxation remains of excellent‌​‌ quality.

Network-flow reformulations can​​ be obtained when all​​​‌ or parts of discrete‌ optimization problems can be‌​‌ described by regular or​​ algebraic languages, or​​​‌ by recursive (such as‌ dynamic programming) formulations, on‌​‌ top of which additional​​ constraints such as resource​​​‌ constraints, disjunctions, are specified.‌ Karp and Held 55‌​‌ provided a systematic approach​​ to building dynamic programming​​​‌ recurrence equations for a‌ large class of optimization‌​‌ problems by characterizing the​​ representation of discrete decision​​​‌ processes by monotone sequential‌ decision processes. Martin et‌​‌ al. 61 characterized discrete​​ optimization problems that can​​​‌ be solved via dynamic‌ programming using directed hypergraphs.‌​‌ The formalism of sequential​​ decision processes allows to​​​‌ build an internal representation‌ of the sequential structure‌​‌ using network-flows in state-graphs​​ or hypergraphs. Additional constraints​​​‌ can be embedded in‌ this representation by increasing‌​‌ the size of the​​ network, for example by​​​‌ discretizing quantities such as‌ time (scheduling), load (vehicle‌​‌ routing), or width (bin-packing)​​ 50. This has​​​‌ several advantages: 1) enforcing‌ the consideration of constraints‌​‌ using the graph structure​​ (that is convexifying these​​​‌ constraints), 2) easing the‌ modeling of complex constraints,‌​‌ 3) facilitating the consideration​​ of resource-dependent parameters 75​​​‌.

The main drawback‌ of these formulations is‌​‌ their typically exponential or​​ pseudo-polynomial number of variables​​​‌ and constraints. This‌ is different from models‌​‌ that arise from a​​ Dantzig-Wolfe decomposition, which have​​​‌ an exponential number of‌ variables, but a generally‌​‌ small number of constraints.​​ The size of network-flow​​​‌ models is usually far‌ too large to make‌​‌ them solvable by modern​​ integer programming, SAT or​​​‌ constraint programming solvers.

To‌ overcome this limitation, aggregation‌​‌ and disaggregation techniques,​​ based either on a​​​‌ scaling of the input‌ parameters or on aggregating‌​‌ nodes of the network,​​ are good candidates. As​​​‌ they generally make use‌ of sub-routines, they allow‌​‌ an efficient hybridization of​​ different optimization paradigms. Several​​​‌ methods sharing common ideas‌ have been introduced in‌​‌ different communities. For solving​​ dynamic programs, techniques based​​​‌ on iterative state-space relaxations‌ 35 have proved their‌​‌ efficiency since the 1980s.​​ The most popular methods​​​‌ are the decremental state-space‌ relaxation 31, 70‌​‌ and the successive sublimation​​ dynamic programming 53.​​​‌ In the field of‌ MIP models, the most‌​‌ promising algorithms for solving​​ exponentially-large network-flow formulations are​​​‌ also based on an‌ increasingly refined series of‌​‌ relaxations (see 36,​​​‌32,69).​ These methods produce initial​‌ models with fewer variables​​ and fewer constraints than​​​‌ the original ones and​ iteratively refine them after​‌ identifying new variables and/or​​ constraints to add. Although​​​‌ these methods have been​ shown to be efficient​‌ for several benchmark problems,​​ only few generic methods​​​‌ have been proposed (see​ 33 and 57).​‌

Iterative aggregation/disaggregation techniques have​​ some relationship to other​​​‌ methods. They share similarities​ with Benders' decomposition or​‌ Logic-based Benders' decomposition. Both​​ methods rely initially on​​​‌ a relaxation of the​ problem. However, in Benders'​‌ decomposition constraints are iteratively​​ introduced to discard infeasible​​​‌ solutions, while iterative aggregation/disaggregation-based​ techniques may also introduce​‌ new variables. Similarities with​​ optimization methods using decision​​​‌ diagrams constructed by (iterative)​ state aggregation procedures can​‌ also be highlighted 28​​. Decision diagrams are​​​‌ graphs storing possible variable​ assignments satisfying some constraints​‌ and are particularly used​​ in CP/SAT solvers.

A​​​‌ conclusion of the above​ is that similar aggregation​‌ and disaggregation techniques are​​ used under different names​​​‌ in different fields (MIP,​ DP, CP/SAT), leading to​‌ a scattered scientific literature.​​ Further, most of the​​​‌ proposed techniques are problem-dependent​ (with the notable exception​‌ of decision diagrams, which​​ offer a more general​​​‌ setting, although we are​ not aware of any​‌ generic implementation). Our goal​​ is to go in​​​‌ the direction of developing​ a unifying formalism and​‌ express the main methods​​ of the literature within​​​‌ this formalism. This generic​ view aims to bring​‌ together methods whose proximity​​ has never really been​​​‌ highlighted. Existing algorithms may​ benefit from algorithmic components​‌ that have proven their​​ effectiveness in other contexts.​​​‌ As an example, existing​ MIP algorithms could benefit​‌ from state-of-the-art approaches developed​​ for decision diagrams.

We​​​‌ will study and design​ effective methods based on​‌ aggregating and disaggregating models.​​ It is necessary to​​​‌ develop a high-level modeling​ tool to specify these​‌ models only implicitly. The​​ use of algebraic languages​​​‌ to produce such higher-level​ formulations is a direction​‌ we are considering to​​ explore. We also believe​​​‌ that a primal-dual solution​ approach is worth exploring.​‌ Such an approach will​​ rely on the local​​​‌ refinement of a coarse​ representation of the global​‌ problem when needed. The​​ idea is to derive​​​‌ primal and dual bounds​ on the objective value​‌ of the problem with​​ a lower computational effort​​​‌ compared to working with​ the original model. We​‌ can distinguish two types​​ of aggregation: 1) a​​​‌ conservative aggregation ensures that​ every solution of the​‌ original model is also​​ a solution of the​​​‌ aggregated model (i.e., the​ aggregated model is a​‌ relaxation of the original​​ model) and 2) a​​​‌ heuristic aggregation ensures that​ every solution of the​‌ aggregated model is also​​ a solution of the​​​‌ original model. After projecting​ the original model onto​‌ an aggregated one, we​​ aim to converge to​​​‌ an optimal solution without​ reaching the size of​‌ the original model. To​​ keep the model tractable,​​​‌ one can make use​ of primal and dual​‌ information from the different​​ aggregated models to fix​​ variables values (using Lagrangian​​​‌ filtering for example). We‌ will focus on finding‌​‌ a systematic way to​​ 1) aggregate an initial​​​‌ model to yield either‌ a relaxation or a‌​‌ restriction and 2) iteratively​​ disaggregate the current model​​​‌ for obtaining better dual‌ bounds. A path worth‌​‌ exploring is to dynamically​​ aggregate the models taking​​​‌ advantage of the information‌ learned in the current‌​‌ phase to build stronger​​ models 52. We​​​‌ will also study an‌ emerging technique consisting in‌​‌ the joint use of​​ several aggregated models with​​​‌ decision synchronization 62,‌58 which can be‌​‌ helpful to derive stronger​​ bounds and to keep​​​‌ tractable network-flow models.

For‌ designing heuristics, the problems‌​‌ generated by dynamic programs​​ / algebraic languages are​​​‌ suited to so-called structured‌ learning techniques, where the‌​‌ objective is to learn​​ how to approximate a​​​‌ hard combinatorial problem (typically‌ a sequencing problem with‌​‌ resource constraints) by means​​ of a simpler problem​​​‌ (typically a shortest-path problem‌ on a graph). More‌​‌ classical learning techniques can​​ also be used to​​​‌ guess the right parameters‌ (lagrangian or surrogate multipliers,‌​‌ or to guess the​​ right decisions to make​​​‌ (state-space modification, relaxation of‌ some constraints, etc.).

In‌​‌ line with the challenges​​ highlighted above, we started​​​‌ to address automatic heuristic‌ for dynamic programs with‌​‌ side constraints based on​​ structured-learning techniques. This is​​​‌ a work that had‌ already begun in a‌​‌ collaboration between F. Clautiaux,​​ A. Froger and A.​​​‌ Parmentier (CERMICS). The objective‌ of the project is‌​‌ to determine the best​​ way to apply machine-learning​​​‌ techniques to obtain heuristics‌ via projection, pruning etc.‌​‌ To work on this​​ challenge, we collaborate with​​​‌ Centre Aquitain des Technologies‌ de l'Information et Électroniques‌​‌ (CATIE). Fulin Yan, a​​ student from INSA Rennes,​​​‌ has done an internship‌ with our team on‌​‌ this subject. We are​​ now waiting for a​​​‌ funding answer to propose‌ him a CIFRE PhD‌​‌ thesis.

We additionally started​​ to lay the scientific​​​‌ foundation for a generic‌ framework that embed various‌​‌ techniques from dynamic programming​​ based on regular languages,​​​‌ resource-constrained shortest path, and‌ decision diagrams. We are‌​‌ comparing the different elements​​ coming from the different​​​‌ fields (SAT / MIP‌ / heuristics), determining the‌​‌ common parts and analyzing​​ the main differences between​​​‌ them. Our objective is‌ to develop a common‌​‌ formalism and express the​​ most important methods of​​​‌ the literature using this‌ formalism. This is a‌​‌ work in progress between​​ F. Clautiaux, B. Detienne​​​‌ and A. Froger. We‌ hired Luis Lopes Marques‌​‌ as a PhD student​​ starting from October 2022​​​‌ to work on this‌ subject. This thesis is‌​‌ financed by our ANR​​ project AD-LIB.

In the​​​‌ near future, we will‌ design exact convergent methods‌​‌ based on aggregation/disaggregation techniques​​ (e.g., use of problem-dependent​​​‌ or primal/dual information) relying‌ on the generic framework‌​‌ cited above. We will​​ focus on finding a​​​‌ systematic way 1) to‌ aggregate an initial model‌​‌ to yield either a​​ relaxation or a restriction​​​‌ and 2) to iteratively‌ disaggregate the current model‌​‌ for obtaining better dual​​​‌ bounds. This is part​ of our ANR project​‌ AD-LIB.

We will also​​ study matheuristics for problems​​​‌ based on time-indexed models​. This work will​‌ focus on the ability​​ of the method to​​​‌ provide the best possible​ solution within a given​‌ time limit. This is​​ a challenge when solving​​​‌ operational problems where the​ decision-making time is limited.​‌ The key area of​​ research will be (i)​​​‌ how to disaggregate in​ a way that a​‌ good feasible solution can​​ be provided as fast​​​‌ as possible (search strategy)​ and (ii) how to​‌ modify infeasible solutions provided​​ by an aggregated model​​​‌ in order to make​ them feasible without impairing​‌ their cost. This is​​ also a part of​​​‌ the ANR project AD-LIB.​

Upon sucessful completion of​‌ the above objectives, we​​ may explore many extensions​​​‌ and generalizations to our​ framework. Among them, we​‌ may cite new mechanisms​​ to integrate several different​​​‌ state-space relaxations in the​ same solution process and​‌ extensions to non-linear constraints​​ and objective / dynamic​​​‌ programs based on different​ semi-rings than $(max‌,+)$ in​​ ${ℝ}^n$. In​​​‌ the longer term, we​ wish to explore the​‌ links with polyedral theory,​​ and develop extensions of​​​‌ the framework from regular​ languages to algebraic languages​‌ (and to extend our​​ algorithms from graph-based algorithms​​​‌ to hypergraph-based algorithms). Polyhedral​ theory can be used​‌ to improve the performance​​ of our algorithms for​​​‌ solving dynamic programs with​ side constraints, and to​‌ provide the equivalent of​​ the branch-and-cut algorithm for​​​‌ dynamic programs.

3.3 Structure​ analysis and problem specific​‌ studies

Polyhedral analysis 21​​ remains a part of​​​‌ our project. When integer​ linear programming methods are​‌ involved, information on the​​ structure of the polyhedron​​​‌ representing the feasible region​ is key for solving​‌ hard problems effectively. The​​ most spectacular success of​​​‌ this kind of methods​ can be found in​‌ Concorde 20, a​​ software dedicated to the​​​‌ traveling salesman problem. Network​ design has also been​‌ the subject of many​​ contributions (see e.g. 44​​​‌). Since we aim​ to propose methods that​‌ can apply to broad​​ classes of problems, we​​​‌ will focus on families​ of constraints/problems that occur​‌ in a large number​​ of practical problems (including​​​‌ capacity, disjunction, precedence or​ set-covering constraints). There are​‌ two promising directions that​​ we can follow in​​​‌ order to study these​ structures.

In the case​‌ where the linear relaxation​​ of an integer programming​​​‌ formulation has an excellent​ quality, but requests a​‌ large computational time, being​​ able to compute good​​​‌ dual solutions rapidly allows​ to provide useful dual​‌ bounds for combinatorial optimization​​ problems. This technique​​​‌ was used for the​ classical cutting-stock problem under​‌ the name dual-feasible functions​​ (see 23). These​​​‌ functions lead to bounds​ of linear complexity that​‌ have an excellent behaviour​​ on average. This concept​​​‌ has already been extended​ to several packing and​‌ location problems (see 56​​, 66). We​​​‌ plan to explore further​ extensions to common problem/constraint​‌ types.

Many hard problems​​ on graphs become easy​​ when the graph has​​​‌ a special structure 45‌, typically perfect graphs‌​‌ such as trees, interval​​ or triangulated graphs (see​​​‌ for example 59,‌ 72). In most‌​‌ problems, the graphs do​​ not belong to an​​​‌ easy class. However, one‌ can compute effective relaxations‌​‌ by exhibiting subgraphs of​​ suitable structure in these​​​‌ general graphs. Unfortunately for‌ many classes the problem‌​‌ of finding a subgraph​​ belonging to this class​​​‌ maximizing a certain criterion‌ is NP-hard. We plan‌​‌ to study methods for​​ finding efficient models to​​​‌ compute such relaxations.

In‌ line with the challenges‌​‌ highlighted above, our first​​ objective is to work​​​‌ on polyhedral analysis and‌ computational studies of formulations‌​‌ for the "best" interval​​ subgraph of a general​​​‌ graph. We have‌ identified several families of‌​‌ formulations, among them strong​​ formulations based on an​​​‌ exponential number of variables‌ and/or constraints. Pricing algorithms‌​‌ and separation problems have​​ to be studied in​​​‌ order to efficiently solve‌ these formulations. The same‌​‌ work can be undertaken​​ with chordal graphs, which​​​‌ offer a stronger relaxation‌ (since they are a‌​‌ superclass of interval graphs),​​ for a higher computational​​​‌ cost.

In the longer‌ term, we plan to‌​‌ work on the extension​​ of our work on​​​‌ so-called dual feasible functions‌ to more complex cases.‌​‌ The theory of superadditive​​ and dual-feasible functions have​​​‌ mainly been studied in‌ the case of a‌​‌ single knapsack constraint. Extensions​​ to the intersection of​​​‌ the knapsack polytope with‌ polytopes related to highly‌​‌ structured constraints (such as​​ precedences, or disjunctions) is​​​‌ already a hard challenge.‌

More generally, we plan‌​‌ to work on several​​ aspects related to polyedral​​​‌ theory: study of extended‌ formulations generated by algebraic‌​‌ grammars. A possible objective​​ is to use implicit​​​‌ formulations expressed in different‌ state spaces to derive‌​‌ efficient cuts for a​​ base formulation ; determining​​​‌ whether considering the structure‌ of the problems will‌​‌ be a stronger tool​​ to derive dual-feasible functions​​​‌ than learning to guess‌ the best dual values‌​‌ from the input parameters​​ (for instance, using structured​​​‌ learning to compute a‌ smaller dual polytope from‌​‌ an initial one) ;​​ studying decomposition schemes based​​​‌ on graph decomposition techniques,‌ such as path or‌​‌ tree-decompositions.

4.1 Integrated problems​​​‌

Most practical optimization problems​ are complex, i.e., they​‌ involve different types of​​ decisions to be made.​​​‌ Such problems are commonly​ called integrated. They​‌ often involve different time​​ scales related to strategic,​​​‌ tactical and operational decisions.​ A classical approach to​‌ solve such problems is​​ their disintegration into independent​​​‌ problems or stages, where​ the solution of a​‌ stage is the input​​ for next one. We​​​‌ prefer the term "disintegration"​ here instead of "decomposition"​‌ to avoid confusion with​​ decomposition approaches presented above.​​​‌ The disintegration approach usually​ results in highly sub-optimal​‌ solutions. There is large​​ potential for improving the​​​‌ quality of solutions if​ two and more decision​‌ stages are considered together.​​

Recently there has been​​​‌ an increase in interest​ for solving integrated optimization​‌ problems. Such problems may​​ involve for example integration​​​‌ of production and outbound​ distribution (production-distribution problem 47​‌), facility location and​​ vehicle routing (location-routing problem​​​‌ 74), inventory management​ and vehicle routing (inventory​‌ routing problem 38),​​ and different levels of​​​‌ distribution (two-echelon routing 60​ and cross-docking based distribution).​‌

As we point out​​ above, integrated problems are​​​‌ common in practice but​ difficult to solve, since​‌ they involve synchronization between​​ stages, and different time​​​‌ scales in different stages.​ Moreover, different classes of​‌ problems are usually encountered​​ in different stages. This​​​‌ means that different exact​ approaches are usually applied​‌ to solve such classes​​ of problems. It is​​​‌ often not known how​ one can efficiently combine​‌ these approaches to solve​​ an integrated problem. Thus,​​​‌ heuristic algorithms are used​ in a vast majority​‌ of cases. However, we​​ believe that advances in​​​‌ efficiency and ease of​ use of exact algorithms​‌ and decomposition algorithms in​​ particular allow us to​​ think of applying them​​​‌ here.

Exact approaches are‌ usually limited to small‌​‌ instances of integrated problems,​​ while real-life instances are​​​‌ tackled by heuristic approaches.‌ Nevertheless, for estimating the‌​‌ quality of these heuristics​​ we need approaches that​​​‌ obtain lower bounds of‌ a good quality, even‌​‌ for large scale instances.​​ We think that BCP​​​‌ algorithms are good candidates‌ to obtain such bounds.‌​‌ The column generation approach​​ has however several drawbacks​​​‌ when applied to large-scale‌ integrated problems. When solving‌​‌ pure academic problems, the​​ bottleneck of BCP algorithms​​​‌ is usually the solution‌ of the pricing problem.‌​‌ On the contrary, when​​ dealing with integrated real-life​​​‌ problems, the size of‌ the master problem may‌​‌ become too large and​​ the solution of the​​​‌ restricted master LP becomes‌ a bottleneck. One possible‌​‌ approach to tackle this​​ problem is a dynamic​​​‌ aggregation of constraints in‌ the master LP 34‌​‌. Another approach could​​ be to use machine​​​‌ learning techniques to choose‌ “good” columns from a‌​‌ large pool generated by​​ the pricing problem. The​​​‌ goal here is to‌ help the column generation‌​‌ algorithm converge faster in​​ the case of a​​​‌ “heavy” master problem or‌ to find “compatible” columns‌​‌ to obtain better primal​​ solutions.

Column generation-based algorithms​​​‌ may also prove useful‌ for obtaining good feasible‌​‌ solutions for integrated problems.​​ A potential directon is​​​‌ to develop matheuristics, i.e.‌, heuristic methods that‌​‌ make use of sophisticated​​ algorithms initially designed for​​​‌ exact methods. The goal‌ is to benefit from‌​‌ the two worlds: exact​​ methods to exploit the​​​‌ special structures of some‌ subproblems, and heuristics to‌​‌ produce solutions in a​​ small amount of time.​​​‌ Column generation-based matheuristics have‌ already shown good results‌​‌ for some integrated problems​​ 22. A common​​​‌ approach is to use‌ heuristics and/or column generation‌​‌ to obtain interesting columns​​ and then solve the​​​‌ restricted master problem as‌ a MIP with a‌​‌ time limit. Then the​​ set of columns can​​​‌ possibly be updated and‌ the restricted master is‌​‌ resolved. However, generic frameworks​​ for such approaches are​​​‌ absent, although they‌ would be highly welcome‌​‌ for a wide class​​ of problems.

Our initial​​​‌ efforts will be concentrated‌ on one or two‌​‌ well-chosen problems of this​​ type. The inventory routing​​​‌ problem (IRP) is probably‌ the most "academic" and‌​‌ simple to state example​​ of integrated problems which​​​‌ stays very hard to‌ solve for both exact‌​‌ and heuristic methods41​​. In this problem,​​​‌ the decision maker in‌ charge of the delivery‌​‌ is also in charge​​ of the stock level​​​‌ of his/her customer. IRP‌ is widely encountered in‌​‌ practice. The integration of​​ electric vehicles in transportation​​​‌ is also a timely‌ topic. Planning the charging‌​‌ operations of electric vehicles​​ is necessary to account​​​‌ for a wide variety‌ of costs (e.g., time-dependent‌​‌ energy costs), charging infrastructure​​ constraints (e.g., grid restrictions,​​​‌ limited number of chargers),‌ battery degradation, and the‌​‌ potential integration of Vehicle-to-Grid​​ technologies. Taking this variety​​​‌ of constraints into account‌ introduces complex coupling decisions‌​‌ between charging and routing,​​​‌ which leads to integrated​ problems.

We plan to​‌ design a comprehensive modelling​​ and solution framework for​​​‌ planning the charging activities​ of a fleet of​‌ electric vehicles considering time-dependent​​ costs and the potential​​​‌ integration of Vehicle-to-Grid technologies.​ Particular attention is directed​‌ towards decreasing the maximum​​ power of energy required​​​‌ in the planning interval.​ This will be a​‌ joint work with O.​​ Jabali (Politecnico di Milano,​​​‌ Italy) that has already​ began with a master​‌ student from Politecnico di​​ Milano visiting our research​​​‌ team for 4 months​ last year and studying​‌ the case of a​​ fleet of electric buses.​​​‌ Our objectives are to​ design advanced mathematical methods​‌ to produce high-quality solutions​​ in a time efficient​​​‌ manner as well as​ to propose an exact​‌ solution method to solve​​ electric routing problems (E-VRPs)​​​‌ with limited charging infrastructure​ constraints (based on a​‌ previous work 46)​​ using a Branch-and-cut-and-price algorithm.​​​‌ We will investigate the​ trade-offs that exist between​‌ driving time and energy​​ consumption (e.g., existence of​​​‌ alternative paths, speed reduction)​ either by refining the​‌ abstraction of the road​​ network on which E-VRPs​​​‌ are defined or by​ working directly with the​‌ road network.

In the​​ long term, our objective​​​‌ is to be able​ to cope with an​‌ increasing amount of integrated​​ problems, with a focus​​​‌ on supply-chain applications (scheduling,​ location, inventory, routing, etc.).​‌ Our work on this​​ topic will benefit from​​​‌ our findings on new​ decomposition methods. Once our​‌ main objectives are achieved,​​ we will explore methodological​​​‌ tools to take different​ sources of uncertainty into​‌ account (e.g., energy consumption​​ of electric vehicles, time-dependent​​​‌ energy costs) using robust​ optimization or stochastic programming​‌ paradigms.

4.2 Robust optimization​​

In most decision making​​​‌ problems the data used​ in the mathematical model​‌ is subject to some​​ form of uncertainty. This​​​‌ uncertainty can be caused​ by measurement errors, variability​‌ or the time duration​​ of the processes under​​​‌ study, or simple lack​ of access to reliable​‌ data. Incomplete information can​​ also come from the​​​‌ presence of competitors or​ adversarial individuals whose policies​‌ are not known to​​ the decision maker. Recent​​​‌ events have also shown​ that the capability to​‌ resist to major disasters​​ is an issue for​​​‌ important organizations and critical​ infrastructure.

There are two​‌ commonly accepted paradigms that​​ are used to incorporate​​​‌ uncertainty in mathematical programming:​ stochastic optimization (including chance-constraints),​‌ and robust optimization.​​ In stochastic optimization, one​​​‌ assumes that a probability​ distribution is known for​‌ the uncertain parameters and​​ optimizes a statistical risk​​​‌ measure such as the​ expected value or the​‌ conditional value-at-risk. In this​​ new project, our main​​​‌ tool for dealing with​ uncertainty will be robust​‌ optimization. Unlike stochastic programming,​​ which requires exact knowledge​​​‌ of the probability distributions,​ robust optimization only describes​‌ the variability of the​​ uncertain parameters through bounded​​​‌ uncertainty sets. Further, replacing​ the risk measures employed​‌ in stochastic optimization, with​​ the worst-case realization, robust​​​‌ optimization is more adapted​ to applications where the​‌ decision-making process involves high​​ risks or adversarial participants.​​

In the last 20​​​‌ years, the robust optimization‌ field has seen significant‌​‌ progress. Static robust optimization​​ problems, which assume that​​​‌ all decisions are here-and-now,‌ have received considerable attention.‌​‌ They have been formulated​​ and studied with polyhedral,​​​‌ conic and ellipsoidal uncertainty‌ sets. From a complexity‌​‌ viewpoint, it has been​​ shown that these problems​​​‌ are barely harder than‌ their deterministic counterparts in‌​‌ most practical cases. From​​ the numerical viewpoint, mixed-integer​​​‌ linear (or second-order conic)‌ reformulations have been proposed‌​‌ and can handle large-scale​​ problems.

Despite these rather​​​‌ encouraging results, static models‌ suffer from over-conservatism. Indeed,‌​‌ in these models, no​​ recourse action can be​​​‌ taken to change or‌ adapt the solution once‌​‌ the uncertain values have​​ been revealed. This substantially​​​‌ limits the applicability of‌ the robust optimization paradigm‌​‌ since in most applications​​ that involve temporal decision-making,​​​‌ it is possible to‌ adapt the solution to‌​‌ (at least partially) mitigate​​ the effects of uncertainty.​​​‌

Acknowledging the importance of‌ adjustable models, the scientific‌​‌ community has started to​​ address solution methods for​​​‌ these problems. While it‌ is theoretically well-known that‌​‌ even two-stage linear programs​​ are NP-hard, approximate (affine​​​‌ decision rules) 26,‌ or exact (row-and-column generation‌​‌ algorithms) 25,76​​ solution methods for problems​​​‌ featuring continuous recourse variables‌ have been proposed in‌​‌ the literature. These two​​ sets of algorithmic tools​​​‌ have made it possible‌ to solve exactly or‌​‌ approximately a large number​​ of adjustable robust optimization​​​‌ problems with continuous recourse.‌ Several studies have also‌​‌ sought to understand the​​ quality of the bounds​​​‌ provided by affine decision‌ rules, as well as‌​‌ proposed extensions to piece-wise​​ affine functions.

The problems​​​‌ we wish to investigate‌ in this project are‌​‌ adjustable robust optimization problems​​ where recourse decisions are​​​‌ integer. The situation‌ is significantly more complex‌​‌ for this setting than​​ for the case of​​​‌ continuous recourse. The two‌ aforementioned approaches do not‌​‌ apply: affine decision rules​​ provide continuous recourse actions​​​‌ by construction, while the‌ separation problem in the‌​‌ row-and-column generation algorithm is​​ based on linear programming​​​‌ duality.

Having no theoretical‌ guarantees regarding their computational‌​‌ complexity, there are some​​ numerical algorithms that aim​​​‌ to solve adjustable robust‌ optimization problems with integer‌​‌ recourse approximately. They are​​ all based on simplifying​​​‌ the type of feasible‌ recourse actions, either by‌​‌ partitioning the uncertainty set​​ or by imposing that​​​‌ the recourse decisions should‌ be chosen among a‌​‌ predetermined finite set of​​ solutions (finite/K-adaptability). Unfortunately, these​​​‌ methods hardly scale up‌ and the recent results‌​‌ 29,51 are​​ limited to small problem​​​‌ instances, which can be‌ partially explained by the‌​‌ fact that they rely​​ on big-$M$ reformulations,​​​‌ known to yield poor‌ continuous relaxations.

In the‌​‌ following years, we plan​​ to develop exact and​​​‌ approximate solution methods for‌ adjustable robust optimization problems‌​‌ with integer recourse. On​​ the one hand, we​​​‌ will study relatively general‌ row-and-column generation algorithms that‌​‌ are based on stronger​​ continuous relaxations than what​​​‌ was done in the‌ literature (aforementioned network formulations‌​‌ and decision diagram-based approaches​​​‌ seem to be promising​ leads in achieving this​‌ goal). On the other​​ hand, we will focus​​​‌ on classes of specific​ robust models (special cases),​‌ which will be studied​​ both from a theoretical​​​‌ and a numerical perspective.​ Some of our efforts​‌ will be spent on​​ improving the efficiency of​​​‌ existing methods such as​ K-adaptability since these approaches​‌ could benefit from the​​ considerable numerical experience of​​​‌ the team.

We developed​ a first approach to​‌ dealing with binary recourse​​ decisions in the context​​​‌ of adjustable robust optimization​ problems with binary recourse​‌ in 24. The​​ main idea of this​​​‌ work is to convexify​ the recourse feasible region​‌ using a Dantzig-Wolfe reformulation.​​ Promising results were presented​​​‌ for the special case​ where the coupling constraints​‌ are deterministic and satisfy​​ additional technical assumptions. In​​​‌ this case, the inner​ maximization and minimization problems​‌ can be interchanged, resulting​​ in a large-scale deterministic​​​‌ equivalent model. We plan​ to extend this technique​‌ to the more general​​ case and to understand​​​‌ how to relax the​ aforementioned technical assumption.

In​‌ the near term, we​​ plan to carry out​​​‌ several projects to respond​ to the challenges we​‌ outline above. We plan​​ to study solution approaches​​​‌ for complex problems arising​ in future 5G networks​‌. This topic is​​ the subject of a​​​‌ CIFRE thesis supervised by​ Boris Detienne and Pierre​‌ Pesneau in collaboration with​​ Orange. We will also​​​‌ address complex network-design and​ location problems (topic of​‌ ANR project DE-SIDE, in​​ collaboration with Sobolev Institute​​​‌ and Kedge Business School).​ We will determine easy​‌ and hard cases for​​ robust multi-stage network-design problems,​​​‌ depending on the set​ of constraints, the definition​‌ of the uncertainty and​​ the possible second-stage actions,​​​‌ with a focus on​ integer recourse.

From a​‌ methodological perspective, we will​​ adress primal and dual​​​‌ bounds for two- and​ multi-stage adjustable robust optimization​‌ problems (topic of ANR-JCJC​​ project DROI which was​​​‌ granted to Ayse N.​ Arslan). Building upon the​‌ results of 24,​​ we propose to deal​​​‌ with constraint uncertainty in​ adjustable robust optimization using​‌ Lagrange and Fenchel duality,​​ which will provide dual​​​‌ bounds. Several issues need​ to be resolved in​‌ investigating this approach, such​​ as the optimization of​​​‌ the dual (infinite size)​ problems and how to​‌ close the duality gap.​​ We additionally propose to​​​‌ study improved decision rules​ for these problems.

In​‌ the long term, our​​ objectives in relation with​​​‌ this challenge are as​ follows. First, we want​‌ to design efficient approximate​​ approaches to solve multi-stage​​​‌ adjustable robust optimization problems​. Although exact methods​‌ seem to be out​​ of reach for the​​​‌ current state-of-the-art in the​ general case, we will​‌ also strive to identify​​ special cases which can​​​‌ be solved to exact​ optimality with numerically viable​‌ algorithms. Second, we seek​​ to bridge the gap​​​‌ between multi-stage integer robust​ optimization and combinatorial games​‌. Some similar concepts​​ are used in both​​​‌ types of problems (typically​ min-max-min problems have to​‌ be solved). This may​​ allow to disseminate our​​ techniques to other fields​​​‌ as well as adapt‌ results obtained for those‌​‌ fields to the context​​ of adjustable robust optimization.​​​‌

5.1 Impact of‌​‌ research results

Our work​​ 30 on a stochastic​​​‌ generation and transmission expansion‌ planning problem studied at‌​‌ RTE will help the​​ company in their future​​​‌ strategic studies (e.g., studies‌ similar to 68,‌​‌ 67). Specifically, we​​ show how to incorporate​​​‌ the French legislation1‌ that imposes that the‌​‌ number of hours with​​ energy not served should​​​‌ be in expectation less‌ than or equal to‌​‌ three per year in​​ the mathematical formulation of​​​‌ the expansion planning problem.‌ This work was part‌​‌ of the PhD thesis​​ of Xavier Blanchot.

We​​​‌ are also involved in‌ the PowDev project. The‌​‌ main objective of this​​ project is to evaluate​​​‌ and optimize the resilience‌ of power systems in‌​‌ the context of a​​ massive insertion of renewable​​​‌ energies. The project aims‌ to elaborate a comprehensive‌​‌ and integrated set of​​ decision support tools by​​​‌ considering extreme events in‌ present and future climates,‌​‌ the complexity of the​​ power grid, and socio-economic​​​‌ scenarios.

One of the‌ algorithms we proposed in‌​‌ 15 has been implemented​​ at the NGO Doctors​​​‌ Without Borders - Logistics‌ (Mérignac). Despite being very‌​‌ lightweight in terms of​​ resources and development, it​​​‌ is estimated to reduce‌ handling times by 40%‌​‌ compared to the previous​​ practice.

7.1 Latest software​​​‌ developments

8.1 Generic Machine-Learning-Augmented Beam​ Search for Resource-Constrained Shortest​‌ Path reformulations of Combinatorial​​ Optimization Problems

In this​​​‌ work, we propose a​ generic heuristic for the​‌ resource-constrained shortest path problem​​ derived from dynamic programming​​​‌ reformulations of hard combinatorial​ optimization problems. The approach​‌ is a machine-learning (ML)-augmented​​ beam search, where an​​ ML model serves as​​​‌ one of the scoring‌ functions to select candidate‌​‌ paths for expansion, complementing​​ lower and upper bound​​​‌ estimates. Our method offers‌ several key advantages. First,‌​‌ the path features used​​ by our model are​​​‌ generic and only derived‌ from the reformulation, without‌​‌ relying on any additional​​ problem-specific information beyond the​​​‌ graph structure and resource‌ constraints. Second, we manually‌​‌ designed and aggregated features​​ to obtain vectors of​​​‌ fixed length, enabling us‌ to train the model‌​‌ on small to medium-sized​​ instances and apply it​​​‌ to much larger instances.‌ We evaluate our algorithm‌​‌ on two benchmark problems:​​ the Single Machine Total​​​‌ Weighted Tardiness Problem and‌ the Temporal Knapsack Problem,‌​‌ each under two settings:​​ with and without access​​​‌ to optimal Lagrangian multipliers.‌ Our numerical experiments show‌​‌ that our integration of​​ ML into beam search​​​‌ improves its solution quality‌ in most cases.

Participants:‌​‌ François Clautiaux, Aurélien​​ Froger, Fulin Yan​​​‌.

8.2 An Efficient‌ Solver for Integral Flows‌​‌ in Decision Hypergraphs with​​ Applications to Orthogonal Knapsack​​​‌ Problems

We propose a‌ generic solver for computing‌​‌ integral flows in decision​​ hypergraphs, subject to upper​​​‌ bound constraints on some‌ hyperarcs. This framework captures‌​‌ an entire class of​​ cutting problems, including the​​​‌ guillotine 2-dimensional knapsack problem‌ (G2KP) -our primary focus.‌​‌ The main contribution of​​ our approach is the​​​‌ introduction of new generic‌ valid inequalities and their‌​‌ effective inclusion into a​​ labeling algorithm, using the​​​‌ concept of potentials. To‌ manage the size of‌​‌ the formulation, we developed​​ a hyperarc generation strategy​​​‌ that constructs only a‌ relevant subset of the‌​‌ vertices and hyperarcs. The​​ resulting speedup enables the​​​‌ efficient inclusion of our‌ new valid inequalities in‌​‌ the solving process. Computational​​ results on instances from​​​‌ the literature demonstrate the‌ strength of our approach.‌​‌

Our solver outperforms the​​ best algorithm known so​​​‌ far, and is the‌ first to close the‌​‌ optimality gap for all​​ instances of several well-known​​​‌ benchmarks.

Participants: François Clautiaux‌, Arthur Léonard.‌​‌

8.3 Multi-stakeholder insights on​​ integrating public transport for​​​‌ urban freight deliveries

This‌ work explores the integration‌​‌ of public transport networks​​ for urban freight deliveries​​​‌ within the framework of‌ Hyperconnected City Logistics (HCL),‌​‌ focusing on multi- stakeholder​​ perspectives. By synergizing freight​​​‌ and passenger networks, the‌ study optimizes parcel consolidation‌​‌ and containerization in the​​ urban middle-mile, efficiently moving​​​‌ parcels between access hubs‌ during off-peak hours to‌​‌ reduce reliance on dedicated​​ freight vehicles. The model​​​‌ is validated through computational‌ experiments based on public‌​‌ transport system, evaluating various​​ collaboration strategies among multiple​​​‌ logistics service providers. Specifically,‌ it examines three consolidation‌​‌ policies: independent, where each​​ provider reserves its own​​​‌ vehicle; partially shared, where‌ different providers share the‌​‌ same vehicle, but containers​​ remain separate; and fully​​​‌ integrated, where parcels from‌ different providers are consolidated‌​‌ in the same container.​​ To compare policies, a​​​‌ realistic case study based‌ on the city of‌​‌ Bordeaux, provides insights into​​ the operational and collaborative​​​‌ potential of integrating public‌ transport into urban logistics‌​‌

Participants: François Clautiaux,​​​‌ Cécile Dupouy.

8.4​ A 2-Competitive Online Algorithm​‌ for Perishable Kit Maintenance​​

We introduce the Kit​​​‌ Update Problem, a new​ online optimization problem motivated​‌ by a real-world application​​ at Doctors Without Borders.​​​‌ We show that the​ deterministic version of the​‌ problem is NP-hard via​​ a reduction from Vertex​​​‌ Cover. We present a​ 2-approximation algorithm for the​‌ deterministic (offline) setting. The​​ algorithm is simple and​​​‌ intuitive, relies only on​ local, non-predictive information, and​‌ builds on techniques inspired​​ by the Joint Replenishment​​​‌ Problem. In contrast to​ the classical joint replenishment​‌ setting, however, our approach​​ naturally extends to dynamic​​​‌ scenarios. Leveraging the structure​ of this approximation algorithm,​‌ we derive a 2-competitive​​ online policy. The resulting​​​‌ method is robust to​ uncertainty and imprecise cost​‌ estimates, making it well-suited​​ for real-world deployment. We​​​‌ evaluate the approach empirically​ using synthetic instances calibrated​‌ to reflect the distributional​​ properties of real data​​​‌ from Doctors Without Borders.​ The online algorithm reduces​‌ total cost by 40%​​ compared to current practices​​​‌ and performs nearly as​ well as a stochastic​‌ look-ahead policy requiring significantly​​ more computational resources. The​​​‌ proposed policy has been​ adopted and integrated into​‌ the organization's operations, where​​ it has produced similar​​​‌ improvements in practice.

Participants:​ Boris Detienne, Mickael​‌ Gaury.

8.5 A​​ semi-infinite constraint generation algorithm​​​‌ for two-stage robust optimization​ problems

In this work,​‌ we consider two-stage linear​​ adjustable robust optimization problems​​​‌ with continuous and fixed​ recourse. These problems have​‌ been the subject of​​ exact solution approaches, notably​​​‌ constraint generation and constraint-and-column​ generation. Both approaches repose​‌ on an exponential-sized reformulation​​ of the problem that​​​‌ uses a large number​ of constraints or constraints​‌ and variables. The decomposition​​ algorithms then solve and​​​‌ reinforce a relaxation of​ the aforementioned reformulations through​‌ iterations that require the​​ solution of bilinear separation​​​‌ problems. Here, we present​ an alternative approach that​‌ is based on a​​ novel reformulation of the​​​‌ problem with an exponential​ number of semi-infinite constraints.​‌ We present a nested​​ decomposition algorithm to deal​​​‌ with the exponential and​ semi-infinite natures of our​‌ formulation separately. We argue​​ that our algorithm will​​​‌ result in a reduced​ number of bilinear separation​‌ problems being solved while​​ providing high-quality relaxations. We​​​‌ additionally study possible MILP​ reformulations of the bilinear​‌ subproblem solved by these​​ algorithms at each iteration,​​​‌ reviewing and consolidating the​ existing literature. Finally, we​‌ perform a detailed numerical​​ study that showcases the​​​‌ superior performance of our​ proposed approach compared to​‌ the state of the​​ art and evaluates the​​​‌ contribution of different algorithmic​ components. We do so​‌ on two distinct applications,​​ a facility location transportation​​​‌ problem and a network​ design problem.

Participants: Ayse​‌ N. Arslan, Boris​​ Detienne, Patxi Flambard​​​‌.

9.1 Bilateral contracts with​​ industry

We have a​​​‌ collaboration with CATIE,​ around the PhD thesis​‌ of Fulin Yan which​​ started in February 2023.​​​‌ The project focuses on​ machine learning and optimization.​‌

Participants: François Clautiaux,​​ Aurélien Froger, Fulin​​ Yan.

We have​​​‌ an industrial contract with‌ EDF around the PhD‌​‌ thesis of Lionel Rolland,​​ which started in 2025.​​​‌ The project is dedicated‌ to the optimization of‌​‌ hydroelectric valleys.

Participants: François​​ Clautiaux, Aurélien Froger​​​‌, Lionel Rolland.‌

Together with Inria team‌​‌ INOCS, we are part​​ of the Inria/EDF challenge​​​‌ "Gérer les systèmes électriques‌ de demain". The work‌​‌ package "Algorithmes de décomposition​​ pour les problèmes d'investissement​​​‌ long-terme" focuses on decomposition‌ method for multi-stage integer‌​‌ stochastic programs, with application​​ to capacity planning problems.​​​‌

Participants: Ayse N. Arslan‌, Boris Detienne,‌​‌ Aurélien Froger, Mariam​​ Sangare.

Saint-Gobain Research​​​‌ Paris is an industrial‌ research and development centre‌​‌ working for light and​​ sustainable construction of the​​​‌ Saint-Gobain Group, the world‌ leader in light and‌​‌ sustainable construction. The collaboration​​ is centered around the​​​‌ PhD thesis of Pierre‌ Pinet. We are working‌​‌ on stochastic vehicle routing​​ problems with uncertainty.

Participants:​​​‌ François Clautiaux, Ayse‌ N. Arslan, Pierre‌​‌ Pinet.

10.1 National​​​‌ initiatives

11.1 Promoting scientific activities‌

11.2 Teaching - Supervision​​ - Juries - Educational​​​‌ and pedagogical outreach

• F.​ Clautiaux is the head​‌ of the master program​​ in operations research at​​​‌ university of Bordeaux (2​ years, 35 students).
• A.​‌ Froger is in charge​​ of interships management of​​​‌ the master program in​ Operations Research, and is​‌ reponsible of the outgoing​​ international mobility for the​​​‌ Master of Engineering in​ Mathematical Optimization (CMI OPTIM)​‌ of the University of​​ Bordeaux
• P. Pesneau is​​​‌ the head of the​ CMI OPTIM of the​‌ University of Bordeaux (5​​ years, 25 students).

11.3 Popularization

12.1 Major​​​‌ publications

• 1 articleA.‌ N.Ayşe N Arslan‌​‌ and B.Boris Detienne​​. Decomposition-based approaches for​​​‌ a class of two-stage‌ robust binary optimization problems‌​‌.INFORMS Journal on​​ Computing342March​​​‌ 2022HALDOI
• 2‌ articleA. N.Ayşe‌​‌ Nur Arslan and M.​​Michael Poss. Uncertainty​​​‌ reduction in robust optimization‌.Operations Research Letters‌​‌552024, 107131​​HALDOI
• 3 article​​​‌M.Michele Barbato,‌ F.Francisco Canas,‌​‌ L.Luís Gouveia and​​ P.Pierre Pesneau.​​​‌ Node based compact formulations‌ for the Hamiltonian p‌​‌ ‐median problem.Networks​​824June 2023​​​‌, 336-370In press.‌ HALDOI
• 4 article‌​‌X.Xavier Blanchot,​​ F.François Clautiaux,​​​‌ B.Boris Detienne,‌ A.Aurélien Froger and‌​‌ M.Manuel Ruiz.​​ The Benders by batch​​​‌ algorithm: design and stabilization‌ of an enhanced algorithm‌​‌ to solve multicut Benders​​ reformulation of two-stage stochastic​​​‌ programs.European Journal‌ of Operational Research309‌​‌12023, 202-216​​HALDOI
• 5 article​​​‌F.François Clautiaux and‌ I.Ivana Ljubić.‌​‌ Last fifty years of​​ integer linear programming: a​​​‌ focus on recent practical‌ advances.European Journal‌​‌ of Operational Research324​​3August 2025,​​​‌ 707-731HALDOI
• 6‌ articleB.Brais González-Rodríguez‌​‌, A.Aurélien Froger​​, O.Ola Jabali​​​‌ and J.Joe Naoum-Sawaya‌. A Continuous Approximation‌​‌ Model for the Electric​​ Vehicle Fleet Sizing Problem​​​‌.Mathematical Programming2024‌. In press. HAL‌​‌DOI

12.2 Publications of​​ the year

12.3 Cited publications

• 20​​ articleD.D .Applegate​​​‌, W.W .Cook​, R.R .Bixby​‌ and V.V .Chvatal​​. Implementing the Dantzig-Fulkerson-Johnson​​​‌ algorithm for large traveling​ salesman problems.Mathematical​‌ Programming, series B97​​2003, 91--153back​​​‌ to text
• 21 article​J.J .Edmonds.​‌ Maximum matching and a​​ polyhedron with 0, 1​​ vertices.Journal of​​​‌ Research National Bureau of‌ Standards69B1965,‌​‌ 125--130back to text​​
• 22 articleN.Nabil​​​‌ Absi, D.Diego‌ Cattaruzza, D.Dominique‌​‌ Feillet, M.Maxime​​ Ogier and F.Frédéric​​​‌ Semet. A Heuristic‌ Branch-Cut-and-Price Algorithm for the‌​‌ ROADEF/EURO Challenge on Inventory​​ Routing.Transportation Science​​​‌accepted2020back to‌ text
• 23 bookC.‌​‌Clàudio Alves, F.​​François Clautiaux, J.​​​‌ M.José Manuel Valério‌ De Carvalho and J.‌​‌Juergen Rietz. Dual-Feasible​​ Functions for Integer Programming​​​‌ and Combinatorial Optimization.‌SpringerJanuary 2016HAL‌​‌back to text
• 24​​ miscA.Ayşe Arslan​​​‌ and B.Boris Detienne‌. Decomposition-based approaches for‌​‌ a class of two-stage​​ robust binary optimization problems​​​‌.July 2019,‌ URL: https://hal.inria.fr/hal-02190059back to‌​‌ textback to text​​
• 25 articleJ.Josette​​​‌ Ayoub and M.Michael‌ Poss. Decomposition for‌​‌ adjustable robust linear optimization​​ subject to uncertainty polytope​​​‌.Computational Management Science‌132April 2016‌​‌, 219--239URL: http://link.springer.com/10.1007/s10287-016-0249-2​​DOIback to text​​​‌
• 26 articleA.A.‌ Ben-Tal, A.A.‌​‌ Goryashko, E.E.​​ Guslitzer and A.A.​​​‌ Nemirovski. Adjustable robust‌ solutions of uncertain linear‌​‌ programs.Mathematical Programming​​992March 2004​​​‌, 351--376URL: http://link.springer.com/10.1007/s10107-003-0454-y‌DOIback to text‌​‌
• 27 articleJ. F.​​J. F. Benders.​​​‌ Partitioning procedures for solving‌ mixed-variables programming problems.‌​‌Numerische Mathematik43​​1962, 238-252URL:​​​‌ https://link.springer.com/article/10.1007%2FBF01386316back to text‌
• 28 articleD.David‌​‌ Bergman, A. A.​​Andre A. Cire,​​​‌ W.-J.Willem-Jan van Hoeve‌ and J. N.J.‌​‌ N. Hooker. Discrete​​ Optimization with Decision Diagrams​​​‌.INFORMS Journal on‌ Computing2812016‌​‌, 47-66back to​​ textback to text​​​‌
• 29 articleD.Dimitris‌ Bertsimas and A.Angelos‌​‌ Georghiou. Design of​​ Near Optimal Decision Rules​​​‌ in Multistage Adaptive Mixed-Integer‌ Optimization.Operations Research‌​‌633Publisher: INFORMS​​April 2015, 610--627​​​‌URL: https://pubsonline.informs.org/doi/abs/10.1287/opre.2015.1365DOIback‌ to text
• 30 article‌​‌X.Xavier Blanchot,​​ F.François Clautiaux,​​​‌ B.Boris Detienne,‌ A.Aurélien Froger and‌​‌ M.Manuel Ruiz.​​ The Benders by batch​​​‌ algorithm: Design and stabilization‌ of an enhanced algorithm‌​‌ to solve multicut Benders​​ reformulation of two-stage stochastic​​​‌ programs.European Journal‌ of Operational Research309‌​‌12023, 202-216​​URL: https://www.sciencedirect.com/science/article/pii/S0377221723000048DOIback​​​‌ to text
• 31 article‌N.Natashia Boland,‌​‌ J.John Dethridge and​​ I.Irina Dumitrescu.​​​‌ Accelerated Label Setting Algorithms‌ for the Elementary Resource‌​‌ Constrained Shortest Path Problem​​.Operations Research Letters​​​‌3412006,‌ 58-68DOIback to‌​‌ text
• 32 articleN.​​N. Boland, M.​​​‌M. Hewitt, L.‌L. Marshall and M.‌​‌M. Savelsbergh. The​​ Continuous-Time Service Network Design​​​‌ Problem.Operations Research‌6552017,‌​‌ 1303-1321DOIback to​​ text
• 33 articleN.​​​‌ L.N. L. Boland‌ and M. W.M.‌​‌ W. P. Savelsbergh.​​ Perspectives on Integer Programming​​​‌ for Time-Dependent Models.‌TOP2019DOIback‌​‌ to text
• 34 article​​​‌H.H. Bouarab,​ I. E.I. El​‌ Hallaoui, A.A.​​ Metrane and F.F.​​​‌ Soumis. Dynamic constraint​ and variable aggregation in​‌ column generation.European​​ Journal of Operational Research​​​‌26232017,​ 835-850URL: http://dx.doi.org/10.1016/j.ejor.2017.04.049back​‌ to text
• 35 article​​N.Nicos Christofides,​​​‌ A.A. Mingozzi and​ P.P. Toth.​‌ State-Space Relaxation Procedures for​​ the Computation of Bounds​​​‌ to Routing Problems.​Networks1121981​‌, 145-164DOIback​​ to text
• 36 article​​​‌F.François Clautiaux,​ S.Sa\"id Hanafi,​‌ R.Rita Macedo,​​ E.Emilie Voge and​​​‌ C.Cláudio Alves.​ Iterative aggregation and disaggregation​‌ algorithm for pseudo-polynomial network​​ flow models with side​​​‌ constraints.European Journal​ of Operational Research258​‌2017, 467 -​​ 477HALDOIback​​​‌ to text
• 37 article​F.François Clautiaux,​‌ R.Ruslan Sadykov,​​ F.François Vanderbeck and​​​‌ Q.Quentin Viaud.​ Combining dynamic programming with​‌ filtering to solve a​​ four-stage two-dimensional guillotine-cut bounded​​​‌ knapsack problem.Discrete​ Optimization292018,​‌ 18-44back to text​​
• 38 articleL. C.​​​‌Leandro C. Coelho,​ J.-F.Jean-François Cordeau and​‌ G.Gilbert Laporte.​​ Thirty Years of Inventory​​​‌ Routing.Transportation Science​4812014,​‌ 1-19back to text​​
• 39 articleG. B.​​​‌George B. Dantzig and​ P.Philip Wolfe.​‌ Decomposition Principle for Linear​​ Programs.Operations Research​​​‌811960,​ 101-111URL: https://doi.org/10.1287/opre.8.1.101DOI​‌back to text
• 40​​ articleG.Guy Desaulniers​​​‌, J.Jacques Desrosiers​ and S.Simon Spoorendonk​‌. Cutting planes for​​ branch-and-price algorithms.Networks​​​‌5842011,​ 301-310back to text​‌
• 41 article G.Guy​​ Desaulniers and J.J\o​​​‌ Rakke. back to​ text
• 42 incollectionJ.​‌Jacques Desrosiers and M.​​ E.Marco E. Lübbecke​​​‌. Branch-Price-and-Cut Algorithms.​Wiley Encyclopedia of Operations​‌ Research and Management Science​​American Cancer Society2011​​​‌back to text
• 43​ articleM.Michael Drexl​‌. Synchronization in Vehicle​​ Routing --- A Survey​​​‌ of VRPs with Multiple​ Synchronization Constraints.Transportation​‌ Science4632012​​, 297-316back to​​​‌ text
• 44 articleB.​B. Fortz, A.​‌ R.A. R. Mahjoub​​, S. T.S.​​​‌ T. McCormick and P.​Pierre Pesneau. Two-edge​‌ connected subgraphs with bounded​​ rings: polyhedral results and​​​‌ branch-and-cut.Mathematical Programming​10512006,​‌ 85--111back to text​​
• 45 inproceedingsA.A.​​​‌ Frank. Some polynomial​ algorithms for certain graphs​‌ and hypergraphs.Proceedings​​ of the Fifth British​​​‌ Combinatorial ConferenceCongressus Numerantium​ XV1975, 211-226​‌back to text
• 46​​ unpublishedA.Aurélien Froger​​​‌, O.Ola Jabali​, J. E.Jorge​‌ E. Mendoza and G.​​Gilbert Laporte. The​​​‌ electric vehicle routing problem​ with capacitated charging stations​‌.December 2020,​​ Submitted paper (available on​​​‌ HAL: https://hal.archives-ouvertes.fr/hal-02386167)HALback​ to text
• 47 article​‌L.-L.Liang-Liang Fu,​​ M. A.Mohamed Ali​​​‌ Aloulou and C.Christian​ Artigues. Integrated production​‌ and outbound distribution scheduling​​ problems with job release​​ dates and deadlines.​​​‌Journal of Scheduling21‌42018, 443--460‌​‌back to text
• 48​​ phdthesisM.Matthew Galati​​​‌. Decomposition Methods for‌ Integer Linear Programming.‌​‌Lehigh University2009back​​ to text
• 49 incollection​​​‌G.Gerald Gamrath and‌ M.Marco Lübbecke.‌​‌ Experiments with a Generic​​ Dantzig-Wolfe Decomposition for Integer​​​‌ Programs.Experimental Algorithms‌6049Lecture Notes in‌​‌ Computer ScienceSpringer Berlin​​ / Heidelberg2010,​​​‌ 239-252back to text‌
• 50 articleL.L.‌​‌ Gouveia, M.M.​​ Leitner and M.M.​​​‌ Ruthmair. Layered Graph‌ Approaches for Combinatorial Optimization‌​‌ Problems.Computers &​​ Operations Research1022019​​​‌, 22-38DOIback‌ to text
• 51 article‌​‌G. A.Grani A.​​ Hanasusanto, D.Daniel​​​‌ Kuhn and W.Wolfram‌ Wiesemann. K -Adaptability‌​‌ in Two-Stage Robust Binary​​ Programming.Operations Research​​​‌634August 2015‌, 877--891URL: http://pubsonline.informs.org/doi/10.1287/opre.2015.1392‌​‌DOIback to text​​
• 52 articleM.M.​​​‌ Horn, G. R.‌G. R. Raidl and‌​‌ E.E. Rönnberg.​​ A* Search for Prize-Collecting​​​‌ Job Sequencing with One‌ Common and Multiple Secondary‌​‌ Resources.Annals of​​ Operations Research2020DOI​​​‌back to text
• 53‌ articleT.T. Ibaraki‌​‌. Successive Sublimation Methods​​ for Dynamic Programming Computation​​​‌.Annals of Operations‌ Research1111987‌​‌, 397--439DOIback​​ to text
• 54 incollection​​​‌S.Stefan Irnich and‌ G.Guy Desaulniers.‌​‌ Shortest Path Problems with​​ Resource Constraints.Column​​​‌ GenerationBoston, MASpringer‌ US2005, 33--65‌​‌back to text
• 55​​ articleR. M.R.​​​‌ M. Karp and M.‌M. Held. Finite-State‌​‌ Processes and Dynamic Programming​​.SIAM Journal on​​​‌ Applied Mathematics153‌1967, 693-718DOI‌​‌back to text
• 56​​ articleA.Ali Khanafer​​​‌, F.François Clautiaux‌ and E.-G.El-Ghazali Talbi‌​‌. New lower bounds​​ for bin packing problems​​​‌ with conflicts.European‌ Journal of Operational Research‌​‌20622010,​​ 281 - 288URL:​​​‌ http://www.sciencedirect.com/science/article/pii/S0377221710000718DOIback to‌ text
• 57 articleV.‌​‌ L.Vinícius L. de​​ Lima, C.Cláudio​​​‌ Alves, F.François‌ Clautiaux, M.Manuel‌​‌ Iori and J. M.​​José M. Valério de​​​‌ Carvalho. Arc flow‌ formulations based on dynamic‌​‌ programming: Theoretical foundations and​​ applications.European Journal​​​‌ of Operational Research2021‌DOIback to text‌​‌
• 58 articleL.Leonardo​​ Lozano, D.David​​​‌ Bergman and J. C.‌J. Cole Smith.‌​‌ On the Consistent Path​​ Problem.Operations Research​​​‌2020, opre.2020.1979DOI‌back to text
• 59‌​‌ articleP.Pierre Mahjoub​​. On the Steiner​​​‌ 2-edge connected subgraph polytope‌.RAIRO Operations Research‌​‌422008, 259-283​​URL: http://hal.inria.fr/inria-00325988/en/back to​​​‌ text
• 60 articleG.‌Guillaume Marques, R.‌​‌Ruslan Sadykov, J.-C.​​Jean-Christophe Deschamps and R.​​​‌Rémy Dupas. An‌ improved branch-cut-and-price algorithm for‌​‌ the two-echelon capacitated vehicle​​ routing problem.Computers​​​‌ & Operations Research114‌2020, 104833back‌​‌ to text
• 61 article​​R. K.R. Kipp​​​‌ Martin, R. L.‌Ronald L. Rardin and‌​‌ B. A.Brian A.​​​‌ Campbell. Polyhedral Characterization​ of Discrete Dynamic Programming​‌.Operations Research38​​11990, 127--138​​​‌DOIback to text​
• 62 articleS.S.​‌ Nadarajah and A. A.​​A. A. Cire.​​​‌ Network-Based Approximate Linear Programming​ for Discrete Optimization.​‌SSRN Electronic Journal2017​​DOIback to text​​​‌
• 63 articleD.Diego​ Pecin, A.Artur​‌ Pessoa, M.Marcus​​ Poggi and E.Eduardo​​​‌ Uchoa. Improved branch-cut-and-price​ for capacitated vehicle routing​‌.Mathematical Programming Computation​​912017,​​​‌ 61--100back to text​back to text
• 64​‌ inproceedingsA.Artur Pessoa​​, R.Ruslan Sadykov​​​‌, E.Eduardo Uchoa​ and F.François Vanderbeck​‌. A Generic Exact​​ Solver for Vehicle Routing​​​‌ and Related Problems.​Integer Programming and Combinatorial​‌ Optimization11480Lecture Notes​​ in Computer ScienceCham​​​‌Springer International Publishing2019​, 354--369back to​‌ text
• 65 articleA.​​Artur Pessoa, R.​​​‌Ruslan Sadykov, E.​Eduardo Uchoa and F.​‌François Vanderbeck. Automation​​ and combination of linear-programming​​​‌ based stabilization techniques in​ column generation.INFORMS​‌ Journal on Computing30​​22018, 339--360​​​‌back to text
• 66​ articleD.D. Porumbel​‌ and G.G. Goncalves​​. Using dual feasible​​​‌ functions to construct fast​ lower bounds for routing​‌ and location problems.​​Discrete Applied Mathematics196​​​‌2015, 83-99back​ to text
• 67 techreport​‌RTE. Energy Pathways​​ to 2050 - Key​​​‌ results (Executive summary).​RTE, Report2021back​‌ to text
• 68 techreport​​RTE. French transmission​​​‌ network development plan.​RTE, Report2019back​‌ to text
• 69 inproceedings​​M.M. Riedler,​​​‌ M.M. Ruthmair and​ G. R.G. R​‌ Raidl. Strategies for​​ Iteratively Refining Layered Graph​​​‌ Models.11th International​ Workshop on Hybrid Metaheuristics​‌Chili2018, 16​​back to text
• 70​​​‌ articleG.Giovanni Righini​ and M.Matteo Salani​‌. New Dynamic Programming​​ Algorithms for the Resource​​​‌ Constrained Elementary Shortest Path​ Problem.Networks51​‌32008, 155-170​​DOIback to text​​​‌
• 71 articleR.Ruslan​ Sadykov, E.Eduardo​‌ Uchoa and A.Artur​​ Pessoa. A bucket​​​‌ graph--based labeling algorithm with​ application to vehicle routing​‌.Transportation Science55​​12021, 4--28​​​‌back to text
• 72​ articleR.Ruslan Sadykov​‌ and F.François Vanderbeck​​. Bin Packing with​​​‌ Conflicts: A Generic Branch-and-Price​ Algorithm.INFORMS Journal​‌ on Computing252​​2013, 244-255back​​​‌ to text
• 73 article​R.Ruslan Sadykov,​‌ F.François Vanderbeck,​​ A.Artur Pessoa,​​​‌ I.Issam Tahiri and​ E.Eduardo Uchoa.​‌ Primal Heuristics for Branch-and-Price:​​ the assets of diving​​​‌ methods.INFORMS Journal​ on Computing312​‌2019, 251-267back​​ to textback to​​​‌ text
• 74 articleM.​Michael Schneider and M.​‌Michael Drexl. A​​ survey of the standard​​​‌ location-routing problem.Annals​ of Operations Research259​‌12017, 389--414​​back to text
• 75​​​‌ articleD. M.Duc​ Minh Vu, M.​‌Mike Hewitt, N.​​Natashia Boland and M.​​Martin Savelsbergh. Dynamic​​​‌ Discretization Discovery for Solving‌ the Time-Dependent Traveling Salesman‌​‌ Problem with Time Windows​​.Transportation Science54​​​‌32020, 703--720‌DOIback to text‌​‌
• 76 articleB.Bo​​ Zeng and L.Long​​​‌ Zhao. Solving two-stage‌ robust optimization problems using‌​‌ a column-and-constraint generation method​​.Operations Research Letters​​​‌415September 2013‌, 457--461URL: http://linkinghub.elsevier.com/retrieve/pii/S0167637713000618‌​‌DOIback to text​​