Pesquisa Operacional / Programação Linear

Universidade Federal de Catalão (UFCAT)

Resolvendo modelos de
programação linear inteira com
Python e PuLP

Prof. Dr. Thiago Alves de Queiroz

PYTHON

• Basic commands and

examples.
What is
• According to its creator, Guido van Rossum:

“Python is a high-level programming language,

and its core design philosophy is all about
code readability and a syntax which allows
programmers to express concepts in a few
lines of code.”
What is
• Python was named after the British comedy group Monty
Python;
• It is a high-level, interpreted, interactive, and object-
oriented programming language.
• Its flexibility allows you to do many things, both big and
small, besides having many libraries and modules to use.
• With Python, you can write basic programs and scripts, and
also create complex and large-scale digital solutions.
Interpreted Languages
• A program, for example, in C/C++ is compiled:
• Compilation involves translating the code to machine code.
• Machine code is the base-level form of instructions that can be directly
executed by the CPU.
• Upon successful compilation, it generates an executable file.
• Python is an interpreted language and not a compiled one,
although compilation is a step.
• Its code, written in .py file is first compiled into what is
called bytecode.
• This bytecode is a low-level set of instructions that can be executed by
an interpreter.
Why to Use Python
• Here is a sampling of its uses:
• Building desktop applications, including GUI applications, CLI
tools, and even games.
• Doing mathematical and scientific analysis of data.
• Building web and Internet applications.
• Doing computer systems administration and automating tasks.
• Performing DevOps tasks.
• Python is the foundation of some of the world’s most
popular websites, including Reddit, Dropbox, and YouTube,
to name a few.
Download and Install Python
• Python works on Linux, Mac, Windows, and several other
platforms.
• It comes preinstalled on macOS and on most Linux distributions.
• However, if you want to be up to date, then you probably need
to download and install the latest version.
• Check if you are using the latest version by opening the terminal
or command prompt/line and running the command:
python3 -V

