close

Вход

Забыли?

вход по аккаунту

?

157

код для вставкиСкачать
Dynamic Slope Scaling and Trust Interval Techniques
for Solving Concave Piecewise Linear
Network Flow Problems
Dukwon Kim
Center for Applied Optimization, Department of Industrial and Systems Engineering, 303 Weil Hall,
University of Florida, Gainesville, Florida 32611
Panos M. Pardalos
Center for Applied Optimization, Department of Industrial and Systems Engineering, 303 Weil Hall,
University of Florida, Gainesville, Florida 32611
In this paper, we propose an efficient heuristic approach for solving concave Piecewise Linear Network
Flow Problems (PLNFP) in which the cost is separable
and each arc cost is concave piecewise linear function of the total flow along the arcs. The problem is
well known to be NP -hard and exact global optimization algorithms are of limited use. In this paper, PLNFP
is transformed into an equivalent Fixed-Charge Network
Flow Problem (FCNFP) using an arc separation procedure, and we develop an algorithm combining the Dynamic Slope Scaling Procedure (DSSP) and Trust Interval techniques. Due to the fast growing size of the transformed FCNFP, exact branch-and-bound methods are
not able to handle the problems of practical size. Based
on the dynamic slope scaling algorithm developed for
solving FCNFP in previous work, we add a trust interval technique based on solution tendencies to speed
up the algorithm. The numerical experiments show that
the proposed algorithm is quite efficient and its performance is very stable. © 2000 John Wiley & Sons, Inc.
Keywords: minimum-cost network flow; piecewise linear cost;
fixed charge; global optimization
1. INTRODUCTION
In most network models considered in the literature,
the involved costs are assumed to be linear and/or convex. In many of the applications encountered in practice,
however, this assumption fails to hold. In fact, many of
the problems arising in real-world situations exhibit concave piecewise linearities or economies of scale in their
cost structures [3, 7].
Received November 1998; accepted December 1999
Correspondence to: P. M. Pardalos; e-mail: pardalos@ufl.edu
c 2000 John Wiley & Sons, Inc.
NETWORKS, Vol. 35(3), 216–222 2000
The concave Piecewise Linear Network Flow Problem (PLNFP) models arise in diverse applications along
with price-discounting situations such as transportation,
communication network design, production planning, location decision, and economic lot sizing. An extended
survey can be found in [1]. Another usage of PLNFP
models is to approximate global solutions for continuous
smooth concave minimization problems in branch-andbound schemes [6]. These problems are well known to
be NP-hard. However, in [2], a polynomial-time solvable concave cost network flow problem was observed
(see also [8]).
In this paper, three different approaches incorporating the Dynamic Slope Scaling Procedure (DSSP) [4]
are discussed. The first approach is used to solve a concave PLNFP by implementing a revised DSSP algorithm on the original formulation of concave PLNFP,
[CCPLNFP]. The second approach is to implement the
original DSSP algorithm for the fixed-charge version of
concave PLNFPs in the extended network. Note that usually we need to solve much larger fixed-charge network
flow problems than the original concave PLNFP due to
the separation of arcs [5]. For example, if each piecewise
linear arc cost function in the original concave PLNFP
has p linear segments (pieces), then the resulting fixed
charge version of concave PLNFP, [CCPLNFP]FC , is p
times larger than the original problem. This means that
the DSSP algorithm can have less capability to solve
large-scale concave PLNFPs. To improve the performance of the DSSP algorithm for the concave PLNFP
in the second approach, a revised DSSP algorithm incorporating a local search scheme, so-called trust intervals,
and a decision strategy, so-called a solution tendency, are
discussed in the third approach. Computational results
show that these schemes effectively remove unnecessary
separated arcs from consideration in the extended network, so that the size of [CCPLNFP]FC can be reduced
at each iteration of the DSSP algorithm. Computational
results from the implementation of these three different
approaches are reported.
2. THE PROBLEM AND FORMULATIONS
We consider the following network problem with concave piecewise arc costs. Given a directed graph G =
(N, A) consisting of a set N of m nodes and a set A of
n arcs, then solve
[CCPLNFP]
min f(x) =
X
fij (xij )
(i,j)∈A
subject to
X
(k,i)∈A
xki −
X
xik = bi ,
∀i ∈ N
(1)
(i,k)∈A
0 ≤ xij ≤ uij ,
∀(i, j) ∈ A,
(2)
where f is separable and each fij is piecewise linear. For
instance, the arc cost fij (xij ) can be defined in a standard
form as follows:

1

c x + sij,1 if 0 ≤ xij < λij

 ij,1 ij


1
2


 cij,2 xij + sij,2 if λij ≤ xij < λij
fij (xij ) = ..
..

.
.





r −1
r

 cij,rij xij + sij,rij if λijij ≤ xij ≤ λijij (= uij ),
(3)
r
, r = 1, 2, . . . , rij − 1, are breakpoints in the
where λij
given interval [0, uij ] and rij is the number of linear segments in each arc cost function fij . Note that due to the
concavity of arc costs slopes of each piecewise linear arc
cost function cij,r , r = 1, 2, . . . , rij satisfy the following
property:
cij,1 > cij,2 > · · · > cij,rij .
(4)
Using the Arc-separation procedure (ASP) [5] (see
Fig. 1), the original concave PLNFP can be transformed
into a fixed-charge model in an extended network. This
extended network is denoted by Ge (N, Ae ), where the
number of arcs |Ae | is given by
X
rij .
ne = |Ae | =
(i,j)∈A
Thus, the size of the extended network depends on the
number of linear segments in each arc cost function. In
general, additional constraints are required for each separated arc to specify the capacity of separated arcs. Due
to the concavity of arc costs, however, it is not necessary
to include these additional capacity constraints. This fact
can be generalized in the following theorem:
FIG. 1. Arc-separation procedure.
Theorem 1. Given an extended network described
∗
is optimal for a minimum
above, if a positive flow xij
q−1
q
∗
≤ λij for 1 ≤ q ≤ rij ,
concave PLNFP and if λij < xij
then it takes only one arc, (i, j)q (i.e., q-th arc) among
all separated arcs between node i and j, (i, j)k for k =
1, 2, . . . , rij .
Proof. Let us consider an arc (i, j) ∈ A with rij segments of concave piecewise linear cost function fij . Dek
the slope and fixed charge of the kth
note by cij,k and sij
piece of linear function for k = 1, 2, . . . , rij , respectively.
Notice that these slopes reflect the decreasing property
in (4). After the ASP, there are rij separated arcs the flow
can take. Let us denote by flowk the optimal flow on the
kth separated arc (i, j)k for k = 1, 2, . . . , rij .
∗
First, it is clear that if xij
is less than or equal to
1
the first breakpoint λij then the optimal flow cannot be
∗
) since we have the cost of arc
split (i.e., flow1 = xij
k
1
1
for k = 2, 3, . . . , rij .
(i, j)1 , fij ≤ fij , ∀xij ≤ λij
p
Second, consider the following two cases when λij ≤
q−1
q
∗
≤ λij , and suppose that the flowp and flowq
λij < xij
are optimal flows in the extended network problem:
∗
− ε > 0 for any
Case I. flowp = ε and flowq = xij
positive ε.
Suppose that the optimal flow is split into two arcs
(i, j)p and (i, j)q , 1 ≤ p < q ≤ rij . Now, let us evaluate
the difference of the cost function values in the original
∗
and the extended network problem with
PLNFP with xij
p
q
flow and flow :
p
q
∗
∗
− ε)] − fij (xij
)
[fij (ε) + fij (xij
∗
∗
− ε)] − (sij,q + cij,q xij
)
= [sij,p + cij,p ε + sij,q + cij,q (xij
= sij,q + ε(cij,p − cij,q )
> 0.
q
The inequality in the last term above holds since sij ≥
and cij,q < cij,p . But this contradicts the optimality of
flowp and flowq .
Case II.
∗
and flowq = 0.
flowp = ε = xij
NETWORKS–2000
217
As in Case I, we evaluate the difference of the cost
function values between node i and j:
p
q
∗
)
[fij (ε) + fij (0)] − fij (xij
∗
)
= (sij,p + cij,p ε) − (sij,q + cij,q xij
∗
∗
) − (sij,q + cij,q xij
)
= (sij,p + cij,p xij
> 0.
We can obtain a contradiction as in the argument for
∗
.
Case I, showing that flowq = xij
Based on the arc separation and Theorem 1, the problem can be formulated in a compact form. To formulate
the fixed-charge version of the concave PLNFP, let us
denote by
(i, j)r
xij,r
fij,r
the r-th separated arc between node i and j on
an extended network;
the flow in the r-th separated arc between node
i and j;
the fixed-charge cost function for r-th separated arc between node i and j, that is:
(
fij,r (xij,r ) =
cij,r xij,r + sij,r if xij,r > 0
0
otherwise.
[CCPLNFP]FC
rij
X X
(i,j)∈A r=1
rij
X
r=1
rij
X X
(i,k)∈A r=1
xij,r = xij ,
p
k
< x̄ij
< λij , p = 1, 2, . . . , rij , then
p
k
= λij , p = 1, 2, . . . , rij − 1, then Iij =
Case III. If x̄ij
{p, p + 1}.
fij,r (xij,r )
R − [CCPLNFP]FC
xik,r = bi ,
∀i ∈ N (5)
∀(i, j) ∈ A
min f(x) =
subject to
X X
(k,i)∈A r∈Iij
xij,r ≥ 0,
0 ≤ xij ≤ uij ,
∀(i, j) ∈ A, r = 1, 2, . . . , rij
∀(i, j) ∈ A.
It is clear that no additional constraints are needed to
specify capacities for separated arcs (i, j)r ∈ Ae , ∀i, j ∈
N due to Theorem 1. As a result, the solution of
concave PLNFP can be found by solving the fixedcharge network problem formulated as above. Note that
[CCPLNFP]FC is much larger than is [CCPLNFP] although it is relatively easier to solve. However, the computational effort can be reduced by using a special search
scheme incorporated in the DSSP approach.
218
p−1
Case II. If λij
Iij = {p}.
k
= λij (= uij ), then Iij = {rij }.
Case IV. If x̄ij
Thus, we solve the following reduced [CCPLNFP]FC
at each iteration of the DSSP instead of the original
[CCPLNFP]FC .
subject to
(k,i)∈A r=1
k
1
< λij
, then Iij = {1}.
If 0 ≤ x̄ij
rij
min f(x) =
xki,r −
Based on Theorem 1, we know that the optimal flow
∗
xij
takes only one among the separated arcs between
node i and j in an extended network. This suggests that
the solution can be obtained by only considering the most
trustable separated arcs in which the solution flow occurs. In other words, solving a reduced [CCPLNFP]FC
which has considerably fewer decision variables than
has the original [CCPLNFP]FC is sufficient to find solutions. These trustable arcs can be chosen in the DSSP
by identifying trust intervals with a solution tendency for
each concave piecewise linear arc cost function. Three
types of solution tendency can be observed, such as (1)
staying in the current interval, (2) moving down to the
next lower interval, and (3) moving up to the next higher
interval.
To explain such a mechanism, let us consider the k-th
iteration in the DSSP. It is clear that there can be four
k
occurs. For
situations in which the current solution, x̄ij
each case, let us define Iij to be an index set of trust
intervals for arc (i, j) ∈ A:
Case I.
Then, the problem is formulated as follows:
rij
X X
3. TRUST INTERVALS AND SOLUTION
TENDENCY
NETWORKS–2000
xki,r −
X
r∈Iij
X X
(i,j)∈A r∈Iij
X X
(i,k)∈A r∈Iij
xij,r = xij ,
xij,r ≥ 0,
0 ≤ xij ≤ uij ,
fij,r (xij,r )
xik,r = bi ,
∀i ∈ N (6)
∀(i, j) ∈ A
∀(i, j) ∈ A, ∀r ∈ Iij
∀(i, j) ∈ A.
As mentioned earlier, this procedure can be considered to be a local search scheme which reduces the number of separated arcs investigated at each iteration. An
example of trust intervals and the solution tendency discussed above is shown in Figure 2.
FIG. 3. Graphical illustration of the initial solution.
FIG. 2.
dency.
A graphical example of trust intervals and the solution ten-
4. ALGORITHMS
We have developed distinct algorithms for each of the
three approaches incorporating the DSSP to solve the
FCNFP. Each was implemented and tested on a common set of 200 PLNFPs. It should be noted that the
DSSP algorithm, discussed in Section 2, for solving the
original concave PLNFP model, [CCPLNFP], can potentially handle not only fixed-charge network problems
but also piecewise linear network problems. The performance of the DSSP algorithm on the original concave
PLNFP without transforming it into a [CCPLNFP]FC is
shown in the following section, including a comparison
with the others. Three different approaches using the revised DSSP algorithms for each formulation model are
described as follows.
1. Approach
I. DSSP
[CCPLNFP]:
•
algorithm
for
solving
–If k ≥ 1, then update

s
if λijr−1 < x̄ijk ≤ λijr
cij,r + x̄ij,r

k

ij

for r = 1, 2, . . . , rij
c̄ijk+1 =


 p
c̄ij
if x̄ijk = 0,
(9)
where p is the index of the most recent value
p−1
of the slope scaling factor, c̄ijk , when x̄ij > 0.
This updating scheme is shown in Figure 4.
2. Approach II. DSSP algorithm for solving [CCPLNFP]FC : In this approach, since the concave PLNFP
has been transformed into a fixed-charge problem
in an extended network, the original DSSP algorithm used for FCNFP can be implemented in the
same scheme. However, we need to solve very large
[CCPLNFP]FC instances since the size of extended
networks considered is much larger than the original
network. It is easy to see that the increasing rate of
the size depends on rij . Consequently, the computational time can grow rapidly if there are many linear
pieces in each arc cost.
3. Approach III. DSSP algorithm for solving R −
[CCPLNFP]FC : Since this approach is basically the
same as the second approach, the same initial solu-
Obtain initial solution x̄ij0 by solving LP with
c̄ij0 = cij,rij +
sij,rij
uij
for (i, j) ∈ A.
(7)
It is clear that this initial solution is obtained
by solving an LP problem with a simple linear underestimation of each concave piecewise
linear arc cost. This initial solution scheme is
illustrated in Figure 3.
• Updating scheme:
–If k = 0, then update

s

if λijr−1 < x̄ijk ≤ λijr
cij,r + x̄ij,r
k


ij

for r = 1, 2, . . . , rij (8)
c̄ijk+1 =


sij,rij

 cij,r +
if x̄ijk = 0.
ij
uij
FIG. 4. Graphical illustration of the updating scheme.
NETWORKS–2000
219
TABLE 1. Computational results of DSSP in Approach I.
Size
DSSP
Problem
Branch and bound
Group
Set no.
m
n
rij
REa (%) (min, max)
CPU (sec) (min, max)
CPU (sec) (min, max)
P1
1
12
35
3
2
12
35
5
0.082
(0.00, 0.28)
0.301
(0.01, 0.88)
0.012
(0.01, 0.02)
0.014
(0.01, 0.02)
5.384
(1.02, 8.30)
14.216
(1.29, 54.75)
3
18
80
3
4
18
80
5
0.688
(0.12, 1.23)
0.713
(0.13, 1.82)
0.016
(0.01, 0.03)
0.019
(0.01, 0.04)
229.718
(21.03, 781.40)
813.244
(45.11, 1610.38)
5
27
175
3
n/ab
n/a
6
27
175
5
n/a
0.039
(0.02, 0.07)
0.072
(0.02, 0.08)
7
32
225
3
n/a
8
32
225
5
n/a
9
37
335
3
n/a
10
37
335
5
n/a
P2
P3
P4
P5
a
b
n/a
0.048
(0.03, 0.11)
0.121
(0.04, 0.34)
n/a
0.106
(0.06, 0.32)
0.153
(0.06, 0.45)
n/a
n/a
n/a
The average Relative Error
Exact solutions are not available from B&B due to memory limitations.
tions and updating scheme as in the original DSSP
for FCNFP are used in the DSSP algorithm for solving the R − [CCPLNFP]FC model. Employing trust
intervals based on the solution tendency, most unnecessary variables (arcs) in the [CCPLNFP]FC model
can be removed from consideration at each iteration by identifying an index set of trust intervals, Iij ,
for each (i, j) ∈ A. Thus, the size of the resulting
R − [CCPLNFP]FC will be much smaller than the
[CCPLNFP]FC model, depending on the size of index
sets Iij . At any iteration, let R be the size of R −
[CCPLNFP]FC . Then,
R=
X
where |Iij | denotes the number of elements in Iij .
Note that 1 ≤ |Iij | ≤ 2. This means that the size
of the problem to be solved at each iteration in this
approach is at most twice that of the original concave
PLNFP.
TABLE 2. Computational results of DSSP in Approach II.
Size
DSSP
Problem
|Iij |,
(i,j)∈A
Branch and bound
Group
Set no.
m
n
rij
RE (%) (min, max)
CPU (sec) (min, max)
CPU (sec) (min, max)
P1
1
12
35
3
2
12
35
5
0.080
(0.00, 0.18)
0.214
(0.01, 0.47)
0.019
(0.01, 0.03)
0.039
(0.01, 0.08)
8.914
(1.92, 19.13)
16.450
(1.98, 49.17)
3
18
80
3
4
18
80
5
0.387
(0.16, 0.62)
0.411
(0.14, 0.83)
0.087
(0.03, 0.15)
0.314
(0.07, 0.79)
204.805
(20.77, 737.61)
792.133
(43.23, 1065.05)
5
27
175
3
n/a
n/a
6
27
175
5
n/a
0.399
(0.07, 0.81)
0.491
(0.09, 0.94)
7
32
225
3
n/a
n/a
8
32
225
5
n/a
0.401
(0.11, 0.92)
1.443
(0.58, 3.69)
9
37
335
3
n/a
n/a
10
37
335
5
n/a
1.219
(0.49, 4.01)
2.208
(0.92, 5.18)
P2
P3
P4
P5
220
NETWORKS–2000
n/a
n/a
n/a
TABLE 3. Computational results of DSSP in Approach III.
Size
DSSP
Problem
Branch and bound
Group
Set no.
m
n
rij
RE (%) (min, max)
CPU (sec) (min, max)
CPU (sec) (min, max)
P1
1
12
35
3
2
12
35
5
0.081
(0.00, 0.19)
0.229
(0.01, 0.59)
0.017
(0.01, 0.04)
0.039
(0.01, 0.07)
8.914
(1.92, 19.13)
16.450
(1.98, 49.17)
3
18
80
3
4
18
80
5
0.382
(0.16, 0.62)
0.441
(0.14, 0.83)
0.080
(0.03, 0.15)
0.121
(0.05, 0.68)
204.805
(20.77, 737.61)
792.133
(43.23, 1065.05)
5
27
175
3
n/a
n/a
6
27
175
5
n/a
0.333
(0.05, 0.79)
0.379
(0.06, 0.84)
7
32
225
3
n/a
n/a
8
32
225
5
n/a
0.351
(0.09, 0.89)
1.126
(0.27, 3.96)
9
37
335
3
n/a
n/a
10
37
335
5
n/a
1.085
(0.32, 3.43)
1.275
(0.68, 4.41)
P2
P3
P4
P5
In the DSSP algorithms described above, the same
stopping criterion as discussed in the previous study [4]
was used with only minor changes for indexing.
5. NUMERICAL EXPERIMENTS
To evaluate the efficiency and effectiveness of the algorithms, 200 problems of different sizes and structures
were solved applying the above-described algorithms.
These test problems are divided into five groups. Each
group has two sets of problems, and each set contains 20
problems. The first and second sets in each group consist of problems with the fixed number of linear pieces
rij = 3 and rij = 5, respectively.
The algorithms were programmed in C incorporating CPLEX 4.0 and implemented on a SUN workstation
running UNIX. Also, the branch-and-bound algorithm
in CPLEX 4.0 was utilized to obtain exact solutions by
solving the corresponding 0–1 mixed-integer programming problems. Due to the problem size and memory
limitations, exact solutions were
Pnot available when the
total number of linear pieces, (i,j)∈A rij exceeded 400
in most instances. Since rij is a fixed number (3 or 5)
in each group of problems, the total number of linear
pieces is n times rij , where n denotes the number of arcs
in the original network. Relative errors were computed
as follows:
#
"
fDSSP − fexact
× 100,
RE (%) =
fexact
and the solution time was measured by the total CPU
time exclusive of I/O operations.
Computational results for Approaches I, II, and III
are summarized in Table 1, 2, and 3, respectively. These
n/a
n/a
n/a
results show that the DSSP in Approach I requires the
smallest solution time (CPU time) to find solutions for
all instances. However, the average relative errors in Approach I are larger than those in Approaches II and III.
This implies that the DSSP in Approach I takes less time
to obtain solutions, but the quality of solutions from the
DSSP in Approach I is slightly worse than the others. For
example, in problem set 4 of group P2 (which consists of
20 problems with 18 nodes, 80 arcs, and 5 linear pieces
in each arc cost function), the average CPU time is 0.019
seconds in Approach I whereas it is 0.314 and 0.121 seconds in Approaches II and III, respectively. However, the
average relative error is 0.713% in Approach I, whereas
it is 0.411 and 0.441% in Approaches II and III, respectively.
Comparing the results for Approaches II and III, the
DSSP in Approach III which solves problems with the R
− [CCPLNFP]FC model turn out to be more efficient (less
solution time) than in Approach II, while the quality of
solutions has no significant difference. This implies that
FIG. 5
Comparison of the average relative errors.
NETWORKS–2000
221
FIG. 6
Comparison of the average CPU times.
the usage of “trust intervals” and “solution tendency” enhancements incorporated in the DSSP algorithm in Approach III is effective, especially when the rij values are
large. This is evident in Tables 2 and 3, where the average CPU time for problem set 4 (with rij = 5) in group
P2 is reduced from 0.314 to 0.121 seconds, whereas the
average CPU time is reduced from 0.087 to 0.080 seconds in problem set 3 (with rij = 5). Comparisons of
the average relative errors and the average CPU times
using these three approaches are shown in Figures 5 and
6, respectively.
In addition, the worst relative errors in Approaches I,
II, and III are 1.82, 0.83, and 0.91%, respectively. As a
result, the DSSP algorithms in both Approaches I and III
have a typical trade-off between a quality of solutions
and a solution time. Thus, choosing a proper approach
depends upon which attribute is more critical in a given
situation.
6. CONCLUDING REMARKS
In this paper, the DSSP algorithms with three different approaches were developed and implemented for
solving concave piecewise linear network flow problems.
As shown by the computational results and comparisons,
the DSSP in Approach I, which solves concave PLNFP
without transforming to the fixed-charge network model,
was the most efficient in CPU time, while the quality of
solutions in Approach I was slightly lower than those
in other approaches. This shows a strong possibility that
the DSSP can be directly applied for solving more general concave and nonconvex optimization problems, such
as continuous concave minimum-cost network problems
and nonconvex discontinuous piecewise linear network
flow problems.
Another positive achievement in this paper is the successful implementation of the trust interval and solu-
222
NETWORKS–2000
tion tendency enhancements to reduce the size of the
extended networks to be considered at each iteration.
Although the DSSP algorithm in Approach III requires
more solution time than does Approach I, it produces
better near-optimal solutions, especially in large-scale
problems. Considering the fact that the average CPU
time in Approach III is still small (less than 2 seconds),
this approach would be recommended in most cases except in the case where the solution time is relatively more
critical than is the quality of the solutions.
One of the referees of this paper suggested that Approaches II and III can be accomplished in the DSSP
using the original network rather than in the extended
network. It is possible only when the parallel arcs are
uncapacitated. However, these two approaches are necessary for the DSSP to handle both capacitated and uncapacitated problems effectively.
Acknowledgments
The authors would like to thank the anonymous
referees for several valuable comments.
REFERENCES
[1] G.M. Guisewite and P.M. Pardalos, Minimum concave-cost
network flow problems: Applications, complexity, and algorithms, Ann Oper Res 25 (1990), 75–100.
[2] G.M. Guisewite and P.M. Pardalos, A polynomial time
solvable concave cost network flow problem, Networks 23
(1993), 143–147.
[3] R. Horst, P.M. Pardalos, and N.V. Thoai, Introduction to
global optimization, Kluwer, 1995.
[4] D. Kim and P.M. Pardalos, A solution approach to the fixed
charge network flow problem using a dynamic slope scaling procedure, Oper Res Lett 24 (1999), 195–203.
[5] B.W. Lamar, “A method for solving network flow problems with general nonlinear arc costs,” D.-Z. Du and P.M.
Pardalos (Editors), Network optimization problems, World
Scientific, Singapore 1993, pp. 147–167.
[6] B.W. Lamar, An improved branch and bound algorithm for
minimum concave cost network flow problems, J Global
Optim 3 (1993), 261–287.
[7] P.M. Pardalos and J.B. Rosen, Constrained global optimization: Algorithms and applications, Lecture Notes in Computer Science 268, Springer-Verlag, Berlin, 1987.
[8] P.M. Pardalos and S. Vavasis, Open questions in complexity theory for numerical optimization, Math Program 57
(1992), 337–339.
[9] P.T. Thach, A decomposition method for the min concave
cost flow problem with a staircase structure, Jpn J Appl
Math 7 (1990), 103–120.
[10] W.I. Zangwill, Minimum concave-cost flows in certain
networks, Mgmt Sci 14 (1968), 429–450.
Документ
Категория
Без категории
Просмотров
3
Размер файла
126 Кб
Теги
157
1/--страниц
Пожаловаться на содержимое документа