Opt Art

New book by TSP and Domino art creator Robert Bosch [1].

Content:

1. Optimization and the Visual Arts?
2. Truchet Tiles
3. Linear Optimization and the Lego Problem
4. The Linear Assignment problem and Cartoon Mosaics
5. Domino Mosaics
6. From the TSP to Continuous Line Drawings
7. TSP Art with Side Constraints
8. Knight's Tours
9. Labyrinth Design with Tiling and Pattern Matching
10. Mosaics with Side Constraints
11. Game-of-life Mosaics

Yes, it contains color pictures.

TSP Art

An example of a TSP drawing (from [2]):

25,000-city TSPortrait of George Dantzig [2,3]

Original fotograph

I guess more cities are needed to prevent his teeth from disappearing.

Domino Art

You can submit your picture and create a domino mosaic through NEOS [4].  I tried this with the Dantzig picture. With a "high quality" output image this creates a large model:

Reduced MIP has 13915 rows, 1511565 columns, and 4534695 nonzeros.
Reduced MIP has 1511565 binaries, 0 generals, 0 SOSs, and 0 indicators.

This is not small at all. Although the model is large, it is easy to solve. It only took 11 nodes (most of the work was in the root node). The model is an assignment problem with side constraints [5]. Basically the costs are the difference in gray scale value between the picture and the domino piece for each cell. The constraints are: exactly one domino in each cell and place all dominos. NEOS solves this by processing the picture in Matlab and then solving the model with GAMS/CPLEX. The output PNG file is also notably large: 2.8 MB. Too large to include in this blog. A screen grab looks like:

Screen capture of hi-res image

After zooming in we see indeed the dominos:

Zooming in

With some effort we can recognize part of the frame of the eye glasses here.

References

1. Robert Bosch, Opt Art, From Mathematical Optimization to Visual Design, 2019,  https://press.princeton.edu/books/hardcover/9780691164069/opt-art
2. http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html
3. https://en.wikipedia.org/wiki/George_Dantzig
4. https://neos-guide.org/content/domino-art
5. Robert Bosch, Opt Art, Math Horizons 14(3) (2006) 6-9, https://www.maa.org/sites/default/files/pdf/upload_library/22/Evans/Horizons-Feb06-p.06-09.pdf