15.081J/6.251J Introduction to Mathematical Programming Lecture 24: Discrete Optimization� 1 Outline Slide 1 • Modeling with integer variables • What is a good formulation? • Theme: The Power of Formulations 2 Integer Programming 2.1 Mixed IP Slide 2 (MIP) max c ′ x + h ′ y s.t. Ax + By ≤ b nR+n∈ Zx+(x ≥ 0, x integer) y ∈ (y ≥ 0) nZ+ 2.2 Pure IP Slide 3 ′ (IP) max c x s.t. Ax ≤ b x ∈ Important special case: Binary IP ′ (BIP) max c x s.t. Ax ≤ b x ∈ {0, 1}n 2.3 LP Slide 4 ′ (LP) max c x s.t. By ≤ b y ∈ Rn + 3 Modeling with Binary Variables 3.1 Binary Choice � Slide 5 1, if event occurs x ∈ 0, otherwise Example 1: IP formulation o f the knapsack problem n : projects, total budget b aj : cost of project j cj : value of project j Slide 6 1, if project j is selected. xj = 0, otherwise. 1� � � � � � � n max cjxj j=1 s.t. ajxj ≤ b xj ∈ {0, 1} 3.2 Modeling relations Slide 7 • At most one event occurs xj ≤ 1 j • Neither or both events oc c ur 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 ≤ U x, x ∈ {0, 1} 3.3 The assignment problem Slide 8 n people m jobs cij : cost of assigning person j to job i. 1 person jis assigned to job i xij = 0 min cij xij n s.t. xij = 1 each job is assigned j=1 m xij ≤ 1 each person can do at most one job. i=1 xij ∈ {0, 1} 3.4 Multiple optimal solutions Slide 9 • Generate all optimal solutions to a BOP. ′ max c x s.t. Ax ≤ b x ∈ {0, 1}n • Generate third best? • Extensions to MIO? 2� � � � � � � � � � 3.5 Nonconvex functions • How to model min c(x), where c(x) is piecewise linear but not c onvex? 4 What is a good formulation? 4.1 Facility Location • Data N = {1 . . . n} potential facility locations I = {1 . . . m} set of clients cj : cost of facility placed at j hij : cost of satisfying client i from facility j. • Decision variables 1, a facility is placed at location j xij =0, otherwise yij = fraction of demand of client i satisfied by facility j. n m n IZ1 = min cjxj + hijyij j=1 i=1 j=1 n s.t. yij = 1 j=1 yij ≤ xj xj ∈ {0, 1}, 0 ≤ yij ≤ 1. Consider an alternative formulation. n m n IZ2 = min cjxj + hijyij j=1 i=1 j=1 n s.t. yij = 1 j=1 m yij ≤ m · xj i=1 xj ∈ {0, 1}, 0 ≤ yij ≤ 1. Are both valid? Which one is preferable? 4.2 Observations • IZ1 = IZ2, since the integer points both formulations define are the same. • n � � 0 ≤ xj ≤ 1 P1 = {(x, y) : yij = 1, yij ≤ xj, 0 ≤ yij ≤ 1 j=1 3 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14� � � � � n P2 = {(x, y) : yij = 1, j=1 0 ≤ xj ≤ 1 m yij ≤ m · xj, i=1 0 ≤ yij ≤ 1 Slide 15 • Let Z1 = min cx + hy, Z2 = min cx + hy (x, y) ∈ P1 (x, y) ∈ P2 • Z2 ≤ Z1 ≤ IZ1 = IZ2 4.3 Implications Slide 16 • Finding IZ1(= IZ2) is difficult. • Solving to find Z1, Z2 is an LP. Since Z1 is closer to IZ1 several methods (branch and bound) would work better (actually much better). • Suppo se that if we solve min cx + hy, (x, y) ∈ P1 we find an integral solution. Have we solved the facility location problem? Slide 17 • 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 Slide 18 • Let P be an LP relaxation for a problem • Let H = {(x, y) : x ∈ {0, 1}n} ∩ P • Consider Convex Hull (H) = {x : x = λix i , λi = 1, λi ≥ 0, x i ∈ H} i i Slide 19 • The extreme points of CH(H) have {0, 1} coordinates. • So, if we know CH(H) explicitly, then by solving min cx + hy, (x, y) ∈ CH(H) we solve the problem. • Message: Quality of formulation is judged by closeness to CH(H). CH(H) ⊆ P1 ⊆ P2 4� � � � � � � 5 Minimum Spanning Tree (MST) Slide 20 • How do telephone companies bill you? • It used to be that rate/minute: Boston → LA pr oportional to distance in MST • Other applications: Telecommunications, Transporta tion (good lower bound for TSP) Slide 21 • Given a graph G = (V, E) undirected and Costs ce, e ∈ 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 22 • The tree should be connected. How can you model this requirement? • Let S be a set of vertices. Then S and V \ S should be connected i ∈ S • Let δ(S) = {e = (i , j) ∈ E : j ∈ V \ S • Then, xe ≥ 1 e∈δ(S) • What is the number of edges in a tree? • Then, xe = n − 1 e∈E 5.1 Formulation Slide 23 IZMST = min cexe     H    Is this a good formulation? e∈E � xe ≥ 1 ∀ S ⊆ V, S �= ∅, V e∈δ(S) � xe = n − 1 e∈E xe ∈ {0, 1}. Slide 24 Pcut = {x ∈ R|E| : 0 ≤ x ≤ e, xe = n − 1 e∈E xe ≥ 1 ∀ S ⊆ V, S �= ∅, V } e∈δ(S) Is Pcut the CH(H)? 5� � � � � � � � � � 5.2 What is CH (H )? Slide 25 Let Psub = {x ∈ R|E| : xe = n − 1 e∈E xe ≤ |S| − 1 ∀ S ⊆ V, S � ∅, V }= e∈E(S) i ∈ S E(S) = e = (i, j) : j ∈ S Why is this a valid IP formulation? Slide 26 • Theorem: Psub = CH(H). • ⇒ Psub is the best possible formulation. • MESSAGE: Good formulations can have an expo nential number of con- straints. 6 The Traveling Salesman Problem Slide 27 Given G = (V, E) an …