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.

This page includes a high-level overview of the model building DSL, as well as a deeper dive into the core monadic interface.

Model-building DSL

We provide a monadic DSL for specifying math programs. This DSL builds up programs statefully, rather than building some pure, abstract representation of a math program.

Creating variables

Continuous variables

free :: MonadLP v c o m => m v

Create a new free variable.

bounded :: MonadLP v c o m => Double -> Double -> m v

Create a new variable bounded between two values.

nonNeg :: MonadLP v c o m => m v

Create a new non-negative variable.

nonPos :: MonadLP v c o m => m v

Create a new non-positive variable.

Discrete variables

integer :: MonadIP v c o m => m v

Create an integer-valued variable.

binary :: MonadIP v c o m => m v

Create a binary variable.

nonNegInteger :: MonadIP v c o m => m v

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

nonPosInteger :: MonadIP v c o m => m v

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

Modifying variables

Regardless of the helper functions used above to create a variable, you can modify its behavior using the following modifiers.

within :: MonadLP v c o m => m v -> Bounds -> m v

Constrain a variable to take on certain values.

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

integer `within` 'Interval 3 7'

creates an integer variable that can take on values 3, 4, 5, 6, or 7.

asKind :: MonadIP v c o m => m v -> Domain -> m v

Set the type of a variable.

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

free `asKind` Binary

Creating constraints

An Inequality a is an inequality over the type a, which in turn is typically an Expr v for some variable type v. Despite the name, Inequality can also represent equality constraints directly.

As an alternative to constructing an inequality and passing it to addConstraint, we can use the convenience operators below. Since linear programming constraints often involve constant bounds, we offer operators specialized for both expressions and constants. The mnemonic is that . characters point to expressions

Equality constraints

(.==.) :: MonadLP v c o m => Expr v -> Expr v -> m c infix 4

An equality constraint

(==.) :: MonadLP v c o m => Double -> Expr v -> m c infix 4

An equality constraint with a numeric left-hand side

(.==) :: MonadLP v c o m => Expr v -> Double -> m c infix 4

An equality constraint with a numeric right-hand side

Less-than constraints

(.<=.) :: MonadLP v c o m => Expr v -> Expr v -> m c infix 4

A less-than or equal-to constraint

(<=.) :: MonadLP v c o m => Double -> Expr v -> m c infix 4

A less-than or equal-to constraint with a numeric left-hand side

(.<=) :: MonadLP v c o m => Expr v -> Double -> m c infix 4

A less-than or equal-to constraint with a numeric right-hand side

Greater-than constraints

(.>=.) :: MonadLP v c o m => Expr v -> Expr v -> m c infix 4

A greater-than or equal-to constraint

(>=.) :: MonadLP v c o m => Double -> Expr v -> m c infix 4

A greater-than or equal-to constraint with a numeric left-hand side

(.>=) :: MonadLP v c o m => Expr v -> Double -> m c infix 4

A greater-than or equal-to constraint with a numeric right-hand side

Creating objectives

minimize :: MonadLP v c o m => Expr v -> m o

Create an objective to be minimized.

maximize :: MonadLP v c o m => Expr v -> m o

Create an objective to be maximized.

Creating linear expressions

A LinExpr a b is a linear expression over variables of type b with coefficients of type a (typically Double.) We provide a number of operators to build up linear expressions naturally. The mnemonic is that . characters point to expressions.

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

A linear expression with a single variable term.

con :: a -> LinExpr a b

A linear expression with only a constant term.

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

Construct a term in a linear expression by multiplying a variable by a constant.

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

Construct a term in a linear expression by multiplying a constant by a variable.

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

Addition of linear expressions.

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

The difference of linear expressions.

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

Construct a term in a linear expression by dividing a variable by a constant.

eval :: Num a => LinExpr a a -> a

Reduce an expression to its value.

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

Simplify an expression by grouping like terms.

vsum :: Num a => [b] -> LinExpr a b

The sum of variable terms with coefficients of unity.

esum :: Num a => Foldable t => t (LinExpr a b) -> LinExpr a b

The sum of linear expressions.

