COMP9334: Capacity Planning of Computer Systems and Networks
Week 9A: Optimisation (2): Integer programming
COMP9334, Chun Tung Chou, 2021
Optimisation
What have we covered so far?
Formulation of linear programming (LP) problems Using AMPL to solve LP problems
This lecture
Different types of LP problems
Formulation of integer programming (IP) problems Using AMPL to solve IP problems
COMP9334, Chun Tung Chou, 2021
Page 1
Linear programming
Linear programming (LP) is a tool for solving a type of optimization problems where
Decision variables are real numbers
Objective function is linear in the decision variables All the constraints are linear in the decision variables
LP problems with 2 variables have a nice graphical solution, e.g.
min x1 + x2 subject to 2×1 + x2 ≥ 4 x1 + 3×2 ≥ 6
x1,x2 ≥0
COMP9334, Chun Tung Chou, 2021 Page 2
6
Feasible solutions
x2
5
4
3
2 1
Feasible solutions
Any (x1, x2) that satisfies all the constraints is a feasible solution. Otherwise, it is an infeasible solution
For LP problems with 2 variables, the feasible region is a polygon
In general, it is a polyhedron
2×1+x2 >= 4
x1+3×2>=6
x1
0123456
COMP9334, Chun Tung Chou, 2021
Page 3
Objective function
x2
6
5
4
3
2 1
Decreasing
x1+x2
x1+x2 =6 x1+x2=4
Since the aim is to minimize x1 + x2, we look for contour of x1 + x2
0123456
x1
COMP9334, Chun Tung Chou, 2021
Page 4
Optimal solution
x2
6
5
4
3
2 1
Decreasing x1+x2
Optimal solution of this LP problem is x1 = 1.2, x2 = 1.6, with objective function value = 2.8
Optimal solution
0123456
x1
COMP9334, Chun Tung Chou, 2021
Page 5
Extreme point
x2
6
5
4
3
2
= Extreme point/vertex
(0,4)
Regardless of the objective function, the optimal solution of an LP problem (if it exists) must be at one of the extreme points or vertices of the polyhedron formed by the constraints
(1.2,1.6)
1
0123456
(6,0)
x1
COMP9334, Chun Tung Chou, 2021
Page 6
Special cases: Multiple optimal solutions
What is the optimal solution to the following LP problem?
min x1 + x2 subjectto x1 +x2 ≥4
x1 + 3×2 ≥ 6 x1,x2 ≥0
COMP9334, Chun Tung Chou, 2021 Page 7
Special cases: Infeasible LP
What is the optimal solution to the following LP problem?
min x1 + x2 subject to x1 + 3×2 ≤ 4 x1 + 3×2 ≥ 6
x1,x2 ≥0
COMP9334, Chun Tung Chou, 2021 Page 8
Special cases: Unbounded LP
What is the optimal solution to the following LP problem?
max x1 + x2 subject to 2×1 + x2 ≥ 4 x1 + 3×2 ≥ 6
x1,x2 ≥0
COMP9334, Chun Tung Chou, 2021 Page 9
Algorithms for LP
Simplex method (Dantzig 1947)
Found in many LP software
Principle: Move from an extreme point to another Worst-case complexity: Exponential
Average performance on practical LP problems: Very good
COMP9334, Chun Tung Chou, 2021
Page 10
Algorithms for LP (cont.)
Interior-point method (Karmarkar 1984)
Very competitive compared with the simplex method Principle: Move from an interior point to another Worst-case complexity: Polynomial
The algorithm for large LP problems
COMP9334, Chun Tung Chou, 2021
Page 11
Motivating Ex 1: Cloud computing (Week 8B)
A job requires 107 million cycles
Question: How should the job be split, so that completion time T is
minimized subject to two constraints: Completion time constraint: T ≤ 4,800 sec
Cost constraint: C ≤ 1,500 dollars
COMP9334, Chun Tung Chou, 2021 Page 12
Motivating example 2: Cloud computing
Now, each resource further charges a set up cost of fixed amount
Resource 1: Set up cost = 200 dollars Resource 2: Set up cost = 100 dollars Resource 3: Set up cost = 50 dollars
Again, the computation job has the following requirements:
Requires 107 million cycles Completion time ≤ 4,800 sec Cost ≤ 1,500 dollars Minimize the completion time
Problem faced by the job:
From which resource should we buy the computing power? How many cycles to buy from each chosen resource?
COMP9334, Chun Tung Chou, 2021
Page 13
Yes-or-no decision
What is the cost of buying cycles from a chosen resource? Yes-or-no questions: Is Resource i chosen?
E.g. is Resource 3 chosen? 50
Yes⇒x3 >0⇒Cost=2000×x3 +200×1
No ⇒x3 =0⇒Cost=2000×x3 +200×0 50
This type of optimization problems involves 0-or-1 logical decisions among other decisions
You will learn in the rest of this lecture
How to formulate this type of optimization problems How to solve this type of optimization problems
COMP9334, Chun Tung Chou, 2021 Page 14
Formulating optimization problem
Given:
n resources
Resource i offers computing power at a speed of pi million cycles/sec with cost ci dollars/sec
Set up cost for using Resource i is si dollars
Customer requires N million cycles
Completion time ≤ Tmax
Cost ≤ Cmax
Decision variables:
yi = xi =
T = COMP9334, Chun Tung Chou, 2021
1 if Resource i is chosen 0 otherwise
fraction of the job allocated to Resource i
completion time, which is maxi Nxi pi
Page 15
Exercise
Exercise: Express the cost of using Resource i in terms of ci, N, xi, pi, si, yi Recall that:
Resource i offers computing power at a speed of pi million cycles/sec with cost ci dollars/sec
Set up cost for using Resource i is si dollars
Customer requires N million cycles
Decision variables
xi = yi =
fraction of the job allocated to Resource i
1 if Resource i is chosen 0 otherwise
COMP9334, Chun Tung Chou, 2021
Page 16
Formulating optimization problem (cont.)
Cost:
n c i N x i C = p + siyi
i=1 i
Constraint: Cannot have cycles from Resource i if it is not chosen
xi ≤ yi, i = 1,2,…,n
Note that we require xi ≥ 0, thus
Exercise: If yi = 0, what value(s) can xi take? Exercise: If yi = 1, what value(s) can xi take?
COMP9334, Chun Tung Chou, 2021 Page 17
Formulating optimization problem (cont.)
The problem formulation is
subject to
min T
T ≥ Nxi, i=1,2,…,n
pi T ≤ Tmax
n c i N x i p+siyi
≤Cmax
i=1 i
xi = 1
xi ≥ 0,
yi ∈ {0,1}, i=1,2,…,n
n i=1
xi ≤ yi,
i = 1,2,…,n
i = 1,2,…,n
COMP9334, Chun Tung Chou, 2021
Page 18
Integer programming
LP in which some or all decision variables can only take non- negative integer values
Specific type of integer programming (IP):
Mixed integer programming (MIP): Some decision variables are integers, others are real
Pure integer programming: All decision variables are integers Binary integer programming: All decision variables must be either 0 or 1
COMP9334, Chun Tung Chou, 2021 Page 19
LP relaxation
An simple minded (but incorrect) way to solve IP is to:
Relax the integer constraints (= ignore the integer constraints) Solve the resulting LP problem
Round the optimal solution to the LP problem to get an integer solution
IP problem (IP1)
min x1 + x2 subject to 2×1 + x2 ≥ 4 x1 + 4×2 ≥ 6
x1, x2 ≥ 0, integer
LP relaxation of (IP1)
min x1 + x2 subject to 2×1 + x2 ≥ 4 x1 + 4×2 ≥ 6
x1,x2 ≥0
COMP9334, Chun Tung Chou, 2021 Page 20
Feasible solutions
x2 Optimal solution (1,2) or (2,1) Optimal value = 3
x2
6 5 4 3
= Feasible solution 6
Feasible solutions
5
4 3
2*2
(1.43,1.14) Objective = 2.57
*
1
0123456 0123456
(IP1) LP relaxation of (IP1)
1
x1
x1
Question: Can we round the LP relaxation solution to obtain a solution to (IP1)?
COMP9334, Chun Tung Chou, 2021 Page 21
Results and observations
Rounding the LP relaxation solution may produce an infeasible solution for the original IP problem
However, for minimization problems, it is always true that:
Optimal value of an IP problem ≥ Optimal value of its LP relaxation
If the LP relaxation gives an integer solution
The optimal solution to the LP relaxation is also an optimal solution to the original problem
This is true for some special classes of IP problems e.g. network flow problems
COMP9334, Chun Tung Chou, 2021 Page 22
Solving IP exactly
Complete enumeration will require a lot of computation
A smarter way is to use the branch-and-bound or branch-and-cut methods
Ref: Winston sections 9.3, 9.4
In principle, these methods can find the optimal solution but practically it may take a very long time
Some IP problems with 60 variables may take hours to run
COMP9334, Chun Tung Chou, 2021 Page 23
AMPL/CPLEX for solving example 2
This is saved in the file grid_mip.mod
set COMP; #Set of resources
param c {COMP}; #Cost
param p {COMP}; #Speed
param s {COMP}; #Set up cost
param Tmax;
param Cmax;
param N;
var x {i in COMP} >= 0;
var y {i in COMP} binary;
var T >= 0;
minimize time: T;
subject to T_constraint {i in COMP}: T >= N * x[i] / p[i];
subject to Tmax_constraint: T <= Tmax;
subject to Cmax_constraint: sum {i in COMP}
(N * c[i] * x[i] / p[i] + s[i] * y[i]) <= Cmax;
subject to x_sum: sum {i in COMP} x[i] = 1;
subject to restriction {i in COMP}: x[i] <= y[i];
COMP9334, Chun Tung Chou, 2021
Page 24
AMPL/CPLEX for solving example 2 (cont.)
Results from the solver
CPLEX 12.6.0.0: optimal integer solution; objective 3333.33333
5 MIP simplex iterations
0 branch-and-bound nodes
x [*] :=
COMP_1 0.333333
COMP_2 0.666667
COMP_3 0
;
y [*] :=
COMP_1 1
COMP_2 1
COMP_3 0
;
T = 3333.33
sum{i in COMP} (N*c[i]*x[i]/p[i] + s[i]*y[i]) = 1466.67
COMP9334, Chun Tung Chou, 2021
Page 25
Question
Cost:
n c i N x i C = p + siyi
i=1 i
Constraint: Cannot have cycles from Resource i if it is not chosen
xi ≤ yi, i = 1,2,...,n
This means:
yi =0⇒xi =0
yi =1⇒1≥xi ≥0
Question: The constraint allows yi = 1 and xi = 0, which means you pay set-up cost but do not buy any cycle. Fortunately, this won’t happen. Why?
COMP9334, Chun Tung Chou, 2021 Page 26
Summary
Use binary variables to make yes/no decision
Constraint to enforce consistency. E.g., if a provider is not chosen, will not buy cycles from the provider
Integer programming
COMP9334, Chun Tung Chou, 2021 Page 27
Acknowledgment
Grid computing example based on Menasce ́ and Casalicchio, “QoS in computing”, IEEE Internet Computing, pp. 85–87, Jul./Aug. 2004.
COMP9334, Chun Tung Chou, 2021 Page 28