RELP：Rust精确线性规划

一个用Rust编写的描述和精确求解线性规划的框架。 线性规划 是一种建模技术，用于解决可以表示为线性约束和线性目标函数的广泛优化问题。

此仓库包含库。您只想从命令行解决存储在文件中的线性规划吗？请参阅 relp-bin。

用法

将此添加到您的 Cargo.toml

[dependencies]
relp = "0.2.4"

您可能希望使用由 relp-num crate 提供的数字类型，因此请包括此依赖项

relp-num = "0.1.11"

现在您可以同时使用这两个crate，例如，以任意精度读取经典 MPS格式 的线性规划

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

功能

描述LP

通过约束矩阵、右侧向量和成本函数描述线性规划。您可以明确提供这些，但Relp还提供了 MatrixProvider trait，该trait可以实现以表示您的问题。您可以在 示例目录 中找到此trait的示例实现，用于最短路径和最大流问题。您可以通过实现其他trait，例如在知道问题的部分初始基的情况下实现 PartialInitialBasis trait，来捕获您问题的特定属性。

求解LP

Relp为上述MatrixProvider特质的实现者提供了标准的求解过程，通过SolveRelaxation特质：只需简单地在该特质的作用域内调用problem.solve_relaxation()。当实现其他特质时，它们所代表的特定问题属性将被更快的求解过程利用，而这一切都隐藏在相同的调用背后。

对于更高级的使用场景，也可以替换一些默认的求解算法。例如，您可以实现自己的主元规则或基向量分解。

路线图

• 两阶段单纯形算法
• 懒惰列生成
• LU分解
• 最速下降定价
• 预处理框架
• 预缩放框架
• 通过Gomory割集实现整数变量
• 浮点数支持
• 分支定界