Classes¶
Classes used in solver callbacks, for a bidirectional communication with the solver engine
PythonMIP constants
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 reoptimizing MixedInteger Programming Models.
To check how models are created please see the examples included.

add_constr
(lin_expr, name='')¶ 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
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}^{n1} 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 (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 preprocessing 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 (LinExpr) – the linear constraint

add_sos
(sos, sos_type)¶ Adds an Special Ordered Set (SOS) to the model
In models with binary variables it is often the case that from a list of variables only one can receive value 1 in a feasible solution. When large constraints of this type exist (packing and partitioning), branching in one variable at time usually doesn’t work well: while fixing one of these variables to one leaves only one possible feasible value for the other variables in this set (zero), fixing one variable to zero keeps all other variables free. This unbalanced branching is highly ineffective. A Special ordered set (SOS) is a set \(\mathcal{S}=\{s_1, s_2, \ldots, s_k\}\) with weights \([w_1, w_2, \ldots, w_k] \in \mathbb{R}^+\). With this structure available branching on a fractional solution \(x^*\) for these variables can be performed computing:
\[\min \{ u_{k'} : u_{k'} =  \sum_{j=1\,\ldots \,k'1} w_j \ldotp x^*_j  \sum_{j=k'\,\ldots ,k} w_j \ldotp x^*_j  \}\]Then, branching \(\mathcal{S}_1\) would be \(\displaystyle \sum_{j=1, \ldots, k'1} x_j = 0\) and \(\displaystyle \mathcal{S}_2 = \sum_{j=k', \ldots, k} x_j = 0\).
 Parameters
sos (List[Tuple[Var, float]]) – 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 (float) – variable lower bound, default 0.0
ub (float) – variable upper bound, default infinity
obj (float) – 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 modelm
:x = m.add_var()
The following code creates a vector of binary variables
x[0], ..., x[n1]
to modelm
:x = [m.add_var(var_type=BINARY) for i in range(n)]
 Return type

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
int

constr_by_name
(name)¶ Queries a constraint by its name
 Parameters
name (str) – constraint name
 Return type
 Returns
constraint or None if not found

copy
(solver_name=None)¶ Creates a copy of the current model
 Parameters
solver_name (str) – solver name (optional)
 Return type
 Returns
clone of 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
int

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
float

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
int

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 branchandcut tree where a solution that violates the integrality constraint of one or more variables is found. Return type

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
SearchEmphasis

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{bl}{b}\). If no solution was found or if \(b=0\) then \(g=\infty\). If the optimal solution was found then \(g=0\). Return type
float

property
infeas_tol
¶ 1e6. 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.
 Type
Maximum allowed violation for constraints. Default value
 Return type
float

property
integer_tol
¶ Maximum distance to the nearest integer for a variable to be considered with an integer value. Default value: 1e6. 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
float

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 preprocessing 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

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 \((cl)/l <\)
max_mip_gap
the search will be concluded. Default value: 1e4. Return type
float

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 \(cl<\)
mip_gap_abs
, the search will be concluded, seemax_mip_gap
to determine a percentage value. Default value: 1e10. Return type
float

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

property
max_seconds
¶ time limit in seconds for search
 Return type
float

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

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
str

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

property
num_int
¶ number of integer variables in the model
 Return type
int

property
num_nz
¶ number of nonzeros in the constraint matrix
 Return type
int

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

property
num_solutions
¶ Number of solutions found during the MIP search
 Return type
int
 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[n1]
, 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. Return type
float

property
objective_const
¶ Returns the constant part of the objective function
 Return type
float

property
objective_value
¶ Objective function value of the solution found
 Return type
float

property
objective_values
¶ List of costs of all solutions in the solution pool
 Return type
List
[float
] 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: 1e6. 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
float

optimize
(max_seconds=inf, max_nodes=inf, max_solutions=inf)¶ 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 (float) – Maximum runtime in seconds (default: inf)
max_nodes (float) – Maximum number of nodes (default: inf)
max_solutions (float) – Maximum number of solutions (default: inf)
 Return type
 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.

property
preprocess
¶ Enables/disables preprocessing. Preprocessing tries to improve your MIP formulation. 1 means automatic, 0 means off and 1 means on.
 Return type
int

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
int

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 feasible solution
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 – can be a Var, a Constr or a list of these objects

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
sense
¶ The optimization sense
 Return type
str
 Returns
the objective function sense, MINIMIZE (default) or (MAXIMIZE)

property
start
¶ Initial feasible solution
Enters an initial feasible solution. Only the main binary/integer decision variables which appear with nonzero values in the initial feasible solution need to be informed. Auxiliary or continuous variables are automatically computed.
 Return type
List
[Tuple
[Var
,float
]]

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
bool

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
int

var_by_name
(name)¶ Searchers a variable by its name
 Return type
 Returns
Variable or None if not found

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

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

add_const
(_LinExpr__const)¶ adds a constant value to the linear expression, in the case of a constraint this correspond to the righthandside

add_expr
(_LinExpr__expr, coeff=1)¶ extends a linear expression with the contents of another

add_term
(_LinExpr__expr, coeff=1)¶ extends a linear expression with another multiplied by a constant value coefficient

add_var
(var, coeff=1)¶ adds a variable with a coefficient to the constraint

property
const
¶ constant part of the linear expression
 Return type
float

equals
(other)¶ returns true if a linear expression equals to another, false otherwise
 Return type
bool

property
expr
¶ the nonconstant part of the linear expression
Dictionary with pairs: (variable, coefficient) where coefficient is a float.
 Return type
dict

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
str

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
lb
¶ Variable lower bound.
 Return type
float

property
name
¶ Variable name.
 Return type
str

property
obj
¶ Coefficient of variable in the objective function.
 Return type
float

property
rc
¶ Reduced cost, only available after a linear programming model (only continuous variables) is optimized
 Return type
float

property
ub
¶ Variable upper bound.
 Return type
float

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

property
x
¶ Value of this variable in the solution.
 Return type
float

xi
(i)¶ Value for this variable in the \(i\)th solution from the solution pool.
 Return type
float

property
Constr¶

class
Constr
(model, idx)¶ A row (constraint) in the constraint matrix.
A constraint is a specific
LinExpr
that includes a sense (<, > or == or lessorequal, greaterorequal and equal, respectively) and a righthandside 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
name
¶ constraint name
 Return type
str

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). Return type
float

property
slack
¶ Value of the slack in this constraint in the optimal solution. Available only if the formulation was solved.
 Return type
float

property
Column¶

class
Column
(constrs=None, coeffs=None)¶ A column contains all the nonzero entries of a variable in the constraint matrix. To create a variable see
add_var()
.
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)¶ 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 inx
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 (Model) – model for which cuts may be generated. Please note that this model may have fewer variables than the original model due to preprocessing. 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 preprocessed problem. In this procedure you can query model properties and add cuts or lazy constraints (
add_constrs()
), but you cannot perform other model modifications, such as add columns.

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
solution (cost) – nonzero variables
the solution (in) –
 Return type
List
[Tuple
[Var
,float
]]

CutPool¶
OptimizationStatus¶

class
OptimizationStatus
¶ 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.

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
¶ Tuple in the format \((time, (lb, ub))\), where \(time\) is the processing time and \(lb\) and \(ub\) are the lower and upper bounds, respectively
 Type
Tuple[float, Tuple[float, float]]

instance
¶ instance name
 Type
str

settings
¶ identification of the formulation/parameter
 Type
str

settings used in the optimization (whatever is relevant to

identify a given computational experiment)

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

Useful functions¶

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

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

model.
xsum
()¶ 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