RELP: Rust Exact Linear Programming

A framework to describe and solve linear programs exactly, written in Rust. Linear programming is a modelling technique to solve the wide range of optimization problems that can be represented by linear constraints and a linear target function.

This repository houses the library. Do you just want to solve a linear program stored in a file from the command line? See relp-bin.

Usage

Add this to your Cargo.toml:

[dependencies]
relp = "0.2.4"

You'll probably want to use the number types provided by the relp-num crate, so include that dependency as well:

relp-num = "0.1.11"

You can now use both crates, for example to read a linear program in the classic MPS format in arbitrary precision:

fn main() {
    let path = std::path::Path::new("my_program.mps");
    let my_program = relp::io::import::<relp_num::RationalBig>(path);
}

Features

Describing LPs

Linear programs are described through a constraint matrix, right-hand side vector and cost function. You can provide these explicitly, but Relp also offers the MatrixProvider trait which can be implemented to represent your problem. You can find an example implementation of this trait for the shortest path and max flow problems in the examples/ directory. You can capture the specific properties of your problem by implementing additional traits, such as the PartialInitialBasis trait in case you know a partial initial basis for your problem.

Solving LPs

Relp provides standard solve procedures for implementors of the aforementioned MatrixProvider trait through the SolveRelaxation trait: simply call problem.solve_relaxation() with that trait in scope. When additional traits are implemented, will the problem-specific properties they represent be exploited by faster solve procedures, seemlessly hidden behind that same call.

For more advanced use cases, it is also possible to replace some of the solve default algorithms. You can, for example, implement your own pivot rule or basis factorization.

Roadmap

• Two-phase simplex algorithm
• Lazy column generation
• LU decomposition
• Steepest descent pricing
• Presolving framework
• Prescaling framework
• Integer variables through Gomory cuts
• Floating point support
• Branch and bound