goop

package module
v0.0.0-...-1318b30 Latest Latest
Warning

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

 Go to latest Published: Apr 7, 2019 License: GPL-3.0 Imports: 6 Imported by: 0

README

Goop Go Report Card Build Status Go Doc Maintainability codecov

General Linear Optimization in Go. goop provides general interface for solving mixed integer linear optimization problems using a variety of back-end solvers including LPSolve and Gurobi.

Quickstart

We are going to start with a simple example showing how goop can be used to solve integer linear programs. The example below seeks to maximize the following MIP:

maximize    x +   y + 2 z
subject to  x + 2 y + 3 z <= 4
            x +   y       >= 1
x, y, z binary

This is is the same example implemented here. Below we have implemented the model using goop and have optimized the model using the supported Gurobi solver.

package main

import (
    "fmt"
    "github.com/mit-drl/goop"
    "github.com/mit-drl/goop/solvers"
)

func main() {
    // Instantiate a new model
    m := goop.NewModel()

    // Add your variables to the model
    x := m.AddBinaryVar()
    y := m.AddBinaryVar()
    z := m.AddBinaryVar()

    // Add your constraints
    m.AddConstr(goop.Sum(x, y.Mult(2), z.Mult(3)).LessEq(goop.K(4)))
    m.AddConstr(goop.Sum(x, y).GreaterEq(goop.One))

    // Set a linear objective using your variables
    obj := goop.Sum(x, y, z.Mult(2))
    m.SetObjective(obj, goop.SenseMaximize)

    // Optimize the variables according to the model
    sol, err := m.Optimize(solvers.NewGurobiSolver())

    // Check if there is an error from the solver. No error should be returned
    // for this model
    if err != nil {
    	panic("Should not have an error")
    }

    // Print out the solution
    fmt.Println("x =", sol.Value(x))
    fmt.Println("y =", sol.Value(y))
    fmt.Println("z =", sol.Value(z))

    // Output:
    // x = 1
    // y = 0
    // z = 1
}

Installation

  1. First get the code
mkdir -p $GOPATH/github.com/mit-drl && cd $GOPATH/github.com/mit-drl
git clone https://github.com/mit-drl/goop && cd goop
  1. Next build install the dependencies
