Ockham - OR toolkit

comprehensive OR toolkit for LP, optimization & math modeling in rust. provides efficient, numerically stable algorithms w/ clean API.

features

• performance: optimized simplex solver w/ multiple pivot rules
• intuitive API: builder pattern for easy problem construction
• variable types: continuous, int & binary vars
• robust numerics: scaling, presolve & validation utils
• extensible: plugin arch for custom solvers
• comprehensive: detailed diagnostics & solution analysis
• pure rust: memory-safe, concurrent & cross-platform

Quick Start

Add Ockham to your Cargo.toml:

[dependencies]
ockham = "0.1.0"

Basic Example

use ockham::prelude::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Create a simple linear program: maximize 3x + 2y subject to x + y <= 10, x,y >= 0
    let problem = ProblemBuilder::new()
        .add_non_negative_variable("x")?
        .add_non_negative_variable("y")?
        .add_constraint_by_name(
            &[("x", 1.0), ("y", 1.0)],
            ConstraintType::LessEqual,
            10.0,
        )?
        .objective_by_name(
            &[("x", 3.0), ("y", 2.0)],
            ObjectiveType::Maximize,
        )?
        .build()?;

    // Solve the problem
    let solution = solve(&problem)?;

    if solution.is_optimal() {
        println!("Optimal solution found!");
        println!("x = {:.2}", solution.variables[0]);
        println!("y = {:.2}", solution.variables[1]);
        println!("Objective value = {:.2}", solution.objective_value);
    }

    Ok(())
}

Examples

The repository includes several detailed examples:

• Basic LP: Simple linear programming problem
• Production Planning: Resource allocation optimization
• Diet Problem: Cost minimization with nutritional constraints

Run examples with:

cargo run --example basic_lp
cargo run --example production_planning
cargo run --example diet_problem

Problem Modeling

Variables

use ockham::prelude::*;

let mut builder = ProblemBuilder::new();

// Continuous variables
builder = builder.add_variable("x", 0.0, 100.0)?;           // Bounded
builder = builder.add_non_negative_variable("y")?;          // Non-negative
builder = builder.add_free_variable("z")?;                  // Unbounded

// Integer variables
builder = builder.add_integer_variable("i", 0.0, 10.0)?;    // Integer
builder = builder.add_binary_variable("b")?;                // Binary (0 or 1)

Constraints

// Using variable names (recommended)
builder = builder.add_constraint_by_name(
    &[("x", 2.0), ("y", 3.0)],
    ConstraintType::LessEqual,
    15.0,
)?;

// Using coefficient vectors
builder = builder.add_constraint(
    vec![1.0, 1.0, 0.0],
    ConstraintType::Equal,
    5.0,
)?;

// Named constraints for debugging
builder = builder.add_named_constraint(
    "capacity",
    vec![2.0, 3.0],
    ConstraintType::LessEqual,
    100.0,
)?;

Objectives

// Maximize profit
builder = builder.objective_by_name(
    &[("x", 10.0), ("y", 15.0)],
    ObjectiveType::Maximize,
)?;

// Minimize cost with constant term
let objective = Objective::new_with_constant(
    vec![2.0, 3.0],
    ObjectiveType::Minimize,
    100.0, // Fixed cost
)?;

Advanced Features

Presolve

Automatically simplify problems before solving:

let presolve = Presolve::new();
let result = presolve.apply(&problem)?;
println!("{}", result.statistics);

Scaling

Improve numerical stability:

let scaling = Scaling::new(ScalingMethod::Equilibration);
let scaled_problem = scaling.apply(&problem)?;

Custom Solver Configuration

let config = SolverConfig::new()
    .with_max_iterations(10_000)
    .with_optimality_tolerance(1e-9)
    .verbose()
    .with_option("pivot_rule", "steepest_edge");

let solution = solve_with_config(&problem, &config)?;

Problem Validation

let validator = Validator::new();
let validation = validator.validate(&problem);

if !validation.is_valid {
    for error in &validation.errors {
        eprintln!("Error: {}", error);
    }
}

Solver Algorithms

Simplex Method

• Two-phase method for handling artificial variables
• Multiple pivot rules: Most negative, first negative, steepest edge
• Degeneracy handling with Bland's anti-cycling rule
• Numerical stability with careful pivot selection

Future Algorithms

• Interior Point Methods
• Branch and Bound (for integer programming)
• Cutting Plane Methods
• Heuristic Algorithms

Performance

Ockham is designed for performance:

• Efficient data structures minimize memory allocation
• SIMD optimizations for linear algebra operations (optional)
• Parallel processing support (optional)
• Benchmark suite for performance regression testing

Run benchmarks:

cargo bench

Features Flags

• default = ["serde"]

• serde: Serialization support for problems and solutions

• parallel: Parallel processing with Rayon

• linalg: Advanced linear algebra with nalgebra

License

Licensed under MIT license (http://opensource.org/licenses/MIT)