Creating a mathematical programming model

Building a model requires:

  • defining decision variables and their scopes (what are the possible values for these variables),
  • creating constraints from variables to express interactions between variables and business limitations; only variable values which satisfy the constraints are possible,
  • adding constraints in a model, and
  • defining what is the objective to optimize. The objective is a numerical criterion which is used to rank possible solutions. Mathematical programming algorithms aim to return the best possible solution. This step is optional: if no objective is defined, the algorithm returns one feasible solution.

The folder Examples contains a set of examples that can be used as a starting point to create a new model.

The mathematical programming elements are implemented in the Python modules located in docplex/mp. The factory used to create constraints, manipulate the expressions, and so on is described in the DOcplex.MP reference manual.

Define model decision variables

Decision variables are created using factory methods on the Model class. The Model can create single variables, lists of variables, and dictionaries of variables indexed by business objects. Here is a table of the standard factory methods to create variables:

Function Creates
binary_var() Single binary variable
binary_var_list() List of binary variables
binary_var_dict() Dictionary of binary variables
binary_var_matrix() Matrix of binary variables
integer_var() Single integer variable
integer_var_list() List of integer variables
integer_var_dict() Dictionary of integer variables
integer_var_matrix() Matrix of integer variables
continuous_var() Single continuous variable
continuous_var_list() List of continuous variables
continuous_var_dict() Dictionary of continuous variables
continuous_var_matrix() Matrix of continuous variables

There are three types of decision variables according to their scope of possible values: binary variables (0 or 1), integer variables, or continuous variables. The detailed attributes for variables can be found in the class Var in the module

Build model expressions

Constraints in mathematical programming are built with linear combinations of decision variables, sums of elementary expressions of the form k *x where k is a number and x is a variable.

Python arithmetic operators (+,-,*,/) are overloaded to create expressions in a simple manner; for example, if x, y, z are decision variables, 3*x+5*y+7*z is an expression.

Aggregated expressions

DOcplex.MP allows the creation of large expressions over collections of variables by using the Model.sum method. Though Python’s built-in sum() function can also be used, Model.sum() is much faster for building larger expressions. Aggregated expressions can also be used to build constraints.

Building constraints

To simplify the writing of a model, Python comparison operators (==,<=,>=) are also overloaded to compare expressions and build constraints that must be satisfied by the decision variables. For example, x+y+z == 1 is a constraint that forces the sum of all three variables to be equal to 1.

Explicit methods are also available on the model object to ease their creation, such as eq_constraint, le_constraint

Build a model

The mathematical programming model itself is represented by the class Model implemented in the module

A constraint is added to the model by calling the method add_constraint() with the constraint as the parameter, and, possibly, an optional string argument to name the constraint. A constraint is active only if it has been added to the model.

Import necessary modules

The following is a condensed example of a sudoku problem that uses the default import policy. More comments are available in the files in the directory docplex/mp/examples.

from import Model

myInput =[[8, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 6, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 9, 0, 2, 0, 0],
 [0, 5, 0, 0, 0, 7, 0, 0, 0],
 [0, 0, 0, 0, 4, 5, 7, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0, 6, 8],
 [0, 0, 8, 5, 0, 0, 0, 1, 0],
 [0, 9, 0, 0, 0, 0, 4, 0, 0]]

model = Model("sudoku")
R = range(1, 10)
idx = [(i, j, k) for i in R for j in R for k in R]

x = model.binary_var_dict(idx, "X")

for i in R:
    for j in R:
        if myInput[i - 1][j - 1] != 0:
            model.add_constraint(x[i, j, myInput[i - 1][j - 1]] == 1)

for i in R:
    for j in R:
        model.add_constraint(model.sum(x[i, j, k] for k in R) == 1)
for j in R:
    for k in R:
        model.add_constraint(model.sum(x[i, j, k] for i in R) == 1)
for i in R:
    for k in R:
        model.add_constraint(model.sum(x[i, j, k] for j in R) == 1)

solution = model.solve()

The solve() method returns an object of class SolveSolution that contains the result of solving, or None if the model has no solution. This object is described in the section “Retrieve results”.

The method print_information() prints a default view of the status of the solve and the values of all variables. The object SolveSolution contains all the necessary accessors to create a customized solution output.

Solving parameters

Solving parameters can be adjusted using the “parameters” attribute of the model. Parameters implement a hierarchical tree of attributes reflecting the parameter hierarchy of CPLEX. For example, use model.parameters.mip.tolerances.mip_gap = 0.05 to set the MIP gap to 5% before solve.

Retrieve results

Results from the solve are returned in a data structure of the class SolveSolution, implemented in the module SolveSolution. This object contains:

  • global model information, such as status of the search, value of the objective, and
  • the value of each variable

Many shortcuts are available to write simpler code.

  • As solve() returns None if the model has no solution, one can test directly if a solution is present.
  • A simplified Python value for each object is directly accessible by using square brackets (msol[vname]). The result is:
    • an integer for integer variables and
    • a float for continuous variables.

The following code is an example of solution printing for the NQueen example:

from sys import stdout
if msol:
    for v in x:
        stdout.write(" " + str(msol[v]))
    stdout.write("Solve status: " + msol.get_solve_status() + "\n")

Generate LP file

The generation of the LP file corresponding to a model is made available by calling the method export_as_lp(), as demonstrated in the following example:

mdl = Model()
. . . . .
<Construction of the model>
. . . . .