Optimization & Art: Linear Programming Formulation for LEGO Portraits

Voiceover

Presenter(s)

Gabriel Elftman-Hanson

Abstract or Description

Combinatorial optimization is a powerful modeling and problem-solving tool used in many real-world applications to determine the best (or “optimal”) choice from a discrete set of possible options. However, the techniques used can also be applied in a more creative capacity: optimization art.  In this poster, we explore this intersection of mathematics and art utilizing Python via Jupyter Notebook (open source) and the well-known optimization solver Gurobi.  

Many well-known examples of optimization art were popularized by Dr. Robert Bosch of Oberlin College. His 2019 book, “Opt Art”, presents an overview of the key techniques. The goal of this project was to develop these optimization methods and apply them to new artistic applications. That is, for our chosen image, we ask what is the best way to reconstruct it using a given LEGO portrait set, i.e., we are restricted to a fixed size and color allotment of the tiles.  

To accomplish this, we began by studying a previous Python implementation of artwork construction methods. However, to solve the problem of interest, these techniques had to be expanded because our chosen method requires a more complex optimization approach.  In particular, our work uses a linear programming formulation to model the problem of LEGO artwork construction. 

After identifying the correct mathematical formulation, we modeled the LEGO problem in Jupyter Notebook and utilized the Gurobi solver to determine the optimal solution. We then wrote a program that tiles an image based on this optimal solution to produce a LEGO version of the original image. In this poster, we present our findings by explaining the mathematics used, breaking down our code, and showcasing examples of the LEGO artwork produced.

Mentor

Emily Speakman