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

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.

Article

Download

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