Min-Max Formulas for Separable Discrete Convex Minimization on Box-TDI Polyhedra
E¨otv¨os University Budapest Andr´as FRANK 01603194 Tokyo Metropolitan University *Kazuo MUROTA
1. Introduction
In discrete convex analysis [6], Fenchel-type min-max formulas are discussed for L- and M- convex functions and convex-cost integral flows.
The following is an example of such min-max formula for minimization of square-sum of com- ponents over an M-convex set (the set of integer points of an integral base-polyhedron).
Theorem 1 ([4]). Let B ⊆ Rn be an inte- gral base-polyhedron and p be the associated integer-valued supermodular function. Then
min{∑
1≤i≤n
z2i :z∈B∩Zn}
= max{p(w)ˆ − ∑
1≤i≤n
⌊wi 2
⌋ ⌈wi 2
⌉
: w∈Zn},
where p is the linear (or Lov´asz) extension of p.ˆ The objective of this paper is show that the discrete Fenchel-type min-max formula holds for integer-valued separable convex functions defined on the set of integral elements of a box- TDI polyhedronR. Details are given in [5].
An important special case is where R is de- scribed by a totally unimodular matrix. This in- cludes the case of L-convex or L♮-convex sets.
It can be proved that L♮2-convex (in particular, L2-convex) sets are also discrete box-TDI sets.
Another special case is the one of integral sub- modular flows, in particular, M2-convex and M♮2- convex sets.
2. TDI and discrete convex function
A (rational) linear system Qx ≥ p is called totally dual integral(orTDI) [1] if the maximum in the LP duality
min{cx:Qx≥ p} = max{yp:y≥0,yQ=c}
has an integral optimal solution y for every in- tegral vectorcfor which the maximum is finite.
The systemQx≥ pis calledbox-totally dual in- tegral (orbox-TDI) if the system [Qx ≥ p, f ≤ x≤ g] is TDI for every choice of rational bound- ing functions f ≤ g. A polyhedron is called a box-TDI polyhedron if it can be described by a box-TDI system [1, 3]. See also [2, 7].
A functionφ:Z→Z∪{+∞}is calleddiscrete convexifφ(k−1)+φ(k+1)≥ 2φ(k) for eachk withφ(k)<+∞. A functionΦ:Zn →Z∪{+∞}
is called aseparable discrete convex function if it is represented as
Φ(z)= ∑
1≤i≤n
φi(zi) (1)
with discrete convex functions φ1, . . . , φn. The discrete conjugateφ• of a functionφ:Z→Z∪ {+∞}is defined, for integersℓ, by
φ•(ℓ)=max{kℓ−φ(k) :k∈Z}.
The discrete conjugateΦ• ofΦis given, forw ∈ Zn, by
Φ•(w)=max{wz−Φ(z) :z∈Zn}= ∑
1≤i≤n
φ•i(wi),
wherewzdenotes the inner product ofwandz.
3. Main results
Let R be an integral box-TDI polyhedron in Rn. We assume thatΦis an integer-valued sepa- rable discrete convex function, finite-valued and bounded from below onR∩Zn.
The following is a Fenchel-type duality theo- rem using function µR(w) = min{wx : x ∈ R}, which coincides with ˆp(w) whenRis an integral base-polyhedron.
2-B-7
日本オペレーションズ・リサーチ学会2021年 春季研究発表会
Theorem 2. Let R be an integral box-TDI poly- hedron inRn. Then
min{Φ(z) :z∈R∩Zn}
=max{µR(w)−Φ•(w) :w∈Zn}.
The second theorem makes explicit reference to a description ofR.
Theorem 3. Let Q be an integral m ×n matrix and p an integral vector. Assume that Qx≥ p is box-TDI and let R={x: Qx≥ p}. Then
min{Φ(z) :z∈R∩Zn}
= max{yp−Φ•(yQ) :y≥0, integer-valued}, where the optimal y∈Zmcan be chosen to have at most2n positive components.
4. Special cases
Theorem 4 (Square-sum on box-TDI set). Let R={x: Qx≥ p}be a box-TDI polyhedron.
min{∑
1≤i≤n
z2i :z∈R∩Zn}
=max{yp− ∑
1≤i≤n
⌊wi
2
⌋ ⌈wi
2
⌉
: w=yQ,y∈Zm+}, where z∗ ∈ R∩Zn is a minimizer if and only if there exists an integer vector y∗ ≥ 0 such that y∗(Qz∗− p) = 0 and ⌊y∗Q/2⌋ ≤ z∗ ≤ ⌈y∗Q/2⌉. More generally, for positive c∈Zn,
min{∑
1≤i≤n
ciz2i :z∈R∩Zn}
=max{yp− ∑
1≤i≤n
⌊wi+ci 2ci
⌋ ( wi−ci
⌊wi+ci 2ci
⌋),
w= yQ: y≥ 0 integral},
where z∗ ∈ R∩Zn is a minimizer if and only if there exists an integer vector y∗ ≥ 0 such that y∗(Qz∗ − p) = 0 and ⌈(y∗Q−c)/(2c)⌉ ≤ z∗ ≤
⌊(y∗Q+c)/(2c)⌋.
Theorem 5(Square-sum on M2-convex set [4]).
Let B1 and B2 be integral base-polyhedra with associated supermodular functions p1 and p2, where B1∩B2 ,∅is assumed. Then
min{∑
1≤i≤n
z2i :z∈B1∩B2∩Zn}
= max
w,u∈Zn{pˆ1(w)+ pˆ2(u)−∑
1≤i≤n
⌊wi+ui 2
⌋ ⌈wi+ui 2
⌉},
where pˆk is the linear (Lov´asz) extension of pk. Network flow: Let D = (V,A) be a digraph and m ∈ ZV be a vector with zero component- sum. An m-flow means a flow (a vector on A) that meets the supply-demand requirement rep- resented by m. For a potential functionπ onV, the potential difference is denoted by∆π(uv) = π(v)−π(u) foruv∈A.
Theorem 6. The minimum square-sum of an in- tegral m-flow is equal to
max{mπ−⌊∆π 2
⌋ ⌈∆π 2
⌉
:π :V →Z+}.
The minimum square-sum of a non-negative in- tegral m-flow is equal to
πmax:V→Z+{mπ−⌊max(∆π,0) 2
⌋ ⌈max(∆π,0) 2
⌉}.
Acknowledgements: This work was partially supported by National Research, Development and Innovation Fund of Hungary (FK-18) - No.NKFI-128673, and by JSPS KAKENHI Grant Number JP20K11697.
References
[1] J. Edmonds and R. Giles, A min-max re- lation for submodular functions on graphs, Ann. Disc. Math., 1 (1977), 185–204.
[2] P. Chervet, R. Grappe, L.-H. Robert, Box- total dual integrality, box-integrality, and equimodular matrices, Math. Prog., A (on- line), 2020.
[3] W. Cook,On box totally dual integral poly- hedra, Math. Prog., 34 (1986) 48–61.
[4] A. Frank and K. Murota,Discrete decreas- ing minimization, Part II: Views from dis- crete convex analysis, arXiv: 1808.08477, 2018.
[5] A. Frank and K. Murota, A discrete con- vex min-max formula for box-TDI polyhe- dra, arXiv: 2007.03507, 2020.
[6] K. Murota, Discrete Convex Analysis, SIAM, 2003.
[7] A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.
