Thanks to the evolution of Python and its applications to solve linear programs and their variations supply chain and operations research analysts now have access to numerous packages and tools that support decision making. In this article I will use CPLEX and DOCPLEX to model and solve a linear integer program.

Linear programming, also referred to as linear optimization, is a discipline focusing on maximization or minimization of linear objectives, subject to linear constraints. In continuous linear programming (i.e. linear continuous optimization) all decision variables are continuous. That is, no discrete variables are allowed.

Exemplary formulation of a continuous linear program

Linear integer programming, on  the other hand, is a specific variation of linear programming. In a linear integer program all decision variables are integers.

Exemplary formulation of a linear integer program

I provide a template for declaring integer programs in form of the model formulation below:

Some problems are modelled with both integer and continuous decision variables. Such models are referred to as mixed integer programs, or mixed integer programming. Other problems are modelled with binary decision variables. Such programs are a special subset of integer programs.

Applying integer programming to a production planning problem

In this paragraph I will analyze a simple production planning problem. More precisely I will solve a resource allocation problem. All data used in this problem is fictitious data.

Problem description of simple production planning problem in automotive industry

Below example is taken from ANDRADE, EL Introduction to Operations Research – methods and models for decision analysis. LTC publisher. 2nd edition. 2002

A small automotive manufacturer produces two competing car assemblies,  standard  and  luxury. Each unit of the  standard model requires 1 hour of sanding  and  1 hour of polishing. Each unit of the luxury module requires  1 hour of sanding  and  4 hours of polishing. The factory has  2 sanders  and  3 polishers. Eeach of these work centers has a weekly production capacity of 40 hours per week. The profit margins are $24 and $34, respectively, for each standard and luxury assembly unit. There are no demand restrictions for both assembly types.

I want to calculate the weekly production program that maximizes the manufacturer’s total profit.

First, to arrive at a descriptive model, I consider the following questions:

• What are the decision variables?
• What is the objective and how can a objective function be formulated?
• What are the constraints?

Defining relevant decision variables of the integer program

Relevant decision variables are listed below, and are discrete by nature (i.e. integer decision variables).

x1 = standard car
x2 = luxury car

If the manufacturer has a very high production output then I could neglect the integer constraint and model the problem as a continuous linear program. For example it does not make much of a difference whether the optimal production outout is x1 = 1000000 or x1 = 1000000.3. In that case I could “relax” the problem, meaning that I could solve it as a continuous problem instead of modelling it as a integer problem. Solving a continuous linear program is easier for the solver, and such problem can be solved with less runtime.

Defining the objective function of the integer optimization problem

Since the marginal profits are defined for both assembly types the total profit can be modelled as follows:

Profit = 24 * X1 + 34 * X2

Profit has to be maximized and thus this is a maximization problem.

Importing IBM’s DOCPLEX package and the solver CPLEX

Upon having defined decision variables and a relevant objective function I now install the CPLEX solver and the DOCPLEX module in Python. Using CPLEX and DOCPLEX I will be able to model the integer optimization problem in Python. I will furthermore be able to solve the integer program.

!pip install cplex
!pip install docplex

Upon importing CPLEX and DOCPLEX in Python I have to create an instance with the name of the model to be resolved:

from docplex.mp.model import Model

# creating an instance with a specified name
m = Model(name='carro_producao')

Next follows an important step of model declaration: The decision variables must be required to be of type integer. This is implemented in below decision variable declaration.

# by default all DOCPLEX variables have lower bound 0 and upper bound infinity 
x1 = m.integer_var(name='Standard')
x2 = m.integer_var(name='Luxo')

Modeling the constraints of the integer program using DOCPLEX in Python

1 * x1 + 1 * x2 <= 80 (40 hours per week  2 sanders)
1 *  x1 + 4  * X2 <= 120 (40 hours per week * 2 polishers)

# including constraints 

# constraint #1: Sander Limit 
ct_prod = m.add_constraint( 1 * x1 + 1 * x2 <= 80) # 40h semanais x 2Lixadoras

# constraint #4: Polisher Limit 
ct_prod = m.add_constraint( 1 * x1 + 4 * x2 <= 120) # 40h semanais x 3 Polidoras

Implementing the objective function with DOCPLEX in Python

Above all, as stated at the beginning of this article, the main objective is to maximize profit through the correct allocation of resources. That is we seek to maximize profits by making an optimal decision about how much to produce of each assembly type.

I implement the objective function in one line of Python code. Afterwards I print all model information, listing all information added to the model so far.

m.maximize(24 * x1 + 34 * x2)
m.print_information()

Model: carro_producao
 - number of variables: 2
   - binary=0, integer=2, continuous=0
 - number of constraints: 2
   - linear=2
 - parameters: defaults
 - objective: maximize
 - problem type is: MILP

From above DOCPLEX output we can see that the model is considered to be a mixed integer linear program (MILP). This is OK, since an algorithm that can solve a mixed integer linear program will also be capable of solving an integer linear program (ILP).

Solving the integer program with CPLEX, using CPLEX in Python

I complete this example by solving the integer optimization problem with CPLEX in Python. I do so in the line of Python code listed below.

s = m.solve()
m.print_solution()

objective: 2050
  Standard=67
  Luxo=13

The optimal production program is provided by the solver output in above coding example: 67 standard and 13 luxury assemblies. This will generate total profits of $ 2,050.

Concluding remarks and future work

Future articles will produce additional use cases for linear and non-linear programming and further demonstrate relevant implementations in Python. Besides Python other programming languages will be used, such as e.g. Julia. Both commercial and open-source solvers will be used. Several publications have already been released on our blog. For example we have already covered simple examples demonstrating LocalSolver and Gurobi.

Lucas Tayrone

Industrial and safety engineer. I have experience in continuous and business improvement, statistics as well as advanced analytics. Acting as PMO and business consultant in mining, metallurgy, civil construction and financial segments.