Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs

Manish Bansal () and Yingqiu Zhang ()
Additional contact information
Manish Bansal: Virginia Tech
Yingqiu Zhang: Virginia Tech

Journal of Global Optimization, 2021, vol. 81, issue 2, No 6, 433 pages

Abstract: Abstract In this paper, we derive (partial) convex hull for deterministic multi-constraint polyhedral conic mixed integer sets with multiple integer variables using conic mixed integer rounding (CMIR) cut-generation procedure of Atamtürk and Narayanan (Math Prog 122:1–20, 2008), thereby extending their result for a simple polyhedral conic mixed integer set with single constraint and one integer variable. We then introduce two-stage stochastic p-order conic mixed integer programs (denoted by TSS-CMIPs) in which the second stage problems have sum of $$l_p$$ l p -norms in the objective function along with integer variables. First, we present sufficient conditions under which the addition of scenario-based nonlinear cuts in the extensive formulation of TSS-CMIPs is sufficient to relax the integrality restrictions on the second stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We utilize scenario-based CMIR cuts for TSS-CMIPs and their distributionally robust generalizations with structured CMIPs in the second stage, and prove that these cuts provide conic/linear programming equivalent or approximation for the second stage CMIPs. We also perform extensive computational experiments by solving stochastic and distributionally robust capacitated facility location problem and randomly generated structured TSS-CMIPs with polyhedral CMIPs and second-order CMIPs in the second stage, i.e. $$p=1$$ p = 1 and $$p =2$$ p = 2 , respectively. We observe that there is a significant reduction in the total time taken to solve these problems after adding the scenario-based cuts.

Keywords: Two-stage stochastic p-order conic mixed integer program; Scenario-based cutting planes; Two-stage distributionally robust program; (Partial) convex hull; Conic mixed integer rounding; Multi-module capacitated facility location (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00986-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:2:d:10.1007_s10898-020-00986-w

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00986-w

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().