scale :: Num a => a -> LinExpr a b -> LinExpr a b

Multiplication of linear expressions by a constant.

Math programs

The MonadLP and MonadIP classes provide low-level APIs for defining linear and integer programs, respectively, although the high-level DSL will typically be easier to work with.

Linear programs

class Monad m => MonadLP v c o m | m -> v c o where

A linear program.

This is a monadic context for formulating and solving linear programs. The types v, c, and o refer to the types of variables, constraints, and objectives, respectively, used by a particular solver backend.

Methods

addVariable :: m v

Add a new (free) variable to the model.

See free, bounded, nonNeg, and nonPos as higher-level alternatives.

deleteVariable :: v -> m ()

Remove a variable from the model.

getVariableName :: v -> m Text

Get the name of a variable.

setVariableName :: v -> Text -> m ()

Set a name for a variable.

getVariableBounds :: v -> m Bounds

Retrieve the current bounds associated with a variable.

setVariableBounds :: v -> Bounds -> m ()

Apply bounds to a variable.

See within as a higher-level alternative.

getVariableValue :: v -> m Double

Get the value of a variable in the current solution.

This value could be arbitrary if no solve has been completed, or a solve produced an infeasible or unbounded solution.

addConstraint :: Inequality (Expr v) -> m c

Add a constraint representing the given inequality to the model.

See the .==., .==#, ==., .>=., .>=, >=., .<=., .<=, and <=. functions as higher-level alternatives.

deleteConstraint :: c -> m ()

Remove a constraint from the model.

getConstraintName :: c -> m Text

Get the name of a constraint.

setConstraintName :: c -> Text -> m ()

Set a name for a constraint.

getConstraintValue :: c -> m Double

Get the dual value associated with a constraint.

addObjective :: Expr v -> m o

Add an objective to the problem.

Depending on the solver backend, this might replace an existing objective.

deleteObjective :: o -> m ()

Remove an objective from the model.

getObjectiveName :: o -> m Text

Get the name of a objective.

setObjectiveName :: o -> Text -> m ()

Set a name for a objective.

getObjectiveSense :: o -> m Sense

Get the sense of an objective.

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

Set the sense of an objective.

getObjectiveValue :: o -> m Double

Get the value of an objective.

getTimeout :: m Double

Get the timeout associated with a problem.

setTimeout :: Double -> m ()

Set the timeout associated with a problem.

optimizeLP :: m SolutionStatus

Compute an LP-optimal solution.

Instances

MonadLP v c o m => MonadLP v c o (ReaderT r m)

Defined in Math.Programming.Types

Methods

addVariable :: ReaderT r m v

deleteVariable :: v -> ReaderT r m ()

getVariableName :: v -> ReaderT r m Text

setVariableName :: v -> Text -> ReaderT r m ()

getVariableBounds :: v -> ReaderT r m Bounds

setVariableBounds :: v -> Bounds -> ReaderT r m ()

getVariableValue :: v -> ReaderT r m Double

addConstraint :: Inequality (Expr v) -> ReaderT r m c

deleteConstraint :: c -> ReaderT r m ()

getConstraintName :: c -> ReaderT r m Text

setConstraintName :: c -> Text -> ReaderT r m ()

getConstraintValue :: c -> ReaderT r m Double

addObjective :: Expr v -> ReaderT r m o

deleteObjective :: o -> ReaderT r m ()

getObjectiveName :: o -> ReaderT r m Text

setObjectiveName :: o -> Text -> ReaderT r m ()

getObjectiveSense :: o -> ReaderT r m Sense

setObjectiveSense :: o -> Sense -> ReaderT r m ()

getObjectiveValue :: o -> ReaderT r m Double

getTimeout :: ReaderT r m Double

setTimeout :: Double -> ReaderT r m ()

optimizeLP :: ReaderT r m SolutionStatus

MonadLP v c o m => MonadLP v c o (StateT s m)

Defined in Math.Programming.Types

Methods

addVariable :: StateT s m v

deleteVariable :: v -> StateT s m ()

getVariableName :: v -> StateT s m Text

setVariableName :: v -> Text -> StateT s m ()

