Math.Programming

A library for modeling and solving linear and integer programs.

This library is merely a frontend to various solver backends. At the time this was written, the only known supported backend is GLPK.

Math programs

The LPMonad provides all the primitives necessary to formulate and solve linear programs; the IPMonad provides the same for integer programs. However, you should not often need to use these APIs directly, as we provide more user-friendly functions wrapping these low-level functions below.

Linear programs

class (Monad m, Num (Numeric m)) => LPMonad m where

A monad for formulating and solving linear programs.

We manipulate linear programs and their settings using the Mutable typeclass.

Associated Types

type Numeric m :: *

The numeric type used in the model.

data Variable m :: *

The type of variables in the model. LPMonad treats these as opaque values, but instances may expose more details.

data Constraint m :: *

The type of constraints in the model. LPMonad treats these as opaque values, but instances may expose more details.

data Objective m :: *

The type of objectives in the model. LPMonad treats these as opaque values, but instances may expose more details.

Methods

addVariable :: m (Variable m)

Create a new decision variable in the model.

This variable will be initialized to be a non-negative continuous variable.

removeVariable :: Variable m -> m ()

Remove a decision variable from the model.

The variable cannot be used after being deleted.

getVariableName :: Variable m -> m String

Get the name of the variable.

setVariableName :: Variable m -> String -> m ()

Set the name of the variable.

getVariableBounds :: Variable m -> m (Bounds (Numeric m))

Get the allowed values of a variable.

setVariableBounds :: Variable m -> Bounds (Numeric m) -> m ()

Constrain a variable to take on certain values.

getVariableValue :: Variable m -> m (Numeric m)

Get the value of a variable in the current solution.

addConstraint :: Inequality (LinearExpression (Numeric m) (Variable m)) -> m (Constraint m)

Add a constraint to the model represented by an inequality.

removeConstraint :: Constraint m -> m ()

Remove a constraint from the model.

The constraint cannot used after being deleted.

getConstraintName :: Constraint m -> m String

Get the name of the constraint.

setConstraintName :: Constraint m -> String -> m ()

Set the name of the constraint.

getDualValue :: Constraint m -> m (Numeric m)

Get the value of the dual variable associated with the constraint in the current solution.

This value has no meaning if the current solution is not an LP solution.

addObjective :: LinearExpression (Numeric m) (Variable m) -> m (Objective m)

Add a constraint to the model represented by an inequality.

getObjectiveName :: Objective m -> m String

Get the name of the objective.

setObjectiveName :: Objective m -> String -> m ()

Set the name of the objective.

getObjectiveSense :: Objective m -> m Sense

Whether the objective is to be minimized or maximized.

setObjectiveSense :: Objective m -> Sense -> m ()

Set whether the objective is to be minimized or maximized.

getObjectiveValue :: Objective m -> m (Numeric m)

Get the value of the objective in the current solution.

getTimeout :: m Double

Get the number of seconds the solver is allowed to run before halting.

setTimeout :: Double -> m ()

Set the number of seconds the solver is allowed to run before halting.

optimizeLP :: m SolutionStatus

Optimize the continuous relaxation of the model.

writeFormulation :: FilePath -> m ()

Write out the formulation.

type Expr m = LinearExpression (Numeric m) (Variable m)

A convient shorthand for the type of linear expressions used in a given model.

data Bounds b

An interval of the real numbers.

Constructors

NonNegativeReals

The non-negative reals.

NonPositiveReals

The non-positive reals.

Interval b b

Any closed interval of the reals.

Free

Any real number.

Instances

Read b => Read (Bounds b)

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS (Bounds b)

readList :: ReadS [Bounds b]

readPrec :: ReadPrec (Bounds b)

readListPrec :: ReadPrec [Bounds b]

Show b => Show (Bounds b)

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> Bounds b -> ShowS

show :: Bounds b -> String

showList :: [Bounds b] -> ShowS

data SolutionStatus

The outcome of an optimization.

Constructors

Optimal

An optimal solution has been found.

Feasible

A feasible solution has been found. The result may or may not be optimal.

Infeasible

The model has been proven to be infeasible.

Unbounded

The model has been proven to be unbounded.

Error

An error was encountered during the solve. Instance-specific methods should be used to determine what occurred.

Instances

Eq SolutionStatus

Defined in Math.Programming.Types

Methods

(==) :: SolutionStatus -> SolutionStatus -> Bool

(/=) :: SolutionStatus -> SolutionStatus -> Bool

Ord SolutionStatus

