Generating Uncertainty Sets Using Conformal Prediction for Robust Optimization in Minimum Cost Flow

Zion Johnson, Bruce Cox, Chancellor Johnstone
Proceedings of the Fifteenth Symposium on Conformal and Probabilistic Prediction with Applications, PMLR 329:710-729, 2026.

Abstract

Uncertainty presents a significant challenge in optimization, particularly in problems where unpredictable costs influence decision-making. Robust Optimization (RO) addresses this issue by modeling uncertainty through uncertainty sets, which ensure solutions hold under worst-case scenarios, with the model’s success depending directly on the accuracy of these sets. This research explores the application of conformal prediction to construct uncertainty sets for RO, an area not yet extensively investigated. The study specifically tests split and full conformal prediction within a robust optimization minimum cost flow problem. These methods are compared against traditional techniques, including interval-based and normal-based ellipsoidal uncertainty sets. Experiments were conducted across various network structures and under different error distributions, encompassing normal, skewed, and bimodal cases. The results indicate that conformal prediction uncertainty sets perform comparably to traditional methods, exhibiting slight variations in solution quality and coverage across different scenarios. While the conformal prediction uncertainty sets generally demonstrated tighter cost variability, their median performance did not consistently surpass that of traditional approaches. Notably, the full conformal models exhibited inconsistencies in coverage, a finding that warrants further investigation into the best method for generating an uncertainty set via full conformal prediction. The findings also highlight that network characteristics, particularly structural properties and inherent cost distributions, may influence the effectiveness of these uncertainty sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v329-johnson26a, title = {Generating Uncertainty Sets Using Conformal Prediction for Robust Optimization in Minimum Cost Flow}, author = {Johnson, Zion and Cox, Bruce and Johnstone, Chancellor}, booktitle = {Proceedings of the Fifteenth Symposium on Conformal and Probabilistic Prediction with Applications}, pages = {710--729}, year = {2026}, editor = {Ahlberg, Ernst and Johansson, Ulf and Boström, Henrik and Carlevaro, Alberto and Hallberg Szabadváry, Johan and Carlsson, Lars}, volume = {329}, series = {Proceedings of Machine Learning Research}, month = {02--04 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v329/main/assets/johnson26a/johnson26a.pdf}, url = {https://proceedings.mlr.press/v329/johnson26a.html}, abstract = {Uncertainty presents a significant challenge in optimization, particularly in problems where unpredictable costs influence decision-making. Robust Optimization (RO) addresses this issue by modeling uncertainty through uncertainty sets, which ensure solutions hold under worst-case scenarios, with the model’s success depending directly on the accuracy of these sets. This research explores the application of conformal prediction to construct uncertainty sets for RO, an area not yet extensively investigated. The study specifically tests split and full conformal prediction within a robust optimization minimum cost flow problem. These methods are compared against traditional techniques, including interval-based and normal-based ellipsoidal uncertainty sets. Experiments were conducted across various network structures and under different error distributions, encompassing normal, skewed, and bimodal cases. The results indicate that conformal prediction uncertainty sets perform comparably to traditional methods, exhibiting slight variations in solution quality and coverage across different scenarios. While the conformal prediction uncertainty sets generally demonstrated tighter cost variability, their median performance did not consistently surpass that of traditional approaches. Notably, the full conformal models exhibited inconsistencies in coverage, a finding that warrants further investigation into the best method for generating an uncertainty set via full conformal prediction. The findings also highlight that network characteristics, particularly structural properties and inherent cost distributions, may influence the effectiveness of these uncertainty sets.} }
Endnote
%0 Conference Paper %T Generating Uncertainty Sets Using Conformal Prediction for Robust Optimization in Minimum Cost Flow %A Zion Johnson %A Bruce Cox %A Chancellor Johnstone %B Proceedings of the Fifteenth Symposium on Conformal and Probabilistic Prediction with Applications %C Proceedings of Machine Learning Research %D 2026 %E Ernst Ahlberg %E Ulf Johansson %E Henrik Boström %E Alberto Carlevaro %E Johan Hallberg Szabadváry %E Lars Carlsson %F pmlr-v329-johnson26a %I PMLR %P 710--729 %U https://proceedings.mlr.press/v329/johnson26a.html %V 329 %X Uncertainty presents a significant challenge in optimization, particularly in problems where unpredictable costs influence decision-making. Robust Optimization (RO) addresses this issue by modeling uncertainty through uncertainty sets, which ensure solutions hold under worst-case scenarios, with the model’s success depending directly on the accuracy of these sets. This research explores the application of conformal prediction to construct uncertainty sets for RO, an area not yet extensively investigated. The study specifically tests split and full conformal prediction within a robust optimization minimum cost flow problem. These methods are compared against traditional techniques, including interval-based and normal-based ellipsoidal uncertainty sets. Experiments were conducted across various network structures and under different error distributions, encompassing normal, skewed, and bimodal cases. The results indicate that conformal prediction uncertainty sets perform comparably to traditional methods, exhibiting slight variations in solution quality and coverage across different scenarios. While the conformal prediction uncertainty sets generally demonstrated tighter cost variability, their median performance did not consistently surpass that of traditional approaches. Notably, the full conformal models exhibited inconsistencies in coverage, a finding that warrants further investigation into the best method for generating an uncertainty set via full conformal prediction. The findings also highlight that network characteristics, particularly structural properties and inherent cost distributions, may influence the effectiveness of these uncertainty sets.
APA
Johnson, Z., Cox, B. & Johnstone, C.. (2026). Generating Uncertainty Sets Using Conformal Prediction for Robust Optimization in Minimum Cost Flow. Proceedings of the Fifteenth Symposium on Conformal and Probabilistic Prediction with Applications, in Proceedings of Machine Learning Research 329:710-729 Available from https://proceedings.mlr.press/v329/johnson26a.html.

Related Material