toysolver-0.3.0: Assorted decision procedures for SAT, Max-SAT, PB, MIP, etc

Copyright(c) Masahiro Sakai 2014-2015
LicenseBSD-style
Maintainermasahiro.sakai@gmail.com
Stabilityprovisional
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

ToySolver.Arith.FourierMotzkin.Optimization

Description

Naïve implementation of Fourier-Motzkin Variable Elimination

Reference:

Synopsis

Documentation

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

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.