lp-modeler

MIT license Build Status Gitter Github Actions This project provides a mathematical programming modeling library for Rust.

An optimization problem (e.g. an integer or linear programme) can be formulated using familiar Rust syntax (see examples), and written into a universal LP model format. This can then be processed by a mixed integer programming solver. Presently supported solvers that require a separate installation (see below the examples section) to be present at runtime of your lp_modeler-based project are: * COIN-OR cbc * Gurobi * GLPK

Presently supported solvers that you can import as Rust crates (as optional features) are: * minilp * coin_cbc (requires the Cbc library files to be present at compile time of your lp_modeler-based project, see the coin_cbc project README for how to do this)

This project is inspired by COIN-OR PuLP which provides such a library for Python.

Usage

These examples present a formulation (in LP model format), and demonstrate the Rust code required to generate this formulation. Code can be found in tests/problems.rs.

Example 1 - Simple model

Formulation

``` \ One Problem

Maximize 10 a + 20 b

Subject To c1: 500 a + 1200 b + 1500 c <= 10000 c2: a - b <= 0

Generals a c b

End ```

Rust code

```rust extern crate lp_modeler;

use lpmodeler::solvers::{CbcSolver, SolverTrait}; use lpmodeler::dsl::*; use lp_modeler::constraint;

fn main() { // Define problem variables let ref a = LpInteger::new("a"); let ref b = LpInteger::new("b"); let ref c = LpInteger::new("c");

// Define problem and objective sense
let mut problem = LpProblem::new("One Problem", LpObjective::Maximize);

// Objective Function: Maximize 10*a + 20*b
problem += 10.0 * a + 20.0 * b;

// Constraint: 500*a + 1200*b + 1500*c <= 10000
problem += constraint!(500*a + 1200*b + 1500*c <= 10000);

// Constraint: a <= b
problem += constraint!(a <= b);

// Specify solver
let solver = CbcSolver::new();

// Run optimisation and process output hashmap
match solver.run(&problem) {
    Ok(solution) => {
        println!("Status {:?}", solution.status);
        for (name, value) in solution.results.iter() {
            println!("value of {} = {}", name, value);
        }
    },
    Err(msg) => println!("{}", msg),
}

} ```

To generate the LP file which is shown above: rust problem.write_lp("problem.lp")

Example 2 - An Assignment model

Formulation

This more complex formulation programmatically generates the expressions for the objective and constraints.

We wish to maximise the quality of the pairing between a group of men and women, based on their mutual compatibility score. Each man must be assigned to exactly one woman, and vice versa.

Compatibility Score Matrix

| | Abe | Ben | Cam | | --- | --- | --- | --- | | Deb | 50 | 60 | 60 | | Eve | 75 | 95 | 70 | | Fay | 75 | 80 | 80 |

This problem is formulated as an Assignment Problem.

Rust code

```rust extern crate lp_modeler;

use std::collections::HashMap;

use lpmodeler::dsl::*; use lpmodeler::solvers::{SolverTrait, CbcSolver};

fn main() { // Problem Data let men = vec!["A", "B", "C"]; let women = vec!["D", "E", "F"]; let compatibilityscore: HashMap<(&str, &str),f32> = vec![ (("A", "D"), 50.0), (("A", "E"), 75.0), (("A", "F"), 75.0), (("B", "D"), 60.0), (("B", "E"), 95.0), (("B", "F"), 80.0), (("C", "D"), 60.0), (("C", "E"), 70.0), (("C", "F"), 80.0), ].intoiter().collect();

// Define Problem
let mut problem = LpProblem::new("Matchmaking", LpObjective::Maximize);

// Define Variables
let vars: HashMap<(&str,&str), LpBinary> =
    men.iter()
        .flat_map(|&m| women.iter()
        .map(move |&w| {
            let key = (m,w);
            let value = LpBinary::new(&format!("{}_{}", m,w));
            (key, value)
        }))
        .collect();

// Define Objective Function
let obj_vec: Vec<LpExpression> = {
   vars.iter().map( |(&(m,w), bin)| {
       let &coef = compatibility_score.get(&(m, w)).unwrap();
       coef * bin
   } )
}.collect();
problem += obj_vec.sum();

// Define Constraints
// - constraint 1: Each man must be assigned to exactly one woman
for &m in &men{
    problem += sum(&women, |&w| vars.get(&(m,w)).unwrap() ).equal(1);
}

// - constraint 2: Each woman must be assigned to exactly one man
for &w in &women{
    problem += sum(&men, |&m| vars.get(&(m,w)).unwrap() ).equal(1);
}

// Run Solver
let solver = CbcSolver::new();
let result = solver.run(&problem);

// Compute final objective function value
// (terminate if error, or assign status & variable values)
assert!(result.is_ok(), result.unwrap_err());
let (status, results) = result.unwrap();
let mut obj_value = 0f32;
for (&(m, w), var) in &vars{
    let obj_coef = compatibility_score.get(&(m, w)).unwrap();
    let var_value = results.get(&var.name).unwrap();

    obj_value += obj_coef * var_value;
}

// Print output
println!("Status: {:?}", status);
println!("Objective Value: {}", obj_value);
for (var_name, var_value) in &results{
    let int_var_value = *var_value as u32;
    if int_var_value == 1{
        println!("{} = {}", var_name, int_var_value);
    }
}

} ```

This code computes the objective function value and processes the output to print the chosen pairing of men and women: Status: Optimal Objective Value: 230 B_E = 1 C_D = 1 A_F = 1

installing external solvers

installing conda (package manager)

If you want the latest release version of Cbc, Gurobi or GLPK, the easiest cross-platform installation pathway should be via conda. Importantly, this does not require admin rights on the system you want to install it on. All you need to do is install conda. Once this is done, use the respective conda command for the solver you want to use (see below).

COIN-OR Cbc

latest release (via conda)

To get the latest Cbc release for your system with conda (installation see above), use this command: conda create -n coin-or-cbc -c conda-forge coin-or-cbc Then activating the newly created environment will make the cbc executable available: conda activate coin-or-cbc

latest release (via coinbrew)

To get the latest Cbc release, including the . We recommend using COIN-OR's coinbrew, as described here: https://coin-or.github.io/user_introduction#building-from-source

latest commit (via coinbrew)

To get the very latest Cbc version, including unreleased bug fixes, you will need to build it from source. We recommend using COIN-OR's coinbrew, as described here: https://coin-or.github.io/user_introduction#building-from-source

GLPK

recent release (via conda)

To get a recent release of GLPK for your system with conda, use this command: conda create -n glpk -c conda-forge glpk Then activating the newly created environment will make the glpsol executable available: conda activate glpk

Gurobi

latest release (via conda)

To use Gurobi, you need to have a valid license key and have it in a location that Gurobi can find it. Once you have a valid license, you can get the latest Gurobi release for your system with conda, use this command: conda create -n gurobi -c gurobi gurobi Then activating the newly created environment will make the gurobi_cl executable available: conda activate gurobi

Changelog

0.5.0

0.4.3

0.4.2

0.4.1

0.4.0

0.3.3

0.3.3

0.3.1

0.3.0

Contributors

Main contributor

All contributions :heart:

Further work