NIPS workshop: Discrete Optimization in Machine Learning:
Connecting Theory and Practice(Lake Tahoe, December 9, 2013)

Discrete Convex Analysis:
Basics, DC Programming, andSubmodular Welfare Algorithm

Kazuo Murota (U. Tokyo)

131209NIPSlakeTahoe
1Discrete Convex Analysis
Convexity Paradigm in Discrete Optimization

Matroid Theory + Convex Analysis
Submodular fn ↔ Matroid base⇓⇓L-convex fn↔ M-convex fn

6-• Global optimality ⇐⇒ local optimality• Conjugacy:

Legendre–Fenchel transform• Duality (Fenchel min-max, discrete separation)• Minimization algorithms• Applications:OR, game, economics, matrices
2Applications• Combinatorial optimization– matching, even factor, min-cost ﬂow,
shortest path, min-cost tension• Mathematical economics / Game theory– Walrasian equilibrium, stable marriage• Operations research– inventory, queueing, resource allocation• Discrete structures– ﬁnite metric space• Algebra– polynomial matrix, tropical geometry3Some History
1935 Matroid

Whitney, Nakasawa

1965 Submodular function

Edmonds

1975 Application of matroid

Iri, Recski

1983 Submodularity and convexity
Lovász, Frank, Fujishige

1990 Valuated matroid
Integrally convex fn
1996 Discrete convex analysis

Dress–Wenzel
Favati–Tardella
Murota2000 Submod. fn minimization algorithm
Iwata–Fleischer–Fujishige, Schrijver
4

Contents
B1. Submodularity and Convexity
B2. L-convex and M-convex Functions
B3. Conjugacy — Legendre transform
B4. Duality
Recent Topics(with T. Maehara)

T1. Discrete DC Programming↖

use of conjugacy

T2. Valuated Matroid-Based
Submodular Welfare Algorithm↖

use of duality5

B1.
Submodularity and Convexity

6Submodular Function
Set function ρ is submodular:X ∪Y

ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )X

g : Zn → R

is submodular:g(p) + g(q) ≥ g(p ∨ q) + g(p ∧ q)

q

X ∩Y

Y

compnt-max
p∨qp∧q
compnt-minp7

Submodularity & Convexity in 1980’s
ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )• min/max algorithms(Grötschel–Lovász–Schrijver/ Jensen–Korte, Lovász)

min ⇒ polynomial,• Convex extension

max ⇒ NP-hard(Lovász)

set fn is submod ⇔ Lovász ext is convex• Duality theorems(Edmonds, Frank, Fujishige)

discrete separation, Fenchel min-max

Duality for submodular set functions= Convexity + Discreteness8Frank’s Discrete Separation(Frank 82)

ρ : 2V → R: submodular(ρ(∅) = 0)

µ : 2V → R: supermodular(µ(∅) = 0)•

ρ(X) ≥ µ(X)(∀X ⊆ V ) ⇒ρ(X) ≥ x∗(X) ≥ µ(X)•∃ x∗ ∈ RV :(∀X ⊆ V )ρ, µ: integer-valued ⇒ x∗ ∈ ZV

Equivalent to Edmonds’ polymatroid intersection
9

On the other hand . . .
decreasing
marginal return ←→ concave/submodularThis means . . .
Submodular ≈ Concave

Moreover . . .
ρ(X) = φ(|X|) (φ: concave) is submodular
10Submodularity & Convexity in DCA• M♮-concave function is submodular• L♮-convex

function is submodular
submodular

M♮-

L♮ -

concaveconvex• Sum of M♮-concave fns is submodular• Sum of L♮-convex fns is L♮-conv (subm)
11

B2.
L-convex and M-convex
Functions12Discrete Convex Functions
functions Zn → R
convex-extensible

L♮

SeparableM♮

f : Zn → R

f is convex-extensible⇔ ∃ convex f :f (x) = f (x)Convex-extensibility does not help much
13

Discrete Convex Functions
f (x)

g(p)

x2
p2

p1

x1

L♮-convex fn

M♮-convex fn

14L♮-convexity from Mid-pt-convexity(Murota 98, Fujishige–Murota 00)
6qq

