Optimization Online


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(fengqiaoluo2014***at***u.northwestern.edu)
Sanjay Mehrotra(mehrotra***at***northwestern.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


Download: [PDF]

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

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