use crate::game::Rational;
use num_traits::{One, Zero};
#[derive(Debug, Clone, PartialEq)]
pub struct LpProblem {
pub objective: Vec<Rational>,
pub constraints: Vec<Vec<Rational>>,
pub rhs: Vec<Rational>,
}
#[derive(Debug, Clone, PartialEq)]
pub enum LpSolution {
Optimal {
x: Vec<Rational>,
value: Rational,
},
Infeasible,
Unbounded,
}
pub fn solve_lp(problem: LpProblem) -> LpSolution {
let LpProblem {
objective,
mut constraints,
mut rhs,
} = problem;
let rows = constraints.len();
assert_eq!(
rows,
rhs.len(),
"constraint rows and right-hand sides must match: {rows} rows, {} values",
rhs.len()
);
if rows == 0 {
return if objective.iter().any(|c| *c > Rational::zero()) {
LpSolution::Unbounded
} else {
LpSolution::Optimal {
x: vec![Rational::zero(); objective.len()],
value: Rational::zero(),
}
};
}
let cols = constraints[0].len();
assert!(
constraints.iter().all(|row| row.len() == cols),
"constraint matrix must be rectangular: expected {cols} columns in every row"
);
assert_eq!(
objective.len(),
cols,
"objective length must match the column count: {} vs {cols}",
objective.len()
);
for r in 0..rows {
if rhs[r] < Rational::zero() {
for entry in constraints[r].iter_mut() {
*entry = -&*entry;
}
rhs[r] = -&rhs[r];
}
}
let total = cols + rows;
let mut tableau: Vec<Vec<Rational>> = Vec::with_capacity(rows);
for r in 0..rows {
let mut row = Vec::with_capacity(total + 1);
row.extend(constraints[r].iter().cloned());
for a in 0..rows {
row.push(if a == r {
Rational::one()
} else {
Rational::zero()
});
}
row.push(rhs[r].clone());
tableau.push(row);
}
let mut basis: Vec<usize> = (cols..total).collect();
let mut phase_one_cost = vec![Rational::zero(); total];
for c in phase_one_cost.iter_mut().skip(cols) {
*c = -Rational::one();
}
match simplex(&mut tableau, &mut basis, &phase_one_cost, total) {
SimplexOutcome::Optimal => {}
SimplexOutcome::Unbounded => unreachable!("phase one is bounded above by zero"),
}
let phase_one_value = objective_value(&tableau, &basis, &phase_one_cost);
if phase_one_value < Rational::zero() {
return LpSolution::Infeasible;
}
let mut r = 0usize;
while r < tableau.len() {
if basis[r] < cols {
r += 1;
continue;
}
match (0..cols).find(|&c| !tableau[r][c].is_zero()) {
Some(c) => {
pivot(&mut tableau, &mut basis, r, c);
r += 1;
}
None => {
tableau.remove(r);
basis.remove(r);
}
}
}
let mut phase_two_cost = objective.clone();
phase_two_cost.resize(total, Rational::zero());
match simplex(&mut tableau, &mut basis, &phase_two_cost, cols) {
SimplexOutcome::Unbounded => LpSolution::Unbounded,
SimplexOutcome::Optimal => {
let mut x = vec![Rational::zero(); cols];
for (r, &b) in basis.iter().enumerate() {
if b < cols {
x[b] = tableau[r][total].clone();
}
}
let value = objective
.iter()
.zip(&x)
.fold(Rational::zero(), |acc, (c, v)| acc + c * v);
LpSolution::Optimal { x, value }
}
}
}
enum SimplexOutcome {
Optimal,
Unbounded,
}
fn simplex(
tableau: &mut [Vec<Rational>],
basis: &mut [usize],
cost: &[Rational],
enterable: usize,
) -> SimplexOutcome {
let total = cost.len();
loop {
let entering = (0..enterable).find(|&c| {
let dual: Rational = basis
.iter()
.enumerate()
.fold(Rational::zero(), |acc, (r, &b)| {
acc + &cost[b] * &tableau[r][c]
});
&cost[c] - dual > Rational::zero()
});
let Some(entering) = entering else {
return SimplexOutcome::Optimal;
};
let mut leaving: Option<usize> = None;
let mut best_ratio: Option<Rational> = None;
for r in 0..tableau.len() {
if tableau[r][entering] <= Rational::zero() {
continue;
}
let ratio = &tableau[r][total] / &tableau[r][entering];
let take = match &best_ratio {
None => true,
Some(best) => {
ratio < *best || (ratio == *best && basis[r] < basis[leaving.unwrap()])
}
};
if take {
best_ratio = Some(ratio);
leaving = Some(r);
}
}
let Some(leaving) = leaving else {
return SimplexOutcome::Unbounded;
};
pivot(tableau, basis, leaving, entering);
}
}
fn pivot(tableau: &mut [Vec<Rational>], basis: &mut [usize], row: usize, col: usize) {
let p = tableau[row][col].clone();
for entry in tableau[row].iter_mut() {
*entry /= &p;
}
let pivot_row = tableau[row].clone();
for (r, current) in tableau.iter_mut().enumerate() {
if r == row || current[col].is_zero() {
continue;
}
let factor = current[col].clone();
for (entry, pivot_entry) in current.iter_mut().zip(&pivot_row) {
*entry -= &factor * pivot_entry;
}
}
basis[row] = col;
}
fn objective_value(tableau: &[Vec<Rational>], basis: &[usize], cost: &[Rational]) -> Rational {
let total = cost.len();
basis
.iter()
.enumerate()
.fold(Rational::zero(), |acc, (r, &b)| {
acc + &cost[b] * &tableau[r][total]
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::Rational;
fn int(n: i64) -> Rational {
Rational::from_integer(n.into())
}
fn r(n: i64, d: i64) -> Rational {
Rational::new(n.into(), d.into())
}
#[test]
fn maximizes_a_bounded_two_variable_program() {
let problem = LpProblem {
objective: vec![int(1), int(1), int(0), int(0)],
constraints: vec![
vec![int(1), int(1), int(1), int(0)],
vec![int(1), int(3), int(0), int(1)],
],
rhs: vec![int(4), int(6)],
};
match solve_lp(problem) {
LpSolution::Optimal { value, x } => {
assert_eq!(value, int(4));
assert_eq!(x.len(), 4);
assert_eq!(&x[0] + &x[1] + &x[2], int(4));
assert_eq!(&x[0] + int(3) * &x[1] + &x[3], int(6));
assert!(x.iter().all(|v| *v >= int(0)));
}
other => panic!("expected an optimum, got {other:?}"),
}
}
#[test]
fn reports_a_fractional_optimum_exactly() {
let problem = LpProblem {
objective: vec![int(1), int(0)],
constraints: vec![vec![int(3), int(1)]],
rhs: vec![int(1)],
};
match solve_lp(problem) {
LpSolution::Optimal { value, .. } => assert_eq!(value, r(1, 3)),
other => panic!("expected an optimum, got {other:?}"),
}
}
#[test]
fn reports_an_infeasible_program() {
let problem = LpProblem {
objective: vec![int(1), int(1)],
constraints: vec![vec![int(1), int(1)], vec![int(1), int(1)]],
rhs: vec![int(1), int(2)],
};
assert!(matches!(solve_lp(problem), LpSolution::Infeasible));
}
#[test]
fn reports_an_unbounded_program() {
let problem = LpProblem {
objective: vec![int(1), int(0)],
constraints: vec![vec![int(1), int(-1)]],
rhs: vec![int(1)],
};
assert!(matches!(solve_lp(problem), LpSolution::Unbounded));
}
#[test]
fn normalizes_a_negative_right_hand_side() {
let problem = LpProblem {
objective: vec![int(1), int(0)],
constraints: vec![vec![int(-1), int(-1)]],
rhs: vec![int(-2)],
};
match solve_lp(problem) {
LpSolution::Optimal { value, .. } => assert_eq!(value, int(2)),
other => panic!("expected an optimum, got {other:?}"),
}
}
#[test]
fn a_redundant_constraint_does_not_make_the_program_infeasible() {
let problem = LpProblem {
objective: vec![int(1), int(0)],
constraints: vec![vec![int(1), int(1)], vec![int(2), int(2)]],
rhs: vec![int(1), int(2)],
};
match solve_lp(problem) {
LpSolution::Optimal { value, .. } => assert_eq!(value, int(1)),
other => panic!("expected an optimum, got {other:?}"),
}
}
#[test]
fn a_degenerate_program_terminates() {
let problem = LpProblem {
objective: vec![int(1), int(1), int(0), int(0)],
constraints: vec![
vec![int(1), int(0), int(1), int(0)],
vec![int(0), int(1), int(0), int(1)],
],
rhs: vec![int(0), int(1)],
};
match solve_lp(problem) {
LpSolution::Optimal { value, x } => {
assert_eq!(value, int(1));
assert_eq!(x[0], int(0), "the degenerate variable stays at zero");
assert_eq!(x[1], int(1));
}
other => panic!("expected an optimum, got {other:?}"),
}
}
#[test]
fn solves_a_dominance_shaped_program() {
let problem = LpProblem {
objective: vec![int(0), int(0), int(1), int(0), int(0)],
constraints: vec![
vec![int(3), int(0), int(-1), int(-1), int(0)],
vec![int(0), int(3), int(-1), int(0), int(-1)],
vec![int(1), int(1), int(0), int(0), int(0)],
],
rhs: vec![int(1), int(1), int(1)],
};
match solve_lp(problem) {
LpSolution::Optimal { value, x } => {
assert_eq!(
value,
r(1, 2),
"the even mixture beats the candidate by 1/2"
);
assert_eq!(x[0], r(1, 2));
assert_eq!(x[1], r(1, 2));
}
other => panic!("expected an optimum, got {other:?}"),
}
}
#[test]
#[should_panic(expected = "constraint rows and right-hand sides must match")]
fn a_mismatched_right_hand_side_panics_naming_the_mismatch() {
let problem = LpProblem {
objective: vec![int(1)],
constraints: vec![vec![int(1)], vec![int(1)]],
rhs: vec![int(1)],
};
let _ = solve_lp(problem);
}
#[test]
#[should_panic(expected = "constraint matrix must be rectangular")]
fn a_ragged_constraint_matrix_panics() {
let problem = LpProblem {
objective: vec![int(1), int(1)],
constraints: vec![vec![int(1), int(1)], vec![int(1)]],
rhs: vec![int(1), int(1)],
};
let _ = solve_lp(problem);
}
#[test]
#[should_panic(expected = "objective length must match the column count")]
fn an_objective_of_the_wrong_length_panics() {
let problem = LpProblem {
objective: vec![int(1)],
constraints: vec![vec![int(1), int(1)]],
rhs: vec![int(1)],
};
let _ = solve_lp(problem);
}
}