q p+q p
2

-

p+q
2

=⇒
p

p

Mid-point convex ((g : Rn )→ R):
p+qg(p) + g(q) ≥ 2g
2=⇒ Discrete mid-point convex (g : Zn → R)(⌈p+qg(p) + g(q) ≥ g
2L♮-convex function

⌉)

(⌊

⌋)

p+q
+g
2
(L = Lattice)15

Mid-pt Convexity for 01-Vectorsq

For p, q ∈ {0, 1}n
⌊

p+q
2

⌋

⌈

6

p+q
2

⌉

=p∨q

p=p∧q

Discrete mid-pt convexity:
(⌈
⌉)
(⌊
⌋)
p+q
p+q
g(p) + g(q) ≥ g+g
2
2⇐⇒ Submodularity:g(p) + g(q) ≥ g (p ∨ q) + g (p ∧ q)16

L♮-convexity from Submodularity—Original deﬁnition of L♮-convexity—

Def:g : Zn → R is L♮-convex ⇐⇒g̃(p0, p) = g(p − p01) is submodular in (p0, p)g̃ : Zn+1 → R,

1 = (1, 1, . . . , 1, 1)

17Remark: L♮-convex vs Submodular• L♮-convex function is convex-extensible• General submodular function is NOT

Fact 1: Any g : Z → R is submodular• Submodularity does not imply convexity

Fact 2: A function g : Z → R is L♮-convex⇐⇒ g(p − 1) + g(p + 1) ≥ 2g(p) for all p ∈ Z
18

L♮-convex Function: Examples
Quadratic: g(p) =∑∑i⇔ aij ≤ 0

aij pipj is L♮-convex

j(i ̸= j),∑aij ≥ 0 (∀i)

j

Separable convex: For univariate convex ψi and ψij∑∑g(p) =
ψi(pi) +ψij (pi − pj )ii̸=jRange: g(p) = max{p1, p2, . . . , pn} − min{p1, p2, . . . , pn}
Submodular set function: ρ : 2V → R⇔ ρ(X) = g(χX ) for some L♮-convex g
Multimodular: h : Zn → R is multimodular ⇔h(p) = g(p1, p1 + p2, . . . , p1 + · · · + pn) for L♮-convex g
19M♮-convexity from Equi-dist-convexity(Murota 96, Murota–Shioura 99)
6

j

y6

y
y′

x′

=⇒
x

y y ′ x′ x
Equi-distance convex (f : Rn → R):
-

-

x i

f (x) + f (y) ≥ f (x − α(x − y)) + f (y + α(x − y))=⇒ Exchange (f : Zn → R) ∀x, y , ∀i : xi > yi[f (x) + f (y) ≥ min f (x − ei) + f (y + ei),]min {f (x − ei + ej ) + f (y + ei − ej )}xj <yjM♮-convex function(M = Matroid)20

M♮-convex Function: Examples
Quadratic: f (x) =∑∑i⇔ aij ≥ 0,

aij xixj is M♮-convex

jaij ≥ min(aik , ajk ) (∀k ̸∈ {i, j})

Min value: f (X) = min{ai | i ∈ X}

[unit preference]

Matroid rank: f (X) = − rank of X
Cardinality convex: f (X) = φ(|X|)∑
Separable convex: f (x) =φi(xi)(φ: convex)(φi: convex)i

Laminar convex: f (x) =∑φA(x(A))(φA: convex)

A{A, B, ....}: laminar ⇔ A ∩ B = ∅ or A ⊆ B or A ⊇ B
21

Matching / Assignment
U
u1
u2
u3
u4

V
v1
v2
v3

X = {u1, u2}
u1
v1
u2
v2

X = {u1, u2}
u1
v1
u2
v3

M1

M2

E

Max weight for X ⊆ U

f (X) = max{∑

(w: given weight)

w(e) | M : matching, U ∩ ∂M = X}e∈M

Max-weight func f is M♮-concave(Murota 96)• Proof by augmenting path
• Extension to min-cost network ﬂow
22M♮-concavity = Gross Substitutes
Think of f as a utility function
M♮-concave ⇐⇒ Gross substitutes (+ ∗ ∗)Reijnierse–van Gallekom–Potters 02, Fujishige-Yang 03
Danilov-Koshevoy-Lang 03, M.-Tamura 03

