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.

vars¶

list of problem variables (Var)

Type:: mip.VarList

constrs¶

list of constraints (Constr)

Type:: mip.ConstrList

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 (LinExpr) – linear expression
name (str) – optional constraint name, used when saving model to lp or mps files
priority (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:: Constr

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 (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 property lazy_constrs_generator of Model.

Parameters:: expr (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, 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 (Real) – variable lower bound, default 0.0
ub (Real) – variable upper bound, default infinity
obj (Real) – coefficient of this variable in the objective function, default 0
var_type (str) – CONTINUOUS (“C”), BINARY (“B”) or INTEGER (“I”)
column (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 model m:

x = m.add_var()

The following code adds a vector of binary variables x[0], ..., x[n-1] to the model m:

x = [m.add_var(var_type=BINARY) for i in range(n)]

Return type:: Var

add_var_tensor(shape, name, **kwargs)¶

Creates new variables in the model, arranging them in a numpy tensor and returning its reference

Parameters:

shape (Tuple[int, ...]) – shape of the numpy tensor
name (str) – variable name
**kwargs – all other named arguments will be used as add_var() arguments

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 model m:

x = m.add_var_tensor((3, 5), "x")

Return type:: LinExprTensor

add_vars(n, name='', lb=0.0, ub=inf, obj=0.0, var_type='C')¶

Creates n variables at once, returning a list of Var.

This is a faster alternative to calling add_var() in a loop when all variables share the same bounds, objective coefficient and type.

Parameters:

n (int) – number of variables to create
name (str) – optional name prefix; variables will be named name_0, name_1, …, name_{n-1} when provided
lb (Real) – lower bound (default 0)
ub (Real) – upper bound (default infinity)
obj (Real) – objective coefficient (default 0)
var_type (str) – CONTINUOUS, BINARY or INTEGER

Example:

x = m.add_vars(n * n, var_type=BINARY)

Return type:: List[Var]

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: int¶: Controls the generation of clique cuts. -1 means automatic, 0 disables it, 1 enables it and 2 enables more aggressive clique generation.

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[Constr]]) – constraints that should be checked for merging. All constraints will be checked if constrs is None.

property conflict_graph: ConflictGraph¶

Returns the ConflictGraph of a MIP model.

Return type:: mip.ConflictGraph

constr_by_name(name)¶

Queries a constraint by its name

Parameters:: name (str) – constraint name
Return type:: Optional[Constr]
Returns:: constraint or None if not found

copy(solver_name='')¶

Creates a copy of the current model

Parameters:: solver_name (str) – solver name (optional)
Return type:: Model
Returns:: clone of current model

property cut_passes: int¶: 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.

property cutoff: Real¶: 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

property cuts: int¶: 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.

property cuts_generator: ConstrsGenerator | None¶

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: SearchEmphasis¶

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:: mip.SearchEmphasis

property gap: float¶: 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\).

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 (Optional[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:

CutPool

property infeas_tol: float¶

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.

property integer_tol: float¶: 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.

property lazy_constrs_generator: ConstrsGenerator | None¶

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 same ConstrsGenerator 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: 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:: mip.LP_Method

property max_iter: int¶

no limit)

Type:: maximum number of simplex iterations for LP solves (default

property max_mip_gap: float¶: 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.

property max_mip_gap_abs: float¶: 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, see max_mip_gap to determine a percentage value. Default value: 1e-10.

property max_nodes: int¶: maximum number of nodes to be explored in the search tree

property max_seconds: float¶: time limit in seconds for search

property max_solutions: int¶: solution limit, search will be stopped when max_solutions were found

property name: str¶

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.

property num_cols: int¶: number of columns (variables) in the model

property num_int: int¶: number of integer variables in the model

property num_nz: int¶: number of non-zeros in the constraint matrix

property num_rows: int¶: number of rows (constraints) in the model

property num_solutions: int¶

Number of solutions found during the MIP search

Returns:: number of solutions stored in the solution pool

property objective: LinExpr¶

The objective function of the problem as a linear expression.

Examples

The following code adds all x variables x[0], ..., x[n-1], to the objective function of model m with the same cost w:

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:: mip.LinExpr

property objective_bound: Real | None¶: 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_const: float¶: Returns the constant part of the objective function

property objective_value: Real | None¶: Objective function value of the solution found or None if model was not optimized

property objective_values: List[Real]¶

List of costs of all solutions in the solution pool

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: float¶: 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.

optimize(max_seconds=inf, max_nodes=1073741824, max_solutions=1073741824, max_seconds_same_incumbent=inf, max_nodes_same_incumbent=1073741824, relax=False, lp_preprocess=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 (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 (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.
lp_preprocess (bool) – when solving the LP relaxation (relax=True), apply fast combinatorial bound-tightening (knapsack-based) before the LP solve. Disabled by default to preserve the pure LP relaxation. When enabled, bounds may be tightened beyond the LP relaxation, which is useful in custom B&B node-solving loops but means the solution is no longer the unmodified LP relaxation. Only supported by the CBC backend; ignored by other solvers.

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:

OptimizationStatus

property preprocess: int¶: Enables/disables pre-processing. Pre-processing tries to improve your MIP formulation. -1 means automatic, 0 means off and 1 means on.

property pump_passes: int¶: Number of passes of the Feasibility Pump [FGL05] heuristic. You may increase this value if you are not getting feasible solutions.

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[Var, Constr, List[Union[Var, Constr]]]) – can be a Var, a Constr or a list of these objects

reset()¶: Discards the current solution, putting the model to an unsolved state.

property round_int_vars: bool¶: 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.

property search_progress_log: ProgressLog¶

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 the search_progress_log set store_search_progress_log to True.

Return type:: mip.ProgressLog

property seed: int¶: 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.

property sense: str¶

The optimization sense

Returns:: the objective function sense, MINIMIZE (default) or (MAXIMIZE)

property sol_pool_size: int¶: Maximum number of solutions that will be stored during the search. To check how many solutions were found during the search use num_solutions().

property start: List[Tuple[Var, Real]] | None¶

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: OptimizationStatus¶

Return type:: mip.OptimizationStatus

property store_search_progress_log: bool¶: Wether search_progress_log will be stored or not when optimizing. Default False. Activate it if you want to analyze bound improvements over time.

property threads: int¶: 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.

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], 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[Var]
Returns:: Variable or None if not found

property verbose: int¶: 0 to disable solver messages printed on the screen, 1 to enable

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='', expr=None)¶

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 a Var.

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 corresponds to the right-hand-side

Parameters:: val (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 (Real) – coefficient which will multiply the linear expression added

add_term(term, coeff=1)¶

Adds a term to the linear expression.

Parameters:

term (Union[Var, LinExpr, Real]) – can be a variable, another linear expression or a real number.
coeff (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 (Var) – a variable
coeff (Real) – coefficient which the variable will be added

property const: Real¶: constant part of the linear expression

equals(other)¶

returns true if a linear expression equals to another, false otherwise

Return type:: bool

property expr: Dict[Var, Real]¶

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 | None¶

Model which this LinExpr refers to, None if no variables are involved.

Return type:: Optional[mip.Model]

property sense: str¶

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

set_expr(expr)¶

Sets terms of the linear expression

Parameters:: expr (Dict[Var, Real]) – dictionary mapping variables to their coefficients in the linear expression.

property violation: Real | None¶

Amount that current solution violates this constraint

If a solution is available, than this property indicates how much the current solution violates this constraint.

property x: Real | None¶: Value of this linear expression in the solution. None is returned if no solution is available.

LinExprTensor¶

class LinExprTensor¶

Var¶

class Var(model, idx)¶

Decision variable of the Model. The creation of variables is performed calling the add_var().

property branch_priority: Real¶: Variable’s branching priority in the branch and bound process. Note: variables with higher priority are selected first. Default value is zero.

property column: Column¶

Variable coefficients in constraints.

Return type:: mip.Column

property idx: int¶

Internal index of the variable to the model.

Return type:: int

property lb: Real¶: Variable lower bound.

property model: Model¶

Model which this variable refers to.

Return type:: mip.Model

property name: str¶: Variable name.

property obj: Real¶: Coefficient of variable in the objective function.

property rc: Real | None¶: 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 ub: Real¶: Variable upper bound.

property var_type: str¶: Variable type, (‘B’) BINARY, (‘C’) CONTINUOUS and (‘I’) INTEGER.

property x: Real | None¶: Value of this variable in the solution. Note that None is returned if no solution is not available.

xi(i)¶

Value for this variable in the \(i\)-th solution from the solution pool. Note that None is returned if the solution is not available.

Return type:: Optional[Real]

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 method add_constr() of the Model class:

m += 3*x1 + 4*x2 <= 5

summation expressions are also supported:

m += xsum(x[i] for i in range(n)) == 1

property expr: LinExpr¶

Linear expression that defines the constraint.

Return type:: mip.LinExpr

property name: str¶: constraint name

property pi: Real | None¶: 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: ConstraintPriority¶: priority value

property rhs: Real¶: The right-hand-side (constant value) of the linear constraint.

property slack: Real | None¶: Value of the slack in this constraint in the optimal solution. Available only if the formulation was solved.

Column¶

class Column(constrs=None, coeffs=None)¶: A column contains all the non-zero entries of a variable in the constraint matrix. To create a variable see add_var().

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[LinExpr, 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[LinExpr, 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:

bool

conflicting_assignments(v)¶

Returns from the conflict graph all assignments conflicting with one specific assignment.

Parameters:: v (Union[LinExpr, Var]) – 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:: Tuple[List[Var], List[Var]]
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 as len(m.vars) or as m.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)

add_vars(n, name='', lb=0.0, ub=inf, obj=0.0, var_type='C')¶

Creates n variables at once, returning a list of Var.

Faster than calling add() in a loop for large n because it avoids per-variable Python dispatch overhead. All variables share the same bounds, objective coefficient and type.

Parameters:

n (int) – number of variables to create
name (str) – optional name prefix; variables will be named name_0, name_1, …, name_{n-1} when provided
lb (Real) – lower bound (default 0)
ub (Real) – upper bound (default infinity)
obj (Real) – objective coefficient (default 0)
var_type (str) – CONTINUOUS, BINARY or INTEGER

Return type:

List[Var]

ConstrList¶

class ConstrList(model)¶: List of problem constraints

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 the x attribute, one or more constraints may be generated and added to the solver with the add_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 your ConstrsGenerator object in the attributes cuts_generator or lazy_constrs_generator (adding to both is also possible).

Parameters:

model (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

Parameters:

objective_value (float) – cost of the new solution found
best_bound (float) – current lower bound for the optimal solution cost
solution (List[Tuple[Var, float]]) – non-zero variables in the solution

Return type:

List[Tuple[Var, float]]

CutType¶

class CutType(*values)¶

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.

CLIQUE = 12¶: Clique cuts [Padb73].

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.

GOMORY = 1¶: Gomory Mixed Integer cuts [Gomo69], as implemented by John Forrest.

KNAPSACK_COVER = 14¶: Knapsack cover cuts [Bala75].

LATWO_MIR = 8¶: Lagrangean relaxation for two-phase Mixed-integer rounding cuts, as in LAGomory

LIFT_AND_PROJECT = 9¶: Lift-and-project cuts [BCC93], implemented by Pierre Bonami.

MIR = 6¶: Mixed-Integer Rounding cuts [Marc01].

ODD_WHEEL = 13¶: Lifted odd-hole inequalities.

PROBING = 0¶: Cuts generated evaluating the impact of fixing bounds for integer variables

RED_SPLIT = 3¶: Reduce and split cuts [AGY05], implemented by Francois Margot.

RED_SPLIT_G = 4¶: Reduce and split cuts [AGY05], implemented by Giacomo Nannicini.

RESIDUAL_CAPACITY = 10¶: Residual capacity cuts [AtRa02], implemented by Francisco Barahona.

TWO_MIR = 7¶: Two-phase Mixed-integer rounding cuts.

ZERO_HALF = 11¶: Zero/Half cuts [Capr96].

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 (LinExpr) – a constraint
Return type:: bool

OptimizationStatus¶

class OptimizationStatus(*values)¶

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

INF_OR_UNBD = 8¶: Special state for gurobi solver. In some cases gurobi could not determine if the problem is infeasible or unbounded due to application of dual reductions (when active) during presolve.

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

TRUNCATED = 9¶: The LP solve was truncated by a time or iteration limit. A partial primal solution (if primal feasible) and/or a dual bound may be available.

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(*values)¶

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¶

class LP_Method(*values)¶

Different methods to solve the linear programming problem.

AUTO = 0¶: Let the solver decide which is the best method

BARRIER = 3¶: The barrier algorithm

BARRIERNOCROSS = 4¶: The barrier algorithm without performing crossover

DUAL = 1¶: The dual simplex algorithm

PRIMAL = 2¶: The primal simplex algorithm

RACING = 5¶

opportunistic parallel LP racing. Multiple LP method configurations (dual simplex, primal with Idiot crash, primal with Sprint) run in parallel threads and the first to reach optimality wins. Requires at least 2 threads (see Model.threads()); with fewer threads it silently degrades to RECOMMEND. Ignored by HiGHS and Gurobi.

Type:: CBC-specific

RECOMMEND = 6¶

ML-based per-instance recommendation of a single LP method/configuration, using a classifier trained on instance features. Runs sequentially. Ignored by HiGHS and Gurobi.

Type:: CBC-specific

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 and settings 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

Type:: List[Tuple[float, Tuple[float, float]]]

instance¶

instance name

Type:: str

settings¶

identification of the formulation/parameter settings used in the optimization (whatever is relevant to identify a given computational experiment)

Type:: str

read(file_name)¶: Reads a progress log stored in a file

write(file_name='')¶: Saves the progress log. If no extension is informed, the .plog extension will be used. If only a directory is informed then the name will be built considering the instance and settings attributes

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[LinExpr, Var]) – linear expression
Return type:: LinExpr

maximize(objective)¶

Function that should be used to set the objective function to MAXIMIZE a given linear expression (passed as argument).

Parameters:: objective (Union[LinExpr, Var]) – linear expression
Return type:: LinExpr

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:: LinExpr

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

Parameters:: model (Model) – the MIP model were features will be extracted
Return type:: List[float]

features()¶

This function returns the list of problem feature names that can be computed compute_features()

Return type:: List[str]