Optimization Online


Intersection Cuts for Mixed Integer Conic Quadratic Sets

Kent Andersen(kent***at***imf.au.dk)
Anders Jensen(jensen***at***imf.au.dk)

Abstract: Balas introduced intersection cuts for mixed integer linear sets. Intersection cuts are given by closed form formulas and form an important class of cuts for solving mixed integer linear programs. In this paper we introduce an extension of intersection cuts to mixed integer conic quadratic sets. We identify the formula for the conic quadratic intersection cut by formulating a system of polynomial equations with additional variables that are satisfied by points on a certain piece of the boundary defined by the intersection cut. Using a software package from algebraic geometry we then eliminate variables from the system and get a formula for the intersection cut in dimension three. This formula is finally generalized and proved for any dimension. The intersection cut we present generalizes a conic quadratic cut introduced by Modaresi, Kilinc and Vielma.

Keywords: Intersection cut, Mixed Integer Conic Quadratic Optimization, Computational Algebraic Geometry

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


Download: [PDF]

Entry Submitted: 03/05/2013
Entry Accepted: 03/05/2013
Entry Last Modified: 03/05/2013

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