Integer Program Combination Optimization - Modeling with Integer Variables

1 Structure of Class Formulations and relaxations, Lec. 1-8 Slide 1 Algebra and geometry of IO, Lec. 9-14 Algorithms for IO, Lec. 15-22 Extensions of IO, Lectures 23-25 2 Requirements Slide 2 Homeworks: 30% Midterm Exam: 30% Final Exam: 30% Contributions to class: (Class participation, comments on book): 10% Use of CPLEX for solving IO problems 3 Todays Lecture Slide 3 Modeling with integer variables What is a good formulation? Theme: The Power of Formulations 4 Integer Optimization 4.1 Mixed IO (MIO) max s.t. c x+hy Ax + nBy
b x 2 Z+n (x  0 x integer) y 2 R+(y  0) 0 0 1 Slide 4 4.2 Pure IO (IO) max c x s.t. Ax
b x 2 Z+n Important special case: Binary Optimization (BO) max c x s.t. Ax
b x 2 f0 1gn 0 Slide 5 0 4.3 LO (LO) max c x s.t. By
b y 2 Rn+ 0 Slide 6 5 Modeling with Binary Variables 5.1 Binary Choice occurs x 2 10 if event otherwise Example 1: IO formulation of the knapsack problem n : projects, total budget b aj : cost of project j cj : value of project j j is selected. xj = 01 if project otherwise. n P cj xj max j �1 P s.t. aj xj
b xj 2 f0 1g 5.2 Modeling relations At most one event occurs X j Slide 8 Slide 9 xj
1 Neither or both events occur x2 ; x1 = 0 2 Slide 7 If one event occurs then, another occurs 0
x2
x1 If x = 0, then y = 0 if x = 1, then y is uncontrained 0
y
Ux x 2 f0 1g 5.3 The assignment problem Slide 10 n people m jobs cij : cost of assigning person j to job i: xij = 10 person j is assigned to job i Pc x min ij ij n P s.t. xij = 1 each job is assigned j�1 m P xij 1 each person can do at most one job. i�1 xij 2 f0
1g 6 What is a good formulation? 6.1 Facility Location Slide 11 Data N = f1 : : :ng potential facility locations I = f1 : : :mg set of clients cj : cost of facility placed at j hij : cost of satisfying client i from facility j: Decision variables placed at location j xij = 01 a facility isotherwise yij = fraction of demand of client i satised by facility j: IZ1 = min s.t. n P j �1 n P cj xj + i�1 j �1 yij = 1 j �1 yij
xj xj 2 f0 1g 3 m P n P hij yij 0
yij
1: Slide 12 Slide 13 Consider an alternative formulation. n m P n P P IZ2 = min cj xj + hij yij j �1 i�1 j �1 n P s.t. yij = 1 j �1 m P yij
m  xj i�1 xj 2 f0 1g 0
yij
1: Are both valid? Which one is preferable? 6.2 Observations IZ1 = IZ2 , since the integer points both formulations dene are the same. P1 = f(x y) : n X xj
1 yij = 1 yij
xj 00

