Crate microlp 

A linear programming solver: it finds the minimum (or maximum) of a linear function of a set of variables subject to linear equality and inequality constraints. Variables can be real, integer, or boolean.

Getting started

You can use microlp directly, but the rooc modeling language and good_lp provide higher-level ways to write models.

Features

• Pure Rust. Runs on WebAssembly.
• Real, integer, and boolean variables.
• Time limits and MIP gap, with the possibility to edit and resume a solve.
• Warm starts from a known solution.
• Handles problems with hundreds of thousands of variables and constraints.

Integer and boolean variables are handled with branch & bound. The solver may still cycle or lose precision on some hard problems.

Example

use microlp::{ComparisonOp, OptimizationDirection, Problem};

// Maximize x + 2y, where x is real with x >= 0 and y is an integer
// with 0 <= y <= 3.
let mut problem = Problem::new(OptimizationDirection::Maximize);
let x = problem.add_var(1.0, (0.0, f64::INFINITY));
let y = problem.add_integer_var(2.0, (0, 3));

// Subject to x + y <= 4 and 2x + y >= 2.
problem.add_constraint(&[(x, 1.0), (y, 1.0)], ComparisonOp::Le, 4.0);
problem.add_constraint(&[(x, 2.0), (y, 1.0)], ComparisonOp::Ge, 2.0);

// The optimum is 7, at x = 1, y = 3.
let solution = problem.solve().unwrap().into_solution().unwrap();
assert_eq!(solution.objective(), 7.0);
assert_eq!(solution.var_value(x), 1.0);
assert_eq!(solution.var_value(y), 3.0);

Solving and reading the solution

Problem::solve tries to find the optimal solution. Contradictory constraints produce Error::Infeasible, while an objective that can improve forever produces Error::Unbounded. Invalid explicit numeric options produce Error::InvalidOptions, and unrecoverable numerical failures produce Error::InternalError.

When a solve call returns successfully:

• SolveOutcome::Solution contains a validated assignment. Its status is SolutionStatus::Optimal when exact optimality was proved, or SolutionStatus::Feasible when a valid assignment is available without an exact proof, for example after reaching a time limit, node limit, or MIP gap.
• SolveOutcome::Interrupted means a time or node limit fired before a usable assignment was found. It exposes the TerminationReason and Stats, but no objective or variable values because no validated assignment is available. This does not mean the problem is impossible to solve. Use SolveOutcome::resume to continue the search.

SolveOutcome::termination_reason distinguishes TerminationReason::ProvenOptimal, TerminationReason::MipGap, TerminationReason::TimeLimit, and TerminationReason::NodeLimit.

Time limits, resuming, and editing

Problem::set_time_limit sets a time budget. SolveOutcome::resume uses the per-call options from the immediately preceding solve or resume call. SolveOutcome::resume_with instead uses only the supplied ResumeOptions: every field replaces the previous setting, and values are not merged.

A Solution can be edited and re-solved. Solution::add_constraint adds a constraint, Solution::fix_var pins a variable to a value, and Solution::unfix_var releases a previous fix. Each edit consumes the solution and returns a new SolveOutcome for the edited problem.

Structs

InterruptedSolve

An outcome returned when a limit is reached before a usable solution exists.

LinearExpr

A weighted sum of variables used on the left-hand side of a constraint.

Problem

A linear optimization model that can be populated and solved.

ResumeOptions

Overrides for the solver settings used for a subsequent search/resume call.

Solution

A validated feasible assignment returned by a solve-like call.

SolutionIter

Iterates over a Solution’s variables in creation order.

SolveOptions

Options controlling a solve. Construct with SolveOptions::default and mutate the fields you need.

Stats

Statistics of a solve, available via crate::Solution::stats.

Tolerances

Numeric tolerances for a solve (see SolveOptions::tolerances).

Variable

Identifies a variable created by a Problem.

Enums

ComparisonOp

Specifies how a constraint’s left-hand expression is compared with its right-hand value.

Error

An error returned while validating, solving, or editing a problem.

OptimizationDirection

Selects whether a problem’s objective is minimized or maximized.

SolutionStatus

Whether a usable solution is proven optimal.

SolveOutcome

The result of a successful solve.

TerminationReason

Why a solve or resume call returned.

VarDomain

The values a variable is allowed to take.