Chapter 6 - Integer Programming (Part 1)

M C S D 11 3 3 O p e r a t i o n s R e s e a r c h & O p t i m i z a t i o n
CHAPTER 6:
INTEGER PROGRAMMING
(PART 1)
nzah@utm.my-20232024(S1)
UTM JOHOR BAHRU

Introduction
• Linear programming:
• Assumes that the decision variables are continuous.
• In practice, decision variables may need to be integers.
§ Sometimes, binary (i.e., 0 or 1)
• When the decisions variables are integer, we have integer programming problem.
o Pure integer programming (IP)- All decision variables required to have integer solution values.
o Binary integer programming (BIP)-All decision variables required to have integer values of zero or one.
o Mixed integer programming (MIP)-Some of the decision variables (but not all) required to have integer
values.
2
Integer Programming Model
§ Rounding non-integer solution values up to the nearest

integer value can result in an infeasible solution.
§ A feasible solution is ensured by rounding down non-integer

solution values but may result in a less than optimal (sub-
optimal) solution.
3
Example 1
§ Machine shop obtaining new presses and lathes.
§ Marginal profitability: each press $100/day; each lathe $150/day.
§ Resource constraints: $40,000, 200 sq. ft. floor space.
§ Machine purchase prices and space requirements:
Required Floor
Machine Purchase
Space
Price
(sq. ft.)
Press 15 $8,000
Lathe 30 4,000
§ How many of each type of machine to purchase to maximize the daily increase in
profit?
4
Example 1 (cont’d)
𝑥1 = number of presses
𝑥2 = number of lathes
Integer Programming Model:
Maximize 𝑍 = 100𝑥1 + 150𝑥2
Subject to:
8000𝑥1 + 4000𝑥2 £ 40000
15𝑥1 + 30𝑥2 £ 200
𝑥1, 𝑥2 ³ 0 and integer
5
§ Optimal Solution:
Z = 1,055.56
𝑥1 = 2.22 presses
𝑥2 = 5.55 lathes
§ The dots indicate integer solution points.

§ Rounding non-integer solution values up to
the nearest integer value (𝑥1 = 2 and 𝑥2 = 6)
can result in an infeasible solution:
Feasible Solution Space with Integer Solution Points
6
§ The point (𝑥1 = 2 and 𝑥2 = 5) is the rounded-

down solution. Notice that as the objective
function edge moves outward through the
feasible solution space.
§ One of the difficulties of simply rounding down
non-integer values is that another integer
solution may result in a higher profit (𝑥1 = 1 and
𝑥2 = 6)
§ Thus, a more direct approach for solving integer
problems is required.
Feasible Solution Space with Integer Solution Points
7
Integer Programming using Excel Solver
8
Integer Programming using Phython
# Import PuLP modeler functions

from pulp import *
# Create the 'prob' variable to contain the problem data
prob = LpProblem("Machine",LpMaximize)
# The 2 variables are created with a lower limit of zero
x1=LpVariable("presses",0,None,'Integer')
x2=LpVariable("lathes",0,None,'Integer')
# The objective function is added to 'prob' first
prob += 100*x1 + 150*x2, "Total daily profit"
# The four constraints are entered
prob += 8000*x1 + 4000*x2 <= 40000, "Purchased Price"
prob += 15*x1 + 30*x2 <= 200, "Floor Space"
9
Integer Programming using Python (cont’d)
# The problem data is written to an .lp file

prob.writeLP("machines.lp")
# The problem is solved using PuLP's choice of Solver
prob.solve()
# The status of the solution is printed to the screen
print ("Status:", LpStatus[prob.status])
# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
print(v.name, "=", v.varValue)
# The optimised objective function value is printed to the screen
print ("Total Profit = ", value(prob.objective))
10
Integer Programming using Python (cont’d)
11
Exercise 1
A textbook publishing company has developed two new sales regions and is planning to transfer
some of its existing sales force into these two regions. The company has 10 salesperson available for
the transfer. Because of the different geographic configurations and the location of schools in each
region, the average annual expenses for a salesperson differ in the two regions:
§ The average is $10,000 per salesperson in region 1; $7,000 per salesperson in region 2.
The total annual expense budget for the new regions is $72,000. It is estimated that a salesperson in
region 1 will generate an average of $85,000 in sales each year, and a salesperson in region 2 will
generate $60,000 annually in sales. The company wants to know how many salesperson to transfer
into each region to maximize increased sales.
12
Example 2
§ Recreation facilities selection to maximize daily usage by residents.
§ Resource constraints: $120,000 budget; 12 acres of land.
§ Selection constraint: either swimming pool or tennis center (not both).
§ Data:
13
Binary Integer Programming Model:
Maximize 𝑍 = 300𝑥1 + 90𝑥2 + 400𝑥3 + 150𝑥4