• If your version is not the 3.10 or 3.9, follow the instructions given in
“Python-code editor, interpreter, and first code.pdf”.
The Basic Python Syntax
• The Python syntax is clear, concise, and focused on readability.
• Readability is one of the more attractive features of the language itself.
• It makes Python ideal for people who are learning to program.
• Some components of the Python syntax:
• Comments
• Variables
• Keywords
• Built-in data types
• Conditional statements
• Loops
• Functions
Python Indentation
• Indentation refers to the spaces at the beginning of a code line.
• Where in other programming languages the indentation in code
is for readability only, the indentation in Python is very
important.
• Python uses indentation to indicate a block of code.
• The number of spaces is up to you as a programmer, but it has
to be at least one:
• We have to use the same number of spaces in the same block of code;
otherwise Python will give you an error.
Python Indentation
• In languages like C, C++, Java, we use curly braces { } to
indicate the start and end of a block of code.
• In Python, we use space/tab as indentation to indicate the
same to the interpreter:
• To avoid errors: use the tab button to indent the code.
Python Indentation
• Some examples:
Comments
• Comments are pieces of text that live in your code but are
ignored by the Python interpreter as it executes the code.
• You can use comments to describe the code so that you and
other developers can quickly understand what the code does or
why the code is written in a given way.
• In general, your comments should be short and to the point (less
than 72 characters).
• To write a comment in Python, just add a hash mark (#) before
your comment text:
Variables
• They are names attached to a particular object.
• They hold a reference to the memory address at which an object
is stored.
• Once a variable is assigned an object, we can access the object
using the variable name.
• In Python, everything is an object, with at least three pieces of
data:
• Reference count
• Type
• Value
Variables
• We define variables with the syntax:

• Variable names can be any length and can consist of uppercase and
lowercase letters (A-Z, a-z), digits (0-9), and also the underscore
character (_).
• The first character cannot be a digit.
• Use a naming scheme that makes your variables intuitive and readable.
• The variable name should provide some indication as to what the values
assigned to it are.
• Avoid single-character names and use something more descriptive.
• Python is sensitive case language.
VARIABLES

Some examples:
Keywords
• Python has a set of special words that are part of its syntax,
which are called keywords.
• They are reserved words that have specific meanings and
purposes in the language:
• Do not use them for anything but those specific purposes.
Built-In Data Types
• Python has a handful of built-in data types, such
as numbers (integers, floats, complex
numbers), Booleans, strings, lists, tuples, dictionaries,
and sets.
• We can manipulate them with several tools:
• Operators (arithmetic, comparison, logical, bitwise, Identity)
• Built-in functions (abs, all, any, bool, list, len, set, hash, vars, min…)
• Data type methods (class, static, and regular instance methods).
Numbers
• Python provides integers,
floating-point numbers, and
complex numbers.
• Integers and floating-point
numbers are the most used
numeric types in day-to-day
programming.
• Complex numbers have specific
use cases in math and science.
Operations
• Operators represent operations, such as addition,
subtraction, multiplication, division, and so on…
• Python provides you with a bunch of built-in functions for
manipulating numbers.
• There are modules available in the Python standard library,
such as math, that also provide you with functions to
manipulate numbers.
• To use the functions associated with these modules, we first have to
import the module.
• Then, we access the function using module.function_name().
Booleans
• Booleans are implemented as a subclass of integers with
only two possible values in Python: True or False.
• Note that these values must start with a capital
letter.
• We use Boolean values to express the truth value of an
expression or object.
• Booleans are handy when we are
writing predicate functions or when we are
using comparison operators, such as greater than (>),
lower than (<), equal (==), and so on.
Operators
• They are special symbols that designate that some sort of computation
should be performed. The values that an operator acts on are
called operands.
• A sequence of operands and operators, like a + b * 5, is called an
expression.
• All operators that the language supports are assigned a precedence.
• In an expression, all operators of highest precedence are performed
first.
• Once those results are obtained, operators of the next highest
precedence are performed:
• It continues, until the expression is fully evaluated.
• Any operators of equal precedence are performed in left-to-right order.
Arithmetic Operators
Comparison Operators
Logical Operators
OPERATOR
PRECEDENCE
The Standard Library
• One of the great things about Python is the plethora of available
modules, packages, and libraries both built into the Python core and
made available by third-party developers.
• These modules, packages, and libraries can be quite helpful in your day-
to-day work as a Python coder.
• Here are some of the most used built-in modules:
• math for mathematical operations.
• random for generating pseudo-random numbers.
• re for working with regular expressions.
• os for using operating system-dependent functionalities.
• itertools for working with iterators.
• collections for specialized container data types.
The Standard Library
• For example, here we import math to use pi, find the square
root of a number with sqrt(), and raise a number to a power
with pow():
Import
• In Python, we use the import keyword to make code in
one module available in another:
• A module usually corresponds to one .py file containing Python
code.
• Imports in Python are important for structuring the
code effectively.
• Using imports properly will make we more productive,
allowing to reuse code while keeping the projects
maintainable.
Import

• Note that we write math.pi and not just simply pi.

• In addition to being a module, math acts as a namespace that
keeps all the attributes of the module together:
• Namespaces are useful for keeping the code readable and
organized.
• We can list the contents of a namespace with dir():
Import
• There are other ways to use import that allow to import
specific parts of a module and to rename the module as we
import it:
To import only the pi variable from the math To rename modules and attributes as they are
module: imported:
Input
• Programs often need to obtain data from the user, usually by
way of input from the keyboard:
• The simplest way to accomplish this in Python is with input().
• input() pauses program execution to allow the user to type
in a line of input from the keyboard.
• Once the user presses the Enter key, all characters typed are read
and returned as a string.
• It always returns a string. If we want a numeric type, then we need
to convert the string to the appropriate type with the int(), float(),
or complex() built-in functions.
Input
• Some examples of obtaining data from the keyboard:
Output
• In addition to obtaining data from the user, a program will
also usually need to present data back to the user:
• We can display program data to the console in Python
with print().
• To display objects to the console, pass them as a comma-
separated list of arguments to print().
• Any type of object can be specified as an argument to print().
Output
• The Python string .format() method goes well beyond in
versatility:
• The replacement fields can be specified in any order, and they can
appear more than once. We can even omit them.
PYTHON

• PuLP: library to linear

optimization problems
PuLP: Python Library to Linear Optimization
• PuLP is a Linear Programming (LP) modeler written in Python.
• It can generate MPS (Mathematical Programming System) or LP
files:
• It can also call solvers as GLPK, COIN-OR CLP/CBC, CPLEX,
GUROBI, MOSEK, XPRESS, CHOCO, MIPCL, SCIP.
• To install this package:
• Go to the command prompt and use the command:
• python -m pip install pulp
or (it depends on the operating system)
• python3 -m pip install pulp

• More details in:

• https://www.coin-or.org/PuLP/main/installing_pulp_at_home.html
PuLP
• We do not have to mathematically modify our problem or
use vectors and matrices.
• Let’s solve the following linear programming problem:
PuLP
• We start by importing what we need:
from pulp import *

• The first step is to initialize an instance of LpProblem to

represent your model:
#create the model
model = LpProblem(name="model 1", sense=LpMaximize)

• We use the sense parameter to define:

• minimization (LpMinimize or 1, which is the default), or
• maximization (LpMaximize or -1).
PuLP
• We can define the decision variables as instances of the LpVariable class:
• LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)
#create the variables
x = LpVariable(name="x", lowBound=0)
y = LpVariable(name="y", lowBound=0)
• We need to provide a lower bound with lowBound=0 because the
default value is negative infinity.
• The parameter upBound defines the upper bound, but we can omit it
here because it defaults to positive infinity.
• The optional parameter cat defines the category of a decision variable:
• It can be: Integer, Binary or Continuous (default).
PuLP
• The next step is to create objective function as well as to assign it to
the model:
• We just write Python expressions and use the += operator to append them to the model:
#objective function
model += lpSum([x, 2*y]), "objective function"

