Lower bounds for minimization problems are essential for convergence of both branching-based and iterative solution methods for optimization problems. They also serve an important role in evaluating the quality of feasible solutions by providing conservative optimality gaps. We derive a closed-form analytical lower bound for a class of quadratic optimization problems with binary decision variables. Unlike traditional lower bounds obtained by solving relaxed models, our bound is purely analytical and does not require numerically solving any optimization problem. This is particularly valuable for problem instances that are too large to even formulate or load into a solver due to memory limitations. Further, we propose a greedy heuristic for obtaining feasible solutions. Together, the analytical bound and heuristic provide a provable optimality gap without solving any optimization model. Numerical experiments demonstrate that we can solve real-world large-scale instances, that were previously unsolvable due to memory limitations, in under a minute with provable optimality gaps of under 7%. For smaller instances where the optimal solution is computable, our greedy solutions are about 1% away from the optimal. These results highlight the practical value and scalability of our approach when direct solution methods are computationally prohibitive.

A recent work proposes a new quadratic facility location model to address ecological challenges faced by policymakers in Bavaria, Germany. Building on this, we significantly extend our understanding of this new problem. We develop connections to traditional combinatorial optimization models and show that the problem is [Formula: see text] hard. We then develop several classes of easy-to-implement heuristics to solve this problem. These are rooted in solving special cases of the generalized quadratic assignment problem as a subproblem; this subproblem is also [Formula: see text] hard. On moderate-sized instances from Bavaria—that were previously intractable—our proposed heuristics compute feasible solutions that are 0.5% (on average) improved over the generic solution method in just over a minute (on average), even when the generic solver runs for 20,000 seconds. Larger instances show an improvement of 5% (on average) compared with the generic solution method in an average of 410 seconds. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: B. Singh was partially supported by the University of Southampton [Research Investment and Support Building Sustainable and Green Futures Program]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0693 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0693 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Typically, within facility location problems, fairness is defined in terms of accessibility of users. However, for facilities perceived as undesirable by communities hosting them, fairness between the usage of facilities becomes especially important. Limited research exists on this notion of fairness. To close this gap, we develop a series of optimization models for the allocation of populations of users to facilities such that access for users is balanced with a fair utilization of facilities. The optimality conditions of the underlying nonconvex quadratic models state the precise balance between accessibility and fairness. We define new classes of fairness and a metric to quantify the extent to which fairness is achieved in both optimal and suboptimal allocations. We show that a continuous relaxation of our central model is sufficient to achieve a perfect extent of fairness, while a special case reduces to the classical notion of proportional fairness. Our work is motivated by pervasive ecological challenges faced by the waste management community as policymakers seek to reduce the number of recycling centers in the last few years. As a computational case study, applying our models on data for the state of Bavaria in Germany, we find that even after the closure of a moderate number of recycling centers, large degrees of access can be ensured, provided that the closures are conducted optimally. Fairness, however, is impacted more, with facilities in rural regions shouldering larger loads of visiting populations than those in urban regions. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Computer resources and support provided by the Erlangen Regional Computing Center are gratefully acknowledged. B. Singh was partially financially supported by the Bavarian State Ministry for Science and Art (Bayerisches Staatsministerium für Wissenschaft und Kunst) under the Competence Network for Scientific High Performance Computing in Bavaria. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0308 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0308 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract Recycling centers sort and process collected waste in the interest of the environment, but also lead to damaging climate effects via released emissions and pollutants in their operation. Consequently, governments are closing such centers to fulfill climate and carbon neutrality goals. However, such closures risk populations being forced to travel further to facilities that collect waste, and can cause an unfair burden on the remaining open centers, thereby reducing participation in recycling. Using a facility location optimization model and mobility survey data within the state of Bavaria in Germany, we show how selective closures of these centers can still lead to high levels of recycling access. Our analysis ensures that even when 20% of facilities are closed smartly, the median travel distance by residents to their assigned recycling center increases by only 450 m. Additionally, we find Bavaria suffers from disparity in recycling patterns in rural and urban regions, both in terms of motivation to recycle and the locations of the facilities. We promote a policy that favors retention of recycling centers in rural regions by reserving 75% of open facilities to be in rural areas, while selectively closing facilities in urban regions, to remove these regional differences. Success of recycling campaigns depends on public perception of closures of such facilities and also on their ease of access. As policymakers gradually implement further closures, such data‐driven strategies can assist in being more transparent to the public thereby increasing the willingness to participate in such recycling programs.

Abstract We develop a stochastic optimization model for scheduling a hybrid solar-battery storage system. Solar power in excess of the promise can be used to charge the battery, while power short of the promise is met by discharging the battery. We ensure reliable operations by using a joint chance constraint. Models with a few hundred scenarios are relatively tractable; for larger models, we demonstrate how a Lagrangian relaxation scheme provides improved results. To further accelerate the Lagrangian scheme, we embed the progressive hedging algorithm within the subgradient iterations of the Lagrangian relaxation. We investigate several enhancements of the progressive hedging algorithm, and find bundling of scenarios results in the best bounds. Finally, we provide a generalization for how our analysis extends to a microgrid with multiple batteries and photovoltaic generators.

Abstract We introduce the two‐stage stochastic minimum s − t cut problem. Based on a classical linear 0‐1 programming model for the deterministic minimum s − t cut problem, we provide a mathematical programming formulation for the proposed stochastic extension. We show that its constraint matrix loses the total unimodularity property, however, preserves it if the considered graph is a tree. This fact turns out to be not surprising as we prove that the considered problem is ‐hard in general, but admits a linear time solution algorithm when the graph is a tree. We exploit the special structure of the problem and propose a tailored Benders decomposition algorithm. We evaluate the computational efficiency of this algorithm by solving the Benders dual subproblems as max‐flow problems. For many tested instances, we outperform a standard Benders decomposition by two orders of magnitude with the Benders decomposition exploiting the max‐flow structure of the subproblems.