mip

package
v0.20.0 Latest Latest
Warning

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

 Go to latest Published: Oct 5, 2022 License: Apache-2.0 Imports: 2 Imported by: 0

Documentation

Overview

Package mip provides a general interface for solving mixed integer linear optimization problems using a variety of back-end solvers. The base interface is the Model which is a collection of variables, constraints and an objective. The interface Solver is constructed by mip.NewSolver. The solver can be invoked using Solver.Solve and returns a Solution.

A new Model is created: 

d := mip.NewModel()

Var instances are created and added to the model: 

x := d.NewFloat(0.0, 100.0)
y := d.NewInt(0, 100)

Constraint instances are created and added to the model: 

c1 := d.NewConstraint(mip.GreaterThanOrEqual, 1.0)
c1.NewTerm(-2.0, x)
c1.NewTerm(2.0, y)

c2 := d.NewConstraint(mip.LessThanOrEqual, 13.0)
c2.NewTerm(-8.0, x)
c2.NewTerm(10.0, y)

The Objective is specified: 

d.Objective().SetMaximize()
d.Objective().NewTerm(1.0, x)
d.Objective().NewTerm(1.0, y)

A Solver is created and invoked to produce a Solution: 

solver, _ := mip.NewSolver("backend_solver_identifier", mipModel)
solution, _ := solver.Solve(mip.DefaultSolverOptions())

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Bool added in v0.20.0 

type Bool interface {
	Int
	// contains filtered or unexported methods
}

Bool a Var which can take two values, zero or one. A bool variable is also an int variable which can have two values zero and one.

type Constraint 

type Constraint interface {
	// Name returns assigned name. If no name has been set it will return
	// a unique auto-generated name.
	Name() string
	// NewTerm adds a term to the invoking constraint, invoking this API
	// multiple times for the same variable will take the sum of coefficients
	// of earlier added terms for that variable
	//
	// 		m := mip.NewModel()
	//
	// 		x := m.NewFloat(10.0, 100.0)
	//
	// 		c := m.NewConstraint(mip.LessThanOrEqual, 123.4)
	// 		c.NewTerm(1.0, x)  	 // results in 1.0 * x <= 123.4 in solver
	// 		c.NewTerm(2.0, x)    // results in 3.0 * x <= 123.4 in solver
	NewTerm(coefficient float64, variable Var) Term
	// RightHandSide returns the right-hand side of the invoking constraint.
	RightHandSide() float64
	// Sense returns the sense of the invoking constraint.
	Sense() Sense
	// SetName assigns name to invoking constraint
	SetName(name string)
	// Term returns a term for variable with the sum of all coefficients of
	// defined terms for variable. The second return argument defines how many
	// terms have been defined on the objective for variable.
	Term(variable Var) (Term, int)
	// Terms returns a copy slice of terms of the invoking constraint,
	// each variable is reported once. If the same variable has been
	// added multiple times the sum of coefficients is reported for that
	// variable.
	Terms() Terms
}

Constraint specifies a relation between variables a solution has to comply with. A constraint consists out of terms, a sense and a right hand side.

For example: 

2.5 * x + 3.5 * y <= 10.0

The less than operator is the sense The value 10.0 is the right hand side 

2.5 * x and 3.5 * y are 2 terms in this example
Example (Equal) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	c := model.NewConstraint(mip.Equal, 1.0)

	fmt.Println(c.Sense())
	fmt.Println(c.RightHandSide())
	fmt.Println(c)
}

Output:

1
1
= 1
Example (GreaterThanEqual) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	c := model.NewConstraint(mip.GreaterThanOrEqual, 1.0)

	fmt.Println(c.Sense())
	fmt.Println(c.RightHandSide())
	fmt.Println(c)
}

Output:

2
1
>= 1
Example (LessThanOrEqual) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	c := model.NewConstraint(mip.LessThanOrEqual, 1.0)
	c.SetName("constraint")
	fmt.Println(c.Sense())
	fmt.Println(c.RightHandSide())
	fmt.Println(c)
	fmt.Println(c.Name())
}

Output:

0
1
<= 1
constraint
Example (Terms) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	v := model.NewBool()
	c := model.NewConstraint(mip.Equal, 1.0)

	t1 := c.NewTerm(1.0, v)
	t2 := c.NewTerm(2.0, v)

	fmt.Println(t1.Var().Index())
	fmt.Println(t1.Coefficient())
	fmt.Println(t2.Coefficient())
	fmt.Println(len(c.Terms()))
	fmt.Println(c.Terms()[0].Coefficient())
	fmt.Println(c)
	fmt.Println(c.Term(v))
}

Output:

