Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Cuts for mixed 0-1 conic programming

M.T. ÇezikContact Information and G. IyengarContact Information

(1) GERAD and Départment d’Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, H3C 3J7, Canada
(2) IEOR Department, Columbia University New York, New York, 10027, USA

Received: 20 August 2001  Accepted: 20 January 2005  Published online: 28 April 2005

Abstract  In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.
Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.

Contact InformationM.T. Çezik
Email: ceziktol@iro.umontreal.ca

Contact InformationG. Iyengar
Email: garud@ieor.columbia.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this article
Export this article as RIS | Text
 
Referenced by
2 newer articles

  1. Atamtürk, Alper (2010) Conic mixed-integer rounding cuts. Mathematical Programming 122(1)
    [CrossRef]
  2. Atamtürk, Alper (2009) Lifting for conic mixed-integer programming. Mathematical Programming
    [CrossRef]
Remote Address: 38.107.191.114 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)