MBVST — Minimum Branch Vertices Spanning Tree

Exact MILP formulations, an iterative heuristic and learned edge predictors for the Minimum Branch Vertices Spanning Tree problem, benchmarked on 400 graph instances.

Given an undirected graph, the MBVST problem asks for a spanning tree with as few branch vertices — vertices of degree three or more — as possible. It comes from optical network design: in a light-tree, every branch vertex needs a light splitter, and splitters are the expensive component. Fewer branch vertices means a cheaper, more robust network.

An optimal solution: the tree in blue over the unused edges, and its one branch vertex in orange. Produced by scripts/draw_solution.py.

The problem is NP-hard, so the project asks a practical question: which formulation actually scales? Five methods are implemented behind one interface and run over the same instance set under the same time budget.

---

Results at a glance

400 instances, 20 to 500 vertices and 27 to 672 edges, each given a time budget of 120 + |V| + |E| seconds with CPLEX 22.1.

Method	Instances solved	Largest graph	Median solve time	Matched the best known tree
Single-commodity flow	400 / 400	500 vertices	2.8 s	reference
Martin	201 / 400	200 vertices	23.7 s	155 / 201 (7 strictly better)
Multi-commodity flow	250 / 400	200 vertices	67.5 s	179 / 250
Cycle basis (heuristic)	371 / 400	500 vertices	2.5 s	42 / 371
Exponential	2 / 400	20 vertices	42.7 s	2 / 2

The single-commodity flow model is the clear winner. It is the only formulation that finishes every instance, and no other method ever beats it except Martin's, on 7 instances out of 201. Its whole advantage is size: it adds one flow variable per arc, where Martin and the multi-commodity model both add O(|V|·|E|) variables and stall past 200 vertices. The cost shows up before the solver even starts — the multi-commodity model needs a median of 1.4 s, and up to 9 s, just to write its program, against 0.06 s for the flow model.

The cycle-basis heuristic buys speed with quality. On the 125 largest instances (300+ vertices) it is roughly 6× faster than the exact model — 5.3 s against 32.5 s — but it overshoots the optimum by 6.6 branch vertices on average, so it is only worth reaching for when the exact model runs out of time.

Times are logarithmic. The two heavyweight formulations climb steeply and stop; the flow model and the heuristic run the full range.

More figures: objective values, gap to the optimum, program build time. The full table is benchmark.csv.

---

Getting started

pip install -r requirements.txt

# solve the smallest instances with the single-commodity flow model
python scripts/run_benchmark.py --model cp --limit 10

# aggregate every solution file into a table, figures and statistics
python scripts/report.py

# render one solution
python scripts/draw_solution.py Spd_Inst_Rid_Final2/Spd_RF2_20_27_211.txt

CPLEX is the reference solver but is not required — when it is missing the project falls back to CBC, which ships with PuLP. Point it at your installation with the CPLEX_PATH environment variable if you have one:

export CPLEX_PATH="/opt/ibm/ILOG/CPLEX_Studio2211/cplex/bin/x86-64_linux/cplex"

The published timings were measured with CPLEX; CBC will produce valid but slower — and, for the heuristic, slightly different — results.

All entry points

Script	What it does
run_benchmark.py	Run one method over an instance set, smallest first, skipping what is already solved
report.py	Fold the solution files into a table, figures and summary statistics
draw_solution.py	Render a solution, highlighting the branch vertices
train_classifiers.py	Train and compare the edge classifiers
predict_trees.py	Build trees from predicted edge scores and score them against the optimum
train_dqn.py	Train the deep Q-learning agent (needs requirements-dqn.txt)

Every script takes --help. A sweep is resumable: an instance that already has a solution file for the chosen method is skipped, so an interrupted run can simply be restarted.

---

The five methods

All five minimise the same objective, min Σᵥ yᵥ, where yᵥ = 1 marks a branch vertex and xₑ = 1 marks an edge of the tree. The link between them is the same everywhere:

Σ_{e ∈ δ(v)} xₑ − 2  ≤  deg(v) · yᵥ

which forces yᵥ = 1 as soon as more than two edges incident to v are chosen. What the formulations disagree about is how to say "the selected edges form a tree".

Module	Idea	Size	Guarantee
exponential.py	Forbid every vertex subset from spanning a cycle	2^|V| constraints	exact
single_flow.py	Ship |V|−1 units of flow from a root, one consumed per vertex	O(|V|+|E|)	exact
multi_flow.py	One unit-flow commodity per destination vertex	O(|V|·|E|)	exact
martin.py	Record which side of each tree edge every vertex falls on	O(|V|·|E|)	exact
cycle_basis.py	Break cycles round by round, reconnecting as you go	small per round	heuristic

Each module opens with its full mathematical model in its docstring.

The heuristic, in five steps

The cycle-basis method never builds a program that knows about connectivity. Instead it loops:

