![[2503.04071] Tightening Optimality gap with confidence through conformal prediction](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2503.04071] Tightening Optimality gap with confidence through conformal prediction
Summary
This article presents a novel conformal prediction framework aimed at tightening optimality gaps in constrained optimization, enhancing solution quality assessments for complex systems.
Why It Matters
In fields like supply chain management and power grid operations, accurately assessing solution optimality is crucial for effective decision-making. This research provides a method to improve the reliability of optimization results, potentially leading to better operational outcomes and resource management.
Key Takeaways
- Introduces a conformal prediction framework to tighten primal and dual bounds in optimization.
- Addresses heteroskedasticity in solution bounds through selective inference.
- Demonstrates that the new method offers more efficient coverage levels in numerical experiments.
- Enhances the practical applicability of optimization solutions in complex systems.
- Provides a pathway for future research in improving optimization techniques.
Statistics > Machine Learning arXiv:2503.04071 (stat) [Submitted on 6 Mar 2025 (v1), last revised 24 Feb 2026 (this version, v4)] Title:Tightening Optimality gap with confidence through conformal prediction Authors:Miao Li, Michael Klamkin, Russell Bent, Pascal Van Hentenryck View a PDF of the paper titled Tightening Optimality gap with confidence through conformal prediction, by Miao Li and 3 other authors View PDF HTML (experimental) Abstract:Decision makers routinely use constrained optimization technology to plan and operate complex systems like global supply chains or power grids. In this context, practitioners must assess how close a computed solution is to optimality in order to make operational decisions, such as whether the current solution is sufficient or whether additional computation is warranted. A common practice is to evaluate solution quality using dual bounds returned by optimization solvers. While these dual bounds come with certified guarantees, they are often too loose to be practically informative. To this end, this paper introduces a novel conformal prediction framework for tightening loose primal and dual bounds. The proposed method addresses the heteroskedasticity commonly observed in these bounds via selective inference, and further exploits their inherent certified validity to produce tighter, more informative prediction intervals. Finally, numerical experiments on large-scale industrial problems suggest that the proposed approach can provide the...