The image of Homer Simpson below was drawn using 25 complete set of double-9 dominos in the following way: the (high resolution) target image was converted to grayscale; with each pixels intensity rounded to a value between 0 (black) and 255 (white). The image was then divided in a rectangular grid with a total number of 2 25 55 cells. (25 for the number of domino sets; 55 is the number of dominos in a set of double-9 dominos.) Each domino has to cover exactly two adjacent cells of this grid. The mean gray value of all the pixels contained in each grid cell was computed and rescaled and rounded from [0, 255] to the target intensity {0, . . . , 9} to match the number of dots of our dominos. Now, when a domino is placed on a pair of cells, the error (or cost) is computed in each cell as the absolute difference between the target intensity value of the cell and the number of dots on the half-domino covering this cell. The goal is to find a placement of all the dominos on this grid such that the overall error (the sum of the error of all cells) is minimum. Formulate this as an integer linear program with binary variables.

.: H i dit H.-. HICAH . .F,...-fe",_..-::///: .,',' H H # //Ht:.: HHI! //// /HXX1HXH.. : HH,' //2..H:-: 2..H..-# I1:HI! ,' Hih","//:://x:-:n::../x::::x.. . # # . : .. :H //H.."X:-:H..H :H HI: / // //H 10#X.__ H?.. H // . . HHH// lll H H H HI ! l H H . HH.::..HHH!!n!! E!1HHH : ////:.: H , .: H i dit H.-. HICAH . .F,...-fe",_..-::///: .,',' H H # //Ht:.: HHI! //// /HXX1HXH.. : HH,' //2..H:-: 2..H..-# I1:HI! ,' Hih","//:://x:-:n::../x::::x.. . # # . : .. :H //H.."X:-:H..H :H HI: / // //H 10#X.__ H?.. H // . . HHH// lll H H H HI ! l H H . HH.::..HHH!!n!! E!1HHH : ////:.: H