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 are; COIN-OR CBC, Gurobi and GLPK.
This project is inspired by COIN-OR PuLP which provides such a library for Python.
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.
\ 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
extern crate lp_modeler;
use lp_modeler::solvers::{CbcSolver, SolverTrait};
use lp_modeler::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:
problem.write_lp("problem.lp")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.
| Abe | Ben | Cam | |
|---|---|---|---|
| Deb | 50 | 60 | 60 |
| Eve | 75 | 95 | 70 |
| Fay | 75 | 80 | 80 |
This problem is formulated as an Assignment Problem.
extern crate lp_modeler;
use std::collections::HashMap;
use lp_modeler::dsl::*;
use lp_modeler::solvers::{SolverTrait, CbcSolver};
fn main() {
// Problem Data
let men = vec!["A", "B", "C"];
let women = vec!["D", "E", "F"];
let compatibility_score: 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),
].into_iter().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
- Add a native coin-or impl (NativeCBCSolver) to call CoinOR CBC trough the C API.
- Fix incorrect simplification of (expr-c1) c2
- Fix failed cbc parsing on infeasible solution
-
Improve modules
- Remove maplit dependency
- All the features to write expressions and constraints are put into
dslmodule use lp_modeler::dsl::*is enough to write a systemuse lp_modeler::solvers::*is always used to choose a solver
-
Add a
sum()method for vector ofLpExpression/Into<LpExpression>instead oflp_sum()function -
Add a
sum()function used in the form:problem = sum(&vars, |&v| v * 10.0) ).le(10.0);
- Fix and improve error message for GLPK solution parsing
- Format code with rust fmt
- Add new examples in documentation
- Improve 0.0 comparison
- Add distributive property (ex:
3 * (a b 2) = 3*a 3*b 6) - Add trivial rules (ex:
3 * a * 0 = 0or3 0 = 3) - Add commutative property to simplify some computations
- Support for GLPK
- Functional lib with simple algebra properties
- Joel Cavat (jcavat)
- Thomas Vincent (tvincent2)
- Antony Phillips (aphi)
- Florian B. (Lesstat)
- Amila Welihinda (amilajack)
- (zappolowski)
- Yisu Rem Wang (remysucre)
- Tony Cox (tony-cox)
- EdorianDark
- Colman Humphrey (ColmanHumphrey)
- Stephan Beyer sbeyer
- Ophir Lojkine lovasoa
- Parse and provide the objective value
- Config for lp_solve and CPLEX
- 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
- ...