lp-modeler

MIT license Build Status Build status

This project provides a mathematical programming modeling library for the Rust language (v1.22+).

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 are; COIN-OR CBC, Gurobi and GLPK.

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 use lpmodeler::problem::{LpObjective, Problem, LpProblem}; use lpmodeler::operations::{LpOperations}; use lpmodeler::variables::LpInteger; use lpmodeler::solvers::{SolverTrait, CbcSolver};

// 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 10a + 20b problem += 10.0 * a + 20.0 * b;

// Constraint: 500a + 1200b + 1500c <= 10000 problem += (500a + 1200b + 1500c).le(10000);

// Constraint: a <= b problem += (a).le(b);

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

// Run optimisation and process output hashmap match solver.run(&problem) { Ok((status, varvalues)) => { println!("Status {:?}", status); for (name, value) in varvalues.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 (solver_status, var_values) = 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 = var_values.get(&var.name).unwrap();

    obj_value += obj_coef * var_value;
}

// Print output
println!("Status: {:?}", solver_status);
println!("Objective Value: {}", obj_value);
for (var_name, var_value) in &var_values{
    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

Changelog

0.4.0

0.3.3

0.3.3

0.3.1

0.3.0

Contributors

Further work