Classes¶
Classes used in solver callbacks, for a bi-directional communication with the solver engine
Model¶
-
class
Model
(name='', sense='MIN', solver_name='', solver=None)¶ Mixed Integer Programming Model
This is the main class, providing methods for building, optimizing, querying optimization results and re-optimizing Mixed-Integer Programming Models.
To check how models are created please see the examples included.
Examples
>>> from mip import Model, MAXIMIZE, CBC, INTEGER, OptimizationStatus >>> model = Model(sense=MAXIMIZE, solver_name=CBC) >>> x = model.add_var(name='x', var_type=INTEGER, lb=0, ub=10) >>> y = model.add_var(name='y', var_type=INTEGER, lb=0, ub=10) >>> model += x + y <= 10 >>> model.objective = x + y >>> status = model.optimize(max_seconds=2) >>> status == OptimizationStatus.OPTIMAL True
-
add_constr
(lin_expr, name='', priority=None)¶ Creates a new constraint (row).
Adds a new constraint to the model, returning its reference.
- Parameters
lin_expr (mip.LinExpr) – linear expression
name (str) – optional constraint name, used when saving model to lp or mps files
priority (mip.constants.ConstraintPriority) – optional constraint priority
Examples:
The following code adds the constraint \(x_1 + x_2 \leq 1\) (x1 and x2 should be created first using
add_var()
):m += x1 + x2 <= 1
Which is equivalent to:
m.add_constr( x1 + x2 <= 1 )
Summation expressions can be used also, to add the constraint \(\displaystyle \sum_{i=0}^{n-1} x_i = y\) and name this constraint
cons1
:m += xsum(x[i] for i in range(n)) == y, "cons1"
Which is equivalent to:
m.add_constr( xsum(x[i] for i in range(n)) == y, "cons1" )
- Return type
-
add_cut
(cut)¶ Adds a violated inequality (cutting plane) to the linear programming model. If called outside the cut callback performs exactly as
add_constr()
. When called inside the cut callback the cut is included in the solver’s cut pool, which will later decide if this cut should be added or not to the model. Repeated cuts, or cuts which will probably be less effective, e.g. with a very small violation, can be discarded.- Parameters
cut (mip.LinExpr) – violated inequality
-
add_lazy_constr
(expr)¶ Adds a lazy constraint
A lazy constraint is a constraint that is only inserted into the model after the first integer solution that violates it is found. When lazy constraints are used a restricted pre-processing is executed since the complete model is not available at the beginning. If the number of lazy constraints is too large then they can be added during the search process by implementing a
ConstrsGenerator
and setting the propertylazy_constrs_generator
ofModel
.- Parameters
expr (mip.LinExpr) – the linear constraint
-
add_sos
(sos, sos_type)¶ Adds an Special Ordered Set (SOS) to the model
An explanation on Special Ordered Sets is provided here.
- Parameters
sos (List[Tuple[Var, numbers.Real]]) – list including variables (not necessarily binary) and respective weights in the model
sos_type (int) – 1 for Type 1 SOS, where at most one of the binary variables can be set to one and 2 for Type 2 SOS, where at most two variables from the list may be selected. In type 2 SOS the two selected variables will be consecutive in the list.
-
add_var
(name='', lb=0.0, ub=inf, obj=0.0, var_type='C', column=None)¶ Creates a new variable in the model, returning its reference
- Parameters
name (str) – variable name (optional)
lb (numbers.Real) – variable lower bound, default 0.0
ub (numbers.Real) – variable upper bound, default infinity
obj (numbers.Real) – coefficient of this variable in the objective function, default 0
var_type (str) – CONTINUOUS (“C”), BINARY (“B”) or INTEGER (“I”)
column (mip.Column) – constraints where this variable will appear, necessary only when constraints are already created in the model and a new variable will be created.
Examples
To add a variable
x
which is continuous and greater or equal to zero to modelm
:x = m.add_var()
The following code adds a vector of binary variables
x[0], ..., x[n-1]
to the modelm
:x = [m.add_var(var_type=BINARY) for i in range(n)]
- Return type
-
add_var_tensor
(shape, name, **kwargs)¶ Creates new variables in the model, arranging them in a numpy tensor and returning its reference
- Parameters
Examples
To add a tensor of variables
x
with shape (3, 5) and which is continuous in any variable and have all values greater or equal to zero to modelm
:x = m.add_var_tensor((3, 5), "x")
- Return type
-
check_optimization_results
()¶ Checks the consistency of the optimization results, i.e., if the solution(s) produced by the MIP solver respect all constraints and variable values are within acceptable bounds and are integral when requested.
-
clear
()¶ Clears the model
All variables, constraints and parameters will be reset. In addition, a new solver instance will be instantiated to implement the formulation.
-
property
clique
¶ Controls the generation of clique cuts. -1 means automatic, 0 disables it, 1 enables it and 2 enables more aggressive clique generation.
- Return type
-
clique_merge
(constrs=None)¶ This procedure searches for constraints with conflicting variables and attempts to group these constraints in larger constraints with all conflicts merged.
For example, if your model has the following constraints:
\[ \begin{align}\begin{aligned}x_1 + x_2 \leq 1\\x_2 + x_3 \leq 1\\x_1 + x_3 \leq 1\end{aligned}\end{align} \]Then they can all be removed and replaced by the stronger inequality:
\[x_1 + x_2 + x_3 \leq 1\]- Parameters
constrs (Optional[List[mip.Constr]]) – constraints that should be checked for merging. All constraints will be checked if
constrs
is None.
-
property
conflict_graph
¶ Returns the
ConflictGraph
of a MIP model.- Return type
-
constr_by_name
(name)¶ Queries a constraint by its name
- Parameters
name (str) – constraint name
- Return type
Optional[mip.Constr]
- Returns
constraint or None if not found
-
copy
(solver_name='')¶ Creates a copy of the current model
-
property
cut_passes
¶ Maximum number of rounds of cutting planes. You may set this parameter to low values if you see that a significant amount of time is being spent generating cuts without any improvement in the lower bound. -1 means automatic, values greater than zero specify the maximum number of rounds.
- Return type
-
property
cutoff
¶ upper limit for the solution cost, solutions with cost > cutoff will be removed from the search space, a small cutoff value may significantly speedup the search, but if cutoff is set to a value too low the model will become infeasible
- Return type
-
property
cuts
¶ Controls the generation of cutting planes, -1 means automatic, 0 disables completely, 1 (default) generates cutting planes in a moderate way, 2 generates cutting planes aggressively and 3 generates even more cutting planes. Cutting planes usually improve the LP relaxation bound but also make the solution time of the LP relaxation larger, so the overall effect is hard to predict and experimenting different values for this parameter may be beneficial.
- Return type
-
property
cuts_generator
¶ A cuts generator is an
ConstrsGenerator
object that receives a fractional solution and tries to generate one or more constraints (cuts) to remove it. The cuts generator is called in every node of the branch-and-cut tree where a solution that violates the integrality constraint of one or more variables is found.- Return type
Optional[mip.ConstrsGenerator]
-
property
emphasis
¶ defines the main objective of the search, if set to 1 (FEASIBILITY) then the search process will focus on try to find quickly feasible solutions and improving them; if set to 2 (OPTIMALITY) then the search process will try to find a provable optimal solution, procedures to further improve the lower bounds will be activated in this setting, this may increase the time to produce the first feasible solutions but will probably pay off in longer runs; the default option if 0, where a balance between optimality and feasibility is sought.
- Return type
-
property
gap
¶ The optimality gap considering the cost of the best solution found (
objective_value
) \(b\) and the best objective bound \(l\) (objective_bound
) \(g\) is computed as: \(g=\\frac{|b-l|}{|b|}\). If no solution was found or if \(b=0\) then \(g=\infty\). If the optimal solution was found then \(g=0\).- Return type
-
generate_cuts
(cut_types=None, depth=0, npass=0, max_cuts=8192, min_viol=0.0001)¶ Tries to generate cutting planes for the current fractional solution. To optimize only the linear programming relaxation and not discard integrality information from variables you must call first
model.optimize(relax=True)
.This method only works with the CBC mip solver, as Gurobi does not supports calling only cut generators.
- Parameters
cut_types (List[CutType]) – types of cuts that can be generated, if an empty list is specified then all available cut generators will be called.
depth (
int
) – depth of the search tree, when informed the cut generator may decide to generate more/less cuts depending on the depth.max_cuts (int) – cut separation will stop when at least max_cuts violated cuts were found.
min_viol (float) – cuts which are not violated by at least min_viol will be discarded.
- Return type
-
property
infeas_tol
¶ Maximum allowed violation for constraints.
Default value: 1e-6. Tightening this value can increase the numerical precision but also probably increase the running time. As floating point computations always involve some loss of precision, values too close to zero will likely render some models impossible to optimize.
- Return type
-
property
integer_tol
¶ Maximum distance to the nearest integer for a variable to be considered with an integer value. Default value: 1e-6. Tightening this value can increase the numerical precision but also probably increase the running time. As floating point computations always involve some loss of precision, values too close to zero will likely render some models impossible to optimize.
- Return type
-
property
lazy_constrs_generator
¶ A lazy constraints generator is an
ConstrsGenerator
object that receives an integer solution and checks its feasibility. If the solution is not feasible then one or more constraints can be generated to remove it. When a lazy constraints generator is informed it is assumed that the initial formulation is incomplete. Thus, a restricted pre-processing routine may be applied. If the initial formulation is incomplete, it may be interesting to use the sameConstrsGenerator
to generate cuts and lazy constraints. The use of only lazy constraints may be useful then integer solutions rarely violate these constraints.- Return type
Optional[mip.ConstrsGenerator]
-
property
lp_method
¶ Which method should be used to solve the linear programming problem. If the problem has integer variables that this affects only the solution of the first linear programming relaxation.
- Return type
-
property
max_mip_gap
¶ value indicating the tolerance for the maximum percentage deviation from the optimal solution cost, if a solution with cost \(c\) and a lower bound \(l\) are available and \((c-l)/l <\)
max_mip_gap
the search will be concluded. Default value: 1e-4.- Return type
-
property
max_mip_gap_abs
¶ Tolerance for the quality of the optimal solution, if a solution with cost \(c\) and a lower bound \(l\) are available and \(c-l<\)
mip_gap_abs
, the search will be concluded, seemax_mip_gap
to determine a percentage value. Default value: 1e-10.- Return type
-
property
max_solutions
¶ solution limit, search will be stopped when
max_solutions
were found- Return type
-
property
name
¶ The problem (instance) name.
This name should be used to identify the instance that this model refers, e.g.: productionPlanningMay19. This name is stored when saving (
write()
) the model in.LP
or.MPS
file formats.- Return type
-
property
num_solutions
¶ Number of solutions found during the MIP search
- Return type
- Returns
number of solutions stored in the solution pool
-
property
objective
¶ The objective function of the problem as a linear expression.
Examples
The following code adds all
x
variablesx[0], ..., x[n-1]
, to the objective function of modelm
with the same costw
:m.objective = xsum(w*x[i] for i in range(n))
A simpler way to define the objective function is the use of the model operator +=
m += xsum(w*x[i] for i in range(n))
Note that the only difference of adding a constraint is the lack of a sense and a rhs.
- Return type
-
property
objective_bound
¶ A valid estimate computed for the optimal solution cost, lower bound in the case of minimization, equals to
objective_value
if the optimal solution was found.
-
property
objective_value
¶ Objective function value of the solution found or None if model was not optimized
-
property
objective_values
¶ List of costs of all solutions in the solution pool
- Return type
- Returns
costs of all solutions stored in the solution pool as an array from 0 (the best solution) to
num_solutions
-1.
-
property
opt_tol
¶ Maximum reduced cost value for a solution of the LP relaxation to be considered optimal. Default value: 1e-6. Tightening this value can increase the numerical precision but also probably increase the running time. As floating point computations always involve some loss of precision, values too close to zero will likely render some models impossible to optimize.
- Return type
-
optimize
(max_seconds=inf, max_nodes=1073741824, max_solutions=1073741824, max_seconds_same_incumbent=inf, max_nodes_same_incumbent=1073741824, relax=False)¶ Optimizes current model
Optimizes current model, optionally specifying processing limits.
To optimize model
m
within a processing time limit of 300 seconds:m.optimize(max_seconds=300)
- Parameters
max_seconds (numbers.Real) – Maximum runtime in seconds (default: inf)
max_nodes (int) – Maximum number of nodes (default: inf)
max_solutions (int) – Maximum number of solutions (default: inf)
max_seconds_same_incumbent (numbers.Real) – Maximum time in seconds that the search can go on if a feasible solution is available and it is not being improved
max_nodes_same_incumbent (int) – Maximum number of nodes that the search can go on if a feasible solution is available and it is not being improved
relax (bool) – if true only the linear programming relaxation will be solved, i.e. integrality constraints will be temporarily discarded.
- Returns
optimization status, which can be OPTIMAL(0), ERROR(-1), INFEASIBLE(1), UNBOUNDED(2). When optimizing problems with integer variables some additional cases may happen, FEASIBLE(3) for the case when a feasible solution was found but optimality was not proved, INT_INFEASIBLE(4) for the case when the lp relaxation is feasible but no feasible integer solution exists and NO_SOLUTION_FOUND(5) for the case when an integer solution was not found in the optimization.
- Return type
-
property
preprocess
¶ Enables/disables pre-processing. Pre-processing tries to improve your MIP formulation. -1 means automatic, 0 means off and 1 means on.
- Return type
-
property
pump_passes
¶ Number of passes of the Feasibility Pump [FGL05] heuristic. You may increase this value if you are not getting feasible solutions.
- Return type
-
read
(path)¶ Reads a MIP model or an initial feasible solution.
One of the following file name extensions should be used to define the contents of what will be loaded:
.lp
mip model stored in the LP file format
.mps
mip model stored in the MPS file format
.sol
initial integer feasible solution
.bas
optimal basis for the linear programming relaxation.
Note: if a new problem is readed, all variables, constraints and parameters from the current model will be cleared.
- Parameters
path (str) – file name
-
relax
()¶ Relax integrality constraints of variables
Changes the type of all integer and binary variables to continuous. Bounds are preserved.
-
remove
(objects)¶ removes variable(s) and/or constraint(s) from the model
- Parameters
objects (Union[mip.Var, mip.Constr, List[Union[mip.Var, mip.Constr]]]) – can be a
Var
, aConstr
or a list of these objects
-
property
round_int_vars
¶ MIP solvers perform computations using limited precision arithmetic. Thus a variable with value 0 may appear in the solution as 0.000000000001. Thus, comparing this var to zero would return false. The safest approach would be to use something like abs(v.x) < 1e-7. To simplify code the solution value of integer variables can be automatically rounded to the nearest integer and then, comparisons like v.x == 0 would work. Rounding is not always a good idea specially in models with numerical instability, since it can increase the infeasibilities.
- Return type
-
property
search_progress_log
¶ Log of bound improvements in the search. The output of MIP solvers is a sequence of improving incumbent solutions (primal bound) and estimates for the optimal cost (dual bound). When the costs of these two bounds match the search is concluded. In truncated searches, the most common situation for hard problems, at the end of the search there is a
gap
between these bounds. This property stores the detailed events of improving these bounds during the search process. Analyzing the evolution of these bounds you can see if you need to improve your solver w.r.t. the production of feasible solutions, by including an heuristic to produce a better initial feasible solution, for example, or improve the formulation with cutting planes, for example, to produce better dual bounds. To enable storing thesearch_progress_log
setstore_search_progress_log
to True.- Return type
-
property
seed
¶ Random seed. Small changes in the first decisions while solving the LP relaxation and the MIP can have a large impact in the performance, as discussed in [Fisch14]. This behaviour can be exploited with multiple independent runs with different random seeds.
- Return type
-
property
sense
¶ The optimization sense
- Return type
- Returns
the objective function sense, MINIMIZE (default) or (MAXIMIZE)
-
property
sol_pool_size
¶ Maximum number of solutions that will be stored during the search. To check how many solutions were found during the search use
num_solutions()
.- Return type
-
property
start
¶ Initial feasible solution
Enters an initial feasible solution. Only the main binary/integer decision variables which appear with non-zero values in the initial feasible solution need to be informed. Auxiliary or continuous variables are automatically computed.
- Return type
Optional[List[Tuple[mip.Var, numbers.Real]]]
-
property
status
¶ optimization status, which can be OPTIMAL(0), ERROR(-1), INFEASIBLE(1), UNBOUNDED(2). When optimizing problems with integer variables some additional cases may happen, FEASIBLE(3) for the case when a feasible solution was found but optimality was not proved, INT_INFEASIBLE(4) for the case when the lp relaxation is feasible but no feasible integer solution exists and NO_SOLUTION_FOUND(5) for the case when an integer solution was not found in the optimization.
- Return type
-
property
store_search_progress_log
¶ Wether
search_progress_log
will be stored or not when optimizing. Default False. Activate it if you want to analyze bound improvements over time.- Return type
-
property
threads
¶ number of threads to be used when solving the problem. 0 uses solver default configuration, -1 uses the number of available processing cores and \(\geq 1\) uses the specified number of threads. An increased number of threads may improve the solution time but also increases the memory consumption.
- Return type
-
translate
(ref)¶ Translates references of variables/containers of variables from another model to this model. Can be used to translate references of variables in the original model to references of variables in the pre-processed model.
- Return type
Union[List[Any], Dict[Any, Any], mip.Var]
-
validate_mip_start
()¶ Validates solution entered in MIPStart
If the solver engine printed messages indicating that the initial feasible solution that you entered in
start
is not valid then you can call this method to help discovering which set of variables is causing infeasibility. The current version is quite simple: the model is relaxed and one variable entered in mipstart is fixed per iteration, indicating if the model still feasible or not.
-
var_by_name
(name)¶ Searchers a variable by its name
- Return type
Optional[mip.Var]
- Returns
Variable or None if not found
-
write
(file_path)¶ Saves a MIP model or an initial feasible solution.
One of the following file name extensions should be used to define the contents of what will be saved:
.lp
mip model stored in the LP file format
.mps
mip model stored in the MPS file format
.sol
initial feasible solution
.bas
optimal basis for the linear programming relaxation.
- Parameters
file_path (str) – file name
-
LinExpr¶
-
class
LinExpr
(variables=None, coeffs=None, const=0.0, sense='')¶ Linear expressions are used to enter the objective function and the model constraints. These expressions are created using operators and variables.
Consider a model object m, the objective function of
m
can be specified as:m.objective = 10*x1 + 7*x4
In the example bellow, a constraint is added to the model
m += xsum(3*x[i] i in range(n)) - xsum(x[i] i in range(m))
A constraint is just a linear expression with the addition of a sense (==, <= or >=) and a right hand side, e.g.:
m += x1 + x2 + x3 == 1
If used in intermediate calculations, the solved value of the linear expression can be obtained with the
x
parameter, just as with aVar
.a = 10*x1 + 7*x4 print(a.x)
-
add_const
(val)¶ adds a constant value to the linear expression, in the case of a constraint this correspond to the right-hand-side
- Parameters
val (numbers.Real) – a real number
-
add_expr
(expr, coeff=1)¶ Extends a linear expression with the contents of another.
- Parameters
expr (LinExpr) – another linear expression
coeff (numbers.Real) – coefficient which will multiply the linear expression added
-
add_term
(term, coeff=1)¶ Adds a term to the linear expression.
- Parameters
expr (Union[mip.Var, LinExpr, numbers.Real]) – can be a variable, another linear expression or a real number.
coeff (numbers.Real) – coefficient which will multiply the added term
-
add_var
(var, coeff=1)¶ Adds a variable with a coefficient to the linear expression.
- Parameters
var (mip.Var) – a variable
coeff (numbers.Real) – coefficient which the variable will be added
-
equals
(other)¶ returns true if a linear expression equals to another, false otherwise
- Return type
-
property
expr
¶ the non-constant part of the linear expression
Dictionary with pairs: (variable, coefficient) where coefficient is a real number.
- Return type
Dict[mip.Var, numbers.Real]
-
property
model
¶ Model which this LinExpr refers to, None if no variables are involved.
- Return type
Optional[mip.Model]
-
property
sense
¶ sense of the linear expression
sense can be EQUAL(“=”), LESS_OR_EQUAL(“<”), GREATER_OR_EQUAL(“>”) or empty (“”) if this is an affine expression, such as the objective function
- Return type
-
set_expr
(expr)¶ Sets terms of the linear expression
- Parameters
expr (Dict[mip.Var, numbers.Real]) – dictionary mapping variables to their coefficients in the linear expression.
-
property
violation
¶ Amount that current solution violates this constraint
If a solution is available, than this property indicates how much the current solution violates this constraint.
-
Var¶
-
class
Var
(model, idx)¶ Decision variable of the
Model
. The creation of variables is performed calling theadd_var()
.-
property
column
¶ Variable coefficients in constraints.
- Return type
-
property
rc
¶ Reduced cost, only available after a linear programming model (only continuous variables) is optimized. Note that None is returned if no optimum solution is available
-
property
x
¶ Value of this variable in the solution. Note that None is returned if no solution is not available.
-
property
Constr¶
-
class
Constr
(model, idx, priority=None)¶ A row (constraint) in the constraint matrix.
A constraint is a specific
LinExpr
that includes a sense (<, > or == or less-or-equal, greater-or-equal and equal, respectively) and a right-hand-side constant value. Constraints can be added to the model using the overloaded operator+=
or using the methodadd_constr()
of theModel
class:m += 3*x1 + 4*x2 <= 5
summation expressions are also supported:
m += xsum(x[i] for i in range(n)) == 1
-
property
expr
¶ Linear expression that defines the constraint.
- Return type
-
property
pi
¶ Value for the dual variable of this constraint in the optimal solution of a linear programming
Model
. Only available if a pure linear programming problem was solved (only continuous variables).
-
property
priority
¶ priority value
- Return type
ConstraintPriority
-
property
Column¶
ConflictGraph¶
-
class
ConflictGraph
(model)¶ A conflict graph stores conflicts between incompatible assignments in binary variables.
For example, if there is a constraint \(x_1 + x_2 \leq 1\) then there is a conflict between \(x_1 = 1\) and \(x_2 = 1\). We can state that \(x_1\) and \(x_2\) are conflicting. Conflicts can also involve the complement of a binary variable. For example, if there is a constraint \(x_1 \leq x_2\) then there is a conflict between \(x_1 = 1\) and \(x_2 = 0\). We now can state that \(x_1\) and \(\lnot x_2\) are conflicting.
-
conflicting
(e1, e2)¶ Checks if two assignments of binary variables are in conflict.
- Parameters
e1 (Union[mip.LinExpr, mip.Var]) – binary variable, if assignment to be tested is the assignment to one, or a linear expression like x == 0 to indicate that conflict with the complement of the variable should be tested.
e2 (Union[mip.LinExpr, mip.Var]) – binary variable, if assignment to be tested is the assignment to one, or a linear expression like x == 0 to indicate that conflict with the complement of the variable should be tested.
- Return type
-
conflicting_assignments
(v)¶ Returns from the conflict graph all assignments conflicting with one specific assignment.
- Parameters
v (Union[mip.Var, mip.LinExpr]) – binary variable, if assignment to be tested is the assignment to one or a linear expression like x == 0 to indicate the complement.
- Return type
- Returns
Returns a tuple with two lists. The first one indicates variables whose conflict occurs when setting them to one. The second list includes variable whose conflict occurs when setting them to zero.
-
VarList¶
-
class
VarList
(model)¶ List of model variables (
Var
).The number of variables of a model
m
can be queried aslen(m.vars)
or asm.num_cols
.Specific variables can be retrieved by their indices or names. For example, to print the lower bounds of the first variable or of a varible named
z
, you can use, respectively:print(m.vars[0].lb)
print(m.vars['z'].lb)
ConstrsGenerator¶
-
class
ConstrsGenerator
¶ Abstract class for implementing cuts and lazy constraints generators.
-
generate_constrs
(model, depth=0, npass=0)¶ Method called by the solver engine to generate cuts or lazy constraints.
After analyzing the contents of the solution in model variables
vars
, whose solution values can be queried with thex
attribute, one or more constraints may be generated and added to the solver with theadd_cut()
method for cuts. This method can be called by the solver engine in two situations, in the first one a fractional solution is found and one or more inequalities can be generated (cutting planes) to remove this fractional solution. In the second case an integer feasible solution is found and then a new constraint can be generated (lazy constraint) to report that this integer solution is not feasible. To control when the constraint generator will be called set yourConstrsGenerator
object in the attributescuts_generator
orlazy_constrs_generator
(adding to both is also possible).- Parameters
model (mip.Model) – model for which cuts may be generated. Please note that this model may have fewer variables than the original model due to pre-processing. If you want to generate cuts in terms of the original variables, one alternative is to query variables by their names, checking which ones remain in this pre-processed problem. In this procedure you can query model properties and add cuts (
add_cut()
) or lazy constraints (add_lazy_constr()
), but you cannot perform other model modifications, such as add columns.depth (int) – depth of the search tree (0 is the root node)
npass (int) – current number of cut passes in this node
-
IncumbentUpdater¶
-
class
IncumbentUpdater
(model)¶ To receive notifications whenever a new integer feasible solution is found. Optionally a new improved solution can be generated (using some local search heuristic) and returned to the MIP solver.
-
update_incumbent
(objective_value, best_bound, solution)¶ Method that is called when a new integer feasible solution is found
-
CutType¶
-
class
CutType
(value)¶ Types of cuts that can be generated. Each cut type is an implementation in the COIN-OR Cut Generation Library. For some cut types multiple implementations are available. Sometimes these implementations were designed with different objectives: for the generation of Gomory cutting planes, for example, the GMI cuts are focused on numerical stability, while Forrest’s implementation (GOMORY) is more integrated into the CBC code.
-
FLOW_COVER
= 5¶ Lifted Simple Generalized Flow Cover Cut Generator.
-
GMI
= 2¶ Gomory Mixed Integer cuts [Gomo69], as implemented by Giacomo Nannicini, focusing on numerically safer cuts.
-
LATWO_MIR
= 8¶ Lagrangean relaxation for two-phase Mixed-integer rounding cuts, as in LAGomory
-
ODD_WHEEL
= 13¶ Lifted odd-hole inequalities.
-
PROBING
= 0¶ Cuts generated evaluating the impact of fixing bounds for integer variables
-
TWO_MIR
= 7¶ Two-phase Mixed-integer rounding cuts.
-
CutPool¶
-
class
CutPool
¶ -
add
(cut)¶ tries to add a cut to the pool, returns true if this is a new cut, false if it is a repeated one
- Parameters
cut (mip.LinExpr) – a constraint
- Return type
-
OptimizationStatus¶
-
class
OptimizationStatus
(value)¶ Status of the optimization
-
CUTOFF
= 7¶ No feasible solution exists for the current cutoff
-
ERROR
= -1¶ Solver returned an error
-
FEASIBLE
= 3¶ An integer feasible solution was found during the search but the search was interrupted before concluding if this is the optimal solution or not.
-
INFEASIBLE
= 1¶ The model is proven infeasible
-
INT_INFEASIBLE
= 4¶ A feasible solution exist for the relaxed linear program but not for the problem with existing integer variables
-
LOADED
= 6¶ The problem was loaded but no optimization was performed
-
NO_SOLUTION_FOUND
= 5¶ A truncated search was executed and no integer feasible solution was found
-
OPTIMAL
= 0¶ Optimal solution was computed
-
UNBOUNDED
= 2¶ One or more variables that appear in the objective function are not included in binding constraints and the optimal objective value is infinity.
-
SearchEmphasis¶
-
class
SearchEmphasis
(value)¶ An enumeration.
-
DEFAULT
= 0¶ Default search emphasis, try to balance between improving the dual bound and producing integer feasible solutions.
-
FEASIBILITY
= 1¶ More aggressive search for feasible solutions.
-
OPTIMALITY
= 2¶ Focuses more on producing improved dual bounds even if the production of integer feasible solutions is delayed.
-
LP_Method¶
ProgressLog¶
-
class
ProgressLog
¶ Class to store the improvement of lower and upper bounds over time during the search. Results stored here are useful to analyze the performance of a given formulation/parameter setting for solving a instance. To be able to automatically generate summarized experimental results, fill the
instance
andsettings
of this object with the instance name and formulation/parameter setting details, respectively.-
log
¶ List of tuples in the format \((time, (lb, ub))\), where \(time\) is the processing time in seconds and \(lb\) and \(ub\) are the lower and upper bounds, respectively
-
settings
¶ identification of the formulation/parameter settings used in the optimization (whatever is relevant to identify a given computational experiment)
- Type
-
read
(file_name)¶ Reads a progress log stored in a file
-
Exceptions¶
-
class
MipBaseException
¶ Base class for all exceptions specific to Python MIP. Only sub-classes of this exception are raised. Inherits from the Python builtin
Exception
.
-
class
ProgrammingError
¶ Exception that is raised when the calling program performs an invalid or nonsensical operation. Inherits from
mip.MipBaseException
.
-
class
InterfacingError
¶ Exception that is raised when an unknown error occurs while interfacing with a solver. Inherits from
mip.MipBaseException
.
-
class
InvalidLinExpr
¶ Exception that is raised when an invalid linear expression is created. Inherits from
mip.MipBaseException
.
-
class
InvalidParameter
¶ Exception that is raised when an invalid/non-existent parameter is used or set. Inherits from
mip.MipBaseException
.
-
class
ParameterNotAvailable
¶ Exception that is raised when some parameter is not available or can not be set. Inherits from
mip.MipBaseException
.
-
class
InfeasibleSolution
¶ Exception that is raised the produced solution is unfeasible. Inherits from
mip.MipBaseException
.
-
class
SolutionNotAvailable
¶ Exception that is raised when a method that requires a solution is queried but the solution is not available. Inherits from
mip.MipBaseException
.
Useful functions¶
-
minimize
(objective)¶ Function that should be used to set the objective function to MINIMIZE a given linear expression (passed as argument).
- Parameters
objective (Union[mip.LinExpr, Var]) – linear expression
- Return type
-
maximize
(objective)¶ Function that should be used to set the objective function to MAXIMIZE a given linear expression (passed as argument).
- Parameters
objective (Union[mip.LinExpr, Var]) – linear expression
- Return type
-
xsum
(terms)¶ Function that should be used to create a linear expression from a summation. While the python function sum() can also be used, this function is optimized version for quickly generating the linear expression.
- Parameters
terms – set (ideally a list) of terms to be summed
- Return type
-
compute_features
(model)¶ This function computes instance features for a MIP. Features are instance characteristics, such as number of columns, rows, matrix density, etc. These features can be used in machine learning algorithms to recommend parameter settings. To check names of features that are computed in this vector use
features()
-
features
()¶ This function returns the list of problem feature names that can be computed
compute_features()