clp

package module
v1.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 8, 2022 License: BSD-3-Clause Imports: 6 Imported by: 4

README

clp

Go Reference Go project version Go Report Card

Description

The clp package provides a Go interface to the COIN-OR Linear Programming (CLP) library, part of the COIN-OR (COmputational INfrastructure for Operations Research) suite.

Linear programming (LP) is a method for maximizing or minimizing a linear expression subject to a set of constraints expressed as inequalities. As an example that's simple enough to solve by hand, what roll of three six-sided dice has the largest total value if no two dice are allowed have the same value and the difference in value between the first and second largest dice must be smaller than the difference in value between the second and third largest dice? From an LP standpoint, the objective function we need to maximize to answer that question is a + b + c, where each variable represents the value on one die. The first constraint is that each die be six sided:

  • 1 ≤ a ≤ 6
  • 1 ≤ b ≤ 6
  • 1 ≤ c ≤ 6

The second constraint is that the three dice all have different values. We specify this by imposing a total order, a > b > c, which we express as

  • 1 ≤ a - b ≤ ∞
  • 1 ≤ b - c ≤ ∞

The third constraint is that the difference in value between the first and second largest dice (a − b) is smaller than the difference in value between the second and third largest dice (b − c). To put this in a suitable format for LP, we rewrite a − b < b − c as

  • -∞ ≤ a - 2b + c ≤ -1

These constraints translate directly to Go using the clp package's API:

package main

import (
        "fmt"
        "github.com/lanl/clp"
        "math"
)

func main() {
        // Set up the optimization problem.
        pinf := math.Inf(1)
        ninf := math.Inf(-1)
        simp := clp.NewSimplex()
        simp.EasyLoadDenseProblem(
                //         A    B    C
                []float64{1.0, 1.0, 1.0},
                [][2]float64{
                        // LB UB
                        {1, 6}, // 1 ≤ a ≤ 6
                        {1, 6}, // 1 ≤ b ≤ 6
                        {1, 6}, // 1 ≤ c ≤ 6
                },
                [][]float64{
                        // LB  A    B    C    UB
                        {1.0, 1.0, -1.0, 0.0, pinf},  // 1 ≤ a - b ≤ ∞
                        {1.0, 0.0, 1.0, -1.0, pinf},  // 1 ≤ b - c ≤ ∞
                        {ninf, 1.0, -2.0, 1.0, -1.0}, // -∞ ≤ a - 2b + c ≤ -1
                })
        simp.SetOptimizationDirection(clp.Maximize)

        // Solve the optimization problem.
        simp.Primal(clp.NoValuesPass, clp.NoStartFinishOptions)
        soln := simp.PrimalColumnSolution()

        // Output the solution.
        fmt.Printf("Die 1 = %.0f\n", soln[0])
        fmt.Printf("Die 2 = %.0f\n", soln[1])
        fmt.Printf("Die 3 = %.0f\n", soln[2])
}

The output is the expected

Die 1 = 6
Die 2 = 5
Die 3 = 3

Installation

clp has been tested only on Linux. The package requires a CLP installation to build. To check if CLP is installed, ensure that the following command produces a list of libraries, typically along the lines of -lClp -lCoinUtils …, and, more importantly, issues no error messages:

pkg-config --libs clp

Once CLP installation is confirmed, you're ready to install the clp package. As clp has opted into the Go module system, installation is in fact unnecessary if your program or package has done likewise. Otherwise, install the clp package with go get:

go get github.com/lanl/clp

Documentation

Pre-built documentation for the clp API is available online at https://pkg.go.dev/github.com/lanl/clp.

Copyright © 2011, Triad National Security, LLC. All rights reserved.

This software was produced under U.S. Government contract 89233218CNA000001 for Los Alamos National Laboratory (LANL), which is operated by Triad National Security, LLC for the U.S. Department of Energy/National Nuclear Security Administration. All rights in the program are reserved by Triad National Security, LLC, and the U.S. Department of Energy/National Nuclear Security Administration. The Government is granted for itself and others acting on its behalf a nonexclusive, paid-up, irrevocable worldwide license in this material to reproduce, prepare derivative works, distribute copies to the public, perform publicly and display publicly, and to permit others to do so. NEITHER THE GOVERNMENT NOR TRIAD NATIONAL SECURITY, LLC MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to produce derivative works, such modified software should be clearly marked, so as not to confuse it with the version available from LANL.

clp is provided under a BSD 3-clause license. See the LICENSE file for the full text.

This package is part of the LANL Go Suite, represented internally to LANL as LA-CC-11-056.

Author

Scott Pakin, pakin@lanl.gov

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

Examples

Constants

View Source 
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.

View Source 
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.

View Source 
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.

View Source 
const (
	Optimal    SimplexStatus = 0
	Infeasible               = 1
	Unbounded                = 2
)

These constants are the possible values for a SimplexStatus.

View Source 
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

View Source 
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 Bounds 

type Bounds struct {
	Lower float64
	Upper float64
}

Bounds represents the lower and upper bound on a value.

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 Scaling 

type Scaling int

Scaling indicates how problem data are to be scaled.

type Simplex 

type Simplex struct {
	// contains filtered or unexported fields
}

A Simplex represents solves linear-programming problems using the simplex method.

func NewSimplex 

func NewSimplex() *Simplex

NewSimplex creates a new simplex model.

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

func (s *Simplex) Dims() (rows, cols int)

Dims returns a model's dimensions (rows and columns).

func (*Simplex) Dual 

func (s *Simplex) Dual(vp ValuesPass, sfo StartFinishOptions) SimplexStatus

Dual solves a simplex model with the dual method.

func (*Simplex) DualColumnSolution 

func (s *Simplex) DualColumnSolution() []float64

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 

func (s *Simplex) DualRowSolution() []float64

DualRowSolution returns the dual row solution computed by a solver.

func (*Simplex) EasyLoadDenseProblem 

func (s *Simplex) EasyLoadDenseProblem(obj []float64, varBounds [][2]float64, ineqs [][]float64)

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 

func (s *Simplex) LoadProblem(m Matrix, cb []Bounds, obj []float64, rb []Bounds, rowObj []float64)

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 

func (s *Simplex) MaxIterations() int

MaxIterations returns the maximum number of iterations for a solve.

func (*Simplex) MaxSeconds 

func (s *Simplex) MaxSeconds() float64

MaxSeconds returns the maximum number of seconds for a solve.

func (*Simplex) ObjectiveValue 

func (s *Simplex) ObjectiveValue() float64

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 

func (s *Simplex) PrimalColumnSolution() []float64

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 

func (s *Simplex) PrimalRowSolution() []float64

PrimalRowSolution returns the primal row solution computed by a solver.

func (*Simplex) PrimalTolerance 

func (s *Simplex) PrimalTolerance() float64

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 

func (s *Simplex) SetMaxIterations(maxIter int)

SetMaxIterations sets the maximum number of iterations for a solve.

func (*Simplex) SetMaxSeconds 

func (s *Simplex) SetMaxSeconds(maxSeconds float64)

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 

func (s *Simplex) SetPrimalTolerance(tolerance float64)

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 

func (s *Simplex) SetScaling(sc Scaling)

SetScaling determines how the problem data are to be scaled.

func (*Simplex) WriteMPS 

func (s *Simplex) WriteMPS(filename string) bool

WriteMPS writes the model to the named MPS file. It returns true on success and false on failure.

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.

type ValuesPass 

type ValuesPass int

A ValuesPass specifies whether to perform a values pass.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.