pub type Constraint = ([f64; 3], f64);
pub const BIG: f64 = 1e8;
pub fn minimize(cons: &[Constraint], c: [f64; 3]) -> Option<[f64; 3]> {
SCRATCH.with_borrow_mut(|s| solve(3, cons, c, [(-BIG, BIG); 3], s))
}
thread_local! {
static SCRATCH: std::cell::RefCell<[Vec<Constraint>; 2]> = const {
std::cell::RefCell::new([Vec::new(), Vec::new()])
};
}
pub fn shuffle(cons: &mut [Constraint]) {
let mut s = 0x2545f4914f6cdd1du64;
for i in (1..cons.len()).rev() {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
cons.swap(i, (s % (i as u64 + 1)) as usize);
}
}
fn solve(
d: usize,
cons: &[Constraint],
c: [f64; 3],
bounds: [(f64, f64); 3],
scratch: &mut [Vec<Constraint>],
) -> Option<[f64; 3]> {
if d == 1 {
let (mut lo, mut hi) = bounds[0];
for &(a, b) in cons {
let a = a[0];
if a.abs() < 1e-14 {
if b < -1e-9 * (1.0 + b.abs()) {
return None;
}
} else if a > 0.0 {
hi = hi.min(b / a);
} else {
lo = lo.max(b / a);
}
}
if lo > hi + 1e-9 * (1.0 + lo.abs()) {
return None;
}
let x = if c[0] < 0.0 { hi } else { lo.min(hi) };
return Some([x, 0.0, 0.0]);
}
let mut x = [0.0; 3];
for k in 0..d {
x[k] = if c[k] < 0.0 { bounds[k].1 } else { bounds[k].0 };
}
for i in 0..cons.len() {
let (a, b) = cons[i];
let ax: f64 = (0..d).map(|k| a[k] * x[k]).sum();
let mag: f64 = (0..d).map(|k| (a[k] * x[k]).abs()).sum();
if ax <= b + 1e-9 * (1.0 + b.abs() + mag) {
continue;
}
let p = (0..d)
.max_by(|&i, &j| a[i].abs().total_cmp(&a[j].abs()))
.unwrap();
if a[p].abs() < 1e-12 {
if b < -1e-9 * (1.0 + b.abs()) {
return None;
}
continue;
}
let mut keep = [0; 2];
let mut r = [0.0; 2];
for (kk, k) in (0..d).filter(|&k| k != p).enumerate() {
keep[kk] = k;
r[kk] = a[k] / a[p];
}
let keep = &keep[..d - 1];
let x0 = b / a[p];
let (sub, deeper) = scratch[..d - 1].split_last_mut().unwrap();
sub.clear();
for &(aj, bj) in &cons[..i] {
let mut na = [0.0; 3];
for (kk, &k) in keep.iter().enumerate() {
na[kk] = aj[k] - aj[p] * r[kk];
}
sub.push((na, bj - aj[p] * x0));
}
let mut up = [0.0; 3];
let mut down = [0.0; 3];
for kk in 0..keep.len() {
up[kk] = -r[kk];
down[kk] = r[kk];
}
sub.push((up, bounds[p].1 - x0));
sub.push((down, x0 - bounds[p].0));
let mut nc = [0.0; 3];
let mut nb = [(0.0, 0.0); 3];
for (kk, &k) in keep.iter().enumerate() {
nc[kk] = c[k] - c[p] * r[kk];
nb[kk] = bounds[k];
}
let y = solve(d - 1, sub, nc, nb, deeper)?;
let mut xp = x0;
for (kk, &k) in keep.iter().enumerate() {
x[k] = y[kk];
xp -= r[kk] * y[kk];
}
x[p] = xp;
}
Some(x)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn rotated_cube() {
let s = 2f64.sqrt();
let mut cons = vec![
([1.0, 1.0, 0.0], s),
([-1.0, -1.0, 0.0], s),
([1.0, -1.0, 0.0], s),
([-1.0, 1.0, 0.0], s),
([0.0, 0.0, 1.0], 1.0),
([0.0, 0.0, -1.0], 1.0),
];
shuffle(&mut cons);
let x = minimize(&cons, [1.0, 0.0, 0.0]).unwrap();
assert!((x[0] + s).abs() < 1e-9, "{x:?}");
let x = minimize(&cons, [0.0, -1.0, 0.0]).unwrap();
assert!((x[1] - s).abs() < 1e-9, "{x:?}");
let x = minimize(&cons, [0.0, 0.0, -1.0]).unwrap();
assert!((x[2] - 1.0).abs() < 1e-9);
}
#[test]
fn infeasible_and_unbounded() {
let cons = vec![([1.0, 0.0, 0.0], -1.0), ([-1.0, 0.0, 0.0], -1.0)];
assert!(minimize(&cons, [1.0, 0.0, 0.0]).is_none());
let cons = vec![([1.0, 1.0, 1.0], 1.0)];
let x = minimize(&cons, [1.0, 0.0, 0.0]).unwrap();
assert!(x[0] <= -BIG * 0.99);
}
}