Documentation ¶
Overview ¶
Package clp provides an interface to the COIN-OR Linear Programming (CLP) library. As the name implies, CLP is a solver for linear-programming problems:
CLP is a high quality open-source LP solver. Its main strengths are its Dual and Primal Simplex algorithms. It also has a barrier algorithm for Linear and Quadratic objectives. There are limited facilities for Nonlinear and Quadratic objectives using the Simplex algorithm. It is available as a library and as a standalone solver. It was written by John Forrest, jjforre at us.ibm.com
Linear programming is an optimization technique. Given an objective function, such as a + b, and a set of constraints in the form of linear inequalities, such as 0 ≤ 2a + b ≤ 10 and 3 ≤ 2b − a ≤ 8, find values for the variables that maximizes or minimizes the objective function. In this example, the maximum value of a + b is 7.6, which is achieved when a = 2.4 and b = 5.2. The example code associated with Simplex.LoadProblem shows how to set up and solve this precise problem using an API based directly on CLP's C++ API. The example code associated with Simplex.EasyLoadDenseProblem shows how to specify the same problem using a more equation-oriented API specific to the clp package.
The clp package currently exposes only a tiny subset of the CLP library.
Relevant URLs:
• COIN-OR (COmputational INfrastructure for Operations Research): http://www.coin-or.org/
• LP (Linear Programming): https://en.wikipedia.org/wiki/Linear_programming
• CLP (COIN-OR Linear Programming): http://www.coin-or.org/projects/Clp.xml
Index ¶
- Constants
- type Bounds
- type Matrix
- type Nonzero
- type OptDirection
- type PackedMatrix
- func (pm *PackedMatrix) AppendColumn(col []Nonzero)
- func (pm *PackedMatrix) AppendRow(row []Nonzero)
- func (pm *PackedMatrix) DeleteColumns(cols []int)
- func (pm *PackedMatrix) DeleteRows(rows []int)
- func (pm *PackedMatrix) DenseData() [][]float64
- func (pm *PackedMatrix) Dims() (rows, cols int)
- func (pm *PackedMatrix) DumpMatrix(w io.Writer) error
- func (pm *PackedMatrix) Reserve(newMaxMajorDim int, newMaxSize int, create bool)
- func (pm *PackedMatrix) SetDimensions(numrows, numcols int)
- func (pm *PackedMatrix) SparseData() (starts, lengths, indices []int, elements []float64)
- type Scaling
- type Simplex
- func (s *Simplex) Barrier(xover bool) SimplexStatus
- func (s *Simplex) Dims() (rows, cols int)
- func (s *Simplex) Dual(vp ValuesPass, sfo StartFinishOptions) SimplexStatus
- func (s *Simplex) DualColumnSolution() []float64
- func (s *Simplex) DualRanging(n int, which []int, costIncrease []float64, sequenceIncrease []int, ...) int
- func (s *Simplex) DualRowSolution() []float64
- func (s *Simplex) EasyLoadDenseProblem(obj []float64, varBounds [][2]float64, ineqs [][]float64)
- func (s *Simplex) LoadProblem(m Matrix, cb []Bounds, obj []float64, rb []Bounds, rowObj []float64)
- func (s *Simplex) MaxIterations() int
- func (s *Simplex) MaxSeconds() float64
- func (s *Simplex) ObjectiveValue() float64
- func (s *Simplex) Primal(vp ValuesPass, sfo StartFinishOptions) SimplexStatus
- func (s *Simplex) PrimalColumnSolution() []float64
- func (s *Simplex) PrimalRanging(n int, which []int, valueIncrease []float64, sequenceIncrease []int, ...) int
- func (s *Simplex) PrimalRowSolution() []float64
- func (s *Simplex) PrimalTolerance() float64
- func (s *Simplex) ReducedGradient(phase bool) SimplexStatus
- func (s *Simplex) SecondaryStatus() SimplexStatus
- func (s *Simplex) SetMaxIterations(maxIter int)
- func (s *Simplex) SetMaxSeconds(maxSeconds float64)
- func (s *Simplex) SetOptimizationDirection(d OptDirection)
- func (s *Simplex) SetPrimalTolerance(tolerance float64)
- func (s *Simplex) SetScaling(sc Scaling)
- func (s *Simplex) WriteMPS(filename string) bool
- type SimplexStatus
- type StartFinishOptions
- type ValuesPass
Examples ¶
Constants ¶
const ( Ignore OptDirection = 0.0 // Ignore the objective function Maximize = -1.0 // Maximize the objective function Minimize = 1.0 // Minimize the objective function )
These constants are used to specify the objective sense in Simplex.SetOptimizationDirection.
const ( NoValuesPass ValuesPass = 0 // Use status variables to determine basis and solution DoValuesPass = 1 // Do a values pass so variables not in the basis are given their current values and one pass of variables is done to clean up the basis with an equal or better objective value OnlyValuesPass = 2 // Do only the values pass and then stop )
These constants specify the sort of value pass to perform.
const ( NoStartFinishOptions StartFinishOptions = 0 // Convenient name for no special options KeepWorkAreas = 1 // Do not delete work areas and factorization at end OldFactorization = 2 // Use old factorization if same number of rows ReduceInitialization = 4 // Skip as much initialization of work areas as possible )
These constants can be or'd together to specify start and finish options.
const ( Optimal SimplexStatus = 0 Infeasible = 1 Unbounded = 2 )
These constants are the possible values for a SimplexStatus.
const ( SecondaryNone SimplexStatus = 0 SecondaryPrimalInfeasible = 1 SecondaryScaledOptimalUnscaledPrimalInfeasible = 2 SecondaryScaledOptimalUnscaledDualInfeasible = 3 SecondaryScaledOptimalUnscaledBothInfeasible = 4 SecondaryGaveUp = 5 SecondaryFailedEmptyCheck = 6 SecondaryPostSolveNotOptimal = 7 SecondaryFailedBadElement = 8 SecondaryStoppedOnTime = 9 SecondaryStoppedPrimalInfeasible = 10 )
These constants are the corresponding values for the secondary status
const ( NoScaling Scaling = 0 // No scaling EquilibriumScaling = 1 // Equilibrium scaling GeometricScaling = 2 // Geometric scaling AutoScaling = 3 // Automatic scaling AutoInitScaling = 4 // Automatic scaling but like the initial solve in branch-and-bound )
These constants can be passed as an argument to Simplex.SetScaling.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Matrix ¶
type Matrix interface { AppendColumn(col []Nonzero) // Append a column given values for all of its nonzero elements Dims() (rows, cols int) // Return the matrix's dimensions }
A Matrix sparsely represents a set of linear expressions. Each column represents a variable, each row represents an expression, and each cell containing a coefficient. Bounds on rows and columns are applied during model initialization.
type Nonzero ¶
type Nonzero struct { Index int // Zero-based element offset Value float64 // Value at that offset }
A Nonzero represents an element in a sparse row or column.
type OptDirection ¶
type OptDirection float64
An OptDirection specifies the direction of optimization (maximize, minimize, or ignore).
type PackedMatrix ¶
type PackedMatrix struct {
// contains filtered or unexported fields
}
A PackedMatrix is a basic implementation of the Matrix interface.
func NewPackedMatrix ¶
func NewPackedMatrix() *PackedMatrix
NewPackedMatrix allocates a new, empty, packed matrix.
func (*PackedMatrix) AppendColumn ¶
func (pm *PackedMatrix) AppendColumn(col []Nonzero)
AppendColumn appends a sparse column to a packed matrix. The column is specified as a slice of {row number, value} pairs.
func (*PackedMatrix) AppendRow ¶ added in v1.2.0
func (pm *PackedMatrix) AppendRow(row []Nonzero)
AppendRow appends a sparse row to a packed matrix. The row is specified as a slice of {column number, value} pairs.
func (*PackedMatrix) DeleteColumns ¶
func (pm *PackedMatrix) DeleteColumns(cols []int)
DeleteColumns removes a list of columns from a packed matrix.
func (*PackedMatrix) DeleteRows ¶ added in v1.2.0
func (pm *PackedMatrix) DeleteRows(rows []int)
DeleteRows removes a list of rows from a packed matrix.
func (*PackedMatrix) DenseData ¶
func (pm *PackedMatrix) DenseData() [][]float64
DenseData returns a packed matrix's data in a dense representation. This method has no exact equivalent in the CLP library. It is merely a convenient wrapper for SparseMatrix that makes it easy to work with smaller matrices.
func (*PackedMatrix) Dims ¶
func (pm *PackedMatrix) Dims() (rows, cols int)
Dims returns a packed matrix's dimensions (rows and columns).
func (*PackedMatrix) DumpMatrix ¶
func (pm *PackedMatrix) DumpMatrix(w io.Writer) error
DumpMatrix outputs a packed matrix in a human-readable format. This method is intended primarily to help with testing and debugging.
func (*PackedMatrix) Reserve ¶
func (pm *PackedMatrix) Reserve(newMaxMajorDim int, newMaxSize int, create bool)
Reserve reserves sufficient space in a packed matrix for appending major-ordered vectors.
func (*PackedMatrix) SetDimensions ¶
func (pm *PackedMatrix) SetDimensions(numrows, numcols int)
SetDimensions reserves sufficient space in a packed matrix for appending major-ordered vectors.
func (*PackedMatrix) SparseData ¶
func (pm *PackedMatrix) SparseData() (starts, lengths, indices []int, elements []float64)
SparseData returns a packed matrix's data in a sparse representation. It corresponds to the getVectorStarts(), getVectorLengths(), getIndices(), and getElements() methods in the CLP library's CoinPackedMatrix class.
type Simplex ¶
type Simplex struct {
// contains filtered or unexported fields
}
A Simplex represents solves linear-programming problems using the simplex method.
func (*Simplex) Barrier ¶
func (s *Simplex) Barrier(xover bool) SimplexStatus
Barrier solves a simplex model with the barrier method. The argument says whether to cross over to simplex.
func (*Simplex) Dual ¶
func (s *Simplex) Dual(vp ValuesPass, sfo StartFinishOptions) SimplexStatus
Dual solves a simplex model with the dual method.
func (*Simplex) DualColumnSolution ¶
DualColumnSolution returns the dual column solution computed by a solver.
func (*Simplex) DualRanging ¶
func (s *Simplex) DualRanging(n int, which []int, costIncrease []float64, sequenceIncrease []int, costDecrease []float64, sequenceDecrease []int, valueIncrease, valueDecrease []float64) int
DualRanging returns the increases and decreases in costs of the given variables that do not change the solution basis. valueIncrease and valueDecrease can be nil. If both are non-nil they are filled with the new values corresponding to those cost changes. This method panics unless all non-nil input slices are of length n and returns non-0 if the solution is infeasible or unbounded.
func (*Simplex) DualRowSolution ¶
DualRowSolution returns the dual row solution computed by a solver.
func (*Simplex) EasyLoadDenseProblem ¶
EasyLoadDenseProblem has no exact equivalent in the CLP library. It is merely a convenient wrapper for LoadProblem that lets callers specify problems in a more natural, equation-like form (as opposed to CLP's normal matrix form). The main limitation is that it does not provide a space-efficient way to represent a sparse coefficient matrix; all coefficients must be specified, even when zero. A secondary limitation is that it does not support a row objective function.
The arguments to EasyLoadDenseProblem are the coefficients of the objective function, lower and upper bounds on each variable, and a matrix in which each row is of the form {lower bound, var_1, var_2, …, var_N, upper bound}.
Example ¶
Maximize a + b subject to both 0 ≤ 2a + b ≤ 10 and 3 ≤ 2b − a ≤ 8.
package main import ( "fmt" "github.com/lanl/clp" ) func main() { // Set up the problem. simp := clp.NewSimplex() simp.EasyLoadDenseProblem( // A B []float64{1.0, 1.0}, // a + b nil, // No explicit bounds on A or B [][]float64{ // LB A B UB {0.0, 2.0, 1.0, 10.0}, // 0 ≤ 2a + b ≤ 10 {3.0, -1.0, 2.0, 8.0}, // 3 ≤ -a + 2b ≤ 8 }) simp.SetOptimizationDirection(clp.Maximize) // Solve the optimization problem. simp.Primal(clp.NoValuesPass, clp.NoStartFinishOptions) val := simp.ObjectiveValue() soln := simp.PrimalColumnSolution() // Output the results. fmt.Printf("a = %.1f\nb = %.1f\na + b = %.1f\n", soln[0], soln[1], val) }
Output: a = 2.4 b = 5.2 a + b = 7.6
func (*Simplex) LoadProblem ¶
LoadProblem loads a problem into a simplex model. It takes as an argument a matrix (with inequalities in rows and coefficients in columns), the upper and lower column bounds, the coefficients of the column objective function, the upper and lower row bounds, and the coefficients of the row objective function. Any of these arguments except for the matrix can be nil. When nil, the column bounds default to {0, ∞} for each row; the column and row objective functions default to 0 for all coefficients; and the row bounds default to {−∞, +∞} for each column.
Example ¶
Maximize a + b subject to both 0 ≤ 2a + b ≤ 10 and 3 ≤ 2b − a ≤ 8.
package main import ( "fmt" "github.com/lanl/clp" ) func main() { // Set up the problem. mat := clp.NewPackedMatrix() mat.AppendColumn([]clp.Nonzero{ {Index: 0, Value: 2.0}, // 2a {Index: 1, Value: -1.0}, // -a }) mat.AppendColumn([]clp.Nonzero{ {Index: 0, Value: 1.0}, // b {Index: 1, Value: 2.0}, // 2b }) rb := []clp.Bounds{ {Lower: 0, Upper: 10}, // [0, 10] {Lower: 3, Upper: 8}, // [3, 8] } obj := []float64{1.0, 1.0} // a + b simp := clp.NewSimplex() simp.LoadProblem(mat, nil, obj, rb, nil) simp.SetOptimizationDirection(clp.Maximize) // Solve the optimization problem. simp.Primal(clp.NoValuesPass, clp.NoStartFinishOptions) val := simp.ObjectiveValue() soln := simp.PrimalColumnSolution() // Output the results. fmt.Printf("a = %.1f\nb = %.1f\na + b = %.1f\n", soln[0], soln[1], val) }
Output: a = 2.4 b = 5.2 a + b = 7.6
func (*Simplex) MaxIterations ¶
MaxIterations returns the maximum number of iterations for a solve.
func (*Simplex) MaxSeconds ¶
MaxSeconds returns the maximum number of seconds for a solve.
func (*Simplex) ObjectiveValue ¶
ObjectiveValue returns the value of the objective function after optimization.
func (*Simplex) Primal ¶
func (s *Simplex) Primal(vp ValuesPass, sfo StartFinishOptions) SimplexStatus
Primal solves a simplex model with the primal method.
func (*Simplex) PrimalColumnSolution ¶
PrimalColumnSolution returns the primal column solution computed by a solver.
func (*Simplex) PrimalRanging ¶
func (s *Simplex) PrimalRanging(n int, which []int, valueIncrease []float64, sequenceIncrease []int, valueDecrease []float64, sequenceDecrease []int) int
PrimalRanging returns the increases and decreases in value of the given variables that do not change the solution basis. It panics unless all input slices are of length n and returns non-0 if the solution is infeasible or unbounded.
func (*Simplex) PrimalRowSolution ¶
PrimalRowSolution returns the primal row solution computed by a solver.
func (*Simplex) PrimalTolerance ¶
PrimalTolerance returns the tolerance currently associated with the variables in a simplex model.
func (*Simplex) ReducedGradient ¶
func (s *Simplex) ReducedGradient(phase bool) SimplexStatus
ReducedGradient solves a simplex model with the reduced-gradient method. The argument says whether to get a feasible solution (false) or to use a solution.
func (*Simplex) SecondaryStatus ¶
func (s *Simplex) SecondaryStatus() SimplexStatus
SecondaryStatus returns the secondary status of a model.
func (*Simplex) SetMaxIterations ¶
SetMaxIterations sets the maximum number of iterations for a solve.
func (*Simplex) SetMaxSeconds ¶
SetMaxSeconds sets the maximum number of seconds for a solve.
func (*Simplex) SetOptimizationDirection ¶
func (s *Simplex) SetOptimizationDirection(d OptDirection)
SetOptimizationDirection specifies whether the objective function should be minimized, maximized, or ignored.
func (*Simplex) SetPrimalTolerance ¶
SetPrimalTolerance assigns a new variable tolerance to a simplex model. According to the Clp documentation, "a variable is deemed primal feasible if it is less than the tolerance…below its lower bound and less than it above its upper bound".
func (*Simplex) SetScaling ¶
SetScaling determines how the problem data are to be scaled.
type SimplexStatus ¶
type SimplexStatus int
SimplexStatus represents the status of a simplex optimization.
type StartFinishOptions ¶
type StartFinishOptions uint
A StartFinishOptions is a bit vector for options related to the algorithm's initialization and finalization.