Structure & Discovery / ICML Workshop 2023 (SODS)

Build a Feasible Route Before Trying to Make It Cheap

A hierarchical optimizer splits a graph-routing problem into choices at two scales so that training can get useful feedback before the full route succeeds.

Reading note · The findings, equation, and table were checked against the indexed workshop manuscript. The original PDF file could not be downloaded.

Hierarchical Decomposition Framework for Feasibility-hard Combinatorial Optimization

Hanbum Ko, Minu Kim, Han-Seul Jeong, Sunghoon Hong, Deunsol Yoon, Youngjoon Park, Woohyung Lim, Honglak Lee, Moontae Lee, et al.

Overview

Imagine several groups of locations that each need their own connected network. If the networks cannot share a junction, one early routing choice can make the rest impossible. Moontae and his colleagues study what happens when a learning system breaks that problem into smaller decisions.

Key Findings

The cheap route comes after the possible route

Imagine several groups of terminals trying to share one network. A route can be short and still be useless if it occupies a junction another group needs. The workshop paper studies optimization problems where finding any solution that respects the rules is hard. In its Steiner tree packing example, each group needs a tree connecting its own terminals. The trees can branch through additional nodes. They also have to fit together as a disjoint packing. A learning system may receive little guidance if most complete attempts fail that test.

Make the big decision smaller

The hierarchical combinatorial optimizer splits the job into two levels. A policy first sets aside some vertices yny_n for terminal group TnT_n. The low-level problem chooses a tree inside the induced subgraph G[yn]G[y_n]. In Equation 10, ΣTn\Sigma_{T_n} denotes the Steiner trees spanning those terminals and wew_e is the cost of edge ee:

L(yn)=arg min⁡x⊆E(G[yn])x∈ΣTn∑e∈xwe.L(y_n)=\operatorname*{arg\,min}_{\substack{x\subseteq E(G[y_n])\\x\in\Sigma_{T_n}}} \sum_{e\in x} w_e.

Equation 9 requires the selected vertex sets to be disjoint and minimizes the sum of the resulting tree costs. Reserving too few vertices can make the local solver fail. Reserving the wrong vertices can work for this group and leave the next group without a route. The training setup assigns a large penalty to an infeasible packing so these choices affect the learned policy.

The hierarchy still needs informative training examples. The authors report that starting reinforcement learning from scratch tends to fail under a sparse feasibility reward. They warm up training through self-imitation. The synthetic evaluation instances also use terminal sets designed to be solvable and nontrivial. That design tests the ability to recover feasible packings on cases that have a solution.

Read the gap beside the success rate

Table 1 reports the following results on the 80-node test graphs. The optimality gap measures solution cost relative to the reference. The feasibility ratio records how often a method returns a route that satisfies the constraints. Average time supplies a third part of the comparison.

Solver on 80-node graphsAverage optimality gapFeasible solution ratioAverage time
Hierarchical optimizer0.0540.932124 ms
Flat learned policy0.0870.902529 ms
One-second MILP0.0010.832975 ms
PathFinder-SP0.1500.97620 ms
MILP without the short limit0.0001.0001,648 ms

The hierarchical optimizer improves cost and time relative to the flat policy in these 80-node results. The one-second solver finds inexpensive routes when it succeeds, but succeeds less often. PathFinder-SP returns a route on more cases and runs quickly, with a higher average cost gap.

On the 100-node tests the trade-off shifts. The hierarchy reports a gap of 0.056 versus 0.062 for the flat policy and takes 246 ms versus 679 ms. The flat policy succeeds slightly more often (0.905 versus 0.892). The one-second MILP reports a gap rounded to zero but finds a feasible answer in only 3.5% of cases. Reading all three columns matters if a deployment has a deadline or cannot tolerate a missing route.

The layout still matters

The paper’s decomposition is useful when a coarse choice leaves a manageable local problem. A poor choice of decomposition can leave the hard part intact. The workshop experiments concern synthetic graphs and the chosen packing problem. Applying the same design to another kind of layout would require checking that the chosen coarse actions preserve the constraints and that the smaller problems stay tractable. See the original workshop manuscript and Table 1.

Questions & Answers

The opening answers are simulated author responses based on the paper.

Q: What does an optimality gap mean here?

A: It measures how far a feasible result’s cost is from the reference optimum. The feasible solution ratio tells you how often a solver returns a valid result at all.

Q: Does hierarchy guarantee an answer?

A: The reported learner improves over the flat learner on some settings. It still fails on some inputs. The feasibility check and fallback solver matter whenever a route is required.

Q: What changes when the solver moves from generated graphs to real layouts?

A: The benchmark generates terminal sets designed to admit solutions while still posing a meaningful problem. Real routing requests can have different congestion patterns and can even be infeasible. The one-second MILP result on 80-node instances must be read alongside its 0.832 feasibility ratio. A real test should independently validate returned routes before comparing their costs.

Future Ideas

Use the learned hierarchy to produce candidate decompositions for a time-limited exact router. Validate each candidate, then warm-start the solver with the cheapest feasible route found. Compare cold and warm starts at the same deadline on unseen layouts, counting feasible returns, cost against the long-running MILP reference, and the time spent generating the warm start.

Sources