Max-cut on the G-set, open instances

# Max-cut on the G-set, open instances ## Goal Maximum cut: split the vertices of a weighted graph into two sides so that the total weight of the edges crossing the split is as large as possible. The graphs are ten instances of the G-set, the benchmark Helmberg and Rendl generated with Rinaldi's `rudy` in 2000 (the copies on Yinyu Ye's Gset page). Three flavours: uniform random (G1, G22, G43, G55, G60, G70), "almost planar" (G14, G35) and almost planar with weights in {-1, +1} (G18, G39). Every best-known cut below has stood for years of tabu search, breakout local search, global equilibrium search, Ising machines and annealers; none of them is proven optimal. `cut.py` exposes cut(name: str, n: int, edges: list[tuple[int, int, int]], time_budget: float, seed: int) -> list[int] `edges` is a list of `(u, v, w)` with `0 <= u, v < n` and integer weights (`w = 1` on the unweighted graphs, `w` in `{-1, 1}` on G18 and G39); `name` is the instance label. Return a list of `n` side labels, each `0` or `1`. The eval recomputes the cut weight `sum(w for (u, v, w) in edges if side[u] != side[v])` from those labels, so nothing the solver reports is trusted. Instance files live in `instances/<name>.txt` (line 1 `n m`, then one edge per line, `u v` or `u v w`); they are not mutable. ## Metric metric = mean over the 10 instances of cut(name) / best_known(name) A ratio of 1.0 matches the best-known cut; above 1.0 beats it, and the eval lists those instances in `records_beaten`. A wrong-length list or a label other than 0/1 on any instance is a failed run, as is exceeding the time budget. Environment knobs the eval honours: - `ZT_EVAL_SEED`: only seeds the `seed` handed to your solver. The instance set is fixed. - `ZT_EVAL_PER_INSTANCE_SECONDS`: the `time_budget` per instance (default 8; the full run takes about 75 s). - `ZT_EVAL_INSTANCES`: comma-separated subset of the names below, for quick local runs (`ZT_EVAL_INSTANCES=G14,G43 python eval.py`). ## Records Best-known cut values from Ma and Hao 2017 (Annals of Operations Research 248, "A multiple search operator heuristic for the max-k-cut problem", Table 5), whose "previous best known" column consolidates Benlic and Hao 2013 (breakout local search) and Shylo, Glover and Sergienko 2015 (global equilibrium search), and whose MOH raised G60 to 14190. Cross-checked against the best-known columns of two 2026 Ising-machine papers (arXiv:2606.03917, arXiv:2606.30333). No non-toroidal G-set instance has a matching upper bound: the SDP bound on G1 is about 12080 against a cut of 11624, and the only G-set graphs that have been closed are toroidal grids (G11, G48, G49, G57, G62, G65, G72, G77, G81, whose best cuts match a planar-relaxation upper bound: Glass and Feder 2026, arXiv:2606.28478). Those are left out, as are the other toroidal ones (G12, G13, G32-G34, G50, G66, G67) whose gap to that bound is a handful of units. | instance | n | m | weights | best-known cut | found by | optimal? | |---|---|---|---|---|---|---| | G1 | 800 | 19176 | 1 | 11624 | many (BLS, GES, MOH, ...) | no | | G14 | 800 | 4694 | 1 | 3064 | BLS 2013, GES, MOH | no | | G18 | 800 | 4694 | -1/+1 | 992 | BLS 2013, GES, MOH | no | | G22 | 2000 | 19990 | 1 | 13359 | BLS 2013, GES, MOH | no | | G35 | 2000 | 11778 | 1 | 7687 | MOH 2017 (GES 7686) | no | | G39 | 2000 | 11778 | -1/+1 | 2408 | BLS 2013, GES, MOH | no | | G43 | 1000 | 9990 | 1 | 6660 | BLS 2013, GES, MOH | no | | G55 | 5000 | 12498 | 1 | 10299 | previous best in Ma and Hao's table; MACUT, MAMBP, MOH reach it | no | | G60 | 7000 | 17148 | 1 | 14190 | MOH 2017 (previous best 14188) | no | | G70 | 10000 | 9999 | 1 | 9591 | previous best in Ma and Hao's table (MOH 9544, BLS 9541) | no | The benchmark is still moving: G63 went from 27045 to 27047 in 2025 (Khan and Shukla, arXiv:2510.21105) and the toroidal G72/G77/G81 were raised the same year, so 1.0 is a realistic target on the 800- and 1000-vertex graphs and anything above it is a record candidate. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. - `edges` is a copy; the eval scores against its own. ## Ideas that are known to matter (check the journal before repeating one) - One-flip moves with incremental gains: keep `gain[v]`, the change in cut weight if `v` switches side, update the neighbours' gains in `O(deg v)` after each flip. The baseline does this; every method below is built on it. - Breakout local search (Benlic and Hao 2013): steepest-descent one-flip search to a local optimum, then an adaptive perturbation whose strength grows while the search keeps returning to the same optimum, mixing tabu-directed flips (flip the best non-tabu vertex even if it hurts) with random flips. This set most of the records on the 800- and 2000-vertex graphs. - Tabu search on the one-flip neighbourhood with tenure around `n/100 ... n/10` and aspiration (Kochenberger et al. 2013; Wu, Wang, Lü 2015 add a randomised tenure and a long-term frequency-based restart). Bucket the vertices by gain so the best move is `O(1)` to find. - Global equilibrium search (Shylo, Glover, Sergienko): a simulated-annealing-like probability model over the best solutions seen, which produced the large-instance records (G55-G81). - Multiple search operators (Ma and Hao 2017): alternate a one-flip tabu phase, a two-flip "neighbourhood-mixing" phase and a perturbation phase; it holds G35 and G60. - The almost-planar graphs (G14, G18, G35, G39) have many small-degree vertices: local search gets stuck in shallow optima, and stronger perturbation or a population helps more there than on the random graphs. The weighted ones have a large fraction of negative edges: the sign structure, not the degree, decides which flips pay. - Pure Python is slow; bind neighbour lists to locals, use plain lists rather than dicts in the inner loop, and spend the budget on iterations before tuning the metaheuristic. Write one honest line in `NOTES.md`: the idea, and which instances it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.