ripsolve

There is a command-line application, a Rust library, and a Python module shaped like gurobipy. Nothing links against another solver.

Install

cargo install ripsolve-cli

cargo add ripsolve

pip install ripsolve

One wheel per platform serves every CPython from 3.9 on. Where none fits, pip builds from the source distribution, which needs a Rust toolchain.

Command line

ripsolve solve model.lp                 # solve to proven optimality
ripsolve solve model.mps --time-limit 60 --gap 0.01
ripsolve info  model.lp                 # dimensions and column types
ripsolve relax model.lp                 # LP relaxation bound only
ripsolve gen --kind knapsack --cols 60 --rows 30 --seed 42 -o hard.lp

Output names the objective, the status, and what the search cost:

objective: 225
status:    optimal
presolve:  0 columns fixed, 0 rows removed, 0 coefficients tightened
heuristic: 1 incumbents
2116 nodes, 9284 simplex iterations, 1.21s

Useful flags for solve:

A run that hits its time limit reports the best solution found and the remaining gap rather than failing.

Python

The interface is shaped like gurobipy, so a script that stays inside the supported feature set runs unchanged after swapping the import.

import ripsolve as gp
from ripsolve import GRB

value  = [12, 9, 7, 5, 3]
weight = [ 6, 5, 4, 3, 2]

m = gp.Model("knapsack")
x = m.addVars(len(value), vtype=GRB.BINARY, name="x")
m.setObjective(gp.quicksum(value[j] * x[j] for j in range(len(value))), GRB.MAXIMIZE)
m.addConstr(gp.quicksum(weight[j] * x[j] for j in range(len(value))) <= 10)
m.optimize()

print(m.ObjVal)                              # 19.0
print([j for j in range(len(value)) if x[j].X > 0.5])

Mixed-integer models use the same vtype values as gurobipy:

m = gp.Model()
b = m.addVar(vtype=GRB.BINARY, name="b")
n = m.addVar(vtype=GRB.INTEGER, lb=0, ub=10, name="n")
c = m.addVar(vtype=GRB.CONTINUOUS, lb=0.0, name="c")

m.addConstr(2 * b + n + 0.5 * c <= 12)
m.setObjective(3 * b + 2 * n + c, GRB.MAXIMIZE)
m.setParam("TimeLimit", 30)
m.setParam("MIPGap", 0.01)
m.optimize()

if m.Status == GRB.OPTIMAL:
    print(m.ObjVal, m.NodeCount, m.Runtime)

Reading a model from a file:

m = gp.read("model.mps")
m.optimize()

Callbacks

Lazy constraints and cuts are added from a callback, as in gurobipy. It is called at GRB.Callback.MIPNODE for the root's and every node's relaxation, and at GRB.Callback.MIPSOL for every point before it may become the incumbent. A model whose rows are too many to write down can leave them to the callback:

m.setParam("LazyConstraints", 1)
m._y = y                                     # for the callback to read

def callback(model, where):
    if where == GRB.Callback.MIPSOL:
        value = model.cbGetSolution(model._y)
        for a, b, c in broken_triangles(value):
            model.cbLazy(model._y[a, b] + model._y[b, c] - model._y[a, c] <= 1)

m.optimize(callback)

cbGetNodeRel reads a node's relaxation and cbCut adds a cut there. A Var, a list or a dict of them comes back as a value, a list or a dict. An exception raised in the callback is raised again from optimize().

Supported surface

Two deliberate differences from gurobipy's behaviour. vtype defaults to continuous, as gurobipy's does, even though binary would suit this solver's history: a ported script calling addVar() should not silently get a different model. Unknown parameter names raise KeyError rather than being ignored, so a misspelling fails loudly.

optimize() releases the GIL, so a solve does not block other Python threads.

See python/README.md for the full list.

Rust library

use ripsolve::{Problem, search};
use std::path::Path;

let problem = Problem::from_file(Path::new("model.lp"))?;
problem.validate()?;

let solution = search::solve(&problem, search::Options::default());
println!("{:?} {:?}", solution.status, solution.objective);

Builder assembles a model a column and a row at a time. Objective coefficients are written in the sense you ask for. Maximizing 3b + 2n subject to 2b + n <= 12:

use ripsolve::model::{Builder, RowSense, Sense};
use ripsolve::search;

let mut model = Builder::new(Sense::Maximize).named("example");
let b = model.binary("b");
let n = model.integer("n", 0.0, 10.0);
model.objective(&[(b, 3.0), (n, 2.0)]);
model.row(&[(b, 2.0), (n, 1.0)], RowSense::Le, 12.0);

let problem = model.build();
problem.validate()?;

let solution = search::solve(&problem, search::Options::default());
assert_eq!(solution.objective, Some(23.0));

continuous adds a column with no integrality requirement, and range adds a row bounded on both sides. A binary column is an integer column bounded to [0, 1]; nothing treats that as a distinct case, because branching splits a range and degenerates to fixing at 0 or 1.

Problem is also a plain struct with public fields, so it can be filled in directly when translating a model from somewhere else.

search::Options carries the tuning knobs, including threads, time_limit, gap_tolerance, local_cut_frequency and cut_rounds. The library defaults to one thread so its behaviour is predictable; the CLI defaults to the machine's parallelism.

search::solve_with takes a Separator as well: a function the search asks for rows at the root, at every node, and of every point before it may become the incumbent. The rows a point breaks are added everywhere, so it serves as a cut callback and as lazy constraints at once:

use ripsolve::search::{self, Point};

// Every triangle row a point breaks, from a model that holds none of them.
let separator = |x: &[f64], _: Point| violated_triangles(x);
let solution = search::solve_with(&problem, search::Options::default(), None, &separator);

Full API documentation is on docs.rs.

Building and testing

cargo build --release
cargo test

Builds on stable Rust. The test suite is self-contained and needs no external solver.

Correctness is additionally checked against other solvers used strictly as oracles. bench/refresh_fixtures.py records reference relaxation and optimal values into crates/ripsolve/tests/fixtures/reference.json, and the tests read only that file. Each entry carries a digest of its instance, so changing the generator fails the suite as a stale fixture rather than silently pairing new instances with old values. bench/mip_fuzz.py compares randomized mixed-integer models against a reference solver.

Layout