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

Frank, András and Murota, Kazuo (2022) A Discrete Convex Min-Max Formula for Box-TDI Polyhedra. MATHEMATICS OF OPERATIONS RESEARCH, 47 (2). pp. 1026-1047. ISSN 0364-765X

Preview

Text 2007.03507.pdf Download (356kB) | Preview

Abstract

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 unexpected application, we show how a wide class of inverse combinatorial optimization problems can be covered by this new framework.

Actions (login required)

Edit Item