Death, taxes and optimization

A few months ago, I created a programming challenge, an invitation to do some old-fashioned programming from before the LLM era. The goal was to write a solver for Rushhour. Give it a try! It is a lot of fun, almost as much fun as playing the game!

I implemented two classical search algorithms: BFS and $A^{*}$ .

According to the Book 📗, $A^{*}$ is cost-optimal if it uses an admissible heuristic, i.e., one that never overestimates the cost to reach the goal. The heuristic I used counts the number of blocking cars in front of the red car 🚗. This heuristic is admissible because one would need at least that many moves to reach the goal. Right? Therefore, the solutions provided by $A^{*}$ should be cost-optimal.

So, what’s the point of expressing Rushhour as an optimization problem?

A few calculations will quickly make you reconsider. With a board of $6\times6$ and a maximum number of $50$ steps, plus variables for representing the cars and other auxiliary variables, you end up with thousands or tens of thousands of discrete variables and constraints, possibly including nonlinear or indicator constraints linking the car moves to their positions on the board.

In short, there is no practical point. It’s just for fun.

The main reason I wanted to do this is that when my son brought home this game from the library, the first thing I wondered was if I could formulate it as an optimization problem. So here we are.

If you prefer reading the code, you can jump directly to it here.

Representing the board and the cars

First, we must decide how to represent the board and the cars. The board can be modeled as a three-dimensional binary variable $b(T, 6, 6)$ , where $T$ is the maximum number of time steps and $1$ represents occupied and $0$ represents free. Each car can also be represented as a binary variable of shape $(T, N)$ , $N\in \{2,3\}$ .

I spent quite some time trying to figure out how to link car’s movement to the board, which is non-trivial in a declarative formulation. One cannot simply “assign” a variable based on the outcome of another variable.

It took me a 40-minute walk to come up with a different solution that doesn’t require complicated constraints. Rather than modeling the board and the cars separately, I model them together, adding one more dimension to the board $b(T, C, S, S)$ .

This approach simplifies the logic but it adds a lot of unnecessary variables, even if only a few rows and columns have active constraints.

I ended up combining both approaches by modeling the cars and the board as separate variables but operating on them as if the cars were an additional dimension of the board.

→ Parameter: $T=50$ , maximum number of time steps.

→ Parameter: $S=6$ , board size.

→ Parameter: $C$ , the set of cars in the current game instance, e.g, $C=\{A, B, G, H, I, J, K, O, P, Q, X\}$ .

→ Variable: $b(T, S, S) \in \{0, 1\}$ , the board.

→ Variable: $\text{cars}(T, C, S) \in \{0, 1\}$ , the cars.

→ Constraint 1: The link between the board and the cars. This set of constraints is probably best understood by looking at the code.

\begin{align*} b(t, i, j) &= \sum_{c \in C} \text{cars}(t, c, i) \\ &+ \sum_{c \in C} \text{cars}(t, c, j) \end{align*}

For all $t, i, j$ if car $c$ is in row $i$ or column $j$ .

→ Constraint 2: Non-overlapping cars

\sum_{c \in C} b(t, i, j) \leq 1 \quad \text{for all}\quad t, i, j

The following figures illustrate valid and invalid car positions according to Constraint 2.

Figure: Valid car positions - Car A board (left), Car X board (center), and superposition without overlap (right) at some time $t_{k}$

The following arrangement is not allowed:

Figure: Unfeasible car positions - Car A board (left), Car X board (center), and superposition with overlap (right) at some time $t_{k}$

→ Constraint 3: Constant car size.

\sum_{i=1}^{S}\text{car}(t, c, i) = len(c), \quad \text{for all}\quad t, c

$X$ can leave the board; that’s the objective of the game. However, I consider the position in which $X$ is about to leave to be the last one.

Even if the number of blocks that make up a car is constrained to remain constant, it doesn’t mean that the blocks are automatically contiguous.

