A Discrete Convex Min-Max Formula for Box-TDI Polyhedra

András Frank, Kazuo Murota


A min-max formula is proved for the minimum of an integer-valued separable discrete convex function where the minimum is taken over the set of integral elements of a box total dual integral (box-TDI) polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in non-linear optimization) but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization. The presented framework provides a unified background for separable convex minimization over the set of integral elements of the intersection of two integral base-polyhedra, submodular flows, L-convex sets, and polyhedra defined by totally unimodular (TU) matrices. As an application, we show how inverse combinatorial optimization problems can be covered by this new framework.

Bibtex entry:

AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {A Discrete Convex Min-Max Formula for Box-TDI Polyhedra},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-09}

Last modification: 29.12.2020. Please email your comments to Tamás Király!