COMP9334: Capacity Planning of Computer Systems and Networks
Optimisation (5):
Power of binary variables
Integer Programming – What have you seen?
A recurrent theme is to use integer programming to make binary decisions
Examples of binary decisions
Week 9A: Grid computing problem
Choose a particular grid computing company or not
Week 9B: Routing of flows
Should the flow be routed on a link or not?
Week 10A: Placement problem Should a location be chosen or not?
Page 1
This week’s lecture: Power of binary variables
Not only for making yes-or-no type of decisions, binary variables can be used to capture many other requirements
Restricted range of values Either-or constraints If-then constraints Piecewise linear functions
Page 2
Restricted range of values
Some variables can only take certain values
E.g. network links can only be of capacity 155 Mbps, 466 Mbps, 622 Mbps, etc
If decision variable x can only take values from {a1,a2,…,am}, this can be modeled by using an additional set of binary decision
variables
1 ifai isused 0 otherwise
yi =
Page 3
Restricted range of values
Then, the above requirement can be captured by
m
x = aiyi
yi ∈ {0,1} E.g. if a1 = 155,a2 = 466,a3 = 622, we have
y1=1 ⇒ y2=y3=0 ⇒ x=155 y2=1 ⇒ y1=y3=0 ⇒ x=466 y3=1 ⇒ y1=y2=0 ⇒ x=622
i=1 yi = 1
m i=1
Page 4
Either-or constraints
A Cloud computing service provider offers 3 different packages with different speed and cost for each package. You can buy any cycles from any package but the deal requires that
# cycles from Package 1 + # cycles from Package 2 ≥ 10000, or, # cycles from Package 2 + # cycles from Package 3 ≥ 50000
At least one of these two inequalities must hold, but not necessarily both
Let wi = number of cycles to be bought from Package i
Page 5
Either-or constraints (cont.)
The above requirement can be captured by using an additional binary decision variable p
w1 + w2 ≥ 10000p
w2 +w3 ≥ 50000(1−p)
p ∈ {0,1}
wi ≥ 0, i=1,2,3
Case1: p=0,wehave
w1 + w2 ≥ 0 ← Trivially satisfied w2+w3 ≥ 50000
wi ≥0,i=1,2,3
Case2: p=1,wehave
w1+w2 ≥ 10000
w2 + w3 ≥ 0 ← Trivially satisfied
wi ≥0,i=1,2,3
Page 6
Either-or constraints (cont.)
In general, if one of the following two constraints must be satisfied
n
a1,ixi ≥ b1
i=1 n
a2,ixi ≥ b2 i=1
where aj,i are given parameters, xi(≥ 0) are decision variables, bj’s are constants, then the either-or constraints can be modelled
by
n
a1,ixi ≥ b1p
i=1 n
a2,ixi ≥ b2(1 − p) i=1
p ∈ {0,1}
Page 7
If-then constraints
We may want to impose if-then constraints, e.g. if x1 + x2 > 1, then y ≥ 4
where x1, x2 are binary variables, and 0 ≤ y ≤ 10
The above if-then constraint can be captured by using an additional
binary decision variable p
x1+x2−1 ≤ 1−p −y+4 ≤ 4p
p ∈ {0,1}
Page 8
If-then constraints (cont.)
To understand how this works, consider the two cases:
Case1:Ifx1+x2 >1holds
Sincex1 +x2 >1,x1 +x2 −1>0
Since p can only be 1 or 0, the inequality constraint x1+x2−1 ≤ 1 − p forces p to be 0
Since p = 0, from the inequality constraint −y + 4 ≤ 4p, we have y ≥ 4 which is the condition that we want to impose when x1 +x2 >1holds
Case2:Ifx1+x2 >1doesnothold
Inthiscase,sincex1 +x2 −1≤0,pcanbeeither0or1
If p = 0, the inequality constraint −y + 4 ≤ 4p becomes y ≥ 4 If p = 1, the inequality constraint −y + 4 ≤ 4p becomes y ≥ 0 Thus, p can be chosen such that there is no restriction on the value of y
Page 9
If-then constraints (cont.)
In general, the if-then constraint
if f(x1,x2,…,xn) > 0, then g(x1,x2,…,xn) ≥ 0
can be modeled by
f(x1,x2,…,xn) ≤ M1(1−p) −g(x1,x2,…,xn) ≤ M2 p
where p is a binary variable, M1 and M2 are constants chosen large enough such that f(x1,x2,…,xn) ≤ M1 and −g(x1,x2,…,xn) ≤ M2 hold for all possible choices of x1, x2, . . . , xn
Page 10
Piecewise linear functions
We can use binary variables to model piecewise linear functions
Example: A Cloud computing service provider may use a progressive charging scheme
5 dollars/sec for the first 5,000 sec 2 dollars/sec for the next 15,000 sec 1 dollar/sec thereafter
Page 11
Piecewise linear functions (cont.)
Cost c ($)
55000
c = 55000 + (t−20000)
c = 25000 + 2(t−5000)
Decision variables
1 if segment i is used yi = 0 otherwise
25000
0
c = 5t 5000
Time t (s)
20000
Segment1: 0≤t≤5000,cost=5t
Segment 2: 5000 ≤ t ≤ 20000, cost = 2t + 15000 Segment 3: 20000 ≤ t, cost = t + 35000
Page 12
Piecewise linear functions (cont.)
We have
y1 =1⇒0≤t≤5000andcost=5t
y2 =1⇒5000≤t≤20000andcost=2t+15000 y3 =1⇒20000≤tandcost=t+35000
y1 + y2 + y3 = 1
We can rewrite these as
0 ≤ ty1 ≤ 5000y1
5000y2 ≤ ty2 ≤ 20000y2
20000y3 ≤ ty3
cost = y1(5t) + y2(2t + 15000) + y3(t + 35000) y1 + y2 + y3 = 1
Problem: non-linear constraints
Page 13
Piecewise linear functions (cont.)
Define ti = tyi for i = 1, 2, 3
cost = 5t1 + 2t2 + 15000y2 + t3 + 35000y3 0 ≤ t1 ≤ 5000y1
5000y2 ≤ t2 ≤ 20000y2
20000y3 ≤ t3 ≤ My3
y1 + y2 + y3 = 1 t = t1 + t2 + t3
Note
ti is non-zero if the corresponding yi = 1 M is a sufficiently large number to enforce
y3 =0⇒t3 =0 and t3 ≥20000⇒y3 =1 This is a non-standard expression
Page 14
Piecewise linear functions (Alternative)
Decision variables
1 if segment i is used yi = 0 otherwise
Segment 1: z1, z2 ≥ 0, z1 + z2 = 1, b = z1b1 + z2b2, f = z1f (b1) + z2f (b2) Segment 2: z2, z3 ≥ 0, z2 + z3 = 1, b = z2b2 + z3b3, f = z2f (b2) + z3f (b3) Segment 3: z3, z4 ≥ 0, z3 + z4 = 1, b = z3b3 + z4b4, f = z3f (b3) + z4f (b4)
Page 15
Piecewise linear functions (Alternative)
Decision variables
Segments:
1 if segment i is used yi = 0 otherwise
Segment 1: z1, z2 ≥ 0, z1 + z2 = 1, b = z1b1 + z2b2, f = z1f (b1) + z2f (b2) Segment 2: z2, z3 ≥ 0, z2 + z3 = 1, b = z2b2 + z3b3, f = z2f (b2) + z3f (b3) Segment 3: z3, z4 ≥ 0, z3 + z4 = 1, b = z3b3 + z4b4, f = z3f (b3) + z4f (b4)
z1 ≤y1,z2 ≤y1 +y2,z3 ≤y2 +y3,z4 ≤y3 y1 + y2 + y3 = 1
z1 +z2 +z3 +z4 =1
b=z1b1 +z2b2 +z3b3 +z4b4
f = z1f(b1) + z2f(b2) + z3f(b3) + z4f(b4) z1,z2,z3,z4 ≥ 0, y1,y2,y3 ∈ {0,1}
Formulation:
Reference: Winston, Chapter 9
Page 16
Linear objective and constraints(1)
All integer programming solvers assume the objective and constraints are linear in the decision variables
A nonlinear objective can be approximated by piecewise linear functions
Page 17
Linear objective and constraints(2)
Nonlinear constraints can be replaced by linear constraints. Example: Given that y1, y2 ∈ {0, 1}, we have
y1(1−y2)≥1canbereplacedbyy1 −y2 >0ory1 −y2 ≥1
Key point: Make the objective and constraints linear
Page 18
This lecture: Summary
Using binary integer variables to
Select an option out of many Either-or requirement
If-then condition
Piecewise linear function
Linear objectives and constraints
Page 19
Integer programming and optimisation: Summary
What you have learnt
How to formulate integer programming problems
How to solve them using AMPL
Examples of using integer programming for network design and analysis, placement problems
There are a lot more to learn but this will give you a starting point …
Page 20
References
Advanced formulation of integer programming problems Winston, “Operations Research”, Section 9.2
Page 21