An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support
Abstract
Standard Big-M mixed-integer programming reformulations of chance-constrained programs (CCPs) with finite support often yield weak linear relaxations and scale poorly as the number of scenarios increases. To address this limitation, we derive two families of intersection cuts from problem-specific S-free sets and develop decomposition-based branch-and-cut frameworks. The first one exploits the submodular structure of the scenario requirement function, while the second one uses probability covers. We propose hybrid separation strategies that combine classical mixing inequalities and quantile cuts with the proposed intersection cuts. Computational experiments on integrated production-distribution planning instances show that the proposed hybrid methods reduce computational time compared to pure methods.
Related
- A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
- Efficient ADMM for Soft-Constrained Quadratic Programs via Generalized Slack Projections
- Treewidth and the complexity of box-constrained quadratic programs
- Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs
- Contextual Distributionally Robust Chance-Constrained Programs: Exact Reformulations and Valid Inequalities
BibTeX
@misc{pathy2026intersection,
title = {{An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support}},
author = {Soumya Ranjan Pathy and Hamed Rahimian},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33946},
eprint = {2609.33946},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33946},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support
AU - Soumya Ranjan Pathy
AU - Hamed Rahimian
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33946
UR - https://arxiv.org/abs/2609.33946
AB - Standard Big-M mixed-integer programming reformulations of chance-constrained programs (CCPs) with finite support often yield weak linear relaxations and scale poorly as the number of scenarios increases. To address this limitation, we derive two families of intersection cuts from problem-specific S-free sets and develop decomposition-based branch-and-cut frameworks. The first one exploits the submodular structure of the scenario requirement function, while the second one uses probability covers. We propose hybrid separation strategies that combine classical mixing inequalities and quantile cuts with the proposed intersection cuts. Computational experiments on integrated production-distribution planning instances show that the proposed hybrid methods reduce computational time compared to pure methods.
ER -