Skip to content CVSP — Paper guide | Fabio Furini Skip to content

PAPER GUIDE · MATHEMATICAL PROGRAMMING · 2022

How to optimize concave utility over millions of covering relationships

Double-hypograph decomposition separates the nonlinear utility from the covering structure—and projects out the item variables.

Stefano Coniglio · Fabio Furini · Ivana Ljubić

Selected metaitemsABCovered unionConcave utility
Conceptual illustration of the paper's methodology; drawn for this page, not reproduced from the published article.
THE MAIN CONTRIBUTION

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

01Utility

Exact outer approximation handles the concave function.

02Coverage

Use either submodular cuts or Benders cuts for the set-union operator.

03Projection

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

New exact reformulations

Outer approximation combined with submodular cuts (OA+SC) or Benders cuts (OA+BC).

Provable separation complexity

Under constant-time utility evaluation, OA+BC inequalities are separable in linear time, including at fractional points.

Theory of inequality strength

Formal comparisons of the families, including results on relative strength.

Generalization beyond monotonicity

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.

20,000Items in reported solved instances
60Metaitems
100Scenarios

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.