golp

package module
v0.0.0-...-5f2a34e Latest Latest
Warning

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

 Go to latest Published: Apr 1, 2025 License: MIT Imports: 4 Imported by: 15

README

GoDoc Build Status Code Climate

Golp is a Golang wrapper for the LPSolve linear (and integer) programming library.

Installation

Step 1: Get the golp Go code

go get -d github.com/draffensperger/golp

Step 2: Get the LPSolve library

Golp is configured to dynamically link to LPSolve and expects lpsolve to reside in the following places:

Mac: /opt/local/includes/lpsolve && /opt/local/lib which is where ports puts it. If you installed via homebrew (brew install lp_solve) then the paths are

export CGO_CFLAGS="-I/opt/homebrew/opt/lp_solve/include"
export CGO_LDFLAGS="-L/opt/homebrew/opt/lp_solve/lib"

Linux (general): $GOPATH/src/github.com/draffensperger/golp/lpsolve.

Windows (general): $GOPATH/src/github.com/draffensperger/golp@xxx/lpsolve.

You will need an LPSolve library suitable for your operating system, which you can get from SourceForge.

Here's how you could download the LPSolve library for 64-bit windows:

https://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.0/lp_solve_5.5.2.0_dev_win64.zip/download

Then extract content zip file in $GOPATH/src/github.com/draffensperger/golp@xxx/lpsolve. Finally, copy lpsolve55.dll file into your golang project directory (or maybe into c:\windows\system32).

To install LPSolve on Mac OS X, install MacPorts, then run sudo port install lp_solve.

Here's how you could download and extract the LPSolve library for 64-bit Linux:

LP_URL=http://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.0/lp_solve_5.5.2.0_dev_ux64.tar.gz
LP_DIR=$GOPATH/src/github.com/draffensperger/golp/lpsolve
mkdir -p $LP_DIR
curl -L $LP_URL | tar xvz -C $LP_DIR

On Debian 8+ you can install the lpsolve package with sudo apt-get install liblpsolve55-dev and then set the environment variables for LDFLAGS and CFLAGS like:

export CGO_CFLAGS="-I/usr/include/lpsolve"
export CGO_LDFLAGS="-llpsolve55 -lm -ldl -lcolamd"

With some configuration changes, it would be possible to statically link to LPSolve but that may have licensing/distribution implications for your project since LP Solve is LGPL licensed.

Usage

Not all LPSolve functions are supported, but it's currently possible to run a simple linear and integer program using golp. For details, see the golp GoDoc page.

Feel free to open a GitHub issue or pull request if you'd like more functions added.

Example with real-valued variables

The example below in an adaption of an example in the LP Solve documentation. for maximizing a farmer's profit.

package main

import "fmt"
import "github.com/draffensperger/golp"

func main() {
  lp := golp.NewLP(0, 2)
  lp.AddConstraint([]float64{110.0, 30.0}, golp.LE, 4000.0)
  lp.AddConstraint([]float64{1.0, 1.0}, golp.LE, 75.0)
  lp.SetObjFn([]float64{143.0, 60.0})
  lp.SetMaximize()

  lp.Solve()
  vars := lp.Variables()
  fmt.Printf("Plant %.3f acres of barley\n", vars[0])
  fmt.Printf("And  %.3f acres of wheat\n", vars[1])
  fmt.Printf("For optimal profit of $%.2f\n", lp.Objective())

  // No need to explicitly free underlying C structure as golp.LP finalizer will
}

Outputs:

Plant 21.875 acres of barley
And  53.125 acres of wheat
For optimal profit of $6315.62

MIP (Mixed Integer Programming) example

LPSolve also supports setting variables to be integral or binary and uses the branch-and-bound algorithm for such problems. This example is from the LPSolve integer variables documentation.

import "fmt"
import "github.com/draffensperger/golp"

