  


Intersection Cuts for Mixed Integer Conic Quadratic Sets
Kent Andersen(kentimf.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 ) Citation: Download: [PDF] Entry Submitted: 03/05/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  