I am a recurrent member of the team Shadoks at the annual CG:SHOP optimization challenge organized by the SoCG conference. Each year, there is a hard geometrical problem for which we have to find good (sometimes optimal) solutions using any algorithms. The contest asks for the solutions and not for algorithms, so you can solve the instances by hand if that works for you.
I have participated in three challenges:
Minimum Convex Partition Problem (2020)
We got the fourth place in this challenge. Our approach considered computing optimal solutions for parts of the instance and merging them. You can read the details of the challenge here.
Coordinated Motion Planning (2021)
We got first place in this challenge. To solve this problem, we came up with a solver that we call conflict optimizer. You can read the details of the challenge here and our paper here.
Minimum Partition into Plane Subgraphs (2022)
We got first place again in this challenge. To solve this problem, we used again our conflict optimizer, which became a metaheuristic. Surprisingly, all the top three teams used the conflict optimizer. You can read the details of the challenge here and our paper here.
Conflict Optimizer
The conflict optimizer, which is the algorithm that made us win two consecutive years, is simpler to explain with a specific example. For instance, consider the problem of Numberlink: connect pairs of points in a grid without intersections. The conflict optimizer does:
Start with an empty solution and put all the pairs in a queue
We define a map count that tells how many times a pair has been enqueued
Get the first pair from the queue and find a valid path (it does not intersect other paths). If it does not exist, find a path that minimizes the number of conflicts. That is, find a path that is valid if we remove a set of paths such that the sum of their squared counts are minimal.
Remove the conflicting paths, add the new path and enqueue the corresponding pairs.
Go to step 3
You can explore the conflict optimizer with this example:
Queue and count:
Note that we cannot be sure that this algorithm finds a solution. It is not clear on which problems we can use the conflict optimizer, but a few characteristics seem to be:
The problem consists in assigning something (a path, a color) to a set of items. These somethings have to satisfy some constraints between them.
Given a solution, if you remove one item with its something, you have a solution for a subproblem.
It is easy to find a valid something by minimizing the number of conflicting items to remove.
For instance, you can use the conflict optimizer to solve a sudoku, but we do not see how to use it for solving the travelling salesman problem. You can test uses of the conflict optimizer for the sudoku problem (note that humans don't do it that way) and for the SAT problem.