December 15, 2009 · 9:59 am
↓ Jump to Comments

Let’s Join O.R. Forces to Crack the 17×17 Challenge

I recently came across this post by bit-player, which refers to this post by William Gasarch, on a very interesting feasibility problem: given an m \times n grid, assign one of c colors to each position on the grid so that no rectangle ends up with the same color in all of its vertices (see the original post for applications of this problem). Many results are known for different values of m , n , and c , but the challenge (which comes with a reward of US$289) is to decide whether a feasible solution exists when m=n=17 and c = 4 .

Apparently, some attempts have been made to use Integer Programming (IP) to solve this problem:

SAT-solvers and IP-programs have been used but have not worked— however, I don’t think they were tried that seriously.

By writing this post, I hope to get enough O.R. people excited to brainstorm together in search of a solution. Given this is a feasibility problem, another method of choice here would be Constraint Programming (more on that later).

I decided to begin with the first IP formulation that came to mind. I didn’t expect it to close the deal, but I wanted to see how far it would take me. Here it is: let the binary variable x_{ijt} equal 1 if the cell in row i and column j receives color t . There are two groups of constraints.

Every cell must have a color:

\sum_{t=1}^c x_{ijt} = 1, \enspace \forall \; i,j

Every rectangle can have at most 3 vertices with the same color:

x_{ijt} + x_{i+a,jt} + x_{i,j+b,t} + x_{i+a,j+b,t} \leq 3, \enspace \forall \; i,j,a,b,t

where

1 \leq i \leq m-1 , 1 \leq j \leq n-1 , 1 \leq a \leq m-i , and 1 \leq b \leq n-j .

The objective function does not matter (in theory), but my limited experiments indicate that it’s better to minimize the sum of all x_{ijt} than it is to maximize it. Gasarch also provides this diagram with a rectangle-free subset of size 74 for a 17 x 17 grid. I then added constraints of the form x_{ij1}=1 for every cell (i,j) with an “R” in the diagram. This may be too restrictive, since it’s not clear to me whether a feasible solution to the 17 x 17 grid must contain that diagram as a subset. If that’s true, the latter constraints help with symmetry breaking and also substantially reduce the problem size. To reduce some of the color symmetry in the problem, I also arbitrarily chose cell (1,1) to contain color 2, i.e. x_{112}=1 . Note that this still allows colors 3 and 4 to be swapped. I could have set x_{123}=1 , but that would mean taking a risk.

Finally, for the 17 x 17 grid, it is suspected that each line and each row will have three colors used four times and one color used five times, hence, I also included the following constraints:

4 \leq \sum_{j=1}^n x_{ijt} \leq 5, \enspace \forall \; i,t

4 \leq \sum_{i=1}^m x_{ijt} \leq 5, \enspace \forall \; j,t

Once again, if my understanding is correct, there’s no formal proof that the above constraints are valid.

Here’s a ZIMPL model that can be used to  generate the .LP files and here’s the 17 x 17 LP. I set CPLEX’s MIP emphasis to 4 (look for hidden feasible solutions) and first ran a 14 x 14 as a warm-up. CPLEX 12.1 finds a feasible solution in under 5 seconds (I substituted 1 for 4 in the color usage constraints above). I stopped the 15 x 15 problem after 12 fruitless hours of search, so 14 x 14 is apparently the largest of the easy instances.

I started the 17 x 17 run last Thursday. The initial IP has 1156 variables and 74,620 constraints. Pre-processing reduces that to 642 variables and 15,775 constraints. After approximately 122 hours and 77,000 nodes on a dual-core machine (3.79 GHz), no solution was found.

Now it’s time for smarter ideas. Here are a few candidates:

1) Try a column-generation approach. It’s easy to find solutions for 8×8 and 9×9 grids, which will appear as sub-grids of a 17×17 solution. So it may be possible to write a set partitioning formulation (with side constraints) that has the 8×8 and 9×9 solutions as variables.

2) Try a meta-heuristic approach (e.g. simulated annealing). This problem is probably one of those for which an almost-feasible solution (like this one) can be very far from a feasible solution.

3) Try constraint programming. I think the main difficulty here will be finding a good variable and value selection heuristic. I started building a Comet model for the problem using the global constraint cardinality; here it is. It still does not include the constraints that fix the color of the rectangle free subset provided by Gasarch, but those are very easy to add (see the code that is commented out).

Let me know what your thoughts and hunches are!

6 Comments

Filed under Challenge, Constraint Programming, Integer Programming, Modeling

Tagged as , , ,

6 responses to “Let’s Join O.R. Forces to Crack the 17×17 Challenge”

  1. Perone
    December 15, 2009 at 1:40 pm

    What about a non-naive distributed GA ?
    Greetings from RS/Brasil =)

  2. orbythebeach
    December 15, 2009 at 2:40 pm

    Sure. Care to elaborate? :-)

  3. Perone
    December 15, 2009 at 6:51 pm

    That’s the problem, with my time, when I finally finish the code, someone would have solved the problem hehe !
    But I’ll try to think a faster way to do that ;)

  4. Brian
    December 15, 2009 at 11:51 pm

    There’s quite a lot of symmetry to be broken in this problem. I know that the latest versions of CPLEX have some automatic symmetry breaking, but I wonder if more specialized symmetry breaking could be helpful here.

  5. Robert
    December 16, 2009 at 6:24 am

    In your formulation, you can add more, stronger inequalities, as follows:

    Let i < j < k <= m, and p < q < r <= n. If you now add up the inequalities for the 5 squares (i,p-j,q), (i,q-j,r), (j,p-k,q), (j,q-k,r) and (i,p-k,r) all coefficients are multiples of 2, so you can divide by 2 and round down the rhs from 5*3/2 to 7. Of course there are a lot of them, and adding all at once will slow down the LP solving, but they should be helpful in a cutting plane approach.

  6. orbythebeach
    December 17, 2009 at 11:17 am

    Brian, doesn’t fixing the colors shown in the rectangle-free subset remove all the symmetries from row and column interchange? We would then be left with color symmetries (i.e. given a feasible solution, we can obtain other feasible solutions by permuting colors). Which symmetries were you referring to?

Leave a comment