Gross substitutes:(f : utility, p: price)x ∈ arg max(f − p), p ≤ q ,⇒∃ y ∈ arg max(f − q) : yi ≥ xi

if pi = qi=⇒ Applications to economics / game theory
23

Summary: Defs of L♮/M♮-convexity
Continuous Rn → R
Discrete Zn → R
mid-pt convex−→ disc mid-pt convex⇕
discr (L♮-convex)
convex⇕discr (M♮-convex)
equi-dist convex−→ exchange property
j
y

L♮

j

6

y
~

M♮
}

6
~

}
-

x i

-

x i
24

B3.
Conjugacy— Legendre transform25

Discrete Legendre Transformy 6 f (x)y6−f •(p)slope p
-

x

-

x

•
f (p) = maxn {p · x − f (x)}x∈Z⇒

If f : Zn → Z,then f • : Zn → Z(integer-valued)26

M-L Conjugacy Theorem
Integer-valued discrete fn
Legendre transform:f : Zn → Z

f •(p) = sup [⟨p, x⟩ − f (x)]x∈ZnM♮-convex and L♮-convex are conjugate
f 7→ f • = g 7→ g • = f(Murota 98)

function Zn → Z
convex-extensible

M♮

L♮

27

B4.
Duality28

Discrete Separation Theoremf (x)f : Zn → R “convex”
h : Zn → R “concave”• f (x) ≥ h(x)

f (x)

p∗

(∀x ∈ Zn) ⇒

h(x)

h(x)

∃ α∗ ∈ R,∃ p ∗ ∈ Rn :f (x) ≥ α∗ + ⟨p∗, x⟩ ≥ h(x)(x ∈ Zn)• f , h: integer-valued ⇒ α∗ ∈ Z,p∗ ∈ Zn29

Diﬃculty of Discrete Separation (1)f (x, y) = max(0, x + y) convex
h(x, y) = min(x, y)concavenonintegral
separationp∗ = (1/2, 1/2), α∗ = 0 unique separating plane30

Diﬃculty of Discrete Separation (2)Even real-separation is nontrivial
f (x, y) = |x + y − 1|convex2-101h(x, y) = 1 − |x − y|-2
12

concave

0
4
-1
2
-2
0
-2

• f (x, y) ≥ h(x, y) (∀(x, y) ∈ Z2) true
• No α∗ ∈ R, p∗ ∈ R2:

f (x) ≥ α∗ + ⟨p∗, x⟩ ≥ h(x)∵ f = 0 < h = 1 at (x, y) = (1/2, 1/2)
31

Discrete Separation Theorems(Murota 96/98)
M-separation Thm (for M♮-convex)⇒ Weight splitting for weighted matroid intersection(Iri-Tomizawa 76, Frank 81)(linear fn, indicator fn = M♮-convex fn)

L-separation Thm (for L♮-convex)⇒ Discrete separ. for submod. set fn (Frank 82)(submod. set fn = L♮-convex fn on 0–1 vectors)(1) f (x) ≥ h(x)(∀x) ⇒ ∃ α∗ ∈ R, ∃ p∗ ∈ Rn:

f (x) ≥ α∗ + ⟨p∗, x⟩ ≥ h(x)(x ∈ Zn)(2) f , h: integer-valued ⇒ α∗ ∈ Z, p∗ ∈ Zn
32

Min-Max Duality
f : M♮-convex,

h: M♮-concave（Zn → Z）

Legendre–Fenchel transformf •(p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn}h◦(p) = inf {⟨p, x⟩ − h(x) | x ∈ Zn}

Fenchel-type Duality Thm (Murota 96, 98)◦•
inf n{f (x) − h(x)} = sup {h (p) − f (p)}
x∈Z
p∈Zn

self-conjugate（f •: L♮-convex, h◦: L♮-concave)=⇒ Edmonds’ matroid intersection thm
33

Relation among Duality Thms
Discrete Convex

Combinatorial Opt.

