lpsimplex

README

lpsimplex

This is a port of the python scipy LP simplex routines. It is intended to be a reasonable implementation for 'real projects;' that is not just for educational purposes.

Getting Started

This library has just one main function, LPSimplex(), and two example functions for callback routines. The rest are internal.

To use this software, copy the repository into your gopath, enter the directory and issue the command 'go install.' This will build and install a copy of the library on your system for your use.

Prerequisites

You must have Go installed on your system in order to make use of the library.

Running the tests

Test development is in progress.

To run the test issue the command: go test

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Acknowledgments

As this code is starting based on the SciPy simplex routines I include the following:

Copyright © 2001, 2002 Enthought, Inc. All rights reserved.

Copyright © 2003-2013 SciPy Developers. All rights reserved.

Documentation

Index

• Variables
• func EquilibrationModScalePivotOnly(cc []float64, Aub [][]float64, bub []float64, Aeq [][]float64, beq []float64)
• func GetModelSmall_1() ([][]float64, []float64, []float64)
• func GetModel_Big_1() ([][]float64, []float64, []float64)
• func LPSimplexNewBehaviorGetScalePivDiff() (int, int)
• func LPSimplexNewBehaviorGetUnboundedVarNum() int
• func LPSimplexSetNewBehavior(cmd NB_CMD) int
• func LPSimplexTerseCallback(xk []float64, tableau [][]float64, nit, pivrow, pivcol, phase int, basis []int, ...)
• func LPSimplexVerboseCallback(xk []float64, tableau [][]float64, nit, pivrow, pivcol, phase int, basis []int, ...)
• func TersPrintArray(a []float64)
• func TersPrintIntArray(a []int)
• func TersPrintMatrix(a [][]float64) error
• type Bound
• type Callbackfunc
• type NB_CMD
• type OptResult
  • func LPSimplex(cc []float64, Aub [][]float64, bub []float64, Aeq [][]float64, beq []float64, ...) OptResult

Variables

var Version = struct {
	Major string
	Minor string
	Patch string
	Str   string
}{"0", "4", "11", "beta"}

Functions

func EquilibrationModScalePivotOnly

func EquilibrationModScalePivotOnly(cc []float64, Aub [][]float64,
	bub []float64, Aeq [][]float64, beq []float64)

func GetModelSmall_1

func GetModelSmall_1() ([][]float64, []float64, []float64)

GetModel returns constraint matrix A, b, c

func GetModel_Big_1

func GetModel_Big_1() ([][]float64, []float64, []float64)

GetModel returns constraint matrix A, b, c

func LPSimplexNewBehaviorGetScalePivDiff

func LPSimplexNewBehaviorGetScalePivDiff() (int, int)

func LPSimplexNewBehaviorGetUnboundedVarNum

func LPSimplexNewBehaviorGetUnboundedVarNum() int

func LPSimplexSetNewBehavior

func LPSimplexSetNewBehavior(cmd NB_CMD) int

FIXME: may want to have a special function to return the degeneritePivotCount

func LPSimplexTerseCallback

func LPSimplexTerseCallback(xk []float64, tableau [][]float64, nit, pivrow, pivcol, phase int, basis []int, complete bool)

LPSimplexTerseCallback is an example callbase with verbose output.

A sample callback function demonstrating the LPSimplex callback interface.
This callback produces brief output to sys.stdout before each iteration
and after the final iteration of the simplex algorithm.

Parameters
----------
xk : array_like (float64)
    The current solution vector.
tableau : matrix_like (float64 x float64)
	The current tableau of the simplex algorithm.
	Its structure is defined in _solve_simplex.
nit : int
	The current iteration number.
pivcol : (int)
	The column index of the tableau selected as the next
	pivot column or -1 if no pivot exists
pivrow : (int)
	The row index of the tableau selected as the next pivot
	row or -1 if no pivot exists
phase : int
	The current Phase of the simplex algorithm (1 or 2)
basis : list[tuple(int, float)]
	A list of the current basic variables.
	Each element contains the index of a basic variable and
	its value.
complete : bool
	True if the simplex algorithm has completed
	(and this is the final call to callback), otherwise False.