0
1
2
1
3
3 B0 = 1
3 B0 2

type Constraints 

type Constraints []Constraint

Constraints slice of Constraint instances.

type Float added in v0.20.0 

type Float interface {
	Var
	// contains filtered or unexported methods
}

Float a Var which can take any value in an interval.

type FloatSolverParameterSetting 

type FloatSolverParameterSetting interface {
	GetSolverParameter
	Value() float64
}

FloatSolverParameterSetting interface for setting of type float64.

type FloatSolverParameterSettings 

type FloatSolverParameterSettings []FloatSolverParameterSetting

FloatSolverParameterSettings slice of FloatSolverParameterSetting.

type GetSolverParameter 

type GetSolverParameter interface {
	SolverParameter() SolverParameter
}

GetSolverParameter interface to retrieve a solver parameter.

type Int added in v0.20.0 

type Int interface {
	Var
	// contains filtered or unexported methods
}

Int a Var which can take any integer value in an interval.

type IntSolverParameterSetting 

type IntSolverParameterSetting interface {
	GetSolverParameter
	Value() int64
}

IntSolverParameterSetting interface for setting of type int64.

type IntSolverParameterSettings 

type IntSolverParameterSettings []IntSolverParameterSetting

IntSolverParameterSettings slice of IntSolverParameterSetting.

type Model 

type Model interface {
	// Constraints returns a copy slice of all constraints.
	Constraints() Constraints
	// NewBool adds a bool variable to the invoking model,
	// returns the newly constructed variable.
	NewBool() Bool
	// NewFloat adds a float var with bounds [lowerBound,
	// upperBound] to the invoking model, returns the newly constructed
	// var.
	NewFloat(
		lowerBound float64,
		upperBound float64,
	) Float
	// NewInt adds an integer var with bounds [loweBound,
	// upperBound] to the invoking model, returns the newly constructed
	// var.
	NewInt(
		lowerBound int64,
		upperBound int64,
	) Int
	// NewConstraint adds a constraint with sense and right-hand-side value rhs
	// to the invoking model. All terms for existing and future variables
	// are initially zero. Returns the newly constructed constraint.
	// A constraint where all terms remain zero is ignored by the solver.
	NewConstraint(sense Sense, rhs float64) Constraint
	// Objective returns the objective of the model.
	Objective() Objective
	// Vars returns a copy slice of all vars.
	Vars() Vars
}

Model manages the variables, constraints and objective.

Example (Empty) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	fmt.Println(len(model.Constraints()))
	fmt.Println(len(model.Vars()))
	fmt.Println(len(model.Objective().Terms()))
	fmt.Println(model.Objective().IsMaximize())
	fmt.Println(model)
}

Output:

0
0
0
false
minimize
Example (Queries) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	model.NewBool()
	model.NewFloat(1.0, 2.0)
	model.NewBool()
	model.NewConstraint(mip.Equal, 0.0)

	fmt.Println(len(model.Vars()))
	fmt.Println(len(model.Constraints()))
	fmt.Println(model)
}

Output:

3
1
minimize
      0: = 0
      0: B0 [0, 1]
      1: F1 [1, 2]
      2: B2 [0, 1]

func NewModel 

func NewModel() Model

NewModel creates an empty MIP model.

type Objective 

type Objective interface {
	// IsMaximize return true if the invoking objective is a maximization
	// objective.
	IsMaximize() bool
	// NewTerm adds a term to the invoking objective, invoking this API
	// multiple times for the same variable will take the sum of coefficients
	// of earlier added terms for that variable
	//
	// 		m := mip.NewModel()
	// 		x := m.NewFloat(10.0, 100.0)
	//
	// 		m.Objective().SetMaximize()			// results in: maximize -
	// 		m.Objective().NewTerm(1.0, x)		// results in: maximize 1.0 * x
	// 		m.Objective().NewTerm(2.0, x)		// results in: maximize 3.0 * x
	NewTerm(coefficient float64, variable Var) Term
	// SetMaximize sets the invoking objective to be a maximization objective.
	SetMaximize()
	// SetMinimize sets the invoking objective to be a minimization objective.
	SetMinimize()
	// Term returns a term for variable with the sum of all coefficients of
	// defined terms for variable. The second return argument defines how many
	// terms have been defined on the objective for variable.
	Term(variable Var) (Term, int)
	// Terms returns a copy slice of terms of the invoking objective,
	// each variable is reported once. If the same variable has been
	// added multiple times the sum of coefficients is reported for that
	// variable. The order of the terms is not specified and is not guaranteed
	// to be the same from one invocation to the next.
	Terms() Terms
}

