|
Abigail Lindner Worcester Polytechnic Institute |
|
Nandan Kumar Singh Indian Institute of Management Visakhapatnam |
Introduction
The mathematician does not study pure mathematics because it is useful; he studies it because he delights in it and he delights in it because it is beautiful. - Henri Poincaré (1854-1912)
Operations research (OR) has a long history of contributing to supply chain management, transportation routing, and other business problems. Less well-known is the use of OR tools in non-technical fields. In the humanities, OR appears in the production of pieces of modern art via reframing of the Traveling Salesman Problem and the application of linear optimization and graph partitioning.
Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is a classical question in operations research. The objective of the TSP is to identify the best route through N cities, represented by points, that visits each city exactly once and return to the origin city. The “best” route might be the shortest (distance), least expensive (sum of the costs of each leg of the journey), or a combination of the two.
Dr. Robert Bosch, James F. Clark Professor of Mathematics at Oberlin College & Conservatory, has gained a reputation for creating “optimization art,” which he details in his 2019 book Opt Art: From Mathematical Optimization to Visual Design (Bosch, 2019). Among his inventions is visual art made by treating classic paintings and prints as canvases on which a TSP may be overlaid.
Consider the Mona Lisa, by Leonardo da Vinci, arguably the most famous painting in the world. In place of the lines and curves that form the original painting, Bosch converted the Mona Lisa into a series of tens of thousands of dots representing “cities” in the TSP (Cook, 2022). The optimal solution to the TSP is the continuous-line drawing of the original Mona Lisa that is as accurate as possible.
For small-scale routes of, say, 5 cities, an analyst could determine the optimal route by trying each of the (5−1)!/2 = 12 possible solutions. Dealing manually with the 100,000 “locations” that make up Bosch’s Mona Lisa problem, however, would be a feat of inhuman endurance and an impossible lifespan. Hence, mathematical optimization tools, which are often employed in OR work, are essential to this TSP art (Klotz, 2015).
These experiments in reproducing works of traditional art through mathematical methods are a fun exercise of optimization theory, and worth trying. In the case of the Mona Lisa, successful efforts to find a route shorter than current best solution also entail a cash prize of $1,000 (Cook, 2022)! The current best TSP solution for the Mona Lisa, depicted above, was found in 2009 by Yuichi Nagata and has length 5,757,191, which is 107 more than the lower bound that Cook has identified for an optimal solution (Cook, 2022).
Figure 1: Mona Lisa TSP challenge, From Robert Bosch,William Cook, and Yuichi Nagata
Source: https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html
The Mona Lisa TSP was commissioned by William Cook. The point set was designed by Robert Bosch and the tour was obtained by Yuichi Nagata. The image can also be found on page 108 of Robert Bosch’s Opt Art.
Domino Mossaic
Consider a single set of dominoes, which contains 55 rectangular tiles. Ignoring some “messy details of geometry and orientation, there are more than 1073 ways of placing the 55 tiles” (Hayes, 2020). Now consider 44 sets of dominoes. There are millions of ways to place all 2,420 tiles. What are the odds that one of these arrangements will produce a portrait of, say, former U.S. president Barack Obama?
The idea of recreating pictures and photos with dominoes - creating domino mosaics - originates with Ken Knowlton, a computer graphics pioneer and artist who worked at Bell Labs in the mid-20th century. During his tenure at Bell Labs, Knowlton experimented with the new capabilities of then-modern technology to create art. He made computer-assisted “mosaic art” with unconventional art tools, including dominoes. (A summary of Knowlton’s work is accessible at https://www.knowltonmosaics.com/.)
Bosch drew inspiration from Knowlton to create more complex domino mosaics. As with the TSP art, Bosch aimed to produce the likeness of a monochrome image that “most closely matches the pattern of shadow and light in the original” (Hayes, 2020). His predecessor Knowlton used a two-step process: first, he generated a “pattern of empty domino holders” on a canvas; next, he assigned dominoes to the holders according to brightness, a value based on the number of pips on the domino tile (Cambazard et al., 2011). Bosch diverged by transforming the domino mosaic problem into an integer linear programming problem.
On Bosch’s Domino Artwork site, beginners can download guides to produce portraits of Abraham Lincoln and Martin Luther King, Jr., or recreations of the Mona Lisa and the Statue of Liberty using 12 sets of dominoes. The downloads page is at http://www.dominoartwork.com/downloads.html.
Figure 2: From Robert Bosch, 2008
Source: https://www2.oberlin.edu/math/faculty/bosch/barack-obama-domino-plans.html
Permission to use obtained from Dr. Robert Bosch on May 2, 2022. This image can also be found on page 82 of Robert Bosch’s Opt Art.
Graph Partitioning
Graph theory is a discipline focused on graphs, mathematical structures that model pairwise relationships between objects. It began as a recreational math problem, but it has now evolved into a prominent field of mathematics with applications in chemistry, operations research, social sciences, and computer science.
Partitioning a graph is a critical step in parallelizing graph algorithms (“Graph partitioning”). It divides a complex problem into multiple, more manageable sub-problems that may be solved in parallel. Graph partitioning algorithms are executed using either edge or vertex separators, depending on the algorithm. Effective partitioning can reduce the time and effort to solve the problem.
How does graph partitioning connect to art? Consider INFORM, a software company which provides digital decision making based on Artificial Intelligence (AI) and Operations Research. The company uses an effective algorithm for graph partitioning to solve routine projects, the results of which have surprising artistic value. One context in which an algorithm developed by INFORM was used for a routine project and transformed into art is a bill of materials structure (Keppner, 2015b).
A bill of materials (BOM) details the components and assemblies needed to construct a comprehensive network structure. Oleg Shilovitsky, a software developer and the CEO of OpenBOM, highlights the importance of graph theory in transforming the BOM into a graph that will be helpful in production planning and analysis (Shilovitsky, 2020a). The network artifact that results from the synthesis of many BOMs can serve as a model for analyzing product information and the relationships between the components that comprise the graph (Shilovitsky, 2020b). Shilovitsky notes that this network can also be a source of artistic interest.
For Keppner, the BOM structure above is where he first realized the artist value of supply chain project visualizations. In this, the 5,564 nodes represent a completed product or a precursor to a complete product and nodes of the same color share the same production resource. Greater size indicates that the completed product consumed a higher percentage of the given resource. This graph is an aggregation of 52 mappings of weekly production capacities over a single year.
Unlike the TSP art and domino mosaics, the creators of these graphs had no intention of creating art. Keppner saw this graph displayed on the wall behind a colleague’s desk and assumed that it was a work of abstract art. His mathematical colleague clarified the content of the graph, but Keppner still thought, “This should be framed.” Unintentionally, the BOM structure mimicked features of modern art, and from that day forward Keppner began looking at his work through a more visual, artistic lens (Keppner, 2015b). Other supply chain projects that use graph partitioning algorithms, such as workforce planning and aircraft scheduling, exhibit similar features.
Figure 3: Bill of materials structure
Source: https://www.inform-software.com/blog/post/the-thin-line-between-operations-research-and-modern-art
Permission to use obtained from Kai Keppner on May 4, 2022.
Conclusion
The use of OR in producing modern art is relatively little-known, but there is an amazing store of examples to be discovered. The preceding discussion shares just a small fraction.
Kai Keppner, Head of Corporate Marketing at INFORM, sees two levels of beauty in optimization algorithms translated into graphs: “the visual form which everyone can appreciate, and the underlying aesthetics of pure numbers which is only accessible to a smaller group of mathematicians” (Keppner, 2015a). This idea can be applied to the graph partitioning done by decision-making companies and extended to the less conventional graphs of TSP portraits and domino mosaics.
Many thanks to Dr. Robert Bosch for his corrections and inputs on the early drafts of this article.
References:
- Bosch, R., 2019. Opt Art: From Mathematical Optimization to Visual Design. Princeton University Press.
- Cambazard, H., Horan, J., O’Mahony, E., O’Sullivan, B., 2011. Domino portrait generation: a fast and scalable approach. Annals of Operations Research 184, 79–95.
- Cook, W., 2022. Monalisa tsp challenge URL: https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html.
- Hayes, B., 2020. Mathematical mosaics. American Scientist. URL: https://www.americanscientist.org/article/mathematical-mosaics.
- Keppner, K., 2015a. Supply chain, operations research & modern art. All Things Supply Chain. URL: https://www.allthingssupplychain.com/supply-chain-operations-research-modern-art/.
- Keppner, K., 2015b. The thin line between operations research and modern art. INFORM URL: https://www.inform-software.com/blog/post/the-thin-line-between-operations-research-and-modern-art.
- Klotz, E., 2015. Finding mathematical optimization in unexpected places: The art world. gurobi optimization. INFORM URL:https://www.gurobi.com/resource/finding-mathematical-optimization-in-unexpected-places-the-art-world/.
- Shilovitsky, O., 2020a. Graphs, networks, and boms – part 1. Openbom URL: https://www.openbom.com/blog/graphs-networks-and-boms-part-1.
- Shilovitsky, O., 2020b. Openbom: Graphs, networks, and bill of materials – part 3. Openbom URL: https://www.openbom.com/ blog/openbom-graphs-networks-and-bill-of-materials-part-3.