1. Compute a cycle basis of the working graph.
2. Solve a small MILP: minimise branch vertices, and forbid any basis cycle from keeping all of its edges.
3. Drop the edges the solver left out — the graph usually falls apart.
4. Reconnect each component with the edges that left it, and record that at least one of them must survive next round.
5. Repeat until the working graph is a spanning tree.

It converges in 6 rounds at the median, and needed up to 217 on the hardest instance. An optional preprocessing pass front-loads step 1, repeatedly breaking cycles under a 60-second budget and handing the main loop every basis it saw — far more constraints to start from than a single basis.

---

Learning which edges belong to the tree

Can a classifier guess an optimal tree without solving anything? Each edge becomes one training sample — a few local structural features, labelled by whether the exact model put it in the tree — and a greedy Kruskal pass over the predicted probabilities turns the scores back into a spanning tree.

Measured on 119 instances, 10,756 edges, 80/20 split:

Model	Accuracy	Weighted F1	F1 on tree edges
Logistic regression	0.743	0.74	0.63
Random forest	0.749	0.74	0.61

Both models lean almost entirely on the endpoint degrees — the random forest gives them 95 % of its importance. That is a real signal but a shallow one: degree alone cannot tell which of two equally attractive edges would close a cycle, which is exactly what makes the problem hard. The predicted trees are usable as a warm start, not as a replacement for the solver.

dqn.py holds a more exploratory attempt: a graph convolutional network trained with deep Q-learning that adds edges one at a time, rewarded for keeping degrees low. It is kept for reference and is not part of the benchmark.

---

Repository layout

├── config/cplex_solver.json      Serialised PuLP solver configuration
├── data/instances/               Graph instances, grouped by instance set
├── results/
│   ├── benchmarks/               Benchmark table and figures
│   └── solutions/                One solution file per (instance, method)
├── scripts/                      Command-line entry points
└── src/mbvst/
    ├── config.py                 Every path and the solver location
    ├── graph_io.py               Reading instances, reading/writing solutions
    ├── solver.py                 CPLEX/CBC setup and time limits
    ├── reporting.py              Benchmark table, figures, statistics
    ├── drawing.py                Solution rendering
    ├── models/                   The five solution methods
    └── learning/                 Edge classifiers and the DQN agent

File formats

Instances are plain text — a |V| |E| 0 header, then one u v 0 line per edge. Vertices are numbered from 1; the third column is unused.

20 27 0
1 9 0
1 13 0

Solutions carry a four-line header (status, build time, solve time, objective) followed by one line per decision variable. The header keys and the Arete/Sommet variable prefixes are French because they are part of the archived result files; keeping them means experiments run before this reorganisation are still readable by the current code.

Statut: Optimal
Ecriture du programme lineaire realisee en : 0h 0m 0s 6ms (0.006s).
Resolution du programme lineaire realisee en : 0h 0m 0s 71ms (0.071s).
Valeur de la fonction objectif: 1.0
Arete_(1,_2) = 1.0
Sommet_1 = 0.0

The 400-instance run is archived as zip files under results/solutions/; extract them in place to re-run the reporting or the classifiers against the full set. Only two sample instances are committed under data/instances/ — the complete Spd_Inst_Rid_Final2 family is an external benchmark set.

---

Known limitations

These are real issues in the experimental pipeline, left in place so the published numbers stay reproducible. They are the first things to fix before building on this work.

• "Optimal" does not always mean proven optimal. PuLP reports Optimal when CPLEX stops at the time limit with a feasible incumbent. This is why two exact formulations can disagree: the nonzero gaps in the table are time-limited runs, not modelling errors.
• 40 % of the positive training labels are missed. The flow model works on the bidirected graph, so its solution file names each tree edge in one direction only. The label lookup in features.py uses a single orientation and therefore misses the edges stored the other way round — 3,983 positive labels found where 6,682 exist. Checking both orientations would change every classifier score reported above.
• One feature is constant. shortest path length between u and v is always 1 for adjacent vertices; the random forest gives it exactly 0.0 importance. It is kept because it was part of the feature set behind the reported numbers.
• Two quirks in the heuristic are load-bearing. The orientation-sensitive membership test in _add_forced_edges and the lazily-consumed component iterator in _reconnect_components both look like bugs and both change which trees come out. They are documented in place in cycle_basis.py; normalising either one invalidates the archived results.
• The heuristic is solver-sensitive. Each round has many optimal solutions, so CPLEX and CBC break ties differently and return different trees.
• build_time_cycle is not a time. For the cycle-basis method that column holds the iteration count; its solve time covers the whole loop.

---

Tools

Python 3.10+, PuLP with CPLEX or CBC, NetworkX, scikit-learn, pandas, matplotlib. The optional DQN experiment adds PyTorch and PyTorch Geometric.