Search

Your search keyword '"Libralesso, Luc"' showing total 36 results
Start Over Author "Libralesso, Luc"

Refine your results

36 results on '"Libralesso, Luc"'

2. Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

Author

Crombez, Loïc, da Fonseca, Guilherme D., Fontan, Florian, Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, Libralesso, Luc, Momège, Benjamin, Spalding-Jamieson, Jack, Zhang, Brandon, and Zheng, Da Wei

Subjects
Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms
Abstract

CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this paper, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs., Comment: To appear at ACM Journal of Experimental Algorithmics

Published
2023

3. Shadoks Approach to Low-Makespan Coordinated Motion Planning

Author

Crombez, Loïc, da Fonseca, Guilherme D., Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, and Libralesso, Luc

Subjects
Computer Science - Computational Geometry, Computer Science - Robotics
Abstract

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions., Comment: Journal version to appear on ACM Journal on Algorithmics

Published
2021
Full Text
View/download PDF

4. Iterative beam search algorithms for the permutation flowshop

Author

Libralesso, Luc, Focke, Pablo Andres, Secardin, Aurélien, and Jost, Vincent

Subjects
Computer Science - Artificial Intelligence, Computer Science - Neural and Evolutionary Computing, Mathematics - Optimization and Control
Abstract

We study an iterative beam search algorithm for the permutation flowshop (makespan and flowtime minimization). This algorithm combines branching strategies inspired by recent branch-and-bounds and a guidance strategy inspired by the LR heuristic. It obtains competitive results, reports many new-best-so-far solutions on the VFR benchmark (makespan minimization) and the Taillard benchmark (flowtime minimization) without using any NEH-based branching or iterative-greedy strategy. The source code is available at: https://gitlab.com/librallu/cats-pfsp.

Published
2020

5. An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem

Author

Libralesso, Luc and Fontan, Florian

Subjects
Computer Science - Artificial Intelligence
Abstract

In this article, we present the anytime tree search algorithm we designed for the 2018 ROADEF/EURO challenge glass cutting problem proposed by the French company Saint-Gobain. The resulting program was ranked first among 64 participants. Its key components are: a new search algorithm called Memory Bounded A* (MBA*) with guide functions, a symmetry breaking strategy, and a pseudo-dominance rule. We perform a comprehensive study of these components showing that each of them contributes to the algorithm global performances. In addition, we designed a second tree search algorithm fully based on the pseudo-dominance rule and dedicated to some of the challenge instances with strong precedence constraints. On these instances, it finds the best-known solutions very quickly.

Published
2020

6. An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems

Author

Fontan, Florian and Libralesso, Luc

Subjects
Computer Science - Artificial Intelligence
Abstract

[libralesso_anytime_2020] proposed an anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php). The resulting program was ranked first among 64 participants. In this article, we generalize it and show that it is not only effective for the specific problem it was originally designed for, but is also very competitive and even returns state-of-the-art solutions on a large variety of Cutting and Packing problems from the literature. We adapted the algorithm for two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two- or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints. The algorithm is implemented in a new software package called PackingSolver.

Published
2020

7. Tree search algorithms for the Sequential Ordering Problem

Author

Libralesso, Luc, Bouhassoun, Abdel-Malik, Cambazard, Hadrien, and Jost, Vincent

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms
Abstract

We present a study of several generic tree search techniques applied to the Sequential Ordering Problem. This study enables us to propose a simple and competitive tree search algorithm. It consists of an iterative Beam Search algorithm that favors search over inference and integrates dynamic programming inspired cuts. It proves optimality on half of the SOPLIB instances and finds new best known solutions on 6 among 7 open instances of the benchmark in a small amount of time.

Published
2019

10. Mixed Integer Programming Formulations for the Balanced Traveling Salesman Problem with a Lexicographic Objective

Author

Libralesso, Luc, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Greco, Salvatore, editor, Pavone, Mario F., editor, Talbi, El-Ghazali, editor, and Vigo, Daniele, editor

Published
2021
Full Text
View/download PDF

12. Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

Author

Crombez, Loïc, primary, Da Fonseca, Guilherme D., additional, Fontan, Florian, additional, Gerard, Yan, additional, Gonzalez-Lorenzo, Aldo, additional, Lafourcade, Pascal, additional, Libralesso, Luc, additional, Momège, Benjamin, additional, Spalding-Jamieson, Jack, additional, Zhang, Brandon, additional, and Zheng, Da Wei, additional

