lp-modeler

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;

[macro_use] extern crate maplit;

use std::collections::HashMap;

use lpmodeler::variables::*; use lpmodeler::variables::LpExpression::*; use lpmodeler::operations::LpOperations; use lpmodeler::problem::{LpObjective, LpProblem, LpFileFormat}; use lp_modeler::solvers::{SolverTrait, CbcSolver};

// Problem Data let men = vec!["A", "B", "C"]; let women = vec!["D", "E", "F"]; let compat_scores = hashmap!{ ("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, };

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

// Define Variables let mut vars = HashMap::new(); for m in &men{ for w in &women{ vars.insert((m, w), LpBinary::new(&format!("{}_{}", m, w))); } }

// Define Objective Function let mut objvec: Vec = Vec::new(); for (&(&m, &w), var) in &vars{ let objcoef = compatscores.get(&(m, w)).unwrap(); objvec.push(*objcoef * var); } problem += lpsum(&obj_vec);

// Define Constraints // Constraint 1: Each man must be assigned to exactly one woman for m in &men{ let mut constr_vec = Vec::new();

for w in &women{
    constr_vec.push(1.0 * vars.get(&(m, w)).unwrap());
}

problem += lp_sum(&constr_vec).equal(1);

}

// Constraint 2: Each woman must be assigned to exactly one man for w in &women{ let mut constr_vec = Vec::new();

for m in &men{
    constr_vec.push(1.0 * vars.get(&(m, w)).unwrap());
}

problem += lp_sum(&constr_vec).equal(1);

}

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

// Terminate if error, or assign status & variable values assert!(result.isok(), result.unwraperr()); let (solverstatus, varvalues) = result.unwrap();

// Compute final objective function value let mut objvalue = 0f32; for (&(&m, &w), var) in &vars{ let objcoef = compatscores.get(&(m, w)).unwrap(); let varvalue = var_values.get(&var.name).unwrap();

obj_value += obj_coef * var_value;

}

// Print output println!("Status: {:?}", solverstatus); println!("Objective Value: {}", objvalue); // println!("{:?}", varvalues); for (varname, varvalue) in &varvalues{ let intvarvalue = *varvalue as u32; if intvarvalue == 1{ println!("{} = {}", varname, intvarvalue); } } ```

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.3.3

• Fix and improve error message for GLPK solution parsing
• Format code with rust fmt

0.3.3

• Add new examples in documentation
• Improve 0.0 comparison

0.3.1

• Add distributive property (ex: 3 * (a + b + 2) = 3*a + 3*b + 6)
• Add trivial rules (ex: 3 * a * 0 = 0 or 3 + 0 = 3)
• Add commutative property to simplify some computations
• Support for GLPK

0.3.0

• Functional lib with simple algebra properties

Contributors

• Joel Cavat (jcavat)
• Thomas Vincent (tvincent2)
• Antony Phillips (aphi)
• Florian B. (Lesstat)
• Amila Welihinda (amilajack)

Further work

• Config for lp_solve and CPLEX
• 'complex' algebra operations such as commutative and distributivity
• It would be great to use some constraint for binary variables such as
  • a && b which is the constraint a + b = 2
  • a || b which is the constraint a + b >= 1
  • a <=> b which is the constraint a = b
  • a => b which is the constraint a <= b
  • All these cases are easy with two constraints but more complex with expressions
  • ...