hmatrix-glpk-0.5.0.0: Linear Programming based on GLPK

Copyright(c) Alberto Ruiz 2010
LicenseGPL
MaintainerAlberto Ruiz
Stabilityprovisional
Safe HaskellNone
LanguageHaskell98

Numeric.LinearProgramming

Description

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).

Synopsis

Documentation

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

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

sparseOfGeneral :: Constraints -> Constraints Source

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

data Constraints Source

Constructors

Dense [Bound [Double]] 
Sparse [Bound [(Double, Int)]] 
General [Bound [(Double, Int)]] 

data Bound x Source

Constructors

x :<=: Double 
x :>=: Double 
x :&: (Double, Double) 
x :==: Double 
Free x 

Instances

Show x => Show (Bound x) Source 

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

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