Originally posted by: JorisK
I'm relatively new to Constraint Programming and the the ILOG CP optimizer. Hence I decided to try to solve a simple puzzle using CP Optimizer. The puzzle I'm trying to solve is called Crux 25. Given are a set of circles. Based on their diameter, the circles can be grouped into 3 different sizes (1x large, 10x medium, 14x small). Goal of the game is to place all circles in a large circular container. The circles may not overlap. Clearly this is a simple SAT problem (circle packing problem). A smaller problem instance (not the crux 25 one), and a possible solution, is depicted in this figure:
http://mathworld.wolfram.com/images/eps-gif/CircleTriplets_1000.gif Two solvers for the Crux 25 problem have been implemented: 1. a heuristic, capable of solving Crux 25 within a few minutes. 2. a solution based on CP Optimizer, currently incapable of solving Crux 25. Obviously, I found the latter quite frustrating, so I was wondering whether you could give me some suggestions, and comments. Below I'll discuss the model I'm using, as well as several implementation considerations.
Model (using latex notation):
Let R be the radius of the container, C the set of circles, c.r the radius of circle c \in C, c.ID the ID of circle c \in C, c.x resp. c.y the x,y coordinates of circle c\in C. The coordinate R,R is the center of the container.
Then the following constraints model the problem:
1. (c.y-R)^2+(c.x-R)^2 <= (R-c.r)^2 \forall c\in C
2. (c1.y-c2.y)^2+(c1.x-c2.x)^2 >= (c1.r+c2.r)^2 \forall c1,c2\in C, c1 \neq c2
Constraint 1 requires that each circle is completely contained within the container. Constraint 2 ensures that circles do not overlap. Basically, Constraint 1 and 2 are sufficient to model the problem, but the performance is bad (crux25 cannot be solved). Hence I simplified the crux25 problem instance by increasing the radius of the container. The simplified instance is solved in 49s using constraints 1 & 2.
Proposition 1 - Breaking symmetry. Two solutions are identical if one solution is a rotation of the other. Proposed solution: fix the position of a single circle. Result: solution found in 45s (4s improvement).
Proposition 2. In difficult problem instances, a feasible solution is a tight packing where each circle will touch at least one other circle. Constraint:
3. \sum_{c2 \in C, c2 \neq c1}
http://(c1.y-c2.y)^2+(c1.x-c2.x)^2 == (c1.r+c2.r)^2 >=1 \forall c1\in C
Hypothesis: This constraint should improve domain reduction.
Result: NO solution was found within 10 minutes. Only by decreasing the variable domains manually, a solution could be found. Why does the performance become so bad when adding this constraint? Judging from the documentation, it should be a good thing to add redundant or trivial constraints to improve domain reductions? Due to its bad performance, constraint 3 is dropped.
Proposition 3 - Breaking symmetry 2. Two solutions are the same if one solution is obtained from the other by swapping two equally sized circles. To prevent this, we impose an order on equally sized circles using a hash function. Constraint:
4. 13*c1.x+17*c1.y < 13*c2.x+17*c2.y \forall c1,c2 \in S, c1.ID<c2.ID
where S \subseteq C is a set of identically sized circles.
A solution was NOT found within 10 minutes. Only by decreasing the variable domains manually, a solution could be found.
Again a huge performance decrease, even though symmetry has been removed. Any clue why this performance decrease occurs? Constraint 4 is removed from the model.
Proposition 4. The order in which circles are placed matters. In general it makes sense to first place the largest circle, then the second largest circle, ... and finally the smallest circle. So we first order the circles in decreasing size. Next, in the searchPhase we set a variable selector which will first select c1.x, then c1.y, then c2.x, c2.y, c3.x... Solution found in: 682s. Again a pretty bad result.
Basically, the overall performance of the CP using Constraints 1 and 2 is bad. In addition, whichever constraint I seem to add to improve the CP model, the performance gets even worse. What is going wrong? How can I improve the performance? I will try to implement this problem using a different CP solver to see whether the performance issues are caused by the ILOG CP optimizer.
Ps. Is there a different, more active CP community (forum/mailing list/irc channel) as judging from the thread dates, this forum isn't used very much.
#ConstraintProgramming-General#DecisionOptimization