|
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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-09} |