Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization
Abstract
This paper considers convex envelopes of disjunctive submodular functions---functions that are lattice family submodular over faces of a hypercube---and constructs the first strongly polynomial algorithm for their separation when there are two facial disjunctions. Submodular functions, whose convex envelopes are characterized by the Lovász extension, have occupied a fundamental role in constructing relaxations for combinatorial and nonlinear optimization problems. However, disjunctive submodular function envelopes have not been explored besides the use of ellipsoid algorithm, which remains practically intractable. Our algorithm is derived in three steps by expressing the disjunctive function as a minimum of two extended submodular functions, introducing a variable lifting technique, and constructing the sublinear envelope in the lifted space. The paper also makes several other contributions. First, we provide a disjunctive formulation for the case where each submodular function admits a linear programming formulation. Second, we derive the closed-form sublinear envelope characterization for intersecting submodular functions, yielding new structural insights into a multi-product inventory sales maximization problem. Third, we fully characterize the convex envelope of a bilinear function defined over a cycle graph in the original variable space. Finally, we show computationally that the cycle inequalities close approximately 60\% of the gap for complete and Hadamard graphs, over 30\% of the gap for complete bipartite graphs, and over 80\% of the gap for sparse graphs such as cactus and Halin graphs. The resulting relaxations are also more efficient to solve than previous extended space formulations.
Related
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- All minimum cuts of symmetric submodular functions
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- MiNCE: Nonparametric, Strongly Consistent Confidence Envelopes for Band-Limited Functions and their Smoothed Spectra
- Semi-differentiability of generalised L∞ envelopes with applications to supremal functionals
BibTeX
@misc{wu2026disjunctive,
title = {{Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization}},
author = {Zhongqi Wu and Taotao He and Mohit Tawarmalani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30712},
eprint = {2609.30712},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30712},
}
RIS
TY - UNPB
TI - Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization
AU - Zhongqi Wu
AU - Taotao He
AU - Mohit Tawarmalani
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30712
UR - https://arxiv.org/abs/2609.30712
AB - This paper considers convex envelopes of disjunctive submodular functions---functions that are lattice family submodular over faces of a hypercube---and constructs the first strongly polynomial algorithm for their separation when there are two facial disjunctions. Submodular functions, whose convex envelopes are characterized by the Lovász extension, have occupied a fundamental role in constructing relaxations for combinatorial and nonlinear optimization problems. However, disjunctive submodular function envelopes have not been explored besides the use of ellipsoid algorithm, which remains practically intractable. Our algorithm is derived in three steps by expressing the disjunctive function as a minimum of two extended submodular functions, introducing a variable lifting technique, and constructing the sublinear envelope in the lifted space. The paper also makes several other contributions. First, we provide a disjunctive formulation for the case where each submodular function admits a linear programming formulation. Second, we derive the closed-form sublinear envelope characterization for intersecting submodular functions, yielding new structural insights into a multi-product inventory sales maximization problem. Third, we fully characterize the convex envelope of a bilinear function defined over a cycle graph in the original variable space. Finally, we show computationally that the cycle inequalities close approximately 60\% of the gap for complete and Hadamard graphs, over 30\% of the gap for complete bipartite graphs, and over 80\% of the gap for sparse graphs such as cactus and Halin graphs. The resulting relaxations are also more efficient to solve than previous extended space formulations.
ER -