Published
2023
Full Text
View/download PDF

13. Local search with weighting schemes for the CG:SHOP 2022 competition

Author

Fontan, Florian, Lafourcade, Pascal, Libralesso, Luc, Momège, Benjamin, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), and Atoptima

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], digital geometry, vertex coloring, heuristics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Abstract

International audience; This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA 1 team for the CG:SHOP 2022 challenge. We introduce a new greedy algorithm that exploits information about the challenge instances, and hybridize two classical local-search schemes with weighting schemes. We found 211/225 best-known solutions. Hence, with the algorithms presented in this article, our team was able to reach the 3rd place of the challenge, among 40 participating teams.

Published
2022
Full Text
View/download PDF

16. Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge)

Author

Fontan, Florian, Lafourcade, Pascal, Libralesso, Luc, Fontan, Florian, Lafourcade, Pascal, and Libralesso, Luc

Abstract

This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA team for the CG:SHOP 2022 challenge. We introduce a new greedy algorithm that exploits information about the challenge instances, and hybridize two classical local-search schemes with weighting schemes. We found 211/225 best-known solutions. Hence, with the algorithms presented in this article, our team was able to reach the 3rd place of the challenge, among 40 participating teams.

Published
2022
Full Text
View/download PDF

17. Longest common subsequence: an algorithmic component analysis

Author

Libralesso, Luc, Secardin, Aurélien, Jost, Vincent, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), LIBRALESSO, Luc, Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), and Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

We study the performance of various algorithmic components for the longest common sequence problem (LCS). In all experiments, a simple and original anytime tree search algorithm, iterative beam search is used. A new dominance scheme for LCS, inspired by dynamic programming, is compared with two known dominance schemes: local and beam dominance. We show how to compute the probabilistic and expectation guides with high precision, using logarithms. We show that the contribution of the components to the algorithm substantially depends on the number of sequences and if the sequences are dependent or not. Out of this component analysis, we build a competitive tree search algorithm that finds new-best-known solutions on various instances of public datasets of LCS. We provide access to our computational code to facilitate further improvements.

Published
2020

18. Automatic Generation of Declarative Models for Differential Cryptanalysis

Author

Libralesso, Luc, Delobel, François, Lafourcade, Pascal, Solnon, Christine, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria), Robots coopératifs et adaptés à la présence humaine en environnements dynamiques (CHROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)

Subjects
ILP, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Differential Cryptanalysis, SAT, Security and privacy → Cryptanalysis and other attacks, Constraint Programming, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

When designing a new symmetric block cipher, it is necessary to evaluate its robustness against differential attacks. This is done by computing Truncated Differential Characteristics (TDCs) that provide bounds on the complexity of these attacks. TDCs are often computed by using declarative approaches such as CP (Constraint Programming), SAT, or ILP (Integer Linear Programming). However, designing accurate and efficient models for these solvers is a difficult, error-prone and time-consuming task, and it requires advanced skills on both symmetric cryptography and solvers. In this paper, we describe a tool for automatically generating these models, called Tagada (Tool for Automatic Generation of Abstraction-based Differential Attacks). The input of Tagada is an operational description of the cipher by means of black-box operators and bipartite Directed Acyclic Graphs (DAGs). Given this description, we show how to automatically generate constraints that model operator semantics, and how to generate MiniZinc models. We experimentally evaluate our approach on two different kinds of differential attacks (e.g., single-key and related-key) and four different symmetric block ciphers (e.g., the AES (Advanced Encryption Standard), Craft, Midori, and Skinny). We show that our automatically generated models are competitive with state-of-the-art approaches. These automatically generated models constitute a new benchmark composed of eight optimization problems and eight enumeration problems, with instances of increasing size in each problem. We experimentally compare CP, SAT, and ILP solvers on this new benchmark., LIPIcs, Vol. 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), pages 40:1-40:18

Published
2021
Full Text
View/download PDF

19. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Author

