A good answer sooner

In my experience MIP (mixed-integer programming) solvers have mostly been used as something that cooks on a server for a few hours, and then someone looks at the answer. A good answer sooner changes that: a plan you watch improve while the solver runs, or a solve quick enough to sit inside a loop. That’s why I got interested in primal heuristics. A primal heuristic tries to find a good solution fast. It proves nothing; that’s left to branch-and-bound, the search that runs after it.

The field is looking the same way. The MIP 2022 computational competition asked for primal heuristics and encouraged ones that don’t solve the LP relaxation, the problem with the integer requirements dropped, I’d guess for speed and scale. Feasibility Jump won it, and an early version of FPR (fix, propagate and repair) came second. In March, Bussieck and Dirkse introduced mipfeas, a benchmark that scores how soon a solver finds good solutions, not whether it proves them optimal. On its table, as of 30 October, cuOpt leads on a GPU, ahead of ReXi and a concurrent SCIP, all open source. The benchmark runs on an NVIDIA DGX Spark.

In September I put out a preprint and the code for four published primal heuristics built into HiGHS, the open source MIP solver: Feasibility Jump, FPR, LocalMIP and Scylla. Feasibility Jump and LocalMIP are local searches that move one variable at a time, FPR fixes variables and repairs, and Scylla rounds approximate LP solutions. Each comes from its own paper and was benchmarked on its own setup. I wanted to see how they behave inside branch-and-bound, and HiGHS was among the fastest open source MIP solvers when I started. So now they run in one solver, before the first LP is solved, under the same kind of budget on the same 16 workers. That isn’t quite what the leaders on mipfeas do. cuOpt, ReXi and the concurrent SCIP all run solvers or heuristics side by side with the search and share the solutions they find. Mine run before it.

Feasibility Jump was already in HiGHS, and mine wraps that implementation with fixes for two bugs that agents found while checking the code. Both are fixed upstream now (#3310).

Sooner, not much better

The benchmark, mipfeas, is 233 feasible instances from MIPLIB 2017, ten minutes each, scored by the primal integral. That’s the area under the curve of how far the best solution so far is from the best known one, with the worst value charged until a first solution appears.

I compared the patched solver with an unpatched HiGHS built from the same version, on the same machine. Over all 233 instances the primal integral is 23.7% better in shifted geometric mean. On the 143 instances I never used for tuning, it’s 12.9%.

At the ten-minute limit it’s only slightly ahead. It finds a solution on four instances where plain HiGHS finds none, against one the other way, and HiGHS’s own components still hold the best solution at the end on 188 of the 214 instances it finds one for. I’d expect the earlier start to help branch-and-bound cut off parts of the search, but I haven’t measured that.

Plain HiGHS already runs Feasibility Jump once, on one thread, before the first LP, and usually has an early solution too. The patched solver runs the same Feasibility Jump with the two fixes, on 16 workers that each get their own budget, and then FPR and LocalMIP after it.

The gain is also in size, not in how often. On the 143 unseen instances the patched solver is better on 63 and worse on 61. A minority of instances with large gains make the difference.

Two of the five added nothing

The four papers give five mechanisms: the four heuristics, plus a variant of FPR that uses the LP solution in branch-and-bound’s dives. Two of them never produced an accepted solution in a full run, and both ship switched off.

One is Scylla. Run alone before the solve, with no limit on its budget, it found solutions on 129 of the 233 instances, but none that counted in a full run. It runs last in the chain, so it only counts if it beats what the other three have left.

That didn’t surprise me much. Scylla is built around PDLP, a first-order method for LPs too large for the simplex method. In my implementation it uses HiGHS’s own PDLP, which is cuPDLP-C on the CPU, and rounds with the same kernel as FPR. On problems this size I think that’s too slow, and FPR gets there first without the LP. A quick test with a GPU build gave no advantage either. Scylla probably belongs on very large problems.

The other is the LP-guided FPR. Given the dive budget to itself, with HiGHS’s own dive heuristics switched off, it found solutions on 10 of 49 instances. Next to those heuristics it found none.

More effort didn’t help

I spent a long time tuning the heuristic budgets. The configuration I started from had more than four times the total effort and Scylla switched on. Over all 233 instances the one that ships is better on 140 and worse on 67, but a few large losses offset the wins. On a held-out check the cheaper one came out ahead.

The heuristics run before the first LP, so they delay it, and branch-and-bound with it. Where branch-and-bound has a solution within the first second, that’s pure overhead, and for plain HiGHS that’s two in five mipfeas instances. That includes the quick solves in a loop from the opening. On six instances a heuristic finds a solution when it runs alone and the budgeted chain doesn’t. If you run to the time limit and only take the final answer, it buys you little.

Every number is one seed per configuration on one 16-core machine, and the budgets were tuned at 16 workers and not tested at other counts. Stronger solvers are on the mipfeas table; this compares only with the HiGHS it patches.

Next

Running before branch-and-bound is why the heuristics need a budget. ReXi, by Mexi and Rehfeldt, races several differently configured solvers on one model, sharing solutions between them, with heuristic workers improving what’s shared. Heuristics like these could be workers in a setup like that, and a concurrent HiGHS is something I’m looking into.

If you need answers sooner, the code is there to run or get inspired by.