Numeric.LinearProgramming

This module provides an interface to the standard simplex algorithm.

For example, the following LP problem

maximize 4 x_1 - 3 x_2 + 2 x_3 subject to

2 x_1 + x_2 <= 10

x_2 + 5 x_3 <= 20

and

x_i >= 0

can be solved as follows:

import Numeric.LinearProgramming

prob = Maximize [4, -3, 2]

constr1 = Sparse [ [2#1, 1#2] :<=: 10
                 , [1#2, 5#3] :<=: 20
                 ]

>>> simplex prob constr1 []
Optimal (28.0,[5.0,0.0,4.0])

The coefficients of the constraint matrix can also be given in dense format:

constr2 = Dense [ [2,1,0] :<=: 10
                , [0,1,5] :<=: 20
                ]

Note that when using sparse constraints, coefficients cannot appear more than once in each constraint. You can alternatively use General which will automatically sum any duplicate coefficients when necessary.

constr3 = General [ [1#1, 1#1, 1#2] :<=: 10
                  , [1#2, 5#3] :<=: 20
                  ]

By default all variables are bounded as x_i >= 0, but this can be changed:

>>> simplex prob constr2 [ 2 :>=: 1, 3 :&: (2,7)]
Optimal (22.6,[4.5,1.0,3.8])

>>> simplex prob constr2 [Free 2]
Unbounded

The given bound for a variable completely replaces the default, so 0 <= x_i <= b must be explicitly given as i :&: (0,b). Multiple bounds for a variable are not allowed, instead of [i :>=: a, i:<=: b] use i :&: (a,b).

Documentation

simplex :: Optimization -> Constraints -> Bounds -> Solution

exact :: Optimization -> Constraints -> Bounds -> Solution

Simplex method with exact internal arithmetic. See glp_exact in glpk documentation for more information.

sparseOfGeneral :: Constraints -> Constraints

Convert a system of General constraints to one with unique coefficients.

data Optimization

Constructors

Maximize [Double]

Minimize [Double]

data Constraints

Constructors

Dense [Bound [Double]]

Sparse [Bound [(Double, Int)]]

General [Bound [(Double, Int)]]

type Bounds = [Bound Int]

data Bound x

Constructors

x :<=: Double

x :>=: Double

x :&: (Double, Double)

x :==: Double

Free x

Instances

Show x => Show (Bound x)

(#) :: Double -> Int -> (Double, Int) infixl 5

Coefficient of a variable for a sparse and general representations of constraints.

data Solution

Constructors

Undefined

Feasible (Double, [Double])

Infeasible (Double, [Double])

NoFeasible

Optimal (Double, [Double])

Unbounded

Instances

Show Solution