Module on Large-Scale Integer Programming and Combinatorial Optimization

Module on Large-Scale Integer Programming & Combinatorial Optimization Three Lectures † Traveling salesman problem † Facility location † Network design Games/Challenges Applications, Models, and Solution Methods Traveling Salesman Problem 1 Agenda † † Origins Origins † † Electronic Electronic Component Component Placement Placement † † TSP TSP Model Model † † Turbine Turbine Vane Vane Placement Placement † † Other Other Applications Applications of of TSP TSP † † Solution Solution Methods Methods ‹ ‹Heuristic Heuristic Methods Methods ‹ ‹Lagrangian Lagrangian relaxation relaxation (bounding (bounding methods) methods) † † Some Some large large scale scale instances instances (computations) (computations) 2 William Rowan Hamilton Icosian game 3 20 19 Icosian game 1 18 2 15 14 17 16 3 4 5 6 13 7 9 10 11 8 12 Hamiltonian Path and the TSP 4 Interest in Traveling Salesman Problem (TSP) † Arises in Many Applications † Alluring (Captures Imagination) † Notoriously Difficult to Solve † Has Attracted Best Minds in Math/CS/OR for 40 Years 5 The Traveling Salesman Problem and Electronics Assembly 6 Placement Problem Placement Locations Feeders 7 Placement Sequence 8 Traveling Salesman Interpretation Home Position 9 Model Ingredients cjkjk cost of placing module k after placing module j xjkjk = 1 if placement k follows =1 placement j 0 otherwise 10 Assignment Problem Minimize Σjj Σkk cjkjkxjkjk subject to Σkkxjkjk Σjj xjkjk xjkjk = = > 1 for each j 1 for each k 0 for all j & k Proper TSP Model? 11 Subtour Solution 12 TSP Model Assignment Model + Subtour Breaking Constraints Σjj∈S < |S| - 1 for all subsets ∈S Σkk∈S ∈S xjk jk S of nodes {2,3,…,n} Proper TSP Model? 13 13 Implications for IC Insertions † Manual Designs ⇒ Long Time ‹10 ‹10 hours hours for for 70 70 to to 100 100 components components † Better Solutions ‹10-25% ‹10-25% improvements improvements by by optimization optimization Other Applications Similar 23 Feeder Placement † Modeling? † Solution Methods? ‹Heuristic ‹Heuristic ‹Optimization ‹Optimization 24 ? ? Other Applications of TSP? 14 Other Applications of TSP Machine Scheduling Machine “Visits” Jobs Travel Time = Set up Time 15 15 Other Applications † † Analyzing Analyzing the the structure structure of of crystals crystals † † Material Material handling handling in in aa warehouse warehouse † † Clustering Clustering of of data data arrays arrays † † Cutting Cutting stock stock problems problems † † Genome Genome sequencing sequencing † † Starlight Starlight interferometer interferometer satellite satellite positioning positioning † † DNA DNA universal universal strings strings † † Collecting Collecting coins coins from from payphones payphones Solving the TSP 26 City Traveling Salesman Problem 55 00 SS EE 44 55 MN MN PP OO M MLL OOM M BBOO CCLL CCHH 44 00 PPII DDEE Latitude Latitude DDTT KKSS LL aa titi tutu dd ee SS FF TTUU 33 55 SS LL IN IN CCNN NNYY PPHH W WAA M MEE LLAA AATT DDAA 33 00 HHUU 22 55 112200 111100 110000 Lo Long ngitud itudee NNOO 99 00 88 00 77 00 20 20 Finding a Good Solution ‰ How? ‰ How good is good? ‹ LP bounds ‹LP ‹ Combinatorial bounds ‹Combinatorial 21 Solution Methods † Heuristics ‹Growing ‹Growing solutions: solutions: nearest nearest neighbor, neighbor, farthest farthest neighbor, neighbor, nearest nearest insertion insertion ‹Improvement ‹Improvement procedures: procedures: 2-opt, 2-opt, 3-opt 3-opt † Optimization Methods ‹Bounding: ‹Bounding: LP LP relaxation, relaxation, Lagrangian Lagrangian dual dual ‹Polyhedral ‹Polyhedral methods methods (cutting (cutting planes) planes) Heuristics † Build Tour ‹Nearest ‹Nearest Neighbor Neighbor ‹Nearest/Farthest ‹Nearest/Farthest Insertion Insertion † Improve Tour ‹Swapping ‹Swapping Edges Edges 22 Insertion Heuristics 5 1 x 4 5 1 2 3 6 2 x 4 Nearest Insertion 3 6 Farthest Insertion Tour Improvements 5 2-opt 2 1 3 4 5 6 2 1 3 4 6 Eliminate Eliminate 22 arcs arcs and and reconnect reconnect Choose Choose best best alternative alternative at at each each step step Exploiting Embedded Structure ∑ ∑ cx subject to ∑ x = 1 for all i = 1, 2,K , n ∑ x = 1 for all j = 1, 2,K , n ∑ ∑ x = n−2 ∑ ∑ x ≤ S − 1 for all S ⊆ {2,3,K , n} minimize n n i =1 j =1 ij ij n j =1 ij n i =1 ij n n i=2 j =2 i∈S Redundant Redundant Constraint Constraint j∈S ij ij xij ≥ 0 and integer Minimum Minimum spanning spanning tree tree on on nodes nodes 22 to to nn Underlying Structure Decomposed Tour 5 2 1 3 4 Arc Arc in in and and out out of of node node 11 6 Path Path (hence (hence tree) tree) on on nodes nodes 22 to to nn Lagrangian Relaxation n  L(u , v) = minimize ∑ i =1 ∑ j =1 cij xij + ∑ i = 2 ui ∑ j =1 xij − 1    n n  + ∑ j = 2 v j ∑ i =1 xij − 1    n ∑ ∑ ∑ ∑ ∑ ∑ subject to n n n x =1 j =1 1 j n x =1 i =1 i1 n n i =2 j =2 i∈S j∈S xij = n − 2 xij ≤ S − 1 for all S ⊆ {2,3,K , n} xij ≥ 0 and integer Improving Lagrangian Lower Bound Solution x* to Lagrangian Relaxation 5 2 1 3 4 Too many arcs out Increase u5 c5j+ u5 + vj more expensive 6 Too few arcs out Decrease u6 c6j+ u6 + vj less expensive Solution Approach (Dual Ascent) † † Solve Solve L(u,v) L(u,v) ‹ ‹Use Use costs costs ccijij++ vvii ++ uujj ‹ ‹Select Select least least cost cost arc arc out out of of and and into into node node 11 ‹ ‹Find Find minimal minimal spanning spanning tree tree on on nodes nodes 22 to to nn (easy) (easy) † † Let Let x* x* be be optimal optimal solution solution to to L(u,v) L(u,v) † † Using Using x* x* alter alter u u and and vv to to increase increase lower lower bound bound L(u,v) L(u,v) † † Iterate Iterate to to solve solve Lagrangian Lagrangian dual dual L(u,v) d d == max max u,v u,v L(u,v) Dual Ascent in General v * = minimize cx Complicating Complicating subject to Ax = b Constraints Constraints x∈ X e.g., X = { x : Dx = d , x ≥ 0} Lagrangian Dual L(u ) = minimize cx + u [ Ax − b ] subject to x ∈ X Dual Ascent in General If L(u ) = cx(u ) + u  Ax(u ) − b  k k ∇L(u ) ≈ Ax(u ) − b k k k k = u − θ k  Ax(u ) − b  k λk cx(u ) − v * θk = 2 k Ax(u ) − b u k +1 k k Dual Ascent Convergence Theorem If 0 < ε1 ≤ λk ≤ 2 − ε 2 and Ax(u ) − b are bounded, k then c(xk) converges to v*. In practice, continue with fixed λk except half λk after some number (50?) of iterations if c(xk) doesn’t decrease Solving Minimum Spanning Tree Greedy (Kruskal Algorithm) † Order arcs from smallest to highest costs † Choose arcs in order ‹If ‹If arc arc does does not not form form an an undirected undirected circuit circuit with with arcs arcs already already chosen, chosen, then then choose choose arc; arc; ‹Otherwise ‹Otherwise eliminate eliminate arc arc from from consideration consideration Amazing Facts! † † Greedy Greedy algorithm algorithm (and (and several several variants) variants) solves solves the the minimum minimum spanning spanning problem problem † † The The linear linear programming programming relaxation relaxation of of the the formulation formulation we we have have given given for for the the minimum minimum spanning spanning problem problem always always has has an an integer integer solution solution (the (the underlying underlying polyhedron polyhedron has has integer integer extreme extreme points) points) Solving Network Flow Problems † Giden (Graphical Environment for Network Optimization) ‹Demonstration of • Minimum spanning trees • Maximum flows • Minimum cost flows 2103 hole printed circuit board example 11,849 hole printed circuit board example 11,849 hole printed circuit board solution 13,094,345 seconds total on 55 CPUs Traveling Traveling salesman salesman problem problem through through 15,112 15,112 cities cities in in Germany Germany 22.6 22.6 years years of of computation computation on on network network of of 110 110 Processors Processors Today’s Lessons † † Traveling Traveling salesman salesman problem problem arises arises in in numerous numerous applications applications † † Problem Problem is is aa large-scale large-scale integer integer program program † † Many Many heuristic heuristic methods: methods: often often find find good good solutions solutions † † Lagrangian Lagrangian dual dual (bounding) (bounding) exploits exploits special special problem problem structure structure (embedded (embedded minimal minimal spanning spanning tree) tree) † † MST MST is is easy easy to to solve solve We We did did NOT NOT examine examine polyhedral polyhedral (cutting (cutting plane) plane) methods methods