Defined in Math.Programming.Types

Methods

compare :: SolutionStatus -> SolutionStatus -> Ordering

(<) :: SolutionStatus -> SolutionStatus -> Bool

(<=) :: SolutionStatus -> SolutionStatus -> Bool

(>) :: SolutionStatus -> SolutionStatus -> Bool

(>=) :: SolutionStatus -> SolutionStatus -> Bool

max :: SolutionStatus -> SolutionStatus -> SolutionStatus

min :: SolutionStatus -> SolutionStatus -> SolutionStatus

Read SolutionStatus

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS SolutionStatus

readList :: ReadS [SolutionStatus]

readPrec :: ReadPrec SolutionStatus

readListPrec :: ReadPrec [SolutionStatus]

Show SolutionStatus

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> SolutionStatus -> ShowS

show :: SolutionStatus -> String

showList :: [SolutionStatus] -> ShowS

data Sense

Whether a math program is minimizing or maximizing its objective.

Constructors

Minimization

Maximization

Instances

Eq Sense

Defined in Math.Programming.Types

Methods

(==) :: Sense -> Sense -> Bool

(/=) :: Sense -> Sense -> Bool

Ord Sense

Defined in Math.Programming.Types

Methods

compare :: Sense -> Sense -> Ordering

(<) :: Sense -> Sense -> Bool

(<=) :: Sense -> Sense -> Bool

(>) :: Sense -> Sense -> Bool

(>=) :: Sense -> Sense -> Bool

max :: Sense -> Sense -> Sense

min :: Sense -> Sense -> Sense

Read Sense

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS Sense

readList :: ReadS [Sense]

readPrec :: ReadPrec Sense

readListPrec :: ReadPrec [Sense]

Show Sense

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> Sense -> ShowS

show :: Sense -> String

showList :: [Sense] -> ShowS

Integer programs

class LPMonad m => IPMonad m where

A (mixed) integer program.

In addition to the methods of the LPMonad class, this monad supports constraining variables to be either continuous or discrete.

Methods

optimizeIP :: m SolutionStatus

Optimize the mixed-integer program.

getVariableDomain :: Variable m -> m Domain

Get the domain of a variable.

setVariableDomain :: Variable m -> Domain -> m ()

Set the domain of a variable.

getRelativeMIPGap :: m Double

Get the allowed relative gap between LP and IP solutions.

setRelativeMIPGap :: Double -> m ()

Set the allowed relative gap between LP and IP solutions.

data Domain

The type of values that a variable can take on.

Note that the Integer constructor does not interfere with the Integer type, as the Integer type does not define a constuctor of the same name. The ambiguity is unfortunate, but other natural nomenclature such as Integral are similarly conflicted.

Constructors

Continuous

The variable lies in the real numbers

Integer

The variable lies in the integers

Binary

The variable lies in the set {0, 1}.

Instances

Read Domain

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS Domain

readList :: ReadS [Domain]

readPrec :: ReadPrec Domain

readListPrec :: ReadPrec [Domain]

Show Domain

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> Domain -> ShowS

show :: Domain -> String

showList :: [Domain] -> ShowS

Model-building DSL

The functions in the LPMonad and IPMonad typeclasses are designed to interface with low-level solver backends. We provide a cleaner interface in the following sections.

Creating variables

LPMonad provides addVariable and setVariableBounds, and IPMonad additionally provides setVariableDomain. While sufficient to create your programs, you are encouraged to use the more natural functions below.

Continuous variables

free :: LPMonad m => m (Variable m)

Create a new free variable.

nonNeg :: LPMonad m => m (Variable m)

Create a new non-negative variable.

nonPos :: LPMonad m => m (Variable m)

Create a new non-positive variable.

bounded :: LPMonad m => Numeric m -> Numeric m -> m (Variable m)

Create a new variable bounded between two values.

within :: LPMonad m => m (Variable m) -> Bounds (Numeric m) -> m (Variable m)

Constrain a variable to take on certain values.

This function is designed to be used as an infix operator, e.g.

addVariable `within` NonNegativeReals

Integer variables

integer :: IPMonad m => m (Variable m)

Create an integer-valued variable.

binary :: IPMonad m => m (Variable m)

Create a binary variable.

nonNegInteger :: IPMonad m => m (Variable m)

Create an integer-value variable that takes on non-negative values.

nonPosInteger :: IPMonad m => m (Variable m)

Create an integer-value variable that takes on non-positive values.

asKind :: IPMonad m => m (Variable m) -> Domain -> m (Variable m)

