hmatrix-glpk-0.4.0.1: 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_3 + 5 x_4 <= 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
                ]

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

data Constraints Source

Constructors

Dense [Bound [Double]] 
Sparse [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) 

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

Coefficient of a variable for a sparse representation of constraints.