Crombez, Loïc, da Fonseca, Guilherme D., Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, Libralesso, Luc, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), MAAD, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), MODélisation Géométrique (GMOD), ANR-19-CE48-0005,ADDS,Algorithmes pour les données multidimensionnelles(2019), ANR-19-CE19-0005,ACTIVmap,Assistance à la Conception de carTes pour défIcients Visuels(2019), ANR-20-CE10-0002,COHERENCE4D,Cohérence des jumeaux numériques pour l'industrie du futur : Modélisation, visualisation et interaction de maquettes numériques 4D interfacées aux systèmes physiques(2020), ANR-18-CE39-0019,MobiS5,La sécurité et la privacy dans les réseaux 5G(2018), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), ANR-20-CE39-0005,PRIVABIO,Vers des systèmes de reconnaissance biométrique respectueux de la vie privée(2020), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)

Subjects
shortest path, digital geometry, Computing methodologies → Motion path planning, Theory of computation → Computational geometry, heuristics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], motion planning, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Abstract

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them., LIPIcs, Vol. 189, 37th International Symposium on Computational Geometry (SoCG 2021), pages 63:1-63:9

Published
2021
Full Text
View/download PDF

20. Tree searches for the Sequential Ordering Problem

Author

Libralesso, Luc, Bouhassoun, Abdel-Malik, Cambazard, Hadrien, Jost, Vincent, LIBRALESSO, Luc, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), and Université Grenoble Alpes (UGA)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

We study several generic tree search techniques applied to the Sequential Ordering Problem.This study enables us to propose a simple yet competitive tree search. It consists of an iterative beam search that favors search over inference and integrates prunings that are inspired by dynamic programming. The resulting method proves optimality on half of the SOPLIB instances, 10 to 100 times faster than other existing methods. Furthermore, it finds new best-known solutions on 6 among 7 open instances of the benchmark in a small amount of time. These results highlight that there is a category of problems (containing at least SOP) where an anytime tree search is extremely efficient (compared to classical meta-heuristics) but was underestimated.

Published
2020

22. Triangle width: at the intersection of graph theory, scheduling and matrix visualization

Author

Libralesso, Luc, Jost, Vincent, Hadj Salem, Khadija, Fontan, Florian, Maffray, Frédéric, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), and Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL)

Subjects
Preprint, submitted to Annals of Operations Research (ANOR), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Computer Science::Databases
Abstract

International audience; We introduce a new problem that can be studied from 3 different angles: scheduling, matrix visualization and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to prove several of its NP-Hard and polynomial subcases. This problem allows to find more elegant (and arguably shorter) proofs for several combinatorial problems. Including "Can a matrix can be made triangular by permuting rows and columns?" and weak k-visit. It also provides an elegant generalization of Johnson's argument for the two-machine flowshop.

Published
2020

23. Anytime tree search for combinatorial optimization

Author

Libralesso, Luc, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), Université Grenoble Alpes [2020-....], and Louis Esperet

Subjects
Combinatorial optimization, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Recherches arborescentes, Metaheuristics, Tree search algorithms, Metaheuristiques, Optimisation combinatoire
Abstract

Tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations research.In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions.; Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opérationnelle.Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/planning.Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente.Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues.

Published
2020

24. Recherches arborescentes anytime pour l'optimisation combinatoire

Author

Libralesso, Luc, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), Université Grenoble Alpes [2020-....], and Louis Esperet

Subjects
Combinatorial optimization, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Recherches arborescentes, Metaheuristics, Tree search algorithms, Metaheuristiques, Optimisation combinatoire
Abstract

Tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations research.In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions.; Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opérationnelle.Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/planning.Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente.Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues.

Published
2020

25. PackingSolver: a tree search-based solver for two-dimensional two-and three-staged guillotine packing problems

Author

Fontan, Florian, Libralesso, Luc, ROSP (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), and Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)

Subjects
two-dimensional guillotine packing, strip packing, bin packing, knapsack, anytime algorithm, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

In this article, we introduce PackingSolver, a new solver for two-dimensional two-and three-staged guillotine Packing Problems. It relies on a simple yet powerful anytime tree search algorithm called Memory Bounded A* (MBA*). This algorithm was first introduced in libralesso2020 for the 2018 ROADEF/EURO challenge glass cutting problem † , for which it had been ranked first during the final phase. In this article, we generalize it for a large variety of Cutting and Packing problems. The resulting program can tackle two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two-or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. Despite its simplicity and genericity, computational experiments show that this approach is competitive compared to the other dedicated algorithms from the literature. It even returns state-of-the-art solutions on several variants. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints.

Published
2020

26. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Author

da Fonseca, Guilherme D., Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, Libralesso, Luc, da Fonseca, Guilherme D., Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, and Libralesso, Luc

