Optimization Online


Two-stage stochastic and distributionally robust p-order conic mixed integer programs

Manish Bansal (bansal***at***vt.edu)
Yingqiu Zhang ( yqzhang7***at***vt.edu)

Abstract: In this paper, we introduce two-stage stochastic and distributionally robust p-order conic mixed integer programs (denoted by TSS-CMIPs and TSDR-CMIPs, respectively) in which the second stage problems have p-order conic constraints along with integer variables. First, we consider TSS-CMIPs and TSDR-CMIPs with structured p-order CMIPs in the second stage and derive classes of globally valid parametric (non)-linear cuts for them. These cuts provide convex programming equivalent, under certain conditions, for the second stage CMIPs. We then present conditions under which the addition of sparse nonlinear cuts in the extensive formulation of TSSCMIPs is sucient to relax the integrality restrictions on the second stage integer variables without e ecting the integrality of the optimal solution of the TSS-CMIP. Our aforementioned cuts for TSSCMIPs with p = 1 satisfy these conditions. We also perform extensive computational experiments by solving randomly generated structured TSS-CMIPs with polyhedral CMIPs and second-order CMIPs in the second stage, i.e. p = 1 and p = 2, respectively, and observe that there is a signi cant reduction in the total time taken to solve these problems after adding our sparse cuts. Finally, we demonstrate the signi cance of our results for TSS-CMIP by deriving (partial) convex hull for deterministic multi-constraint conic mixed integer sets with multiple integer variables. This study extends the result of Atamturk and Narayanan [Math. Prog. 122: 1-20, 2008] for a simple polyhedral conic mixed integer set with single constraint and one integer variable.

Keywords: two-stage stochastic p-order conic mixed integer program; sparse cutting planes; convexi cation; distributionally robust; parametric cuts

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 05/19/2018
Entry Accepted: 05/20/2018
Entry Last Modified: 12/13/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society