#linear-programming #optimization #linear-solver #constrained

ripped

A pure-Rust Interior-Point solver for linear programs

1 unstable release

0.1.0 Oct 29, 2023

#1765 in Algorithms

GPL-3.0-or-later

54KB
1K SLoC

A pure-Rust Interior Point solver for linear programs with equality and inequality constraints.

The algorithm is heavily based on the MOSEK solver (open-access link) , and the implementation thereof in SciPy.

Linear programs

A linear program is a mathematical optimization problem defined as (using ' as the dot product):

   min_x c ' x
   st A_eq ' x == b_eq
      A_ub ' x <= b_ub
             x >= 0

Example

use ripped::prelude::*;
use approx::assert_abs_diff_eq;
use ndarray::array;

let A_ub = array![[-3f64, 1.], [1., 2.]];
let b_ub = array![6., 4.];
let A_eq = array![[1., 1.]];
let b_eq = array![1.];
let c = array![-1., 4.];

let res = Problem::target(&c)
    .ub(&A_ub, &b_ub)
    .eq(&A_eq, &b_eq)
    .build()
    .unwrap();

let solver = InteriorPoint::default();

let solution = solver.solve(&problem);

assert_abs_diff_eq!(solution.x, array![1., 0.], epsilon = 1e-6);

Dependencies

~2–19MB
~243K SLoC