A Finitely Convergent Cutting Plane, and a Bender's Decomposition Algorithm for Mixed-Integer Convex and Two-Stage Convex Programs using Cutting Planes

fengqiao luo(fengqiaoluo2014u.northwestern.edu)
Sanjay Mehrotra(mehrotranorthwestern.edu)

Abstract: We consider a general mixed-integer convex program. We first develop an algorithm for solving this problem, and show its nite convergence. We then develop a finitely convergent decomposition algorithm that separates binary variables from integer and continuous variables. The integer and continuous variables are treated as second stage variables. An oracle for generating a parametric cut under a subgradient decomposition assumption is developed. The decomposition algorithm is applied to show that two-stage (distributionally robust) convex programs with binary variables in the first stage can be solved to optimality within a cutting plane framework. For simplicity, the paper assumes that certain convex programs generated in the course of the algorithm are solved to optimality.

Keywords: cutting planes, finite convergence, two-stage mixed-integer convex programming, Bender's decomposition method

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

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 12/08/2021
Entry Accepted: 12/08/2021
Entry Last Modified: 12/08/2021

Modify/Update this entry