domino optimization art

Domino opt-art version of me

I discovered a picture of me in my student lab – one of the students optimized me for a class project using dominos(!)  My second blog post ever was about Bob Bosch’s optimization art – see some of his domino art here. It’s worth revisiting opt art.

Bob Bosch wrote about his domino optimization models in Math Horizons, a trade journal from the Mathematical Association of America, and OR/MS Today. Bob also does other types of optimization art (TSP art, mosaic art, etc.). Let’s take a closer look at domino art.

The art is created by solving an integer programming model that finds the arrangement of dominos that is closest to the picture. When complete sets of dominoes are used, there are limited numbers of each type of tile/domino, and intelligently using each type of domino (a limited resource) by assigning it to the “right” part of the photo is the basis for the optimization model.

First, the photo of interest is divided into m x n squares. The goal is to fully use s sets of dominoes, where each set of dominoes contains 55 tiles. Therefore, the photo must be divided into squares such that is satisfies

.

The photo must then be divided into a set P of adjacent pairs of squares to account for different domino orientations (i.e., laying a tile horizontally or vertically). Decision variable is 1 of we place domino d on the photo to cover pair p and 0 otherwise. There is a parameter  that captures the “cost” of placing domino d on the photo to cover pair p based on the brightness of the photograph and the number of dots on the tiles. This then gives us an integer programming model that is an assignment problem variation:

The objective function minimizes the deviation between the photo and the placement of the dominoes. The first set of constraints ensures that all dominoes are used. The second set of constraints ensures that each pair in the photo is covered by exactly one domino. Bob’s article in  Math Horizons has all the details on constructing the set P and computing the costs. There is no shortage of cool opt art photos of Bob’s creations – check out his stuff on twitter and his web site.

What do you think of my domino photo? I think it’s terrific, but I think I prefer the non-optimized version of me.