Network Design - Network Loading and Pup Matching

Network Design: Network Loading and Pup Matching Today’s Agenda † Network design in general † Network loading † Solution approaches ‹Polyhedral ‹Polyhedral combinatorics combinatorics ‹Heuristics ‹Heuristics † Pup matching Network Design: Basic Issue Total Total (Fixed) (Fixed) Cost Cost on on Each Each Arc Arc Commodity Commodity k: k: Origin Origin O(k) O(k) Destination Destination D(k) D(k) Flow Flow req. req. rrkk Link Link (i,j): (i,j): Fixed Fixed cost cost F Fijij Flow Flow cost cost ccijij Possibly: Possibly: Capacity Capacity C C per per unit unit installed installed on on any any edge edge Network Design Applications † Telecommunications systems † Airline route maps † Chip design † Facility location † Even TSP! Multicommodity Flow Model with Complex Costs minimize c( f ) subject to Nf k = b k for k = 1, 2,..., K f = ( f 1 , f 2 ,..., f K ) ≥ 0  r kk if i = O(k )    biikk =  − r kk if i = D(k )   0 otherwise    k ij (possible flow bounds on f ) c( f ) = ∑ ( i , j )∈A cij ( fij ) separability c( f ) = ∑ ( i , j )∈A lij c ( fij ) proportionality fij = ∑ k fijk ( fij = ∑ k wk f ijk ) Basic Cost Structures cij(fij) cij (fij) fij fij Network Loading Cost LP Approximation cij(fij) LP Gap C 2C fij Other Cost Structures cij (fij) cij (fij) fij fij Integer Programming Model minimize ∑ k c k f k + ∑ ( i , j )∈E Fij yij subject to Nf = b k ∑ (f k k ij +f k ji k k = 1, 2,..., K ) ≤ Cy ij {i, j} ∈ E fijk ≤ r k yij {i, j} ∈ E , all k f = ( f 1 , f 2 ,..., f K ) ≥ 0 yij ≥ 0 and integer all {i, j} ∈ E (configuration constraints and y ) (1) (2) Cuts for Lower Bounds † † LP LP relaxations relaxations yield yield lower lower bounds bounds † † Addition Addition of of cuts cuts can can tighten tighten bounds bounds ‹ ‹ Cut Cut away away solutions solutions to to the the LP LP relaxation relaxation but but leave leave all all feasible feasible integer integer points points † † Network Loading Model min ∑ {i , j}∈E Fij yij subject to  1, i = O(k )  k k fij − ∑ f ji = −1, i = D(k ) all k ∈ K , i ∈ N ∑ { j:(i , j )∈A} { j:( j ,i )∈A} 0, otherwise  ∑( k∈K ) fijk + f jik ≤ Cyij all {i,j}∈ E fijk ≥ 0, yij ≥ 0 and integer Improved Modeling (Cutset Inequalities) F Fjj == 11 all all edges, edges, all all ccijij == 00 C C == 24 24 Designs Designs 11 Demands Demands Y>3 1 Y>2 24 24 1 66 Y>1 2 30 30 4 12 12 11 1/4 1/4 1/4 1/4 4 Y>3 3 12 12 2 2 1 2 1 4 1/2 1/2 3 LP LP == 33 ½ ½ 1/2 1/2 11 11 Opt = Opt = 3 55 General Cutset Inequality DST = total demand (nodes in S to nodes in T) Set S of nodes Set T of nodes  DST  YST ≥   C  Cutset Inequalities Aren’t Sufficient Capacity C = 1 Demand = 1 between all non -adjacent nodes non-adjacent Loading 1 unit on all visible edges satisfies cutset inequalities, but not feasible Pup Matching Example optimal solution is 9 Pup Matching † † Instance: Instance: A A directed directed network network G G == (N,A), (N,A), aa set set of of K K pairs pairs of of elements elements from from N, N, and and aa cost cost function function c: c: A→R+. A→R+. † † Problem: Problem: Find Find the the minimum minimum cost cost loading loading of of G G permitting permitting unit unit flow flow from from the the first first to to the the second second node node of of each each of of the the K K pairs pairs such such that that 11 unit unit or or 22 units units together together can can traverse traverse an an arc arc for for each each unit unit of of loading. loading. One One unit unit of of loading loading on on aa ∈A ∈A costs costs c(a). c(a). Example on City Blocks Solution with cost 196 Several days computation can prove only that the objective is at least 184 (LP lower bound = 182). Can we do better? Heuristics for Upper Bounds † † Matching Matching Heuristic Heuristic ‹ ‹permits permits each each pup pup to to be be paired paired with with at at most most one one other other pup pup ‹ ‹solved solved with with aa weighted weighted matching matching routine routine † † Shortest Shortest Path Path Heuristics Heuristics ‹ ‹three three variations variations † † Each Each heuristic heuristic provides provides aa 2-approximation 2-approximation to to the the NLP NLP formulation formulation Odd Flow Inequality † If the flow on an arc is odd, one unit of loaded capacity will be unused † If the net demand of a node is odd, the total inflow or total outflow is odd  1 1 k k + y − f + f ) (  ∑∑ ij ij ji ji )  ≥ 2 k j  2 ∑( y j Odd Flows on the City Block Each Each of of the the 56 56 nodes nodes must must be be incident incident to to at at least least one one arc arc with with 1 unit of spare capacity unit of spare capacity 2 Ä Ä solution solution requires requires at at least least 56   1 ⋅ = 14 cabs’ cabs’  2 2   worth worth of of empty empty capacity capacity LP LP relaxation relaxation of of 182 182 gives gives lower lower bound bound on on required required used used capacity capacity Ä Ä 196 196 is is optimal optimal Gap Reductions on City Block Problems † Trials Using Realistic Data † † Node Node set set given given in in (latitude, (latitude, longitude) longitude) format format based based on on aa real real logistics logistics network network † † Defined Defined problems problems by by choosing choosing aa subset subset of of nodes, nodes, calculating calculating arc arc lengths, lengths, and and randomly randomly selecting selecting O-D O-D pairs pairs † † 30 30 problems, problems, about about half half single single origin origin † † Complete Complete graphs, graphs, 12-25 12-25 nodes, nodes, 6-50 6-50 pups pups Results † † Branch Branch and and Bound Bound limited limited to to 22 hours hours CPU CPU time time and and aa 220M 220M tree tree † † With With all all 33 cut cut families, families, 67% 67% were were solved solved to to optimality optimality with with an an average average gap gap reduction reduction of of 18.8% 18.8% to to 6.4% 6.4% † † Without Without odd odd flow flow cuts, cuts, 30% 30% were were solved, solved, and and the the gap gap was was reduced reduced to to 7.8% 7.8% on on average average † † With With no no cuts, cuts, 17% 17% were were solved solved † † Among Among solved solved problems, problems, average average heuristic heuristic error error was was 1.3% 1.3% Conclusions and Extensions † † Extensions Extensions apply apply to to compartmentalized compartmentalized problems problems † † Cuts Cuts seem seem critical critical to to provably provably solving solving the the PM PM problem problem † † Odd Odd flow flow inequalities inequalities define define what what seems seems an an important important set set of of facets facets ‹ ‹generalize generalize to to arbitrary arbitrary capacity capacity ‹ ‹can can generalize generalize to to several several facilities? facilities? † † Are Are there there other other cuts cuts based based on on even-odd even-odd type type arguments? arguments? Many, Many Network Design Variants † Network loading for compartmentalized capacity ‹airline ‹airline capacity capacity planning, planning, tanker tanker trucks trucks † Network survivability † Network restoration † Hierarchical designs †… Today’s Lessons † Network design arises in numerous applications † Problem is a large-scale integer program † Introduction to cutting planes (polyhedral combinatorics) † Cutting planes valuable in tightening formulations and in problem solving Module on Large-Scale Integer Programming & Combinatorial Optimization Three Lectures † Traveling salesman problem † Facility location † Network design Games/Challenges Applications, Models, and Solution Methods