### 12 releases

0.2.5 | Feb 12, 2024 |
---|---|

0.2.4 | Jan 1, 2023 |

0.2.3 | Jan 6, 2022 |

0.2.2 | Aug 3, 2021 |

0.0.5 | May 12, 2021 |

#**513** in Algorithms

**62** downloads per month

Used in relp-bin

**GPL-3.0-only**

740KB

14K
SLoC

# RELP: Rust Exact Linear Programming

A framework to describe and solve linear programs exactly, written in Rust. Linear programming is a modelling technique to solve the wide range of optimization problems that can be represented by linear constraints and a linear target function.

This repository houses the library. Do you just want to solve a linear program stored in a file from the command line? See

.`relp-bin`

## Usage

Add this to your

:`Cargo.toml`

`[``dependencies``]`
`relp ``=` `"`0.2.4`"`

You'll probably want to use the number types provided by the

crate, so include that dependency as well:`relp-num`

`relp-num = "0.1.11"
`

You can now use both crates, for example to read a linear program in the classic MPS format in arbitrary precision:

`fn` `main``(``)`` ``{`
`let` path `=` `std``::``path``::``Path``::`new`(``"`my_program.mps`"``)``;`
`let` my_program `=` `relp``::``io``::``import``::``<``relp_num``::`RationalBig`>``(`path`)``;`
`}`

## Features

### Describing LPs

Linear programs are described through a constraint matrix, right-hand side vector and cost function. You can provide these explicitly, but Relp also offers the

trait which can be implemented to represent your problem. You can find an example implementation of this trait for the shortest path and max flow problems in the `MatrixProvider`

directory. You can capture the specific properties of your problem by implementing additional traits, such as the `examples/`

trait in case you know a partial initial basis for your problem.`PartialInitialBasis`

### Solving LPs

Relp provides standard solve procedures for implementors of the aforementioned

trait through the `MatrixProvider`

trait: simply call `SolveRelaxation`

with that trait in scope. When additional traits are implemented, will the problem-specific properties they represent be exploited by faster solve procedures, seemlessly hidden behind that same call.`problem .solve_relaxation()`

For more advanced use cases, it is also possible to replace some of the solve default algorithms. You can, for example, implement your own pivot rule or basis factorization.

## Roadmap

- Two-phase simplex algorithm
- Lazy column generation
- LU decomposition
- Steepest descent pricing
- Presolving framework
- Prescaling framework
- Integer variables through Gomory cuts
- Floating point support
- Branch and bound

#### Dependencies

~1.6–2.3MB

~50K SLoC