Subject to:
35,000𝑥1 + 10,000𝑥2 + 25,000𝑥3 + 90,000𝑥4 £ 120,000
4𝑥1 + 2𝑥2 + 7𝑥3 + 3𝑥4 £ 12 (𝑎𝑐𝑟𝑒𝑠)
𝑥1 + 𝑥2 £ 1 ( 𝑓𝑎𝑐𝑖𝑙𝑖𝑡𝑦)
𝑥1, 𝑥2, 𝑥3, 𝑥4 = 0 𝑜𝑟 1
𝑥1 = 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑎 𝑠𝑤𝑖𝑚𝑚𝑖𝑛𝑔 𝑝𝑜𝑜𝑙
𝑥2 = 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑎 𝑡𝑒𝑛𝑛𝑖𝑠 𝑐𝑒𝑛𝑡𝑒𝑟
𝑥3 = 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑎𝑛 𝑎𝑡ℎ𝑙𝑒𝑡𝑖𝑐 𝑓𝑖𝑒𝑙𝑑
𝑥4 = 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑎 𝑔𝑦𝑚𝑛𝑎𝑠𝑖𝑢𝑚
14
Example 2 (cont’d) Binary Integer Programming Model – in Excel Solver
C5*C12+D5*C13+E5*C14+F5*C15
15
Example 2 (cont’d) Binary Integer Programming Model – in Excel Solver
§ Recreation facilities selection to maximize daily usage by residents.

=> Swimming Pool and Athletic Field
§ Total daily usage = 700
16
Example 2 (cont’d) Binary Integer Programming Model – in Python
# Import PuLP modeler functions

from pulp import *
# Create the 'prob' variable to contain the problem data

prob = LpProblem("facility",LpMaximize)
# The 4 variables are created with a lower limit of zero

x1=LpVariable("SP",0,1,'Integer')
x2=LpVariable("TC",0,1,'Integer')
x3=LpVariable("AF",0,1,'Integer')
x4=LpVariable("G",0,1,'Integer')
# The objective function is added to 'prob' first
prob += 300*x1 + 90*x2+400*x3+150*x4, "Total daily usage"
# The constraints are entered

prob += 35000*x1 + 10000*x2+25000*x3+90000*x4 <= 120000, "Costs"
prob += 4*x1 + 2*x2+7*x3+3*x4 <= 12, "acre"
prob += 1*x1 + 1*x2 <= 1, "facility "
17
# The problem data is written to an .lp file

prob.writeLP("facilities.lp")
# The problem is solved using PuLP's choice of Solver

prob.solve()
# The status of the solution is printed to the screen

print ("Status:", LpStatus[prob.status])
# Each of the variables is printed with it's resolved optimum value

for v in prob.variables():
print(v.name, "=", v.varValue)
# The optimised objective function value is printed to the screen

print ("Total Usage = ", value(prob.objective))
18
19
Mix Integer Programming Model
In a mixed integer model, some solution values for decision variables are
integers and others can be non-integer.
Example 3:
Nancy Smith has $250,000 to invest in three alternative investments—condominiums, land,
and municipal bonds. She wants to invest in the alternatives that will result in the greatest
return on investment after 1 year. Each condominium costs $50,000 and will return a profit of
$9,000 if sold at the end of 1 year; each acre of land costs $12,000 and will return a profit of
$1,500 at the end of 1 year; and each municipal bond costs $8,000 and will result in a return
of $1,000 if sold at the end of 1 year. In addition, there are only 4 condominiums, 15 acres of
land, and 20 municipal bonds available for purchase.
20
𝑥1 = condominiums purchased
𝑥2 = acres of land purchased
𝑥3 = bonds purchased
Maximize 𝑍 = 9000𝑥1 + 1500𝑥2 + 1000𝑥3
Subject to:
50000𝑥1 + 12,000𝑥2 + 8,000𝑥3 £ 250,000
𝑥1 £ 4 𝑐𝑜𝑛𝑑𝑜𝑚𝑖𝑛𝑖𝑢𝑚𝑠
𝑥2 £ 15 𝑎𝑐𝑟𝑒𝑠
𝑥3 £ 20 𝑏𝑜𝑛𝑑𝑠
𝑥2 ³ 0
𝑥1, 𝑥3 ³ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟
21
Notice that the constraint values for the

availability of each type of investment is
enter directly into Solver
(i.e., 4 condos, 15 acres of land, and 20
bonds)
Integer requirement for condos and

bonds)
22

Chapter 6 - Integer Programming (Part 1)

Uploaded by

Copyright:

Available Formats

Chapter 6 - Integer Programming (Part 1)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 6 - Integer Programming (Part 1)

Uploaded by

Copyright:

Available Formats

M C S D 11 3 3 O p e r a t i o n s R e s e a r c h & O p t i m i z a t i o n

UTM JOHOR BAHRU

• Assumes that the decision variables are continuous.

• In practice, decision variables may need to be integers.

§ Sometimes, binary (i.e., 0 or 1)

§ Rounding non-integer solution values up to the nearest

§ A feasible solution is ensured by rounding down non-integer

§ The dots indicate integer solution points.

Feasible Solution Space with Integer Solution Points

§ The point (𝑥1 = 2 and 𝑥2 = 5) is the rounded-

Feasible Solution Space with Integer Solution Points

# Import PuLP modeler functions

# The problem data is written to an .lp file

Maximize 𝑍 = 300𝑥1 + 90𝑥2 + 400𝑥3 + 150𝑥4

§ Recreation facilities selection to maximize daily usage by residents.

# Import PuLP modeler functions

# Create the 'prob' variable to contain the problem data

# The 4 variables are created with a lower limit of zero

# The constraints are entered

# The problem data is written to an .lp file

# The problem is solved using PuLP's choice of Solver

# The status of the solution is printed to the screen

# Each of the variables is printed with it's resolved optimum value

# The optimised objective function value is printed to the screen

Notice that the constraint values for the

Integer requirement for condos and

You might also like