Objective specifies the objective of the model. An objective consists out of terms and a specification if it should be maximized or minimized.

For example: 

maximize 2.5 * x + 3.5 * y

2.5 * x and 3.5 * y are 2 terms in this example.

Example (Sense) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	model.Objective().SetMaximize()

	fmt.Println(model.Objective().IsMaximize())
	fmt.Println(model.Objective())

	model.Objective().SetMinimize()

	fmt.Println(model.Objective().IsMaximize())
	fmt.Println(model.Objective())
}

Output:

true
maximize
false
minimize
Example (Terms) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	v1 := model.NewBool()
	v2 := model.NewBool()

	fmt.Println(len(model.Objective().Terms()))

	t1 := model.Objective().NewTerm(2.0, v1)
	fmt.Println(t1)
	t2 := model.Objective().NewTerm(1.0, v1)
	fmt.Println(t2)
	t3 := model.Objective().NewTerm(3.0, v2)
	fmt.Println(t3)

	fmt.Println(t1.Var().Index())
	fmt.Println(t1.Coefficient())

	fmt.Println(t2.Var().Index())
	fmt.Println(t2.Coefficient())

	fmt.Println(t3.Var().Index())
	fmt.Println(t3.Coefficient())

	terms := model.Objective().Terms()
	fmt.Println(len(terms))
	for _, term := range terms {
		fmt.Println(term.Var(), term.Coefficient())
	}
	fmt.Println("isMaximize: ", model.Objective().IsMaximize())
}

Output:

0
2 B0
1 B0
3 B1
0
2
0
1
1
3
2
B0 3
B1 3
isMaximize:  false
Example (TermsToString) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	m := mip.NewModel()
	x0 := m.NewBool()
	x1 := m.NewBool()
	x2 := m.NewBool()
	x3 := m.NewBool()
	z := m.Objective()
	z.NewTerm(3, x2)
	z.NewTerm(2, x1)
	z.NewTerm(1, x0)
	fmt.Println(z)
	fmt.Println(z.Term(x0))
	z.NewTerm(1, x0)
	fmt.Println(z.Term(x0))
	fmt.Println(z.Term(x3))
}

Output:

minimize   1 B0 + 2 B1 + 3 B2
1 B0 1
2 B0 2
0 B3 0

type Sense 

type Sense int64

Sense defines the constraint operator between the left-hand-side and the right-hand-side. 

const (
	// LessThanOrEqual is used to define a less than or equal constraint
	// 		c, _ := d.NewConstraint(mip.LessThanOrEqual, 123.4)
	//
	// 		c.NewTerm(1.0, x)  	 // results in 1.0 * x <= 123.4 in solver
	LessThanOrEqual Sense = iota
	// Equal is used to define an equality constraint
	// 		c, _ := d.NewConstraint(mip.Equal, 123.4)
	//
	// 		c.NewTerm(1.0, x)  	 // results in 1.0 * x = 123.4 in solver
	Equal
	// GreaterThanOrEqual is used to define a greater or equal constraint
	// 		c, _ := d.NewConstraint(mip.	GreaterThanOrEqual, 123.4)
	//
	// 		c.NewTerm(1.0, x)  	 // results in 1.0 * x >= 123.4 in solver
	GreaterThanOrEqual
)

Sense of a Constraint.

type Solution 

type Solution interface {
	// HasValues returns true if the solver was able to associate values with
	// variables.
	HasValues() bool
	// IsInfeasible returns true if the solver has proven that the model
	// defines an infeasible solution, otherwise returns false.
	IsInfeasible() bool
	// IsNumericalFailure returns true if the solver encountered a numerical
	// failure, otherwise returns false. Numerical failures can have different
	// causes and depend on the underlying solver provider.
	IsNumericalFailure() bool
	// IsOptimal returns true if the solver has proven that the solution
	// is one of the optimal solutions, otherwise returns false.
	IsOptimal() bool
	// IsSubOptimal returns true if the solver sub-optimal conform the
	// model of the underlying solver, otherwise false.
	IsSubOptimal() bool
	// IsTimeOut returns true if the solver returned due to a time limit
	// before reaching a conclusion, otherwise returns true.
	IsTimeOut() bool
	// IsUnbounded returns true if the solver proved the solution is
	// unbounded, otherwise returns false. An unbounded solution is
	// a solution that can be improved by changing a variable in a
	// direction it is not limited by bounds.
	IsUnbounded() bool
	// ObjectiveValue return the value of the objective, the value should only
	// be used if HasValues returns true. Returns 0.0 if HasValues is false.
	ObjectiveValue() float64
	// RunTime returns the duration it took for the Solver.Solve to return
	// this solution
	RunTime() time.Duration
	// Value returns the value the solver has associated with the variable
	// in the invoking solution. the value should only be used if HasValues
	// returns true. Returns math.MaxFloat64 if HasValues is false.
	Value(variable Var) float64
}