Abstract

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.

Published
2021
Full Text
View/download PDF

28. Study on partial flexible job-shop scheduling problem under tooling constraints: complexity and related problems

Author

Libralesso, Luc, Jost, Vincent, Hadj Salem, Khadija, Fontan, Florian, Maffray, Frédéric, LIBRALESSO, Luc, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and Optimisation Combinatoire (G-SCOP_OC )

Subjects
Graph theory, Scheduling, Combinatorial Optimization, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Binary matrix visualization
Abstract

We introduce a new problem, which is an extension of the classical job shop with tooling constraints. We study it from 3 different aspects: scheduling, matrix visualization and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to prove several of its NP-Hard and polynomial subcases. This problem allows to find more elegant (and arguably shorter) proofs for several combinatorial problems. Including "Can a matrix can be made triangular by permuting rows and columns?", weak k-visit and a generalization of Johnson's argument for the two-machines flowshop.

Published
2019

29. anytime tree searches for operations research

Author

Libralesso, Luc, Jost, Vincent, Esperet, Louis, Honegger, Thibault, LIBRALESSO, Luc, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des technologies de la microélectronique (LTM ), and Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])

Subjects
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2019

30. Recherches arborescentes pour le Sequential Ordering Problem

Author

Libralesso, Luc, Bouhassoun, Abdel-Malik, Cambazard, Hadrien, Jost, Vincent, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), and Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

We study several generic tree search techniques applied to the Sequential Ordering Problem.This study enables us to propose a simple yet competitive tree search. It consists of an iterative beam search that favors search over inference and integrates prunings that are inspired by dynamic programming. The resulting method proves optimality on half of the SOPLIB instances, 10 to 100 times faster than other existing methods. Furthermore, it finds new best-known solutions on 6 among 7 open instances of the benchmark in a small amount of time. These results highlight that there is a category of problems (containing at least SOP) where an anytime tree search is extremely efficient (compared to classical meta-heuristics) but was underestimated.

Published
2020

31. The 2-machine FJSP with tooling constraints: a theoretical analysis

Author

Libralesso, Luc, Jost, Vincent, Hadj Salem, Khadija, Fontan, Florian, Maffray, Frédéric, and HADJ SALEM, Khadija

Subjects
Graph theory, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Scheduling, Combinatorial Optimization, Binary matrix visualization, Computer Science::Databases
Abstract

This paper addresses the triangle width problem, which generalizes the classic 2-machine flexible job-shop problem (FJSP) with tooling constraints. This new problem can be studied from 3 different angles: scheduling, matrix visualization, and the order of vertices in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to establish the NP-Hardness and polynomiality of several of its sub-cases. This problem allows us to find more elegant (and probably shorter) proofs for several combinatorial problems in our analysis setting. Our study provides an elegant generalization of Johnson’s argu- ment for the two-machine flow-shop. It also shows if a matrix can be triangular by permuting rows and columns and a low k -visit.

Published
2020

32. How to design brains on a chip

Author

Libralesso, Luc, Larramendy, Florian, Jost, Vincent, Maffray, Frédéric, Honegger, Thibault, ROSP ( G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production ( G-SCOP ), Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut polytechnique de Grenoble - Grenoble Institute of Technology ( Grenoble INP ) -Institut National Polytechnique de Grenoble ( INPG ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut polytechnique de Grenoble - Grenoble Institute of Technology ( Grenoble INP ) -Institut National Polytechnique de Grenoble ( INPG ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), Équipe NanoBioSystèmes ( LAAS-NBS ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), OC ( G-SCOP_OC ), Laboratoire des technologies de la microélectronique ( LTM ), Université Joseph Fourier - Grenoble 1 ( UJF ) -Centre National de la Recherche Scientifique ( CNRS ), LIBRALESSO, Luc, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire des technologies de la microélectronique (LTM ), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Optimisation Combinatoire (G-SCOP_OC ), and Université Grenoble AlpesERC Connexio GA 714291

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [SPI.NANO] Engineering Sciences [physics]/Micro and nanotechnologies/Microelectronics, [ SPI.NANO ] Engineering Sciences [physics]/Micro and nanotechnologies/Microelectronics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [SPI.NANO]Engineering Sciences [physics]/Micro and nanotechnologies/Microelectronics, ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience

Published
2017

33. Mixed Integer Programming formulations for the balanced Traveling Salesman Problem with a lexicographic objective

Author

Luc Libralesso, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), and LIBRALESSO, Luc

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Competition (economics), Mathematical optimization, Computer science, Structure (category theory), MathematicsofComputing_NUMERICALANALYSIS, Lexicographical order, Travelling salesman problem, Metaheuristic, Integer programming, Integer (computer science), MathematicsofComputing_DISCRETEMATHEMATICS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

This paper presents a Mixed Integer Program to solve the Balanced TSP. It exploits the underlying structure of the instances and is able to find optimal solutions for all the instances provided in the Metaheuristics Summer School competition. We study the efficiency of this new model on several variants of the Balanced TSP. The proposed method was ranked first in the MESS18 Metaheuristic competition among 9 submissions.

Published
2020

34. Iterative beam search algorithms for the permutation flowshop

Author

Vincent Jost, Pablo Andres Focke, Luc Libralesso, Aurélien Secardin, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), and LIBRALESSO, Luc

