# linprog
A Rust library for optimizing [linear programming](https://en.wikipedia.org/wiki/Linear_programming) (LP) models, implemented using [Dantzig's simplex algorithm](https://en.wikipedia.org/wiki/Simplex_algorithm).
Linprog provides utilities to create and optimize dynamic LP models.
This library does not (yet :turtle:) support mixed integer programming.
Linprog is available on [crates.io](https://crates.io/crates/linprog)!
## Table of contents
- [linprog](#linprog)
- [Table of contents](#table-of-contents)
- [Usage](#usage)
- [Understanding a LP's lifetime in linprog](#understanding-a-lps-lifetime-in-linprog)
- [Example](#example)
- [Example with story](#example-with-story)
- [How you can help](#how-you-can-help)
- [Authors](#authors)
- [License](#license)
## Usage
Add this to your `Cargo.toml`:
```toml
[dependencies]
linprog = "0.3"
```
Then bring the library into scope:
```rust
use linprog::{
Model,
Objective,
Summand,
Operator,
Var
};
```
### Understanding a LP's lifetime in linprog
In this library a linear program is represented by a datatype called `Model`, created like this:
```rust
let mut model = Model::new("My LP", Objective::Max);
```
The `Model`'s lifetime follows three strictly seperated phases:
- In the first (and initially set) phase, variables can be registered.
```rust
let mut vars: Vec<Var> = vec![];
vars.push(model.reg_var(2.0));
```
- In the second phase, constraints can be registered.
```rust
model.reg_constr(vec![Summand(1.0, &vars[0])], Operator::Le, 10.0);
```
- In the third phase, the `Model` can be optimized.
```rust
model.optimize();
```
The `Models`'s phase can be explicitly updated to the next phase using the `update` method. Or implicitly, by calling the method for the next phase.
After the variables or constraints are submitted to the `Model`, they can not be changed again (The phases can not be reverted or modified).
## Example
The code below can be used to optimize the following model:
```
max. 3x + 5y
st. x + 2y <= 170
3y <= 180
```
Rust implementation:
```rust
let mut model = Model::new("Readme example", Objective::Max);
let mut vars: Vec<Var> = vec![];
vars.push(model.reg_var(3.0));
vars.push(model.reg_var(5.0));
model.reg_constr(
vec![Summand(1.0, &vars[0]), Summand(2.0, &vars[1])],
Operator::Le,
170.0,
);
model.reg_constr(
vec![Summand(1.0, &vars[0]), Summand(1.0, &vars[1])],
Operator::Le,
150.0,
);
model.reg_constr(
vec![Summand(0.0, &vars[0]), Summand(3.0, &vars[1])],
Operator::Le,
180.0,
);
model.optimize();
print!("{}", model);
```
This program will print out the following:
```
Model "Readme example" [optimized]:
Optimum: 490
Variable "1": 130
Variable "2": 20
```
## Example with story
Lets say a company produces three products:
- Product `A` selling at `50$`
- Product `B` selling at `100$`
- Product `C` selling at `110$`
The company has three machines:
- Machine `X` with a maximum operating minutes per week of `2500`
- Machine `Y` with a maximum operating minutes per week of `2000`
- Machine `Z` With a maximum operating minutes per week of `450`
Every product needs to be processed by one of the machines for a specific amount of time:
- One unit of `A` needs
- `10` min. at `X`
- `4` min. at `Y`
- `1` min. at `Z`
- One unit of `B` needs
- `5` min. at `X`
- `10` min. at `Y`
- `1.5` min. at `Z`
- One unit of `C` needs
- `6` min. at `X`
- `9` min. at `Y`
- `3` min. at `Z`
The question is: How mutch units does the company want to produce for each product in order to `maximize` their profit?
In the Rust program, the data could look like this:
```rust
let products: HashMap<&str, f64> = [
("Product A", 50.0),
("Product B", 100.0),
("Product C", 110.0),
].iter().cloned().collect();
let machines: HashMap<&str, f64> = [
("Machine X", 2500.0),
("Machine Y", 2000.0),
("Machine Z", 450.0),
].iter().cloned().collect();
let mut time_needed: HashMap<(&str, &str), f64> = HashMap::new();
time_needed.insert(("Product A", "Machine X"), 10.0);
time_needed.insert(("Product A", "Machine Y"), 4.0);
time_needed.insert(("Product A", "Machine Z"), 1.0);
time_needed.insert(("Product B", "Machine X"), 5.0);
time_needed.insert(("Product B", "Machine Y"), 10.0);
time_needed.insert(("Product B", "Machine Z"), 1.5);
time_needed.insert(("Product C", "Machine X"), 6.0);
time_needed.insert(("Product C", "Machine Y"), 9.0);
time_needed.insert(("Product C", "Machine Z"), 3.0);
```
A less verbose way to define the data might look like this:
```rust
let product_price: [f64;3] = [50.0, 100.0, 110.0];
let machine_max_workload: [f64;3] = [2500.0, 2000.0, 450.0];
let prod_machine_time_needed: [[f64;3];3] = [
[10.0, 4.0, 1.0],
[5.0, 10.0, 1.5],
[6.0, 9.0, 3.0],
];
```
For the sake of this example, I will use the previous of the two versions.
Now onto the Model's construction:
```rust
let mut model = Model::new("ABC_Company", Objective::Max);
let mut vars: HashMap<&str, Var> = HashMap::new();
```
Then register the variables with names and prices:
```rust
for (product, &price) in &products {
vars.insert(product, model.reg_var_with_name(price, product));
}
```
Register the constraints:
```rust
for (&machine, &max_time) in &machines {
let mut sum: Vec<Summand> = Vec::new();
for (&product, _) in &products {
sum.push(Summand(time_needed[&(product, machine)], &vars[product]));
}
model.reg_constr(sum, Operator::Le, max_time);
}
```
Finally the model gets optimized and the results get printed:
```rust
model.optimize();
print!("{}", model);
```
The output will look like this:
```
Model "ABC_Company" [optimized]:
Optimum: 22738.095238095237
Variable "Product C": 47.61904761904763
Variable "Product A": 178.57142857142856
Variable "Product B": 85.71428571428572
```
A customized display of the solution could be done in this way:
```rust
println!("\nThe optimum is at {:.*}$.", 2, model.optimum().unwrap());
for (product, var) in &vars {
println!("We need to produce {} units of product {}.", model.x(&var).unwrap().floor(), product);
}
```
Leading to the following output:
```
The optimum is at 22738.10$.
We need to produce 85 units of product Product B.
We need to produce 178 units of product Product A.
We need to produce 47 units of product Product C.
```
Make of this what you want :ok_woman:
## How you can help
* Please have a look at the [help wanted issues](https://github.com/jonathansc/linprog/labels/help%20wanted) -- these include both development and data supply issues
## Authors
* Jonathan S. - *Developer* - jonathansc(at)airmail.cc
## License
This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details