→ Variable: $\text{pin}(T, C, S - 1) \in \{0, 1\}$

This variable indicates the starting position of the car: the leftmost and uppermost positions for horizontal and vertical cars, respectively.

→ Constraint 4: Cars can only start at one position.

\sum_{i=1}^{S-1} \text{pin}(c, t, i) = 1, \quad \text{for all}\quad t,c

However, I suspect that this condition is redundant and can be removed.

→ Constraint 5: The blocks that make up a car must be contiguous.

\text{cars}(t, c, j) = \sum_{k=0}^{len(c)-1} \text{pin}(t, c, j-k)

\quad \text{for all}\quad t, c \quad \text{if } 1 \le j-k \leq S-1 \quad

Preventing “Tunneling”

The crux of this formulation is the constraint that ensures cars of length two cannot “tunnel” through other cars. This is not an issue for cars of length three because the non-overlapping constraint guarantees that all moves are valid.

As shown in the figure below, the two moves in the middle ( $+1$ , $+2$ ) are not problematic because they are accounted for by the non-overlapping constraint. However, the move on the far right is problematic (pun intended 😉) because the red car would go through the purple car.

Figure. A car that is two tiles long starts in the third row, first column. In a single time step, it moves right by 1, 2, and 3 tiles, respectively.

Model 0

This is the base model, the first one I implemented. It restricts cars from moving more than one tile per turn. This condition prevents tunneling. The objective function is the number of steps it takes to move car $X$ 🚗 to the exit.

This model solves a normalized version of the puzzle. The optimal value is the number of one-tile moves required to solve the puzzle. This number is equal to the number of one-tile moves in the optimal solution. Unfortunately, there is no one-to-one correspondence between one-tile moves and actual moves. The solution obtained by aggregating one-tile moves generally does not correspond to the optimal solution. You can think of this solution as an upper bound though.

Model 1

This model builds on Model 0. It introduces the variable $\text{nmoves}$ , which indirectly counts the actual number of moves. A move is defined as a car that is different from the car in the previous $\text{turn}$ and that moves any number of tiles. The objective function is the sum over $\text{nmoves}$ . The resulting sequence is equivalent to the optimal one (although it must be compressed), but the objective value does not represent the actual number of moves (at least not directly). This objective function is not well-behaved, and the problem can become intractable for larger instances.

Model 2

This model uses the same objective function as in Model 0, but it allows cars to move more than one tile per turn. To prevent tunneling, a $\text{mask}$ representing the tiles between the starting and the end positions of a single move is introduced. This constraint, which is only active if $\text{turn}(t, c)=1$ , is added to the board as if it were an additional dimension. The rest of the post describes this model in detail.

Definition of Model 2

→ Variable: $z(T, C, S) \in \{0, 1\}$ , auxiliary variable to count the number of tiles a car moves in a single turn.

→ Variable: $\text{turn}(T-1, C, S) \in \{0, 1\}$ , indicates which car can move at each time step.

→ Constraint 6: Only one car can move per time step.

\sum_{c \in C} \text{turn}(t, c) \leq 1 \quad \text{for all}\quad t > 1

We will need a few tricks to represent Boolean conditions in a linear way.

	$z = a \wedge b$	$z = a \vee b$
1	$z \leq a$	$a \leq z$
2	$z \leq a$	$b \leq z$
3	$z \geq a + b - 1$	$z \leq a + b$

Table: Tricks for representing AND and OR logical conditions. Source: jump.dev

→ Constraint 7: Cars can only move if it is their turn.

\begin{align*} z(t, c, i) &= \text{cars}(t, c, j) \\ & \vee \text{cars}(t-1, c, j), \quad t>1, c, j\\ \sum_{i=1}^{S}z(t, c, i) &\leq len(c) + \text{turn}(t, c)\cdot len(c) \end{align*}

For all $t>1$ , and all $c$ .

Preventing tunneling

