-
Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
Authors:
Loïc Crombez,
Guilherme D. da Fonseca,
Florian Fontan,
Yan Gerard,
Aldo Gonzalez-Lorenzo,
Pascal Lafourcade,
Luc Libralesso,
Benjamin Momège,
Jack Spalding-Jamieson,
Brandon Zhang,
Da Wei Zheng
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…
▽ More
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.
△ Less
Submitted 24 March, 2023; v1 submitted 16 March, 2023;
originally announced March 2023.
-
Shadoks Approach to Low-Makespan Coordinated Motion Planning
Authors:
Loïc Crombez,
Guilherme D. da Fonseca,
Yan Gerard,
Aldo Gonzalez-Lorenzo,
Pascal Lafourcade,
Luc Libralesso
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…
▽ More
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.
△ Less
Submitted 9 March, 2022; v1 submitted 25 March, 2021;
originally announced March 2021.
-
Iterative beam search algorithms for the permutation flowshop
Authors:
Luc Libralesso,
Pablo Andres Focke,
Aurélien Secardin,
Vincent Jost
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…
▽ More
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.
△ Less
Submitted 12 September, 2020;
originally announced September 2020.
-
An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems
Authors:
Florian Fontan,
Luc Libralesso
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…
▽ More
[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.
△ Less
Submitted 20 April, 2020; v1 submitted 2 April, 2020;
originally announced April 2020.
-
An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
Authors:
Luc Libralesso,
Florian Fontan
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…
▽ More
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.
△ Less
Submitted 2 April, 2020;
originally announced April 2020.
-
Tree search algorithms for the Sequential Ordering Problem
Authors:
Luc Libralesso,
Abdel-Malik Bouhassoun,
Hadrien Cambazard,
Vincent Jost
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 so…
▽ More
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.
△ Less
Submitted 25 November, 2019;
originally announced November 2019.
