Minimum Concave cost flows in capacitated grid networks

Minimum Concave Cost Flows in Capacitated Grid Networks
Shabbir
1
Ahmed ,
Qie
2
He ,
Shi
3
Li ,
George L.
1
Nemhauser
2014 Mixed Integer Programming Workshop
1 H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
2 Department of Industrial and Systems Engineering, University of Minnesota
3 Toyota Technological Institute at Chicago
Problem description
CFG: find a min cost flow over the following grid network
v 1,1
v 1,T −1
v 1,2
v 1,T
The dynamic programing formulation
• Decision stages. T + 1 stages corresponding to the dummy period 0 and periods t = 1, . . . , T .
• States st. L-dimensional vector, with each component being the flow over the forward arc
(vl,t, vl,t+1) for echelon l = 1, . . . , L.
v 2,1
v 2,2
v 2, T
v 2, T −1
...
v L−1,1
• Decision variables ut, with each component being the flow over the downward arc (vl,t+1, vl+1,t+1)
for each echelon l.
v L−1,T
Observation 1. Essentially CFG is to optimize a concave function over a polyhedron, so there
must exist an extreme point (extreme flow) which is optimal.
We only need to consider the states corresponding to a finite number of extreme flows.
v L ,1
v L ,2
Assumption: sources at echelon 1 and sinks at echelon 2 to L.
P
Given an extreme flow, the flow over arc a is fa = v∈T2 b(v).
T1
State space reduction: from uncountable to finite.
v L−1,T −1
v L−1,2
Polynomially solvable uncapacitated cases
v L ,T −1
v L ,T
We can prove that CFG is polynomially solvable with fixed L by showing that each horizontal
arc takes a polynomial number of values under all extreme flows.
T2
u
Proof. Partition the sources and sinks in T2 through echelons: T2 = ∪L
l=1Vl , where Vl is the set of
sources and sinks in T2 at echelon l. Then
fa =
Polynomially solvable capacitated cases
• T time periods and L echelons,
• supply or demand b(vl,t) at each node vl,t (source, sink, or transshipment node),
• capacity Ua over arc a ∈ A,
• concave cost function ca : R+ → R+ over each arc a ∈ A, given by a value oracle.
Main results
Capacitated case (suppose the cardinality of the set {Ua|a ∈ A} is constant)
One echelons of sources and one echelon of sinks Two echelons of sources
Fixed L
P∗
NP-hard∗
General L
?
NP-hard∗
Assumption: all sources at echelon 1, all sinks at echelon L and a constant number of capacity
values.
Fixed L
General L
P [Erickson et al. 87]
P [Erickson et al. 87]
Deleting arc a breaks T into two subtrees T1 and T2.
P
P
P
The flow over arc a is fa = v∈T2 b(v) + e∈δ(T1,T2) Ue. We are trying to argue that v∈T2 b(v)
P
and e∈δ(T1,T2) Ue take a polynomial number of values under all extreme flows, respectively.
l=1 v∈Vl
Claim: for each echelon l, Vl is a union of vertices in at most three intervals.
P
Then the term v∈Vl b(v) can take O(T 6) values.
NP-hard cases
The polynomially solvable cases all become NP-hard when any of the conditions is relaxed.
Proposition 3. If there are two echelon of sinks, CFG is NP-hard with L = 3, a single source and
a single capacity value.
n
Σ i=1 (B− yi )+Y
T2
v 1,1
(0, B)
Two echelons of sources
and two echelons of sinks
a
u
v
B− y1
Another polynomially solvable case is the uncapacitated planar graph with sources and sinks on
a constant number of faces [Erickson et al. 87].
(0, B)
v 2, n−1
v 2, n
B− y n−1
(c n−1 , B)
B− y n
(c n , B)
v 3, n
Y
P
v∈T2 b(v).
Proposition 1. The term
2) values under all extreme flows.
b(v)
takes
O(T
v∈T2
P
Proof. We claim that the sources and sinks in T2 lie consecutively on the boundary of the grid for
any extreme flow. Proof by contradiction. Suppose that u1, v1, u2, v2 lie on the boundary in the
clockwise order with u1, u2 ∈ T1 and v1, v2 ∈ T2.
u1
The pair (c, U ) on some arc a denotes that the cost is c if the arc carries nonzero flow and 0
otherwise and the arc capacity is U .
Proposition 4. CFG with two echelons of sources and two echelons of sinks is NP-hard.
Proof. Reduction from the partition problem.
Σ ni=1 y i / 2
v 1,1
v1
v 1,2 n
D
v 2,1
• Uncapacitated polynomially solvable cases: uncapacitated lot-sizing model [Wagner and Whitin
58] and many of its variants (multi-echelon [Zangwill 69], backlogging, intermediate demands
[Zhang et al. 12]), pure remanufacturing model with fixed-charge production cost and linear
inventory holding cost [van den Heuvel and Wagelmans 08], grid network with a single source
and multi-echelon sinks, grid network with one echelon of sources and two echelons of sinks
[He et al. 14].
Our results generalize the above complexity results.
(0, B)
B− y 2
(c 2, B)
D
• Capacitated polynomially solvable cases (very few): constant capacitated lot-sizing model
[Florian and Klein 71], two-stage lot-sizing model with constant production capacity at the
first stage and linear production cost [Kaminsky and Simchi-Levi 03], multi-echelon serial supply chain with constant production capacity at the first stage and general concave production
and inventory costs [Van Hoesel et al. 05], uncapacitated lot-sizing with bounded inventory
[Atamt¨urk and K¨uc¸u¨ kyavuz 05, 08].
.....
v 2,2
(c 1, B)
Polynomiality of
Related results
(0, B)
v 2,1
NP-hard∗
NP-hard∗
All polynomial solvable cases are tight in a sense that each case becomes NP-hard when any
condition is relaxed.
b(v).
Proof. Reduction from the knapsack problem.
T1
∗ - New complexity results.
L X
X
Given an extreme flow, the set of arcs carrying flow between 0 and the capacity induces a tree T .
Uncapacitated case
One echelons of sources
and multiple echelons of
sinks
P∗
NP-hard∗
v
Proposition 2. The flow fa can take O(T 6L) values under all extreme flows.
given the input:
One echelon of sources
and one echelon of sinks
a
v 2,2
(1,∞)
v 3,1
u2
(1,∞)
D
v 2,3
v 2,2 n−1
v 2,4
(1,∞)
v 3,2
y1
v 3,3
(1,∞)
v 2,2 n
(1,∞)
v 3,4
.....
v 3,2 n−1
y2
(1,∞)
v 3,2 n
yn
v 4,1
nD −Σ ni=1 y i / 2
v2
The path u1u2 will intersect the path v1v2, implying that T1 and T2 are connected, a contradiction.
Proposition 5.
• If the number of echelons L is an input parameter, CFG is NP-hard.
Polynomiality of
P
e∈δ(T1,T2) Ue.
The cardinality of δ(T1, T2) is O(T ), and there are a constant number of capacity values, so
P
o(1)) values under all extreme flows.
U
can
take
O(T
e
e∈δ(T1,T2)
• If the grid network contains upward arcs, CFG is NP-hard for fixed L ≥ 3.
For more details, please see the following working paper.
Shabbir Ahmed, Qie He, Shi Li and George L. Nemhauser. Minimum concave cost flows in
capacitated grid networks (2014). Available at http://www.optimization-online.
org/DB_HTML/2014/03/4300.html.

Download Report