1 Todays Lecture Slide 1 Modeling with integer variables What is a good formulation? Theme: The Power of Formulations 2 Integer Optimization 2.1 Mixed IO (MIO) max c x + h y s.t. Ax + B y b x 2 Z+mn (x 0 x integer) y 2 R+ (y 0) 0 0 2.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 2 Slide 3 0 2.3 LO (LO) max c x s.t. By b y 2 Rn+ 0 Slide 4 3 Modeling with Binary Variables 3.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. 1 Slide 5 Slide 6 n P max cj xj j �1 P s.t. aj xj b xj 2 f0 1g 3.2 Modeling relations At most one event occurs X j Slide 7 xj 1 Neither or both events occur x2 ; x1 = 0 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 3.3 The assignment problem n people m jobs Slide 8 cij : cost of assigning person j to job i: xij = 10 person j is assigned to job i Pc x min ij ij Pn x = 1 each job is assigned s.t. ij j�1 m P xij 1 each person can do at most one job. i�1 xij 2 f0 1g 4 What is a good formulation? 4.1 Facility Location Data Slide 9 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: 2 Decision variables placed at location j xj = 10 a facility isotherwise yij = fraction of demand of client i satis ed by facility j: Slide 10 n m P n P P IZ1 = min cj xj + hij yij j �1 i�1 j �1 n P s.t. yij = 1 j �1 yij xj xj 2 f0 1g 0 yij 1: Consider an alternative formulation. n m P n P P h y IZ = min cx + 2 s.t. j �1 n P j �1 m P j j yij = 1 i�1 j �1 Slide 11 ij ij yij m xj i�1 xj 2 f0 1g 0 yij 1: Are both valid? Which one is preferable? 4.2 Observations IZ1 = IZ2 , since the integer points both formulations de ne are the same. n X xj 1 P1 = f(x y) : 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 yij m xj Z2 = min cx + hy (x y) 2 P2 3 Slide 12 Slide 13 4.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? Slide 14 Slide 15 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.4 Ideal Formulations Let P be a linear relaxation for a problem Let H = f(x y) : x 2 f0 1gng \ P Slide 16 Consider Convex Hull (H) X X = fx : x = i xi i = 1 i 0 xi 2 H g i i Slide 17 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 5 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) 4 Slide 18 Slide 19 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 Slide 20 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 Let (S) = fe = (i j) 2 E : ij 22 SV n S Then, X xe 1 e2 (S ) What is the number of edges in a tree? P Then, xe = n ; 1 e2E 5.1 Formulation P IZM ST = min cexe 8 ePE x 1 > < eP(S ) e H > x = n;1 >eE e : xe 2 f0 1g: Is this a good formulation? 2 2 Slide 21 8SV S= 6 V 2 Pcut = fx 2 R E : 0 x e X xe = n ; 1 e E X 6 Vg xe 1 8 S V S = j 2 Is Pcut the CH (H)? e2 (S ) 5 j Slide 22 5.2 What is C H (H )? Let X Slide 23 Psub = fx 2 R E : xe = n ; 1 e E X xe jS j ; 1 8 S V S 6= V g j j 2 e2E (S ) i 2S E(S) = e = (i j) : j 2 S Why is this a valid IO formulation? Slide 24 Theorem: Psub = CH (H). ) Psub is the best possible formulation. MESSAGE: Good formulations can have an exponential number of constraints. 6 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. 6.1 Formulation I xe = 1 if edge e is included in the tour. 0 otherwise. Pcx min e e eP E s:t: xe 2 S E e P(S ) xe = 2 i 2 V e (i) xe 2 f0 1g Slide 25 Slide 26 2 2 2 6.2 Formulation II min s:t: Pc x Pe ex jS j ; 1 S E e eP E (S ) x =2 i2V Slide 27 2 e e2 (i) xe 2 f0 1g 6 Slide 28 TS P = Pcut TS P = Psub fx 2 RjE j P e2 (S ) xe 2 0 xe 1g P fx 2 R E xe = 2 P x ejS j(i;) 1 e e (S ) 0 xe 1g j P e2 (i) xe = 2 j 2 2 TS P Pcut Slide 29 TSP 6 = Psub Theorem: CH (H) Nobody knows CH (H) for the TSP 7 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 Slide 30 2 Is the linear relaxation CH (H)? Let P x =1 PM AT = fx 2 R E : e e (i) P 6 xe 1 jS j = 2k + 1 S = e (S ) xe 0g Theorem: PM AT = CH (H) j Slide 31 j 2 2 8 Observations For MST, Matching there are ecient algorithms. CH (H) is known. For TSP 6 9 ecient algorithm. TSP is an NP ; hard problem. CH (H) is not known. Conjuecture: The convex hull of problems that are polynomially solvable are explicitly known. 7 Slide 32 9 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 33