Opt Art 3: Linear Optimization and the Lego Problem

Opt Art: Chapter 3

The meeting began with an abundance of drinks and snacks that everyone had kindly provided. In the time between meetings, a few people had built their own implementations of Flexible Truchet Tiles from chapter two:

• https://dmitrykandalov.com/truchet-tiles/
• https://urbanautomaton.github.io/optart/02/

Becka also presented an implementation that started from a random pattern and gradually changed to an image.

We began with our usual round of introductions and then collectively decided to spend the meeting working through the chapter together, since it contained a lot of technical material, rather than attempt to mob program an implementation.

The chapter introduced us to a "toy problem" in which two different products could be made out of "small" and "large" pieces of lego. Each product required a different number of resources and sold for a different amount. The objective was to maximise the total sales price whilst keeping withing the resource limits specified in the chapter.

We walked through a geometric representation of the problem and were introduced to the simplex algorithm which is an approach for finding the optimal solution based on some linear constraints. The chapter initially presented a two dimensional version of this problem (chairs and tables) and then introduced a third dimension (sofabordes) which made the problem three dimensional.

We then worked through a purely algorithmic/algebraic implementation of the simplex algorithm that worked for any number of dimensions, although we struggled a bit with some of the mathematical rearrangements of equations.

The last part of the chapter was only interested in integer solutions and we learned about how the branch and bound algorithm could be used to find these. Finally, we learned about the gurobi optimizer which is able to solve linear and integer programming problems and had a quick play to plug in the constraints from the chapter:

# Solve the following MIP:
#  maximize
#        8 * X1 + 11 * X2 + 15 * X3
#  subject to
#        2 * X1 + 2 * X2 + 2 * X3 <= 25
#        1 * X1 + 2 * X2 + 3 * X3 <= 19
#        X1, X2, X3 >= 0

import gurobipy as gp

# Create a new model
m = gp.Model()

# Create variables
x1 = m.addVar(vtype=gp.GRB.INTEGER, name="X1")
x2 = m.addVar(vtype=gp.GRB.INTEGER, name="X2")
x3 = m.addVar(vtype=gp.GRB.INTEGER, name="X3")

# Set objective function
m.setObjective(8 * x1 + 11 * x2 + 15 * x3, gp.GRB.MAXIMIZE)

# Add constraints
m.addConstr(2 * x1 + 2 * x2 + 2 * x3 <= 25)
m.addConstr(x1 + 2 * x2 + 3 * x3 <= 19)
m.addConstr(x1 >= 0)
m.addConstr(x2 >= 0)
m.addConstr(x3 >= 0)

# Solve it!
m.optimize()

print(f"Optimal objective value: {m.objVal}")
print(f"Solution values: x={x1.X}, y={x2.X}, z={x3.X}")

After the meeting, Dmitry shared an interesting technique to change the direction of Truchet tiles based on a mask image:

Thanks

Thanks to everyone who came along and contributed drinks, snacks and to Chris Lowis for hosting the meeting at his office.