use num_rational::BigRational;
use num_traits::{Signed, Zero};
pub fn is_feasible(rows: &[Vec<BigRational>], rhs: &[BigRational]) -> bool {
rows.is_empty() || phase_one(rows, rhs, rows[0].len()).is_some()
}
struct Tableau {
lines: Vec<Vec<BigRational>>,
values: Vec<BigRational>,
basis: Vec<usize>,
}
fn phase_one(rows: &[Vec<BigRational>], rhs: &[BigRational], variables: usize) -> Option<Tableau> {
let m = rows.len();
let mut lines: Vec<Vec<BigRational>> = Vec::with_capacity(m);
let mut values: Vec<BigRational> = Vec::with_capacity(m);
for (i, (row, b)) in rows.iter().zip(rhs).enumerate() {
let flip = b.is_negative();
let mut line: Vec<BigRational> = row
.iter()
.map(|a| if flip { -a.clone() } else { a.clone() })
.collect();
line.extend((0..m).map(|k| if k == i { one() } else { BigRational::zero() }));
lines.push(line);
values.push(if flip { -b.clone() } else { b.clone() });
}
let columns = variables + m;
let mut basis: Vec<usize> = (variables..columns).collect();
let mut reduced: Vec<BigRational> = (0..columns)
.map(|j| {
if j >= variables {
BigRational::zero()
} else {
-lines
.iter()
.map(|line| line[j].clone())
.fold(BigRational::zero(), |acc, a| acc + a)
}
})
.collect();
let mut infeasibility: BigRational = values.iter().fold(BigRational::zero(), |acc, b| acc + b);
while let Some(entering) = (0..columns).find(|&j| reduced[j].is_negative()) {
let row = ratio_test(&lines, &values, &basis, entering).expect("第 1 段階の LP は有界");
pivot(&mut lines, &mut values, row, entering);
let factor = reduced[entering].clone();
for (d, a) in reduced.iter_mut().zip(&lines[row]) {
*d -= &factor * a;
}
infeasibility += &factor * &values[row];
basis[row] = entering;
}
if !infeasibility.is_zero() {
return None;
}
for row in 0..m {
if basis[row] >= variables
&& let Some(column) = (0..variables).find(|&j| !lines[row][j].is_zero())
{
pivot(&mut lines, &mut values, row, column);
basis[row] = column;
}
}
Some(Tableau {
lines,
values,
basis,
})
}
#[derive(Clone, Debug, PartialEq)]
pub enum Outcome {
Optimal {
value: BigRational,
solution: Vec<BigRational>,
},
Infeasible,
Unbounded,
}
pub fn minimize(rows: &[Vec<BigRational>], rhs: &[BigRational], cost: &[BigRational]) -> Outcome {
let variables = cost.len();
let m = rows.len();
let Some(Tableau {
lines: mut tableau,
mut values,
mut basis,
}) = phase_one(rows, rhs, variables)
else {
return Outcome::Infeasible;
};
let columns = variables + m;
let basic_cost = |i: usize| -> BigRational {
if basis[i] < variables {
cost[basis[i]].clone()
} else {
BigRational::zero()
}
};
let mut reduced: Vec<BigRational> = (0..columns)
.map(|j| {
let c = if j < variables {
cost[j].clone()
} else {
BigRational::zero()
};
(0..m).fold(c, |acc, i| acc - basic_cost(i) * &tableau[i][j])
})
.collect();
while let Some(entering) = (0..variables).find(|&j| reduced[j].is_negative()) {
let Some(row) = ratio_test(&tableau, &values, &basis, entering) else {
return Outcome::Unbounded;
};
pivot(&mut tableau, &mut values, row, entering);
let factor = reduced[entering].clone();
for (d, a) in reduced.iter_mut().zip(&tableau[row]) {
*d -= &factor * a;
}
basis[row] = entering;
}
let mut solution = vec![BigRational::zero(); variables];
for (i, &b) in basis.iter().enumerate() {
if b < variables {
solution[b] = values[i].clone();
}
}
let value = solution
.iter()
.zip(cost)
.fold(BigRational::zero(), |acc, (z, c)| acc + z * c);
Outcome::Optimal { value, solution }
}
fn ratio_test(
tableau: &[Vec<BigRational>],
values: &[BigRational],
basis: &[usize],
entering: usize,
) -> Option<usize> {
let mut leaving: Option<(usize, BigRational)> = None;
for (i, line) in tableau.iter().enumerate() {
if line[entering].is_positive() {
let ratio = &values[i] / &line[entering];
let better = match &leaving {
None => true,
Some((r, best)) => ratio < *best || (ratio == *best && basis[i] < basis[*r]),
};
if better {
leaving = Some((i, ratio));
}
}
}
leaving.map(|(row, _)| row)
}
fn one() -> BigRational {
BigRational::from_integer(1.into())
}
fn pivot(tableau: &mut [Vec<BigRational>], values: &mut [BigRational], row: usize, column: usize) {
let scale = tableau[row][column].clone();
for a in tableau[row].iter_mut() {
*a /= &scale;
}
values[row] /= &scale;
let pivot_row = tableau[row].clone();
let pivot_value = values[row].clone();
for (i, line) in tableau.iter_mut().enumerate() {
if i == row || line[column].is_zero() {
continue;
}
let factor = line[column].clone();
for (a, p) in line.iter_mut().zip(&pivot_row) {
*a -= &factor * p;
}
values[i] -= &factor * &pivot_value;
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::rng::SplitMix64;
use microlp::{ComparisonOp, OptimizationDirection, Problem};
fn r(n: i64) -> BigRational {
BigRational::from_integer(n.into())
}
#[test]
fn minimizes_small_programs() {
let rows = vec![vec![r(1), r(2), r(1), r(0)], vec![r(3), r(1), r(0), r(1)]];
match minimize(&rows, &[r(4), r(6)], &[r(-1), r(-1), r(0), r(0)]) {
Outcome::Optimal { value, solution } => {
let q = |a: i64, b: i64| BigRational::new(a.into(), b.into());
assert_eq!(value, q(-14, 5));
assert_eq!(solution[..2], [q(8, 5), q(6, 5)]);
}
other => panic!("{other:?}"),
}
assert_eq!(
minimize(&[vec![r(1), r(-1)]], &[r(1)], &[r(-1), r(0)]),
Outcome::Unbounded
);
assert_eq!(
minimize(&[vec![r(1), r(1)]], &[r(-1)], &[r(1), r(1)]),
Outcome::Infeasible
);
match minimize(
&[vec![r(1), r(1)], vec![r(2), r(2)]],
&[r(2), r(4)],
&[r(1), r(0)],
) {
Outcome::Optimal { value, .. } => assert_eq!(value, r(0)),
other => panic!("{other:?}"),
}
}
#[test]
fn feasible_and_infeasible_systems() {
assert!(is_feasible(
&[vec![r(1), r(1)], vec![r(1), r(-1)]],
&[r(1), r(0)]
));
assert!(!is_feasible(&[vec![r(1), r(1)]], &[r(-1)]));
assert!(!is_feasible(
&[vec![r(1), r(-1)], vec![r(1), r(1)]],
&[r(3), r(1)]
));
}
#[test]
fn agrees_with_floating_lp() {
let mut rng = SplitMix64::new(42);
let mut feasible = 0;
for case in 0..300 {
let rows = 2 + (rng.next_u64() % 4) as usize;
let columns = 3 + (rng.next_u64() % 6) as usize;
let a: Vec<Vec<i64>> = (0..rows)
.map(|_| (0..columns).map(|_| rng.range(0, 6) as i64 - 3).collect())
.collect();
let b: Vec<i64> = (0..rows).map(|_| rng.range(0, 10) as i64 - 5).collect();
let exact_answer = is_feasible(
&a.iter()
.map(|row| row.iter().map(|v| r(*v)).collect())
.collect::<Vec<_>>(),
&b.iter().map(|v| r(*v)).collect::<Vec<_>>(),
);
let mut problem = Problem::new(OptimizationDirection::Minimize);
let z: Vec<_> = (0..columns)
.map(|_| problem.add_var(0.0, (0.0, f64::INFINITY)))
.collect();
for (row, rhs) in a.iter().zip(&b) {
let terms: Vec<_> = z
.iter()
.zip(row)
.map(|(&var, &coef)| (var, coef as f64))
.collect();
problem.add_constraint(terms, ComparisonOp::Eq, *rhs as f64);
}
let float_answer = problem.solve().is_ok();
assert_eq!(
exact_answer, float_answer,
"case {case}: A = {a:?}, b = {b:?}"
);
feasible += usize::from(exact_answer);
}
assert!(feasible > 30 && feasible < 270, "feasible = {feasible}");
}
}