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