yij
1 j �1 P2 = f(x y) : n X j �1 yij = 1 0
xj
1 0
yij
1 Let Z1 = min cx + hy (x y) 2 P1 Z2
Z1
IZ1 = IZ2 m X i�1 Slide 14
yij
m  xj
Slide 15 Z2 = min cx + hy (x y) 2 P2 6.3 Implications Finding IZ1 (= IZ2 ) is dicult. Solving to nd Z1 Z2 is a LOP. Since Z1 is closer to IZ1 several methods (branch and bound) would work better (actually much better). Suppose that if we solve min cx + hy (x y) 2 P1 we nd an integral solution. Have we solved the facility location problem? Formulation 1 is better than Formulation 2. (Despite the fact that 1 has a larger number of constraints than 2.) What is then the criterion? 4 Slide 16 Slide 17 6.4 Ideal Formulations Let P be a linear relaxation for a problem Let H = f(x y) : x 2 f0 1gng \ P Slide 18 Consider Convex Hull (H) X X = fx : x = i xi i = 1 i  0 xi 2 H g i i Slide 19 The extreme points of CH (H) have f0 1g coordinates. So, if we know CH (H) explicitly, then by solving min cx + hy (x y) 2 CH (H) we solve the problem. Message: Quality of formulation is judged by closeness to CH (H). C H (H)  P1  P2 7 Minimum Spanning Tree (MST) How do telephone companies bill you? It used to be that rate/minute: Boston ! LA proportional to distance in MST Other applications: Telecommunications, Transportation (good lower bound for TSP) Given a graph G = (V E ) undirected and Costs ce e 2 E. Find a tree of minimum cost spanning all the nodes. 1 if edge e is included in the tree Decision variables xe = 0 otherwise The tree should be connected. How can you model this requirement? Let S be a set of vertices. Then S and V n S should be connected
i 2S Let (S) = fe = (i j) 2 E : j 2 V n S 5 Slide 20 Slide 21 Slide 22 Then, X e2 (S ) xe  1 What is the number of edges in a tree? P Then, xe = n ; 1 e2E 7.1 Formulation P IZM ST = min cexe 8 ePE x  1 > < eP(S ) e H > xe = n ; 1 : xe E2 f0 1g: e Is this a good formulation? 2 2 Slide 23 8SV S= 6 V 2 Slide 24 Pcut = fx 2 R E : 0
x
e X xe = n ; 1 e E X xe  1 8 S  V S = 6 Vg j j 2 Is Pcut the CH (H)? e2 (S ) 7.2 What is CH (H )? Let X Slide 25 Psub = fx 2 R E : xe = n ; 1 e E X xe
jS j ; 1 8 S  V S = 6 Vg j j 2 e2E (S )
i 2S E(S) = e = (i j) : j 2 S Why is this a valid IO formulation? Slide 26 Theorem: Psub = CH (H). ) Psub is the best possible formulation. MESSAGE: Good formulations can have an exponential number of constraints. 6 8 The Traveling Salesman Problem Given G = (V E ) an undirected graph. V = f1 : : : ng, costs ce 8 e 2 E. Find a tour that minimizes total length. 8.1 Formulation I xe = 1 if edge e is included in the tour. 0 otherwise. P min ce xe eP E s:t: xe  2 S  E e P(S ) xe = 2 i 2 V e (i) xe 2 f0 1g Slide 27 Slide 28 2 2 2 8.2 Formulation II min s:t: TSP = Pcut TSP = Psub TSP Pcut P Pce xex
jS j ; 1 S  E e eP E (S ) x =2 i2V Slide 29 2 e e2 (i) xe 2 f0 1g P x 2 P x =2 fx 2 RjE j e e e2 (S ) e2 (i) 0
xe
1g P xe = 2 fx 2 RjE j P x
ej2S j(i;) 1 e e2 (S ) 0
xe
1g TSP 6 = Psub Theorem: CH (H) Nobody knows CH (H) for the TSP 9 Minimum Matching Given G = (V E ) ce costs on e 2 E. Find a matching of minimum cost. Formulation: P min Pce xe s:t: xe = 1 i 2 V e (i) xe 2 f0 1g 2 7 Slide 30 Slide 31 Slide 32 Is the linear relaxation C H (H)? Let P PM AT = fx 2 R E : xe = 1 e (i) P xe  1 jS j = 2k + 1 S 6= e (S ) xe  0g Theorem: PM AT = C H (H) j Slide 33 j 2 2 10 Observations For MST, Matching there are ecient algorithms. C H (H) is known. For TSP 6 9 ecient algorithm. TSP is an N P ; hard problem. C H (H) is not known. Conjuecture: The convex hull of problems that are polynomially solvable are explicitly known. 11 Summary 1. An IO formulation is better than another one if the polyhedra of their linear relaxations are closer to the convex hull of the IO. 2. A good formulation may have an exponential number of constraints. 3. Conjecture: Formulations characterize the complexity of problems. If a problem is solvable in polynomial time, then the convex hull of solutions is known. 8 Slide 34 Slide 35