Set the type of a variable.

This function is designed to be used as an infix operator, e.g.

addVariable `asKind` Binary

Linear expressions

The module LinearExpression provides operators to build up LinearExpression objects using declared variables.

data LinearExpression a b

A linear expression containing symbolic variables of type b and numeric coefficients of type a.

Using Strings to denote variables and Doubles as our numeric type, we could express 3 x + 2 y + 1 as

  LinearExpression [(3, "x"), (2, "y")] 1

Constructors

LinearExpression [(a, b)] a

Instances

Bifunctor LinearExpression

Defined in Math.Programming.Types

Methods

bimap :: (a -> b) -> (c -> d) -> LinearExpression a c -> LinearExpression b d

first :: (a -> b) -> LinearExpression a c -> LinearExpression b c

second :: (b -> c) -> LinearExpression a b -> LinearExpression a c

Functor (LinearExpression a)

Defined in Math.Programming.Types

Methods

fmap :: (a0 -> b) -> LinearExpression a a0 -> LinearExpression a b

(<$) :: a0 -> LinearExpression a b -> LinearExpression a a0

Foldable (LinearExpression a)

Defined in Math.Programming.Types

Methods

fold :: Monoid m => LinearExpression a m -> m

foldMap :: Monoid m => (a0 -> m) -> LinearExpression a a0 -> m

foldr :: (a0 -> b -> b) -> b -> LinearExpression a a0 -> b

foldr' :: (a0 -> b -> b) -> b -> LinearExpression a a0 -> b

foldl :: (b -> a0 -> b) -> b -> LinearExpression a a0 -> b

foldl' :: (b -> a0 -> b) -> b -> LinearExpression a a0 -> b

foldr1 :: (a0 -> a0 -> a0) -> LinearExpression a a0 -> a0

foldl1 :: (a0 -> a0 -> a0) -> LinearExpression a a0 -> a0

toList :: LinearExpression a a0 -> [a0]

null :: LinearExpression a a0 -> Bool

length :: LinearExpression a a0 -> Int

elem :: Eq a0 => a0 -> LinearExpression a a0 -> Bool

maximum :: Ord a0 => LinearExpression a a0 -> a0

minimum :: Ord a0 => LinearExpression a a0 -> a0

sum :: Num a0 => LinearExpression a a0 -> a0

product :: Num a0 => LinearExpression a a0 -> a0

Traversable (LinearExpression a)

Useful for substituting values in a monadic/applicative context

Defined in Math.Programming.Types

Methods

traverse :: Applicative f => (a0 -> f b) -> LinearExpression a a0 -> f (LinearExpression a b)

sequenceA :: Applicative f => LinearExpression a (f a0) -> f (LinearExpression a a0)

mapM :: Monad m => (a0 -> m b) -> LinearExpression a a0 -> m (LinearExpression a b)

sequence :: Monad m => LinearExpression a (m a0) -> m (LinearExpression a a0)

(Read a, Read b) => Read (LinearExpression a b)

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS (LinearExpression a b)

readList :: ReadS [LinearExpression a b]

readPrec :: ReadPrec (LinearExpression a b)

readListPrec :: ReadPrec [LinearExpression a b]

(Show a, Show b) => Show (LinearExpression a b)

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> LinearExpression a b -> ShowS

show :: LinearExpression a b -> String

showList :: [LinearExpression a b] -> ShowS

Num a => Semigroup (LinearExpression a b)

Implements addition of 'LinearExpression a b' terms

Defined in Math.Programming.Types

Methods

(<>) :: LinearExpression a b -> LinearExpression a b -> LinearExpression a b

sconcat :: NonEmpty (LinearExpression a b) -> LinearExpression a b

stimes :: Integral b0 => b0 -> LinearExpression a b -> LinearExpression a b

Num a => Monoid (LinearExpression a b)

Using '0' as the identity element

Defined in Math.Programming.Types

Methods

mempty :: LinearExpression a b

mappend :: LinearExpression a b -> LinearExpression a b -> LinearExpression a b

mconcat :: [LinearExpression a b] -> LinearExpression a b

eval :: Num a => LinearExpression a a -> a

Reduce an expression to its value.

simplify :: (Ord b, Num a) => LinearExpression a b -> LinearExpression a b

Combine equivalent terms by summing their coefficients.

var :: Num a => b -> LinearExpression a b

Construct an expression representing a variable.

con :: Num a => a -> LinearExpression a b

Construct an expression representing a constant.

