# Category Archives: Challenge

## INFORMS 2010 Wrap-Up

I had a very productive and fun time at the INFORMS Annual Meeting in Austin, Texas. So I thought I’d share with you some of my observations about the meeting:

• Analytics initiative by INFORMS: great idea! I believe that we (INFORMS members) have to jump onto the Analytics bandwagon and let everyone know that we can do Analytics too! It’s all about the power of words these days (see the country’s political arena for a perfect example). Starting today, I’ll tell everyone that I can do “Advanced Prescriptive Analytics” (optimization).
• Panel on Social Networks: it was nice to hear from some of the most popular OR bloggers and learn about their motivations, fun stories, and blogging strategies. Great job Mike and Laura!
• John Birge‘s plenary (Omega Rho Distinguished Lecture): very informative and entertaining. The simple and powerful take-home message was: align incentives. What’s good for the employees has to be good for the company as well.
• RAS Problem Solving Competition: Michael Trick and I (a.k.a. Team MATHY) received an honorable mention at the Railway Applications Section (RAS) 2010 Challenge (certificate + photo :-). After watching the three finalists’ presentations, we were happy to see that our solution value of $11,399,670.88 was equal to the best solution found by the winning team, and better than the solution found by the other two finalists. Nobody managed to prove optimality, though. Interestingly, none of the finalists thought about scaling the problem (thinking in terms of tanks of gasoline instead of gallons of gasoline), which made a huge difference in the performance of our model. Overall, it was a lot of fun to participate in this competition and I want to thank the organizers for putting it together. Here’s a picture of team MATHY with Juan Morales from BNSF Railway. And here’s a picture of the railroad network we had to deal with: • Technical sessions: I watched many interesting and inspiring talks (as a matter of fact, I had some great ideas for my own research while watching a number of presentations). It’s nice to see that *a lot* of people are using Latex Beamer these days. Let’s aim for a Powerpoint-free INFORMS by 2020! • Idea for an iPhone App? I applaud the going-green initiative of reducing the number of conference program booklets that have to be printed out. However, for this to work it requires a lot of organization from each of us: we have to go over the program in advance, select the talks we want, and print the appropriate pages. I don’t know about you, but I never manage to get this done. So I propose we create an iPhone (mobile) app to allow participants to browse the program on-the-go. It’s not convenient to browse the program PDF on a phone. We need an app. We need to be able to filter by author, by chair, by topic/keyword, etc. We want a time-sensitive app that tells you what’s next. We want an app that sends notifications to your phone reminding you that a talk/event is coming up so that you ask for the check in time. If we had something like that, I think that a lot fewer people would ask for a printed program (myself included). • Thumbs up for all the vegetarian food: being a vegetarian myself, I was impressed with the generous availability of vegetarian food (i.e. not only salad) at both the Sunday and Tuesday receptions. Well done! • Austin’s Convention Center: in addition to being huge, the convention center’s numerous under-construction areas made it very hard to navigate from session to session. I always felt like I was taking the longest path from point A to point B. • Meeting old and new friends: it was great to make many new friends and to meet old friends from my PhD days at Carnegie Mellon at the Tepper Alumni reception. I also had some very productive research meetings with several colleagues. Last but not least, I’d like to thank John Hooker, Christopher Beck, and Willem-Jan van Hoeve for agreeing to give a talk in my session, and Willem for inviting me to present in his session. Time to say bye-bye to weird Austin and fly back to Miami! Hence, I had to put on my “U” shirt: 10 Comments Filed under Analytics, Challenge, INFORMS, iPhone, Travel ## 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!