M-separationf (x) ≥ Lin ≥ h(x)⇕Fenchel duality
inf {f − h}= sup{h◦ − f •}Fenchel duality (Fujishige 84)
matroid intersect. (Edmonds 70)
⇕





 ⇒ discrete separ. for submod(Frank 82)⇒ valuated matroid intersect.
(Murota 96)⇕

L-separationf •(p) ≥ Lin ≥ h◦(p)⇓weighted matroid intersect.
(Edmonds 79, Iri-Tomizawa 76,
Frank 81)34

Summary (Part of “Basics”)• Submodularity vs Convexity
submodular=convex (1980’s), submodular=concave• Deﬁnitions of L♮-convex and M♮-convex
mid-point convexity, exchange, gross substitutes• Conjugacy
discrete Legendre transform, L♮ ↔ M♮, f •• = f• Duality
discrete separation, L-/M-separ., Fenchel min-max• Global minimality ⇐⇒ local minimality• Minimization algorithms: greedy, subm-min, scaling• Continuous Variables• Applications:OR, game, economics, matrices
35

T1.
Discrete DC Programming—Use of Conjugacy
T. Maehara, K. Murota: A framework of discrete
DC programming by discrete convex analysis, 201336

Discrete DC Program
DC = Diﬀerence of Convex

min {g(x) − h(x)}x∈Zng, h: “convex”

Convexity:

M♮–M♮, M♮–L♮, L♮–M♮, L♮–L♮

Variable:x ∈ Zn,x ∈ {0, 1}n37

DC Algorithm(Pham Dinh Tao, 1985(ca.))min{g(x) − h(x)}=⇒min{g(x) − ⟨p, x⟩}

subgradient p ∈ ∂h(x)Algorithm 1
DC algorithm
Let x(1) be an initial solution
for k = 1, 2, . . . do
(Dual phase) Pick p(k) ∈ ∂h(x(k))(Primal phase) Pick x(k+1) ∈ argmin (g − p(k))
if (g − p(k))(x(k)) = (g − p(k))(x(k+1)) thenReturn x(k)end ifend for• concave-convex proc (Yuille–Rangarajan 03)• submod-supermod proc (Narasimhan–Bilmes 05)
cf. supermod-submod proc, mod-mod proc
(Iyer–Bilmes 12; Iyer–Jegelka–Bilmes 13)38

Integral Subgradients & Biconjugacy
In general:∂Zf (0) = ∅,f •• ̸= f