• Then, the constraints are assigned to the model:

#constraints
model += 2*x+y <= 20, "constraint 1"
model += -4*x + 5*y <= 10, "constraint 2"
model += -x + 2*y >= -2, "constraint 3"
model += -x + 5*y == 15, "constraint 4"
PuLP
• We can use .writeLP(“name.lp”) to write the model to an output file.
#saving the model to a LP format
model.writeLP("mod1.lp")

• We are now ready to solve the problem .solve() on the model object. It uses the default
solver (CBC):
#solving the model
model.solve()
• solve() calls the underlying solver, modifies the model object, and gives the integer status of the
solution:
PuLP
• We can get the optimization results as the attributes
of model:
• The method value() return the actual values of the attributes:
#printing the status and solution
print("status: ", model.status)
print("objective function: ", model.objective.value())

print(x.name, " = " , x.value())

print(y.name, " = " , y.value())

status: 1
objective function: 16.8181817
x = 7.7272727
y = 4.5454545
PuLP
• The Python program is:
Knapsack Problems
• They involve the choice of objects to be placed in one or
more knapsacks in order to maximize the profit. Some
variants:
• 0-1 Knapsack: there are n projects and capital b for
investment. Each project has the cost aj and an expected
return pj. We want to select a subset of projects that
maximize the total expected return without exceeding
the capital available.
• Integer Knapsack: like the 0-1 Knapsack, but now we
can invest more than once in the same project.
• Multiple Knapsacks: there are n items and m equal
knapsacks of capacity bi. Each item has profit pj and
weight wj. We want m disjoint subset of items, such that
each subset respect the knapsack’s capacity bi and the
total profit is maximum.
0-1 Knapsack Problem
• Parameters:
• n is the number of items (for j = 1, ..., n).
• b is the capacity of the knapsack.
• aj is the weight of item j.
• pj is the value (profit) of item j.
• Variables:
• xj = 1, if item j is chosen.
• xj = 0, otherwise.
0-1 Knapsack Problem

Total value in the knapsack

To respect the knapsack

capacity

Domain of the variables (binary)

Example 1: 0-1 Knapsack Problem
• Model and write a Python code to solve the following problem.
• Consider we have a knapsack capacity of b = 100 and at most 8
items to choose. The value pj and the weight aj of each item j
are:

• Determine the model that allows to select a subset of items that

maximize the total value while respecting the knapsack capacity.
Example 1: 0-1 Knapsack Problem
• This is a typical 0-1 knapsack problem. Then, consider a
binary variable for each item as:
• xj = 1, if item j is chosen.
• xj = 0, otherwise.
• The model is:
Maximize

Subject to:
Example 1:
• A Python code for
the 0-1 Knapsack
Problem is:

Output:
• In several industrial processes, items are

Cutting
produced by cutting larger objects.
• These larger objects can have one, two, or
three relevant dimensions such as:

Problems • Width: steel bars, paper rolls...

• Length and width: wooden plates, steel
sheets.
• Length, width, and height: block foam for
mattress production.
• Some examples:
• One-dimensional: consists of cutting
available bars of size L, to produce m
types of items of sizes l1, l2, …, lm and
demands b1, b2, …, lm, respectively. We
want to minimize the number of bars
used for cutting all items’ demands.
• Two-dimensional: we have a rectangular
plate to be cut into several smaller
rectangular pieces in order to maximize
the plate’s area cut.
One-dimensional Cutting Stock Problem
• Parameters:
• n is the number of the bars in stock (for i = 1, ..., n).
• m is the number of types of items (for j = 1, ..., m).
• L is the size of each bar.
• lj is the size of item j.
• bj is the demand of item j.
• Variables:
• yi = 1, if bar i is cut.
• yi = 0, otherwise.
• xij = integer number of items j to be cut out of bar i.
One-dimensional Cutting Stock Problem
Number of bars that are cut