func main() {
  lp := golp.NewLP(0, 4)
  lp.AddConstraintSparse([]golp.Entry{{0, 1.0}, {1, 1.0}}, golp.LE, 5.0)
  lp.AddConstraintSparse([]golp.Entry{{0, 2.0}, {1, -1.0}}, golp.GE, 0.0)
  lp.AddConstraintSparse([]golp.Entry{{0, 1.0}, {1, 3.0}}, golp.GE, 0.0)
  lp.AddConstraintSparse([]golp.Entry{{2, 1.0}, {3, 1.0}}, golp.GE, 0.5)
  lp.AddConstraintSparse([]golp.Entry{{2, 1.0}}, golp.GE, 1.1)
  lp.SetObjFn([]float64{-1.0, -2.0, 0.1, 3.0})
  lp.SetInt(2, true)
  lp.Solve()

  fmt.Printf("Objective value: %v\n", lp.Objective())
  vars := lp.Variables()
  fmt.Printf("Variable values:\n")
  for i := 0; i < lp.NumCols(); i++ {
    fmt.Printf("x%v = %v\n", i + 1, vars[i])
  }
}

Outputs:

Objective value: -8.133333333333333
Variable values:
x1 = 1.6666666666666665
x2 = 3.333333333333333
x3 = 2
x4 = 0

Alternative linear / mixed integer solver libraries

There are also Go bindings for the GPL-licensed GNU Linear Programming Kit (GLPK) at github.com/lukpank/go-glpk.

The Google or-tools project provides a C++ SWIG compatible inteface for a number of other linear and mixed integer solvers like CBC, CLP, GLOP, Gurobi, CPLEX, SCIP, and Sulum. There is Go support for SWIG bindings, so it should be possible to write a wrapper that would connect to those other solvers via the or-tools library as well.

Acknowledgements and License

The LPSolve library this project depends on is LGPL licensed.

The stringbuilder.c code is from breckinloggins/libuseful.

Thanks to Mike Gaffney (gaffo) for correcting the Linux install instructions. Thanks to khaaan for a typo fix and Debian 8 install instructions.

The golp Go code is MIT licensed as follows:

The MIT License (MIT)

Copyright (c) 2015 David Raffensperger

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Documentation

Overview

Package golp gives Go bindings for LPSolve, a Mixed Integer Linear Programming (MILP) solver.

For usage examples, see https://github.com/draffensperger/golp#examples.

Not all LPSolve functions have bindings. Feel free to open an issue or contact me if you would like more added.

One difference from the LPSolve C library, is that the golp columns are always zero-based.

The Go code of golp is MIT licensed, but LPSolve itself is licensed under the LGPL. This roughly means that you can include golp in a closed-source project as long as you do not modify LPSolve itself and you use dynamic linking to access LPSolve (and provide a way for someone to link your program to a different version of LPSolve). For the legal details: http://lpsolve.sourceforge.net/5.0/LGPL.htm

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type ConstraintType 

type ConstraintType int

ConstraintType can be less than (golp.LE), greater than (golp.GE) or equal (golp.EQ) 

const (
	LE ConstraintType // LE == 1
	GE                // GE == 2
	EQ                // EQ == 3
)

Contraint type constants

func (ConstraintType) String 

func (t ConstraintType) String() string

type Entry 

type Entry struct {
	Col int
	Val float64
}

Entry is for sparse constraint or objective function rows

type LP 

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

LP stores a linear (or mixed integer) programming problem

func NewLP 

func NewLP(rows, cols int) *LP

NewLP create a new linear program structure with specified number of rows and columns. The underlying C data structure's memory will be freed in a Go finalizer, so there is no need to explicitly deallocate it.

func (*LP) AddConstraint 

func (l *LP) AddConstraint(row []float64, ct ConstraintType, rightHand float64) error

AddConstraint adds a constraint to the linear program. This (unlike the LPSolve C function), expects the data in the row param to start at index 0 for the first column. See http://lpsolve.sourceforge.net/5.5/add_constraint.htm

func (*LP) AddConstraintSparse 

func (l *LP) AddConstraintSparse(row []Entry, ct ConstraintType, rightHand float64) error

AddConstraintSparse adds a constraint row by specifying only the non-zero entries. Entries column indices are zero-based. See http://lpsolve.sourceforge.net/5.5/add_constraint.htm

func (*LP) ColName 

func (l *LP) ColName(col int) string

ColName gives a column name, index is zero-based.