Solution contains the results of a Solver.Solve invocation.

type SolveOptions 

type SolveOptions interface {
	// FloatParameters returns all float parameter settings.
	FloatParameters() FloatSolverParameterSettings
	// GetFloatParameter returns value set for parameter, returns error if no
	// such parameter has been set.
	GetFloatParameter(parameter SolverParameter) (float64, error)
	// GetIntParameter returns value set for parameter, returns error if no
	// such parameter has been set.
	GetIntParameter(parameter SolverParameter) (int64, error)
	// GetStringParameter returns value set for parameter, returns error if no
	// such parameter has been set.
	GetStringParameter(parameter SolverParameter) (string, error)
	// IntParameters returns all int parameter settings.
	IntParameters() IntSolverParameterSettings
	// MaximumDuration returns maximum duration of a Solver.Solve invocation.
	MaximumDuration() time.Duration
	// MIPGapAbsolute returns the absolute gap stopping value. If the problem
	// is an integer problem the solver will stop if the gap between the relaxed
	// problem and the best found integer problem is less than this value.
	MIPGapAbsolute() float64
	// MIPGapRelative returns the relative gap stopping value. If the problem
	// is an integer problem the solver will stop if the relative gap between
	// the relaxed problem and the best found integer problem is less than
	// this value.
	MIPGapRelative() float64
	// SetFloatParameter specifies the value to use for parameter, this is
	// back-end-solver specific.
	SetFloatParameter(parameter SolverParameter, value float64)
	// SetIntParameter specifies the value to use for parameter, this is
	// back-end-solver specific.
	SetIntParameter(parameter SolverParameter, value int64)
	// SetMaximumDuration specifies the maximum duration of a Solver.Solve
	// invocation.
	SetMaximumDuration(duration time.Duration) error
	// SetMIPGapAbsolute specifies the absolute gap stopping value, only
	// used in case the problem is an integer solution, raises an error if
	// value is not strictly positive (> 0).
	SetMIPGapAbsolute(value float64) error
	// SetMIPGapRelative specifies the relative gap stopping value, only
	// used in case the problem is an integer solution, raises an error if
	// value is less than zero or larger or equal to one.
	SetMIPGapRelative(value float64) error
	// SetStringParameter specifies the value to use for parameter, this is
	// back-end-solver specific.
	SetStringParameter(parameter SolverParameter, value string)
	// SetVerbosity specifies the verbosity level of the underlying
	// back-end solver. Forwards output to std out.
	SetVerbosity(verbosity Verbosity)
	// StringParameters returns all string parameter settings
	StringParameters() StringSolverParameterSettings
	// Verbosity returns the configured verbosity level of the
	// underlying back-end solver.
	Verbosity() Verbosity
}

SolveOptions interface to options for back-end solver.

Example (Change) 
package main

import (
	"fmt"
	"time"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	solveOptions := mip.NewSolveOptions()
	solveOptions.SetVerbosity(mip.High)
	err := solveOptions.SetMIPGapAbsolute(1.23)
	if err != nil {
		panic(err)
	}
	err = solveOptions.SetMIPGapRelative(0.5)
	if err != nil {
		panic(err)
	}
	err = solveOptions.SetMaximumDuration(time.Minute)
	if err != nil {
		panic(err)
	}

	fmt.Println(solveOptions.Verbosity())
	fmt.Println(solveOptions.MIPGapAbsolute())
	fmt.Println(solveOptions.MIPGapRelative())
	fmt.Println(solveOptions.MaximumDuration())
}

Output:

3
1.23
0.5
1m0s
Example (Default) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	solveOptions := mip.NewSolveOptions()

	fmt.Println(solveOptions.Verbosity())
	fmt.Println(solveOptions.MIPGapAbsolute())
	fmt.Println(solveOptions.MIPGapRelative())
	fmt.Println(solveOptions.MaximumDuration())
}

Output:

0
0
0
10m0s

func NewSolveOptions 

func NewSolveOptions() SolveOptions

NewSolveOptions returns default solver options.

type Solver 

type Solver interface {
	// Solve is the entrypoint to solve the model associated with
	// the invoking solver. Returns a solution when the invoking solver
	// reaches a conclusion.
	Solve(options SolveOptions) (Solution, error)
}

Solver exposes an API to run a MIP solver 

		model := mip.NewModel()

 	// build the model

		provider := "my_favorite_solver"

		solver, err := NewSolver(provider, model)

		solution, err := solver.Solve(mip.DefaultSolverOptions())

