Originally posted by: JorisK
Dear,
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.
I'll first show you some relevant code sections:
In the code below (Java), variables are declared, as well as 2 sets of constraints:
cp =
new IloCP();
/*Create the variables * problem.getR() returns the radius of the container, circle.getR() the radius of Circle circle. * problem.getCircles() returns a list of Circles, ordered in decreasing size. * A square is drawn around the container. Top-left coordinate is 0,0, bottom right is 2R,2R, where R is * the radius of the container */ xCors=cp.intVarArray(problem.getCircles().size(), 0, 2*problem.getR()); yCors=cp.intVarArray(problem.getCircles().size(), 0, 2*problem.getR());
for(Circle c: problem.getCircles())
{ xCors[c.getId()].setName(
"x"+c.getId());
//Holds the x-coordinates of the center of the circles yCors[c.getId()].setName(
"y"+c.getId());
//Holds the y-coordinates of the center of the circles
}
//Add the constraints
//1. Ensure that all the circles end up inside the outer circle.
for(Circle c: problem.getCircles())
{ IloIntExprArg f1=(IloIntExprArg) cp.square(cp.diff(yCors[c.getId()], problem.getR())); IloIntExprArg f2=(IloIntExprArg) cp.square(cp.diff(xCors[c.getId()], problem.getR())); IloRange constr=cp.le(cp.sum(f1, f2),Math.pow(problem.getR()-c.getR(),2)); cp.add(constr);
}
//2. Ensure that two circles do not overlap
for(
int i=0; i<problem.getCircles().size()-1; i++)
{
for(
int j=i+1; j<problem.getCircles().size(); j++)
{ Circle c1=problem.getCircles().get(i); Circle c2=problem.getCircles().get(j); IloIntExprArg f1=(IloIntExprArg) cp.square(cp.diff(yCors[c1.getId()], yCors[c2.getId()])); IloIntExprArg f2=(IloIntExprArg) cp.square(cp.diff(xCors[c1.getId()], xCors[c2.getId()])); IloRange constr=cp.ge(cp.sum(f1, f2),Math.pow(c1.getR()+c2.getR(),2)); cp.add(constr);
}
}
When feeding this model to the solver, no solution is found (within a time limit of 8 hours). The model is however correct as it is capable of finding a feasible solution when I decrease the variable domains using an optimal solution found by the heuristic solver.
First of all, I have tried to improve this model by removing the huge amount of symmetry. 1. Each solution can be rotated. 2. For a given solution, 2 identically sized circles can be swapped.
To solve 1. I fixed the position of one of the circles such that its border touches the outer rim of the container (starting from the solution with 1 fixed circle, the problem could still be solved according to the heuristic solver).
To solve 2., I created a hash based on each pair of x,y coordinates for each circle. Let S be a set of identically circles (having the same diameter) of size n. Since circles may not overlap, it is possible to impose an ordering on the circles based on their hash values. E.g. h(c_1)<h(c_2)<h(c_3)<...<h(c_n), where h(c_n) is the hash value of the x,y coordinates of circle c_i\in S.
Interestingly, adding the additional constraints which are supposed to break the symmetry did not improve the model! To test the model, I created a simpler version of Crux 25. I still used 25 pieces, but I increased the size of the container, hence making it easier. Solving this simplified version without the symmetry breaking constraints is faster than solving the same instance with the symmetry breaking constraints included! Does anyone know why? The additional constraints create some overhead, but certainly not more then the overhead caused by the symmetrical solutions?
One important aspect seems to be the order in which variables are being determined. Clearly it would not make sense to first determine the x coordinates and later all the y-coordinates. The best order (I presume) is to first place all the large circles, than the medium circles and finally the small circles. So first xCor[0] and yCor[0] need to be determined, next xCor[1] and yCor[1], ..., and finally xCor[n] and yCor[n]. How can I enforce this? It seems that you can guide the search using IloVarSelector, but I'm not sure how to do that in this case?
Following on this idea, there is also an order in which the values should be assigned to the variables. In a feasible solution, circles will always touch eachother (unless the container is very large). So instead of trying a value which assigns a cycle a position somewhere in the middle of the container without any direct neighbors, one would first assign the cycle a value such that it touches earlier placed cycles. I'm not sure how to achieve that either.
Finally, are there more suggestions to speed up the search? Any global constraints I should use?
As a last thought, I was wondering whether perhaps CP Optimizer would perform better if I created an optimization version of the problem instead of a SAT problem (although this sounds counter-intuitive). What I could do is add for each circle a boolean variable indicating whether the circle is placed in the container or not. As an objective, I would then maximize the number of placed containers. The constraints are then adjusted such that only 'placed' circles cannot overlap.
#CPOptimizer#DecisionOptimization