Exploit two independent structures—the concavity of the utility function and the set-union covering operator—to obtain an exact MILP reformulation without explicit variables for every covered item.
01 / THE PROBLEM
Which facilities should we select when coverage has diminishing returns?
Choose a subset of metaitems (for example, facilities) under a cardinality constraint. Selecting metaitems covers a union of items (for example, customers); the objective is the expected value of a concave utility of the covered items' scenario-dependent values.
The difficulty is both combinatorial (which items are covered by a set union?) and nonlinear (how to represent the concave objective exactly?). The formulation can involve vastly more items than metaitems.
02 / THE INSIGHT
Two hypographs, two sources of structure
Exact outer approximation handles the concave function.
Use either submodular cuts or Benders cuts for the set-union operator.
Remove the large family of item-associated variables from the resulting model.
The paper calls this a double-hypograph decomposition. Its principal benefit is the ability to model problems where the number of covered items is several orders of magnitude larger than the number of selectable metaitems.
03 / THE CONTRIBUTIONS
More than a new reformulation
Outer approximation combined with submodular cuts (OA+SC) or Benders cuts (OA+BC).
Under constant-time utility evaluation, OA+BC inequalities are separable in linear time, including at fractional points.
Formal comparisons of the families, including results on relative strength.
An extension for concave differentiable utility functions that need not be increasing.
See Sections 3–5 and the appendix for the derivations, proofs and counterexamples.
04 / COMPUTATIONAL RESULTS
Large item sets become manageable
The computational experiments compare branch-and-cut approaches based on the different reformulations, as well as classical and global-optimization alternatives. The approach combining outer approximation with Benders cuts is reported as the strongest in the experimental comparison.
These are instance dimensions explicitly stated in Section 1.4 of the original paper; they are not claimed as a universal performance guarantee. Detailed comparisons and performance profiles appear in Section 6 and Appendix G.
05 / WHY READ THE PAPER?
A decomposition blueprint for nonlinear covering models
The central lesson is that the structure of a nonlinear objective and the structure of a combinatorial mapping need not be treated together. Separating the two can lead to compact, strong, and exactly solvable formulations.
Explore the mathematical details ↗Browse the implementation ↗Selected citing literature reviewed on 9 October 2026. The items below are editorial selections, not citation-based rankings.
06 / SUBSEQUENT RESEARCH
How this work has been used or discussed
Selected citing research, with an explanation of the documented relationship to this paper.
Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints ↗
The authors discuss Coniglio, Furini and Ljubić (2022) as related work on scenario-based concave utility maximization with a covering relationship between items and metaitems. This is a conceptual connection in the literature review, not evidence that their algorithm implements the earlier decomposition.
A selective set of verified examples, not a complete Google Scholar citing-articles list. Where the later work only discusses the original paper, this is explicitly distinguished from adopting its method.
INFORMS Journal on Computing (2024)
A Model-Free Approach for Solving Choice-Based Competitive Facility Location Problems Using Simulation and Submodularity ↗
Uses the relationship between submodular covering cuts and Benders cuts established in Coniglio–Furini–Ljubić to derive and strengthen a partial Benders reformulation for random-utility facility location.
INFORMS Journal on Computing (2026)
A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems ↗
Develops combinatorial Benders cuts for backup covering; the article places the earlier concave-utility/submodular model among related large-scale covering developments. The relationship is contextual rather than direct algorithm reuse.
Computers & Operations Research (2024)
Accelerated Benders Decomposition and Local Branching for Dynamic Maximum Covering Location Problems ↗
Studies a multi-period covering model and develops an accelerated Benders and local-branching approach. It explicitly cites Coniglio–Furini–Ljubić's outer-approximation, submodular-cut and Benders treatment of the set-union model as related methodology.
INFORMS Journal on Optimization (2026)
Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems ↗
Studies exact mixed-integer formulations and strong submodular inequalities for robust objective functions. Cites the earlier concave-utility work in the surrounding submodular modelling literature; this is a thematic and theoretical connection, not a claim that its algorithm directly implements the OA+BC decomposition.