lp-modeler

此项目为 Rust 提供了一个数学规划建模库。

一个优化问题（例如整数或线性规划）可以使用熟悉的 Rust 语法（见示例）进行公理化，并写入通用的 LP 模型格式。然后可以由混合整数规划求解器进行处理。目前支持需要单独安装（见下面的示例部分）并在运行时存在于基于 lp_modeler 的项目中的求解器

• COIN-OR cbc
• Gurobi
• GLPK

目前支持作为 Rust crate（作为 可选功能）导入的求解器

• minilp
• coin_cbc（需要在编译基于 lp_modeler 的项目的编译时存在 Cbc 库文件，有关如何做到这一点的说明，请参阅 coin_cbc 项目 README）

此项目受到了 COIN-OR PuLP 的启发，后者为 Python 提供了这样的库。

用法

以下示例展示了公理化（在 LP 模型格式中），并演示了生成此公理化所需的 Rust 代码。代码可在 tests/problems.rs 中找到。

示例 1 - 简单模型

公理化

\ 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 代码

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),
    }
}

生成上述所示的 LP 文件

problem.write_lp("problem.lp")

示例 2 - 一个分配模型

公理化

这个更复杂的公式通过程序生成目标函数和约束的表达式。

我们希望最大化一组男性和女性之间匹配的质量，基于他们之间的兼容性分数。每个男人必须被分配给一个女性，反之亦然。

兼容性分数矩阵

这个问题被表述为一个分配问题。

Rust 代码

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);
        }
    }
}

此代码计算目标函数值并处理输出以打印选择的男性和女性的匹配

Status: Optimal
Objective Value: 230
B_E = 1
C_D = 1
A_F = 1

安装外部求解器

安装 conda（包管理器）

如果您想安装 Cbc、Gurobi 或 GLPK 的最新发布版本，最简单的跨平台安装途径应该是通过 conda。重要的是，这不需要在您要安装它的系统上拥有管理员权限。您需要做的只是 安装 conda。完成此操作后，使用您想使用的求解器的相应 conda 命令（见下文）。

COIN-OR Cbc

最新发布版本（通过 conda）

要使用 conda（安装说明见上文）获取您的系统上最新的 Cbc 发布版本，请使用此命令

conda create -n coin-or-cbc -c conda-forge coin-or-cbc

然后激活新创建的环境将使 cbc 可执行文件可用

conda activate coin-or-cbc

最新发布版本（通过 coinbrew）

要获取最新的 Cbc 发布版本（包括 .），我们建议使用 COIN-OR 的 coinbrew，具体说明如下：https://coin-or.github.io/user_introduction#building-from-source

最新提交（通过 coinbrew）

要获取最新的 Cbc 版本（包括未发布的错误修复），您需要 从源代码构建它。我们建议使用 COIN-OR 的 coinbrew，具体说明如下：https://coin-or.github.io/user_introduction#building-from-source

GLPK

近期发布版本（通过 conda）

要使用 conda 为您的系统获取 GLPK 的最新发布版本，请使用此命令

conda create -n glpk -c conda-forge glpk

然后激活新创建的环境将使 glpsol 可执行文件可用

conda activate glpk

Gurobi

最新发布版本（通过 conda）

要使用 Gurobi，您需要有效的 许可证密钥，并且需要将其放置在 Gurobi 可以找到它的位置。一旦您拥有有效的许可证，您可以使用 conda 为您的系统获取最新的 Gurobi 发布版本，使用此命令

conda create -n gurobi -c gurobi gurobi

然后激活新创建的环境将使 gurobi_cl 可执行文件可用

conda activate gurobi

变更日志

0.5.0

• 向 Rust 原生求解器 minilp 添加了本地 minilp 实现
• 将基于 coin_cbc 的 NativeCbcSolver 改为可选功能
• 修复了向 NativeCbc 添加上界的问题
• 添加了 coinstraint! 宏
• 添加了 AddAssign、SubAssign 和 MulAssign 特性
• 重写了各种内部函数以删除递归（修复了相关的堆栈溢出问题）
• 将求解器的安装信息添加到文档中

0.4.3

• 添加了本地 coin-or 实现（NativeCBCSolver），通过 C API 调用 CoinOR CBC。

0.4.2

• 修复了（expr-c1）+c2 的错误简化

0.4.1

• 修复了不可行解上的 cbc 解析失败

0.4.0

• 改进了模块

  • 移除了 maplit 依赖
  • 将所有编写表达式和约束的功能放入 dsl 模块中
  • 使用 use lp_modeler::dsl::* 就足以编写一个系统
  • 使用 use lp_modeler::solvers::* 始终用于选择一个求解器

• 为 LpExpression 向量添加一个 sum() 方法，而不是使用 lp_sum() 函数

• 添加一个用于形式的 sum() 函数

  problem += sum(&vars, |&v| v * 10.0) ).le(10.0);
  

0.3.3

• 修复并改进 GLPK 解析的错误信息
• 使用 rust fmt 格式化代码

0.3.3

• 在文档中添加新示例
• 改进 0.0 比较

0.3.1

• 添加分配律（例如：3 * (a + b + 2) = 3*a + 3*b + 6）
• 添加平凡规则（例如：3 * a * 0 = 0 或 3 + 0 = 3）
• 添加交换律以简化某些计算
• 支持 GLPK