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

András Frank () and Kazuo Murota ()
Additional contact information
András Frank: MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös University, Budapest H-1117, Hungary
Kazuo Murota: School of Business Administration, Tokyo Metropolitan University, Tokyo 192-0397, Japan

Mathematics of Operations Research, 2022, vol. 47, issue 2, 1026-1047

Abstract: A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear 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 matrices. As an unexpected application, we show how a wide class of inverse combinatorial optimization problems can be covered by this new framework.

Keywords: Primary: 90C27; secondary: 90C25; 90C10; min-max formula; discrete convex function; combinatorial inverse problem; integral base-polyhedron; M-convex set; total dual integrality (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1160 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:1026-1047

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().