Graph Clearing Problem

The Problem

A building has rooms connected by corridors. Each room requires a certain number of robots to clear, and each corridor requires robots to guard it while adjacent rooms are being cleared. The goal: find the order in which to clear the rooms that minimizes the peak number of robots needed at any single step.

More precisely, when you clear a room, the cost is the room's weight plus the sum of weights of all "protected" corridors — corridors that connect a cleared room to an uncleared one, or are incident to the room being cleared. The objective is to minimize the maximum cost across all steps: a minimax problem.

This was the competition problem for the ACP Summer School 2018, a constraint programming workshop where participants built solvers for a problem revealed at the start of the event. I was the only participant to submit solutions within the competition's time limit.

The Approach

The solver is built on an experimental graph-based solver framework. The key insight is modeling the clearing process as a decision diagram (DD): each layer represents choosing the next room to clear, and each state tracks the set of cleared rooms and the running peak cost.

A greedy heuristic provides an initial upper bound by always clearing the room with the lowest immediate cost. Then a DD-based search explores the full decision space layer by layer. At each layer, a reduce step merges equivalent states — those with the same last-cleared room and remaining domain — keeping only the one with lowest cost. A prune step discards any state whose lower bound can't beat the incumbent solution.

The bounding function uses two estimates: a static bound (the maximum individual room cost among remaining rooms) and a dynamic bound (the minimum cost achievable by the next clearing step given current corridor protection). Together, reduce and prune keep the diagram compact enough to solve in practice.

Decision Diagrams vs. MIP

Decision diagrams excel at finding feasible solutions quickly: each BFS layer guarantees complete clearing sequences after n layers, and the reduce operation exploits problem-specific structure by merging states that are provably equivalent. The custom bounding function is tailored to the minimax objective.

Mixed-integer programming (MIP) brings different strengths: LP relaxations provide continuous dual bounds, and decades of solver engineering — cutting planes, presolve reductions, branch-and-cut — make MIP effective across a wide range of problems. Adding side constraints is also straightforward in a MIP formulation.

In practice, the DD finds good solutions fast (critical for competition time limits), while MIP gets strong optimality proofs through LP bounds. This demo lets you compare both approaches side by side.

Results

The solver finds optimal solutions for graphs up to about 20 nodes in reasonable time. For the competition instances (up to 100 nodes), the greedy heuristic provides good solutions almost instantly, and the decision diagram improves on them when given enough time.