func (*LP) Copy 

func (l *LP) Copy() *LP

func (*LP) DualResult 

func (l *LP) DualResult(index int) float64

DualResult retrieves dual variable aka reduced costs for given index. DualResult should be called only after Solve() is successful. Duals indexing starts from 0. See https://lpsolve.sourceforge.net/5.5/get_sensitivity_rhs.htm

func (*LP) Duals 

func (l *LP) Duals() []float64

Duals retrieves all dual variable aka reduced costs. Duals should be called only after Solve() is successful. See https://lpsolve.sourceforge.net/5.5/get_sensitivity_rhs.htm This is not using `C.get_dual_solution()` because of suspicion of memory corruption via the pointer that needs to be passed in. See details at https://github.com/draffensperger/golp/issues/22

func (*LP) GetPresolveLoops 

func (l *LP) GetPresolveLoops() int

GetPresolveLoops determines optimal number of loops for pre solve. See: http://lpsolve.sourceforge.net/5.5/get_presolveloops.htm

func (*LP) IsBinary 

func (l *LP) IsBinary(col int) bool

IsBinary returns whether the given column must take a binary (0 or 1) value See http://lpsolve.sourceforge.net/5.5/is_binary.htm

func (*LP) IsInt 

func (l *LP) IsInt(col int) bool

IsInt returns whether the given column must take an integer value See http://lpsolve.sourceforge.net/5.5/is_int.htm

func (*LP) NumCols 

func (l *LP) NumCols() int

NumCols returns the number of columns (variables) in the linear program. See http://lpsolve.sourceforge.net/5.5/get_Ncolumns.htm

func (*LP) NumRows 

func (l *LP) NumRows() int

NumRows returns the number of rows (constraints) in the linear program. See http://lpsolve.sourceforge.net/5.5/get_Nrows.htm

func (*LP) Objective 

func (l *LP) Objective() float64

Objective gives the value of the objective function of the solved linear program. See http://lpsolve.sourceforge.net/5.5/get_objective.htm

func (*LP) SetAddRowMode 

func (l *LP) SetAddRowMode(addRowMode bool)

SetAddRowMode specifies whether adding by row (true) or by column (false) performs best. By default NewLP sets this for adding by row to perform best. See http://lpsolve.sourceforge.net/5.5/set_add_rowmode.htm

func (*LP) SetBinary 

func (l *LP) SetBinary(col int, mustBeBinary bool)

SetBinary specifies that the given column must take a binary (0 or 1) value See http://lpsolve.sourceforge.net/5.5/set_binary.htm

func (*LP) SetBounds 

func (l *LP) SetBounds(col int, lower, upper float64)

SetBounds sets the lower and upper bounds for the given column. By default, columns have a lower bound of 0 and an upper bound of +infinity. See http://lpsolve.sourceforge.net/5.5/set_bounds.htm

func (*LP) SetColName 

func (l *LP) SetColName(col int, name string)

SetColName changes a column name. Unlike the LPSolve C library, col is zero-based

func (*LP) SetInt 

func (l *LP) SetInt(col int, mustBeInt bool)

SetInt specifies that the given column must take an integer value. This triggers LPSolve to use branch-and-bound instead of simplex to solve. See http://lpsolve.sourceforge.net/5.5/set_int.htm

func (*LP) SetMaximize 

func (l *LP) SetMaximize()

SetMaximize will set the objective function to maximize instead of minimizing by default. and http://lpsolve.sourceforge.net/5.5/set_maxim.htm

func (*LP) SetObjFn 

func (l *LP) SetObjFn(row []float64)

SetObjFn changes the objective function. Row indices are zero-based. See http://lpsolve.sourceforge.net/5.5/set_obj_fn.htm

func (*LP) SetPresolve 

func (l *LP) SetPresolve(level PresolveType, maxLoops int)

SetPresolve specifies whether pre solve should be used to try to simplify problem, by default it is set to not to perform pre solve, level specifies type of pre solve and maxLoops the maximum number of times pre solve may be done (use 0 to determine number of pre solve loops automatically by get_presolveloop()). For more info see: http://lpsolve.sourceforge.net/5.5/set_presolve.htm

