15.083 Lecture 1: Formulations

6.859J/15.083J Integer Programming and Combinatorial Optimization 1 Structure of Class Formulations, complexity and relaxations, Lec. 1-9 Robust Discrete Optimization, Lec. 10-11 Algebra and geometry of IO, Lec. 12-15 Algorithms for IO, Lec. 16-23 Mixed Integer Optimization, Lec. 24-25 2 Requirements Homeworks: 30% Midterm Exam: 30% Final Exam: 40% Contributions to class: An important tie breaker Use of CPLEX for solving IO problems 3 Todays Lecture 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+ (x  0 x integer) y 2 Rm+ (y  0) 0 0 1 4.2 Pure IO (IO) max s.t. cx Ax  b x 2 Z+n 0 Important special case: Binary Optimization (BO) max c x s.t. Ax  b x 2 f0 1gn 0 4.3 LO (LO) max s.t. cx By  b y 2 Rn+ 0 5 Modeling with Binary Variables 5.1 Binary Choice if event occurs x 2 1 0 otherwise Example 1: IO formulation of the knapsack problem n : projects, total budget b aj : cost of project j cj : value of project j if project j is selected. xj = 1 0 otherwise. n P max cj xj jP �1 s.t. aj xj  b xj 2 f0 1g 5.2 Modeling relations At most one event occurs X j 9 xj  1 Neither or both events occur x2 ; x1 = 0 2 8 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 0 n people m jobs cij : cost of assigning person j to job i: xij = 10 person j is assigned to job i P min cij xij 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 5.4 Multiple optimal solutions Generate all optimal solutions to a BOP. max c x s.t. Ax  b x 2 f0 1gn 0 Generate third best? Extensions to MIO? 5.5 Modeling nonconvex objective functions How to model min c(x), where c(x) is piecewise linear but not convex? 6 What is a good formulation? 6.1 Facility Location 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: 3 Decision variables a facility is placed at location j xj = 1 0 otherwise yij = fraction of demand of client i satised by facility j: n m P n P P 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 IZ = min cx + h y IZ1 = min 2 s.t. j �1 n P j �1 m P j j yij = 1 i�1 j �1 ij ij 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. 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 4 m X i�1  yij  m  xj   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? 8 9 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? 6.4 Ideal Formulations Let P be a linear relaxation for a problem Let H = f(x y) : x 2 f0 1gng \ P Consider Convex Hull (H) X X = fx : x = i xi i = 1 i  0 xi 2 H g i i 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). CH (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) 5 0 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  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 7.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 8 S  V  S 6= 2 Pcut = fx 2 R E : 0  x  e X xe = n ; 1 e E X xe  1 8 S  V  S 6=  V g j 2 Is Pcut the CH (H)? e2(S ) 6 j V 7.2 What is C H (H)? Let X 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? 8 Theorem: Psub = CH (H). ) Psub is the best possible formulation. MESSAGE: Good formulations can have an exponential number of con straints. 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 eP (S ) xe = 2 i 2 V e (i) xe 2 f0 1g 2 2 2 8.2 Formulation II min s:t: Pc x Pe ex  jS j ; 1 S  E e eP E (S ) x = 2 i 2 V 2 e e2(i) xe 2 f0 1g 7 9 0 TSP = Pcut TSP = Psub fx 2 RjE j P e2(S ) xe  2 0  xe  1g P fx 2 R E  xe = 2 e (i) P xe  jS j ; 1 e (S ) 0  xe  1g j P e2(i) xe = 2 j 2 2 TS P = P TSP 6 CH (H) Theorem: Pcut sub 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 Is the linear relaxation CH (H)? Let P x =1 PM AT = fx 2 R E : e e (i) P xe  1 jS j = 2k + 1 S = 6 e (S ) xe  0g Theorem: PM AT = CH (H) j j 2 2 10 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. 8 11 Summary 1. Modeling with binary variables allows a lot of modelling power. 2. An IO formulation is better than another one if the polyhedra of their linear relaxations are closer to the convex hull of the IO. 3. A good formulation may have an exponential number of constraints. 4. Conjecture: Formulations characterize the complexity of problems. If a problem is solvable in polynomial time, then the convex hull of solutions is known. 9