François Clautiaux
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
François Clautiaux has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Cláudio Alves
University of Minho
4 shared publications - José Manuel Valério de Carvalho
Universidade do Minho
4 shared publications Jürgen Rietz
University of Minho
3 shared publications- Aurélien Froger
Université de Bordeaux, Centre National de la Recherche Scientifique, Bordeaux INP, Institut de Mathématiques de Bordeaux, Unité Mixte de Recherche 5251, F-33400 Talence, France
2 shared publications - Ruslan Sadykov
Atoptima, 33000 Bordeaux, France
2 shared publications Alain Nguyen
1 shared publication
Latest Publications
- 16 July 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
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 two-dimensional knapsack problem (G2KP), which is 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 thus far and is the first to close the optimality gap for all instances of several well-known benchmarks. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1692 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1692 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 16 July 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
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 two-dimensional knapsack problem (G2KP), which is 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 thus far and is the first to close the optimality gap for all instances of several well-known benchmarks. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1692 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1692 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 8 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Cutting Problems by A. Léonard and F. Clautiaux.
- 8 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Orthogonal Knapsack Problems
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper An Efficient Solver for Integral Flows in Decision Hypergraphs with Applications to Cutting Problems by A. Léonard and F. Clautiaux.
- Open Access
- 27 November 2025
- Published by Elsevier in Computers & Operations Research
- Vol. 187
Generic machine-learning-augmented beam search for resource-constrained shortest path reformulations of combinatorial optimization problems
- 27 November 2025
- Published by Elsevier in Computers & Operations Research
- Vol. 187
Open AccessGeneric machine-learning-augmented beam search for resource-constrained shortest path reformulations of combinatorial optimization problems
- Open Access
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.
Open AccessAn 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.
- Top Cited PapersOpen Access
- 19 November 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 324 (3) , 707-731
Last fifty years of integer linear programming: A focus on recent practical advances
- 19 November 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 324 (3) , 707-731
Top Cited PapersOpen AccessLast fifty years of integer linear programming: A focus on recent practical advances
- Open Access
- 17 September 2024
- Published by Elsevier in Computers & Operations Research
- Vol. 173
Models and algorithms for configuring and testing prototype cars
- 17 September 2024
- Published by Elsevier in Computers & Operations Research
- Vol. 173
Open AccessModels and algorithms for configuring and testing prototype cars
- Open Access
- 16 September 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 321 (1) , 57-74
Mathematical models based on decision hypergraphs for designing a storage cabinet
- 16 September 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 321 (1) , 57-74
Open AccessMathematical models based on decision hypergraphs for designing a storage cabinet
- 9 January 2023
- Published by Elsevier in European Journal of Operational Research
- Vol. 309 (1) , 202-216
The Benders by batch algorithm: Design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
- 9 January 2023
- Published by Elsevier in European Journal of Operational Research
- Vol. 309 (1) , 202-216
The Benders by batch algorithm: Design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
- 1 July 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (4) , 2249-2270
Bin Packing Problem with Time Lags
We introduce and motivate several variants of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the general problem: a compact one and a stronger formulation with an exponential number of variables and constraints. We propose a branch-cut-and-price approach that exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem: when the number of possible bins available at each period is infinite and when this number is limited to one and time lags are nonnegative. Computational experiments are reported for instances inspired from a real-case application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branch-cut-and-price approach, as it outperforms the compact formulation on newly proposed instances and is able to obtain improved lower and upper bounds for literature instances. Summary of Contribution: The paper considers a new variant of the bin packing problem, which is one of the most important problems in operations research. A motivation for introducing this variant is given, as well as a real-life application. We present a novel and original exact branch-cut-and-price algorithm for the problem. We implement this algorithm, and we present the results of extensive computational experiments. The results show a very good performance of our algorithm. We give several research directions that can be followed by subsequent researchers to extend our contribution to more complex and generic problems.
- 1 July 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (4) , 2249-2270
Bin Packing Problem with Time Lags
We introduce and motivate several variants of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the general problem: a compact one and a stronger formulation with an exponential number of variables and constraints. We propose a branch-cut-and-price approach that exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem: when the number of possible bins available at each period is infinite and when this number is limited to one and time lags are nonnegative. Computational experiments are reported for instances inspired from a real-case application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branch-cut-and-price approach, as it outperforms the compact formulation on newly proposed instances and is able to obtain improved lower and upper bounds for literature instances. Summary of Contribution: The paper considers a new variant of the bin packing problem, which is one of the most important problems in operations research. A motivation for introducing this variant is given, as well as a real-life application. We present a novel and original exact branch-cut-and-price algorithm for the problem. We implement this algorithm, and we present the results of extensive computational experiments. The results show a very good performance of our algorithm. We give several research directions that can be followed by subsequent researchers to extend our contribution to more complex and generic problems.
- Open Access
Arc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications
Network flow formulations are among the most successful tools to solve optimization problems. Such formulations correspond to determining an optimal flow in a network. One particular class of network flow formulations is the arc flow, where variables represent flows on individual arcs of the network. For $\mathcal{NP}$-hard problems, polynomial-sized arc flow models typically provide weak linear relaxations and may have too much symmetry to be efficient in practice. Instead, arc flow models with a pseudo-polynomial size usually provide strong relaxations and are efficient in practice. The interest in pseudo-polynomial arc flow formulations has grown considerably in the last twenty years, in which they have been used to solve many open instances of hard problems. A remarkable advantage of pseudo-polynomial arc flow models is the possibility to solve practical-sized instances directly by a Mixed Integer Linear Programming solver, avoiding the implementation of complex methods based on column generation. In this survey, we present theoretical foundations of pseudo-polynomial arc flow formulations, by showing a relation between their network and Dynamic Programming (DP). This relation allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. The relation with DP also allows a new perspective to relate state-space relaxation methods for DP with arc flow models. We also present a dual point of view to contrast the linear relaxation of arc flow models with that of models based on paths and cycles. To conclude, we review the main solution methods and applications of arc flow models based on DP in several domains such as cutting, packing, scheduling, and routing.
Open AccessArc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications
Network flow formulations are among the most successful tools to solve optimization problems. Such formulations correspond to determining an optimal flow in a network. One particular class of network flow formulations is the arc flow, where variables represent flows on individual arcs of the network. For $\mathcal{NP}$-hard problems, polynomial-sized arc flow models typically provide weak linear relaxations and may have too much symmetry to be efficient in practice. Instead, arc flow models with a pseudo-polynomial size usually provide strong relaxations and are efficient in practice. The interest in pseudo-polynomial arc flow formulations has grown considerably in the last twenty years, in which they have been used to solve many open instances of hard problems. A remarkable advantage of pseudo-polynomial arc flow models is the possibility to solve practical-sized instances directly by a Mixed Integer Linear Programming solver, avoiding the implementation of complex methods based on column generation. In this survey, we present theoretical foundations of pseudo-polynomial arc flow formulations, by showing a relation between their network and Dynamic Programming (DP). This relation allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. The relation with DP also allows a new perspective to relate state-space relaxation methods for DP with arc flow models. We also present a dual point of view to contrast the linear relaxation of arc flow models with that of models based on paths and cycles. To conclude, we review the main solution methods and applications of arc flow models based on DP in several domains such as cutting, packing, scheduling, and routing.