getVariableBounds :: v -> StateT s m Bounds

setVariableBounds :: v -> Bounds -> StateT s m ()

getVariableValue :: v -> StateT s m Double

addConstraint :: Inequality (Expr v) -> StateT s m c

deleteConstraint :: c -> StateT s m ()

getConstraintName :: c -> StateT s m Text

setConstraintName :: c -> Text -> StateT s m ()

getConstraintValue :: c -> StateT s m Double

addObjective :: Expr v -> StateT s m o

deleteObjective :: o -> StateT s m ()

getObjectiveName :: o -> StateT s m Text

setObjectiveName :: o -> Text -> StateT s m ()

getObjectiveSense :: o -> StateT s m Sense

setObjectiveSense :: o -> Sense -> StateT s m ()

getObjectiveValue :: o -> StateT s m Double

getTimeout :: StateT s m Double

setTimeout :: Double -> StateT s m ()

optimizeLP :: StateT s m SolutionStatus

(MonadLP v c o m, Monoid w) => MonadLP v c o (WriterT w m)

Defined in Math.Programming.Types

Methods

addVariable :: WriterT w m v

deleteVariable :: v -> WriterT w m ()

getVariableName :: v -> WriterT w m Text

setVariableName :: v -> Text -> WriterT w m ()

getVariableBounds :: v -> WriterT w m Bounds

setVariableBounds :: v -> Bounds -> WriterT w m ()

getVariableValue :: v -> WriterT w m Double

addConstraint :: Inequality (Expr v) -> WriterT w m c

deleteConstraint :: c -> WriterT w m ()

getConstraintName :: c -> WriterT w m Text

setConstraintName :: c -> Text -> WriterT w m ()

getConstraintValue :: c -> WriterT w m Double

addObjective :: Expr v -> WriterT w m o

deleteObjective :: o -> WriterT w m ()

getObjectiveName :: o -> WriterT w m Text

setObjectiveName :: o -> Text -> WriterT w m ()

getObjectiveSense :: o -> WriterT w m Sense

setObjectiveSense :: o -> Sense -> WriterT w m ()

getObjectiveValue :: o -> WriterT w m Double

getTimeout :: WriterT w m Double

setTimeout :: Double -> WriterT w m ()

optimizeLP :: WriterT w m SolutionStatus

(MonadLP v c o m, Monoid w) => MonadLP v c o (RWST r w s m)

Defined in Math.Programming.Types

Methods

addVariable :: RWST r w s m v

deleteVariable :: v -> RWST r w s m ()

getVariableName :: v -> RWST r w s m Text

setVariableName :: v -> Text -> RWST r w s m ()

getVariableBounds :: v -> RWST r w s m Bounds

setVariableBounds :: v -> Bounds -> RWST r w s m ()

getVariableValue :: v -> RWST r w s m Double

addConstraint :: Inequality (Expr v) -> RWST r w s m c

deleteConstraint :: c -> RWST r w s m ()

getConstraintName :: c -> RWST r w s m Text

setConstraintName :: c -> Text -> RWST r w s m ()

getConstraintValue :: c -> RWST r w s m Double

addObjective :: Expr v -> RWST r w s m o

deleteObjective :: o -> RWST r w s m ()

getObjectiveName :: o -> RWST r w s m Text

setObjectiveName :: o -> Text -> RWST r w s m ()

getObjectiveSense :: o -> RWST r w s m Sense

setObjectiveSense :: o -> Sense -> RWST r w s m ()

getObjectiveValue :: o -> RWST r w s m Double

getTimeout :: RWST r w s m Double

setTimeout :: Double -> RWST r w s m ()

optimizeLP :: RWST r w s m SolutionStatus

Integer programs

class MonadLP v c o m => MonadIP v c o m | m -> v c o where

A (mixed) integer program.

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

Methods

getVariableDomain :: v -> m Domain

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

getRelativeMIPGap :: m Double

setRelativeMIPGap :: Double -> m ()

optimizeIP :: m SolutionStatus

Instances

MonadIP v c o m => MonadIP v c o (ReaderT r m)

Defined in Math.Programming.Types

Methods