These constraints are rather convoluted, but I haven’t found a simpler way yet. Ideas are welcome!

The basic idea is to create a mask representing the tiles between the car’s starting and ending positions in the current turn. This mask is then added to the board as an additional dimension to ensure there are no obstacles in the path.

→ Variable: $\text{mask}(W, T, C, S, S) \in \{0, 1\}$ , is the set of variables to implement the approach described above.

$W \in \{\text{fwd}, \text{bwd}, \text{or}, \text{and1}, \text{and2}, \text{mask}, \text{mask\_cond}\}$ is just an index to identify the different variables.

→ Constraint 8: Calculate the mask representing the car’s path as it moves through the current turn.

\begin{align*} \text{mask}(\text{fwd}, t, c, i) &= \text{mask}(\text{fwd}, t, c, i-1)\\ &+ \text{pin}(t, c, i)\quad i=1\dots S\\ \text{mask}(\text{bwd}, t, c, i) &= \text{mask}(\text{bwd}, t, c, i-1)\\ &+\text{pin}(t, c, i)\quad i=S-1\dots 1\\ \text{mask}(\text{and1}, t, c, i) &= \text{mask}(\text{fwd}, t-1, c, i)\\ &\wedge \text{mask}(\text{bwd}, t, c, i)\\ \text{mask}(\text{and2}, t, c, i) &= \text{mask}(\text{fwd}, t, c, i)\\ &\wedge \text{mask}(\text{bwd}, t-1, c, i)\\ \text{mask}(\text{mask}, t, c, i) &= \text{mask}(\text{and1}, t, c, i)\\ &\vee \text{mask}(\text{and2}, t, c, i)\\ \text{mask\_cond}(t, c, i) &= \text{mask}(\text{mask}, t, c, i)\\ &-\text{cars}(t, c, i) \end{align*}

For all $t>1, c, i$ . The last constraint is implemented using the auxiliary variable $\text{mask\_diff}$ and big-M constraints. The Boolean operations are implemented using the aforementioned tricks. See the code for details.

Success criterium

The goal of the game is to get the red car $X$ 🚗 to the exit.

Figure: Car X at the exit position

→ Variable: $\text{exit}(T) \in \{0, 1\}$ , indicates wheter car X is at the exit position at time step $t$ .

→ Constraint 9: Car X must be at the exit at some time step $t < T$ .

\begin{align*} \text{exit}(t) &= \text{cars}(t, X, 5) \wedge \text{cars}(t, X, 6) \quad \text{for all}\quad t\\ 1 &= \sum_{t=1}^{T} \text{exit}(t) \end{align*}

Objective function

→ Objective: Minimize the number of time steps it takes for car X to reach the exit.

\text{Min} \sum_{t=1}^{T} t \cdot \text{exit}(t)

Conclusions

A note on the solvers

I tried HiGHS and cuOpt which was recently open-sourced. However, I only had success with HiGHS. I didn’t investigate why cuOpt failed in these instances.

Based on this and previous experiences, my only conclusion is that HiGHS is a superb solver.

Open questions

I am convinced that this is one is not the best possible formulation. Ideas are welcome!

Final thoughts

I enjoy doing this kind of work because I always learn something new. If you compare the Branch and Bound (B&B) algorithm used by HiGHS with the $A^{*}$ algorithm, you will see that they are very similar. I learned that someone in the past tried to generalize these ideas —search algorithms, dynamic programming, and B&B— into a single concept. Check out this article.

And a final though on optimization, and why the title of this post is “Death, taxes and optimization”.

Optimization is one of those beautiful, pervasive theories that has made an indelible mark on the history of mathematics, engineering, and many other disciplines since its inception. It will continue to be relevant, even if hidden behind something more showy and bombastic. Mathematical optimization is a fundamental discovery. It will continue to be relevant in the foreseeable future and will survive all the hype.

If those lines sound dramatic and opinionated, they are. They’re also true 😉.