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 ¶
- func Format(options any, solution any, solverSolution Solution) schema.Output
- type Bool
- type Constraint
- type Constraints
- type ControlOptions
- type CustomResultStatistics
- type Float
- type GapOptions
- type Int
- type MIPOptions
- type Model
- type Objective
- type QuadraticTerm
- type QuadraticTerms
- type Sense
- type Solution
- type SolveOptions
- type Solver
- type SolverProvider
- type Term
- type Terms
- type TypedControlOption
- type TypedControlOptions
- type Var
- type Vars
- type Verbosity
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
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 ControlOptions ¶ added in v0.30.0
type ControlOptions struct {
Bool string `` /* 175-byte string literal not displayed */
Float string `` /* 178-byte string literal not displayed */
Int string `` /* 172-byte string literal not displayed */
String string `` /* 181-byte string literal not displayed */
}
ControlOptions allow the user to define solver-specific parameters. The parameters' names and types must be known beforehand so that the correct type is used.
func (ControlOptions) MarshalJSON ¶ added in v0.30.0
func (controlOptions ControlOptions) MarshalJSON() ([]byte, error)
MarshalJSON implements the json.Marshaler interface.
func (ControlOptions) ToTyped ¶ added in v0.30.0
func (controlOptions ControlOptions) ToTyped() (*TypedControlOptions, error)
ToTyped converts the string-based control options into fully typed options.
type CustomResultStatistics ¶ added in v0.26.0
type CustomResultStatistics struct {
// Constraints in the matrix, i.e. the number of constraints.
Constraints int `json:"constraints,omitempty"`
// Provider of the solution.
Provider SolverProvider `json:"provider,omitempty"`
// Status of the solution.
Status string `json:"status,omitempty"`
// Variables in the matrix, i.e. the number of variables.
Variables int `json:"variables,omitempty"`
}
CustomResultStatistics is an example of custom statistics that can be added to the output and used in experiments.
func DefaultCustomResultStatistics ¶ added in v0.26.0
func DefaultCustomResultStatistics(model Model, solution Solution) CustomResultStatistics
DefaultCustomResultStatistics creates default custom statistics for a given solution.
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 GapOptions ¶ added in v0.30.0
type GapOptions struct {
// Absolute gap.
Absolute float64 `` /* 228-byte string literal not displayed */
// Relative gap.
Relative float64 `` /* 235-byte string literal not displayed */
}
GapOptions specifies the gap stopping criteria.
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 MIPOptions ¶ added in v0.30.0
type MIPOptions struct {
// Gap stopping criteria.
Gap GapOptions `json:"gap" usage:"Gap stopping criteria."`
}
MIPOptions are options specific to MIP problems. LP problems do not use these options.
type Model ¶
type Model interface {
// Constraints returns a copy slice of all constraints.
Constraints() Constraints
// Copy returns a copy of the model.
Copy() Model
// 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 (Copy) ¶
package main
import (
"fmt"
"github.com/nextmv-io/sdk/mip"
)
func main() {
model := mip.NewModel()
model.Objective().SetMaximize()
model.NewBool()
model.NewFloat(1.0, 2.0)
model.NewBool()
model.NewConstraint(mip.Equal, 0.0)
copyModel := model.Copy()
fmt.Println(len(copyModel.Vars()))
fmt.Println(len(copyModel.Constraints()))
fmt.Println(copyModel)
}
Output: 3 1 maximize 0: = 0 0: B0 [0, 1] 1: F1 [1, 2] 2: B2 [0, 1]
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]
type Objective ¶
type Objective interface {
// IsLinear returns true if the invoking objective is a linear function.
IsLinear() bool
// IsMaximize returns true if the invoking objective is a maximization
// objective.
IsMaximize() bool
// IsQuadratic returns true if the invoking objective is a quadratic function.
IsQuadratic() 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
// NewQuadraticTerm adds a new quadratic term to the invoking objective,
// invoking this API multiple times for the same variables will take the sum
// of coefficients of earlier added terms for that variable.
//
// m := mip.NewModel()
// x1 := m.NewFloat(10.0, 100.0)
// x2 := m.NewFloat(10.0, 100.0)
//
// m.Objective().SetMaximize()
// // results in: maximize -
// m.Objective().NewQuadraticTerm(1.0, x1, x1)
// // results in: maximize 1.0 * x1^2
// m.Objective().NewQuadraticTerm(1.0, x1, x2)
// // results in: maximize 1.0 * x1^2 + x1x2
// m.Objective().NewQuadraticTerm(1.0, x2, x1)
// // results in: maximize 1.0 * x1^2 + 2.0 * x1x2
NewQuadraticTerm(coefficient float64, variable1, variable2 Var) QuadraticTerm
// 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 a given variable together with the sum of the
// coefficients of all terms referencing that variable. The second return
// argument defines how many terms have been defined on the objective for
// the given 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
// QuadraticTerm returns a quadratic term for a given pair of variables
// together with the sum of the coefficients of all quadratic terms
// referencing that variable. The second return argument defines how many
// quadratic terms have been defined on the objective the given pair of
// variables.
QuadraticTerm(variable1, variable2 Var) (QuadraticTerm, int)
// QuadraticTerms returns a copy slice of quadratic terms of the invoking
// objective, each variable pair is reported once. If the same pair 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.
QuadraticTerms() QuadraticTerms
}
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 QuadraticTerm ¶ added in v0.20.4
type QuadraticTerm interface {
// Coefficient returns the coefficient value of the invoking term.
Coefficient() float64
// Var1 returns the first variable.
Var1() Var
// Var2 returns the second variable.
Var2() Var
}
QuadraticTerm consists of a coefficient and two vars. It should be interpreted as the product of a coefficient and the two vars.
type QuadraticTerms ¶ added in v0.20.4
type QuadraticTerms []QuadraticTerm
QuadraticTerms is a slice of QuadraticTerm instances.
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
// Provider of the solver that produced the invoking solution.
Provider() SolverProvider
// 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 struct {
// Duration is the maximum duration of the solver. A duration limit of 0 is
// treated as infinity.
Duration time.Duration `json:"duration" usage:"Maximum duration of the solver." default:"30s"`
// Verbosity of the solver in the console.
Verbosity Verbosity `json:"verbosity" usage:"{off, low, medium, high} Verbosity of the solver in the console." default:"off"`
// MIP-specific options.
MIP MIPOptions `json:"mip" usage:"Options specific to MIP problems. Linear problems do not use these options."`
// Control options for the specific solver.
Control ControlOptions `json:"control" usage:"Options to control a specific solver, as defined by the provider."`
}
SolveOptions are options that can be cionfigured for any solver.
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 for a MIP problem.
type SolverProvider ¶
type SolverProvider string
SolverProvider identifier for a back-end solver.
const ( // Highs is the [HiGHS] open-source solver. // // [HiGHS]: https://highs.dev Highs SolverProvider = "highs" // Xpress is the [FICO Xpress] commercial solver. // // [FICO Xpress]: https://www.fico.com/en/products/fico-xpress-optimization Xpress SolverProvider = "xpress" )
type Term ¶
type Term interface {
// Coefficient returns the coefficient value of the invoking term.
Coefficient() float64
// Var returns the variable of the 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 TypedControlOption ¶ added in v0.30.0
type TypedControlOption[T string | float64 | int | bool] struct { // Name of the option. Name string `json:"name"` // Value for the option. The value's type is defined by how the control // option is instantiated. Value T `json:"value"` }
TypedControlOption defines a generic way to specify a control parameter for a solver.
type TypedControlOptions ¶ added in v0.30.0
type TypedControlOptions struct {
Bool []TypedControlOption[bool] `json:"bool"`
Float []TypedControlOption[float64] `json:"float"`
Int []TypedControlOption[int] `json:"int"`
String []TypedControlOption[string] `json:"string"`
}
TypedControlOptions is the typed equivalent to ControlOptions for configuring a solver's parameters.
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 Verbosity ¶ added in v0.20.0
type Verbosity string
Verbosity specifies the level of verbosity of the back-end solver.
const ( // Off logs nothing. Off Verbosity = "off" // Low logs essentials, depends on the back-end solver. Low Verbosity = "low" // Medium logs essentials plus high level events, // depends on the back-end solver. Medium Verbosity = "medium" // High logs everything the underlying logs, // depends on the back-end solver. High Verbosity = "high" )