getVariableDomain :: v -> ReaderT r m Domain

setVariableDomain :: v -> Domain -> ReaderT r m ()

getRelativeMIPGap :: ReaderT r m Double

setRelativeMIPGap :: Double -> ReaderT r m ()

optimizeIP :: ReaderT r m SolutionStatus

MonadIP v c o m => MonadIP v c o (StateT s m)

Defined in Math.Programming.Types

Methods

getVariableDomain :: v -> StateT s m Domain

setVariableDomain :: v -> Domain -> StateT s m ()

getRelativeMIPGap :: StateT s m Double

setRelativeMIPGap :: Double -> StateT s m ()

optimizeIP :: StateT s m SolutionStatus

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

Other types and functions

evalExpr :: MonadLP v c o m => Expr v -> m Double

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

formatExpr :: MonadLP v c o m => Expr v -> m Text

type Expr = LinExpr Double

A convient shorthand for the type of linear expressions used in models.

data Bounds

An interval of the real numbers.

Constructors

NonNegativeReals

The non-negative reals.

NonPositiveReals

The non-positive reals.

Interval Double Double

Any closed interval of the reals.

Free

Any real number.

Instances

Read Bounds

Defined in Math.Programming.Types

Methods

readsPrec :: Int -> ReadS Bounds

readList :: ReadS [Bounds]

readPrec :: ReadPrec Bounds

readListPrec :: ReadPrec [Bounds]

Show Bounds

Defined in Math.Programming.Types

Methods

showsPrec :: Int -> Bounds -> ShowS

show :: Bounds -> String

showList :: [Bounds] -> 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

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

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

data Sense

Whether a math program is minimizing or maximizing its objective.

Constructors

Minimization

Maximization

Instances

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

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

data Inequality a

Non-strict inequalities.

Constructors

Inequality Ordering a a

Instances

Foldable Inequality

Defined in Math.Programming.Types

Methods

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

foldMap :: Monoid m => (a -> m) -> Inequality a -> 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)

Functor Inequality

Defined in Math.Programming.Types

Methods

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

(<$) :: a -> Inequality b -> 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

data LinExpr a b

A linear expression.

Linear expressions contain symbolic variables of type b and numeric coefficients of type a. Often a will be Double, and b will be whatever variable type your linear program uses.

Constructors

LinExpr ![(a, b)] !a

Instances

Foldable (LinExpr a)

Defined in Math.Programming.LinExpr

Methods

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

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

foldMap' :: Monoid m => (a0 -> m) -> LinExpr a a0 -> m

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

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

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

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

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

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

toList :: LinExpr a a0 -> [a0]

null :: LinExpr a a0 -> Bool

length :: LinExpr a a0 -> Int

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

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

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

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

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

Traversable (LinExpr a)

Defined in Math.Programming.LinExpr

Methods

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

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

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

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

Functor (LinExpr a)

Defined in Math.Programming.LinExpr

Methods

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

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

Num a => Monoid (LinExpr a b)

Defined in Math.Programming.LinExpr

Methods

mempty :: LinExpr a b

mappend :: LinExpr a b -> LinExpr a b -> LinExpr a b

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

Num a => Semigroup (LinExpr a b)

Defined in Math.Programming.LinExpr

Methods

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

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

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

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

Defined in Math.Programming.LinExpr

Methods

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

readList :: ReadS [LinExpr a b]

readPrec :: ReadPrec (LinExpr a b)

readListPrec :: ReadPrec [LinExpr a b]

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

Defined in Math.Programming.LinExpr

Methods

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

show :: LinExpr a b -> String

showList :: [LinExpr a b] -> ShowS

(Eq a, Eq b) => Eq (LinExpr a b)

Defined in Math.Programming.LinExpr

Methods

(==) :: LinExpr a b -> LinExpr a b -> Bool

(/=) :: LinExpr a b -> LinExpr a b -> Bool

Naming model attributes

withVariableName :: MonadLP v c o m => m v -> Text -> m v

withConstraintName :: MonadLP v c o m => m c -> Text -> m c

withObjectiveName :: MonadLP v c o m => m o -> Text -> m o