slides (short)

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.

similar documents