Report

LP-Based Algorithms for Capacitated Facility Location Hyung-Chan An EPFL July 29, 2013 Joint work with Mohit Singh and Ola Svensson Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities 12 3 10 2 Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i∈F oi: opening cost of i∈F ≤3 5 ≤2 1 ≤3 20 Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i∈F oi: opening cost of i∈F Want: Choose S⊆F to open ≤3 5 ≤2 1 ≤3 20 Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i∈F oi: opening cost of i∈F Want: ≤3 5 ≤2 1 ≤3 20 Choose S⊆F to open Assign every client to an open facility f : D→S Capacities satisfied Capacitated facility location problem Given a metric cost c on 2 D: set of clients F: set of facilities Ui: capacity of i∈F oi: opening cost of i∈F 2 Want: 5 5 2 2 3 20 Choose S⊆F to open Assign every client to an open facility f : D→S Capacities satisfied Minimize Σi∈S oi + Σj∈D cj,f(j) = (20 + 5) + (2 + 2 + 2 + 5 + 2 + 3) Successful special case Uncapacitated facility location problem Ui = ∞ ∀i NP-hard to approximate better than 1.463 [Guha & Khuller 1999] [Sviridenko] 1.488-approximation algorithm [Li 2011] Successful special case Uncapacitated facility location problem Ui = ∞ ∀i NP-hard to approximate better than 1.463 [Guha & Khuller 1999] [Sviridenko] 1.488-approximation algorithm [Li 2011] Combining a linear program(LP)-rounding algorithm with a primal-dual algorithm LP-rounding 3.16-approximation [Shmoys, Tardos, Aardal 1997], LP-rounding & greedy 2.41approximation [Guha & Khuller 1999], LP-rounding 1.74-approximation [Chudak & Shmoys 1999], primal-dual 3-approximation [Jain & Vazirani 2001], combining 1.73-approximation [Charikar & Guha 1999], primal-dual 1.61-approximation [Jain, Mahdian, Markakis, Saberi,Vazirani 2003], LP-rounding 1.59approximation [Sviridenko 2002], primal-dual 1.52-approximation [Mahdian,Ye, Zhang 2006], combining 1.5-approximation algorithm [Byrka & Aardal 2010] The Question Can we use these LP-based techniques to solve the capacitated facility location problem? The Question Can we use these LP-based techniques to solve the capacitated facility location problem? All known approximation algorithms based on local search [Bansal, Garg, Gupta 2012], [Pal, Tardos, Wexler 2001], [Korupolu, Plaxton, Rajaraman 2000] 5-approximation The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Rich toolkit of algorithmic techniques The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Rich toolkit of algorithmic techniques Per-instance performance guarantee Application to related problems One of the ten Open Problems selected by the textbook of Williamson and Shmoys The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Why is this hard? Standard LP relaxation fails to bound the optimum within a reasonable factor Relaxed problems: uncapacitated problem, capacities can be violated [Abrams, Meyerson, Munagala, Plotkin 2002], facilities can be opened multiple times [Shmoys, Tardos, Aardal 1997], [Jain, Vazirani 2001], opening costs are uniform [Levi, Shmoys, Swamy 2012] The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Why is this hard? Standard LP relaxation fails to bound the optimum within a reasonable factor No LP relaxation known that is algorithmically amenable Main result Theorem There is a good LP: its optimum is within a constant factor of the true optimum. In particular, there is a poly-time algorithm that finds a solution whose cost is within a constant factor of the LP optimum. Our relaxation Standard LP rewritten ∀i∈F yi=1 if open, 0 if not ∀i∈F, j∈D xij=1 if j is assigned to i, 0 if not Consider a multicommodity flow network: arc (j, i) of capacity xij j∈D is a source of commodity j with demand 1 i∈F is a sink of commodity-oblivious capacity yi∙Ui commodity-specific capacity yi∙1 ≤3 y=1 ≤2 y=0 ≤3 y=1 All shown arcs are of capacity 1; others 0. Our relaxation Standard LP rewritten ∀i∈F yi=1 if open, 0 if not ∀i∈F, j∈D xij=1 if j is assigned to i, 0 if not Consider a multicommodity flow network: arc (j, i) of capacity xij j∈D is a source of commodity j with demand 1 i∈F is a sink of commodity-oblivious capacity yi∙Ui commodity-specific capacity yi∙1 Minimize subject to ≤3 y=1 ≤2 y=0 ≤3 y=1 All shown arcs are of capacity 1; others 0. Σi∈F oiyi + Σ i∈F, j∈D cijxij the flow network defined by (x, y) is feasible xij, yi ∈ {0, 1} Our relaxation Standard LP rewritten ∀i∈F yi=1 if open, 0 if not ∀i∈F, j∈D xij=1 if j is assigned to i, 0 if not Consider a multicommodity flow network: arc (j, i) of capacity xij j∈D is a source of commodity j with demand 1 i∈F is a sink of commodity-oblivious capacity yi∙Ui commodity-specific capacity yi∙1 Minimize subject to ≤3 y=1 ≤2 y=0 ≤3 y=1 All shown arcs are of capacity 1; others 0. Σi∈F oiyi + Σ i∈F, j∈D cijxij the flow network defined by (x, y) is feasible xij, yi ∈ [0, 1] Our relaxation Consider arbitrary partial assignment g : D↛F Suppose that clients are assigned according to g (x, y) should still give a feasible solution for the remaining clients: i.e., the flow network should still be feasible when the remaining clients have demand of 1 commodity-oblivious capacity of i is yi∙(Ui -|g-1(i)|) ≤3 ≤2 ≤3 only In similar spirit as knapsack-cover inequalities [Wolsey 1975] [Carr, Fleischer, Leung, Phillips 2000] LP constraint: the flow network defined by (g, x, y) is feasible for all g Is this really a relaxation? x ≤32 y=1 x ≤21 y=0 ≤3 y=1 All shown arcs are of capacity 1; others 0. Our relaxation Is this really a relaxation? No. The only facility adjacent from remaining clients has 1∙0 = 0 commodity-oblivious capacity ≤3 ≤2 ≤3 Introduce backward edges corresponding to g Now flows can be routed along alternating paths ≤3 y=1 ≤2 y=0 x ≤30 y=1 All shown arcs are of capacity 1; others 0. Our relaxation Minimize subject to Σi∈F oiyi + Σ i∈F, j∈D cijxij MFN(g, x, y) is feasible ∀partial assignment g where MFN(g, x, y) is a multicommodity flow network with arc (j, i) of capacity xij, arc (i, j) of capacity 1 if g assigns j to i, j∈D is a source of commodity j with demand 1 if not assigned by g, i∈F is a sink of commodity-oblivious capacity yi∙(Ui -|g-1(i)|) and commodity-specific capacity yi∙1. Our relaxation Minimize subject to Automatically embraces Σi∈F oiyi + Σ i∈F, j∈D cijxij MFN(g, x, y) is feasible ∀partial assignment g Standard LP when g is the empty partial function Knapsack-cover inequalities Can be separated with respect to any given g Algorithm uses feasibility of MFN(g, x, y) for a single g Invoke standard techniques [Carr, Fleischer, Leung, Phillips 2000], [Levi, Lodi, Sviridenko 2007] LP-rounding algorithm LP-rounding algorithm I ← {i∈F | y*i > ½}, S ← {i∈F | y*i ≤ ½}; open I Choose a partial assignment g : D↛I For each client j assigned by g, Can afford it assign j in the same way Remaining clients are to be assigned to S Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S. LP-rounding algorithm Remaining clients are to be assigned to S MFN(g, x*, y*) remains feasible even when “restricted” to S MFN(∅, x*, y*) is feasible when restricted to remaining clients i.e., it is feasible for the standard LP Commodity-oblivious capacity of i∈S is yi∙Ui ≤ Ui / 2 Capacity constraints are not tight Can use Abrams et al.’s algorithm based on the standard LP Finds 18-approx soln where capacities are violated by 2 Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S. LP-rounding algorithm Can use Abrams et al.’s algorithm based on the standard LP Finds 18-approx soln where capacities are violated by 2 A 288-approximation algorithm Obvious improvements, but perhaps not leading to ≤5 Determination of integrality gap remains open Lemma We can choose a fractional partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where at least half of each commodity’s flow is drained at S. LP-rounding algorithm Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S. LP-rounding algorithm Simplifying assumption For each client j, all its incident edges in the support have equal costs Support of x* := { (i, j) | x*ij > 0 } 1 1/3 1/3 1/3 1 1/2 1/2 1/2 1/2 ≤2 y=1 ≤1 y=1 ≤1 y=1 ≤2 y=1/2 ≤2 y=1/2 x-values shown on edges Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S. LP-rounding algorithm ≤2 Simplifying assumption For each client j, all its incident edges in the support have equal costs Support of x* := { (i, j) | x* ij >0} ≤1 ≤1 ≤2 ≤2 Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S. LP-rounding algorithm y* I ← {i∈F | i > ½}, S ← {i∈F | i ≤ ½}; open I Find a maximum bipartite matching g on the support of x* j∈D is matched at most once i∈I is matched up to Ui times i∈S is not matched y* ≤2 ≤1 I ≤1 ≤2 ≤2 S LP-rounding algorithm y* I ← {i∈F | i > ½}, S ← {i∈F | i ≤ ½}; open I Find a maximum bipartite matching g on the support of x* j∈D is matched at most once i∈I is matched up to Ui times i∈S is not matched y* ≤2 ≤1 I ≤1 ≤2 ≤2 S LP-rounding algorithm y* I ← {i∈F | i > ½}, S ← {i∈F | i ≤ ½}; open I Find a maximum bipartite matching g on the support of x* y* j∈D is matched at most once i∈I is matched up to Ui times i∈S is not matched Now we observe MFN(g, x*, y*) There exists no path from a remaining client to a facility in I that is “undermatched” ≤2 ≤1 I ≤1 ≤2 ≤2 S ≤2 ≤1 I ≤1 ≤2 ≤2 S LP-rounding algorithm y* I ← {i∈F | i > ½}, S ← {i∈F | i ≤ ½}; open I Find a maximum bipartite matching g on the support of x* y* j∈D is matched at most once i∈I is matched up to Ui times i∈S is not matched Now we observe MFN(g, x*, y*) There exists no path from a remaining client to a facility in I that is “undermatched” “Fully matched” facility has zero capacity All flow drained at S ≤2 ≤1 I ≤1 ≤2 ≤2 S x ≤21 x I ≤10 x ≤10 ≤2 ≤2 S Main result Theorem There is a good LP: its optimum is within a constant factor of the true optimum. In particular, there is a poly-time algorithm that finds a solution whose cost is within a constant factor of the LP optimum. The Question Can we use LP-based techniques to solve the capacitated facility location problem? Yes! Can we use other LP-based techniques with our new relaxation? Can we apply these results to related problems? Can we improve our integrality gap bounds? Thank you.