The Tokyo Elevator

An elevator that stops at every floor is slow; one that skips floors is fast but strands the passengers it skips. The puzzle, set by Kojon Fujimura in The Tokyo Puzzles and brought into integer programming by Chlond, asks for the compromise. A building has a bank of elevators. Every elevator stops at the top floor and the bottom floor, and at a fixed number of floors in between; no elevator stops everywhere. The bank is acceptable when any two floors are joined by a single elevator, so that a passenger between them need never change cars. If each elevator may pause at only a handful of the middle floors, how few elevators make the building fully connected? Behind the lifts and floors is one of the oldest workhorses of integer programming, the set-covering problem, and the puzzle is a clean place to meet it.

The puzzle

Strip the top and bottom floors away first. Every elevator stops at both, so they are connected to everything and to each other no matter what; only the floors in between carry any choice. Write $n$ for the number of those middle floors and $r$ for the number of them each elevator is allowed to visit, and call the resulting puzzle $E\{n, r\}$. A passenger on middle floor $j$ can reach the top and bottom on any elevator that stops at $j$, so floor $j$ is served as soon as one elevator visits it. Two middle floors $j$ and $k$ are joined when some single elevator visits both. The bank works precisely when every floor is visited and every pair of floors shares an elevator.

The original eight-storey puzzle has six middle floors with four stops allowed to each elevator, the case $E\{6, 4\}$, and three elevators suffice. Fujimura’s question tightens the allowance to three stops, the case $E\{6, 3\}$; Martin Gardner later asked for $E\{8, 4\}$, eight middle floors with four stops each. We want the fewest elevators in each.

The model

Variables

An elevator is fixed entirely by the set of middle floors it visits, so a candidate elevator is just a choice of $r$ floors out of $n$. List every such choice; there are $\binom{n}{r}$ of them, and they are the only elevators worth considering, since any elevator visiting fewer than $r$ floors is dominated by one that fills its spare stops. For each candidate $e$ let $x_e = 1$ when that elevator is installed and $0$ otherwise.

The covering constraint

A pair of middle floors $j$ and $k$ is joined exactly when an installed elevator visits both, that is when $\sum_{e \ni j, k} x_e \ge 1$, the sum running over the installed elevators whose floor set contains both. Impose this for every pair. Taking $j = k$ collapses the condition to $\sum_{e \ni j} x_e \ge 1$, which forces floor $j$ to be visited at all, so the single family of constraints $$\sum_{e \,\ni\, j,\,k} x_e \;\ge\; 1 \qquad (1 \le j \le k \le n)$$ carries both requirements at once. There is no structure to exploit beyond this: a $1$ wherever an elevator covers a pair, a demand of at least one everywhere, and a count to keep down. That shape, minimize a sum of binary variables subject to “cover every requirement at least once,” is the set-covering problem, and the objective is simply $$\min \; \sum_e x_e .$$

The solver

from itertools import combinations
from ortools.sat.python import cp_model

def min_elevators(n, r):
    elevators = list(combinations(range(n), r))   # candidate cars
    m = cp_model.CpModel()
    use = [m.NewBoolVar("") for _ in elevators]
    for j in range(n):
        for k in range(j, n):                # j == k uses floor j
            serve = [use[i] for i, e in enumerate(elevators)
                     if j in e and k in e]
            m.Add(sum(serve) >= 1)
    m.Minimize(sum(use))
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return [e for i, e in enumerate(elevators) if s.Value(use[i])]

Run on $E\{6, 3\}$ the program installs six elevators, and no five can cover all fifteen pairs of middle floors; Fujimura’s tightened building needs twice the three that four stops allowed. Gardner’s larger $E\{8, 4\}$ also settles on six. The six-elevator solution to the three-stop puzzle is drawn in Figure 27.1, top and bottom floors restored: read down a column to see where one elevator stops, and every pair of rows is met by a shaded column they share.

Reading the cover

What the puzzle teaches is how to turn a connection requirement into a covering matrix. The objects to be covered are not the floors but the pairs of floors, $\binom{n}{2}$ of them once the diagonal is folded in; the things that cover them are the candidate elevators, each covering the $\binom{r}{2}$ pairs among its own stops. A bank works when its chosen columns together hit every pair, and the best bank is the fewest columns that still do. The same template, requirements as rows, resources as columns, a one where a resource meets a requirement, fits crew rostering, sensor placement, and the assembly of test suites, and each is solved by the very lines above with only the covering matrix changed. Fujimura’s elevators are a small and concrete doorway into a problem that, at scale, is one of the harder things an integer programmer is asked to do.

Sources. The puzzle and its set-covering formulation follow Martin J. Chlond, A Tokyo Elevator Puzzle, INFORMS Transactions on Education volume $6$, number $3$ ($2006$), pages $55$–$59$. The puzzle itself is from Kojon Fujimura, The Tokyo Puzzles (Frederick Muller, London, $1979$; first published in Japanese, $1969$), and the larger ten-storey variant from Martin Gardner, “Elevator Puzzles,” Scientific American volume $228$, number $2$ ($1973$), pages $106$–$109$. The optimal counts of six for both $E\{6, 3\}$ and $E\{8, 4\}$ are reproduced here by the model above and checked for minimality.