./install.sh

  1. Follow the [instructions](#Solver Notes) for your solver of choice. Note, currently only Gurobi is supported

  2. Finally build the library

go build

Note that due to a quirk with Gurobi, if you are using Ubuntu < 16.04, you must build with

go build -tags pre_xenial
  1. (Optional) Test our installation
govendor test -v +local

Solver Notes

We currently have bindings for Gurobi and LPSolve. Please follow the instructions below for using these specific solvers.

Gurobi

  • You must have Gurobi installed and have a valid license.
  • The GUROBI_HOME environment variable must be set to the home directory of your Gurobi installation

LPSolve

LPSolve is installed using the normal install procedure and should work out of the box.

Documentation

Overview

Package goop provides a general interface for solving mixed integer linear optimization problems using a variety of back-end solvers.

Index

Examples

Constants

View Source 
const (
	Zero = K(0)
	One  = K(1)
)

Integer constants represnting commonly used numbers. Makes for better readability

View Source 
const (
	SenseEqual            ConstrSense = '='
	SenseLessThanEqual                = '<'
	SenseGreaterThanEqual             = '>'
)

Different constraint senses conforming to Gurobi's encoding.

View Source 
const (
	Continuous VarType = 'C'
	Binary             = 'B'
	Integer            = 'I'
)

Multiple common variable types have been included as constants that conform to Gurobi's encoding.

Variables

This section is empty.

Functions

This section is empty.

Types

type Constr 

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

Constr represnts a linear constraint of the form x <= y, x >= y, or x == y. Constr uses a left and right hand side expressions along with a constraint sense (<=, >=, ==) to represent a generalized linear constraint

func Eq 

func Eq(lhs, rhs Expr) *Constr

Eq returns a constraint representing lhs == rhs

func GreaterEq 

func GreaterEq(lhs, rhs Expr) *Constr

GreaterEq returns a constraint representing lhs >= rhs

func LessEq 

func LessEq(lhs, rhs Expr) *Constr

LessEq returns a constraint representing lhs <= rhs

type ConstrSense 

type ConstrSense byte

ConstrSense represents if the constraint x <= y, x >= y, or x == y. For easy integration with Gurobi, the senses have been encoding using a byte in the same way Gurobi encodes the constraint senses.

type Expr 

type Expr interface {
	// NumVars returns the number of variables in the expression
	NumVars() int

	// Vars returns a slice of the Var ids in the expression
	Vars() []uint64

	// Coeffs returns a slice of the coefficients in the expression
	Coeffs() []float64

	// Constant returns the constant additive value in the expression
	Constant() float64

	// Plus adds the current expression to another and returns the resulting
	// expression
	Plus(e Expr) Expr

	// Mult multiplies the current expression to another and returns the
	// resulting expression
	Mult(c float64) Expr

	// LessEq returns a less than or equal to (<=) constraint between the
	// current expression and another
	LessEq(e Expr) *Constr

	// GreaterEq returns a greater than or equal to (>=) constraint between the
	// current expression and another
	GreaterEq(e Expr) *Constr

	// Eq returns an equality (==) constraint between the current expression
	// and another
	Eq(e Expr) *Constr
}

Expr represents a linear general expression of the form c0 * x0 + c1 * x1 + ... + cn * xn + k where ci are coefficients and xi are variables and k is a constant. This is a base interface that is implemented by single variables, constants, and general linear expressions.

func Dot 

func Dot(vs []*Var, coeffs []float64) Expr

Dot returns the dot product of a vector of variables and slice of floats.

func NewExpr 

func NewExpr(c float64) Expr

NewExpr returns a new expression with a single additive constant value, c, and no variables. Creating an expression like sum := NewExpr(0) is useful for creating new empty expressions that you can perform operatotions on later

func NewLinearExpr 

func NewLinearExpr(c float64) Expr

NewLinearExpr returns a new expression with a single additive constant value, c, and no variables.

func Sum 

func Sum(exprs ...Expr) Expr

Sum returns the sum of the given expressions. It creates a new empty expression and adds to it the given expressions.

func SumCol 

func SumCol(vs [][]*Var, col int) Expr

SumCol returns the sum of all variables in a single specified column of a variable matrix.

func SumRow 

func SumRow(vs [][]*Var, row int) Expr

SumRow returns the sum of all the variables in a single specified row of a variable matrix.

func SumVars 

func SumVars(vs ...*Var) Expr

SumVars returns the sum of the given variables. It creates a new empty expression and adds to it the given variables.

type K 

type K float64

K is a constant expression type for an MIP. K for short ¯\_(ツ)_/¯

func (K) Coeffs 

func (c K) Coeffs() []float64

Coeffs returns a slice of the coefficients in the expression. For constants, this is always nil

func (K) Constant 

func (c K) Constant() float64

Constant returns the constant additive value in the expression. For constants, this is just the constants value

func (K) Eq 

func (c K) Eq(other Expr) *Constr

Eq returns an equality (==) constraint between the current expression and another

func (K) GreaterEq 

func (c K) GreaterEq(other Expr) *Constr

GreaterEq returns a greater than or equal to (>=) constraint between the current expression and another

func (K) LessEq 

func (c K) LessEq(other Expr) *Constr

LessEq returns a less than or equal to (<=) constraint between the current expression and another

func (K) Mult 

func (c K) Mult(val float64) Expr

Mult multiplies the current expression to another and returns the resulting expression

func (K) NumVars 

func (c K) NumVars() int

NumVars returns the number of variables in the expression. For constants, this is always 0

func (K) Plus 

func (c K) Plus(e Expr) Expr

Plus adds the current expression to another and returns the resulting expression

func (K) Vars 

func (c K) Vars() []uint64

Vars returns a slice of the Var ids in the expression. For constants, this is always nil

type LinearExpr 

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

LinearExpr represents a linear general expression of the form c0 * x0 + c1 * x1 + ... + cn * xn + k where ci are coefficients and xi are variables and k is a constant

func (*LinearExpr) Coeffs 

func (e *LinearExpr) Coeffs() []float64

Coeffs returns a slice of the coefficients in the expression

func (*LinearExpr) Constant 

func (e *LinearExpr) Constant() float64

Constant returns the constant additive value in the expression

func (*LinearExpr) Eq 

func (e *LinearExpr) Eq(other Expr) *Constr

Eq returns an equality (==) constraint between the current expression and another

func (*LinearExpr) GreaterEq 

func (e *LinearExpr) GreaterEq(other Expr) *Constr

GreaterEq returns a greater than or equal to (>=) constraint between the current expression and another

func (*LinearExpr) LessEq 

func (e *LinearExpr) LessEq(other Expr) *Constr

LessEq returns a less than or equal to (<=) constraint between the current expression and another

func (*LinearExpr) Mult 

func (e *LinearExpr) Mult(c float64) Expr

Mult multiplies the current expression to another and returns the resulting expression

func (*LinearExpr) NumVars 

func (e *LinearExpr) NumVars() int

NumVars returns the number of variables in the expression

func (*LinearExpr) Plus 

func (e *LinearExpr) Plus(other Expr) Expr

Plus adds the current expression to another and returns the resulting expression

func (*LinearExpr) Vars 

func (e *LinearExpr) Vars() []uint64

Vars returns a slice of the Var ids in the expression

type Model 

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

Model represents the overall constrained linear optimization model to be solved. Model contains all the variables associated with the optimization problem, constraints, objective, and parameters. New variables can only be created using an instantiated Model.

Example (Simple)

This example shows how goop can be used to solve a simple MIP: 

// maximize    x +   y + 2 z
// subject to  x + 2 y + 3 z <= 4
//             x +   y       >= 1
// x, y, z binary

MIP being modelled is the same as in http://www.gurobi.com/documentation/7.5/examples/mip1_cpp_cpp.html 

package main

import (
	"fmt"

	"github.com/mit-drl/goop"
	"github.com/mit-drl/goop/solvers"
)

func main() {
	// Instantiate a new model
	m := goop.NewModel()

	// Add your variables to the model
	x := m.AddBinaryVar()
	y := m.AddBinaryVar()
	z := m.AddBinaryVar()

	// Add your constraints
	m.AddConstr(goop.Sum(x, y.Mult(2), z.Mult(3)).LessEq(goop.K(4)))
	m.AddConstr(goop.Sum(x, y).GreaterEq(goop.One))

	// Set a linear objective using your variables
	obj := goop.Sum(x, y, z.Mult(2))
	m.SetObjective(obj, goop.SenseMaximize)

	// Optimize the variables according to the model
	sol, err := m.Optimize(solvers.NewLPSolveSolver())

	// Check if there is an error from the solver. No error should be returned
	// for this model
	if err != nil {
		panic("Should not have an error")
	}

	// Print out the solution
	fmt.Println("x =", sol.Value(x))
	fmt.Println("y =", sol.Value(y))
	fmt.Println("z =", sol.Value(z))

}

Output:

x = 1
y = 0
z = 1

func NewModel 

func NewModel() *Model

NewModel returns a new model with some default arguments such as not to show the log and no time limit.

func (*Model) AddBinaryVar 

func (m *Model) AddBinaryVar() *Var

AddBinaryVar adds a binary variable to the model and returns said variable.

func (*Model) AddBinaryVarMatrix 

func (m *Model) AddBinaryVarMatrix(rows, cols int) [][]*Var

AddBinaryVarMatrix adds a matrix of binary variables to the model and returns the resulting slice.

func (*Model) AddBinaryVarVector 

func (m *Model) AddBinaryVarVector(num int) []*Var

AddBinaryVarVector adds a vector of binary variables to the model and returns the slice.

func (*Model) AddConstr 

func (m *Model) AddConstr(constr *Constr)

AddConstr adds a the given constraint to the model.

func (*Model) AddVar 

func (m *Model) AddVar(lower, upper float64, vtype VarType) *Var

AddVar adds a variable of a given variable type to the model given the lower and upper value limits. This variable is returned.

func (*Model) AddVarMatrix 

func (m *Model) AddVarMatrix(
	rows, cols int, lower, upper float64, vtype VarType,
) [][]*Var

AddVarMatrix adds a matrix of variables of a given type to the model with lower and upper value limits and returns the resulting slice.

func (*Model) AddVarVector 

func (m *Model) AddVarVector(
	num int, lower, upper float64, vtype VarType,
) []*Var

AddVarVector adds a vector of variables of a given variable type to the model. It then returns the resulting slice.

func (*Model) Optimize 

func (m *Model) Optimize(solver solvers.Solver) (*Solution, error)

Optimize optimizes the model using the given solver type and returns the solution or an error.

func (*Model) SetObjective 

func (m *Model) SetObjective(e Expr, sense ObjSense)

SetObjective sets the objective of the model given an expression and objective sense.

func (*Model) SetTimeLimit 

func (m *Model) SetTimeLimit(dur time.Duration)

SetTimeLimit sets the solver time limit for the model.

func (*Model) ShowLog 

func (m *Model) ShowLog(shouldShow bool)

ShowLog instructs the solver to show the log or not.

type ObjSense 

type ObjSense int

ObjSense represents whether an optimization objective is to be maximized or minimized. This implementation conforms to the Gurobi encoding 

const (
	SenseMinimize ObjSense = 1
	SenseMaximize          = -1
)

Objective senses (minimize and maximize) encoding using Gurobi's standard

type Objective 

type Objective struct {
	Expr
	// contains filtered or unexported fields
}

Objective represents an optimization objective given an expression and objective sense (maximize or minimize).

func NewObjective 

func NewObjective(e Expr, sense ObjSense) *Objective

NewObjective returns a new optimization objective given an expression and objective sense

type Solution 

type Solution struct {

	// The objective for the solution
	Objective float64

	// Whether or not the solution is within the optimality threshold
	Optimal bool

	// The optimality gap returned from the solver. For many solvers, this is
	// the gap between the best possible solution with integer relaxation and
	// the best integer solution found so far.
	Gap float64
	// contains filtered or unexported fields
}

Solution stores the solution of an optimization problem and associated metatdata

func (*Solution) IsOne 

func (s *Solution) IsOne(v *Var) bool

IsOne returns true if the value assigned to the variable is an integer, and assigned to one. This is a convenience method which should not be super trusted...

func (*Solution) Value 

func (s *Solution) Value(v *Var) float64

Value returns the value assigned to the variable in the solution

type Var 

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

Var represnts a variable in a optimization problem. The variable is identified with an uint64.

func (*Var) Coeffs 

func (v *Var) Coeffs() []float64

Coeffs returns a slice of the coefficients in the expression. For a variable, it always returns a singleton slice containing the value one.

func (*Var) Constant 

func (v *Var) Constant() float64

Constant returns the constant additive value in the expression. For a variable, it always returns zero.

func (*Var) Eq 

func (v *Var) Eq(other Expr) *Constr

Eq returns an equality (==) constraint between the current expression and another

func (*Var) GreaterEq 

func (v *Var) GreaterEq(other Expr) *Constr

GreaterEq returns a greater than or equal to (>=) constraint between the current expression and another

func (*Var) ID 

func (v *Var) ID() uint64

ID returns the ID of the variable

func (*Var) LessEq 

func (v *Var) LessEq(other Expr) *Constr

LessEq returns a less than or equal to (<=) constraint between the current expression and another

func (*Var) Lower 

func (v *Var) Lower() float64

Lower returns the lower value limit of the variable

func (*Var) Mult 

func (v *Var) Mult(c float64) Expr

Mult multiplies the current expression to another and returns the resulting expression

func (*Var) NumVars 

func (v *Var) NumVars() int

NumVars returns the number of variables in the expression. For a variable, it always returns one.

func (*Var) Plus 

func (v *Var) Plus(e Expr) Expr

Plus adds the current expression to another and returns the resulting expression.

func (*Var) Type 

func (v *Var) Type() VarType

Type returns the type of variable (continuous, binary, integer, etc)

func (*Var) Upper 

func (v *Var) Upper() float64

Upper returns the upper value limit of the variable

func (*Var) Vars 

func (v *Var) Vars() []uint64

Vars returns a slice of the Var ids in the expression. For a variable, it always returns a singleton slice with the given variable ID.

type VarType 

type VarType byte

VarType represents the type of the variable (continuous, binary, integer, etc) and uses Gurobi's encoding.

Source Files

View all Source files

Directories

Path Synopsis
gurobi

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.