Compact Optimality Verification for Optimization Proxies

Wenbo Chen, Haoruo Zhao, Mathieu Tanneau, Pascal Van Hentenryck
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:7847-7863, 2024.

Abstract

Recent years have witnessed increasing interest in optimization proxies, i.e., machine learning models that approximate the input-output mapping of parametric optimization problems and return near-optimal feasible solutions. Following recent work by (Nellikkath & Chatzivasileiadis, 2021), this paper reconsiders the optimality verification problem for optimization proxies, i.e., the determination of the worst-case optimality gap over the instance distribution. The paper proposes a compact formulation for optimality verification and a gradient-based primal heuristic that brings significant computational benefits to the original formulation. The compact formulation is also more general and applies to non-convex optimization problems. The benefits of the compact formulation are demonstrated on large-scale DC Optimal Power Flow and knapsack problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-chen24bj, title = {Compact Optimality Verification for Optimization Proxies}, author = {Chen, Wenbo and Zhao, Haoruo and Tanneau, Mathieu and Van Hentenryck, Pascal}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {7847--7863}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/chen24bj/chen24bj.pdf}, url = {https://proceedings.mlr.press/v235/chen24bj.html}, abstract = {Recent years have witnessed increasing interest in optimization proxies, i.e., machine learning models that approximate the input-output mapping of parametric optimization problems and return near-optimal feasible solutions. Following recent work by (Nellikkath & Chatzivasileiadis, 2021), this paper reconsiders the optimality verification problem for optimization proxies, i.e., the determination of the worst-case optimality gap over the instance distribution. The paper proposes a compact formulation for optimality verification and a gradient-based primal heuristic that brings significant computational benefits to the original formulation. The compact formulation is also more general and applies to non-convex optimization problems. The benefits of the compact formulation are demonstrated on large-scale DC Optimal Power Flow and knapsack problems.} }
Endnote
%0 Conference Paper %T Compact Optimality Verification for Optimization Proxies %A Wenbo Chen %A Haoruo Zhao %A Mathieu Tanneau %A Pascal Van Hentenryck %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-chen24bj %I PMLR %P 7847--7863 %U https://proceedings.mlr.press/v235/chen24bj.html %V 235 %X Recent years have witnessed increasing interest in optimization proxies, i.e., machine learning models that approximate the input-output mapping of parametric optimization problems and return near-optimal feasible solutions. Following recent work by (Nellikkath & Chatzivasileiadis, 2021), this paper reconsiders the optimality verification problem for optimization proxies, i.e., the determination of the worst-case optimality gap over the instance distribution. The paper proposes a compact formulation for optimality verification and a gradient-based primal heuristic that brings significant computational benefits to the original formulation. The compact formulation is also more general and applies to non-convex optimization problems. The benefits of the compact formulation are demonstrated on large-scale DC Optimal Power Flow and knapsack problems.
APA
Chen, W., Zhao, H., Tanneau, M. & Van Hentenryck, P.. (2024). Compact Optimality Verification for Optimization Proxies. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:7847-7863 Available from https://proceedings.mlr.press/v235/chen24bj.html.

Related Material