func LPSimplexVerboseCallback

func LPSimplexVerboseCallback(xk []float64, tableau [][]float64, nit, pivrow, pivcol, phase int, basis []int, complete bool)

LPSimplexVerboseCallback is an example callbase with verbose output. A sample callback function demonstrating the LPSimplex callback interface. This callback produces detailed output to sys.stdout before each iteration and after the final iteration of the simplex algorithm.

    Parameters
    ----------
    xk : array_like (float64)
       The current solution vector.
    tableau : array_like
        The current tableau of the simplex algorithm.
        Its structure is defined in _solve_simplex.
    phase : int
        The current Phase of the simplex algorithm (1 or 2)
    nit : int
        The current iteration number.
    pivcol : (int)
		The column index of the tableau selected as the next
		pivot column or -1 if no pivot exists
    pivrow : (int)
		The row index of the tableau selected as the next pivot
		row or -1 if no pivot exists
    basis : array(int)
        A list of the current basic variables.
        Each element contains the name of a basic variable and its value.
    complete : bool
        True if the simplex algorithm has completed
        (and this is the final call to callback), otherwise False.

func TersPrintArray

func TersPrintArray(a []float64)

TersPrintArray prints, skipping middle elements, so the array fits on a line.

func TersPrintIntArray

func TersPrintIntArray(a []int)

TersPrintIntArray prints, skipping middle elements, so the array fits on a line.

func TersPrintMatrix

func TersPrintMatrix(a [][]float64) error

TersPrintMatrix prints, skipping middle elements, so it fits on a screen.

Types

type Bound

type Bound struct {
	Lb float64
	Ub float64
}

Bound is a struc that carries the low and high values of a variable's range.

type Callbackfunc

type Callbackfunc func([]float64, [][]float64, int, int, int, int, []int, bool)

Callbackfunc is the function type for the callback that LPSimplex takes.

type NB_CMD

type NB_CMD int64

const (
	NB_CMD_NOP              NB_CMD = 0x00 // New Behavior Do Nothing
	NB_CMD_RESET            NB_CMD = 0x01 // Reset all New Behavior to Default
	NB_CMD_USEDYNAMICBLAND  NB_CMD = 0x02 // Use Dynamic Bland pivoting
	NB_CMD_SCALEME          NB_CMD = 0x04 // Use Implicit scaling
	NB_CMD_SCALEME_POW2     NB_CMD = 0x08 // Use Implicit scaling power of 2
	NB_CMD_SCALEME_PIV_DIFF NB_CMD = 0x10 // Check pivot diff scaling vs. not
)

type OptResult

type OptResult struct {
	X       []float64
	Fun     float64
	Nitr    int
	Status  int
	Slack   []float64
	Message string
	Success bool
	Y       []float64
	Z       []float64
}

Functions ---------

LPSimplex
LPSimplexVerboseCallback
LPSimplexTerseCallback

OptResult carries the result of the simplex operation.

func LPSimplex

func LPSimplex(cc []float64,
	Aub [][]float64, bub []float64,
	Aeq [][]float64, beq []float64,
	bounds []Bound, callback Callbackfunc, disp bool,
	maxiter int, tol float64, bland bool) OptResult

LPSimplex takes a general LP model, converts to standard LP and then calls solveSimplex() to solves each phase of the two-phase algorithm.

Solve the following linear programming problem via a two-phase
simplex algorithm.

minimize:     c^T * x

subject to:   A_ub * x <= b_ub
	          A_eq * x == b_eq
	          x >= 0 if not explicitly overriden with defined bounds

Parameters
----------
c : array_like
	Coefficients of the linear objective function to be minimized.
A_ub : array_like
	2-D array which, when matrix-multiplied by x, gives the values of the
	upper-bound inequality constraints at x.
b_ub : array_like
	1-D array of values representing the upper-bound of each inequality
	constraint (row) in A_ub.
A_eq : array_like
	2-D array which, when matrix-multiplied by x, gives the values of the
	equality constraints at x.
b_eq : array_like
	1-D array of values representing the RHS of each equality constraint
	(row) in A_eq.
