Abstract
A conic integer program is an integer programming problem with conic constraints. Conic integer programming has important applications in finance, engineering, statistical learning, and probabilistic integer programming.
Here we study mixed-integer sets defined by second-order conic constraints. We describe general-purpose conic mixed-integer rounding cuts based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve continuous conic programming relaxations at the nodes of the search tree. Our preliminary computational experiments with the new cuts show that they are quite effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alizadeh, F.: Interior point methods in semidefinite programming and applications to combinatorial optimization. SIAM Journal on Optimization 5, 13–51 (1995)
Alizadeh, F., Goldfarb, D.: Second-order cone programming. Mathematical Programming 95, 3–51 (2003)
Atamtürk, A.: Sequence independent lifting for mixed–integer programming. Operations Research 52, 487–490 (2004)
Balas, E.: Disjunctive programming. Annals of Discrete Mathematics 5, 3–51 (1979)
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58, 295–324 (1993)
Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, Philadelphia (2001)
Benson, S.J., Ye, Y.: DSDP5: Software for semidefinite programming. Technical Report ANL/MCS-P1289-0905, Mathematics and Computer Science Division, Argonne National Laboratory (September 2005)
Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An algorithmic framework for convex mixed integer nonlinear programs. Technical Report RC23771, IBM (November 2005)
Borchers, B.: CDSP, a C library for semidefinite programing. Optimization Methods and Software 11, 613–623 (1999)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Çezik, M.T., Iyengar, G.: Cuts for mixed 0-1 conic programming. Mathematical Programming 104, 179–202 (2005)
Goemans, M.X.: Semidefinite programming in combinatorial optimization. Mathematical Programming 79, 143–161 (1997)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfyibility problems using semidefinite programming. Journal of the ACM 42, 1115–1145 (1995)
Kim, S., Kojima, M., Yamashita, M.: Second order cone programming relaxation of a positive semidefinite constraint. Optimization Methods and Software 18, 535–541 (2003)
Kojima, M., Tuncel, L.: Cones of matrices and successive convex relaxations of nonconvex sets. SIAM Journal on Optimization 10, 750–778 (2000)
Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 293–303. Springer, Heidelberg (2001)
Linderoth, J.: A simplical branch-and-bound algorithm for solving quadratically constrained quadratic programs. Mathematical Programming 103, 251–282 (2005)
Lobo, M., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra and its Applications 284, 193–228 (1998)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1, 166–190 (1991)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley and Sons, New York (1988)
Nemhauser, G.L., Wolsey, L.A.: A recursive procedure for generating all cuts for 0-1 mixed integer programs. Mathematical Programming 46, 379–390 (1990)
Nesterov, Y., Nemirovski, A.: A general approach to polynomial-time algorithm design for convex programming. Technical report, Center. Econ. & Math. Inst, USSR Acad. Sci., Moskow, USSR (1988)
Nesterov, Y., Nemirovski, A.: Self-concordant functions and polynomial time methods in convex programming. Technical report, Center. Econ. & Math. Inst, USSR Acad. Sci., Moskow, USSR (1990)
Nesterov, Y., Nemirovski, A.: Conic formulation of a convex programming problem and duality. Technical report, Center. Econ. & Math. Inst, USSR Acad. Sci., Moskow, USSR (1991)
Nesterov, Y., Nemirovski, A.: Interior-point polynomial algorithms for convex programming. SIAM, Philadelphia (1993)
Sherali, H.D., Shetti, C.: Optimization with disjunctive constraints. Lectures on Econ. Math. Systems, vol. 181. Springer, Heidelberg (1980)
Sherali, H.D., Tunçbilek, C.H.: A hierarchy of relaxations between continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3, 411–430 (1990)
Sherali, H.D., Tunçbilek, C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. Journal of Global Optimization 7, 1–31 (1995)
Stubbs, R., Mehrotra, S.: A branch-and-cut methods for 0-1 mixed convex programming. Mathematical Programming 86, 515–532 (1999)
Sturm, J.: Using SeDuMi 1.02, a MATLAB toolbox for ptimization over symmetric cones. Optimization Methods and Software 11, 625–653 (1999)
Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming 99, 563–591 (2004)
Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3 – a Matlab software package for semidefinite programming. Optimization Methods and Software 11/12, 545–581 (1999)
Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0). Optimization Methods and Software 18, 491–505 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Atamtürk, A., Narayanan, V. (2007). Cuts for Conic Mixed-Integer Programming. In: Fischetti, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2007. Lecture Notes in Computer Science, vol 4513. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72792-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-72792-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72791-0
Online ISBN: 978-3-540-72792-7
eBook Packages: Computer ScienceComputer Science (R0)