microlp 0.5.0

A fast linear programming solver library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

//! A shadow model of an LP/MILP instance, kept alongside the `microlp::Problem`.
//!
//! `microlp::Problem` does not expose its constraint matrix or variable domains,
//! so the suite records its own copy of everything while building. This shadow
//! copy is what the independent verifier checks returned solutions against —
//! deliberately *not* trusting any state inside the solver.

use microlp::{ComparisonOp, OptimizationDirection, Problem, Variable};

#[derive(Clone, Copy, PartialEq)]
pub enum Domain {
    Real,
    Integer,
}

#[derive(Clone)]
pub struct VarSpec {
    pub obj_coeff: f64,
    pub min: f64,
    pub max: f64,
    pub domain: Domain,
}

#[derive(Clone)]
pub struct ConstraintSpec {
    pub terms: Vec<(usize, f64)>, // (variable index, coefficient)
    pub op: ComparisonOp,
    pub rhs: f64,
}

#[derive(Clone)]
pub struct ModelSpec {
    pub vars: Vec<VarSpec>,
    pub constraints: Vec<ConstraintSpec>,
}

/// Builds a `microlp::Problem` and the shadow `ModelSpec` in lockstep.
pub struct Builder {
    pub problem: Problem,
    pub spec: ModelSpec,
    pub vars: Vec<Variable>,
}

impl Builder {
    pub fn new(direction: OptimizationDirection) -> Self {
        Builder {
            problem: Problem::new(direction),
            spec: ModelSpec {
                vars: vec![],
                constraints: vec![],
            },
            vars: vec![],
        }
    }

    pub fn real(&mut self, obj_coeff: f64, min: f64, max: f64) -> Variable {
        let v = self.problem.add_var(obj_coeff, (min, max));
        self.push_spec(v, obj_coeff, min, max, Domain::Real);
        v
    }

    pub fn integer(&mut self, obj_coeff: f64, min: i32, max: i32) -> Variable {
        let v = self.problem.add_integer_var(obj_coeff, (min, max));
        self.push_spec(v, obj_coeff, min as f64, max as f64, Domain::Integer);
        v
    }

    pub fn binary(&mut self, obj_coeff: f64) -> Variable {
        let v = self.problem.add_binary_var(obj_coeff);
        self.push_spec(v, obj_coeff, 0.0, 1.0, Domain::Integer);
        v
    }

    fn push_spec(&mut self, v: Variable, obj_coeff: f64, min: f64, max: f64, domain: Domain) {
        assert_eq!(v.idx(), self.spec.vars.len(), "shadow model out of sync");
        self.spec.vars.push(VarSpec {
            obj_coeff,
            min,
            max,
            domain,
        });
        self.vars.push(v);
    }

    pub fn constraint(&mut self, terms: &[(Variable, f64)], op: ComparisonOp, rhs: f64) {
        self.problem.add_constraint(terms, op, rhs);
        self.spec.constraints.push(ConstraintSpec {
            terms: terms.iter().map(|(v, c)| (v.idx(), *c)).collect(),
            op,
            rhs,
        });
    }
}

/// Comparison tolerance for objective values: `|a - b| <= abs + rel * |b|`.
#[derive(Clone, Copy)]
pub struct Tol {
    pub abs: f64,
    pub rel: f64,
}

impl Tol {
    pub const DEFAULT: Tol = Tol {
        abs: 1e-6,
        rel: 1e-6,
    };

    pub fn matches(&self, got: f64, expected: f64) -> bool {
        (got - expected).abs() <= self.slack(expected)
    }

    /// The absolute slack this tolerance grants around `expected`.
    pub fn slack(&self, expected: f64) -> f64 {
        self.abs + self.rel * expected.abs()
    }
}

/// What the suite knows about the true answer of a case.
pub enum Expected {
    Objective {
        value: f64,
        tol: Tol,
        /// Variable values, asserted only when the optimum is known to be unique.
        vars: Option<Vec<(Variable, f64)>>,
    },
    Infeasible,
    Unbounded,
}

impl Expected {
    pub fn objective(value: f64) -> Expected {
        Expected::Objective {
            value,
            tol: Tol::DEFAULT,
            vars: None,
        }
    }

    pub fn objective_tol(value: f64, tol: Tol) -> Expected {
        Expected::Objective {
            value,
            tol,
            vars: None,
        }
    }

    pub fn unique(value: f64, vars: Vec<(Variable, f64)>) -> Expected {
        Expected::Objective {
            value,
            tol: Tol::DEFAULT,
            vars: Some(vars),
        }
    }
}