lp

Documentation

Overview

Package lp implements routines to solve linear programming problems.

package lp implements routines for solving linear programs.

Index

• Variables
• func Convert(c []float64, g mat.Matrix, h []float64, a mat.Matrix, b []float64) (cNew []float64, aNew *mat.Dense, bNew []float64)
• func Simplex(c []float64, A mat.Matrix, b []float64, tol float64, initialBasic []int) (optF float64, optX []float64, err error)

Examples

• Simplex

Variables

var (
	ErrBland      = errors.New("lp: bland: all replacements are negative or cause ill-conditioned ab")
	ErrInfeasible = errors.New("lp: problem is infeasible")
	ErrLinSolve   = errors.New("lp: linear solve failure")
	ErrUnbounded  = errors.New("lp: problem is unbounded")
	ErrSingular   = errors.New("lp: A is singular")
	ErrZeroColumn = errors.New("lp: A has a column of all zeros")
	ErrZeroRow    = errors.New("lp: A has a row of all zeros")
)

Functions

func Convert

func Convert(c []float64, g mat.Matrix, h []float64, a mat.Matrix, b []float64) (cNew []float64, aNew *mat.Dense, bNew []float64)

Convert converts a General-form LP into a standard form LP. The general form of an LP is:

minimize cᵀ * x
s.t      G * x <= h
         A * x = b

And the standard form is:

minimize cNewᵀ * x
s.t      aNew * x = bNew
         x >= 0

If there are no constraints of the given type, the inputs may be nil.

func Simplex

func Simplex(c []float64, A mat.Matrix, b []float64, tol float64, initialBasic []int) (optF float64, optX []float64, err error)

Simplex solves a linear program in standard form using Danzig's Simplex algorithm. The standard form of a linear program is:

minimize	cᵀ x
s.t. 		A*x = b
			x >= 0 .

The input tol sets how close to the optimal solution is found (specifically, when the maximal reduced cost is below tol). An error will be returned if the problem is infeasible or unbounded. In rare cases, numeric errors can cause the Simplex to fail. In this case, an error will be returned along with the most recently found feasible solution.

The Convert function can be used to transform a general LP into standard form.

The input matrix A must have at least as many columns as rows, len(c) must equal the number of columns of A, and len(b) must equal the number of rows of A or Simplex will panic. A must also have full row rank and may not contain any columns with all zeros, or Simplex will return an error.

initialBasic can be used to set the initial set of indices for a feasible solution to the LP. If an initial feasible solution is not known, initialBasic may be nil. If initialBasic is non-nil, len(initialBasic) must equal the number of rows of A and must be an actual feasible solution to the LP, otherwise Simplex will panic.

A description of the Simplex algorithm can be found in Ch. 8 of

Strang, Gilbert. "Linear Algebra and Applications." Academic, New York (1976).

For a detailed video introduction, see lectures 11-13 of UC Math 352

https://www.youtube.com/watch?v=ESzYPFkY3og&index=11&list=PLh464gFUoJWOmBYla3zbZbc4nv2AXez6X.

Example

package main

import (
	"fmt"
	"log"

	"gonum.org/v1/gonum/mat"
	"gonum.org/v1/gonum/optimize/convex/lp"
)

func main() {
	c := []float64{-1, -2, 0, 0}
	A := mat.NewDense(2, 4, []float64{-1, 2, 1, 0, 3, 1, 0, 1})
	b := []float64{4, 9}

	opt, x, err := lp.Simplex(c, A, b, 0, nil)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("opt: %v\n", opt)
	fmt.Printf("x: %v\n", x)
}

Output:

opt: -8
x: [2 3 0 0]