func (*LP) SetTimeout 

func (l *LP) SetTimeout(timeoutSecond int)

SetTimeout sets the timeout in seconds for the solver. The default timeout is 0, resulting in no timeout. If a timout occurs, then solve will return SUBOPTIMAL or TIMEOUT. See http://lpsolve.sourceforge.net/5.5/set_timeout.htm

func (*LP) SetUnbounded 

func (l *LP) SetUnbounded(col int)

SetUnbounded specifies that the given column has a lower bound of -infinity and an upper bound of +infinity. (By default, columns have a lower bound of 0 and an upper bound of +infinity.) See http://lpsolve.sourceforge.net/5.5/set_unbounded.htm

func (*LP) SetVerboseLevel 

func (l *LP) SetVerboseLevel(level VerboseLevel)

SetVerboseLevel changes the output verbose level (golp defaults it to IMPORTANT). See http://lpsolve.sourceforge.net/5.5/set_verbose.htm

func (*LP) Solve 

func (l *LP) Solve() SolutionType

Solve the linear (or mixed integer) program and return the solution type See http://lpsolve.sourceforge.net/5.5/solve.htm

func (*LP) Variables 

func (l *LP) Variables() []float64

Variables return the values for the variables of the solved linear program See http://lpsolve.sourceforge.net/5.5/get_variables.htm

func (*LP) WriteToStdout 

func (l *LP) WriteToStdout()

WriteToStdout writes a representation of the linear program to standard out See http://lpsolve.sourceforge.net/5.5/write_lp.htm

func (*LP) WriteToString 

func (l *LP) WriteToString() string

WriteToString returns a representation of the linear program as a string

type PresolveType 

type PresolveType int

PresolveType specifies type of presolve, see http://lpsolve.sourceforge.net/5.5/set_presolve.htm 

const (
	NONE        PresolveType = 0
	ROWS        PresolveType = 1
	COLS        PresolveType = 2
	LINDEP      PresolveType = 4
	SOS         PresolveType = 32
	REDUCEMIP   PresolveType = 64
	KNAPSACK    PresolveType = 128
	ELIMEQ2     PresolveType = 256
	IMPLIEDFREE PresolveType = 512
	REDUCEGCD   PresolveType = 1024
	PROBEFIX    PresolveType = 2048
	PROBEREDUCE PresolveType = 4096
	ROWDOMANITE PresolveType = 8192
	COLDOMINATE PresolveType = 16384
	MERGEROWS   PresolveType = 32768
	COLFIXDUAL  PresolveType = 131072
	BOUNDS      PresolveType = 262144
	DUALS       PresolveType = 524288
	SENSDUALS   PresolveType = 1048576
)

Presolve types

func (PresolveType) String 

func (level PresolveType) String() string

type SolutionType 

type SolutionType int

SolutionType represents the result type. 

const (
	NOMEMORY    SolutionType = -2
	OPTIMAL     SolutionType = 0
	SUBOPTIMAL  SolutionType = 1
	INFEASIBLE  SolutionType = 2
	UNBOUNDED   SolutionType = 3
	DEGENERATE  SolutionType = 4
	NUMFAILURE  SolutionType = 5
	USERABORT   SolutionType = 6
	TIMEOUT     SolutionType = 7
	PROCFAIL    SolutionType = 10
	PROCBREAK   SolutionType = 11
	FEASFOUND   SolutionType = 12
	NOFEASFOUND SolutionType = 13
)

Constants for the solution result type. See http://lpsolve.sourceforge.net/5.5/solve.htm

func (SolutionType) String 

func (t SolutionType) String() string

type VerboseLevel 

type VerboseLevel int

VerboseLevel represents different verbose levels, see http://lpsolve.sourceforge.net/5.1/set_verbose.htm 

const (
	NEUTRAL  VerboseLevel = iota // NEUTRAL == 0
	CRITICAL                     // CRITICAL == 1
	SEVERE
	IMPORTANT
	NORMAL
	DETAILED
	FULL
)

Verbose levels

func (VerboseLevel) String 

func (level VerboseLevel) String() string

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.