Example: D = {(0, 0, 0), ±(1, 1, 0), ±(0, 1, 1), ±(1, 0, 1)}{(x1 + x2 + x3)/2, x ∈ D,
f (x1, x2, x3) =
+∞,
o.w.

D is “convex”: conv(D) ∩ Zn = D∂fR(0) = {(1/2, 1/2, 1/2)},∂Zf (0) = ∅f ••(0) = − inf max{0, |p1+p2−1|, |p2+p3−1|, |p3+p1−1|}p∈Z3

f ••(0) = −1 ̸= 0 = f (0)39Subgradient of M♮-/L♮-convex Func
For f : Zn → Z
integral subdiﬀerential / subgradient∂f (x) = {p ∈ Zn | f (y) − f (x) ≥ ⟨p, y − x⟩ (∀y)}
f : M♮-convex⇒∂f (x) ̸= ∅: L♮-convex set− pi ≤ f (x − χi) − f (x),pj ≤ f (x + χj ) − f (x),pj − pi ≤ f (x − χi + χj ) − f (x)f : L♮-convex⇒(∀i, j)∂f (x) ̸= ∅: M♮-convex set

f (x) − f (x − χA) ≤ ⟨p, χA⟩ ≤ f (x + χA) − f (x) (∀A)

40

Optimality Conditions minn{g(x) − h(x)}x∈Zx: global opt ⇐⇒ ∂ϵg(x) ⊇ ∂ϵh(x) (∀ϵ ≥ 0)⇓∂g(x) ⊇ ∂h(x)⇓x: local opt, i.e., x: minimum in∪∂h•(p)U =p∈∂g(x)∂ϵf (x) = {p ∈ Rn | f (y) − f (x) ≥ ⟨p, y − x⟩−ϵ (∀y)}
41

Discrete DC Algorithmminn{g(x) − h(x)}x∈Zminn{g(x) − ⟨p, x⟩}=⇒x∈Z
integral subgradient p ∈ ∂h(x)Algorithm 2
Discrete DC algorithm
Let x(1) be an initial solution
for k = 1, 2, . . . do
(Dual phase) Pick p(k) ∈ ∂h(x(k)) \ ∂g(x(k))(Primal phase) Pick x(k+1) ∈ argmin (g − p(k))
if (g − p(k))(x(k)) = (g − p(k))(x(k+1)) thenReturn x(k)end ifend for• monotone decreasing g(x) − h(x)• ∂g(x) ⊇ ∂h(x) guaranteed• local optimality within U =

∪

•(p)
∂h
p∈∂g(x)42

Testing for Local Opt: ∂g(x) ⊇ ∂h(x)M♮–M♮: poly-time(explicit O(n2) ineqs)

M♮–L♮: poly-time(O(n2) M-min)L♮–M♮: poly-time(L-min, submod-min)

L♮–L♮: NP-hard(submod containment)⇒ M♮–M♮ by Toland-Singer duality

43

Discrete Toland-Singer Dualityf •(p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn}

g : Zn → Z: any fn;

h : Zn → Z: M♮- or L♮-convex

Toland-Singer Duality Thm (Maehara-Murota 13)••
inf n{g(x) − h(x)} = infn{h (p) − g (p)}x∈Z
p∈Z

(Proof) Integral biconjugacy: h•• = h.
inf {g(x) − h(x)} = inf {g(x) − h••(x)}x

x= inf {g(x) − sup{⟨p, x⟩ − h•(p)}}xp= inf inf {g(x) − ⟨p, x⟩ + h•(p)}x

p= inf {h•(p) − sup{⟨p, x⟩ − g(x)}} = inf {h•(p) − g •(p)}.
p

x

p

44

Summary (“DC Programming”)• Theoretical framework
M♮–M♮, L♮–M♮ (subm), M♮–L♮ (superm), L♮–L♮,
integral subgradient, biconjugacy, Toland-Singer• Local optimality condition∂g(x) ⊇ ∂h(x), checking this condition• Algorithm
monotone, ﬁnite, local opt• Using discrete convex analysis for nonconvex prob
• DC Representability• Hardness of minimization• Approximation guarantee (for some 01 cases)• Computational results (will come)45

T2.
Valuated Matroid-Based
Submodular Welfare Algorithm—Use of Duality
T. Maehara, K. Murota: Valuated matroid-basedalgorithm for submodular welfare problem, 201346

Submodular Welfare Maximization
Maximize f1(X1) + · · · + fm(Xm)s.t. (X1, . . . , Xm): partition of V⇒

NP-hard for general submodular fi

fi: M♮-concave (matroid valuation)⇒ poly-time solvable byvaluated matroid intersection/
partition algorithm(Murota 96)⇒

Add “neg-cycle” heuristics for general fi
cf. ejection chain (Glover 96)
47

Budgeted Allocation Problem(Garg-Kumar–Pandit 01)

fi(X) = min{∑bix, Bi}(X ⊆ V )x∈X

Maximize f1(X1) + · · · + fm(Xm)s.t. X1, . . . , Xm: subpartition of Vm bidders,n items V

bidder i has budget Bi
will pay bix > 0 for item x
48

Budgeted Allocation Problem (R102570)
m = 10, n = 25, Bi = 70
LLN = Lehmann-Lehmann-Nisan (06)
Opt
646
649
650
639
648
649
648
646
649
643
Aver.

LLN (ratio) Proposed (ratio) Cycle
633 (0.979)
643 (0.995)
0/5
635 (0.978)646 (0.995)
0/1
650 (1.000)
0/2
640 (0.984)
625 (0.978)636 (0.995)
0/3
631 (0.973)
648 (1.000)
0/2
649 (1.000)
0/2
639 (0.984)
635 (0.979)
648 (1.000)
0/2
636 (0.984)
645 (0.998)0/1
644 (0.992)
649 (1.000)
0/1
631 (0.981)
642 (0.998)
0/1(0.981)(0.998)“Cycle”: contractions / detected negative cycles
49Min-GAP (Generalized Assignment Problem)fi(X) =

∑

cix

x∈X

if

∑

bix ≤ Bix∈X

Minimize f1(X1) + · · · + fm(Xm)s.t. X1, . . . , Xm: partition of Vm bidders,n items V

bidder i has budget Bi
will pay bix > 0 for item x
gets proﬁt cix0 for item x
50

Min-GAP(ORLIB: types a, b)

Generalized Assignment Problem
Problema05100a05200a10100a10200a20100a20200b05100b05200b10100b10200b20100b20200Chu–Beasley (1997)

Best kwn Proposed (ratio)
Cycle
1698 opt
1698 (1.000)
0/03235 opt
3235 (1.000)
0/01360 opt
1360 (1.000)
0/02623 (1.000)
0/02623 opt
1158 opt
1158 (1.000)
0/02339 opt
2341 (1.001)
0/0
18431855 (1.006)
113/230
3552
3565 (1.003)
4968/5197
1407
1413 (1.004)
0/7
2828
2848 (1.007)
1764/1918
1166
1168 (1.002)
0/3
2340
2343 (1.001)
0/9“Cycle”: contractions / detected negative cycles
P: feasible point diﬃcult to ﬁnd
51

P
P

P

Min-GAP(ORLIB: types c, d)Generalized Assignment Problem
Problemc05100c05200c10100c10200c20100c20200d05100d05200d10100d10200d20100d20200Chu–Beasley (1997)

Best kwn Proposed (ratio)
1931 opt
1969 (1.019)
3482 (1.007)
3456 opt
1402 opt
1415 (1.009)
2806 opt
2820 (1.004)
1243 opt
1257 (1.011)
2391
2402 (1.004)
6353 opt
6729 (1.059)
12743
13272 (1.041)
6349
6662 (1.049)
12436
13058 (1.050)
6196
6528 (1.053)
12264
12974 (1.057)

Cycle
63/1674261/4509
531/5674863/5011
247/226
1241/1311
9/264
2759/3337
683/849
2131/2631
645/6992167/2473“Cycle”: contractions / detected negative cycles
P: feasible point diﬃcult to ﬁnd; F: G ̸= G(M )
52

P
P
P
P
P
PF
P
P
PF
P

Submodular Set Function in DCA• Submodular set func = L♮-convex on {0, 1}n• (Sums of) M♮-concave form a nice subclassf : {0, 1}n → R
submod=L♮-convex
M♮ + M ♮ + M ♮M♮ + M ♮M♮concavef : Zn → R
submodularM♮ concaveL♮convex53

M♮-concave Set Functions
Set function f : 2V → R ∪ {−∞}
M♮-concave or matroid valuation⇐⇒ ∀ X, Y ⊆ V ,∀ x∈X \Y:f (X) + f (Y )

X

Y

x

y

≤ max{f (X − x) + f (Y + x),
max [f (X − x + y) + f (Y + x − y)]}y∈Y \X

Dress–Wenzel (90,92) on bases
54M♮-concave Set Functions
M♮-concave is submodular (NOT conversely)M♮-concave forms a nice subclass for maximization• f (X) = φ(|X|)(φ: concave)∑• f (X) =φA(|A ∩ X|)(φA: concave)A∈T

T : laminar (A, B ∈ T ⇒ A ∩ B = ∅ or A ⊆ B or A ⊇ B )• max-value f (X) = max{ai | i ∈ X}
• matroid rank

(Fujishige 05)

f (X) = max{|I| | I : independent, I ⊆ X}
• weighted matroid rank (w ≥ 0)

(Shioura 09)

f (X) = max{w(I) | I : independent, I ⊆ X}
55

Valuated Matroid Partition
fi: matroid valuations (2V → R)
Maximize f1(X1) + · · · + fm(Xm) =: Φ(X)s.t. {X1, . . . , Xm}: partition of V
Existence of (integral) subgradient (Murota 96)∗, . . . , X ∗ ): optimal(1) (X1m⇐⇒ ∃ p(certiﬁcate of optimality)• X ∗ maximizesfi(X) − p(X) (∀i)

i
• p(V ) = 0(2) fi are integer-valued ⇒ integral p

56

Valuated Matroid Partition Algorithms
Extension of weighted matroid partition

V (1)

s

V

6

V 

V (1)



=
9
y

*

6 6
6

Y

j

V (2)
j

Y
z
:

*
j
~

I

?
?

t

 

6

V (2)
Exchange: fi(X) − fi(X − v + u)
Sink arc:fi(X) − fi(X ± u)
Valuated matroid intersection(Murota 96)• cycle-canceling alg• augmenting path alg• “upper-bound lemma”• “unique-max lemma”
57Augmenting Path Algorithm
Maximize f1(X1) + · · · + fm(Xm) =: Φ(X)s.t. {X1, . . . , Xm}: partition of V
Algorithm 3 Augmenting path algorithm
1: Let M = ∅ be an initial solution
2: for k = 1, . . . , n do
3:
Find a shortest path P from source-vertex s to sink-vertex t
4:Update M ← (M ∆P ) ∩ E
5: end for
V (1)

V 
s



=
9
y

*

6 6
6

Y

j

j

I
Y
z
:

*
j
~

Exchange: fi(X) − fi(X − v + u)

6

?
?

 

6

V (2)

Sink arc:tfi(X) − fi(X ± u)

58

Cycle-canceling Algorithm
Maximize f1(X1) + · · · + fm(Xm) =: Φ(X)s.t. {X1, . . . , Xm}: partition of V
|X1 ∪ · · · ∪ Xm| = k
Algorithm 4 Cycle-canceling algorithm
1: Let M be an initial matching of size k
2: loop3:
Find a negative cycle C with the fewest edges4:
if there are no negative cycles then5:
return M as an optimal solution
=
9
y
6:
else
Y
~
7:
M ← (M ∆C) ∩ E
8:end if
9: end loop

6
*

66 I
Y
6
z
:

*
j
j

j

?
?

 

6

59

Algorithm 5 Proposed algorithm for submodular welfare problem
1: Let M = ∅ be an initial solution
2: for k = 1, . . . , n + 1 do
3:
G ← G(M )
4:
loop
5:
Find a negative cycle C with the fewest edges in G
6:
if there are no negative cycles then break end if
7:
Let M ′ := (M ∆C) ∩ E
8:if Φ(M ′) > Φ(M ) then

6


66 I
Y
6

*
M ← M ′; G ← G(M )

=
9
*
10:
else
y
j
Y
11:
Set γ(e) ← 0 for all e ∈ C in G
~
j
?
12:
end if?
13:
end loop6j14:
if k < n then15:
Find a shortest path P of G from source s to sink t
16:
Update M ← (M ∆P ) ∩ E
17:
end if
18: end for

9:

z
:
 

60

Summary (“Submodular Welfare”)• Algorithm
based on valuated-matroid partition algs
exact for a subclass of submodular welfare
negative-cycle heuristics• Computational results
fairly good performance• Using discrete convex analysis for nonconvex prob
• 1/2 approx ratio

under an a posteriori assumption• More computational experiments (will come)61

BooksMurota: Matrices and Matroids for Systems Analysis,
Springer, 2000/2010 (Chap.5)(valuated matroid intersection algorithm)
Murota: Discrete Convex Analysis, SIAM, 2003
Fujishige: Submodular Functions and Optimization,
2nd ed., Elsevier, 2005 (Chap. VII)

62

Survey/Slide/Video/Software[Survey]
Murota: Recent developments in discrete convex
analysis (Research Trends in Combinatorial
Optimization, Bonn 2008, Springer, 2009, 219–260)[Slide] [Video]
http://www.misojiro.t.u-tokyo.ac.jp/ murota/publist.html#DCA[Video]https://smartech.gatech.edu/xmlui/handle/1853/43257/
https://smartech.gatech.edu/xmlui/handle/1853/43258/[Software] DCP (Discrete Convex Paradigm)
http://www.misojiro.t.u-tokyo.ac.jp/DCP/

63

E N D64