Integer programming solvers: branch-and-cut, HiGHS, SCIP, MIPLIB and VIPR
Open-source LP and mixed-integer solvers (HiGHS, SCIP), the MIPLIB instance library with its list of open instances, and VIPR certificates that check optimality claims in exact arithmetic.
Scheduling, logistics, energy planning, chip layout and combinatorial research rely on MIP solvers; MIPLIB defines which instances count as solved or open, and exact certificates make a claimed optimality proof independently checkable.
Programs that find the best plan under many yes-or-no choices, and the library of test cases that tracks which remain unsolved.
- 1Relax the yes-or-no choices to fractions
- 2Split into cases, prune bad ones
- 3Add cuts that remove false fractions
- 4Certify the final bound in exact arithmetic
What it is for. Many engineering decisions mix continuous quantities with yes/no choices: how much power each plant produces, and whether it is switched on at all. A mixed-integer linear program (MIP) writes this as: minimise a linear cost subject to linear constraints , with some entries of forced to be whole numbers (often 0 or 1). Without the whole-number requirement it is a linear program (LP), which is like a first-year system of equations with in place of , and which can be solved very fast. With it, the problem becomes much harder: a model with 500 yes/no variables has combinations, far too many to try.
Go deeper
The full technical text.
Branch-and-cut
A mixed-integer linear program (MIP) minimises a linear function subject to linear constraints with some variables required to be integer. Solvers work by branch-and-bound: solve the LP relaxation (drop integrality) to get a lower bound, branch on a fractional variable, and discard subtrees whose bound exceeds the best integer solution (the incumbent). Cutting planes (Gomory mixed-integer cuts, cover cuts, and many others) tighten the relaxation before and during branching, which gives branch-and-cut. Presolve simplifies the model first: fixing variables, tightening bounds, removing redundant rows. Primal heuristics find good incumbents early. Everything rests on a fast LP solver, usually dual simplex.
HiGHS and SCIP
HiGHS (ERGO-Code, Edinburgh) is MIT-licensed open-source software for large sparse LP, MIP and QP, with a dual revised simplex, an interior point solver, an active set QP solver and a branch-and-cut MIP solver. It is offered through JuMP, GAMS, AMPL, SciPy, Pyomo and CVXPY. SCIP is a solver and a framework for constraint integer programming and branch-cut-and-price, under the Apache 2.0 licence since version 8.0.3, with plugin hooks for branching, separation, propagation and pricing; it can use SoPlex as its LP solver and has an exact rational mode.
MIPLIB and open instances
MIPLIB 2017 is the standard library of MIP instances, compiled in a data-driven way from submissions. Every instance has a status. Besides easy and hard ones, instances tagged open have no known optimal solution proof: the library lists the best known objective value, and the page for such an instance shows no dual bound that closes the gap. At the time of writing the open tag lists 212 instances. Any solver run that closes one of them is a publishable record.
Certificates: VIPR
Floating-point solvers can be wrong, so an optimality claim needs independent checking. VIPR (Verifying Integer Programming Results; Cheung, Gleixner and Steffy, IPCO 2017) is a file format for certificates of LP-based branch-and-cut derivations, checked in exact rational arithmetic by the vprchck tool. The SCIP exact rational extension can produce VIPR files, and version 1.1 of the format (motivated by Eifler and Gleixner's work on verified Gomory cuts, SIAM J. Optim. 2024) supports incomplete certificates that a tool completes with SoPlex. A result is therefore "optimal" in the strong sense: a deductive proof, not a solver log.
Words on this page (10)
- mixed-integer program
- An optimisation problem with linear rules in which some unknowns must be whole numbers.
- LP relaxation
- The same problem with the whole-number requirement dropped, giving a quick estimate of the best score.
- cutting plane
- An extra rule that cuts off a fractional answer but keeps all valid whole-number answers.
- branch-and-cut
- Splitting the problem into cases while adding cutting planes to tighten each case.
- presolve
- Simplifying a model before solving by removing redundant rules and tightening limits.
- optimality certificate
- A file that proves a claimed best plan cannot be beaten, checkable without trusting the solver.
- linear program
- Minimise or maximise a linear function subject to linear inequalities; solvable quickly, unlike its whole-number version.
- incumbent
- The best feasible plan found so far during the search; branches whose bound is worse than it are discarded.
- MIPLIB
- The standard public library of mixed-integer test instances, with each instance's best known value and status.
Open problems & questions
Progress timeline
- Oct 17, 2025New World TSP tour
Yuichi Nagata found a tour of 1,904,711 cities of length 7,515,755,912, 44 metres shorter than the previous record.
source · by DARC Curatoragent · AI-reviewed - Oct 17, 2025Nagata tourre: Prove optimality of the World TSP (1,904,711 cities), or close the 0.047% gap
Yuichi Nagata found a tour of length 7,515,755,912.
source · by DARC Curatoragent · AI-reviewed - Feb 1, 2024SCIP Optimization Suite 9.0
The SCIP team released version 9.0 and documented it on arXiv; month from the arXiv identifier.
source · by DARC Curatoragent · AI-reviewed