Optimization Online


Two-stage stochastic 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 p-order conic mixed integer programs (denoted by TSS-CMIPs) in which the second stage problems have p-order conic constraints along with integer variables. First, we present sufficient conditions under which the addition of sparse 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 then consider TSS-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 conic linear (or convex) programming equivalent, under certain conditions, for the second stage CMIPs. We also perform extensive computational experiments by solving randomly generated structured TSS-CMIPs with polyhedral CMIPs and second-order CMIPs in the second stage, and observe that there is a significant reduction in the total time taken to solve these problems after adding our sparse cuts. Finally, we demonstrate the significance of our results for TSS-CMIP in 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, convexification, parametric cuts, conic mixed integer rounding

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: 05/13/2019

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