Integer Program Combination Optimization - Duality II and Efficient Algorithms

University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

169

Pages:

6
Author:

Branden Miles

1 Outline Slide 1 Solution of Lagrangean dual Geometry and strength of the Lagrangean dual E cient algorithms and computational complexity 2 The TSP X e2 (fig) xe = 2 i2V X xe jS j ; 1 e2E(S) xe 2 f0 1g: min s:t: X e2E Slide 2 SV S= 6 V ce xe X e2 (fig) X e2 (f1g) X e2E(S) xe = 2 i 2 V n f1g xe = 2 xe jS j ; 1 S V n f1g S = 6 V n f1g X xe = jV j ; 2 e2E(V nf1g) xe 2 f0 1g: P Dualize e2 (fig) xe = 2 i 2 V n f1g: What is the relation of ZD and ZLP ? 3 Solution ; Z ( ) = mink2K c0 xk + 0 (b;Axk ) xk k 2 K are extreme points of conv(X ). f k = b ; Axk and hk = c0xk . ; Z ( ) = mink2K hk + f 0k piecewise linear and concave. Recall t+1 = t + t rZ ( t ) 3.1 Subgradients Prop: f : Z , then t Z Zt Let t t + 1 and go to Step 2. 5 Ecient algorithms The LO problem Slide 13 min c x s:t: Ax = b 0 x0 A LO instance min 2x + 3y s:t: x + y x 4 y 1 0 f ZP conv(Y ) =1 duality gap ZD = ; 13 g A problem is a collection of instances 5.1 Size The size of an instance is the number of bits used to describe the instance, according to a prespecied format A number r U Slide 14 r = ak 2k + ak;1 2k;1 + + a1 21 + a0 is represented by (a0 a1 : : : ak ) with k blog2 U c Size of r is blog2 U c + 2 Instance of LO: (c A b) Size is ; (mn + m + n) blog 2 U c + 2 5.2 Running Time Let A be an algorithm which solves the optimization problem . If there exists a constant > 0 such that A terminates its computation after at most f (I ) elementary steps for each instance I , then A runs in O(f ) time. Elementary operations are � variable assignments � random access to variables � conditional jumps � � A \brute force" algorithm for solving the min-cost ow problem: 5 � Slide 15 comparison of numbers arithmetic operations . .. Slide 16 Consider all spanning trees and pick the best tree solution among the feasible ones. Suppose we had a computer to check 1015 trees in a second. It would need more than 109 years to nd the best tree for a 25-node min-cost ow problem. It would need 1059 years for a 50-node instance. That's not e cient! Ideally, we would like to call an algorithm \ecient" when it is suciently fast to be usable in practice, but this is a rather vague and slippery notion. Slide 17 The following notion has gained wide acceptance: An algorithm is considered ecient if the number of steps it performs for any input is bounded by a polynomial function of the input size. Polynomials are, e.g., n, n3 , or 106 n8 . 5.3 The Tyranny of Exponential Growth 100 n log n 10 n2 n3:5 2n n! nn;2 9 9 10 /sec 1:19 10 600 000 3 868 41 15 13 1010 /sec 1:08 1010 1 897 370 7 468 45 16 13 Maximum input sizes solvable within one hour. 5.4 Punch line Slide 18 Slide 19 The equation e cient = polynomial has been accepted as the best available way of tying the empirical notion of a \practical algorithm" to a precisely formalized mathematical concept. 5.5 Denition An algorithm runs in polynomial time if its running time is O(jI jk ), where jI j is the input size, and all numbers in intermediate computations can be stored with O(jI jk ) bits. 6 Slide 20