The Cleaning Robot Puzzle: The Shortest Route, Exactly

Part 3’s fast route cleans a furnished 20×20 room in 243 commands. The shortest route takes 221, and this part proves that no route takes fewer.

This is Part 9 of the cleaning robot puzzle. Part 8 wrote Part 3’s fewest-commands question as a linear program and got a lower bound from it: on that room, 220. The fast route had 243. Somewhere between the two lay the answer, and Part 8 couldn’t say where, because it had dropped two rules to make the program linear: that the robot walks between two fields a whole number of times, and that it enters every field as often as it leaves.

This part puts them back. That makes the program an integer program, which is NP-hard in general and very often solvable in practice, and the answer on that room is 221: one command above Part 8’s bound, and 22 below Part 3’s fast route. The new algorithms:

• parity as a whole-number rule: “even” is not linear, but “equal to twice a whole number” is;
• branch and bound, from scratch on top of Part 8’s exact simplex method: split the question in two whenever the answer isn’t whole, and throw away any half that can’t beat the best route found so far;
• Gomory’s cuts, read off the final tableau: rules every whole-number answer obeys and the fractional one breaks;
• Hierholzer’s algorithm, which turns the numbers back into a route;
• strong and weak formulations: two ways to say “connected”, one compact and weak, one huge and strong, and why HiGHS needs both.

As in Part 8, everything written from scratch uses only Python’s standard library, and the big rooms use HiGHS through highspy. Every file behind all the parts is listed in the code’s README.

What Part 8 left open

Part 8’s program counted, for every pair of neighbouring fields, how many times the route walks between them, $x_e$, and marked where it ends, $z_v$. It asked for every set of fields without the start to be entered and left, and minimised the number of steps. As a linear program it may use fractions, and it does: an answer can walk between two fields half a time, or end a third of the way through a field. Its minimum is a lower bound on every route, and on the 300 small rooms of Part 8’s test it was the exact answer every time.

On bigger rooms it isn’t. Here is the smallest room the search for Part 9’s tests found where it falls short, ten fields:

########
######.#
######.#
####...#
####*..#
####..##
########

Part 8’s program proves at least 10 commands. The shortest route has 11, and so does Part 3’s fast route. So the fast route was the best all along, but nothing in Part 8 could prove it.

Putting parity back

A route, closed with a free step from its end back to the start, enters every field as often as it leaves it: every field touches an even number of steps. Part 8 dropped that rule because “even” is not something a linear program can say. It can say it with one more variable per field, a whole number $w_v$:

and $x(\delta(s)) - z_s + 1 = 2\,w_s$ at the start, where the closing step always arrives. If $w_v$ must be a whole number, the left side must be even. So the rule is linear after all, provided some variables must be whole numbers: a mixed-integer linear program, or here, since everything is whole, an integer program. Its minimum is exactly the shortest route.

Linear programs can’t enforce “whole number”. The rest of this part is how to make them.

Branch and bound

Solve the linear program. If the answer is all whole numbers, it is a route, and since no route can do better than the linear program’s minimum, it is the shortest. Otherwise some variable has a fractional value, say $x_e = \tfrac12$. Every route walks that pair a whole number of times, so every route has either $x_e \le 0$ or $x_e \ge 1$. Split the question in two, each with one of those rules added, and solve each the same way. The fractional answer is in neither half; every route is in one of them.

That alone is a correct algorithm, and hopelessly slow: the halves split again and again. What makes it work is bounding. Keep the best route found so far, the incumbent. Every half-question’s linear program gives a lower bound for every route in that half, so if the bound can’t beat the incumbent, the whole half can be thrown away unexplored: it is pruned. The first incumbent is free: Part 3’s fast route. A route has a whole number of commands, so a bound of 10½ is as good as 11.

branch_cut.solve keeps the half-questions on a stack, which makes the search depth-first: it follows one branch down to a route or a dead end before trying the next, finds routes early, and needs little memory:

stack = [({}, None, None)]
while stack:
    bounds, parent, branch = stack.pop()
    node = stats['nodes']
    stats['nodes'] += 1
    solved = p.solve(bounds)
    x = z = None
    if solved is None:
        outcome, bound = 'infeasible', None
    else:
        value, values = solved
        bound = value
        x, z = values[:m], values[m:m + n]
        if parent is None:
            stats['root'] = value
        if math.ceil(value) >= len(best):
            outcome = 'pruned'
        else:
            j = fractional(values)
            if j is None:
                route = euler_route(p.model, [int(v) for v in values[:m]], [int(v) for v in values[m:m + n]])
                assert len(route) == value
                best, outcome = route, 'route'
            else:
                outcome = 'branched'
                low, high = bounds.get(j, (0, p.upper[j]))
                below, above = math.floor(values[j]), math.ceil(values[j])
                down_bounds, up_bounds = dict(bounds), dict(bounds)
                down_bounds[j], up_bounds[j] = (low, below), (above, high)
                down = (down_bounds, node, (j, '<=', below))
                up = (up_bounds, node, (j, '>=', above))
                # the side nearer the fractional value is searched first, so it goes on last
                near_up = values[j] - below >= Fraction(1, 2)
                stack += [down, up] if near_up else [up, down]
    if record:
        record(node, parent, branch, bound, outcome, x, z)

p.solve is Part 8’s cutting-plane loop with the node’s extra bounds: at every node, the connected rules the answer breaks are found with minimum cuts and added, and the rules found anywhere are kept for every node after. Adding rules inside the search is what turns branch and bound into branch and cut.

On the ten-field room, the tree has 7 nodes. The root’s bound is 10, below the fast route’s 11, so it splits; every half either has a bound that rounds up to 11, and is pruned, or splits again, until nothing is left. Nothing in the tree beat the fast route, and the tree is the proof that nothing could.

Gomory’s cuts

Branching splits the question; cutting shrinks it without splitting. A cut is a rule that every whole-number answer obeys and the current fractional answer breaks. Part 8’s connected rules are cuts of a special kind. Ralph Gomory showed in 1958 that the simplex method’s own final table always contains one.

Take a row of the final tableau whose basic variable $x_B$ has a fractional value $b$. It says $x_B + \sum_k a_k y_k = b$, summed over the variables $y_k$ outside the basis, which are all zero at the current corner. If every variable, slacks included, must be a whole number, then subtracting the whole parts of every coefficient leaves

where $\operatorname{frac}(t) = t - \lfloor t \rfloor$. Every whole-number answer obeys it: the left side is non-negative, and it differs from $b - x_B$ by a whole number, so it can’t lie strictly between 0 and $\operatorname{frac}(b)$. The current corner, where every $y_k$ is 0, breaks it. simplex.gomory_cuts reads one off every such row, writes it back in the original variables, and scales it to whole numbers, so that its own slack is a whole number too and the next round’s cuts stay valid.

On the ten-field room, one round of Gomory’s cuts at the root, before any branching, raises the root’s bound from 10 to 21/2. That rounds up to 11, the fast route’s length, so the tree is the root alone: proven without a single split. Across the 11 small rooms where Part 8’s program falls short, one round did the same on 10: 17 nodes in all, against 47 without. On the eleventh the bound rose to 29/2, which rounds up to 15, but the fast route there has 16 commands, so the tree still had to find a 15-command route, which took 7 nodes. A second round raises the bound further, but its cuts have huge coefficients, and exact arithmetic pays for every digit: on the ten-field room, measured in one run, two rounds took 94 s and one round 3 s.

From numbers back to a route

A whole-number answer says how many times the route walks each pair of fields, not in what order. Every field touches an even number of steps except the start and the end, and the steps are connected, so they can be walked in one go. Hierholzer’s algorithm finds the order: walk from the start along unused steps until stuck, which can only happen at the end; then back up along the walk, and wherever a field still has unused steps, walk them as a loop and splice the loop in:

stack, path = [s], []
while stack:
    u = stack[-1]
    if left[u]:
        v = next(iter(left[u]))
        for a, b in ((u, v), (v, u)):
            left[a][b] -= 1
            if not left[a][b]:
                del left[a][b]
        stack.append(v)
    else:
        path.append(stack.pop())
path.reverse()

Each step is used once, so it takes time proportional to the route’s length. Every route this part reports comes out of it and is replayed through Part 1’s simulator, which checks that it cleans every field.

HiGHS on the big rooms

Exact fractions are fine for rooms of a dozen fields; Part 8’s 20×20 room has 194 fields, 269 pairs of neighbours and hundreds of connected rules, and there HiGHS takes over. It does everything above, with every trick fifty years of integer programming have added: presolve, which shrinks the program before solving it; its own families of cuts; heuristics that look for good routes along the way; and a branch-and-bound tree run from a fast, warm-started dual simplex method.

One thing it can’t do from Python yet is what branch_cut.py does at every node: find broken connected rules with a minimum cut and add them in the middle of the search. So route_ip.py says “connected” a second way, one compact enough to write down in full. The start sends one unit of a commodity to every other field, along pairs of neighbours the route walks, at most N − 1 units over each:

Walks that don’t reach every field can’t carry that flow. It needs only two variables per pair and one rule per field and per pair. It is also weak: as a linear program, a walk of $x_e = 1/(N-1)$ carries a whole unit, so the flow rules alone barely bound anything. Part 8’s connected rules are strong but can’t all be written down. The model uses both: the flow rules to make it exact, and every connected rule Part 8’s loop found to make its bound good. On four 20×20 rooms with 30% furniture, measured in one run:

The fourth room is what random_room sometimes makes: the start walled into a pocket of five fields. On the other three, the flow rules alone bound less than a sixteenth of the answer; with Part 8’s rules the bound is within 1 to 5 commands of it, and every room is solved.

Part 3’s fast route goes in as the first incumbent. On these rooms it made HiGHS no faster: quicker on one, slower on two, since HiGHS’s own heuristics find good routes early anyway. What it does guarantee is that a search stopped by its time limit never answers worse than Part 3 did, which matters on the biggest rooms below.

The shortest routes

Part 8’s three rooms, solved:

Every command beyond the first N − 1 steps onto a field that is already clean. On the 20×20 room the fast route takes 50 such steps and the shortest 28. The routes look alike from a distance; the difference is all in where they turn back.

Across random furnished rooms:

Up to 20×20 every room is solved, and the picture is clear. Part 8’s bound is almost always within a command or two of the shortest route, and the fast route, which Part 3 could only bracket, is 3 to 4 commands too long on 12×12 rooms and 17 to 28 on 20×20 rooms.

The 40×40 rooms are where this stops. In fifteen minutes HiGHS found a route 14 commands shorter than Part 3’s on one of them and none on the other, and raised the bound only a few commands above Part 8’s: no route is shorter than 1,271 on the first and 1,198 on the second, so the best routes found may be up to 8.4% and 12.6% too long. That is the honest frontier of this approach. Solving rooms of a thousand fields exactly is what Concorde, the travelling-salesman solver, does with far stronger cuts than the connected rules, and it is a research project, not a Python module.

Testing Part 9

test_branch_cut.py produces every number above:

What Part 9 teaches

• Relax, then repair. Part 8 dropped the hard rules to get a bound; Part 9 puts them back one split or one cut at a time.
• Bounds do the pruning. Branch and bound is only as fast as its bounds are tight, so Part 8’s work is what makes Part 9 possible.
• A good first answer is worth having. Part 3’s fast route, the first incumbent, lets the search throw away most of the tree at once.
• Say it twice. A compact, weak formulation makes the model exact; a huge, strong one makes it solvable. Together they solve rooms neither could alone.
• Exact arithmetic has a price. Gomory’s cuts prove small rooms at the root, and a second round makes the fractions so long that the exact simplex method crawls. That is why solvers work in floating point, and why they check their answers.