Subjects
FOS: Computer and information sciences, Information Systems and Management, Source code, General Computer Science, Heuristic (computer science), Computer science, Computer Science - Artificial Intelligence, media_common.quotation_subject, 0211 other engineering and technologies, 02 engineering and technology, [INFO] Computer Science [cs], Management Science and Operations Research, Industrial and Manufacturing Engineering, Permutation, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, [INFO]Computer Science [cs], Neural and Evolutionary Computing (cs.NE), Mathematics - Optimization and Control, ComputingMilieux_MISCELLANEOUS, media_common, 021103 operations research, Job shop scheduling, Computer Science - Neural and Evolutionary Computing, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Artificial Intelligence (cs.AI), Optimization and Control (math.OC), Modeling and Simulation, Benchmark (computing), Beam search, 020201 artificial intelligence & image processing, Minification, Algorithm
Abstract

We study an iterative beam search algorithm for the permutation flowshop (makespan and flowtime minimization). This algorithm combines branching strategies inspired by recent branch-and-bounds and a guidance strategy inspired by the LR heuristic. It obtains competitive results on large instances compared to the state-of-the-art algorithms, reports many new-best-so-far solutions on the VFR benchmark (makespan minimization) and the Taillard benchmark (flowtime minimization) without using any NEH-based branching or iterative-greedy strategy. The source code is available at: https://github.com/librallu/dogs-pfsp .

Published
2020
Full Text
View/download PDF

35. Triangle Width de l'ordonnancement à la théorie des graphes

Author

Luc Libralesso, Vincent Jost, Khadija Hadj Salem, Frédéric Maffray, Florian Fontan, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), LIBRALESSO, Luc, and Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL)

Subjects
visualisation de matrices, Mots-clés : Ordonnancement, théorie des graphes, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2019

36. Comment la recherche opérationnelle peut elle créer des cerveaux sur puce

Author

Luc Libralesso, vincent jost, Frédéric Maffray, Thibault Honegger, Florian Larramendy, LIBRALESSO, Luc, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire Leibniz (Leibniz - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), Laboratoire des technologies de la microélectronique (LTM ), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Université Grenoble AlpesERC Connexio GA 714291, ROADEF, and Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; Ces dernières années, de nouvelles technologies de micro-fabrication ont permis de faire croître de vrais neurones dans des puces en sillicone. Cette avancée nous permet de reproduire des parties du cerveau bien connues par les neurobiologistes ([Lim et al.2014], [Yi et al.2015]) impliquées dans des maladies comme Alzheimer, épilepsie, Parkinson. Le fait de pouvoir réaliser de telles puces permet de mieux comprendre l'évolution de ces maladies et donc de sauver des vies. Cependant, produire des plans pour ces puces implique la résolution d'une grande quantité de contraintes qui ne peuvent pas être prises en compte par un humain en une quantité de temps et d'efforts raisonnable. C'est ici que la recherche opérationnelle entre en jeu. Durant un stage de master 2, les auteurs ont proposé une modélisation de ces puces ainsi que les contraintes de fabrication, de neuro ingénierie et de microfluidique. Les progrès que nous avons réalisés ces derniers mois nous ont permis d'obtenir des puces intéressantes qui sont présentées dans un article soumis dans un journal.

Published
2018

Catalog

Books, media, physical & digital resources
See catalog results