Search

Your search keyword '"Libralesso, Luc"' showing total 19 results
Start Over Author "Libralesso, Luc" Publisher hal ccsd
19 results on '"Libralesso, Luc"'

1. 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

2. 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

3. 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

4. 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

5. 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

6. 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

7. Tree Search for the 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 ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), 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-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; 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
Full Text
View/download PDF

8. 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

9. 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

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

Author

Fontan, Florian, 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
FOS: Computer and information sciences, two-dimensional guillotine packing, Artificial Intelligence (cs.AI), knapsack, strip packing, bin packing, Computer Science - Artificial Intelligence, anytime algorithm, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
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

11. 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

12. 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

13. 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

14. 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

15. 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

16. 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

17. 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

18. 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

19. 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