CE 467
Systems Engineering I
Department of Civil Engineering
SET 10: INTEGER PROGRAMMING MODELS
Dr. Emmanuel A. Donkor
Department of Civil Engineering, College of Engineering
Kwame Nkrumah University of Science and Technology, Kumasi, Ghana
OUTLINE
1. The Nature of Integer Programs
2. Modeling Logical Constraints
3. Special Classes of Integer Programming Models
i. Knapsack (or burglar) problem
ii. Set-covering problem
iii. Travelling salesman problem
CE 475 COPYRIGHT Dr. E. A. Donkor 2
1
Nature of Integer Programming Models
CE 475 COPYRIGHT Dr. E. A. Donkor 3
NATURE OF INTERGER PROGRAMMING PROBLEMS
• An integer program is a linear program that requires some or all decision
variables to have integer values
• Integer programming is necessary when fractional values for a linear
program do not make sense
CE 475 COPYRIGHT Dr. E. A. Donkor 4
NOMENCLATURE
• PIP: A pure integer program is one where all decision variable are
required to take integer values
• MIP: A Mixed Integer Program is one where some, but not all,
decision variables are required to take integer values
• BIP: A Binary Integer Program, or a 0-1 integer program, requires
decision variables to take values in the set {0,1}. Yes/No decision.
• An LP relaxation of an IP is a model that requires integer solutions
but which has no integer or 0-1 constraints, and so results in
fractional solutions.
CE 475 COPYRIGHT Dr. E. A. Donkor 5
Motivation: The Need for Integer Programming
• Supposing a problem involving (1)
Number of Truck Drivers and (2)
Number of Trucks yields the
solution shown in the graph.
• These resources cannot take
fractional values
• So what solution will you adopt?
• Any implications of the adopted
solutions?
CE 475 COPYRIGHT Dr. E. A. Donkor 6
Possible Solutions and Implications (of Rounding)
CE 475 COPYRIGHT Dr. E. A. Donkor 7
Example 10.1
In the problem stated below, the decision variables x1, and x2 can take only
integer values.
max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0
a) Solve the problem as an LP and recommend possible values for x1 and
x2. What are the implications of your proposed solutions?
b) Solve the problem as an IP
c) Compare the LP solution and the IP solution
CE 475 COPYRIGHT Dr. E. A. Donkor 8
Example 10.1a: Solution---LP Relaxation
max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0
Optimal solution: x1 = 1.857, x2 = 0
Optimal Value: 39
Implications of solution:
• solution not usable because x1
and x2 are supposed to be
integers
• Note that rounding off x1 to 2,
results in an infeasible solution
CE 475 COPYRIGHT Dr. E. A. Donkor 9
Example 10.1b: A Pure IP Model (Solving as IP)
Problem
Max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0; x1, x2 integer
CE 475 COPYRIGHT Dr. E. A. Donkor 10
Example 10.1b: Solution---A Pure IP
Max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13;
x1, x2 ≥ 0; x1, x2 integer
Optimal solution: x1 = 0, x2 = 3
Optimal Value: 33
CE 475 COPYRIGHT Dr. E. A. Donkor 11
COMPARING SOLUTIONS:
GEOMETRICAL ILLUSTRATION OF AN IP
Pure IP: Max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0; x1, x2 integer (0,3): IP Solution
Optimal solution (0,3); Optimal value = 33
LP Relaxation: max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13 x1, x2 ≥ 0
Optimal solution (1.857,0); Optimal value = 39 𝟏. 𝟖𝟓𝟕, 𝟎 : LP Relaxation
∗ ∗
NOTE: For maximization problems: 𝑍"# ≥ 𝑍&#
∗ ∗
For minimization problems: 𝑍"# ≤ 𝑍&#
CE 475 COPYRIGHT Dr. E. A. Donkor 12
Example 10.1c: An MIP
max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0;
x1 integer
CE 475 COPYRIGHT Dr. E. A. Donkor 13
Example 10.1c An MIP---Solution
max z = 21x1 + 11x2
s.t 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0; x1 integer
Optimal solution: x1 = 1, x2 = 1.5
Optimal Value: 37.5
CE 475 COPYRIGHT Dr. E. A. Donkor 14
Example 10.1d: A BIP
max z = 21x1 + 11x2
s.t 7x1 + 8x2 ≤ 13
x1, x2 is binary
CE 475 COPYRIGHT Dr. E. A. Donkor 15
Example 10.1d: A BIP---Solution
max z = 21x1 + 11x2
s.t 7x1 + 8x2 ≤ 13 This problem could have
been solved intuitively,
x1, x2 is binary without a spreadsheet
Optimal solution: x1 = 1, x2 = 0;
Optimal Value: 21
CE 475 COPYRIGHT Dr. E. A. Donkor 16
Exercise: Re-call; Making Aquas and Hydros: Original Model
Maximize: 350𝑥3 + 300𝑥5
s.t 𝑥3 + 𝑥5 ≤ 200 (pump constraints)
9𝑥3 + 6𝑥5 ≤ 𝟏𝟓𝟔𝟔 (labour constraint)
12𝑥3 + 16𝑥5 ≤ 𝟐𝟖𝟖𝟎 (steel tubing constraint)
𝑥3 ≥ 0; 𝑥5 ≥ 0, (non-negativity constraint)
CE 475 COPYRIGHT Dr. E. A. Donkor 17
Revised Model
Test Scenarios
Maximize: 350𝑥3 + 300𝑥5
1. Round solutions up and
check for feasibility
s.t
𝑥3 + 𝑥5 ≤ 200 (pump constraints) 2. Round down solutions and
check for feasibility
9𝑥3 + 6𝑥5 ≤ 1520 (labour constraint)
3. Determine optimal integer
12𝑥3 + 16𝑥5 ≤ 2650 (steel tubing constr) solution
𝑥3 ≥ 0; 𝑥5 ≥ 0, (non-negativity constr)
CE 475 COPYRIGHT Dr. E. A. Donkor 18
2
Modeling Logical Constraints
CE 475 COPYRIGHT Dr. E. A. Donkor 19
MODELING LOGICAL CONDITIONS
• Binary variables {0,1} can be used to model several logical constraints.
Interpret the following constraints, if 𝑥> is binary:
• Example 1 (at most): 𝑥3 + 𝑥5 + 𝑥? + 𝑥@ + 𝑥A + 𝑥B ≤ 3
• Example 2 (mutual exclusivity): 𝑥3 + 𝑥? + 𝑥B =1
CE 475 COPYRIGHT Dr. E. A. Donkor 20
3 Selected Classes of Integer Programs
Knapsack Problem
CE 475 COPYRIGHT Dr. E. A. Donkor 21
IP CLASS 1: KNAPSACK PROBLEMS
A knapsack problem is a Binary
Integer problem with only one
constraint involving a linear
combination of decision variables.
Here, the “goal is to get the most
value in the knapsack without
overloading it” (Albright &
Winston, 2005).
CE 475 COPYRIGHT Dr. E. A. Donkor 22
APPLICATION: CAPITAL BUDGETING
District assemblies plan many projects but have limited budgets for their
implementation. In order to make efficient use of the available financial
resources, Engineering economics may be applied to identify projects that
can be implemented. The objective is to maximize NPV, when each of
these projects require a specific cost and yields a specific NPV.
CE 475 COPYRIGHT Dr. E. A. Donkor 23
EXAMPLE 10.2: CAPITAL BUDGETING
A district assembly is considering Project Cost Expected NPV
six independent investment projects 1 $75 $141
for a total available budget of 2 $90 $187
$250,000. Which of these projects 3 $60 $121
should the district invest in if 4 $30 $83
management wants to maximize 5 $100 $265
expected NPV? All values are in 6 $50 $127
thousands.
CE 475 COPYRIGHT Dr. E. A. Donkor 24
10.2a: Model Formulation And Solution
Let xi represent the decision to either invest or not to invest in project i. Then
1, 𝑖𝑓 𝑝𝑟𝑜𝑗𝑒𝑐𝑡 𝑖 𝑖𝑠 𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑑
𝑥> = O
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
∀ 𝑖 = 1,2, … , 6
Model Formulation
Max: 141𝑥3 + 187𝑥5 + 121𝑥? + 83𝑥@ + 265𝑥A + 127𝑥B
s.t 75𝑥3 + 90𝑥5 + 60𝑥? + 30𝑥@ + 100𝑥A + 50𝑥B ≤ 250
𝑥> 𝑖𝑠 𝑏𝑖𝑛𝑎𝑟𝑦 ∀ 𝑖 = 1,2, … , 6
CE 475 COPYRIGHT Dr. E. A. Donkor 25
