DOCSEARCHbyAlgolia
Submit Docs

good_lp

repository·main·Indexed 19 days ago

https://github.com/rust-or/good_lp

A Mixed Integer Linear Programming (MILP) modeler for Rust providing an idiomatic, type-safe API to define optimization problems. It supports various backend solvers including coin_cbc (default), highs, lpsolve, microlp, lp-solvers, scip, cplex-rs, and clarabel. The library features macros for declaring variables and constraints, and allows for the definition of objective functions via maximise() and minimise() methods.

Tokens
13K
Snippets
60
Records
69
Agent score
65%

What's inside good_lp

  1. Understand variable types and value representation in good_lp

    main

    In good_lp, all variable values and coefficients are internally represented as f64. This affects how you define constraints and how you retrieve results:

    • Defining Constraints: You can use either f64 or i32 to express constraints on variable ranges. i32 values are losslessly converted to f64. Note that types like usize cannot be used directly if they cannot be converted to f64 losslessly.
    • Integer Variables: You can restrict variables to integer values using the (integer) qualifier within the variables! macro.
    • Solution Values: Regardless of whether a variable is defined as continuous or integer, the solution.value(variable) method always returns an f64. You must account for this when performing arithmetic on solution values to avoid compilation errors.
    // Correct use of f64 and i32 to specify feasible ranges for Variables
  variables! {
    problem:
      a <= 10.0;
      2 <= b (integer) <= 4;  // Variables can be restricted using qualifiers like (integer)
  };
  let model = problem
    .maximise(b)
    .using(default_solver)
    .with(constraint!(a + 2 <= b))
    .with(constraint!(1 + a >= 4.0 - b));

// Accessing solution values (always returns f64)
println!("a={}   b={}", solution.value(a), solution.value(b));
println!("a + b = {}", solution.eval(a + b));

// WARNING: This will cause a compilation error because solution.value(a) is f64
// println!("a + 1 = {}", solution.value(a) + 1);

  2. Use the lp-solvers feature for external command-line solvers

    main

    The lp-solvers feature allows good_lp to call external solver commands (like gurobi, cplex, cbc, or glpk) at runtime by writing the problem to a .lp file.

    Considerations:

    • Overhead: There is a delay (hundreds of milliseconds) for file I/O and process launching. This is not recommended for high-frequency solving (e.g., in a web server).
    • Deployment: The end user must have the desired solver installed on their system.

  3. Use Clarabel for fast linear programming and dual values

    main

    Clarabel is a Rust-based linear programming solver.

    Limitations: It does not support integer variables.

    Benefits: It is fast, easy to install, and implements the SolutionWithDual trait, which allows you to access the dual values (shadow prices) of the constraints.

  4. Quickstart: Modeling a Linear Program with good_lp

    main

    You can define a Mixed Integer Linear Programming (MILP) model using the variables! and constraint! macros. This approach allows for an idiomatic Rust syntax to express variables, bounds, objective functions, and constraints.

    Key steps:

    1. Use variables! to declare variables and their bounds (e.g., a <= 1).
    2. Call .maximise() or .minimise() on the variable set to define the objective function.
    3. Use .using(solver) to specify the solver.
    4. Chain .with(constraint!(...)) to add constraints.
    5. Call .solve() to obtain a Solution.
    6. Use .value(variable) to retrieve the optimal value of a specific variable or .eval(expression) to evaluate an expression at the optimal point.
    use std::error::Error;
use good_lp::{constraint, default_solver, Solution, SolverModel, variables};

fn main() -> Result<(), Box<dyn Error>> {
    variables! {
        vars: {
               a <= 1;
          2 <= b <= 4;
        }
    }
    let solution = vars.maximise(10 * (a - b / 5) - b)
        .using(default_solver) // IBM's coin_cbc by default
        .with(constraint!(a + 2 <= b))
        .with(constraint!(1 + a >= 4 - b))
        .solve()?;

    println!("a={}   b={}", solution.value(a), solution.value(b));
    println!("a + b = {}", solution.eval(a + b));
    Ok()
}

  5. Use the microlp solver for WASM or zero-dependency builds

    main

    microlp is a pure Rust solver (a fork of minilp). It is ideal for environments where you cannot install a C compiler or external libraries, and it supports WASM targets.

    Important: It performs poorly in debug mode. Always use --release mode when solving large problems with microlp.

  6. Use SCIP with bundled binaries

    main

    SCIP is a high-performance solver for MIP and MINLP. The easiest way to use it with good_lp is to enable both the scip and scip_bundled features to use a precompiled binary.

    Alternatively, you can use a custom installation by enabling only the scip feature. You can install SCIP via conda:

    conda install --channel conda-forge scip

  7. Use the lp_solve solver

    main

    lp_solve is an implementation of the lp_solve open-source solver (LGPL license) within good_lp. It uses the revised simplex method for linear and integer programming.

    To use it, pass an UnsolvedProblem to the lp_solve() function. This returns an LpSolveProblem which implements the SolverModel trait, allowing you to add constraints and call .solve().

    Requirements: You must have a C compiler available on your system, but you do not need to install any additional libraries manually as good_lp uses the lpsolve crate to handle the bindings.

    use good_lp::lp_solve;

