We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from modularity, we derive analytical bounds on the total curvature of $F(S)$ and, under mild assumptions, show that it lies between zero and one. Next, we identify structural regimes—based on continuous relaxations of the feasible region and parameter values—where our inherently combinatorial problem reduces to a simple convex quadratic problem admitting a closed-form optimal solution. Further, this relaxed formulation not only exhibits remarkable connections to notions of proportional fairness but also restores the supermodularity of $F(S)$. Our results reconcile empirically observed nestedness with theoretical non-modularity, contributing new structural insight into this class of combinatorial quadratic optimization models.
Citation
in peer review (2025)