To cut the required demand

of items

To assure that items are cut

from used bars and not
violate the size of bars

Domain of the variables (binary and integer)

Example 2: 1D Cutting Stock Problem
• Write a Python program that reads a text file with the parameters,
solve the One-dimensional Cutting Stock model below with PuLP,
and write the final solution (variables’ values and objective function
value) in a text file. Use functions to read the instance file and write
the final solution.
Parameters:
n is the number of the bars in
stock (for i = 1, ..., n).
m is the number of types of
items (for j = 1, ..., m).
L is the size of each bar.
lj is the size of item j.
bj is the demand of item j.
Example 2: Instance File cut.txt

Input file for reading

data (instance file)
A Python code for
the 1D Cutting
Stock Problem:
A Python code for
the 1D Cutting
Stock Problem:
Example
• Solution of the 1D
Cutting Stock
Problem: Output file
Exercise 1: Problem
• Model and write a Python code to solve the following LP problem:
• Problem. A factory produces four different products, and that the daily
produced amount of the first product is x₁, the amount produced of the
second product is x₂, and so on. The goal is to determine the profit-
maximizing daily production amount for each product, bearing in mind the
following conditions:
• The profit per unit of product is $20, $12, $40, and $25 for the first, second, third,
and fourth product, respectively.
• Due to manpower constraints, the total number of units produced per day cannot
exceed fifty.
• For each unit of the first product, three units of the raw material A are consumed.
Each unit of the second product requires two units of the raw material A and one
unit of the raw material B. Each unit of the third product needs one unit of A and
two units of B. Finally, each unit of the fourth product requires three units of B.
• Due to the transportation and storage constraints, the factory can consume up to
one hundred units of the raw material A and ninety units of B per day.
Exercise 1: Model
• The mathematical model can be defined like this:
line 1
line 2
line 3
line 4
line 5

• The objective function (profit) is defined in line 1. The

manpower constraint follows from line 2. The constraints on the
raw materials A and B can be derived from lines 3 and 4 by
summing the raw material requirements for each product.
• Finally, the product amounts cannot be negative, so all decision
variables must be greater than or equal to zero.
Exercise 2: Problem
• A company is evaluating locations to open new warehouses to
service geographically spread customers.
• There is a building cost associated with each possible location, and
each location has a limited capacity to serve customers.
• There is a transportation cost to send 1 ton of products between
each possible warehouse and customer.
• Besides that, each customer has a required demand which one or
more warehouses must service exactly.
• Model this problem to decide where to open the warehouses with
the minimum possible cost and serve all customers’ demands.
Exercise 2: Model
Cost of opening facilities

Cost of serving customer j

by the warehouse at location i

Customers’ demand must be

exactly met.

Once a warehouse is open

at location i, the demand its
serves cannot violate its
maximum capacity.

Domain of the variables

Variables:
yi = 1, if a warehouse is open at location i.
yi = 0, otherwise.
xij ≥ 0, the amount of tons sent from the warehouse at i to the customer j.
Exercise 2: Program
• Write a Python program that reads a text file with the problem
parameters, solve the model with PuLP, and write the final solution
(variables’ values and objective function value) in a text file.
• Use functions to read the instance file and write the final solution.
• Problem’s parameters:
• J is the set with the customers’ location (for j = 1, ..., n).
• I is the set with possibly locations for facilities (for i = 1, ..., m).
• fi is the cost of opening a facility at location i.
• Qi is the maximum capacity that the facility at location i can service.
• qj is the demand of customer j.
• cij is the cost of serving customer j by the facility at location i.
Exercise 2: Instance File fac.txt
Bibliography
• CONFORTI, M.; CORNUEJOLS, G.; ZAMBELLI, G. Integer programming. Switzerland:
Springer International Publishing, 2014.
• NEMHAUSER, G. L.; WOLSEY, L. A. Integer and Combinatorial Optimization. John Wiley
and Sons, New York, 1988.
• https://realpython.com/
• https://docs.python.org/3/tutorial/index.html
• https://www.w3schools.com/python/
• https://www.faceprep.in/python
• https://exercism.io/tracks/python
• https://dbader.org/blog/python-file-io
• https://coin-or.github.io/pulp
• VANDERPLAS, J. Python Data Science Handbook. O'Reilly Media, Sebastopol, 2016.