ToySolver.Arith.FourierMotzkin.Optimization

Naïve implementation of Fourier-Motzkin Variable Elimination

Reference:

• http://users.cecs.anu.edu.au/~michaeln/pubs/arithmetic-dps.pdf

Documentation

optimize :: VarSet -> OptDir -> Expr Rational -> [Atom Rational] -> (Interval Rational, Rational -> Model Rational)

optimize dir obj φ returns (I, lift) where

• I is convex hull of feasible region, and
• lift is a function, that takes x ∈ I and returns the feasible solution with objective value better than or equal to x.

Note:

• lowerBound i (resp. upperBound i) is the optimal value in case of minimization (resp. maximization).
• If I is empty, then the problem is INFEASIBLE.