exprSum :: Num a => [LinearExpression a b] -> LinearExpression a b

Construct an expression by summing expressions.

varSum :: Num a => [b] -> LinearExpression a b

Construct an expression by summing variables.

Addition

We can summarize the addition operators with the table

	Constant	Variable	Expression
Constant	+	#+@	#+.
Variable	@+#	@+@	@+.
Expression	.+#	.+@	.+.

(.+.) :: Num a => LinearExpression a b -> LinearExpression a b -> LinearExpression a b infixl 6

(@+@) :: Num a => b -> b -> LinearExpression a b infixl 6

(.+@) :: Num a => LinearExpression a b -> b -> LinearExpression a b infixl 6

(@+.) :: Num a => b -> LinearExpression a b -> LinearExpression a b infixl 6

(@+#) :: Num a => b -> a -> LinearExpression a b infixl 6

(#+@) :: Num a => a -> b -> LinearExpression a b infixl 6

(#+.) :: Num a => a -> LinearExpression a b -> LinearExpression a b infixl 6

(.+#) :: Num a => LinearExpression a b -> a -> LinearExpression a b infixl 6

Subtraction

We can summarize the subtraction operators with the table

	Constant	Variable	Expression
Constant	-	#-@	#-.
Variable	@-#	@-@	@-.
Expression	.-#	.-@	.-.

(.-.) :: Num a => LinearExpression a b -> LinearExpression a b -> LinearExpression a b infixl 6

(@-@) :: Num a => b -> b -> LinearExpression a b infixl 6

(.-@) :: Num a => LinearExpression a b -> b -> LinearExpression a b infixl 6

(@-.) :: Num a => b -> LinearExpression a b -> LinearExpression a b infixl 6

(@-#) :: Num a => b -> a -> LinearExpression a b infixl 6

(#-@) :: Num a => a -> b -> LinearExpression a b infixl 6

(#-.) :: Num a => a -> LinearExpression a b -> LinearExpression a b infixl 6

(.-#) :: Num a => LinearExpression a b -> a -> LinearExpression a b infixl 6

Multiplication

We can summarize the multiplication operators with the table

	Constant	Variable	Expression
Constant	*	#*@	#*.
Variable	@*#
Expression	.*#

As there are few possibilities for valid multiplication, it can be convenient to define e.g. .* or some other short operator as an alias for #*@.

(#*@) :: Num a => a -> b -> LinearExpression a b infixl 7

(@*#) :: Num a => b -> a -> LinearExpression a b infixl 7

(#*.) :: Num a => a -> LinearExpression a b -> LinearExpression a b infixl 7

(.*#) :: Num a => LinearExpression a b -> a -> LinearExpression a b infixl 7

Division

We can summarize the multiplication operators with the table

	Constant	Variable	Expression
Constant	/
Variable	@/#
Expression	./#

As there are few possibilities for valid division, it can be convenient to define e.g. ./ or some other short operator as an alias for @/#.

(@/#) :: Fractional a => b -> a -> LinearExpression a b infixl 7

(./#) :: Fractional a => LinearExpression a b -> a -> LinearExpression a b infixl 7

Constraints

The LPMonad provides the addConstraint function. However, you will typically use the operators below to directly apply constraints to the model. We follow the same conventions as with our arithmetic operators.

data Inequality a

Non-strict inequalities.

Constructors

Inequality Ordering a a

Instances

Functor Inequality

Defined in Math.Programming.Types

Methods

fmap :: (a -> b) -> Inequality a -> Inequality b

(<$) :: a -> Inequality b -> Inequality a

Foldable Inequality

Defined in Math.Programming.Types

Methods

fold :: Monoid m => Inequality m -> m

foldMap :: Monoid m => (a -> m) -> Inequality a -> m

foldr :: (a -> b -> b) -> b -> Inequality a -> b

foldr' :: (a -> b -> b) -> b -> Inequality a -> b

foldl :: (b -> a -> b) -> b -> Inequality a -> b

foldl' :: (b -> a -> b) -> b -> Inequality a -> b

foldr1 :: (a -> a -> a) -> Inequality a -> a

foldl1 :: (a -> a -> a) -> Inequality a -> a

toList :: Inequality a -> [a]

null :: Inequality a -> Bool

length :: Inequality a -> Int

elem :: Eq a => a -> Inequality a -> Bool

maximum :: Ord a => Inequality a -> a

minimum :: Ord a => Inequality a -> a

sum :: Num a => Inequality a -> a

product :: Num a => Inequality a -> a

Traversable Inequality

Defined in Math.Programming.Types

Methods

traverse :: Applicative f => (a -> f b) -> Inequality a -> f (Inequality b)

sequenceA :: Applicative f => Inequality (f a) -> f (Inequality a)

mapM :: Monad m => (a -> m b) -> Inequality a -> m (Inequality b)

sequence :: Monad m => Inequality (m a) -> m (Inequality a)

Read a => Read (Inequality a)

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS (Inequality a)

readList :: ReadS [Inequality a]

readPrec :: ReadPrec (Inequality a)

readListPrec :: ReadPrec [Inequality a]

Show a => Show (Inequality a)

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> Inequality a -> ShowS

show :: Inequality a -> String

showList :: [Inequality a] -> ShowS

Less-than constraints

We can summarize the various inquality operators in the following table.

	Constant	Variable	Expression
Constant		#<=@	#<=.
Variable	@<=#	@<=@	@<=.
Expression	.<=#	.<=@	.<=.

(#<=@) :: LPMonad m => Numeric m -> Variable m -> m (Constraint m) infix 4

(#<=.) :: LPMonad m => Numeric m -> Expr m -> m (Constraint m) infix 4

(@<=#) :: LPMonad m => Variable m -> Numeric m -> m (Constraint m) infix 4

(@<=@) :: LPMonad m => Variable m -> Variable m -> m (Constraint m) infix 4

(@<=.) :: LPMonad m => Variable m -> Expr m -> m (Constraint m) infix 4

(.<=#) :: LPMonad m => Expr m -> Numeric m -> m (Constraint m) infix 4

(.<=@) :: LPMonad m => Expr m -> Variable m -> m (Constraint m) infix 4

(.<=.) :: LPMonad m => Expr m -> Expr m -> m (Constraint m) infix 4

Greater-than constraints

We can summarize the various inquality operators in the following table.

	Constant	Variable	Expression
Constant		#>=@	#>=.
Variable	@>=#	@>=@	@>=.
Expression	.>=#	.>=@	.>=.

(#>=@) :: LPMonad m => Numeric m -> Variable m -> m (Constraint m) infix 4

(#>=.) :: LPMonad m => Numeric m -> Expr m -> m (Constraint m) infix 4

(@>=#) :: LPMonad m => Variable m -> Numeric m -> m (Constraint m) infix 4

(@>=@) :: LPMonad m => Variable m -> Variable m -> m (Constraint m) infix 4

(@>=.) :: LPMonad m => Variable m -> Expr m -> m (Constraint m) infix 4

(.>=#) :: LPMonad m => Expr m -> Numeric m -> m (Constraint m) infix 4

(.>=@) :: LPMonad m => Expr m -> Variable m -> m (Constraint m) infix 4

(.>=.) :: LPMonad m => Expr m -> Expr m -> m (Constraint m) infix 4

Equality constraints

We can summarize the various inquality operators in the following table.

	Constant	Variable	Expression
Constant		#==@	#==.
Variable	@==#	@==@	@==.
Expression	.==#	.==@	.==.

(#==@) :: LPMonad m => Numeric m -> Variable m -> m (Constraint m) infix 4

(#==.) :: LPMonad m => Numeric m -> Expr m -> m (Constraint m) infix 4

(@==#) :: LPMonad m => Variable m -> Numeric m -> m (Constraint m) infix 4

(@==@) :: LPMonad m => Variable m -> Variable m -> m (Constraint m) infix 4

(@==.) :: LPMonad m => Variable m -> Expr m -> m (Constraint m) infix 4

(.==#) :: LPMonad m => Expr m -> Numeric m -> m (Constraint m) infix 4

(.==@) :: LPMonad m => Expr m -> Variable m -> m (Constraint m) infix 4

(.==.) :: LPMonad m => Expr m -> Expr m -> m (Constraint m) infix 4

Specifying objectives

minimize :: LPMonad m => Expr m -> m (Objective m)

Create an objective to be minimized.

maximize :: LPMonad m => Expr m -> m (Objective m)

Create an objective to be maximized.

Utilities

evalExpr :: LPMonad m => Expr m -> m (Numeric m)

Get the value of a linear expression in the current solution.

named :: (Monad m, Nameable m a) => m a -> String -> m a

Name a variable, constraint, or objective.

This function is designed to be used as an infix operator, e.g.

free `named` X_1

nameOf :: (Monad m, Nameable m a) => a -> m String

Retrieve the name of a variable, constraint, or objective.