Classes¶

Classes used in solver callbacks, for a bi-directional communication with the solver engine

Python-MIP 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 re-optimizing Mixed-Integer Programming Models.

To check how models are created please see the examples included.

vars

list of problem variables (Var)

Type

VarList

constrs

list of constraints (Constr)

Type

ConstrList

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}^{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)

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

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

x = m.add_var()


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

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

Return type

Var

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

Constr

Returns

copy(solver_name=None)

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

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

Return type

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

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

float

property infeas_tol

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.

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

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

ConstrsGenerator

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

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 $$c-l<$$ mip_gap_abs, the search will be concluded, see max_mip_gap to determine a percentage value. Default value: 1e-10.

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

LinExpr

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

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

OptimizationStatus

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

Return type

ProgressLog

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

OptimizationStatus

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

Var

Returns

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 right-hand-side

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 non-constant 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 the add_var().

property column

Variable coefficients in constraints.

Return type

Column

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

Constr¶

class Constr(model, idx)

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

contents of the constraint

Return type

LinExpr

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

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

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)


ConstrList¶

class ConstrList(model)

List of problem constraints

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 in 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 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) – non-zero variables

• the solution (in) –

Return type

List[Tuple[Var, float]]

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

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

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

Useful functions¶

model.minimize()

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

Parameters

expr (LinExpr) – linear expression

Return type

LinExpr

model.maximize()

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

Parameters

expr (LinExpr) – linear expression

Return type

LinExpr

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

LinExpr