func NewSolver 

func NewSolver(provider SolverProvider, model Model) (Solver, error)

NewSolver returns a new Solver implemented by the given provider.

type SolverParameter 

type SolverParameter int

SolverParameter identifier for parameters in the back-end solver.

type SolverProvider 

type SolverProvider string

SolverProvider identifier for a back-end solver.

type StringSolverParameterSetting 

type StringSolverParameterSetting interface {
	GetSolverParameter
	Value() string
}

StringSolverParameterSetting interface for setting of type string.

type StringSolverParameterSettings 

type StringSolverParameterSettings []StringSolverParameterSetting

StringSolverParameterSettings slice of StringSolverParameterSetting.

type Term 

type Term interface {
	// Coefficient returns the coefficient value of the invoking term.
	Coefficient() float64
	// Var returns the var of the invoking term.
	Var() Var
}

Term is the building block of a constraint and an objective. A term consist of a coefficient and a var and should be interpreted as the product of coefficient and the var in the context of the constraint or objective.

type Terms 

type Terms []Term

Terms is a slice of Term instances.

type Var 

type Var interface {
	// Index is a unique number assigned to the var. The index corresponds
	// to the location in the slice returned by Model.Variables().
	Index() int
	// IsBool returns true if the invoking variable is a bool variable,
	// otherwise it returns false.
	IsBool() bool
	// IsFloat returns true if the invoking variable is a float
	// variable otherwise false.
	IsFloat() bool
	// IsInt returns true if the invoking variable is an int variable
	// otherwise false.
	IsInt() bool
	// LowerBound returns the lowerBound of the invoking variable.
	//
	// Lower bounds of variables are limited by the lower bounds of the
	// underlying solver technology. The lower bound used will be the maximum
	// of the specification and the lower bound of the solver used.
	LowerBound() float64
	// Name returns assigned name. If no name has been set it will return
	// a unique auto-generated name.
	Name() string
	// SetName assigns name to invoking var
	SetName(name string)
	// UpperBound returns the upperBound of the invoking variable.
	//
	// Upper bounds of variables are limited by the upper bounds of the
	// underlying solver technology. The upper bound used will be the minimum
	// of the specification and the upper bound of the solver used.
	UpperBound() float64
}

Var represents the entities on which the solver has to make a decision without violating constraints and while optimizing the objective. Vars can be of a certain type, bool, float or int.

Float vars can take a value of a float quantity Int vars are vars that must take an integer value (0, 1, 2, ...) Bool vars can take two values, zero or one.

Example (Bool) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	v := model.NewBool()

	fmt.Println(v.LowerBound())
	fmt.Println(v.UpperBound())
	fmt.Println(v.IsFloat())
	fmt.Println(v.IsInt())
	fmt.Println(v.IsBool())
	fmt.Println(v)
}

Output:

0
1
false
true
true
B0
Example (Float) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	v := model.NewFloat(-1.0, 1.0)

	fmt.Println(v.LowerBound())
	fmt.Println(v.UpperBound())
	fmt.Println(v.IsFloat())
	fmt.Println(v.IsInt())
	fmt.Println(v.IsBool())
	fmt.Println(v)
}

Output:

-1
1
true
false
false
F0
Example (Int) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	v := model.NewInt(-1, 1)

	fmt.Println(v.LowerBound())
	fmt.Println(v.UpperBound())
	fmt.Println(v.IsFloat())
	fmt.Println(v.IsInt())
	fmt.Println(v.IsBool())
	fmt.Println(v)
	v.SetName("v")
	fmt.Println(v)
}

Output:

-1
1
false
true
false
I0
v
Example (Vars) 
package main

import (
	"fmt"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	model := mip.NewModel()

	v0 := model.NewBool()
	v1 := model.NewInt(-1, 1)
	v2 := model.NewFloat(-1.0, 1.0)

	fmt.Println(v0.Index())
	fmt.Println(v1.Index())
	fmt.Println(v2.Index())
	fmt.Println(len(model.Vars()))
}

Output:

0
1
2
3

type Vars 

type Vars []Var

Vars is a slice of Var instances.

type Verbosity added in v0.20.0 

type Verbosity int

Verbosity specifies the level of verbosity of the back-end solver. 

const (
	// Off logs nothing.
	Off Verbosity = iota
	// Low logs essentials, depends on the back-end solver.
	Low
	// Medium logs essentials plus high level events,
	// depends on the back-end solver.
	Medium
	// High logs everything the underlying logs,
	// depends on the back-end solver.
	High
)

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.