bounds : array_like of Bound struct with lb, ub of type float64
	The bounds for each independent variable in the solution, which
	can take one of three forms::
	    None : The default bounds, all variables are non-negative.
		(lb, ub) : if only one struct, the same lower bound (lb) and
		   		   upper bound (ub) will be applied to all variables.
		[(lb_0, ub_0), (lb_1, ub_1), ...] : If an n x Bound struct
				   sequence is provided, each variable x_i will be
				   bounded by Bounds[i].Lb and Bound[i].Ub.
	    Infinite bounds are specified using math.Inf(-1) (negative)
	       		   and math.Inf(1) (positive).
callback : callable
	If a callback function is provide, it will be called within each
	iteration of the simplex algorithm. The callback must have the
	signature `callback(xk, **kwargs)` where xk is the current solution
	vector and kwargs is a dictionary containing the following::
	    "tableau" : The current Simplex algorithm tableau
	    "nit"     : The current iteration.
	    "pivot"   : The pivot (row, column) used for the next iteration.
	    "phase"   : Whether the algorithm is in Phase 1 or Phase 2.
		"bv"      : A structured array containing a string representation
		            of each basic variable and its current value.
maxiter : int
	The maximum number of iterations to perform.
disp : bool
	If True, print exit status message to sys.stdout
tol : float
	The tolerance which determines when a solution is "close enough" to zero
	in Phase 1 to be considered a basic feasible solution or close enough
	to positive to to serve as an optimal solution.
bland : bool
	If True, use Bland's anti-cycling rule [3] to choose pivots to
	prevent cycling.  If False, choose pivots which should lead to a
	converged solution more quickly.  The latter method is subject to
	cycling (non-convergence) in rare instances.

Returns
-------
An OptResult struct consisting of the following fields::
	x : []float64
	    The independent variable vector which optimizes the linear
	    programming problem.
	fun : float64
	    Value of the objective function.
	slack : []float64
	    The values of the slack variables.  Each slack variable corresponds
	    to an inequality constraint.  If the slack is zero, then the
	    corresponding constraint is active.
	success : bool
	    Returns True if the algorithm succeeded in finding an optimal
	    solution.
	status : int
	    An integer representing the exit status of the optimization::
	    0 : Optimization terminated successfully
	    1 : Iteration limit reached
	    2 : Problem appears to be infeasible
	    3 : Problem appears to be unbounded
	nit : int
	    The number of iterations performed.
	message : str
	    A string descriptor of the exit status of the optimization.

Examples
--------
Consider the following problem:

Minimize: f = -1*x[0] + 4*x[1]

Subject to: -3*x[0] + 1*x[1] <= 6
	         1*x[0] + 2*x[1] <= 4
	                    x[1] >= -3

	   where:  -inf <= x[0] <= inf

This problem deviates from the standard linear programming problem.  In
standard form, linear programming problems assume the variables x are
non-negative.  Since the variables don't have standard bounds where
0 <= x <= inf, the bounds of the variables must be explicitly set.

There are two upper-bound constraints, which can be expressed as

dot(A_ub, x) <= b_ub

The input for this problem is as follows:

>>> from scipy.optimize import linprog
>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bnds = (None, None)
>>> x1_bnds = (-3, None)
>>> res = linprog(c, A, b, bounds=(x0_bnds, x1_bnds))
>>> print(res)
	        fun: -22.0
message: 'Optimization terminated successfully.'
	        nit: 1
	      slack: array([ 39.,   0.])
	     status: 0
	    success: True
	          x: array([ 10.,  -3.])

References
----------
[1] Dantzig, George B., Linear programming and extensions. Rand
	Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963
[2] Hillier, S.H. and Lieberman, G.J. (1995), "Introduction to
	Mathematical Programming", McGraw-Hill, Chapter 4.
[3] Bland, Robert G. New finite pivoting rules for the simplex method.
	Mathematics of Operations Research (2), 1977: pp. 103-107.
[4] Paul R. Thie, Gerard E. Keough, "An Introduction to Linear
	Programming and Game Theory" 3rd Ed, Chapter 3.7 Redundant Systems
	pp. 102