// Assuming 'problem' is an UnsolvedProblem created via the good_lp API
let solution = lp_solve(problem)
    .with_time_limit(60.0)
    .solve()
    .expect("Failed to solve");

println!("Optimal value: {}", solution.value(some_variable));

  8. Configure alternative solvers via Cargo features

    main

    By default, good_lp uses the coin_cbc solver. To use a different solver, you must disable default features and enable the specific feature for your chosen solver in Cargo.toml.

    Note: The lpsolve and cplex-rs features are mutually exclusive and will cause a compilation error if both are enabled. Using --all-features will also cause a compilation error.

    good_lp = { version = "*", features = ["your solver feature name"], default-features = false }

  9. Install dependencies for the CBC solver

    main

    The default coin_cbc solver requires the Cbc C library headers during build and the dynamic library at runtime.

    Ubuntu:

    sudo apt-get install coinor-cbc coinor-libcbc-dev

    MacOS (Homebrew):

    brew install cbc

    Warning: If you manually enable the coin_cbc feature (disabling default features), you must also enable the singlethread-cbc feature unless you have compiled Cbc with the CBC_THREAD_SAFE option, otherwise multi-threaded usage is unsafe.

  10. How to define variables and expressions

    main

    Variables are the building blocks of your model. You can create them in bulk using the variables! macro or individually. Once created, they can be combined into Expression objects using standard arithmetic operators. You can also write helper functions that take Variable as input and return Expression to modularize complex objective functions.

    use good_lp::{Expression, Variable, variables};

// Programmatic approach
let mut vars = variables!{};
let x = vars.add(variable().min(2).max(9));

// Modular expression approach
fn total_cost(energy: Variable, time: Variable) -> Expression {
    energy_cost(energy) + 10.0 * time
}

fn energy_cost(energy: Variable) -> Expression {
    energy * 0.5
}

  11. Use the Expression type for linear programming

    main

    The Expression type represents an affine expression (e.g., 2x + 3). It is the primary building block for defining objective functions and constraints in good_lp. You can create expressions from constants (f64, i32) or Variable objects using the From trait or arithmetic operators.

    Key capabilities:

    • Arithmetic: Supports standard operators (+, -, *, /) between expressions, variables, and scalars.
    • Constraint Creation: Use methods like .leq(), .geq(), and .eq() to turn an expression into a Constraint.
    • Evaluation: Use .eval_with(&solution) to calculate the numerical value of an expression given a specific variable assignment (a Solution).
    use good_lp::Expression;
// Assuming variables are already created
let expr = 2.0 * v1 + 3.0 * v2 + 5.0;
let constraint = expr.leq(10.0);
let value = expr.eval_with(&solution);

  12. How UnsolvedProblem and Solvers work together

    main

    The workflow for solving a problem in good_lp follows this pattern:

    1. Define Variables: Use ProblemVariables to create and add variables.
    2. Define Objective: Use .maximise() or .minimise() on the ProblemVariables instance to create an UnsolvedProblem.
    3. Attach Solver: Call .using(solver) on the UnsolvedProblem to convert it into a SolverModel.
    4. Add Constraints: Use .with(constraint) on the SolverModel to add constraints.
    5. Solve: Call .solve() on the SolverModel to get a Solution.
    6. Extract Values: Use solution.value(variable) to get the result for a specific variable.
    use good_lp::{variables, variable, default_solver, SolverModel, Solution};
use good_lp::solvers::ObjectiveDirection;

// 1. Define variables
variables! {problem: 0 <= x <= 10;}
let x = problem.add(variable().min(0).max(10));

// 2 & 3. Define objective and attach solver
let mut model = problem.maximise(x).using(default_solver);

// 4. Add constraints (if any)
// model = model.with(constraint!(x >= 5));

// 5. Solve
let solution = model.solve().unwrap();

// 6. Extract values
let val = solution.value(x);