This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
(/(x)) is quasi convex. Quasi-convex functions enjoy the following nice properties: • A strict local minimum of a quasi-convex function is a strict global minimum. • A local minimum of a semistrictly quasi-convex function is a global minimum. • Level sets of quasi-convex functions are convex sets. Due to these properties, quasi convexity also plays an important role in continuous optimization (see, e.g., Avriel-Diewert-Schaible—Zang [5]). The concept of quasi M-convexity is defined for a function / : Zv —> Ru{+oo} as follows. Recall the exchange axiom for M-convex functions: (M-EXC[Z]) For x,y € dom/ and u £ supp+(x — y), there exists v £ supp~ (x — y) satisfying
The sign patterns of &f(x;v,u) and A/(j/;u, v) compatible with (implied by) inequality (6.91) are as follows:
Here Q and x denote possible and impossible cases, respectively. Relaxing condition (6.91) to compatible sign patterns leads to two versions of quasi M-convex functions. We say that a function / : Zv —> R U {+00} with dom / / 0 is quasi M-convex if it satisfies the following: (QM) For x,y 6 dom/ and u G supp+(x — y), there exists v £ supp~ (a: - y) satisfying
Similarly, a function / : Zv —> R U {+00} with dom/ ^ 0 is semistrictly quasi M-convex if it satisfies the following: (SSQM) For x,y e dom/ and u € supp+(o; - y), there exists v 6 supp~ (x — y) satisfying
170
Chapter 6.
M-Convex Functions
Example 6.66. A quasi M-convex function arises from a nonlinear scaling of an M-convex function. For an M-convex function / : Zv —> R U {+00} and a function (p : R -» R U {+00}, define / : Zv -> R U {+00} by
Then / satisfies (QM) if if is nondecreasing and (SSQM) if
dz
\\ 0 by the nonexistence of arcs leaving W in Gv, we have z~(V) > p(W) — n5. Since dtp(v) < (n — 1)5 for every v 6 V, we have Z with O(n5 Iog2 M) function evaluations and arithmetic operations, where n = \V\ and M = max.{\p(X}\ X C V}. Proof. This can be derived from the properties listed in Proposition 10.22. /2, and go to SI. Procedure F\x+(p,D,rj) is identical to Fix" (p,D,n) except that step S4 is replaced with S4: If there exists w G U with x(w) > n2S, then return such a w. The correctness of the above procedures at the termination in step S4 is guaranteed by Proposition 10.23. As to the complexity we have the following as well as Proposition 10.22 (3)-(7). Proposition 10.25. The following statements hold true for Fix ± (p, D,rj). (1) The number of scaling phases is O(log2 n), where n = \U . (2)//
The frontier vertex is updated to this w' and the boundaries to b( =b\~Xw+ Xw1, 62 = 62 + Xw - Xw'- The flows remain the same: ip{ = ipi and ip'2 = y? 2 A crossover updates ((/PI, tp2,61, 62, w) with reference to another flow-boundary tuple (^,?2,6i,62, U ) °) with the same frontier vertex w° = w. The flow-boundary tuple is updated to
according to whether
or not. The condition (9.94) is maintained, since
276
Chapter 9. Network Flows
Under the additional conditions that we have We use crossovers to avoid cycling in generating the flow-boundary tuples. The generation of flow-boundary tuples consists of stages. Each stage consists of repeated applications of flow push and base exchange, possibly followed by an application of crossover. Denote by (ip\ , y>2 \b\ , 62 j w^) the flow-boundary tuple at the beginning of a stage and by (4 , v4 > b[ ,b% ,w^) (j = 2 , . . . , fc) the flowboundary tuples generated so far in the stage. We end the stage if either (a) w^ G supp~(yi — 7/2) or (b) u/ fc ) = u 7^ w/ 1 ); we are done in case (a), whereas in case (b) we go on to the next stage. If w^k> — w^ for some j with 1 < j < k — 1, we apply crossover to (^\^\bf\b(^\w^) with reference to (
9.6.
Network Duality
277
which shows (TRF[Zj) for g. Suppose that g(q) is finite for q = qi,q2- There exist (77i,Pi,7*i) and (772,252,7*2) such that
Here we have by the submodularity (SBF[Zj) of g and with by the convexity of ga (see Note 2.20). The submodularity (SBF[Z]) of g then follows because
(cf. (9.21)), whereas the assumed conjugacy implies
Therefore, we have
from which follows the weak duality Fix y with f ( y ) finite. By Theorem 9.16 (4) there exists (p*,q*,r*) such that
with 77* = — S(p*,q*,r*). This implies
Combining this with (9.97) shows g = /*. The proof of Theorem 9.26 is completed. It is mentioned that (1) follows from (2) and (3) with the aid of the conjugacy theorem (Theorem 8.12).
278
Chapter 9. Network Flows
Proof of Theorem 9.27 Because the functions are real valued, the infima in (9.81) and (9.82) may not be attained. The proof for Theorem 9.26 can be adapted to this case by introducing £ > 0 and letting s -> 0 as in Notes 2.19 and 2.20. Proof of Theorem 9.28 The augmenting flow argument for (1) suffers from a technical difficulty that the amount of augmenting flow may possibly converge to zero. To circumvent this difficulty we first prove (2) and (3) and then use the conjugacy (Theorem 8.4) to show (1). See Murota-Shioura [152] for details.
Bibliographical Notes The minimum cost flow problem treated in section 9.1 is one of the most fundamental problems in combinatorial optimization. For network flows, Ford-Fulkerson [53] is the classic, whereas Ahuja-Magnanti-Orlin [1] describes recent algorithmic developments; see also Cook-Cunningham-Pulleyblank-Schrijver [26], Du-Pardalos [43], Korte-Vygen [115], Lawler [119], and Nemhauser-Wolsey [167]. Thorough treatments of the network flow problem on the basis of convex analysis can be found in Iri [94] and Rockafellar [178]. The submodular flow problem was introduced by Edmonds-Giles [46] using crossing-submodular functions. The present form avoids crossing-submodular functions on the basis of the fact, due to Fujishige [61], that the base polyhedron defined by a crossing-submodular function can also be described by a submodular function. See Fujishige [65] for other equivalent neoflow problems, such as the independent flow (Fujishige [59]) and the polymatroidal flow (Hassin [87], Lawler-Martel [120], [121]). The M-convex submodular flow problem was introduced by Murota [142]. Section 9.3 is a collection of standard results on the submodular flow problem. Theorems 9.10 and 9.13 are taken from Fujishige [65] (Theorems 5.1 and 5.11, respectively), where the former is ascribed to Frank [56]. The optimality criterion by potentials for the M-convex submodular flow problem was established by Murota [142] for the integer-flow version (Theorem 9.16) and adapted to the real-valued case (Theorem 9.14) with the integrality assertion (Theorem 9.15) in Iwata-Shigeno [105] and Murota [147]. The optimality criterion by negative cycles (Theorem 9.20) was established by Murota [140], [142] for the integer-flow version and adapted to the real-valued case (Theorem 9.18) in Murota-Shioura [152]. Theorem 9.22 is in [140], [142]. Proposition 9.23 is a reformulation of the unique-max lemma due to Murota [135]. Proposition 9.25 is also from [135]; the proof technique using (9.80) originated in Fujishige [59]. Transformation by networks was found first for M-convex functions / s M [Z —> R] by Murota [137]; the proof given in section 9.6.2 is due to Shioura [188], [189]. Transformation of L-convex functions is stated explicitly in Murota [145]. The extension to polyhedral M-convex and L-convex functions is made in Murota-Shioura
9.6.
Network Duality
279
[152]. Theorems 9.26, 9.27, and 9.28 are explicit in Murota [147]. Induction of matroids through graphs is due to Perfect [171] (for bipartite graphs) and Brualdi [21]; see also Schrijver [183], Welsh [211], and White [213]. The alternative proof of the M^-convexity of a laminar convex function described in Note 9.31 is communicated by A. Shioura.
This page intentionally left blank
Chapter 10
Algorithms
Algorithmic aspects of M-convex and L-convex functions are discussed in this chapter. Three fundamental optimization problems tractable by efficient algorithms are (i) M-convex function minimization, which is a nonlinear extension of the minimumweight base problem for matroids; (ii) L-convex function minimization, which includes submodular set function minimization as a special case; and (iii) minimization/maximization in the Fenchel-type min-max duality, which is equivalent to the M-convex submodular flow problem.
10.1
Minimization of M-Convex Functions
Four kinds of algorithms for M-convex function minimization are described: the steepest descent algorithm, the steepest descent scaling algorithm, the domain reduction algorithm, and the domain reduction scaling algorithm. Throughout this section we assume that / : Zv —> RU {+00} is an M-convex function, n = \V\, and F is an upper bound on the time to evaluate /.
10.1.1
Steepest Descent Algorithm
The local characterization of global minimality for M-convex functions (Theorem 6.26) immediately suggests the following algorithm of steepest descent type. Steepest descent algorithm for an M-convex function / € Ai[Z —> R] SO: Find a vector x & dom /. SI: Find u, v G V (u ^ v) that minimize f(x — Xu + Xv)S2: If f ( x ) < f(x — Xu + Xv), then stop (x is a minimizer of /). S3: Set x := x — Xu + Xv and go to SI. Step SI can be done with n2 evaluations of function /. At the termination of the algorithm in step S2, x is a global minimizer by Theorem 6.26 (M-optimality criterion). The function value / decreases monotonically with iterations. This 281
282
Chapter 10.
Algorithms
property alone does not ensure finite termination in general, although it does if / is integer valued and bounded from below. Let us derive an upper bound on the number of iterations by considering the distance to the optimal solution rather than the function value. Proposition 10.1. If f has a unique minimizer, say, x*, the number of iterations in the steepest descent algorithm is bounded by \\x° — x*\\\/1, where x° denotes the initial vector found in step SO. Proof. Put x' = x — Xu + Xv m step S2. By Theorem 6.28 (M-minimizer cut), we have x*(u) < x(u) — 1 = x'(u) and x*(v) > x(v) + I = x'(v), which implies \\x' — x*||i — \\x — x* \\ — 2. Note that ||x° — x*\\i is an even integer. D When given an M-convex function /, which may have multiple minimizers, we consider a perturbation of / so that we can use Proposition 10.1. Assume now that the effective domain is bounded and denote its ^i-size by We arbitrarily fix a bijection (p : V —> {1,2,... ,n} to represent an ordering of the elements of V, put Vi = tp~l(i) for i = 1,... ,n, and define a vector p € Ry by p(vi) = el for i = 1,... ,n, where e > 0. The function /£ = f\p] is M-convex by Theorem 6.13 (3) and, for a sufficiently small e, it has a unique minimizer that is also a minimizer of /. Suppose that the steepest descent algorithm is applied to the perturbed function fe. Since fs(x - Xu + Xv) = f(x - Xu + Xv) + E"=i ^x(vi) e v(«) -)_ £v(v) ^ this amounts to employing a tie-breaking rule: where
in the case of multiple candidates in step SI of the steepest descent algorithm applied to /. With this tie-breaking rule we have the following complexity bound. Proposition 10.2. For an M-convex function f with finite K\ in (10.1), the number of iterations in the steepest descent algorithm with tie-breaking rule (10.2) is bounded by K\/2. Hence, if a vector in dom/ is given, the algorithm finds a minimizer of f in O(F • n2Ki) time. By Theorem 6.76 (quasi M-optimality criterion) and Theorem 6.77 (quasi Mminimizer cut), the steepest descent algorithm can also be used for minimizing quasi M-convex functions satisfying (SSQM^). Note 10.3. For integrally convex functions we have the local optimality criterion for global optimality (Theorem 3.21). This naturally suggests the following.
10.1.
Minimization of M-Convex Functions
283
Steepest descent algorithm for an integrally convex function / SO: Find a vector x € dom/. SI: Find disjoint Y,ZCV that minimize f(x — XY + Xz)S2: If f ( x ) < f(x — XY + X z ) , then stop (x is a minimizer of /). S3: Set x := x — XY + Xz and go to SI. The steepest descent algorithm for M-convex functions is a special case of this. It is emphasized that no efficient algorithm for step SI is available for general integrally convex functions. •
10.1.2
Steepest Descent Scaling Algorithm
Scaling is one of the fundamental general techniques in designing efficient algorithms. The proximity theorem for M-convex functions leads us to the following steepest descent scaling algorithm for M-convex function minimization. We assume that the effective domain is bounded and denote its £00-size by
Steepest descent scaling algorithm for an M-convex function / 6 M\L -f R]
SO: Find a vector x e dom/, and set a ~ 2^82(^00^n)^ B .= dom /. SI: Find an integer vector y that locally minimizes f(,,\ _ / f(x +ay) (x + ay&B), J(y> ~ { +00 (x + ayiB) in the sense of f ( y ) < f(y — Xu + Xv) (Vu, v & V) by the steepest descent algorithm of section 10.1.1 with initial vector 0 and set x := x + ay. S2: If a = 1, then stop (x is a minimizer of /).
S3: Set B := B n (y e Zv to SI.
\\y - x^
< (n - 1)(a - 1)} and a := a/2 and go
By the M-proximity theorem (Theorem 6.37 (1)), the set B always contains a global minimizer of / and, at the termination of the algorithm in step S2, x is a global minimizer by the M-optimality criterion (Theorem 6.26 (1)). The number of iterations is bounded by [Iog2(-ft'oo/4n.)] • Some remarks are in order concerning step SI. If the function / is such that the scaled function / remains M-convex, step SI can be done in O(F • n4) time by the steepest descent algorithm with tie-breaking rule (10.2). This time bound follows from Proposition 10.2 with K\ < 4ra2. For a general /, however, / is not necessarily M-convex (see Note 6.18) and no polynomial bound for step SI is guaranteed, although we have an obvious exponential time bound 0(F-(4n)"n 2 ). On the basis of Theorem 6.76 (quasi M-optimality criterion) and Theorem 6.78 (quasi M-proximity theorem), the steepest descent scaling algorithm can be adapted to the minimization of quasi M-convex functions satisfying (SSQM^).
284
10.1.3
Chapter 10. Algorithms
Domain Reduction Algorithm
The domain reduction algorithm is a kind of bisection method that searches for the minimum of an M-convex function by generating a sequence of nested subsets of the domain on the basis of the M-minimizer cut theorem (Theorem 6.28). For an M-convex function with bounded effective domain, the algorithm finds a minimizer in time polynomial in n and Iog2 KOC, where K^ is defined by (10.3). We introduce the following notations for a bounded nonempty set B C Zv:
The set B° is intended to represent the central part of B, i.e., the set of vectors of B lying away from the boundary. The set B° is nonempty if B is M-convex; see Proposition 10.6 below. Domain reduction algorithm for an M-convex function / S Ai[Z —*• R] SO: Set B :=dom/. SI: Find a vector x <E B°. S2: Find u, v € V (u ^ v) that minimize f(x — Xu + Xv)S3: If f ( x ) < f(x — Xu + Xv), then stop (x is a minimizer of /). S4: Set B := B D {y € Zv \ y(u) < x(u) - 1, y ( v ) > x(v) + 1} and go to SI. The vector x G B° in step SI can be found with O(n2log2K00) evaluations of / by the procedure to be described below. The set B forms a decreasing sequence of M-convex sets, which contain a minimizer of / because of the M-minimizer cut theorem (Theorem 6.28). Since x is taken from the central part of B, UB(W) — IB(W) for w e {u, v} decreases with a factor of (1 — ~) and hence the number of iterations is bounded by O(n2 Iog2 -ftToo)- The above algorithm, therefore, finds a minimizer of / with O(n 4 (log 2 Koo)2) evaluations of / provided that it is given a vector in dom /. Proposition 10.4. If a vector in dom / is given, the domain reduction algorithm finds a minimizer of an M-convex function f in O(F • n4(log2 Koc)2) time. It remains to show how to find x e B° in step SI when given a vector of B. For a vector y of an M-convex set B and two distinct elements u,v of V, the exchange capacity is defined by
which is a nonnegative integer representing the distance from y to the boundary of B in the direction of Xv - Xu- In the domain reduction algorithm, B is always an M-convex set and the exchange capacity can be computed by a binary search with [Iog2 KOO] evaluations of /. For x e B we define
10.1.
Minimization of M-Convex Functions
285
with an obvious observation that V° (x) = V if and only if x 6 B°. If V°(x) i- V, we can modify x to x' e B with the property \V°(x')\ > \V°(x)\ + 1 as follows. Take any u e V \V°(x) and assume x(u) > u°B(u); the other case with x(u) < i°B(u) can be treated in a similar manner. Putting {vi,V2, • • • ,vn-i} = V\ {u} and x0 = x, we define a sequence r c i , x 2 , . . . ,xn-i by Xi = Xi-i + oti(xVi - Xu) with
for i = 1 , 2 , . . . , n — 1 and put x' = xn-iProposition 10.5. V°(x') D V°(x) U {u}. Proof. The inclusion V°(x'} 2 V°(x) is obvious. To prove x'(u) = u°B(u) by contradiction, suppose x'(u) > u°B(u) and take x* & B°, where B° ^ 0 by Proposition 10.6 below. Since u & supp+(o;' — #*), it follows from (M-EXC[Z]) that x" = x' + Xvi — Xu € B and x'(vi) < x*(vi) < u°B(vi) for some Vi. Since Vi 6 supp+(x" — Xi) and supp~(o;" — Xi) = {u}, (M-EXC[Zj) implies Xi + \Vi — \u 6 B. But this contradicts the definition of x,. D The modification of x to x' described above can be done with n evaluations of the exchange capacity. Repeating such modifications at most n times we arrive at x with V°(x) = V. Thus, given a vector in B, we can find x e B° with at most n2 evaluations of the exchange capacity. We finally prove the nonemptiness of B°. Proposition 10.6. B° ^ 0 if B is an M-convex set. Proof. Let p 6 <S[Z] be the submodular function satisfying B = B(/o) n Zv and p be its Lovasz extension. Then we have IB(V) — p(V) — p(V\{v}} and UB(V) — p(v). We can assert the nonemptiness of B° by establishing
(see Theorem 3.8 in Pujishige [65]). We prove (i) here; a similar argument works for (ii). Fix X C V and put p = xx, Pv = 1 — Xv (v € X), and k — \X\. It follows from
that kp(V) = /3(fcl) = p(p + Y^vexPv) and
286
Chapter 10. Algorithms
With these identities we see
The last inequality holds true since
by the positive homogeneity and convexity of p. Hence follows i°B(X} < p ( X ) .
D
By Theorem 6.77 (quasi M-minimizer cut), the domain reduction algorithm can also be used for minimizing quasi M-convex functions satisfying (SSQM5^) provided that the effective domain is a bounded M-convex set.
10.1.4
Domain Reduction Scaling Algorithm
We present here the domain reduction scaling algorithm for M-convex function minimization, a combination of the idea of the domain reduction algorithm of section 10.1.3 with a scaling technique based on the theorem of M-minimizer cut with scaling (Theorem 6.39). The algorithm works with a pair (x, (.) of integer vectors, where x is the current solution and £ is a lower bound for an optimal solution. Specifically, two conditions
are maintained, where The algorithm consists of scaling phases parametrized (or labeled) by a nonnegative integer a, called the scaling factor, which is initially set to be sufficiently large and is decreased until it reaches unity. In each scaling phase with a fixed a, the pair (x, (.} is modified so that it satisfies an additional condition
At the end of the algorithm we have a = 1 and hence x = i by (10.6). This means S(l) n dom/ = {x}, since x(V) = y(V) for any y G dom/ by Proposition 6.1 and since x(V) < y(V) for any y e S(£) distinct from x. Furthermore, we see from the second condition in (10.5) that a; is a minimizer of /, since {x} — S(K) n dom/ D S(f)nargmin/^0. The outline of the algorithm reads as follows, where step SI for the a-scaling phase is described later and K^ is defined in (10.3).
10.1.
Minimization of M-Convex Functionsiions
287
Domain reduction scaling algorithm for an M-convex function
/ e M[Z -> R]
SO: SI: S2: S3:
Find a vector x € dom/ and set t := x - K^l, a := ^lo^K^/2n^. Modify (x,£) to meet (10.6) (a-scaling phase). If a = 1, then stop (x is a minimizer of /). Set a := a/2 and go to SI.
The a-scaling phase is now described. In view of (10.6) we employ a subset V of V such that
Initially, V* is set to V and then decreases monotonically to the empty set. ct-scaling phase for (x, (., a) SO: Set V := V. SI: If V — 0, then output (x,l) and stop. S2: Take any ueV*. S3: Find v e V that minimizes f(x + a(\v - x«))S4: If v = u or x(u) - a < l(u), then set l(u) := max[l(u), x(u) - (n - l)(a - 1)] and V := V \ {u} and go to SI. S5: Otherwise, set £(v) := max[l(v),x(v) + a — (n — l)(a — \)}, x := x + a(xv ~Xu) and V := V \ {v} and go to SI. As is easily seen, the first condition in (10.5) is maintained in steps S4 and S5. The second condition in (10.5) is also maintained by virtue of Theorem 6.39 (Mminimizer cut with scaling). The subset V is nonincreasing, although it may be that v $. V* in step S5, and then the operation V := V \ {v} is void and V* remains unchanged. Denote the initial value of (x,l) by (x°,l°). For each w € V the value of x(w) is decreased at most (x°(w) — l°(w))/a times before it is deleted from V*. Hence, the number of iterations in the a-scaling phase is bounded by \\x° — i°\\\/a. In particular, the a-scaling phase terminates with V = 0. The time complexity of the domain reduction scaling algorithm is given as follows, where it is assumed for simplicity that K^ is known. Proposition 10.7. // a vector in dom/ is given, the domain reduction scaling algorithm finds a minimizer of an M-convex function j in 0(F • n3log2(K00/n)) time. Proof. At the beginning of the a-scaling phase we have \\x°— (°\\\ < n(n— l)(2a—1) by (10.6). Since step S3 in the a-scaling phase can be done with n evaluations of /, the a-scaling phase terminates in O(F • n3) time. The number of scaling phases is equal to \\og2(Koc/2n)~\. D On the basis of Theorem 6.79 (quasi M-minimizer cut with scaling), the domain reduction scaling algorithm can be adapted to the minimization of quasi M-convex functions satisfying (SSQM^) provided that the effective domain is a bounded M-convex set.
288
Chapter 10. Algorithms
10.2
Minimization of Submodular Set Functions
The minimization of submodular set functions is one of the most fundamental problems in combinatorial optimization. In this section we deal with algorithms for minimizing submodular set functions, which we will use as an essential component in algorithms for L-convex functions.
10.2.1
Basic Framework
Let p : 2 —> R be a submodular set function,60 where p(0) = 0 and n = \V\. In discussing the efficiency or complexity of algorithms it is customary to categorize them into finite, pseudopolynomial, weakly polynomial and strongly polynomial algorithms. For our problem of minimizing p, a finite algorithm is trivial; we may evaluate p(X) for all subsets X to find the minimum. This takes O(F • 2") time, where F is an upper bound on the time to evaluate p. The complexity of an algorithm may depend on the complexity or size of p; if p is integer valued, V
often serves as a measure of the size of p. An algorithm for minimizing p is said to be (i) pseudopolynomial, (ii) weakly polynomial, or (iii) strongly polynomial, according as the total number of evaluations of p as well as other arithmetic operations involved is bounded by a polynomial in (i) n and M, (ii) n and Iog2 M, or (iii) n alone. Our objective in this section is to describe two strongly polynomial algorithms for minimizing p. Let
be the base polyhedron associated with p. Recall that a point in B(/o) is called a base and an extreme point of B(p) is an extreme base. For any base x and any subset X we obviously have
where x~ is the vector in R^ defined by x~(v) = min(0,x(v)) for v e V. The inequalities are tight for some x and X, as follows. Proposition 10.8. For a submodular set function p : 2V —-> R, we have
If p is integer valued, the maximizer x can be chosen to be an integer vector. Proof. Although this is an easy consequence of Edmonds's intersection theorem (Theorem 4.18) with pi = p and p2 = 0, a direct proof is given here. Let x be a 60
Note that we assume p to be finite valued for all subsets. An adaptation to the general case p : 2V —> RU {+00} is explained in Note 10.14.
10.2.
Minimization of Submodular Set Functions
289
maximizer on the left-hand side. For any u € supp~(z) and v €. supp + (x), there exists a subset Xuv such that u 6 Xuv C V \ {v} and x(Xuv) — p(Xuv). Put X = U u6 sup P -(x) a6,Upp+(a,) Xuv. We have x(X) = p(X) by (4.23) and x'(V) = x(X) since supp~(x) C X and supp+(a;) C V \ X.. The integrality assertion can be established by the same argument starting with an integral base x that maximizes x~(V) over all integral bases. D The min-max relation (10.11) shows that we can demonstrate the optimality of a subset X by finding a base x with x~(V) — p(X). But how can we verify that a vector x belongs to B(p)? By definition, x e B(p) if and only if mmx(p(X) — x(X)) = p(V) - x(V) = 0. Thus, testing for membership in B(p) for an arbitrary x seems to need a submodular function minimization procedure. To circumvent this difficulty, we recall from Note 4.10 that we can generate an extreme base by the greedy algorithm. Let L = (vi,v<2, • • •, vn) be a linear ordering of V and define L(VJ) = {i>i, t>2, • • •, vj} for j — 1,...,n. Then the extreme base y associated with L is given by Any base x can be represented as a convex combination of a number of extreme bases, say, {yi \ i £ I}, as
where we may assume |J| < n by the Caratheodory theorem. Combining (10.12) and (10.13) shows that any base can be represented by a list of linear orderings {Li | i € /} (that generate {j/j | i 6 /}) and coefficients of the convex combination {A; | i e /}. With this representation of x we can be sure that x is a member of B(p). For u, v € V and i e I we use the notation
where w ^ v means w -<, v or w = v. The following proposition gives a sufficient condition for optimality in terms of the linear orderings {Li | i € /}. Proposition 10.9. Let x be a base represented as (10.13) with {(Lj,Aj) i e 1} and W be a subset of V. (1) //supp-(z) C W and supp+(x) CV\W, then x~(V) = x(W). (2) Ifu^v for every u e W, v e V \ W, and i G /, then x(W) = p(W). (3) If the conditions in (1) and (2) are satisfied, x and W are optimal in (10.11). Proof. (1) is obvious. By (10.12) the condition in (2) implies p(W) = yi(W) for every i € /. Then x(W) = Eie/^W = P(W)- (3) follows from (1), (2), and (10.10). D
290
Chapter 10. Algorithms
We are thus led to a basic algorithmic framework: 1. We maintain (and update) a number of linear orderings {Li i € /}, together with the associated extreme bases {yi \ i 6 /} and the coefficients of convex combination {A^ i e /}, to represent a base x. 2. We terminate when the conditions in Proposition 10.9 are satisfied. Two strongly polynomial algorithms using this framework are described in subsequent sections. Note 10.10. Here is a brief historical account of submodular function minimization. Its importance seems to have been recognized around 1970 by J. Edmonds [44] and others. The first polynomial algorithm was given by M. Grotschel, L. Lovasz, and A. Schrijver—weakly polynomial in 1981 [82], and strongly polynomial in 1988 [83]. These algorithms, however, are based on the ellipsoid method and, as such, are not so much combinatorial as geometric. Efforts for a combinatorial polynomial algorithm have been continued with major contributions made by W. H. Cunningham and others [15], [28], [29], who showed the basic framework above as well as a combinatorial pseudopolynomial algorithm for submodular function minimization. In 1994, extending the min-cut algorithm of Nagamochi-Ibaraki [163], M. Queyranne [172] came up with a combinatorial algorithm for symmetric submodular function minimization, which is to minimize over nonempty proper subsets a submodular function p such that p(X) = p(V \ X) for all X C V. Combinatorial strongly polynomial algorithms for general submodular functions were found, independently, in the summer of 1999 by two groups, S. Iwata, L. Fleischer, and S. Fujishige [101], [102] and A. Schrijver [182]. Both of these follow Cunningham's framework, but they are significantly distinct in technical aspects. Subsequently, a new problem was recognized by Schrijver. These two algorithms are certainly combinatorial, but they rely on arithmetic operations (division, in particular) in computing the coefficients of convex combination in (10.13). The question posed by Schrijver is as follows: Is it possible to design a fully combinatorial strongly polynomial algorithm that is free from division and relies only on addition, subtraction, and comparison? This was answered in the affirmative by Iwata [99] in the fall of 2000. • Note 10.11. Because the minimizers form a ring family (see Note 4.8), there exists a unique minimal minimizer as well as a unique maximal minimizer of a submodular set function p : 2V —> R. Given an optimal base x with the representation x = Sie/^il/i m (10.13), we can compute the minimal and maximal minimizers in strongly polynomial time as follows. With the notation T>(x) for the family of tight sets at x, introduced in (4.22) of Note 4.9, we have a representation
for the family of the minimizers of p. Noting that T>(x) is a ring family, let Gx = (V,AX) be the directed graph associated with T>(x), as defined by (4.20) in Note
10.2.
Minimization of Submodular Set Functions
291
4.7. This is equivalent to saying that (u, v) € Ax if and only if v G dep(x, u), where dep(x,w) means the smallest tight set at x that contains u. Then the minimal minimizer can be identified as the set of vertices reachable from supp~ (x) in Gx and the maximal minimizer as the complement of the set of vertices reachable to supp+ (x) in Gx. Moreover, the graph Gx enables us to enumerate all the minimizers. By (10.13) we have
Since each yi is an extreme base, we can easily compute dep(yi,u). For each u e V, we start with D := V and update D to D \ {v} as long as D \ {v} € T^(yi) for some v £ D \ {u}; we obtain D = dep(yi,u) at the termination. We can thus compute dep(yi, u) with O(n 2 ) evaluations of p. The number of function evaluations can be reduced to O(n) if a linear ordering Lj = (vi,vz,... ,vn) generating yi is also available; assuming u = Vk, start with D = {vi,f2> • • • ,Vk-i} and, for j = k - 1, k - 2 , . . . , 1, update D to D \ {vj} if D \ {vj} e £>(&). Therefore, the graph Gx can be constructed with O(n 3 |/|) or 0(n 2 |/|) evaluations of function p, where it is reasonable to assume |/| < n. • Note 10.12. The minimal minimizer of a submodular set function p : 1V —> R can also be computed using any submodular function minimization algorithm n + I times. Let X be a minimizer of p. For each v e X, compute a minimizer Yv of a submodular set function pv : 2X\^ —> R, the restriction of p to X \ {v}, defined by pv(Y) = p(Y) for Y C X \ {v}. Then the minimal minimizer of p is given by {v G X | p(Yv) > p ( X ) } , since p(Yv) > p(X) if v is contained in the minimal minimizer and p(Yv) = p(X) if not. The maximal minimizer can be computed similarly. • Note 10.13. An alternative way to find the minimal minimizer of a submodular set function p : 2V —> R is to introduce a penalty term to represent the size of a subset and to minimize a modified submodular set function p(X) = p(X) + s\X\ with a sufficiently small positive parameter e. If p is integer valued, e = l/(n + 1) is a valid choice. The maximal minimizer can be computed similarly. • Note 10.14. It has been assumed that the submodular function p is finite valued for all subsets. This assumption is not restrictive but for convenience of description. Let p 6 <S[R] be a submodular set function on V taking values in RU{+oo}; T> = domp is a ring family with {0, V} C T>. For v € V we denote by Mv the smallest member of T> containing v and by Nv the largest member of T> not containing v. For X C V we denote by X the smallest member of T> including X. We assume that we can compute Mv for each v & V efficiently, say, in time polynomial in n. Then we can compute X and Nv by
292
Chapter 10. Algorithms
Let us assume, without loss of generality, that the length of a maximal chain of V is equal to n = \V\. Consider now a set function ~p : 2V —> R denned by
with c e R^ given by
As is shown below, (i) p is a finite-valued submodular function and (ii) X £ arg min p implies X e arg min p. Thus we can minimize p via the minimization of p. Proof of (i): p is obviously finite valued. If X e V, v £ X, and Y = X U {v} e T>, we have YL)NV = NVU {v} and Y D Nv = X and, therefore,
This means that n(X) = p(X}-\-c(X) is nondecreasing on T>. Putting Ji(X) — n(X) for X C V and noting X U F = XUY and X n F D X n F, we see
which shows the submodularity of /I and hence that of p. Proof of (ii): For any Y e D we have p(T) < p(T) + c(X) - c(X) = p(X) < p(Y) = p(Y). m Note 10.15. The method in Note 10.14 can be used to minimize a submodular function defined on a (finite) distributive lattice. By a lattice we mean a tuple (S, V, A) of a nonempty set S and two binary operations V and A on S1 such that
for any a, b, c €. S. A lattice (S, V , A ) is a distributive lattice if, in addition, the distributive law
holds true. A ring family T> is a typical distributive lattice, where (S, V, A) = (Z>, U , n ) . The converse is essentially true: any distributive lattice (S, V , A ) can be represented in the form of a ring family (Birkhoff's representation theorem). The size of the underlying set of the ring family is equal to the length of a maximal chain of S. A function p : S —> R defined on a distributive lattice (S, V, A) is said to be submodular if it satisfies
10.2.
Minimization of Submodular Set Functions
293
Thus, with an appropriate representation of (S, V, A), a submodular function p on S can be minimized by using the method in Note 10.14. • Note 10.16. Maximizing a submodular set function is a difficult task in general. It is known that no polynomial algorithm exists for it (and this statement is independent of the P ^ NP conjecture); see Jensen-Korte [106] and Lovasz [122], [123]. In this context, M^-concave functions on {0, l}-vectors form a tractable subclass of submodular set functions. Recall that an M^-concave function is submodular (Theorem 6.19) and that it can be maximized efficiently by algorithms in section 10.1. •
10.2.2
Schrijver's Algorithm
We explain here Schrijver's strongly polynomial algorithm for submodular function minimization. This algorithm achieves strong polynomiality using a distance labeling with an ingenious lexicographic rule. Following the basic framework introduced in section 10.2.1, the algorithm employs the representation of a base in terms of a convex combination of extreme bases associated with linear orderings. Given {(I/i,Ai) | i € /}, the algorithm constructs a directed graph G = (V, A) with arc set
(see (10.14) for the notation -
294
Chapter 10. Algorithms
Index the elements of V so that Lk = (vi, • - •, vn) and assume vp = s. Then we have vp+a = t and ( s , t } ^ k = {vp+i,...,vp+a}. For j = l , . . . , a , consider a linear ordering
which is obtained from Lk by moving vp+j to the position just before vp = s, and let Zj be the extreme base associated with L*. Proposition 10.17. For some S > 0, j/fc + 6(xt ~ Xs) can be represented as a convex combination of {zj \ j = 1 , . . . , a}. Proof. Put Vh = Lk(vh) = {vi,..., vh} for h = 1,..., n and VQ = 0. By (10.12) we have
and, therefore,
where the inequalities follow from submodularity; for instance, for h = p+j, we have
in which (Vp-i U {vp+j}) U Vp+j-i = Vp+j and (Vp-i U {vp+j}) n Vp+j-! = Vp-!. The sign pattern of (10.18), as well as that of (xt~Xs)(vh), for h with p < h < p+j looks like:
Note also that each row sum is equal to zero since Zj(V) = yk(V). If all the diagonal entries marked by @ are strictly positive, we can represent xt ~ Xs as a nonnegative combination of {zj —y^ \ j = 1 , . . . , a} with a positive coefficient for j — a; namely,
10.2.
Minimization of Submodular Set Functions
295
X t ~ X s = E°=i »j(zi ~ yk) with //j > 0 (j = 1,..., a - 1) and p,a > 0. Then the claim is true for 5 = 1/($3?=1 Mj)- ^ a diagonal entry, say, in the j'oth row, vanishes, then Zj0 = yk and the claim is true for 6 = 0. D Define x = x + \k$(Xt — Xa)- This vector can be represented as a convex combination of Y" = {y, | i € / \ {fc}} U {zj \ j = 1,..., a} by Proposition 10.17 and (10.13). Let x' be the point on the line segment connecting x and x that is closest to x with the t-component x'(t) < 0. This means
Note that x' can be represented as a convex combination of Y U {yk} and, moreover, {yk} can be dispensed with if x'(t) < 0. By a variant of Gaussian elimination we can obtain a convex combination representation of x' using at most n vectors from Y U {yk}- We update {(Li, A,) | i e /} according to this representation. Since \Y\ + 1 < 2n, step S4 can be done with O(n3) arithmetic operations. Proposition 10.18. The number of iterations in Schrijver's algorithm is bounded by O(n 6 ). Hence, Schrijver's algorithm finds a minimizer of a submodular set function p : 2V —> R with O(n8) function evaluations and 0(n 9 ) arithmetic operations, where n = \V\. Proof. Denote by 0 the number of indices i £ I such that |(s,t]^J = a. Let x',d',A',P',N',t',s',a',/3' be the objects x,d,A,P,N,t,s,a,/3 in the next iteration. We first observe that a new arc appears only if it connects two vertices lying between s and t with respect to -<&: (a) For each arc (v, w) e A' \ A we have s -
is lexicographically
Proof of (b): Note that P' C P. If (b) fails, there exists an arc (v, w)eA'\A with d(w) > d(v) + 2. By (a) we have s -
296
Chapter 10. Algorithms
j — 1,..., a, (s, £]_<• is a proper subset of (s, t]->k. This implies a' < a. If a' = a, then /3' < (3, since x'(t) = x'(t') < 0 and L^ disappears in the update. Hence (c). It follows from (c) that d(v) increases for some v € V in O(n 4 ) iterations because each of d(t), t, s, a, (3 is bounded by n and there are at most n pairs (d(t),t) if d does not change. For each v € V, d(v) can increase at most n times. Therefore, the total number of iterations is bounded by O(n 6 ). D Note 10.19. A more detailed analysis of Vygen [208] yields an improved bound of O(n 5 ) on the number of iterations in Schrijver's algorithm. •
10.2.3
Iwata-Fleischer-Fujishige's Algorithm
We explain here Iwata-Fleischer-Fujishige's strongly polynomial algorithm for submodular function minimization. While sharing the basic framework of section 10.2.1, this algorithm differs substantially from Schrijver's in that it is based on a scaling technique rather than distance labeling. Weakly Polynomial Scaling Algorithm
We start with a scaling algorithm for minimizing a submodular set function p : 2V —> R. The algorithm is weakly polynomial for integer-valued p. It is emphasized that the value of M in (10.8) need not be computed. Recall from Proposition 10.8 that the problem dual to minimizing p is to maximize x~(V) over x e B(/o). To add flexibility in solving this maximization problem we introduce a scaling parameter 6 > 0 to relax (or enlarge) the feasible region B(p) to B(p + Kg), where
The function Kg is submodular and therefore B(p + K,j) — B(p) + B(K^) by Theorem 4.23 (1). For a concrete representation of B(K^) we observe that Kg is the cut capacity function associated with a complete directed graph G = (V, A), where
and the arc capacities are all equal to 6; indeed, Kg coincides with K in (9.16) with c(a) = 8 and c(a) = 0 for every arc a € A. By a S-feasible flow we mean a function if : A —> R such that for each (u,v) € A we have (i) 0 <
(10.21)
The algorithm consists of scaling phases, each of which corresponds to a fixed parameter value 5. We start with an arbitrary linear ordering, the extreme base x associated with it, zero flow (p = 0, and
10.2.
Minimization of Submodular Set Functions
297
where x+ is the vector in Rv defined by x+(v) = m&x(Q,x(v)) for v € V. In each scaling phase, we construct an approximate solution to (10.21) from a given pair of a base x and a ^-feasible flow
Proof. Since S C W C V \ T, we have z(v) < 6 for every v £ W and z(v) > —5 for every v € V \ W. Therefore, Since x(W) = p(W] by the nonexistence of active triples and Proposition 10.9 (2) and d
298
Chapter 10. Algorithms
With 5 < A/n 2 we have x~(V) > p(W) - n25 > p(W) - A, whereas x~(V) < p(Y) for all Y C V by (10.10). Hence W is a minimizer of p. D On the basis of Proposition 10.20 above we terminate the scaling phase if neither augmenting path nor active triple exists. Otherwise, while keeping z invariant, we aim at "improving the situation" by either 1. eliminating an active triple or 2. enlarging the reachable set W. With a view to eliminating an active triple (i, u, v) we modify Li by swapping u and v in Li; denote the old pair (L/i,yi) by (Lk,yk) with a new index fc. The extreme base associated with the updated Li is given by yi — yk + /3(Xu — Xv) with
(see (10.12)). Defining a = mm((f>(u,v),Xi(3)
let us modify x and ip by setting
Then z = x + dip is invariant and ip remains ^-feasible. The updated x is equal to
which is a convex combination of {yj j € / U {k}}. In the saturating case where a = \i/3, the old extreme base yk disappears from (10.25). Since u precedes v in the new L^, the active triple (i,u,v) is successfully eliminated, whereas the size of the index set / remains the same. In the nonsaturating case where a < Aj/3, the old extreme base y^ remains and the size of I increases by one. Nevertheless, the situation is somewhat improved; namely, the reachable set W is enlarged to contain v as a result of (p(u, v) = 0 for the updated flow (p. The above task is done by the procedure Double-Exchange(z,M, v) below. Procedure Double-Exchange(i,«, v) SI: Set /3 := p(Li(u) \ {v}} - p(Lt(u)) + yi(v), a := mm(^(u, v), A;/3). S2: If a < \i/3, then let k be a new index and set / := 7 U {k}, Afc := A* - a//?, A* := a/j3, yk := j/», Lk := Lt. S3: Set ^ := yi + j3(\u - Xv), x := x + a(xu ~ Xv),
10.2.
Minimization of Submodular Set Functions
299
IFF scaling algorithm for submodular function minimization
SO: Take any linear ordering L\ and let y\ be the associated extreme base. If 3/i~(V) = 0, then output V as a minimizer and stop. If l / i ( V ) = 0, then output 0 as a minimizer and stop. Set / := {!}, A! := 1, x := j/i, tp := 0, S := mm{x+(V), \x~ (V)\} / H* . SI: Let W be the set of vertices reachable from S in Gv. S2: If W n T ^ 0, then let P be a ^-augmenting path, apply Augment(<£>, P) and Reduce(x,I), and go to SI. S3: If there exists an active triple, then apply Double-Exchange to an active triple (i,u,v) and go to SI. S4: If S < A/n 2 , then output W as a minimizer and stop. S5: Apply Reduce(o;,/), set 5 := 5/2, and
D
Proposition 10.22.
(1) The number of scaling phases is O(log 2 (M/A)). (2) The first scaling phase calls Augment O(n 2 ) times. (3) A subsequent scaling phase calls Augment O(n 2 ) times. (4) Between calls to Augment, there are at most n — 1 calls to nonsaturating Double-Exchange. (5) Between calls to Augment, there are at most 2n3 calls to saturating DoubleExchange. (6) We always have \I\ < In. (7) Reduce(a;, /) with \I\ < 2n can be done in O(n 3 ) arithmetic operations. Proof. (1) We have 6 < M/n2 in step SO, since x+(V) = x(X) < p(X) < M for X = supp+(:c). The number of scaling phases is bounded by log 2 ((M/n 2 )/(A/n 2 )) = log2(M/A). (2) Let x denote the initial base in step SO. Then z (V) = x (V) at the beginning of the scaling phase. Throughout the scaling phase we have z~(V) < z(V) = x(V) as well as z~(V) < 0. Since Augment increases z~(V) by <5, the number of calls to Augment is bounded by
300
Chapter 10.
Algorithms
(3) At the beginning of a subsequent scaling phase, we have z~(V) > p(W) —nS by Proposition 10.20, where z = x + dtp with (p = 2ip and 6 — 26. Since
this implies that z~(V) > p(W) — 2n8 — «2<5/4 at the beginning of the scaling phase. Throughout the scaling phase we have
Therefore, the number of calls to Augment is bounded by (2n5 + n25/2)/S = 2n + n2/2. (4) Each nonsaturating Double-Exchange adds a new element to W. (5), (6) A call to Reduce results in |/| < n. A new index is added to / only in a nonsaturating Double-Exchange. By (4), |/| grows to at most 2n — 1. Hence, the number of triples (i,u,v) is bounded by 2n3. (7) Reduce can be performed by a variant of Gaussian elimination. D The following is a key property of the scaling algorithm that we make use of in designing a strongly polynomial algorithm. Recall that a scaling phase ends when the algorithm reaches step S4. Proposition 10.23. At the end of a scaling phase with parameter S, the following hold true. (1) If x(w) < —n28, then w is contained in every minimizer of p. (2) // x(w) > n2S, then w is not contained in any minimizer of p. Proof. We have x~(V) > p(W) — n2S by Proposition 10.20, whereas, for any minimizer X of p, we have p(W) > p(X) > x(X) > x ~ ( X ) . Hence, x~(V) > x ~ ( X ) - n25. Therefore, if x(w) < —n2S, then w e X. On the other hand,
Therefore, if x(w] > n2S, then w £ X.
D
Strongly Polynomial Fixing Algorithm
Using the scaling algorithm as a subroutine, we can devise a strongly polynomial algorithm for submodular function minimization. The strongly polynomial algorithm, which we call the IFF fixing algorithm, exploits two fundamental facts: • The minimizers of p form a ring family (see Note 4.8).
10.2.
Minimization of Submodular Set Functions
301
• A ring family can be represented as the set of ideals of a directed graph (see Note 4.7). Let D° be the directed graph representing the family T>° of minimizers of p. This means that W C V is a minimizer of p if and only if it is an ideal of D° such that min£>° C W C max 2}°. The algorithm aims at constructing the graph by identifying arcs of D° or elements of (mini?0) U (V \ max£>°) one by one with the aid of the scaling algorithm. To be more specific, we maintain an acyclic graph D = (U, F) and two disjoint subsets Z and H of V such that • Z is included in every minimizer of p, i.e., Z C min£>°; • H is disjoint from any minimizer of p, i.e., H C V \ maxX>°; • each u € U corresponds to a nonempty subset, say, F(u), of V, and (F(u) | u e U} is a partition of V \ (Z U H); • for each u & U and any minimizer W of p, either F(u) C W or F(w) f~l W = 0; • an arc (u, w) € F implies that every minimizer of p including T(u) includes F(w;) Using the notation T(Y) = Uusr ^(u) f°r ^ — U, we define a function p : 2U —»• Rby It is easy to verify that • p is submodular; • a subset W of V is a minimizer of p if and only if W = T(Y) U Z for a minimizer V C U of /5; • an arc (u, w) G F implies that every minimizer of p containing u contains w; i.e., a minimizer of p is an ideal of D. The algorithm consists of iterations. Initially we set U := V, Z := 0, H := 0, and F :— 0. At the beginning of each iteration, we compute
where R(u) denotes the set of vertices reachable from u £ U in D. If rj < 0, we are done by Proposition 10.24 below. Otherwise, we either enlarge Z Li H or add an arc to D, where directed cycles that may possibly arise in this modification are contracted to a single vertex; the partition F of V \ (Z U H) is modified accordingly. Proposition 10.24. // 77 < 0, then V \ H is the maximal minimizer of p. Proof. Let Y be the unique maximal minimizer of p. If Y ^ U, there is an element u £ U \Y such that Y U {u} is an ideal of D. By Y U {u} 2 R(u) and the submodularity of p, we have
302
Chapter 10. Algorithms
which contradicts the definition of Y. Thus, U is the maximal minimizer of p and hence F(t/) U Z = V \ H is the maximal minimizer of p. D Suppose that 77 > 0 and let u G U be the vertex that attains the maximum in (10.26). Then and we have at least one of the following three cases: (i) p(U) > 77/8, (ii) p(R(u) \ {u}) < -77/3, or (iii) p(R(u)) - p(U) > 77/8. Case (i): If p(U) > 77/8, we invoke a procedure Fix + (p, D, 77), described below, to find an element w 6 U that is not contained in any minimizer of p. Since T(w) cannot be included in any minimizer of p, we add T(w) to H and delete w from D. Case (ii): If p(R(u) \ {u}) < — 77/8, we invoke another procedure Fix~(/5, D, 77), described below, to find an element w € U that is contained in every minimizer of p. Since T(w) must be included in every minimizer of p, we add T(w) to Z and delete w from D. Case (iii): If p(R(u)) — p(U) > 77/8, we consider the contraction of p by R(u), which is a submodular function p* on U \ R(u) defined by
and find an element w G U \ R(u) that is contained in every minimizer of p*. As explained below, we can do this by applying Fix" to (p*,D*,/7), where D* means the subgraph of D induced on the vertex set U \ R(u). A subset X C. U \ R(u) is a minimizer of p* if and only if X U R(u) minimizes p over subsets of U containing R(u). Therefore, if a minimizer of p containing u exists, then it must contain w. Equivalently, if a minimizer of p including T(u) exists, then it must include F(u>). Accordingly, we add a new arc (u, w) to F, where the arc (u, w) is new because w ^ R(u). If the added arc yields directed cycles, we contract the cycles to a single vertex, with corresponding modifications of U and F. Thus, in each iteration with 77 > 0, we either enlarge Z U H or add a new arc to D. Therefore, after at most r? iterations, we can terminate the algorithm with 77 < 0 when we have a minimizer of p by Proposition 10.24. The procedures Fix" (p, D, 77) and Fix + (p, D,rj) are as follows. Given a submodular function p : 2U —> R, an acyclic graph D — (U,F), and a positive real number 77 such that
the procedure F\x~(p,D,r]) finds an element w & U that is contained in every minimizer of p. Similarly, Fix+(/5, D, 77) finds an element w G U that is not contained in any minimizer of p when The procedures F\x.~(p,D,r]) and Fix + (/5, D,rj) are the same as the IFF scaling algorithm except that they start with 6 = 77 and a linear extension of the partial order represented by D and return w in step S4. We put h = \U\.
10.2.
Minimization of Submodular Set Functions
303
Procedure Fix~(/5, D, 77) SO: Take any linear extension LI of the partial order represented by D and let yi be the associated extreme base. Set / := {!}, A! := 1, x :— yi,
then the first scaling phase calls Augment O(n) times. Proof. (1) Assume 8 < n/(3n3). By (10.28) we have x(U) = p(U) > ry/3 > hz5 and hence x(w) > n26 for some w & U. Therefore, the number of scaling phases in Fix+ is bounded by [Iog2(3n3)] = O(log 2 n). For Y in (10.27), we have x(Y) < p(Y) < —rj/3 < -n38 and hence x(w) < -n28 for some w G Y. Therefore, the number of scaling phases in Fix" is bounded by O(log2 n). (2) Let x denote the initial base in step SO. By the proof of Proposition 10.22 (2), the number of calls to Augment is bounded by x+(U)/S, whereas x+(U) < nrj by (10.29). Since S — 77, the number of calls to Augment is bounded by n. D The applications of Fix* in the IFF fixing algorithm are legitimate. Proposition 10.26. Let r? be defined by (10.26). (1) Conditions (10.28) and (10.29) are satisfied by (p,D,r)) in Case (i). (2) Conditions (10.27) and (10.29) are satisfied by (p,D,n) in Case (ii). (3) Conditions (10.27) and (10.29) are satisfied by (p*,D#,rj) in Case (in). Proof. In Case (i), (10.28) is obviously satisfied. Condition (10.27) is satisfied with Y = R(u) \ {w} in Case (ii) and Y = U \ R(u) in Case (iii). To show (10.29) for
304
Chapter 10. Algorithms
(p,D,rj), let y be an extreme base generated by a linear extension of the partial order of D. For each u € U we have y(u) = p(Y) — p(Y \ {u}) for some Y D R(u), whereas
by the submodularity of p and the definition of n. This proves (10.29) for (p, D, 77). Finally, for each u e U \ R(u), put J?*(u) = R(u) \ R(u) and observe
This shows (10.29) for (p,,D*,ri).
D
We are now in the position to assert the correctness and the strong polynomiality of the IFF fixing algorithm. Proposition 10.27. The IFF fixing algorithm finds a minimizer of a submodular set function p : 2V —+ R with O(n 7 log 2 n) function evaluations and arithmetic operations, where n = |V|. Proof. This follows from Proposition 10.25 and Proposition 10.22 (3)-(7).
D
Finally, we note that the maximal minimizer is found. Proposition 10.28. The IFF fixing algorithm finds the maximal minimizer of p. Proof. This follows from Proposition 10.24.
D
Note 10.29. For minimization of a submodular set function p : 2V —> R U {+00} defined effectively on a general ring family, the IFF scaling/fixing algorithm can be applied to the associated finite-valued submodular function ~p in Note 10.14. Alternatively, the IFF scaling/fixing algorithm can be tailored to this general case if the ring family is represented as the set of ideals of a directed graph (V, E). The min-max relation (10.11) in Proposition 10.8 holds true in this general case. The representation (10.13) of a base x as a convex combination of extreme bases y, (i € /) should be augmented by an additional term 9£ as
where 9£ is the boundary of a nonnegative flow £ : E —> R+. Then we have
10.3.
Minimization of L-Convex Functions
305
where tp is a flow in the complete graph on V representing the superposition of £ and (p. It is possible to design an algorithm that finds the minimum of p by maintaining the extreme bases and the flow tp. See Iwata [99] for more details. •
10.3
Minimization of L-Convex Functions
Three kinds of algorithms for L-convex function minimization are described: the steepest descent algorithm, the steepest descent scaling algorithm, and the reduction to submodular function minimization on a distributive lattice. All of them depend heavily on the algorithms for submodular function minimization in section 10.2. Throughout this section g : Zv —> R U {+00} denotes an L- or L''-convex function with \V\ = n. For an L-convex function g, it is assumed that
since otherwise g does not have a minimum.
10.3.1
Steepest Descent Algorithm
The local characterization of global minimality for L-convex functions (Theorem 7.14) naturally leads to the following steepest descent algorithm. Steepest descent algorithm for an L-convex function g € £[Z —» R] SO: Find a vector p e domg. Si: Find X C V that minimizes g(p + xx)S2: If g(p) < g(p + X x ) , then stop (p is a minimizer of g). S3: Set p := p + xx and go to SI. Step SI amounts to minimizing a set function
over all subsets X of V. As a consequence of the submodularity of g, pp is submodular and can be minimized in strongly polynomial time by the algorithms in section 10.2. At the termination in step S2, p is & global minimizer by Theorem 7.14 (1) (L-optimality criterion). The function value g decreases monotonically with iterations. This property alone does not ensure finite termination in general, but it does if g is integer valued and bounded from below. We introduce a tie-breaking rule in step SI:
Thus, we can guarantee an upper bound on the number of iterations. Let p° be the initial vector found in step SO. If g has a minimizer at all, it has a minimizer p* satisfying p° < p* by (10.31). Let p* denote the smallest of such minimizers, which exists since p* A q* € argming for p*, q* € argmin .
306
Chapter 10. Algorithms
Proposition 10.30. In step SI, p < p* implies p + xx < P*• Hence the number of iterations is bounded by \\p° - p*\\iProof. Put Y = {v e V | p(v) — P*(v)} and p' = p + xx- By submodularity we have whereas g(p*) < g(p*Vp') since p* is aminimizer of g. Hence g(p') > g(p*/\p'). Here we have p' = p + Xx and p* A p' — p + Xx\Y, whereas X is the minimal minimizer by the tie-breaking rule (10.33). This means that X \ Y = X; i.e., X n Y = 0. Therefore, p' = p + xx < P*- D It is easy to find the minimal minimizer of pp using the existing algorithms for submodular set function minimization (see Notes 10.11, 10.12, and 10.13 and Proposition 10.28). Assuming that the minimal minimizer of a submodular set function can be computed with O(
where it is noted that domg itself is unbounded by (10.31). Proposition 10.31. For an L-convex function g with finite K\, the number of iterations in the steepest descent algorithm with tie-breaking rule (10.33) is bounded by KI . Hence, if a vector in dom g is given, the algorithm finds a minimizer of g in O((a(n)F + r(n))Ki) time. Proof. We have \\p° — p*||i < KI since p°(v) = p*(v) for some v e V. Then the claim follows from Proposition 10.30. D The steepest descent algorithm can be adapted to L''-convex functions. Let g be an L''-convex function and recall from (7.2) that it is associated with an L-convex function g as The steepest descent algorithm above applied to this L-convex function g yields the following algorithm for the L''-convex function g. Steepest descent algorithm for an L^-convex function g G £&[Z —>• R] SO: Find a vector p e doing. SI: Find e € {1, —1} and X C V that minimize g(p + £Xx)S2: If g(p) < g(p + exx), then stop (p is a minimizer of g). S3: Set p := p + sxx and go to SI. Step SI amounts to minimizing a pair of submodular set functions
10.3.
Minimization of L-Convex Functions
307
Let X+ be the minimal minimizer of p+ and X~ be the maximal minimizer of p~. The tie-breaking rule in step SI above reads
This is a translation of the tie-breaking rule (10.33) for g in (10.35) through the correspondence
where p = (0,p) & Z x Zv. Since (l,Xv\x-) cannot be minimal in the presence of (0, Xx+); we choose (1, X+) in the case of min/9+ = min/9~. At the termination in step S2, p is a global minimizer by Theorem 7.14 (2) (L-optimality criterion). In view of the complexity bound given in Proposition 10.31 we will derive a bound on the size of dom g in terms of the size of dom g. Let K\ (g) be denned by (10.34) for g. The li-size and ^-size of doing are denoted, respectively, by
Proposition 10.32. K^(g) < KI + nKx < min[(n + 1)^,
2nK00\.
Proof. Take p = {po,p} and q = (qo,q) in dom g such that Ki(g) = \po — qo\ + \\p - q\\i and either (i) po = qQ or (ii) p(v) = q(v) for some v € V. We may assume Po > Qo and p > q since p V q,p A q e domg and \\(p V q) - (p A q)\\i = \\p - q\\iThe vectors p' = p — pol and q' = q — qol belong to domg. In case (i), we have Ki(g] = \\p-q\\\ = \\p'~
Note finally that KI < nKx and Kx < KI.
D
The steepest descent algorithm could be used for minimizing quasi L-convex functions satisfying (SSQSBW) because of Theorem 7.53 (quasi L-optimality criterion). Note, however, that the set function pp of (10.32), to be minimized in step SI, is not necessarily submodular and hence no efficient procedure is available for step SI.
308
10.3.2
Chapter 10. Algorithms
Steepest Descent Scaling Algorithm
The steepest descent algorithm for L-convex function minimization can be made more efficient with the aid of a scaling technique. The efficiency of the resulting steepest descent scaling algorithm is guaranteed by the complexity analysis in section 10.3.1 combined with the proximity theorem for L-convex functions. The algorithm for an L-convex function g with (10.31) reads as follows, where
Steepest descent scaling algorithm for an L-convex function g G JC.[Z —*• R] SO: Find a vector p € domg and set a := 2^l°S2(Kaa/'2n)] SI: Find an integer vector q that locally minimizes g(q) = g(p + aq) in the sense of g(q) < g(q + Xx) (VX C V) by the steepest descent algorithm of section 10.3.1 with initial vector 0 and set p := p + aq. S2: If a = 1, then stop (p is a minimizer of g). S3: Set a := a/2 and go to SI. Note first that the function g(q) = g(p + aq) is an L-convex function. By the L-proximity theorem (Theorem 7.18 (1)), there exists a minimizer q of g satisfying 0 < q < (n - 1)1. Then, by Propositions 10.30 and 10.31, the steepest descent algorithm with tie-breaking rule (10.33) finds the minimizer in step SI in O((cr(n)F + r(n))n 2 ) time, where
10.3.3
Reduction to Submodular Function Minimization
The effective domain of an L''-convex function g is a distributive lattice (a sublattice of Zv) on which g is submodular. Hence we can make use of submodular function minimization algorithms as adapted to functions on distributive lattices (see Note 10.15). If the £i-size of domg is given by KI, domg is isomorphic to a sublattice of the Boolean lattice 2V for a set V of cardinality KI . Hence, the complexity of this algorithm is polynomial in n and K\. It may be noted, however, that, being dependent only on the submodularity of g, this approach does not fully exploit L^-convexity.
10.4
Algorithms for M-Convex Submodular Flows
Five algorithms for the M-convex submodular flow problem are described: the twostage algorithm, the successive shortest path algorithm, the cycle-canceling algo-
10.4. Algorithms for M-Convex Submodular Flows
309
rithm, the primal-dual algorithm, and the conjugate scaling algorithm. Because the optimality criterion for the M-convex submodular flow problem is essentially equivalent to the duality theorems for M-/L-convex functions, these algorithms can be used for finding a separating afnne function in the separation theorem and the optimal solutions in the minimization/maximization problems in the Fenchel-type duality.
10.4.1
Two-Stage Algorithm
This section is intended to provide a general structural view on the duality nature of the M-convex submodular flow problem. It is based on the recognition of the M-convex submodular flow problem as a composition of the Fenchel-type duality and the minimum cost flow problem that does not involve an M-convex function. The algorithm presented in this section, called the two-stage algorithm, computes an optimal potential by solving an L-convex minimization problem in the dual problem and constructs an optimal flow as a feasible flow to another submodular flow problem. As an adaptation of our discussion in section 9.1.4, the relationship between the M-convex submodular flow problem MSFPs and the Fenchel-type duality may be summarized as follows. To be specific, we consider the integer-flow version of MSFP3 on the graph G = (V, A) with / <E M[Z -> Z] and /„ e C[Z -> Z] for a e A. M-convex submodular flow problem MSFP3 (integer flow)
We assume the existence of an optimal solution. First, we identify the problem dual to MSFPs and indicate how to compute an optimal potential. With the introduction of a function
we obtain
where / e M[Z -> Z] and fA € M(Z -> Z]. Putting g = /*, ga = /0* for a € A, and
310
Chapter 10. Algorithms
we have gA = fA* (see (9.28)) and also g e £[Z -> Z], #0 e C[Z -> Z] for a € v4, and gA e £[Z -> Z]. The Fenchel-type duality (Theorem 8.21 (3)) gives
which is equivalent to61
The function
to be minimized on the right-hand side of (10.44) is an L-convex function and a minimizer of g is an optimal potential for MSFPa, and vice versa, in the sense of Theorem 9.16. Next we discuss how to construct an optimal flow. Let p* be a minimizer of g and define c* : A -> Z U {-oo}, c* : A -> Z U {+00}, and B* C Zv by
where B* is an M-convex set by Proposition 6.29. Since p* is an optimal potential, a flow £* is optimal if and only if
The two-stage algorithm is described as follows. Two-stage algorithm for MSFP3 (integer flow) SI: Find a minimizer p* of g in (10.45). S2: Find a flow £* satisfying (10.48). The feasibility of this approach is guaranteed by the following facts if the given functions, / and fa for a € A, can be evaluated. 1. We can evaluate g by applying an M-convex function minimization algorithm to /. Similarly, we can evaluate ga for a e A. 2. We can find a minimizer p* in step SI by applying an L-convex function minimization algorithm to g. 3. We can find a member of B* by applying an M-convex function minimization algorithm to /[—p*}. 4. We can find a flow £* in step S2 as a feasible flow to the submodular flow problem defined by c*, c*, and B*. This can be done, e.g., by the successive shortest path algorithm described in section 10.4.2. 61
We have seen (10.44) in (9.83) as a special case of Theorem 9.26 (3).
10.4.
Algorithms for M-Convex Submodular Flows
10.4.2
311
Successive Shortest Path Algorithm
We present the successive shortest path algorithm to find a feasible integer flow in an integral submodular flow problem. We adopt the most primitive form of the algorithm to better explain the basic idea without being bothered by technicalities. Given a graph G = (V,A), an upper capacity c : A —> Z U {+00}, a lower capacity c : A —> Zu{—oo}, and an M-convex set B C Zv, we are to find an integer flow £ : A —> Z satisfying
It is assumed that c(a) < c(a) for each a e A. The algorithm maintains a pair (£, z) e ZA x Zv of integer flow £ satisfying (10.49) and base x e B and repeats modifying (£, z) to resolve the discrepancy between d£ and x. For such (£,x) let G^,x = (V,j4j >x ) be a directed graph with vertex set V and arc set A^tX = A*c U B£ U Cx consisting of three disjoint parts:
and define
In order to reduce the discrepancy ||z - d£\\i = X^ev \x(v) ~ <9£(v)|, tne algorithm augments a unit flow along a shortest path P from S+ to S~ (shortest with respect to the number of arcs) and modifies £ to £ given by
Obviously, £ satisfies the capacity constraint (10.49). The algorithm also updates the base x to
which remains a base belonging to B; see Note 10.33. For the initial vertex s G S+ of the path P, either d£(s) increases or x(s) decreases by one and hence |z(s) — <9£(s)| reduces by one. A similar result is true for the terminal vertex of P in S~, whereas x(v) = d£(v) is kept invariant at every inner vertex v of P. Therefore, each augmentation along a shortest path decreases ||z — £||i by two. Repeating this process until the source S+ and consequently the sink S~ become empty, the algorithm constructs a pair (£, z) with df, — x. Then £ is a feasible flow satisfying both (10.49) and (10.50).
312
Chapter 10. Algorithms
Successive shortest path algorithm for finding a feasible integer flow SO: Find £ e ZA satisfying (10.49) and x <E B. SI: If S+ is empty, then stop (£ is a feasible flow). S2: If there is no path from S+ to S~, then stop (no feasible flow exists). S3: Let P be a shortest path from S+ to S~ and. for each arc a £ P. set
and go to SI.
Note 10.33. The updated vector x in (10.52) remains a base, i.e., x e B, by Proposition 9.23 with / = SB (indicator function of B). Let G(x, x) be the bipartite graph, as defined in section 9.5.2. All the arcs have zero weight. Hence, (x, x) meets the unique-min condition if and only if G(x, x) has a unique perfect matching. The latter condition holds in the algorithm because P is chosen to be a shortest path, whereas Proposition 9.23 says that the unique-min condition implies x £ B. • Note 10.34. Instead of augmenting a unit flow along P it is more efficient to augment as much as possible. The maximum admissible amount is given by 6 = min{c(a) | a € P} with
where cg(-, •, •) means the exchange capacity defined in (10.4). It can be shown that stays in B; see Lemma 4.5 of Fujishige [65]. The successive shortest path algorithm can be adapted to finding a real-valued feasible flow to a nonintegral submodular flow problem. For a polynomial complexity bound of the algorithm, it is important to choose, in the case of multiple candidates, an appropriate shortest path with reference to some lexicographic ordering. The successive shortest path algorithm can be generalized for optimal flow problems involving cost functions; see [65], Fujishige-Iwata [66], and Iwata [98] for such algorithms for MSFPi (without Mconvex cost), whereas such an algorithm for the integer-flow version of MSFP2 (with M-convex cost) is given in Moriguchi-Murota [132]. • Note 10.35. A number of algorithms are available for finding a feasible submodular flow; e.g., Fujishige [59], Frank [56], Tardos-Tovey-Trick [199], and Fujishige-Zhang [70]. The reader is referred to Fujishige [65], Fujishige-Iwata [66], and Iwata [98] for expositions. • 10.4.3
Cycle-Canceling Algorithm
For the M-convex submodular integer-flow problem with linear arc cost, we have seen in section 9.5 that a feasible flow is optimal if and only if there exists no negative
10.4. Algorithms for M-Convex Submodular Flows
313
cycle in an auxiliary network (Theorem 9.20) and that a nonoptimal flow can be improved by augmenting a flow along a suitably chosen negative cycle (Theorem 9.22). These two facts suggest the following cycle-canceling algorithm, which works on the auxiliary network (G^,^) introduced in section 9.5. Cycle-canceling algorithm for MSFP2 (integer flow) SO: Find a feasible integer flow £. SI: If (G^,^) has no negative cycle, then stop (£ is an optimal flow). S2: Let Q be a negative cycle with the smallest number of arcs. S3: Modify £ to £ of (9.75) and go to SI. The objective function I^ decreases monotonically by Theorem 9.22. This property alone does not ensure finite termination in general, but it does if F^ is integer valued and bounded from below. In the special case with dom/ C {0,1}^, which corresponds to the valuated matroid intersection problem (Example 8.28), some variants of the cycle-canceling algorithm are known to be strongly polynomial (see Murota [136]). Cycle-canceling algorithms can also be designed for problems with real-valued flow on the basis of Theorem 9.18. Note 10.36. For MSFPi (submodular flow problem with linear arc cost and without M-convex cost), a number of cycle-canceling algorithms are proposed, including Fujishige [59], Cui-Fujishige [27], Zimmermann [222], Wallacher-Zimmermann [210], and Iwata-McCormick-Shigeno [103]. •
10.4.4
Primal-Dual Algorithm
A primal-dual algorithm for the M-convex submodular flow problem is described. The algorithm maintains a pair of flow and potential and modifies them to optimality. We deal with the case of linear arc cost with dual integrality. M-convex submodular flow problem MSFP2
Here, c : A -^ R U {+00}, c : A -> R U {-oo}, / € M[TL -> R Z], and 7 : A -> Z (see (9.67)). The feasibility of the problem is also assumed. By Theorems 9.14 and 9.15 as well as (9.31), (9.32), and (9.65), a feasible flow £ : A —> R is optimal if and only if there exists an integer-valued potential p : V —> Z such that
314
Chapter 10. Algorithms
where 7P : A —> Z is the (integer-valued) reduced cost defined by
gp : 2V —> R U {+00} is the submodular set function derived from g = f* e £[Z|R -> R] by
with gp(V) = 0 by (9.51), and B(gp) is the base polyhedron (M-convex polyhedron) associated with gp. The algorithm maintains a pair (£,p) 6 R"4 x Zv of a feasible flow £ and an integer-valued potential p that satisfies (10.59) and repeats modifying (£,p) to increase the set of arcs satisfying (10.57) and (10.58). We say an arc is in kilter with respect to (£,p) if it satisfies (10.57) and (10.58) and out of kilter otherwise. Note that exactly one of (10.57) and (10.58) fails for an out-of-kilter arc. An initial (£,p) satisfying (10.59) can be found as follows. For any feasible flow £ we consider a graph Gf — (V, Q) with vertex set V and arc set
and define the length of arc ( u , v ) as /'(<9£; — Xu + Xv), which is an integer by the assumed dual integrality (Note 9.19). By solving a shortest path problem we can find an integral vector p such that
which implies d£ 6 argmin/[-p] = B(gp) by (9.64) and (9.65). To classify out-of-kilter arcs we define
where the dependence on p is implicit in the notation. Note that D^(v) is the set of arcs leaving v for which (10.58) fails, D7 (v) is the set of arcs entering v for which (10.57) fails, and {D^(v) \ v £ V} gives a partition of the set of out-of-kilter arcs. If D^(v) = 0 for all v € V, condition (i) of (POT) is satisfied and the current (£,£>) is optimal. Otherwise, the algorithm picks62 any v* € V with nonempty D^(v*) and tries to meet the conditions (10.57) for a 6 D7(v*) and (10.58) for a e Dt(v*) by changing the flow to £'. The flow £' is determined by solving the following maximum submodular flow problem on G = (V, A) with a more restrictive capacity constraint c*(a) < £'(a) < c*(a) with 62
The original primal-dual algorithm' picks an out-of-kilter arc and tries to meet (10.57) and (10.58) for that arc. The present strategy to pick a vertex is to improve the worst-case complexity bound.
10.4.
Algorithms for M-Convex Submodular Flows
315
for each a 6 A. Maximum submodular flow problem maxSFP
where £' : A —> R is the variable to be optimized. Since the capacity interval [c* (a) ,c* (a)] is included in the original capacity interval [c(a),c(a)], any feasible flow in maxSFP is feasible in MSFP2. Note also that maxSFP has a feasible flow £' = £. In maximizing the objective function
it is intended to~ meet the conditions (10.58) and (10.57) by increasing the flow in a G D£(V*') to the upper capacity and decreasing the flow in a G D^(v*) to the lower capacity. The maximum submodular flow problem is a special case of the feasibility problem for the submodular flow problem and a number of efficient algorithms are available for it (see section 10.4.2). Let £' be an optimal solution to maxSFP above. If D^/(v*) is empty, the algorithm updates £ to £' without changing p. The condition (10.59) is maintained because of (10.65). If D^(v*) is nonempty, the algorithm finds a minimum cut W C V (explained later) and updates p to
as well as £ to £'. The condition (10.59) is maintained, as is shown in Proposition 10.38 below. The primal-dual algorithm for the M-convex submodular flow problem with a linear arc cost (MSFP2) with dual integrality is summarized as follows. Primal-dual algorithm for MSFPz with dual integrality SO: Find (£,p) e R/4 x Zv satisfying (10.54) and (10.59). SI: If D$(v) = 0 for all v 6 V, then stop ((£ ,p) is optimal). S2: Take any v* e V with D^(v*) ^ 0 and solve maxSFP to obtain £'. S3: If D£I(V*) ^ 0, then find a minimum cut W and set p := p + xwS4: Set £ := £' and go to SI. It remains to explain the minimum cut for maxSFP. For W C V containing v*, we define the cut capacity i/(W) by
316
Chapter 10.
Algorithms
Figure 10.1. Structure of G and G at v*.
where A+W and A W mean the sets of arcs leaving W and entering W, respectively, as in (9.14) and (9.15). The following proposition states that the flow value £'(D£(v*))-£'(Dt(v*)) is bounded by v(W] for any W C V with v* e W and that this bound is tight for some W, which is referred to as a minimum cut in the above. A minimum cut can be found with the aid of an appropriately defined auxiliary network. Proposition 10.37. In the maximum submodular flow problem maxSFP, we have
For a maximum flow £' and a minimum cut W, we have
Proof. We prove this by applying Theorem 9.13 (max-flow min-cut theorem) to a maximum submodular flow problem on a graph G = (V, A), which is obtained from G = (V,A) by a local modification at v* illustrated in Fig. 10.1. The vertex v* in G is split into two vertices, v* and v*, and a new arc OQ = (v*,i)*) is introduced; V — V U {{>*} and A = A U {a0}. The initial vertex of a € D£(V*) is changed to v* and the terminal vertex of a & D7(v*) is changed to v*. For W C V we denote by A + jy and A~W the sets of arcs leaving and entering W, respectively, in G. The problem maxSFP is equivalent to maximizing the flow £'(OQ) in OQ in G = (V,A), where the conservation of flow at v* (i.e., d£'(v*) = 0) is assumed and no
10.4. Algorithms for M-Convex Submodular Flows
317
capacity constraint is imposed on UQ. Note that £'(ao) = £'(Dt(v*))—t;'(D7(v*)) as a consequence of the flow conservation at v*. As for cuts, we note the correspondence between W C V with OQ e A+W and W C V with v* G W and observe the identities
for such a W. Then we obtain (10.68) from (9.61) in Theorem 9.13. Note that d(p + Xw) — g(p) = 9p(W) in v(W) corresponds to p in (9.61). Finally, (10.69), (10.70), and (10.71) are shown in (9.62). D The condition (10.59) is maintained when (£,p) is modified to (£',?/)• Proposition 10.38. #£' G B(<jy) for an optimum flow £' mmaxSFP and potential p' = p + xw with a minimum cut W. Proof. It follows from (10.65), (10.69), and discrete midpoint convexity (7.7) that
This shows #£' &B(gp>).
D
The following proposition shows the key properties for the correctness and complexity of the primal-dual algorithm. Proposition 10.39.
(1) The set of out-of-kilter arcs is nonincreasing. (2) For each arc a, |7P(a)| is nonincreasing while the arc stays out of kilter. (3) The potential is changed in at most \V\ iterations and, each time the potential is changed, the value of max.a€rj^(v*) |7p(a)| decreases at least by one. (4) Each time (£,p) is changed, the value of
decreases at least by one. Therefore, the primal-dual algorithm terminates in at most NO iterations, where NO denotes the value of N at step SO. Proof. The reader is referred to the kilter diagram in Fig. 9.1. (1) We show that an in-kilter arc a with respect to (£,p) remains in kilter in updating (£,p). It follows from £'(a) e [c*(a),c*(a)j and (10.62) that a remains in kilter with respect to (£',p). Suppose that p is updated to p' = p + \w- Since
318
Chapter 10.
Algorithms
we may assume that a is in kilter with respect to (£',p) and (i) a G A+VP7 \ Dt(v*) or (ii) a e A~VF \ D^(v*). In case (i) we have £'(a) = c*(a) from (10.70), whereas
In case (ii) we have £'(a) — ^*(a) from (10.71), whereas
Thus the conditions (10.57) and (10.58) are preserved in either case. (2) By (10.73), it suffices to show that, if (i) 7p(a) > 0, a e A+VF, or (ii) 7P(a) < 0, a e A~W, then a is in kilter with respect to (£',p')- In case 0)i we have a e <\+W\D+(v*), from which follows £'(a) = c*(a) = c(a) by (10.70). Since 7P'(a) > 0, a is in kilter with respect to (£',p')> and similarly for case (ii). (3) If the potential does not change, we have D^i(v*) = 0 as well as D^(v) C D^(v) for all w 6 V^ by (1). Therefore, the potential must be updated in |V| iterations. Suppose now that p is changed to p'. An arc a & Df(v*).\ A+W is in kilter with respect to (£',£>'), since 7 P /(a) < 7P(a) < 0 and £'(a) = c*(a) = c(a) by (10.71). Similarly, a e D7(v*) \A~W is in kilter with respect to (£',p') because of (10.70). Fora e D+(w*)nA+VF, we have |7j/(a)| = |7P(a)|-l froni7 p /(a) =7 p (a) + 1 and 7P(a) < 0. Similarly, for a e D~^(v*) n A^H 7 , we have |7P'(a)| = 7 P (a)| - 1 from 7P'(a) = 7P(a) — 1 and 7P(a) > 0. Therefore, maxo6£){(«*) |7P(«)| decreases at least by one. (4) When the potential changes, TV decreases because of (3). When the potential remains invariant, N decreases because of Z?£/(u*) =0. D Primal-dual algorithms can also be designed for problems without dual integrality by using real-valued potential functions. Note 10.40. The framework of the primal-dual algorithm for MSFPi (submodular flow problem without M-convex cost) was established in Frank [55] and CunninghamFrank [30]. See Fujishige [65], Fujishige-Iwata [66], and Iwata [98] for expositions. •
10.4.5
Conjugate Scaling Algorithm
With the use of conjugate scaling of the M-convex cost function, the primal-dual algorithm is enhanced to a polynomial-time algorithm. We continue to deal with the M-convex submodular flow problem MSF?2 with dual integrality; i.e., we assume 7 : A -> Z and / e M[K. -> R Z]. First we explain the intuition behind the cost-scaling algorithm for the submodular flow problem MSFPi without M-convex function (see section 9.2 for MSFPi). As Proposition 10.39 (4) shows, the time complexity of the primal-dual algorithm depends essentially on
10.4.
Algorithms for M-Convex Submodular Flows
319
Motivated by this fact, we consider MSFPi with a new objective function
where a is a positive integer representing cost scaling and [ • ] means rounding up to the nearest integer. It is expected (or hoped) that such a scaling will result in smaller values of (10.74) and hence in an improvement in the computation time of the algorithm. On the other hand, the scaled problem with (10.75) is fairly close to the original problem, since a|~7(a)/a] ~ 7(0), and, therefore, the solution to the scaled problem is likely to be a good approximation that can be used as an initial solution in solving the original problem by the primal-dual algorithm. The scaling algorithm embodies the above idea by starting with a large a and successively halving a until a = 1. When an M-convex function / is involved, as in MSFP2, it is natural to try a scaling of the form [/(•)/<*]. This approach, however, does not seem to work in general, since \f(-)/oi\ is not necessarily M-convex for an M-convex function /. Conjugate scaling is a kind of scaling operation compatible with M-convexity. Let / : Rv —> Ru{+oo} be a polyhedral convex function with dual integrality in the sense that the conjugate function g = /* has integrality (6.75). Then we have where the supremum is taken over integer points. Replacing g(p) with ga(p) = g(ap)/a (p € Zv) in this expression we define
which we call the conjugate scaling of / with scaling factor a £ Z++. Note that /^ is again a dual-integral polyhedral convex function. It is easy to see that
and that doniR,/^ = doniR,/ provided /^ > —oo. Figure 10.2 illustrates the conjugate scaling of a univariate function / with a = 2. Proposition 10.41. For a dual-integral polyhedral M-convex function f £ M [R —> R|Z], we have /< a > e M[R -» R|Z] provided /<"> > -oo. Proof. We have /* = g & £[Z|R -> R] and hence ga e £[Z -» R] by Theorem 7.10 (2). Therefore, /< Q > = (ga)' e M\R, -> R|Z] by (8.10). D We are now in the position to present the conjugate scaling algorithm. Initially the algorithm finds a feasible flow £o and an integer-valued potential po satisfying (10.59) and applies the conjugate scaling to the objective function rewritten as
Chapter 10. Algorithms
320
Figure 10.2. Conjugate scaling f^
and scaling ga for a = 2.
where 7 = 7po and / = /[—p 0 ]. We denote the conjugate scaling of / by /^ and put g = /*. Note that / e M[H -> R|Z] and
where we regard g as a member of £[Z —> R]. Recall the notation n = \V\.
Conjugate scaling algorithm for MSFP2 with dual integrality
SO: Find a feasible flow £o G R"4 and an integer-valued potential po 6 Zv satisfying (10.59) and define 7, /, and g accordingly. Set p* := 0, K :== max a€A |7(a)|, a := 2^2 K] _ SI: If a < 1, then stop ((£,Po + p*) is optimal). S2: Find an integer vector p € Zv that minimizes ga(p) — (p,d£) subject to Ip* < p < 2p* + (n- 1)1. S3: Solve MSFP2 for (7,/) = (py/a], / < Q > ) by the primal-dual algorithm starting with (£,p) to obtain an optimal (£,*,P*) € R"4 x Zv. S4: Set £ := £* and a := a/2 and go to SI.
The correctness of the algorithm is ensured by Theorem 7.18 (L-proximity theorem), which implies that the minimizer p found in step S2 under the restriction 2p* < p < 2p* + (n — 1)1 is in fact a global minimizer of ga(p) — (p, d£). Hence, the condition <9£ € B(gap) = argmin/< a >[-p] for (10.59) is maintained. In step S2, the minimizer p can be found by the L-convex function minimization algorithms of section 10.3, where the number of evaluations of ga is bounded by a polynomial in n. Given /, an evaluation of ga amounts to minimizing a polyhedral M-convex function, since g(p) = sup{(p, x) — f ( x ) \ x (E R^}. If / has primal
10.4.
Algorithms for M-Convex Submodular Flows
321
integrality, i.e., if / G A4[Z|R —> R], theng(p) = swp{(p,x)—f(x) \ x e Zv}, which can be computed by the algorithms in section 10.1. In step S3, the number of iterations (updates of (£,p)) within the primal-dual algorithm is bounded by n2. Denote by pa the value of p at the beginning of step S3 and put p2a = p*, 7™ = |~7/of|, and -J2a = py/(2a:)]. Then we have
from which follows
This means that at the beginning of step S3 we have
for every out-of-kilter arc a and therefore N in (10.72) is bounded by n2. Obviously, steps SI through S4 are repeated flog2 K~\ times. For the value of K we have if the initial potential po in step SO is computed from a shortest path on the graph Gj = (V^Cf), as explained in section 10.4.4, where in the second term on the right-hand side we consider only those x, u, v for which f ' ( x ; —\u + Xv) is finite. If / 6 .M[Z|R —> R], the second term can be bounded as
which implies
Bibliographical Notes The tie-breaking rule (10.2) for M-convex function minimization, as well as Proposition 10.2, is due to Murota [148]. Variants of steepest descent algorithms are reported in Moriguchi-Murota-Shioura [133] with some computational results. Scaling algorithms for M-convex function minimization, including the one described in section 10.1.2, were considered first in [133], although the proposed algorithms run in polynomial time only for a subclass of M-convex functions that are closed under scaling. A polynomial-time scaling algorithm for general M-convex functions is given by Tamura [197]. The domain reduction algorithm in section 10.1.3 is due to Shioura [190] and its extension to quasi M-convex functions is observed in MurotaShioura [154]. The domain reduction scaling algorithm in section 10.1.4, with its extension to quasi M-convex functions, is due to Shioura [192]. Minimizing an Mconvex function on {0, l}-vectors is equivalent to maximizing a matroid valuation, for which a greedy algorithm of Dress-Wenzel [41] works; see also section 5.2.4 of Murota [146].
322
Chapter 10.
Algorithms
The literature of submodular function minimization was described in Note 10.10. The algorithmic framework expounded in section 10.2.1 is due to Cunningham [28], [29] as well as Bixby-Cunningham-Topkis [15]. The algorithm in section 10.2.2 is by Schrijver [182], whereas an earlier version of this algorithm based on partial orders associated with extreme bases (presented at the Workshop on Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, Fields Institute, November 1-6, 1999) is described in Murota [147]. The algorithm in section 10.2.3 is due to Iwata-Fleischer-Fujishige [102]. Improvements on those algorithms in terms of time complexity were made by Fleischer-Iwata [50] and Iwata [100]. See McCormick [127] for a detailed survey on submodular function minimization. Note 10.12 was communicated by K. Nagano, Note 10.14 is based on [182], and Proposition 10.28 was communicated by S. Iwata. Favati-Tardella [49] proposes a weakly polynomial algorithm for submodular integrally convex function minimization. This is the first polynomial algorithm for L-convex function minimization, when translated through the equivalence between submodular integrally convex functions and lAconvex functions. The steepest descent algorithm for L-convex function minimization in section 10.3.1 is given in Murota [145]. The tie-breaking rule (10.33), as well as Proposition 10.31, is due to Murota [148]. The steepest descent scaling algorithm in section 10.3.2 is due to S. Iwata (presented at Workshop on Matroids, Matching, and Extensions, University of Waterloo, December 6-11, 1999), where step SI is performed not by the steepest descent algorithm but by the algorithm in section 10.3.3. The framework of M-convex submodular flow problems is advanced by Murota [142]. The successive shortest path algorithm for a feasible flow described in section 10.4.2 originates in Fujishige [59] and the present form is due to Frank [56]. The cycle-canceling algorithm of section 10.4.3 is devised in [142] as a proof of the negative-cycle criterion for optimality (Theorem 9.20). In the special case of valuated matroid intersection, the algorithm can be polished to a strongly polynomial algorithm (Murota [136]); see also Note 10.36. The primal-dual algorithm of section 10.4.4 is due to Iwata-Shigeno [105]; see also Note 10.40. A strongly polynomial primal-dual algorithm for the valuated matroid intersection problem is given in [136]. The conjugate scaling algorithm of section 10.4.5 is due to [105]. A scaling algorithm for a subclass of the M-convex submodular flow problem is given by Moriguchi-Murota [132]. Capacity scaling algorithms for submodular flow problems (without M-convex costs) are given in Iwata [97] and Fleischer-Iwata-McCormick [51]. For other algorithms for submodular flow problems (without M-convex costs), see the book of Fujishige [65] and surveys of Fujishige-Iwata [66] and Iwata [98].
Chapter 11
Application to Mathematical Economics
This chapter presents an application of discrete convex analysis to a subject in mathematical economics: competitive equilibria in economies with indivisible (or discrete) commodities. For economies consisting of continuous commodities, represented by real-valued vectors, a rigorous mathematical framework was established around 1960 on the basis of convexity, compactness, and fixed-point theorems. For indivisible commodities, however, no general mathematical framework seems to have been established. Such a framework, if any, should embrace both convexity and discreteness; the present theory of discrete convex analysis appears to be a promising candidate for it. It is shown that, in an Arrow-Debreu type model of competitive economies with indivisible commodities, an equilibrium exists under the assumption of the M^-concavity of consumers' utility functions and the M'-'-convexity of producers' cost functions. Moreover, the equilibrium prices form an L''-convex polyhedron, and, therefore, they have maximum and minimum elements. The conjugacy between M-convexity and L-convexity corresponds to the relationship between commodities and prices.
11.1
Economic Model with Indivisible Commodities
As an application of discrete convex analysis we deal with competitive equilibria in economies with a number of indivisible commodities and money. Indivisible commodities mean commodities (goods) whose quantities are represented by integers, such as houses, cars, and aircraft, whereas money is a real number representing the aggregation of the markets of other commodities. We consider an economy (of Arrow-Debreu type) with a finite set L of producers, a finite set H of consumers, a finite set K of indivisible commodities, and a perfectly divisible commodity called money. Productions of producers and consumptions of consumers are integer-valued vectors in ZK representing the numbers of indivisible commodities that they produce or consume. Here producers' outputs are represented by positive numbers, while negative numbers are interpreted as inputs to them, and consumers' inputs are represented by positive numbers, 323
324
Chapter 11. Application to Mathematical Economics
while negative numbers are interpreted as outputs from them. Given a price vector p = (p(k) : k € K) 6 R^ of commodities, each producer (assumed to be male) independently schedules a production in order to maximize his profit, each consumer (assumed to be female) independently schedules a consumption to maximize her utility under the budget constraint, and all agents exchange commodities by buying or selling them through money. An important feature of this model is that the independent agents take the price as granted; i.e., they assume that their individual behaviors do not affect the price. Such an economy is called a competitive economy. We assume that a producer I e L is described by his cost function GI : ZK —> RU {+00}, whose value is expressed in units of money. He wishes to maximize the profit (p,y) — Ci(y) in determining his production y = yi e ZK. This means that yi is chosen from the supply set
where the function Si : RK —> 2Z is called the supply correspondence. Accordingly, the profit function TTJ : R^ —> R is defined by
To avoid possible technical complications irrelevant to discreteness issues, we assume that dom Ci is a bounded subset of 7iK for each I 6 L. This guarantees, for instance, that Si (p) is nonempty for any p. Each consumer h € H has an initial endowment of indivisible commodities and money, represented by a vector (x^,m^) € ZK x R+, where x^(fc) denotes the number of the commodity k e K and m°h the amount of money in her initial endowment. Consumers share in the profits of the producers. We denote by dih the share of the profit of producer I owned by consumer h, where
Thus, consumer h gains an income
where /3h '• RK —> R, and accordingly her schedule (x, m) = (x/j, mh) should belong to her budget set
We assume that a consumer h is associated with a utility function Uh '• "ZK x R —> RU {—00} that is quasi linear in money; namely,
11.1.
Economic Model with Indivisible Commodities
325
Figure 11.1. Consumer's behavior.
with a function63 [//, : Zx —> Ru{—oo}. Consumer h maximizes Uh under the budget constraint; that is, (x,m) — (xh,TTih) ls a solution to the following optimization problem:
(see Fig. 11.1). Under the assumption that domUh is bounded0 and mh is sufficiently large, we can take
to reduce the above problem to an unconstrained optimization problem:
This means that Xh is chosen from the demand set
The function Dh '• RK —> 2Z is called the demand correspondence. A tuple ((xh | h 6 H), (yi \ I e L),p), where xh e ZK, j/j e ZK, and p 6 RK, is called an equilibrium or a competitive equilibrium if 63 In economic terminology, U^ is called the reservation value function, although we refer to it as the utility function in this book. 64 The boundedness of dom I//, is a natural assumption because no one can consume an infinite number of indivisible commodities. This assumption is also convenient for concentrating on discreteness issues in our discussion.
326
Chapter 11. Application to Mathematical Economics
That is, each agent achieves what he or she wishes to achieve, the balance of supply and demand holds, and an equilibrium price vector is nonnegative. Denoting the total initial endowment of indivisible commodities by
we can rewrite the supply-demand balance (11.11) as
On eliminating Xh and yi using (11.9) and (11.10), we see that p e R^ is an equilibrium price if and only if
where the right-hand side is a Minkowski sum in ZK. It is noted that money balance
is implied by (11.11) with (11.3), (11.4), (11.7), and 7rj(p) = (p ) W ) - d(yi). We are concerned with mathematical properties of equilibria, rather than their economic-theoretical significance. A most fundamental question would be as follows: When does an equilibrium exist? Namely, the first problem we should address is this: Problem 1: Give a (sufficient) condition for the existence of an equilibrium in terms of utility functions Uh and cost functions C\. The conditions (11.9) and (11.10) for an equilibrium are given in terms of demand correspondences Dh and supply correspondences 5; without explicit reference to utility functions Uh and cost functions C\. This motivates the following: Problem 2: Give a (sufficient) condition for the existence of an equilibrium in terms of demand correspondences Dh and supply correspondences Si. When an equilibrium exists, we may be interested in its structure: Problem 3: Investigate the structure of the set of equilibria. A more specific problem in this category is as follows: Do the maximum and minimum exist among equilibrium price vectors? We shall answer the above problems with the use of concepts and results in discrete convex analysis. Our answers are the following.
11.2.
Difficulty with Indivisibility
327
(1) An equilibrium exists if Uh (h e H) are M^-concave functions and Ci (I € I/) are M^-convex functions (Theorems 11.13 and 11.14). (2) An equilibrium exists if Dh(p) (h € H) and Si(p) (I € L) are M^-convex sets for each p (Theorem 11.15). (3) The set P* of the equilibrium prices is an L''-convex polyhedron (Theorem 11.16). This means, in particular, that p V q,p A q € P* for any p, q e P* and that there exist a maximum and a minimum among equilibrium prices. As a preliminary consideration, the difficulty arising from indivisible commodities is demonstrated in section 11.2 by a simple example. In section 11.3 we discuss the relevance of M^-concavity as an essential property of utility functions. The results mentioned above are proved in section 11.4. Finally, in section 11.5, we show that an equilibrium can be computed by solving an M-convex submodular flow problem. Note 11.1. A special case of our economic model with L = 0, where no producers are involved, is called the exchange economy. A difficulty of indivisible commodities already arises in this case, as we will see in section 11.2. • Note 11.2. Commodities that can be represented by real-valued vectors are called divisible commodities. A framework for the rigorous mathematical treatment of equilibria in economies of divisible commodities was established around 1960 usin convexity, compactness, and fixed-point theorems as major mathematical tools. See Debreu [37], [38], Nikaido [168], Arrow-Hahn [4], and McKenzie [128]. Note 11.3. A considerable literature already exists on equilibria in economies with indivisible commodities. We name a few: Henry [88], 1970; Shapley-Scarf [187], 1974; Kaneko [107], 1982; Kelso-Crawford [111], 1982; Gale [72], 1984; Quinz [173], 1984; Svensson [196], 1984; Wako [209], 1984; Kaneko-Yamamoto [108], 19 Van der Laan-Talman-Yang [204], 1997; Bikhchandani-Mamer [13], 1997; Danilov Koshevoy-Murota [34], 1998 (also [35], 2001); Bevia-Quinzii-Silva [12], 1999; Gu Stacchetti [84], 1999; and Yang [219], 2000.
11.2
Difficulty with Indivisibility
The difficulty in the mathematical treatment of indivisible commodities is illustrated by a simple example. We consider an exchange economy consisting of two agents (H = {1,2}, L = 0) dealing in two indivisible commodities (K = {1,2}). Putting S = {(0,0), (0,1), (1,0), (1,1)} we define the utility functions Uh for h = 1,2 in (11.6) by
where domC/i = domC/2 = S (see Fig. 11.2). The demand correspondences D\ and _D2, calculated according to (11.8), are also given in Fig. 11.2. For instance, for
328
Chapter 11. Application to Mathematical Economics
Figure 11.2. Exchange economy with no equilibrium for x° = (1,1).
p = (p(l),p(2)) with 0 < p ( l ) < 1 and 0 < p(2) < 1, we have Di(p) = {(1,1)}; for p = (1,1), we have D^p) = {(1,1), (0,1), (1,0)} and £>2(p) = {(1,1)}. Given a total initial endowment x°, an equilibrium is a tuple (xi,x 2 ,p) e Z2 x Z2 x R2. such that
For x° = (1, 2), for example, the tuple of x\ = (0,1), x? = (1,1), p = (2,1) satisfies the above conditions and hence is an equilibrium. Another case, x° = (1,1), is problematic. As we have seen in (11.15), a nonnegative vector p is an equilibrium price if and only if x° € Di(p) + D^p). Superposition of the diagrams for Di(p) and £>2(p) in Fig. 11.2 yields a similar diagram for the Minkowski sum Di(p) + Dz(p), shown in Fig. 11.3. We see from this diagram that no p satisfies (1,1) 6 Di(p) + D^p) and hence no equilibrium exists for x° = (1,1). The diagram consists of eight regions, corresponding to the eight points in [0, 2]z x [0, 2]z except {(1,1)}. Hence an equilibrium exists for every
11.2. Difficulty with Indivisibility
329
Figure 11.3. Minkowski sum Di(p) + D2(p).
x° £ ([0,2] z x [0,2] z ) \ {(1,1)} and not for x° = (1,1). Let us have a closer look at the problematic case to better understand the discreteness inherent in the problem and to identify the source of the difficulty. In view of the established mathematical framework for divisible commodities, we consider an embedding of our discrete problem via a concave extension of the utility functions. Denote by Ui and U2 the concave extensions of U\ and U%, respectively. Obviously, doniRt/i = dom.Rt/2 = S, where S = [0, I]R x [0, I]R, and
The demand correspondences are defined by
for h = 1,2 and an equilibrium is a tuple ( x i , X 2 , p ) 6 R2 x R2 x R+ such that
In our case of x° — (1,1), the tuple of xi = x2 = (1/2,1/2) and p = (3/2,3/2) is an equilibrium in this sense, but it is not qualified as an equilibrium in the original problem of indivisible commodities, in which xi and x2 must be integer vectors. Thus, there is an essential discrepancy between the original discrete problem and the derived continuous problem. We can identify the reason for this discrepancy as the lack of convexity in Minkowski sum discussed in section 3.3. Since Dh(p) coincides with the convex hull Dh(p) of Dh(p) and £>i(p) + D2(p) = -Di(p) + D2(p) holds by Proposition 3.17 (4), the derived continuous problem has an equilibrium if and only if x° e
330
Chapter 11. Application to Mathematical Economics
DI(P) + D2(p). On the other hand, the original discrete problem has an equilibrium if and only if x° e Di(p) + D2(p), as noted already. For p = (3/2,3/2), we have I>i(p) = {(0,1), (1,0)}, D2(p) = {(0, 0), (1,1)}, and
which has a hole at (1,1) (see Example 3.15 and Fig. 3.4). This hole is the very reason for the nonexistence of an equilibrium for indivisible commodities.
11.3
M^-Concave Utility Functions
We demonstrate the relevance of M^-concavity to utility functions by indicating its relationship with fundamental properties such as submodularity, the gross substitutes property, and the single improvement property, discussed in the literature of mathematical economics. First, recall from Theorem 6.2 that we can define an M^-concave function as a function U : ZK —* RU {—00} with domU ^ 0 satisfying the following exchange property:
where Xi is the ith unit vector and a maximum taken over an empty set is denned to be — co. A more compact expression of this exchange property is
where xo is the zero vector, AC/(x;j, i) — U(x — Xi + Xj) - U(x) as in (6.2), &U(x;0,i) = U(x-Xi)'-U(x),aa.d&U(y,i,0) = U(y + Xi)-U(y). All the results established in the previous chapters for M^-convex functions can obviously be rephrased for M^-concave functions. In particular, an M^-concave function U has the following properties (reformulations of Theorems 6.42, 6.19, 6.26, and 6.24, Propositions 6.33 and 6.35, and Theorem 6.30). • Concave extensibility: The concave closure U of U satisfies
• Submodularity:
Utility functions are usually assumed to have decreasing marginal returns, a property that corresponds to submodularity in the discrete case.
11.3.
M^-Concave Utility Functions
331
• Local characterization of global maximality: For x € dom U,
This says that special ascent directions work for increasing a utility function. • (—M^-GSfZ]): Ifx £ argmax£/[-p+p 0 l], P < , Po < x(i) for every i £ K with p(i) = q(i) and (ii) y(K)<x(K) if p0 = qoThis is a version of the gross substitutes property. Recall the brief discussion on the gross substitutes property at the beginning of section 6.8. • (—M^-SWCSfZ]): For x € argmint/[-p], p <E RK, and i € K, at least one of (i) and (ii) holds true: (i) x e argmaxC/[—p — a\i] for any a > 0, (ii) there exist a > 0 and y e argmaxt/[—p - a\i] such that y(i) = x(i) — 1 and y(j) > x(j) for all j € K \ {i}. This is another version of the gross substitutes property, called the stepwise gross substitutes property. • M^-convexity of maximizers: For every p € R^, argmax[/[—p] is an M13convex set. The properties above are essential features of M^-concave functions and, in fact, the last four characterize M^-concavity, as follows (reformulations of Theorems 6.24, 6.34, 6.36, and 6.30). Note that submodularity and concave extensibility (even together) do not imply M^-concavity. Theorem 11.4. For a function U : ZK —> R U {—00} with a nonempty domain,
effective
Theorem 11.5. For a concave-extensible function U : ZK —> R U {—00} with a bounded nonempty effective domain,
Theorem 11.6. For a concave-extensible function U : ZK —> R U {—00} with a nonempty effective domain,
332
Chapter 11. Application to Mathematical Economics
Theorem 11.7. For a function U : ZK —> R U {—00} with a bounded nonempty effective domain, U is M^-concave ^=> argmaxf/[—p] is an ^-convex set for each p 6 RK. Let us consider the special case of set functions to discuss the relationship of the above theorems to the results of Kelso-Crawford [111] and Gul-Stacchetti [84]. The gross substitutes property was denned originally for a set function U : 2K —> R in [111]. It reads as follows: (GS) If X e argmaxt/"[-p] and p < q, there exists Y e argmaxC/[—q] such that {i 6 X \ p ( i ) = q(i)} C Y, where
Two novel properties introduce are introduced in [84]; i.e., the single improvement property:
and the no complementarities property:
It is pointed out in [84] that these three properties are equivalent:65
for a set function U. It is also observed that (NC) is implied by the strong no complementarities property:
To derive these results from our previous theorems, we identify a set function U : 2K -> R with a function U : ZK -> R U {-oo}, where dom U = {0,1} K , by
When translated for U, the properties (GS) and (SI) for U may be written respectively as follows: 65 To be precise, this equivalence is shown in [84] for a monotone nondecreasing U, where p and q can be restricted to nonnegative vectors.
11.3. M^-Concave Utility Functions
333
(—Mb-GS w [Z]) If x e argmaxC/[—p] and p < q, there exists y e argmaxt/[—q] such that y(i) > x(i) for every i € K with p(z) = q(i). (-M^-SIwfZj) For p € R^ and x € domf/ \ argmax[/[-p],
Obviously, we have (-M*-GS[Z]) => (-M»-GS W [Z]) and (-M*-SI[Z]) =» (-M"SIW[Z]) and it can be shown (see Murota-Tamura [160]) that the converses are also true if domC/ = {0,1}^. It follows from this and Theorems 11.4 and 11.5 that
On the other hand, we see
from the multiple exchange axiom for a matroid (see Theorem 4.3.1 in Kung [117]) and Theorem 11.7. Thus, the three conditions (GS), (SI), and (NC) for U are all equivalent to the M^-concavity of U. Obviously, the special case of (SNC) with |/| = 1 coincides with the exchange axiom (—M I '-EXC[Z]) for U and, therefore,
Finally, we mention that the submodularity (11.19) of U is equivalent to the submodularity of U:
Note 11.8. Utility functions are to be maximized by consumers. As is discussed in Note 10.16, however, maximizing a general submodular set function is computationally intractable. M^-concave utility functions form a subclass of submodular functions that can be maximized efficiently. • Note 11.9. We mention here some examples of M^-concave utility functions treated explicitly or implicitly in the literature of indivisible commodities. See also the examples of M^-convex functions shown in section 6.3. (1) A separable concave function
denned in terms of a family of univariate discrete concave functions (ui \ i € K) (i.e., — Ui 6 C[Z —> R]) is an M^-concave function (see (6.31)).
334
Chapter 11. Application to Mathematical Economics
(2) A quasi-separable concave function
defined in terms of a family of univariate discrete concave functions (ui i G /•CU{0}) (i.e., -Ui G C[Z —> R]) is an M^-concave function (see (6.32)). (3) Given a vector (0, | i & K) G RK, we denote by U(X) the maximum value of di with index i belonging to X C K. More formally, choosing a* G R U { —00} with a* < muiigx a^, we define a set function E7 : 2K —> R U {—00} by
Identifying X with its characteristic vector Xx and imposing monotonicity, we obtain a function U : ZK —>• R U {—00} given by
This is an M^-concave function. The function U represents a unit demand preference. •
11.4
Existence of Equilibria
We prove the existence of equilibria by establishing two statements: (i) an equilibrium price can be characterized as a nonnegative subgradient of the aggregate cost function and (ii) under the assumption of M^-convexity/concavity of individual cost functions and utility functions, the aggregate cost function is an M^-convex function for which the subdifferential is nonempty.
11.4.1
General Case
The conditions Xh G Dh(p) and yi G Si(p) in (11.9) and (11.10) can be rewritten by (3.30) as
using the notations for subdifferentials defined in (8.19) and (6.86). Hence, p G R+ is an equilibrium price if and only if it satisfies (11.22) for some x^ G domC/h, (h G H) and yi G domC1; (I G L) meeting the supply-demand balance (11.14) for the given total initial endowment x°. Furthermore, if ((xh h G H), (yi I G L),p) is an equilibrium, the set P*(x°) of all equilibrium prices for x° is expressed as
11.4.
Existence of Equilibria
335
In particular, the right-hand side of this expression is independent of the choice of an equilibrium allocation ((xh h 6 H), (yi \ I & L)). We define the aggregate cost function ^> : ZK —> R U {+00} by
This is the integer infimal convolution (6.43) of producers' cost functions and the negatives of consumers' utility functions. Owing to our assumptions that • dom Uh is bounded for each h £ H, and • domC; is bounded for each / € L, the infimum in (11.24) is attained for each z in
where the right-hand side is a Minkowski sum in ZK (see (6.44)). Proposition 11.10. For a total initial endowment x°, the following statements hold true under the boundedness assumption on dom Uh for h e H and dom C\ for l&L. (1) There exists an equilibrium if and only if x° G dom* and (—dR^(x°)) D R*^0.
(2)p'(x°) = (-dR<Sf(x°»nnx.
(3) I f ( ( x h h e H), (yi | I e L)) satisfies (11.9), (11.10), and (11.14) for some p (not necessarily nonnegative), then
and ((XH | h e H), (yi \ I e L),p') is an equilibrium for any p' e (—0R\l/(a;°)) nR^. Proof. Definition (11.24) can be rewritten as
which shows
Therefore, we have
336
Chapter 11. Application to Mathematical Economics
Figure 11.4. Aggregate cost function 'f and its convex closure fy for an exchange economy with no equilibrium.
If ((xh h G H ) , ( y i | I 6 L),p) is an equilibrium, we have x^ € argmaxt/ft,[— p] (h 6 H), yi e argminC;[—p] (I e L), and (11.14), from which follows
Since p e R£, we have p e (-<9R#(:r0)) n R£. Conversely, for p e (-^R*(X°)) n R£, we have *[p](x°) = inf*[p]. Let (xfc | /i e jf?) and (?/; | I G L) be vectors that attain the minimum on the right-hand side of (11.28) for z = x°. Then we have (11.30) and hence Xh e arg max Uh [—p] (h e H) and yi e argminC t [-p] (I € L) by (11.29). This means that ((xh h £ H), (yi I € L),p) is an equilibrium. The expression (11.26) follows from the above argument. D Proposition 11.10 suggests that if a difficulty in the discreteness of indivisible commodities exists, it should be reflected in the emptiness of the subdifferential dR^(x°). Example 11.11. Let us investigate the previous example (section 11.2) of an exchange economy with no equilibrium. The aggregate cost function ^ takes the values shown in Fig. 11.4 (left), where dom * = [0,2]z x [0,2]z- The convex closure * of # is given on the right of Fig. 11.4. Since #(1,1) ^ *(!,!), ^,#(1,1) is empty and, by Proposition 11.10, no equilibrium exists for x° = (1,1). For x° = (1,2), on the other hand, p = (2,1) is an equilibrium price since (2,1) e ( — d n ^ ( x ° ) ) n R^_. •
11.4.
Existence of Equilibria
11.4.2
337
M"-Convex Case
The M^-concavity of utility functions and the M^-convexity of cost functions are key to the existence of equilibria, as well as to a desirable structure of equilibrium prices. In Proposition 11.10 we saw that the existence of an equilibrium is almost equivalent to the existence of a subgradient of \I>. The latter is guaranteed under M^-concavity/convexity as follows. Proposition 11.12. LetUh (h £ H) be A^-concave functions withdomUh bounded and Ci (I £ L) be Aft-convex functions with domCi bounded. Then $> is an Aflconvex function and ^^(x0) ^ 0 for any x° £ dom^. Proof. By the assumption, ^ is an infimal convolution of M^-convex functions, which is M^-convex by Theorem 6.15. The second claim follows from Theorem 6.61 (2). D We shall present three theorems on the existence of equilibria. The first is for an exchange economy (with L = 0). Theorem 11.13. Consider an exchange economy with agents indexed by H and suppose that Uh (h £ H) are nondecreasing A/*1 -concave functions with domUh bounded. Then there exists an equilibrium ((x^ \ h £ H ) , p ) for every x° £ Eft 6 H d o m ^Proof. We use Proposition 11.10. Since &R^!(X°) ^ 0 by Proposition 11.12, it suffices to show the nonnegativity of (any) p 6 — d^(x°}. The function U(z) = —*&(z) is nondecreasing and Putting z = x° + axi and letting a —> +00, we see that p(i) > 0. We next consider the existence of equilibria in the general case with consumers and producers. To separate discreteness issues from topological ones, we consider an embedding of our discrete model in a continuous space, just as we have done for the simple exchange economy in section 11.2. Utility functions Uh, being M^-concave, are extensible to concave functions Uh '• Rx -> RU{-oo}. Similarly, cost functions Ci, being M^-convex, are extensible to convex functions Ci : RK —» RU {+00}. Then demand correspondences Dh for h £ H and supply correspondences Si for I £ L are defined, respectively, as
Note that Dh(p) and §i(p) coincide respectively with the convex hulls Dh(p) and Si(p) of Dh(p) and Si(p). We define an equilibrium in the continuous model as a
338 tuple ((xh\heH),(yi
Chapter 11. Application to Mathematical Economics I e L),p) of xh & RK, yt e RK, and p 6 R£ satisfying
as well as the supply-demand balance (11.14) and the price nonnegativity (11.12). The following theorems state that the existence of an equilibrium in the continuous model implies that of an equilibrium for indivisible commodities under our assumption of M^-concavity/convexity. We emphasize here that this is by no means a general phenomenon, as we have seen in section 11.2, but is peculiar to M^concavity/convexity. For topological issues, the reader is referred to the literature in economics indicated in Note 11.2. Theorem 11.14. Suppose that utility functions UH (h G H) are Afl -concave and cost functions Ci (I € L) are Afl-convex. If the derived continuous economy has an equilibrium satisfying (11.33), (11.34), (11.14), and (11.12) for a total initial endowment x° e Z^, there exists an equilibrium of indivisible commodities for x° satisfying (11.9), (11.10), (11.14), and (11.12). Proof. By Theorem 11.7, Dh(p) and Si(p) are M^-convex sets if they are not empty. Hence, the claim follows from Theorem 11.15 below. D Theorem 11.15. Suppose that, for eachp € R+, demand sets DH(P) (h £ H) and supply sets Si(p) (I € L) are Afl-convex if they are not empty. If the derived continuous economy has an equilibrium satisfying (11.33), (11.34), (11.14), and (11.12) for a total initial endowment x° e Z+, there exists an equilibrium of indivisible commodities for x° satisfying (11.9), (11.10), (11.14), and (11.12). Proof. For an equilibrium price p e R+ in the continuous model, we have
On noting Dh(p) = Dh(p) and §i(p) = Si(p), as well as Theorem 4.12 and Proposition 3.17 (4), we see
By Theorem 4.23 (3), on the other hand, J2h€H ^h(p)-^2ieL &i(p) *san M^-convex set, which is hole free by Theorem 4.12. Hence follows
which shows (11.15).
11.4.
Existence of Equilibria
339
Finally we consider the structure of equilibrium prices. Theorem 11.16. Suppose that utility functions Uh (h € H) are Afl-concave and cost functions Ci (I 6 L) are Afi -convex and that there exists an equilibrium for a total initial endowment x°. Then the set P*(x°) of all the equilibrium price vectors is an L^-convex polyhedron. This means, in particular, that p, q € P*(x°) => p V q, pf\q&P*(x°), which implies the existence of the smallest and the largest equilibrium price vectors. Proof. The subdifferentials d^Uh(xh) (h e H) and &R.Ci(yi) (I e L) in (11.23) are lAconvex polyhedra by Theorem 6.61 (2). Since R+ is L^-convex and the intersection of L''-convex polyhedra is L''-convex, P*(x°) is an L''-convex polyhedron. As we have seen in the above, we have the correspondence
Note 11.17. Inspection of the proof of Theorem 11.15 shows that it relies solely on the following two properties of M^-convex sets: (i) M^-convex sets are hole free and (ii) Minkowski sums of M^-convex sets are M^-convex sets. This suggests a generalization of Theorem 11.15 for a class J- of sets of integer points such that (i) 5 e T, x e ZK =>• S = 5 n ZK, x - S e T, and (ii) Si, 52 E f => Si + S2 e T (cf. Proposition 3.16). Namely, if Dh(p) e T (h e H) and Si(p) e F (I £ L) for each p e R^f, where we assume 0 € F, and if the derived continuous economy has an equilibrium, then there exists an equilibrium for indivisible commodities. Note 11.18. In an exchange economy with two agents, an equilibrium exists under the L11-concavity of utility functions or the L1'-convexity of demand sets. (1) If the utility functions C/i and C/2 are nondecreasing L^-concave functions, an equilibrium exists for any x° & domC/i + dom[/2 (cf. Theorem 11.13). (2) Suppose that the utility functions C/i and f/2 are L^-concave. If the derived continuous economy has an equilibrium for x° 6 Z^f, there exists an equilibrium for indivisible commodities (cf. Theorem 11.14). (3) Suppose that, for each p e R+, the demand sets -Di(p) and D2(p) are iJconvex if they are not empty. If the derived continuous economy has an equilibrium for x° & Z+, there exists an equilibrium for indivisible commodities (cf. Theorem 11.15). Proof: (1) In the proof of Theorem 11.13, * is an L2-convex function and, therefore, 5a*(x°) ^ 0 by Theorem 8.45. (2) In the proof of Theorem 11.14, D\(p) and D2(p) are lAconvex or empty. Hence the claim follows from (3) by Proposition 7.16. (3) This follows from the proof of Theorem 11.15 by virtue of the convexity in Minkowski sum for L^-convex sets (Theorem 5.8). •
Chapter 11. Application to Mathematical Economics
340
11.5
Computation of Equilibria
In this section we show an algorithmic procedure to compute an equilibrium in the case where C\ are M^-convex and Uh are M^-concave. We use the framework of the M-convex submodular flow problem MSFP2, introduced in section 9.2. The solution to this problem yields consumptions and productions satisfying (11.9), (11.10), and (11.14), as well as a price vector, which, however, may not be nonnegative. This constitutes the first phase of our algorithm. The second phase finds an equilibrium price vector by solving a shortest path problem. We can modify the second phase so that we can find the smallest or the largest equilibrium price vector. For an M^-convex cost function Ci : ZK —•> R U {+00}, we define the corresponding M-convex function Cj : Z^UK —> RU {+00} by
compatibly with (6.4). We also define the M-concave function R U {-00} associated with Uh : ZK -> R U {-00} by
In accordance with (11.24), we consider the aggregate cost function
Obviously, we have
for the aggregate cost function ^ defined in (11.24). For the total initial endowment z° e ZK, we put x° = (-x°(K),x°) € Z<°> UK . The function \I>, being an integer infimal convolution of M-convex functions, is also M-convex and can be evaluated by solving an MSFP2 (see Note 9.30). A concrete description is given below. The instance of MSFPa for the evaluation of ^(x°) is defined on a directed bipartite graph G = (V+,V~,A) with vertex partition (V+,V~) and arc set A given by
11.5.
341
Computation of Equilibria
Figure 11.5. Graph for computing a competitive equilibrium. Note that V+, Vt+, and VJj" are copies of {0}(JK. Figure 11.5 illustrates the graph G for H = {a, /?}, L = {A, B}, and K = {1,2}. For each arc a € A, we put c(a) = —oo, c(a) = +00, and 7(0) = 0. Using the indicator function 5^°} '• %Ve —> {0, +00} of {x°}, we define a function / : Zv+uv~ -> R U {+00} by
where w G Z1^ , yi G Z17; for / G L, and i^ G Zvh for h £ H. The function / is M-convex, since C1/ (I G L) are M-convex and Uh (h G #) are M-concave. This is the instance of the MSFP2 that we use for the computation of ^>(x°). The optimal flow and the optimal potential for the MSFP2 above give the allocation and the price vector in the equilibrium, as is stated later in Theorem 11.20. The following proposition is a lemma for it. Proposition 11.19. Let £ G ZA be an optimal flow andp G R y + u y potential for the above instance of MSFP2. Define66
be an optimal
and regard x*h, y*, w*, and p as vectors on {0} U K. (1) w* = x°, x*h(0) = -x*h(K) for h&H, and ft (0) = - y f ( K ) for I G L.
(2)£° + E J6i i/r = E h€ fl^-
(3) p(fc-) = p(fc+) = p(k+) for k G {0} U K, h G H, and I G L. (4) x*h G arg max Uh [—P] for h £ H and y* G arg min Ci [— p] for I & L. Proof. (1) is obvious from the definitions of Ci, Uh, and 6^°}- By the structure of G, for each k G {0} U K, we have
66
The notation —d£\v- designates the restriction of —d£ to Vh . Hence x*h = — d(,\v- means
*J(fc) = -ae(fc)forfcev- h -.
342
Chapter 11. Application to Mathematical Economics
This means (2), since w* = x° by (1). Since 7(0) = 0, c(a) = —oo, and c(a) = +00 for any a e A, condition (i) of (POT) of Theorem 9.16 implies p(d+a) — p(d~a) = 0 for all a G A. This implies (3). It follows from (3) that
We also have
Then (4) follows from (ii) of (POT) in Theorem 9.16, (11.35), and (11.37). The following theorem, an immediate consequence of Proposition 11.19, shows that consumptions and productions satisfying (11.9), (11.10), and (11.14) can be obtained from a solution to the above instance of MSFP2 and that, if the optimal potential is nonnegative, then it serves as an equilibrium price vector. Theorem 11.20. Let £ e ZA be an optimal flow and p e Ry uv potential with p(Q+) = 0 for the above instance O/MSFP2. Define
be an optimal
and regard x*h, y*, and p as vectors on K. Then we have
Therefore, ((x*h h & H),(yf \ I & L},p) is an equilibrium if p > 0. Moreover, if there exists an equilibrium at all, then ((x*h h e H), (yf \ I 6 L)) is the consumptions and productions of some equilibrium. Any algorithm for the MSFP2 will find a tuple ((x*h h e H), (yf I € L),p), which gives an equilibrium for the total initial endowment x° if the optimal potential p happens to be nonnegative. We go on to consider the set of all nonnegative optimal potentials or, equivalently, the set of all equilibrium price vectors. We already know from Theorem 11.16 that the set is an L^-convex polyhedron, and our objective here is to derive a concrete description in terms of a linear inequality system. With this knowledge, the existence of an equilibrium price vector can be checked by solving
11.5.
Computation of Equilibria
343
a linear programming problem, which can be reduced to the dual of a single-source shortest path problem. Recall from (11.23) that the set P*(x°) of all equilibrium price vectors for x° is expressed as
in which we have
by (3.30). By Theorem 6.26 (2) (M-optimality criterion), we have y^ e arg min Ci [—p] if and only if
and x*h e argmax[/h[—p] if and only if
By defining
we obtain a concrete representation of P*(x°) as follows. Note that l(j) < +00, u(j) > — oo, and u(i,j] > —oo for any i,jEK(i^ j). Theorem 11.21. The set P*(x°) of all equilibrium price vectors is an ifi-convex polyhedron described as
with l ( j ) , u ( j ) , and u(i,j) defined in (11.40), (11.41), and (11.42). By Theorem 11.21, the nonemptiness of P*(x°) can be checked by linear programming. In particular, the largest equilibrium price vector, if any, can be
344
Chapter 11. Application to Mathematical Economics
found by solving a linear programming problem:
Similarly, the smallest equilibrium price vector can be found by solving another linear programming problem:
Both (11.44) and (11.45) can be easily reduced to the dual of a single-source shortest path problem. Theorem 11.22. There exists an equilibrium price vector if and only if the problem (11.44) is feasible. The smallest and the largest equilibrium price vectors, if any, can be found by solving the shortest path problem. Thus, the existence of a competitive equilibrium in our economic model with M^-convex cost functions of producers and M^-concave utility functions of consumers can be checked in polynomial time by the following algorithm. Algorithm for computing an equilibrium SO: Construct the instance of the MSFP2. SI: Solve the MSFP2 to obtain ( ( x * h \ h & H ) , (yf \leL),p). (If MSFPg is infeasible, no equilibrium exists.) S2: Solve the problem (11.44) to obtain an equilibrium ((x*h \ h € H), (yf I e L),p*) with largest p*. (If (11.44) is infeasible, no equilibrium exists.) Whereas the above algorithm yields the largest equilibrium price vector, the smallest price vector can be computed by solving (11.45) instead of (11.44) in step S2.
Bibliographical Notes The unified framework for indivisible commodities by means of discrete convex analysis is proposed in Danilov-Koshevoy-Murota [34], [35], to which Theorems 11.14 and 11.15 as well as Notes 11.9 and 11.17 are ascribed. Theorem 11.16 for the structure of equilibrium prices and Note 11.18 are by Murota [147]. The gross substitutes property was introduced by Kelso-Crawford [111] and investigated thoroughly by Gul-Stacchetti [84], in which the equivalence of (GS), (SI), and (NC) is proved. The connection of these conditions to M^-concavity was pointed out by Fujishige-Yang [69] for set functions, with subsequent generalizations by Danilov-Koshevoy-Lang [33] (Theorem 11.6) and Murota-Tamura [160] (Theorems 11.4 and 11.5). See Roth-Sotomayor [180] for more on (GS).
11.5.
Computation of Equilibria
345
The computation of an equilibrium via an M-convex submodular flow problem described in section 11.5 is due to Murota-Tamura [161]. M-convexity is also amenable to the stable marriage problem (stable matching problem) of Gale-Shapley [74], which is one of the most applicable models in economics and game theory. Eguchi-Fujishige [47] formulates a generalization of the stable marriage problem in terms of M^-convex functions and presents an extension of the Gale-Shapley algorithm. Submodularity plays important roles in economics and game theory. We mention here the paper of Shapley [186] as an early contribution and Bilbao [14], Danilov-Koshevoy [31], Milgrom-Shannon [129], and Topkis [203] as recent literature.
This page intentionally left blank
Chapter 12
Application to Systems Analysis by Mixed Matrices This chapter presents an application of discrete convex analysis to systems analysis by mixed matrices. Motivated by a physical observation to distinguish two kinds of numbers appearing in descriptions of physical/engineering systems, the concepts of mixed matrices and mixed polynomial matrices are introduced as mathematical tools for dealing with two kinds of numbers in systems analysis. Discrete convex functions arise naturally in this context and the discrete duality theorems are vital for the analysis of the rank of mixed matrices and the degree of determinants of mixed polynomial matrices.
12.1
Two Kinds of Numbers
A physical/engineering system can be characterized by a set of relations among various kinds of numbers representing physical quantities, parameter values, incidence relations, etc., where it is important to recognize the difference in the nature of the quantities involved in the problem and to establish a mathematical model that reflects the difference. A primitive, yet fruitful, way of classifying numbers is to distinguish nonvanishing elements from zeros. This dichotomy often leads to graph-theoretic methods for systems analysis, where the existence of nonvanishing numbers is represented by a set of arcs in a certain graph. Closer inspection reveals, however, that two different kinds can be distinguished among the nonvanishing numbers; some of the nonvanishing numbers are accurate in value and others are inaccurate in value but independent of one another. We may alternatively refer to the numbers of the first kind as fixed constants and to those of the second kind as system parameters. Accurate numbers (fixed constants): Numbers accounting for various sorts of conservation laws, such as Kirchhoff's laws, which, stemming from the topological incidence relation, are precise in value (often ±1). Inaccurate numbers (system parameters): Numbers representing independent
347
348
Chapter 12. Application to Systems Analysis by Mixed Matrices
Figure 12.1. Electrical network with mutual couplings.
physical parameters, such as resistances in electrical networks and masses in mechanical systems, which, being contaminated with noise and other errors, take values independent of one another. It is emphasized that the distinction between accurate and inaccurate numbers is not a matter in mathematics but in mathematical modeling, i.e., the way in which we recognize the problem. This means in particular that it is impossible in principle to give a mathematical definition to the distinction between the two kinds of numbers. The objective of this section is to explain, by means of typical examples, what is meant by accurate and inaccurate numbers and how numbers of different nature arise in mathematical descriptions of physical/engineering systems. We consider three examples from different disciplines: an electrical network, a chemical process, and a mechanical system. Example 12.1. Consider the electrical network in Fig. 12.1, which consists of five elements: two resistors of resistances Ti (branch i) (i = 1,2), a voltage source (branch 3) controlled by the voltage across branch 1, a current source (branch 4) controlled by the current in branch 2, and an independent voltage source of voltage e (branch 5). The element characteristics are represented as
where & and rn are the current in and the voltage across branch i (i = 1 , . . . , 5) in the directions indicated in Fig. 12.1. We then obtain the following system of equations:
12.1.
Two Kinds of Numbers
349
The upper five equations are the structural equations (Kirchhoff's laws), while the remaining five are the constitutive equations. The nonzero coefficients, ±1, appearing in the structural equations represent the incidence relation in the underlying graph and are certainly accurate in value. The entries of —1 contained in the constitutive equations are also accurate by definition. In contrast, the values of the physical parameters ri, r2, a, and (3 are likely to be inaccurate, being only approximately equal to their nominal values on account of various kinds of noises and errors. The unique solvability of this network amounts to the nonsingularity of the coefficient matrix of (12.1). A direct calculation shows that the determinant of this matrix is equal to r-2 + (1 — a)(l + /3)ri, which is highly probably distinct from zero by the independence of the physical parameters {ri,r2,a,/?}. Thus, the electrical network of this example is solvable in general or, more precisely, solvable generically with respect to the parameter set {ri,r 2 ,a,/?}. The solvability of this system will be treated in Example 12.11 by a systematic combinatorial method (without direct computation of the determinant). • The second example concerns a chemical process simulation. Example 12.2. Consider a hypothetical system (Fig. 12.2) for the production of ethylene dichloride (C2H4C12), which is slightly modified from an example used in the Users' Manual of Generalized Interrelated Flow Simulation of The Service Bureau Company. Feeds to the system are 100 mol/h of pure chlorine (Ck) (stream 1) and 100 mol/h of pure ethylene (C2H 4 ) (stream 2). In the reactor, 90% of the input ethylene is converted into ethylene dichloride according to the reaction formula
At the purification stage, the product ethylene dichloride is recovered and the unreacted chlorine and ethylene are separated for recycling. The degree of purification is described in terms of the component recovery ratios 01, 02, and 03 of chlorine, ethylene, and ethylene dichloride, respectively, which indicate the ratios of the amounts recovered in stream 6 of the respective components over those in stream 5. We consider the following problem:
350
Chapter 12. Application to Systems Analysis by Mixed Matrices
Figure 12.2. Hypothetical ethylene dichloride production system. Given the component recovery ratios ai and a-2 of chlorine and ethylene, determine the recovery ratio x = 03 of ethylene dichloride with which a specified production rate y mol/h of ethylene dichloride is realized. Let un, Ui2, and Ui3 mol/h be the component flow rates of chlorine, ethylene, and ethylene dichloride in stream i, respectively. The system of equations to be solved may be put in the following form, where u is an auxiliary variable in the reactor and r (= 0.90) is the conversion ratio of ethylene:
This is a system of linear/nonlinear equations in the unknown variables x, u, and Uij, where the equation UQS = x u53 in the purification is the only nonlinear equation. We may regard a, (j = 1,2) and r (— 0.90) as inaccurate and independent numbers. The stoichiometric coefficients in the reaction formula (12.2) are accurate numbers. The Jacobian matrix of (12.3), shown in Fig. 12.3, contains five inaccurate numbers, ai, oi2, r, x, and 1^53. The solvability of this problem will be treated in Example 12.12. Example 12.3. Consider the mechanical system in Fig. 12.4 consisting of two masses m\ andTO2,two springs fci and fc2, and a damper /; u is the force exerted
12.1.
Two Kinds of Numbers
351
Figure 12.3. Jacobian matrix in the chemical process simulation. from outside. This system may be described by vectors x = (xi,X2,X3,x 4 ,X5,o; 6 ) and u = (u), where x\ and x2 are the vertical displacements (downward) of masses m\ and m^, #3 and x± are their velocities, £5 is the force by the damper /, and XQ is the relative velocity of the two masses. The governing equation is
We may regard {rni,m2, &i, &2, /} as independent system parameters and other nonvanishing entries (i.e., ±1) of F, A, and B as fixed constants. The Laplace transform67 of the equation (12.4) gives a frequency domain description
where o;(0) = 0 and it(0) = 0 are assumed. The coefficient matrix [A — sF B] is a polynomial matrix in s with coefficients depending on the system parameters. 67
See Chen [23] or Zadeh-Desoer [220] for the Laplace transform.
352
Chapter 12. Application to Systems Analysis by Mixed Matrices
Figure 12.4. Mechanical system.
We have employed a six-dimensional vector x in our description of the system. It is possible, however, to describe this system using a four-dimensional state vector. The minimum dimension of the state vector is known to be equal to the degree in s of the determinant of
Thus the number degdet[A — sF] is an important characteristic, sometimes called the dynamical degree, of the system (12.4). As illustrated by the examples above, accurate numbers often appear in equations for conservation laws such as Kirchhoff's laws; the law of conservation of mass, energy, or momentum; and the principle of action and reaction, where the nonvanishing coefficients are either 1 or — 1, representing the underlying topological incidence relations. Another typical example is integer coefficients (stoichiometric coefficients) in chemical reactions such as
where nonunit integers such as 2 appear. In dealing with dynamical systems, we encounter another example of accurate numbers that represent the defining relations, such as those between velocity v and position x and between current £ and charge Q:
12.2.
Mixed Matrices and Mixed Polynomial Matrices
353
Figure 12.5. Accurate numbers. Typical accurate numbers are illustrated in Fig. 12.5. The rather intuitive concept of two kinds of numbers will be given a mathematical formalism in the next section.
12.2
Mixed Matrices and Mixed Polynomial Matrices
The distinction of two kinds of numbers can be embodied in the concepts of mixed matrices and mixed polynomial matrices. Assume that we are given a pair of fields F and K, where If is a subfield of F. Typically, K is the field Q of rational numbers and F is a field large enough to contain all the numbers appearing in the problem in question. In so doing we intend to model accurate numbers as numbers belonging to K and inaccurate numbers
Chapter 12. Application to Systems Analysis by Mixed Matrices
354
as numbers in F that are algebraically independent over K, where a family of numbers ti,..., tm of F is called algebraically independent over K if there exists no nonzero polynomial p(X\,..., Xm) over K such that p(ti,..., tm) = 0. Informally, algebraically independent numbers are tantamount to free parameters. A matrix A = (A^) over F, i.e., Aij e F, is called a mixed matrix with respect to (K, F) if where (M-Q) Q = (Qij) is a matrix over K and (M-T) T = (Tij) is a matrix over F such that the set of its nonzero entries is algebraically independent over K. We usually assume to make the decomposition (12.7) unique. Example 12.4. In the electrical network of Example 12.1 it is reasonable to regard {TI, r2, a, (3} as independent free parameters. Then the coefficient matrix in (12.1) is a mixed matrix with respect to (K, F) = (Q, Q(ri, r2, a, /?)), where Q(ri, r%, a, j3) means the field of rational functions in r\,r2,a,(3 with coefficients from Q. The decomposition A = Q + T is given by
Consider now a polynomial matrix in s with coefficients from F:
12.2.
Mixed Matrices and Mixed Polynomial Matrices
355
where Ak (k = 0 , 1 , . . . , N) are matrices over F. We say that A(s) is a mixed polynomial matrix with respect to (K, F) if it can be represented as
with
where (MP-Q) Qk (k = 0,1,..., N) are matrices over K and (MP-T) Tk (k = 0 , 1 , . . . , N) are matrices over F such that the set of their nonzero entries is algebraically independent over K. Obviously, the coefficient matrices
are mixed matrices with respect to (K, F). Also note that A(s) is a mixed matrix with respect to (K(s), F ( s ) ) in spite of the occurrence of the variable s in both Q(s) and T(s), where K(s) and F(s) denote the fields of rational functions in variable s with coefficients from K and JF, respectively. Mixed polynomial matrices are useful in dealing with linear time-invariant dynamical systems. The variable s here is primarily intended to denote the variable for the Laplace transform for continuous-time systems, though it could be interpreted as the variable for the z-transformes for discrete-time systems. Example 12.5. In the mechanical system of Example 12.3 it is reasonable to regard {mi,TO2, ki,kz, /} as independent free parameters. Then the matrix A(s) in (12.6) is a mixed polynomial matrix with respect to (K,F) = (Q, Q(rni,m2,fci,/c 2 ,/)). The decomposition A(s) = Q(s) + T(s) is given by
Our intention in the splitting (12.7) or (12.8) is to extract a meaningful combinatorial structure from the matrix A or A(s) by treating the Q-part numerically and the T-part symbolically. This is based on the following observations. 68
See Chen [23] or Zadeh-Desoer [220] for the z-transform.
356
Chapter 12. Application to Systems Analysis by Mixed Matrices
Q-part: As is typical with electrical networks, the Q-part primarily represents the interconnection of the elements. The Q-matrix, however, is not uniquely determined, but is subject to our choice in the mathematical description. In the electrical network of Example 12.1, for instance, the coefficient matrix
for Kirchhoff 's voltage law may well be replaced with
Accordingly, the structure of the Q-part should be treated numerically or linear algebraically. In fact, this is feasible in practice, since the entries of the Q-matrix are usually small integers, causing no serious numerical difficulty in arithmetic operations. T-part: The T-part primarily represents the element characteristics. The nonzero pattern of the T-matrix is relatively stable against our choice in the mathematical description of constitutive equations, and therefore it can be regarded as representing some intrinsic combinatorial structure of the system. It can be treated properly by graph-theoretic concepts and algorithms. Combination: The structural information from the Q-part and the T-part can be combined properly and efficiently by virtue of the fact that each part defines a combinatorial structure with discrete convexity (matroid or valuated matroid, to be more specific). Mathematical and algorithmic results in discrete convex analysis (matroid theory and valuated matroid theory) afford effective methods of systems analysis. We may summarize the above as follows: Q-part by linear algebra T-part by graph theory Combination by matroid theory
12.3
Rank of Mixed Matrices
The rank of a mixed matrix A = Q + T can be expressed in terms of the L^-convex functions (submodular set functions) associated with Q and T. This enables us, for example, to test efficiently for the solvability of the electrical network in Example 12.1 and of the chemical process simulation problem in Example 12.2. Let A = Q + T be a mixed matrix with respect to (K,F). The rank of A is denned with reference to the field F. That is, the rank of A is equal to (i) the maximum number of linearly independent column vectors of A with coefficients taken from F, (ii) the maximum number of linearly independent row vectors of A with coefficients taken from F, and (iii) the maximum size of a submatrix of A for
12.3.
Rank of Mixed Matrices
357
which the determinant does not vanish in jF. The row set and the column set of A are denoted by R and C, respectively. For / C R and J C C, the submatrix of A with row indices in / and column indices in J is designated by A[I, J]. We start with the nonsingularity of a mixed matrix. Proposition 12.6. A square mixed matrix A = Q + T is nonsingular if and only if there exist some I C R and J C C such that both Q[I, J] and T[R \I,C\J] are nonsingular. Proof. It follows from the denning expansion of the determinant that
with e(I, J) e {1, —1}. If A is nonsingular, we have det A^Q and hence det Q[I, J] • det T[R \ /, C \ J} ^ 0 for some / and J. The converse is also true, since no cancellation occurs among nonzero terms on the right-hand side by virtue of the algebraic independence of the nonzero entries of T. The following is a basic rank identity for a mixed matrix. Theorem 12.7. For a mixed matrix A = Q + T,
Proof. Proposition 12.6 applied to submatrices of A establishes (12.9).
D
The right-hand side of the identity (12.9) is a maximization over all pairs (/, J), the number of which is as large as 2' fl l + l c 'l, too large for an exhaustive search for maximization. Fortunately, however, it is possible to design an efficient algorithm to compute this maximum on the basis of the following facts: • The function p ( I , J) = rankQ[7, J] can be evaluated easily by Gaussian elimination. • The function r(I, J) = rankTf/, J] can be evaluated easily by finding a maximum matching in a bipartite graph representing the nonzero pattern of T. • The maximization can be converted, with the aid of Edmonds's intersection theorem for matroids (a special case of Theorem 4.18), to the minimum of an L''-convex function. To state the main theorem of this section we need another function 7 : 2R x 2° -> Z denned by
Note that 7(7, J) represents the number of nonzero rows of the submatrix T[I, J}.
358
Chapter 12. Application to Systems Analysis by Mixed Matrices
Theorem 12.8. For a mixed matrix A = Q + T,
Proof. (12.10) can be proved from (12.9) with the aid of Edmonds's intersection theorem for matroids (a special case of Theorem 4.18) and (12.11) can be derived from (12.10) using the formula which is a version of the fundamental min-max relation between maximum matchings and minimum covers. (12.12) follows easily from (12.11). For details see the proofs of Theorem 4.2.11 and Corollary 4.2.12 of Murota [146]. We mention the following theorem as an immediate corollary of the third identity (12.12). Note the duality nature of this theorem. Theorem 12.9 (Konig-Egervary theorem for mixed matrices). For a mixed matrix A = Q + T, there exist I C R and J C C such that (i) |/| + |J| -rankQ[7, J] = \R\ + \C\ -rankA, and (ii) rankT[J, J] =0. Proof. Take (/, J) that attains the minimum in (12.12).
D
To see the connection of the above rank formulas to L''-convexity, we define three functions gp,gr^9-y '• ZR(JC —> Z U {+00}, with domgp = domgr = domg7 {0,l}*uc,by
Proposition 12.10. gp, gT, and g^ are Lfi-convex functions. Proof. It is easy to see that p(I(JJ) = p(R\I, J) +1/| is a submodular set function on R U C (see (2.70)). This is equivalent to the L''-convexity of gp by Theorem 7.1, and similarly for gT and 7. D We can rewrite the right-hand sides of (12.10) and (12.11) using these Lficonvex functions. Namely, we see
12.4.
Degree of Determinant of Mixed Polynomial Matrices
359
where 1 e ZRuC. Note that both gp + gT and gp + #7 are lAconvex and therefore (gp + gT)' and (gp + g^)9 are M^-convex. As for (12.12) we observe that
is an L'-convex set and
This shows that the right-hand side of (12.12) is the minimum of an lAconvex function over an L^-convex set. The discrete convexity implicit in Theorem 12.8 is thus exposed. A concrete algorithmic procedure for computing the rank of A = Q + T is described in section 4.2 of Murota [146]. Example 12.11. The unique solvability of the electrical network in Example 12.1 can be shown by Theorem 12.7 applied to A = Q + T in Example 12.4. In (12.9) the maximum value of 10 is attained by / = {1,2,3,4,5,7,10} and J = {3,4,5,7,8,9,10}. In Theorem 12.8 the right-hand sides of (12.10), (12.11), and (12.12) are equal to 10 with the minima attained by / = R and J = 0. Example 12.12. The generic solvability of the chemical process simulation problem in Example 12.2 is denied by Theorem 12.8 applied to the Jacobian matrix in Fig. 12.3. In (12.12) the minimum is attained by
Note that 7(7, J) = 0, |J| = |J| = 10, and p ( I , J ) = 3, for which p ( I , J ) - \I\ \J\ + \R\ + \C\ = 3 - 10 - 10 + 16 + 16 = 15 < \R\ = \C\ = 16. This shows that t Jacobian matrix in Fig. 12.3 is singular, and hence the simulation problem is not solvable in general.
12.4
Degree of Determinant of Mixed Polynomial Matrices
The degree of determinant of a mixed polynomial matrix A(s) = Q(s)+T(s) can be expressed in terms of the infimal convolution of two M-convex functions associated with T(s) and Q(s). This enables us, for example, to compute the dynamical degree of the mechanical system in Example 12.3 in an efficient way by solving an M-convex submodular flow problem. Let A(s) = (Aij(s)) be a polynomial matrix with each entry being a polynomial in s with coefficients from a certain field F. We denote by R and C the row set and the column set of A(s). The degree of minors (subdeterminants) is an important characteristic of A(s). For example, the sequence of 6k (k = 1, 2 , . . . ) of the highest degree in s of a minor of order fc,
360
Chapter 12. Application to Systems Analysis by Mixed Matrices
determines the Smith-McMillan form at infinity as well as the structural indices of the Kronecker form (see section 5.1 of Murota [146]). Here the function to be maximized in (12.13) is essentially M-concave, since w : 2,RUC —> Z U {—00} defined by o>(/ U J) = 5(R \ I, J) for / C R and J C C is a valuated matroid (see (2.74) and (2.77) as well as Example 5.2.15 of Murota [146]). The following is the basic identity for the degree of the determinant of a mixed polynomial matrix. Theorem 12.13. For a square mixed polynomial matrix A(s) = Q(s) + T(s), degdet^ = max{degdetQ[7, J]+degdetT[R\I,C\
J] \ \I\ = \ J\,I C R, J C C}, (12.14)
where both sides are equal to —oo if A is singular. Proof. It follows from the denning expansion of the determinant that
with e ( I , J ) 6 {!,—!}. Since the degree of a sum is bounded by the maximum degree of a summand, we obtain
The inequality turns into an equality if the highest degree terms do not cancel one another. The algebraic independence of the nonzero coefficients in T(s) ensures this. D The right-hand side of the identity (12.14) is a maximization over all pairs (7, J), the number of which is as large as '2\R\+\C\, too large for an exhaustive search for maximization. Fortunately, however, it is possible to compute this maximum efficiently by reducing this maximization problem to the M-convex submodular flow problem. To see the connection to M-convexity, we define functions /Q,/T : ZRuC —> Z U {+00} with dom/ Q ,dom/ T C {0,1} RUC by
Both fq and fa are M-convex functions. The right-hand side of (12.14) can now be identified as the negative of an integer infimal convolution of these M-convex functions. Namely,
12.4.
Degree of Determinant of Mixed Polynomial Matrices
361
where 1 € ZRUC. This reveals the discrete convexity implicit in Theorem 12.13 and also shows an efficient way to compute the degree of determinant of a mixed polynomial matrix A(s) = Q(s) + T(s), since the infimal convolution of M-convex functions can be computed efficiently by solving an M-convex submodular flow problem, as we have seen in Note 9.30. Such an algorithm is described in detail in section 6.2 of Murota [146]. Example 12.14. The dynamical degree of the mechanical system in Example 12.3 can be computed by Theorem 12.13 applied to A(s) = Q(s) + T(s) in Example 12.5. In (12.14) the maximum value of 4 is attained by I = {1,2,5,6} and J = {1,2,5,6}. Hence the dynamical degree is equal to four. •
Bibliographical Notes This chapter is largely based on Murota [146]. The observation on two kinds of numbers and the concept of mixed matrices are due to Murota-Iri [149], [150], in which Theorem 12.7 is given. Theorem 12.8 is taken from [146]. The Konig-Egervary theorem for mixed matrices (Theorem 12.9) is due to Bapat [7] and Hartfiel-Loewy [86]. The connection between mixed polynomial matrices and M-convexity explained in section 12.4 is due to Murota [143] and a related topic can be found in Iwata-Murota [104]. Applications of matroid theory to electrical networks are fully expounded in Iri [95] and Recski [175]. When gyrators are involved in electrical networks, a generalization of mixed matrices to mixed skew-symmetric matrices is useful, as is explained in section 7.3 of Murota [146]. See Geelen-Iwata [75] and Geelen-IwataMurota [76] for recent results on mixed skew-symmetric matrices. Matroid theory also finds applications in statics and scene analysis (GraverServatius-Servatius [80], Recski [175], Sugihara [195], Whiteley [215], [216], [217]). For planar truss structures, in particular, a necessary and sufficient condition for generic (infinitesimal) rigidity can be expressed in terms of unions of graphic matroids, where a matroid union is a special case of the Minkowski sum of two Mconvex sets. It is noted that the rigidity of a truss structure can be represented by a rank condition on a matrix associated with the truss, but that this matrix does not fall into the category of mixed matrices. Recent results on rigidity in nongeneric cases are surveyed in Radics-Recski [174].
This page intentionally left blank
Bibliography [1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin: Network Flows—Theory, Algorithms and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993. (Cited on pp. 74, 145, 278) [2] I. Althofer and W. Wenzel: Two-best solutions Under distance constraints: The model and exemplary results for matroids, Advances in Applied Mathematics, 22 (1999), 155-185. (Cited on p. 75) [3] D. H. Anderson: Compartmental Modeling and Tracer Kinetics, Lecture Notes in Biomathematics, 50, Springer-Verlag, Berlin, 1983. (Cited on p. 43) [4] K. J. Arrow and F. H. Hahn: General Competitive Analysis, Holden-Day, San Francisco, 1971. (Cited on p. 327) [5] M. Avriel, W. E. Diewert, S. Schaible, and I. Zang: Generalized Concavity, Plenum Press, New York, 1988. (Cited on p. 169) [6] O. Axelsson: Iterative Solution Methods, Cambridge University Press, Cambridge, U.K., 1994. (Cited on p. 42) [7] R. B. Bapat: Konig's theorem and bimatroids, Linear Algebra and Its Applications, 212/213 (1994), 353-365. (Cited on p. 361) [8] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty: Nonlinear Programming: Theory and Algorithm, 2nd ed., Wiley, New York, 1993. (Cited on p. 36) [9] A. Berman and R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences, SIAM, Philadelphia, 1994. (Cited on pp. 42, 74) [10] D. P. Bertsekas: Nonlinear Programming, 2nd ed., Athena Scientific, Belmont, MA, 1999. (Cited on p. 36) [11] M. J. Best, N. Chakravarti, and V. A. Ubhaya: Minimizing separable convex functions subject to simple chain constraints, SIAM Journal on Optimization, 10 (2000), 658-672. (Cited on p. 202) [12] C. Bevia, M. Quinzii, and J. Silva: Buying several indivisible goods, Mathematical Social Sciences, 37 (1999), 1-23. (Cited on p. 327) [13] S. Bikhchandani and J, W. Mamer: Competitive equilibrium in an exchange economy with indivisibilities, Journal of Economic Theory, 74 (1997), 385413. (Cited on p. 327) 363
364
Bibliography
[14] J. M. Bilbao: Cooperative Games on Combinatorial Structures, Kluwer Academic, Boston, 2000. (Cited on p. 345) [15] R. E. Bixby, W. H. Cunningham, and D. M. Topkis: Partial order of a polymatroid extreme point, Mathematics of Operations Research, 10 (1985), 367-378. (Cited on pp. 290, 322) [16] A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler: Oriented Matroids, 2nd ed., Cambridge University Press, Cambridge, U.K., 1999. (Cited on pp. 5, 75) [17] J. M. Borwein and A. S. Lewis: Convex Analysis and Nonlinear Optimization: Theory and Examples, Springer-Verlag, Berlin, 2000. (Cited on p. 99) [18] A. Bouchet and W. H. Cunningham: Delta-matroids, jump systems, and bisubmodular polyhedra, SI AM Journal on Discrete Mathematics, 8 (1995), 17-32. (Cited on p. 120) [19] R. K. Brayton and J. K. Moser: A theory of nonlinear networks, I, II, Quarterly of Applied Mathematics, 22 (1964), 1-33, 81-104. (Cited on p. 74) [20] R. A. Brualdi: Comments on bases in dependence structures, Bulletin of the Australian Mathematical Society, 1 (1969), 161-167. (Cited on p. 75) [21] R. A. Brualdi: Induced matroids, Proceedings of the American Mathematical Society, 29 (1971), 213-221. (Cited on p. 279) [22] P. M. Camerini, M. Conforti, and D. Naddef: Some easily solvable nonlinear integer programs, Ricerca Operativa, 50 (1989), 11-25. (Cited on p. 175) [23] Ch.-T. Chen: Linear System Theory and Design, 2nd ed., Holt, Rinehart and Winston, New York, 1970. (Cited on pp. 351, 355) [24] V. Chvatal: Linear Programming, W. H. Freeman and Company, New York, 1983. (Cited on pp. 88, 89, 99) [25] R. Clay: Nonlinear Networks and Systems, John Wiley and Sons, New York, 1971. (Cited on p. 74) [26] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver: Combinatorial Optimization, John Wiley and Sons, New York, 1998. (Cited on pp. 36, 37, 74, 89, 99, 248, 278) [27] W. Cui and S. Pujishige: A primal algorithm for the submodular flow problem with minimum-mean cycle selection, Journal of the Operations Research Society of Japan, 31 (1988), 431-440. (Cited on p. 313) [28] W. H. Cunningham: Testing membership in matroid polyhedra, Journal of Combinatorial Theory (B), 36 (1984), 161-188. (Cited on pp. 290, 322) [29] W. H. Cunningham: On submodular function minimization, Combinatorica, 5 (1985), 185-192. (Cited on pp. 290, 322) [30] W. H. Cunningham and A. Frank: A primal-dual algorithm for submodular flows, Mathematics of Operations Research, 10 (1985), 251-262. (Cited on p. 318)
Bibliography
365
[31] V. I. Danilov and G. A. Koshevoy: Cores of cooperative games, superdifferentials of functions, and the Minkowski difference of sets, Journal of Mathematical Analysis and Applications, 247 (2000), 1-14. (Cited on p. 345) [32] V. I. Danilov and G. A. Koshevoy: Discrete convexity and unimodularity, I, Preprint. (Cited on pp. 99, 120) [33] V. Danilov, G. Koshevoy, and C. Lang: Gross substitution, discrete convexity, and submodularity, Discrete Applied Mathematics (2003), in press. (Cited on pp. 176, 344) [34] V. Danilov, G. Koshevoy, and K. Murota: Equilibria in economies with indivisible goods and money, RIMS Preprint 1204, Kyoto University, May 1998. (Cited on pp. 175, 327, 344) [35] V. Danilov, G. Koshevoy, and K. Murota: Discrete convexity and equilibria in economies with indivisible goods and money, Mathematical Social Sciences, 41 (2001), 251-273. (Cited on pp. 175, 327, 344) [36] G. B. Dantzig: Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963. (Cited on pp. 88, 99) [37] G. Debreu: Theory of Value—An Axiomatic Analysis of Economic Equilibrium, John Wiley and Sons, New York, 1959. (Cited on p. 327) [38] G. Debreu: Existence of competitive equilibrium, in: K. J. Arrow and M. D. Intriligator, eds., Handbook of Mathematical Economics, Vol. II, NorthHolland, Amsterdam, 1982, Chap. 15, 697-743. (Cited on p. 327) [39] P. G. Doyle and J. L. Snell: Random Walks and Electrical Networks, Mathematical Society of America, Washington, DC, 1984. (Cited on p. 74) [40] A. W. M. Dress and W. Terhalle: Well-layered maps and the maximum-degree k x fc-subdeterminant of a matrix of rational functions, Applied Mathematics Letters, 8 (1995), 19-23. (Cited on p. 176) [41] A. W. M. Dress and W. Wenzel: Valuated matroid: A new look at the greedy algorithm, Applied Mathematics Letters, 3 (1990), 33-35. (Cited on pp. 6, 7, 75, 321) [42] A. W. M. Dress and W. Wenzel: Valuated matroids, Advances in Mathematics, 93 (1992), 214-250. (Cited on pp. 6, 7, 75) [43] D.-Z. Du and P. M. Pardalos, eds.: Handbook of Combinatorial Optimization, Vols. 1-3, A, Kluwer Academic, Boston, 1998, 1999. (Cited on pp. 36, 99, 278) [44] J. Edmonds: Submodular functions, matroids and certain polyhedra, in: R. Guy, H. Hanani, N. Saner, and J. Schonheim, eds., Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, 69-87. (Cited on pp. 5, 6, 7, 35, 37, 119, 146, 224 290) [45] J. Edmonds: Matroid intersection, Annals of Discrete Mathematics, 14 (1979), 39-49. (Cited on pp. 6, 7, 35, 224)
366
Bibliography
[46] J. Edmonds and R. Giles: A min-max relation for submodular functions on graphs, Annals of Discrete Mathematics, 1 (1977), 185-204. (Cited on p. 278) [47] A. Eguchi and S. Fujishige: An extension of the Gale-Shapley stable matching algorithm to a pair of M^-concave functions, Discrete Mathematics and Systems Science Research Report, No. 02-05, Division of Systems Science, Osaka University, November 2002; Mathematics of Operations Research, submitted. (Cited on p. 345) [48] U. Faigle: Matroids in combinatorial optimization, in: N. White, ed., Combinatorial Geometries, Cambridge University Press, London, 1987, 161-210. (Cited on p. 74) [49] P. Favati and F. Tardella: Convexity in nonlinear integer programming, Ricerca Operativa, 53 (1990), 3-44. (Cited on pp. 6, 7, 8, 38, 99, 202, 322) [50] L. Fleischer and S. Iwata: A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics (2003), in press. (Cited on p. 322) [51] L. Fleischer, S. Iwata, and S. T. McCormick: A faster capacity scaling algorithm for minimum cost submodular flow, Mathematical Programming, 92 (2002), 119-139. (Cited on p. 322) [52] R. Fletcher: Practical Methods of Optimization, 2nd ed., John Wiley and Sons, New York, 1987. (Cited on p. 36) [53] L. R. Ford, Jr. and D. R. Fulkerson: Flows in Networks, Princeton University Press, Princeton, NJ, 1962. (Cited on pp. 74, 278) [54] A. Frank: A weighted matroid intersection algorithm, Journal of Algorithms, 2 (1981), 328-336. (Cited on pp. 6, 7, 35, 37, 224, 244) [55] A. Frank: An algorithm for submodular functions on graphs, Annals of Discrete Mathematics, 16 (1982), 97-120. (Cited on pp. 6, 35, 37, 119, 224, 318) [56] A. Frank: Finding feasible vectors of Edmonds-Giles polyhedra, Journal of Combinatorial Theory (B), 36 (1984), 221-239. (Cited on pp. 278, 312, 322) [57] A. Frank: Generalized polymatroids, in: A. Hajnal, L. Lovasz, and V. T. Sos, eds., Finite and Infinite Sets, I, North-Holland, Amsterdam, 1984, 285-294. (Cited on p. 119) [58] A. Frank and E. Tardos: Generalized polymatroids and submodular flows, Mathematical Programming, 42 (1988), 489-563. (Cited on p. 119) [59] S. Fujishige: Algorithms for solving the independent-flow problems, Journal of Operations Research Society of Japan, 21 (1978), 189-204. (Cited on pp. 278, 312, 313, 322) [60] S. Fujishige: Lexicographically optimal base of a polymatroid with respect to a weight vector, Mathematics of Operations Research, 5 (1980), 186-196. (Cited on p. 4)
Bibliography
367
[61] S. Fujishige: Structure of polyhedra determined by submodular functions on crossing families, Mathematical Programming, 29 (1984), 125-141. (Cited on p. 278) [62] S. Fujishige: Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions, Mathematical Programming, 29 (1984), 142-155. (Cited on pp. 6, 35, 224, 244) [63] S. Fujishige: On the subdifferential of a submodular function, Mathematical Programming, 29 (1984), 348-360. (Cited on pp. 6, 37, 119) [64] S. Fujishige: A note on Frank's generalized polymatroids, Discrete Applied Mathematics, 7 (1984), 105-109. (Cited on p. 119) [65] S. Fujishige: Submodular Functions and Optimization, Annals of Discrete Mathematics, 47, North-Holland, Amsterdam, 1991. (Cited on pp. 4, 37, 117, 119, 202, 248, 278, 285, 312, 318, 322) [66] S. Fujishige and S. Iwata: Algorithms for submodular flows, IEICE Transactions on Systems and Information, E83-D (2000), 322-329. (Cited on pp. 312, 318, 322) [67] S. Fujishige, K. Makino, T. Takabatake, and K. Kashiwabara: Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2, Discrete Mathematics, to appear. (Cited on p. 120) [68] S. Fujishige and K. Murota: Notes on L-/M-convex functions and the separation theorems, Mathematical Programming, 88 (2000), 129-146. (Cited on pp. 6, 8, 38, 131, 202) [69] S. Fujishige and Z. Yang: A note on Kelso and Crawford's gross substitutes condition, Mathematics of Operations Research, to appear. (Cited on pp. 120, 176, 344) [70] S. Fujishige and X. Zhang: New algorithms for the intersection problem of submodular systems, Japan Journal of Applied Mathematics, 9 (1992), 369382. (Cited on p. 312) [71] M. Fukushima, Y. Oshima, and M. Takeda: Dirichlet Forms and Symmetric Markov Processes, Walter de Gruyter, Berlin, 1994. (Cited on pp. 45, 74) [72] D. Gale: Equilibrium in a discrete exchange economy with money, International Journal of Game Theory, 13 (1984), 61-64. (Cited on p. 327) [73] D. Gale and T. Politof: Substitutes and complements in network flow problems, Discrete Applied Mathematics, 3 (1981), 175-186. (Cited on p. 74) [74] D. Gale and L. S. Shapley: College admissions and stability of marriage, American Mathematical Monthly, 69 (1962), 9-15. (Cited on p. 345) [75] J. F. Geelen and S. Iwata: Matroid matching via mixed skew-symmetric matrices, METR 2002-03, University of Tokyo, April 2002. (Cited on p. 361) [76] J. F. Geelen, S. Iwata, and K. Murota: The linear delta-matroid parity problem, Journal of Combinatorial Theory (B), to appear. (Cited on p. 361)
368
Bibliography
[77] E. Girlich, M. Kovalev, and A. Zaporozhets: A polynomial algorithm for resource allocation problems with polymatroid constraints, Optimization, 37 (1996), 73-86. (Cited on p. 4) [78] E. Girlich and M. M. Kowaljow: Nichtlineare diskrete Optimierung, Akademie-Verlag, Berlin, 1981. (Cited on p. 4) [79] F. Granot and A. F. Veinott, Jr.: Substitutes, complements and ripples in network flows, Mathematics of Operations Research, 10 (1985), 471-497. (Cited on p. 74) [80] J. Graver, B. Servatius, and H. Servatius: Combinatorial Rigidity, American Mathematical Society, Providence, RI, 1993. (Cited on p. 361) [81] H. Groenevelt: Two algorithms for maximizing a separable concave function over a polymatroid feasible region, European Journal of Operational Research, 54 (1991), 227-236. (Cited on p. 4) [82] M. Grotschel, L. Lovasz, and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169197 [Corrigendum: Combinatorica, 4 (1984), 291-295]. (Cited on p. 290) [83] M. Grotschel, L. Lovasz, and A. Schrijver: Geometric Algorithms and Combinatorial Optimization, 1st ed., 2nd. ed., Springer-Verlag, Berlin, 1988, 1993. (Cited on p. 290) [84] F. Gul and E. Stacchetti: Walrasian equilibrium with gross substitutes, Journal of Economic Theory, 87 (1999), 95-124. (Cited on pp. 327, 332, 344) [85] B. Hajek: Extremal splittings of point processes, Mathematics of Operations Research, 10 (1985), 543-556. (Cited on p. 202) [86] D. J. Hartfiel and R. Loewy: A determinantal version of the Frobenius-Konig theorem, Linear Multilinear Algebra, 16 (1984), 155-165. (Cited on p. 361) [87] R. Hassin: Minimum cost flow with set-constraints, Networks, 12 (1982), 1-21. (Cited on p. 278) [88] C. Henry: Indivisibilites dans une economic d'echanges, Econometrica, 38 (1970), 542-558. (Cited on p. 327) [89] J.-B. Hiriart-Urruty and C. Lemarechal: Convex Analysis and Minimization Algorithms I, II, Springer-Verlag, Berlin, 1993. (Cited on p. 99) [90] D. S. Hochbaum: Lower and upper bounds for the allocation problem and other nonlinear optimization problems, Mathematics of Operations Research, 19 (1994), 390-409. (Cited on pp. 4, 158) [91] D. S. Hochbaum and S.-P. Hong: About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Mathematical Programming, 69 (1995), 269-309. (Cited on p. 4) [92] D. S. Hochbaum, R. Shamir, and J. G. Shanthikumar: A polynomial algorithm for an integer quadratic non-separable transportation problem, Mathematical Programming, 55 (1992), 359-371. (Cited on pp. 5, 175)
Bibliography
369
[93] T. Ibaraki and N. Katoh: Resource Allocation Problems: Algorithmic Approaches, MIT Press, Boston, 1988. (Cited on pp. 4, 5) [94] M. Iri: Network Flow, Transportation and Scheduling—Theory and Algorithms, Academic Press, New York, 1969. (Cited on pp. 64, 74, 132, 247, 278) [95] M. Iri: Applications of matroid theory, in: A. Bachem, M. Grotschel, and B. Korte, eds., Mathematical Programming—The State of the Art, SpringerVerlag, Berlin, 1983, 158-201. (Cited on p. 361) [96] M. Iri and N. Tomizawa: An algorithm for finding an optimal "independent assignment," Journal of the Operations Research Society of Japan, 19 (1976), 32-57. (Cited on pp. 6, 7, 35, 224) [97] S. Iwata: A capacity scaling algorithm for convex cost submodular flows, Mathematical Programming, 76 (1997), 299-308. (Cited on p. 322) [98] S. Iwata: Submodular flow problems (in Japanese), in: S. Fujishige, ed., Discrete Structures and Algorithms, Vol. VI, Kindai-Kagakusha, Tokyo, 1999, Chapter 4, 127-170. (Cited on pp. 312, 318, 322) [99] S. Iwata: A fully combinatorial algorithm for submodular function minimization, Journal of Combinatorial Theory (B), 84 (2002), 203-212. (Cited on pp. 290, 305) [100] S. Iwata: A faster scaling algorithm for minimizing submodular functions, in: W. J. Cook and A. S. Schulz, eds., Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, 2337, Springer-Verlag, 2002, 1-8. (Cited on p. 322) [101] S. Iwata, L. Fleischer, and S. Fujishige: A combinatorial, strongly polynomialtime algorithm for minimizing submodular functions, Proceedings of the 32nd ACM Symposium on Theory of Computing (2000), 97-106. (Cited on p. 290) [102] S. Iwata, L. Fleischer, and S. Fujishige: A combinatorial, strongly polynomialtime algorithm for minimizing submodular functions, Journal of the ACM, 48 (2001), 761-777. (Cited on pp. 290, 322) [103] S. Iwata, S. T. McCormick, and M. Shigeno: Fast cycle canceling algorithms for minimum cost submodular flow, Combinatorica, to appear. (Cited on p. 313) [104] S. Iwata and K. Murota: Combinatorial relaxation algorithm for mixed polynomial matrices, Mathematical Programming, 90 (2001), 353-371. (Cited on p. 361) [105] S. Iwata and M. Shigeno: Conjugate scaling algorithm for Fenchel-type duality in discrete convex optimization, SI AM Journal on Optimization, 13 (2003), 204-211. (Cited on pp. 202, 278, 322) [106] P. M. Jensen and B. Korte: Complexity of matroid property algorithms, SIAM Journal on Computing, 11 (1982), 184-190. (Cited on p. 293) [107] M. Kaneko: The central assignment game and the assignment markets, Journal of Mathematical Economics, 10 (1982), 205-232. (Cited on p. 327)
370
Bibliography
[108] M. Kaneko and Y. Yamamoto: The existence and computation of competitive equilibria in markets with an indivisible commodity, Journal of Economic Theory, 38 (1986), 118-136. (Cited on p. 327) [109] K. Kashiwabara and T. Takabatake: Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability, Discrete Applied Mathematics (2003), in press. (Cited on p. 120) [110] N. Katoh and T. Ibaraki: Resource allocation problems, in: D.-Z. Du and P. M. Pardalos, eds., Handbook of Combinatorial Optimization, Vol. 2, Kluwer Academic, Boston, 1998, 159-260. (Cited on p. 176) [111] A. S. Kelso, Jr., and V. P. Crawford: Job matching, coalition formation, and gross substitutes, Econometrica, 50 (1982), 1483-1504. (Cited on pp. 327, 332, 344) [112] J. Kindler: Sandwich theorems for set functions, Journal of Mathematical Analysis and Applications, 133 (1988), 529-542. (Cited on p. 5) [113] S. Kodama and N. Suda: Matrix Theory for System Control (in Japanese), Society of Instrument and Control Engineers, Tokyo, 1978. (Cited on p. 42) [114] B. Korte, L. Lovasz, and R. Schrader: Greedoids, Springer-Verlag, Berlin, 1991. (Cited on p. 5) [115] B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms, Springer-Verlag, Berlin, 2000. (Cited on pp. 36, 74, 89, 99, 278) [116] J. P. S. Kung: A Source Book in Matroid Theory, Birkhauser, Boston, 1986. (Cited on p. 74) [117] J. P. S. Kung: Basis-exchange properties, in: N. White, ed., Theory of Matroids, Cambridge University Press, London, 1986, Chapter 4, 62-75. (Cited on p. 333) [118] E. L. Lawler: Matroid intersection algorithms, Mathematical Programming, 9 (1975), 31-56. (Cited on pp. 6, 7) [119] E. L. Lawler: Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976, Dover Publications, New York, 2001. (Cited on pp. 36, 74, 89, 99, 278) [120] E. L. Lawler and C. U. Martel: Computing maximal polymatroidal network flows, Mathematics of Operations Research, 7 (1982), 334-337. (Cited on p. 278) [121] E. L. Lawler and C. U. Martel: Network flow formulations of polymatroid optimization problems, Annals of Discrete Mathematics, 16 (1982), 515-534. (Cited on p. 278) [122] L. Lovasz: Matroid matching and some applications, Journal of Combinatorial Theory (B), 28 (1980), 208-236. (Cited on p. 293) [123] L. Lovasz: Submodular functions and convexity, in: A. Bachem, M. Grotschel, and B. Korte, eds., Mathematical Programming—The State of the Art, Springer-Verlag, Berlin, 1983, 235-257. (Cited on pp. 5, 6, 37, 119, 14 293)
Bibliography
371
[124] L. Lovasz: The membership problem in jump systems, Journal of Combinatorial Theory (B), 70 (1997), 45-66. (Cited on p. 120) [125] L. Lovasz and M. Plummer: Matching Theory, North-Holland, Amsterdam, 1986. (Cited on p. 99) [126] O. L. Mangasarian: (Cited on p. 36)
Nonlinear Programming, SIAM, Philadelphia, 1994.
[127] S. T. McCormick: Submodular Function Minimization, in: K. Aardal, G. Nemhauser, and R. Weismantel, eds., Handbook on Discrete Optimization, Elsevier Science, Berlin, 2003, to appear. (Cited on p. 322) [128] L. McKenzie: General equilibrium, in: J. Eatwell, M. Milgate, and P. Newman, eds., The New Palgrave: General Equilibrium, Macmillan, London, 1989, Chapter 1. (Cited on p. 327) [129] P. Milgrom and C. Shannon: Monotone comparative statics, Econometrica, 62 (1994), 157-180. (Cited on pp. 198, 203, 345) [130] B. L. Miller: On minimizing nonseparable functions denned on the integers with an inventory application, SIAM Journal on Applied Mathematics, 21 (1971), 166-185. (Cited on pp. 5, 99) [131] M. Minoux: Solving integer minimum cost flows with separable convex objective polynomially, Mathematical Programming, 26 (1986), 237-239. (Cited on p. 4) [132] S. Moriguchi and K. Murota: Capacity scaling algorithm for scalable Mconvex submodular flow problems, Optimization Methods and Software, to appear. (Cited on pp. 312, 322) [133] S. Moriguchi, K. Murota, and A. Shioura: Scaling algorithms for M-convex function minimization, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A (2002), 922-929. (Cited on pp. 175, 321) [134] S. Moriguchi and A. Shioura: On Hochbaum's scaling algorithm for the general resource allocation problem, Research Reports on Mathematical and Computing Sciences, B-377, Tokyo Institute of Technology, January 2002. (Cited on pp. 158, 176) [135] K. Murota: Valuated matroid intersection, I: optimality criteria, SIAM Journal on Discrete Mathematics, 9 (1996), 545-561. (Cited on pp. 6, 7, 35, 224, 244, 278) [136] K. Murota: Valuated matroid intersection, II: algorithms, SIAM Journal on Discrete Mathematics, 9 (1996), 562-576. (Cited on pp. 8, 313, 322) [137] K. Murota: Convexity and Steinitz's exchange property, Advances in Mathematics, 124 (1996), 272-311. (Cited on pp. 6, 8, 37, 175, 176, 244, 278) [138] K. Murota: Matroid valuation on independent sets, Journal of Combinatorial Theory (B), 69 (1997), 59-78. (Cited on p. 176)
372
Bibliography
[139] K. Murota: Fenchel-type duality for matroid valuations, Mathematical Programming, 82 (1998), 357-375. (Cited on pp. 6, 8) [140] K. Murota: Discrete convex analysis, Mathematical Programming, 83 (1998), 313-371. (Cited on pp. 6, 8, 37, 74, 119, 131, 132, 176, 202, 244, 278) [141] K. Murota: Discrete convex analysis (in Japanese), in: S. Fujishige, ed., Discrete Structures and Algorithms, Vol. V, Kindai-Kagakusha, Tokyo, 1998, Chapter 2, 51-100. (Cited on pp. 37, 74, 119, 132, 175, 202) [142] K. Murota: Submodular flow problem with a nonseparable cost function, Combinatorica, 19 (1999), 87-109. (Cited on pp. 8, 37, 74, 176, 221, 244, 278, 322) [143] K. Murota: On the degree of mixed polynomial matrices, SIAM Journal on Matrix Analysis and Applications, 20 (1999), 196-227. (Cited on p. 361) [144] K. Murota: Discrete convex analysis—Exposition on conjugacy and duality, in: L. Lovasz, A. Gyarfas, G. O. H. Katona, A. Recski, and L. Szekely, eds., Graph Theory and Combinatorial Biology, The Janos Bolyai Mathematical Society, Budapest, 1999, 253-278. (Cited on pp. 175, 202) [145] K. Murota: Algorithms in discrete convex analysis, IEICE Transactions on Systems and Information, E83-D (2000), 344-352. (Cited on pp. 202, 278, 322) [146] K. Murota: Matrices and Matroids for Systems Analysis, Springer-Verlag, Berlin, 2000. (Cited on pp. 74, 244, 266, 321, 358, 359, 360, 361) [147] K. Murota: Discrete Convex Analysis—An Introduction (in Japanese), Kyoritsu Publishing Company, Tokyo, 2001. (Cited on pp. xxii, 74, 99, 175, 176, 202, 244, 278, 322, 344) [148] K. Murota: On steepest descent algorithms for discrete convex functions, METR 2002-12, University of Tokyo, November 2002. (Cited on pp. 321, 322) [149] K. Murota and M. Iri: Matroid-theoretic approach to the structural solvability of a system of equations (in Japanese), Transactions of Information Processing Society of Japan, 24 (1983), 157-164. (Cited on p. 361) [150] K. Murota and M. Iri: Structural solvability of systems of equations—A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems, Japan Journal of Applied Mathematics, 2 (1985), 247-271. (Cited on p. 361) [151] K. Murota and A. Shioura: M-convex function on generalized polymatroid, Mathematics of Operations Research, 24 (1999), 95-105. (Cited on pp. 6, 8, 38, 119, 175) [152] K. Murota and A. Shioura: Extension of M-convexity and L-convexity to polyhedral convex functions, Advances in Applied Mathematics, 25 (2000), 352-427. (Cited on pp. 6, 8, 38, 98, 120, 132, 162, 163, 176, 190, 192, 202, 244, 278, 279)
Bibliography
373
[153] K. Murota and A. Shioura: Relationship of M-/L-convex functions with discrete convex functions by Miller and by Favati-Tardella, Discrete Applied Mathematics, 115 (2001), 151-176. (Cited on pp. 36, 38, 99, 119, 132, 176, 231, 244) [154] K. Murota and A. Shioura: Quasi M-convex and L-convex functions: Quasiconvexity in discrete optimization, Discrete Applied Mathematics (2003), in press. (Cited on pp. 176, 202, 321) [155] K. Murota and A. Shioura: Quadratic M-convex and L-convex functions, RIMS Preprint 1326, Kyoto University, July 2001. (Cited on pp. 9, 38, 52, 74, 175) [156] K. Murota and A. Shioura: M-convex and L-convex functions over the real space—Two conjugate classes of combinatorial convex functions, METR 200209, University of Tokyo, July 2002. (Cited on pp. 6, 9, 38, 176, 202, 211) [157] K. Murota and A. Shioura: Conjugacy relationship between M-convex and L-convex functions in continuous variables, RIMS Preprint 1378, Kyoto University, September 2002; Mathematical Programming, to appear. (Cited on pp. 6, 9, 38, 176, 202, 211) [158] K. Murota and A. Shioura: Substitutes and complements in network flows viewed as discrete convexity, RIMS Preprint 1382, Kyoto University, October 2002. (Cited on p. 74) [159] K. Murota and A. Tamura: On circuit valuation of matroids, Advances in Applied Mathematics, 26 (2001), 192-225. (Cited on p. 75) [160] K. Murota and A. Tamura: New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities, Discrete Applied Mathematics (2003), in press. (Cited on pp. 176, 333, 344) [161] K. Murota and A. Tamura: Application of M-convex submodular flow problem to mathematical economics, in: P. Eades and T. Takaoka, eds., Algorithms and Computation, Lecture Notes in Computer Science, 2223, Springer-Verlag, 2001, 14-25; Japan Journal of Applied Mathematics, to appear. (Cited on p. 345) [162] K. Murota and A. Tamura: Proximity theorems of discrete convex functions, RIMS Preprint 1358, Kyoto University, June 2002. (Cited on pp. 158, 228, 244) [163] H. Nagamochi and T. Ibaraki: Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, 5 (1992), 54-64. (Cited on p. 290) [164] T. Nakasawa: Zur Axiomatik der linearen Abhangigkeit, I, II, III, Science Reports of the Tokyo Bunrika Daigaku, Section A, 2 (1935), 235-255; 3 (1936), 45-69; 3 (1936), 123-136. (Cited on p. 74) [165] H. Narayanan: Submodular Functions and Electrical Networks, Annals of Discrete Mathematics, 54, North-Holland, Amsterdam, 1997. (Cited on p. 37)
374
Bibliography
[166] G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, eds.: Optimization, Handbooks in Operations Research and Management Science, Vol. 1, Elsevier Science, Amsterdam, 1989. (Cited on pp. 36, 244) [167] G. L. Nemhauser and L. A. Wolsey: Integer and Combinatorial Optimization, John Wiley and Sons, New York, 1988. (Cited on pp. 36, 99, 244, 278) [168] H. Nikaido: Convex Structures and Economic Theory, Academic Press, New York, 1968. (Cited on p. 327) [169] J. Nocedal and S. J. Wright: Numerical Optimization, Springer-Verlag, New York, 1999. (Cited on p. 36) [170] J. G. Oxley: Matroid Theory, Oxford University Press, Oxford, U.K., 1992. (Cited on p. 74) [171] H. Perfect: Independence spaces and combinatorial problems, Proceedings of the London Mathematical Society, 19 (1969), 17-30. (Cited on p. 279) [172] M. Queyranne: Minimizing symmetric submodular functions, Mathematical Programming, 82 (1998), 3-12. (Cited on p. 290) [173] M. Quinzii: Core and equilibria with indivisibilities, International Journal of Game Theory, 13 (1984), 41-61. (Cited on p. 327) [174] N. Radics and A. Recski: Applications of combinatorics to statics—Rigidity of grids, Discrete Applied Mathematics, 123 (2002), 473-485. (Cited on p. 361) [175] A. Recski: Matroid Theory and Its Applications in Electric Network Theory and in Statics, Springer-Verlag, Berlin, 1989. (Cited on pp. 74, 361) [176] R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, NJ, 1970. (Cited on pp. 84, 85, 99) [177] R. T. Rockafellar: Conjugate Duality and Optimization, SIAM Regional Conference Series in Applied Mathematics 16, SIAM, Philadelphia, 1974. (Cited on pp. 99, 235, 242) [178] R. T. Rockafellar: Network Flows and Monotropic Optimization, John Wiley and Sons, New York, 1984. (Cited on pp. 53, 60, 64, 74, 132, 247, 253, 278) [179] R. T. Rockafellar and R. J.-B. Wets: Variational Analysis, Springer-Verlag, Berlin, 1998. (Cited on p. 99) [180] A. E. Roth and M. A. O. Sotomayor: Two-Sided Matching—A Study in GameTheoretic Modelling and Analysis, Cambridge University Press, Cambridge, U.K., 1990. (Cited on p. 344) [181] A. Schrijver: Theory of Linear and Integer Programming, John Wiley and Sons, New York, 1986. (Cited on pp. 88, 89, 99) [182] A. Schrijver: A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory (B), 80 (2000), 346-355. (Cited on pp. 290, 322) [183] A. Schrijver: Combinatorial Optimization—Polyhedra and Efficiency, Springer-Verlag, Heidelberg, Germany, 2003. (Cited on pp. 74, 119, 279)
Bibliography
375
[184] L. S. Shapley: On network flow functions, Naval Research Logistics Quarterly, 8 (1961), 151-158. (Cited on p. 74) [185] L. S. Shapley: Complements and substitutes in the optimal assignment problem, Naval Research Logistics Quarterly, 9 (1962), 45-48. (Cited on p. 74) [186] L. S. Shapley: Cores of convex games, International Journal of Game Theory, 1 (1971), 11-26 (errata, 199). (Cited on p. 345) [187] L. S. Shapley and H. Scarf: On cores and indivisibilities, Journal of Mathematical Economics, I (1974), 23-37. (Cited on p. 327) [188] A. Shioura: An algorithmic proof for the induction of M-convex functions through networks, Research Reports on Mathematical and Computing Sciences, B-317, Tokyo Institute of Technology, July 1996. (Cited on p. 278) [189] A. Shioura: A constructive proof for the induction of M-convex functions through networks, Discrete Applied Mathematics, 82 (1998), 271-278. (Cited on p. 278) [190] A. Shioura: Minimization of an M-convex function, Discrete Applied Mathematics, 84 (1998), 215-220. (Cited on pp. 176, 321) [191] A. Shioura: Level set characterization of M-convex functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A (2000), 586-589. (Cited on p. 176) [192] A. Shioura: Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem, IEICE Technical Report COMP 2002-43, The Institute of Electronics, Information and Communication Engineers, 2002. Discrete Applied Mathematics, to appear. (Cited on p. 321) [193] D. D. Siljak: Large-Scale Dynamic Systems—Stability and Structure, NorthHolland, New York, 1978. (Cited on p. 42) [194] J. Stoer and C. Witzgall: Convexity and Optimization in Finite Dimensions I, Springer-Verlag, Berlin, 1970. (Cited on pp. 85, 99) [195] K. Sugihara: Machine Interpretation of Line Drawings, MIT Press, Cambridge, MA, 1986. (Cited on p. 361) [196] L.-G. Svensson: Competitive equilibria with indivisible goods, Journal of Economics, 44 (1984), 373-386. (Cited on p. 327) [197] A. Tamura: Coordinatewise domain scaling algorithm for M-convex function minimization, in: W. J. Cook and A. S. Schulz, eds., Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, 2337, Springer-Verlag, 2002, 21-35. (Cited on pp. 176, 321) [198] A. Tamura: On convolution of L-convex functions, Optimization Methods and Software, to appear. (Cited on p. 244) [199] E. Tardos, C. A. Tovey, and M. A. Trick: Layered augmenting path algorithms, Mathematics of Operations Research, 11 (1986), 362-370. (Cited on p. 312)
376
Bibliography
[200] N. Tomizawa: Theory of hyperspaces (XVI)—On the structure of hedrons (in Japanese), Papers of the Technical Group on Circuit and System Theory, Institute of Electronics and Communication Engineers of Japan, CAS82-174, 1983. (Cited on p. 120) [201] N. Tomizawa and M. Iri: An algorithm for solving the "independent assignment" problem with application to the problem of determining the order of complexity of a network (in Japanese), Transactions of the Institute of Electronics and Communication Engineers of Japan, 57A (1974), 627-629. (Cited on pp. 6, 7) [202] D. M. Topkis, Minimizing a submodular function on a lattice, Operations Research, 26 (1978), 305-321. (Cited on pp. 202, 244) [203] D. M. Topkis: Supermodularity and Complementarity, Princeton University Press, Princeton, NJ, 1998. (Cited on pp. 37, 244, 345) [204] G. van der Laan, D. Talman, and Z. Yang: Existence of an equilibrium in a competitive economy with indivisibilities and money, Journal of Mathematical Economics, 28 (1997), 101-109. (Cited on p. 327) [205] B. L. van der Waerden: Algebra, Springer-Verlag, Berlin, 1955. P. 73)
(Cited on
[206] R. J. Vanderbei: Linear Programming: Foundations and Extensions, 2nd ed., Kluwer Academic, Boston, 2001. (Cited on pp. 88, 99) [207] R. S. Varga: Matrix Iterative Analysis, 2nd ed., Springer-Verlag, Berlin, 2000. (Cited on p. 42) [208] J. Vygen: A note on Schrijver's submodular function minimization algorithm, Journal of Combinatorial Theory (B), to appear. (Cited on p. 296) [209] J. Wako: A note on the strong core of a market with indivisible goods, Journal of Mathematical Economics, 13 (1984), 189-194. (Cited on p. 327) [210] C. Wallacher and U. T. Zimmermann: A polynomial cycle canceling algorithm for submodular flows, Mathematical Programming, 86 (1999), 1-15. (Cited on p. 313) [211] D. J. A. Welsh: Matroid Theory, Academic Press, London, 1976. pp. 74, 279)
(Cited on
[212] N. White, ed.: Theory of Matroids, Cambridge University Press, London, 1986. (Cited on p. 74) [213] N. White, ed.: Combinatorial Geometries, Cambridge University Press, London, 1987. (Cited on pp. 74, 279) [214] N. White, ed.: Matroid Applications, Cambridge University Press, London, 1992. (Cited on p. 74) [215] W. Whiteley: Matroids and rigid structures, in: N. White, ed., Matroid Applications, Cambridge University Press, London, 1992, Chapter 1, 1-53. (Cited on p. 361)
Bibliography
377
[216] W. Whiteley: Some matroids from discrete applied geometry, in: J. E. Bonin, J. G. Oxley, and B. Servatius, eds., Matroid Theory, American Mathematical Society, Providence, RI, 1996, 171-311. (Cited on p. 361) [217] W. Whiteley: Rigidity and scene analysis, in: J. E. Goodman and J. O'Rourke, eds., Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton, FL, 1997, 893-916. (Cited on p. 361) [218] H. Whitney: On the abstract properties of linear dependence, American Journal of Mathematics, 57 (1935), 509-533. (Cited on pp. 5, 6, 8, 74) [219] Z. Yang: Equilibrium in an exchange economy with multiple indivisible commodities and money, Journal of Mathematical Economics, 33 (2000), 353-365. (Cited on p. 327) [220] L. A. Zadeh and C. A. Desoer: Linear System Theory, McGraw-Hill, New York, 1963. (Cited on pp. 351, 355) [221] U. Zimmermann: Minimization of some nonlinear functions over polymatroidal network flows, Annals of Discrete Mathematics, 16 (1982), 287-309. (Cited on p. 176) [222] U. Zimmermann: Negative circuits for flows and submodular flows, Discrete Applied Mathematics, 36 (1992), 179-189. (Cited on p. 313)
This page intentionally left blank
Index entering, 53 leaving, 52 augmenting path, 60, 273, 274 6-, 297 auxiliary network, 252, 263
accurate number, 347 active triple, 297 acyclic, 107 admissible potential, 122 affine hull, 78 agent, 324 aggregate cost function, 335 aggregation of function to subset, 143, 162 by network transformation, 272 algebraically independent, 354 algorithm competitive equilibrium, 344 conjugate scaling, 320 cycle-canceling, 313 domain reduction, 284 domain reduction scaling, 287 fully combinatorial, 290 greedy, 3, 108 IFF fixing, 300 IFF scaling, 299 L-convex function minimization, 305, 306, 308 M-convex function minimization, 281, 283, 284, 287 primal-dual, 315 pseudopolynomial, 288 Schrijver's, 293 steepest descent, 281, 305, 306 steepest descent scaling, 283, 308 strongly polynomial, 288 submodular function minimization, 293, 299, 300 successive shortest path, 312 two-stage, 310 weakly polynomial, 288 arc, 52
base, 105 extreme, 105 matrix, 69 matroid, 70 base family matrix, 69 matroid, 70 valuated matroid, 72 base polyhedron, 18, 105 integral, 18 biconjugate function, 82 integer, 212 bipartite graph, 89 bipartite matching, 89 Birkhoff's representation theorem, 292 Boolean lattice, 104 boundary, 53 branch, 52 budget set, 324 certificate of optimality, 12 chain, 88 characteristic curve, 54, 251 discrete, 57 characteristic vector, 16 chemical process, 349 Choquet integral, 16, 104 closed convex function, 79 closed convex hull, 78 closed interval, 77 closure 379
380
concave function, 216 convex function, 93 convex set, 78 coboundary, 53, 248 another convention, 253 cocontent, 55 combinatorial optimization, 3 commodity divisible, 327 indivisible, 323 compartmental matrix, 43 competitive economy, 324 competitive equilibrium, 325 complementarity, 88 complements, 62 concave closure, 216 concave conjugate, 11, 81 discrete, 212 concave extensible, 93 concave extension, 93 concave function, 9, 78 quasi-separable, 334 separable, 333 conductance, 41 cone, 78 convex, 78 L-convex, 131 M-convex, 119 polar, 82 conformal decomposition, 64 conjugacy theorem closed proper M-/L-convex, 210 in convex analysis, 11, 82 discrete M-/L-convex, 30, 212 polyhedral M-/L-convex, 209 conjugate function concave, 81, 212 convex, 81, 212 conjugate scaling, 319 conjugate scaling algorithm, 320 conservation law, 54 constitutive equation, 54, 349 constraint, 1 consumer, 323 consumption, 323 content, 55
Index
contraction normal, 45 unit, 45 convex closure function, 93 set, 78 convex combination, 78 convex cone, 78 convex conjugate, 10, 81 discrete, 212 convex extensible, 93 convex extension, 93 local, 93 convex function, 2, 9, 77 closed, 79 dual-integral polyhedral, 161 integral polyhedral, 161 laminar, 141 polyhedral, 80 positively homogeneous, 82 proper, 77 quadratic, 40 quasi, 168 quasi-separable, 140 separable, 10, 95, 140, 182 strictly, 77 univariate, 10 convex hull, 78 closed, 78 convex polyhedron, 78 convex program, 2 M-, 235 convex set, 2, 78 convexity discrete midpoint, 23, 129, 180 function, 77 in intersection, 92 midpoint, 9 in Minkowski sum, 92 quasi, 168 set, 78 convolution infimal, 80 integer infimal, 143 by network transformation, 272 cost function
Index
aggregate, 335 flow, 53, 246, 255, 256 flow boundary, 256 producer's, 324 reduced, 249 tension, 53 current, 41, 53 current potential, 55 cut capacity function, 247 cycle negative, 122, 252, 263 simple, 62 cycle-canceling algorithm, 313 decreasing marginal return, 330 demand correspondence, 325 set, 325 descent direction, 147 diagonal dominance, 41 directed graph, 52, 88 directional derivative, 80 Dirichlet form, 45 discrete Legendre-Fenchel transformation, 13, 212 discrete midpoint convexity function, 23, 180 set, 129 discrete separation theorem generic form, 13, 216 L-convex function, 218 L-convex set, 36, 126 M-convex function, 217 M-convex set, 36, 114 submodular function, 17, 111 submodular function (as special case of L-separation), 33, 224 discreteness in direction, 10 in value, 13 distance function, 122 distributive lattice, 292 distributive law, 292 divisible commodity, 327 domain reduction algorithm, 284
381
domain reduction scaling algorithm, 287 dual-integral polyhedral convex function, 161 L-convex function, 191 M-convex function, 161 dual integrality intersection theorem, 20, 114 linear programming, 89 minimum cost flow problem, 252 polyhedral convex function, 161 polyhedral L-convex function, 191 polyhedral M-convex function, 161 submodular flow problem, 261 dual linear program, 87 dual problem, 87 dual variable, 53 duality, 2, 11 Edmonds's intersection theorem, 20 Fenchel, 85 Fenchel-type, 222, 225 L-separation, 218 linear programming, 87 M-separation, 217 matroid intersection, 225 separation for convex functions, 84 separation for convex sets, 35, 83 separation for L-convex functions, 218 separation for M-convex functions, 217 separation for submodular functions, 17, 111 strong, 87 valuated matroid intersection, 225 weak, 87 weight splitting, 34, 225 dynamical degree, 352 economy of Arrow-Debreu type, 323 Edmonds's intersection theorem, 3, 20, 112
382
(as special case of Fenchel-type duality), 34, 224 effective domain function over Rn, 9, 21, 77 function over Zn, 21 set function, 103 electrical network, 41, 43, 348 multiterminal, 53 elementary vector, 64 entering arc, 53 epigraph, 79 equilibrium competitive, 325 economy, 325 electrical network, 55 exchange axiom (B-EXC[R]), 118 (B-EXC+pRJ), 118 (B-EXC[Zj), 18, 101 (B-EXC+[Z]), 102 (B-EXC_[Z]), 103 (B-EXC W [ZJ), 103 (B>>-EXC[R]), 118 (B"-EXC[Z]), 117 local, 135 M-convex function, 26, 58, 133 M-convex polyhedron, 118 M-convex set, 18, 101 M^-convex function, 27, 134 M^-convex polyhedron, 118 M^-convex set, 117 (M-EXC[R]), 29, 56, 160 (M-EXC'[R]), 160 (M-EXC[Z]), 26, 58, 133 (M-EXC'[Z]), 26, 133 (M-EXCioc[Z]), 135 (M-EXC w [Zj), 137 (M>i-EXC[R]), 29, 47, 162 (M^-EXC'[R]), 162 (M^-EXC+[R]), 48 (M^-EXC[Z]), 27, 134 (Mb-EXC'[Z]), 134 (-M"-EXC[Z]), 330 matroid, 69 multiple, 333
Index
polyhedral M-convex function, 29, 56, 160 polyhedral M^-convex function, 29, 47, 162 simultaneous, 69 weak, 137 exchange capacity, 284, 312 exchange economy, 327 extension concave, 93 convex, 93 distance function, 165 local convex, 93 Lovasz, 16, 104, 111 partial order, 108 set function, 16, 104 extreme base, 105 Farkas lemma, 50, 87 feasible 6-, 296
dual problem, 236 flow, 247, 258 minimum cost flow problem, 247 potential, 122 primal problem, 235 set, 1 submodular flow problem, 258 Fenchel duality, 12, 85 Fenchel transformation, 81 Fenchel-type duality generic form, 13 L-convex function, 32, 222 M-convex function, 32, 222 submodular function, 225 fixed constant, 347 flow, 53 ^-feasible, 296 feasible, 247, 258 Frank's discrete separation theorem, 17, 111 (as special case of L-separation), 33, 224 Frank's weight-splitting theorem, 34, 225 fully combinatorial algorithm, 290
Index
fundamental circuit, 149 g-polymatroid, 117 generalized polymatroid, 117 generator, 45 global minimizer, 79 global optimality, 2 global optimum, 9 goods divisible, 327 indivisible, 323 gradient, 80 graph acyclic, 107 bipartite, 89 directed, 52, 88 Grassmann-Pliicker relation, 69 greedy algorithm, 3, 108 gross substitutes property, 153, 331 stepwise, 155, 331 ground set, 70 gyrator, 361 Hamiltonian path problem, 257 hole free, 90 ideal, 107 IFF fixing algorithm, 300 IFF scaling algorithm, 298, 299 in kilter, 314 inaccurate number, 347 incidence chain, 88 graph, 88 topological, 347 income, 324 independent set matrix, 68 matroid, 70 indicator function, 79, 90 indivisible commodity, 323 indivisible goods, 323 infimal convolution, 80 integer, 143 by network transformation, 272 initial endowment, 324
383
total, 326 initial vertex, 53 inner product, 79 integer biconjugate, 212 integer infimal convolution, 143 integer interval, 92 integer subdifferential, 166 integral base polyhedron, 18 integral L-convex polyhedron, 131 integral M-convex polyhedron, 118 integral neighborhood, 93 integral polyhedral convex function, 161 L-convex function, 191 L''-convex function, 192 M-convex function, 161 M^-convex function, 162 integral polyhedron, 90 integrality dual, 161, 252, 261 linear programming, 89 minimum cost flow problem, 252 polyhedral convex function, 161 polyhedral L-convex function, 191 polyhedral M-convex function, 161 polyhedron, 90 primal, 252, 261 submodular flow problem, 261 integrally concave function, 94 integrally convex function, 7, 94 submodular, 189 integrally convex set, 96 intersection convexity in, 92 M-convex, 219 matroid, 3 submodular polyhedron, 20 valuated matroid, 225 intersection theorem Edmonds's, 3, 20, 112 Edmonds's (as special case of Fencheltype duality), 34, 224 M-convex, 219 valuated matroid, 225 weighted matroid, 225 interval
Index
384
closed, 77 integer, 92 open, 77 jump system, 120 kilter diagram, 53, 251 in, 314 out of, 314 Kirchhoff's law, 349 current, 353 voltage, 353 Konig-Egervary theorem for mixed matrix, 358 L-concave function, 22 polyhedral, 190 L-convex cone, 131 L-convex function, 8, 22, 177 dual-integral polyhedral, 191 integral polyhedral, 191 polyhedral, 190 positively homogeneous, 193 quadratic, 52, 182 quasi, 199 semistrictly quasi, 199 L-convex polyhedron, 123, 131 integral, 131 L-convex set, 22, 121 L-optimality criterion, 185, 193 quasi, 201 L-proximity theorem, 186 quasi, 201 L-separation theorem, 33, 218 L2-optimality criterion, 232 L2-proximity theorem, 232 L2-convex function, 229 L2-convex set, 128 L^-convex function, 229 L2-convex set, 129 L''-convex function, 8, 23, 178 integral polyhedral, 192 polyhedral, 192 quadratic, 48, 52, 182 L^-convex polyhedron, 129, 131
L^-convex set, 121, 128 Lagrange duality, 234 Lagrangian function, 236 dual, 242 laminar convex function, 141 by network transformation, 273 laminar family, 141 Laplace transform, 351 lattice, 292 distributive, 292 sub-, 104 leading principal minor, 40 leading principal submatrix, 40 leaving arc, 52 Legendre-Fenchel transform concave, 11, 81 convex, 10, 81 discrete, 13, 212 Legendre-Fenchel transformation concave, 11, 81 convex, 10, 81 discrete, 13, 212 Legendre transformation, 81 level set, 172 linear extension partial order, 108 set function, 16, 104 linear order, 108 linear program, 87 dual problem, 87 primal problem, 87 linear programming, 86 duality, 87 linearity in direction 1, 177, 190 local convex extension, 93 local optimality, 2 local optimum, 10 Lovasz extension, 16, 104, 111 LP, 87 duality, 87 M-concave function, 8, 26 polyhedral, 160 M-convex cone, 119 M-convex function, 8, 26, 133 dual-integral polyhedral, 161
Index integral polyhedral, 161 polyhedral, 160 positively homogeneous, 164 quadratic, 52, 139 quasi, 169 semistrictly quasi, 169 M-convex intersection problem, 219, 264 theorem, 219 M-convex polyhedron, 108, 118 integral, 118 M-convex program, 235 M-convex set, 27, 101 M-convex submodular flow problem, 256 economic equilibrium, 341 M-matrix, 42 M-minimizer cut, 149 with scaling, 158 M-optimality criterion, 148, 163 quasi, 173 M-proximity theorem, 156 quasi, 174 M-separation theorem, 33, 217 M2-optimality criterion, 227, 228 M2-proximity theorem, 228 M2-convex function, 226 Mg-convex set, 116 M2-convex function, 226 M^-convex set, 117 M^-convex function, 8, 27, 134 integral polyhedral, 162 polyhedral, 161 quadratic, 48, 52, 139 M^-convex polyhedron, 117, 118 M^-convex set, 102, 117 Markovian, 45 matching, 89 bipartite, 89 perfect, 89 weighted, 89, 266 mathematical programming, 1 matrix compartmental, 43 incidence (chain), 88
385
incidence (graph), 88 M-, 42 mixed, 354 mixed polynomial, 355 mixed skew-symmetric, 361 node admittance, 42 polynomial, 71, 354 positive-definite, 39 positive-semidefinite, 39 principal sub-, 40 totally unimodular, 88 matroid, 70 induction through a graph, 270 intersection problem, 34, 225 valuated, 72 max-flow min-cut theorem for submodular flow, 259 maximum submodular flow problem, 259 maximum weight circulation problem, 61 mechanical system, 350 midpoint convexity, 9 discrete function, 23, 180 discrete set, 129 Miller's discrete convex function, 98 min-max relation, 2 minimizer, 79 global, 9, 79 integrally convex function, 94 L-convex function, 185, 305 L2-convex function, 232 local, 10 M-convex function, 148, 281 M2-convex function, 227, 228 maximal, 290, 291, 304, 307 minimal, 290, 291, 305, 307 submodular set function, 288 minimizer cut M-convex function, 149 M-convex function with scaling, 158 quasi M-convex function, 174 quasi M-convex function with scaling, 175 minimum cost flow problem, 53, 245
386
integer flow, 246 minimum cut, 316 minimum spanning tree problem, 149 Minkowski sum, 80, 90 convexity in, 92 discrete, 90 integral, 90 minor, 40, 359 leading principal, 40 principal, 40 mixed matrix, 354 mixed polynomial matrix, 355 mixed skew-symmetric matrix, 361 money, 323 monotonicity, 54 multimodular function, 183 multiple exchange axiom, 333 multiterminal electrical network, 53 negative cycle, 122, 252, 263 criterion, 252, 263, 264 negative support, 18 neighborhood, integral, 93 network, 53 auxiliary, 252, 263 electrical, 53 transformation by, 270 network flow duality, 268 electrical network, 41, 43 L-convexity, 24, 31, 56, 58, 270 M-convexity, 28, 31, 56, 58, 270 maximum weight circulation, 61 minimum cost flow, 245 multiterminal, 53 submodular flow, 255 no complementarities property, 332 strong, 332 node, 52 node admittance matrix, 42 normal contraction, 45 objective function, 1 off-diagonal nonpositivity, 41 open interval, 77 optimal potential, 89, 251
Index
optimal value function, 236 optimality global, 2, 9 local, 2, 10 optimality criterion integrally convex function, 94, 95 L-convex function, 185, 193 L2-convex function, 232 M-convex function, 148, 163 M-convex submodular flow, 262264 M2-convex function, 219, 227, 228 minimum cost flow, 249, 252 by negative cycle, 252, 263, 264 by potential, 249, 260, 262 quasi L-convex function, 201 quasi M-convex function, 173 submodular flow, 260 submodular set function, 185 sum of M-convex functions, 219 valuated matroid intersection, 225 weighted matroid intersection, 225 optimization combinatorial, 3 continuous, 1 discrete, 3 optimum global, 9 local, 10 out of kilter, 314 pairing, 79 parallel, 62 partial order acyclic graph, 107 extreme base, 108 perfect matching, 89 minimum weight, 89, 266 Poisson equation, 41, 43, 47 polar cone, 82 polyhedral convex function, 25, 80 L-concave function, 190 L-convex function, 190 L^-convex function, 192 M-concave function, 160
Index
M-convex function, 160 M^-convex function, 161 method, 8 polyhedron base, 105 convex, 78 integral, 90 integral L-convex, 131 integral M-convex, 118 L-convex, 123, 131 L^-convex, 129, 131 M-convex, 108, 118 M^-convex, 117, 118 rational, 90 submodular, 112 polynomial matrix, 71, 354 mixed, 355 polytope, 90 positive definite, 39 positive semidefinite, 39 positive support, 18 positively homogeneous function, 7, 82 L-convex function, 193 M-convex function, 164 potential, 41, 53, 89, 248 criterion, 249, 260, 262 optimal, 251 primal-dual algorithm, 315 primal integrality, 252, 261 intersection theorem, 20, 114 linear programming, 89 primal problem, 87 principal minor, 40 principal submatrix, 40 leading, 40 producer, 323 production, 323 profit, 324 function, 324 projection base polyhedron, 117 function to subset, 143, 162 M-convex function, 134 M-convex polyhedron, 118 M-convex set, 102
387
M2-convex function, 226 Mg-convex set, 117 polyhedral M-convex function, 161 proper convex function, 77 proximity theorem, 156 L-convex function, 186 L2-convex function, 232 M-convex function, 156 M2-convex function, 228 quasi L-convex function, 201 quasi M-convex function, 174 pseudopolynomial algorithm, 288 quadratic form, 39 function, 39 L-convex function, 182 L^-convex function, 48, 52, 182 M-convex function, 139 M-convex function, 48, 52, 139 quasi convex, 168 semistrictly, 168 quasi L-convex function, 199 quasi L-optimality criterion, 201 quasi L-proximity theorem, 201 quasi linear, 324 quasi M-convex function, 169 quasi M-minimizer cut, 174 with scaling, 175 quasi M-optimality criterion, 173 quasi M-proximity theorem, 174 quasi-separable concave function, 334 convex function, 140 quasi submodular, 198 semistrictly, 198 rank function matrix, 69 matroid, 70 rational polyhedron, 90 reduced cost, 249, 251 relative interior, 78 reservation value function, 325 resistance, 41 resolvent, 45
388
resource allocation problem, 4, 176 restriction function to interval, 92 function to subset, 143, 162 L-convex function, 178 L-convex polyhedron, 131 L-convex set, 121 L2-convex function, 229 L2-convex set, 129 polyhedral L-convex function, 192 rigidity, 361 ring family, 104, 107, 292 saddle-point theorem, 238 scaling, 145 conjugate, 319 cost, 318 domain, 145 nonlinear, 170, 199 scaling algorithm L-convex function, 308 M-convex function, 283, 287 M-convex submodular flow, 320 semigroup, 45 semistrictly quasi convex, 168 semistrictly quasi L-convex, 199 semistrictly quasi M-convex, 169 semistrictly quasi submodular, 198 separable concave function, 333 quasi, 334 separable convex function, 10, 95, 140, 182 with chain condition, 182 quasi, 140 separation theorem convex function, 2, 11, 84 convex set, 35, 83 generic discrete, 13, 216 L-convex function, 218 L-convex set, 36, 126 M-convex function, 217 M-convex set, 36, 114 submodular function, 17, 111 series, 62 simple cycle, 62 single improvement property, 332
Index
spanning tree, 149 stable marriage problem, 345 stable matching problem, 345 steepest descent algorithm L-convex function, 305, 306 M-convex function, 281 steepest descent scaling algorithm L-convex function, 308 M-convex function, 283 stepwise gross substitutes property, 155, 331 stoichiometric coefficient, 350 strictly convex function, 77 strong duality, 87 strong no complementarities property, 332
strongly polynomial algorithm, 288 structural equation, 54, 349 subdeterminant, 40, 359 subdifferential, 80 concave function, 217 discrete function, 166 integer, 166 subgradient, 80 discrete function, 166 sublattice, 104 submatrix leading principal, 40 submodular, 62, 206 function, 16, 44, 70, 104 function on distributive lattice, 292 integrally convex-function, 7, 189 polyhedron, 20, 112 utility function, 330 submodular flow problem, 255 economic equilibrium, 341 feasibility theorem, 258 M-convex, 256 maximum, 259 submodular function minimization IFF fixing algorithm, 300 IFF scaling algorithm, 298, 299 Schrijver's algorithm, 293 submodularity, 44, 177, 190 inequality, 16, 44, 177 local, 180
Index
substitutes, 62 successive shortest path algorithm, 312 sum
of functions, 80 of M-convex functions, 226 supermodular, 16, 62, 105, 145, 206 function 105 supply correspondence, 324 set, 324 support function, 82 negative, 18 positive, 18 system parameter, 347 tension, 53 another convention, 253 terminal vertex, 52, 53 tight set, 108 transformation by network, 269 of flow type, 269 of potential type, 269 transitive, 107, 119 translation submodularity, 23, 44, 178 triangle inequality, 24, 122 two-stage algorithm, 310 unimodular totally, 88 unique-min condition, 266 unit contraction, 45 unit demand preference, 334 univariate function, 10 discrete convex, 95 polyhedral convex, 80 utility function, 324 valuated matroid, 7, 72, 225 intersection problem, 225 valuation, 72 variational formulation, 43, 55 vertex, 52 initial, 53 terminal, 53 voltage, 41, 53
389
voltage potential, 55 weak duality, 87 exchange axiom, 137 weakly polynomial algorithm, 288 weight splitting matroid intersection, 34, 225 valuated matroid intersection, 225
weak
z-transform, 355