Painting by numbers

A client of mine was trying to implement as an exercise the models in Robert A. Bosch, "Painting By Numbers", OPTIMA 65, May 2001. He was using Excel/Frontline. (Being snowed-in for some days causes people to do strange things).  My guess is that this is not completely trivial. The indexing is somewhat complicated, as illustrated by some of the messy math:

However it is not too difficult to use both Excel as front-end and a real modeling system to deal with the model:

It looks like this picture is slightly different than in the Bosch article (figure 4).

Basically we export the raw data immediately (i.e. with minimal preprocessing) to the GAMS model and ship the final solution (which cells to paint black) back to Excel. IMHO, this is often more convenient than trying to do everything in Excel.

Turns out the well-known mip solvers such as Gurobi and Cplex do a good job on (most of) these models. In http://webpbn.com/survey/ the performance looks dismal for this formulation (see last column labeled Bosch/glpk) but I see much better results. First this formulation can easily handle empty rows, so the ‘X’ entries can disappear. Second for most models zero nodes are needed, so many models solve fairly quickly. That should remove some of the entries with ‘-‘.