callback request

Search the site

Find out More

Bibliography and Software

This page contains a bibliography, a list of relevant software packages, and links to some relevant web sites.

Books

  • C.A. Floudas (1995) Nonlinear and Mixed-Integer Optimization. Oxford University Press.
  • L.A. Wolsey (1998) Integer Programming. Wiley.
  • H.D. Sherali & W.P. Adams (1998) A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Springer.
  • M. Tawarmalani & N.V. Sahinidis (2003) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Springer.
  • S. Boyd & L. Vandenberghe (2004) Convex Optimization. Cambridge University Press.
  • I. Novak (2005) Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Springer.
  • D. Li & X. Sun (2006) Nonlinear Integer Programming. Springer.
  • G. Cornuejols & R. Tutuncu (2007) Optimization Methods in Finance.  Cambridge University Press.

Papers

  • K. Abhishek, S. Leyffer & J. Linderoth (2010) FilMINT: an outer approximation-based solver for convex mixed-integer nonlinear programs. INFORMS Journal of Computing, 22, 555-567.
  • M.S. Akturk, A. Atamturk & S. Gurel (2009) A strong conic quadratic reformulation for machine-job assignment with controllable process times. Operations Research Letters, 37, 187-191.
  • A. Atamturk & V. Narayanan (2009) The submodular knapsack polytope. Discrete Optimization, 6, 333-344.
  • A. Atamturk & V. Narayanan (2010) Conic mixed-integer rounding cuts. Mathematical Programming, 122, 1-20.
  • A. Atamturk & V. Narayanan (2011) Lifting for conic mixed-integer programming. Mathematical Programming, 126, 351-363.
  • P. Belotti et al. (2009) Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods and Software, 24, 597-634.
  • P. Bonami et al. (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization, 5, 186-204.
  • P. Bonami et al. (2009) A feasibility pump for mixed-integer non-linear programs. Mathematical Programming, 119, 331-352.
  • P. Bonami, M. Kilinc & J. Linderoth (2009) Algorithms and software for convex mixed integer nonlinear programs. Working paper.
  • S. Burer (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming, 120, 479-495.
  • S. Burer & A.N. Letchford (2009) On non-convex quadratic programming with box constraints. SIAM Journal on Optimization, 20, 1073-1089.
  • M.T. Cezik & G. Iyengar (2005) Cuts for mixed 0-1 conic programming. Mathematical Programming, 104, 179-202.
  • J.A. De Loera, R. Hemmecke, M. Köppe & R. Weismantel (2006) Integer polynomial optimization in fixed dimension. Mathematics of Operations Research, 31, 147-153.
  • R. Fletcher & S. Leyffer (1994) Solving mixed integer nonlinear programs by outer approximation. Mathematical Programming, 66, 327-349.
  • C.A. Floudas & C.E. Gounaris (2009) A review of recent advances in global optimization. Journal of Global Optimization, 45, 3-38.  
  • A. Frangioni & C. Gentile (2006) Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming, 106, 225-236.
  • A. Frangioni & C. Gentile (2009) A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes. Operations Research Letters, 37, 206-210.
  • L. Galli & A.N. Letchford (2010) Small bipartite subgraph polytopes. Operations Research Letters, 38, 337-340.
  • L. Galli, K. Kaparis & A.N. Letchford (2011) Gap inequalities for non-convex mixed-integer quadratic programs. Operations Research Letters, 39, 297-300.
  • L. Galli, K. Kaparis & A.N. Letchford (2011) Complexity results for the gap inequalities for the max-cut problem. Operations Research Letters, to appear.
  • M. Giandomenico & A.N. Letchford (2006) Exploring the relationship between max-cut and stable set relaxations. Mathematical Programming, 106, 159-175.
  • M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2009) An application of the Lovász-Schrijver M(K,K) operator to the stable set problem. Mathematical Programming, 120, 381-401.
  • M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2011) A new approach to the stable set problem based on ellipsoids. In O. Günlük & G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization XV. Lecture Notes in Computer Science, vol. 6655. Heidelberg: Springer.
  • M.X. Goemans (1997) Semidefinite programming in combinatorial optimization. Mathematical Programming, 79, 143-161.
  • M.X. Goemans & D.P. Williamson (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the Association for Computing Machinery, 42, 1115-1145.
  • I.E. Grossmann (2002) Review of nonlinear mixed-integer and disjunctive techniques.  Optimization and Engineering, 3, 227-252.
  • I.E. Grossman & Z. Krovanja (1995) Mixed-integer nonlinear programming techniques for process system engineering.  Computers & Chemical Engineering, 19 (supplement), 189-204.
  • J. Judice et al. (2006) A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. Journal of Global Optimization, 36, 89-114.
  • L. Khatchiyan & L. Porkolab (2000) Integer optimization on convex semialgebraic sets. Discrete and Computational Geometry, 23, 207-224.
  • M. Laurent & F. Rendl (2005) Semidefinite programming and integer programming. In K. Aardal, G. Nemhauser & R. Weismantel (eds.) Handbook on Discrete Optimization. Elsevier.
  • J. Lee (2007) Mixed-integer nonlinear programming: some modelling and solution issues.  IBM Journal of Research and Development, 51.
  • A.N. Letchford (2010) Integer quadratic quasi-polyhedra. In F. Eisenbrand & B. Shepherd (eds.) Integer Programming and Combinatorial Optimization XIV. Lecture Notes in Computer Science, vol. 6080. Berlin: Springer.
  • A.N. Letchford & M.M. Sřrensen (2009) Binary positive semidefinite matrices and associated integer polytopes. Mathematical Programming, to appear (extended abstract in proceedings of IPCO 2008).
  • L. Lovász (2003) Semidefinite programs and combinatorial optimization. In B.A. Reed & C.L. Linhares-Sales (eds.) Recent Advances in Algorithms and Combinatorics. New York: Springer.
  • L. Lovász & A. Schrijver (1991) Cones of matrices and set functions and 0-1 optimization.  SIAM Journal on Optimization, 1, 166-190.
  • D. Michaels & R. Weismantel (2006) Polyhedra related to integer convex polynomial systems, Mathematical Programming 105, 215-232.
  • F. Rendl (1999) Semidefinite programming and combinatorial optimization. Applied Numerical Mathematics, 29, 255-281. 
  • J.P. Richard & M. Tawarmalani (2010) Lifting inequalities: a framework for generating strong cuts for non-linear programs. Mathematical Programming, 121, 61-104.
  • A. Saxena, P. Bonami & J. Lee (2010) Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations. Mathematical Programming, 124, 383-411.
  • A. Saxena, P. Bonami & J. Lee (2011) Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. Mathematical Programming, 130. 359-413.
  • M. Skutella (2001) Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the Association for Computing Machinery, 48, 206-242. 
  • R.A. Stubbs & S. Mehrotra (1999) A branch-and-cut method for 0-1 mixed convex programming.  Mathematical Programming, 86, 515-532.
  • M. Tawarmalani & N.V. Sahinidis (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study.  Mathematical Programming, 99, 563-591.
  • M. Tawarmalani & N.V. Sahinidis (2005) A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103, 225-249.
  • J.P. Vielma, S. Ahmed & G.L. Nemhauser (2008) A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS Journal on Computing, 20, 438-450.    

Software

  • ALPHA-ECP is an exact solver for Mixed-Integer Non-Linear Programs with 'pseudo-convex' objective and constraint functions.  The underlying algorithm is the 'extended cutting plane' method.
  • BARON is a software package for general Mixed-Integer Non-Linear Programs.  Several exact algorithms are available, all based on the 'branch-and-reduce' paradigm.  See also the BARON manual.
  • BONMIN is a software package for general Mixed-Integer Non-Linear Programs.  Several algorithms are available.  They are exact when the problem is convex, and heuristic otherwise.
  • COUENNE is an exact solver for general Mixed-Integer Non-Linear Programs.  The underlying algorithm is branch-and-reduce.
  • CPLEX now has an exact solver for convex Mixed-Integer Quadratically-Constrained Programs.  The method used appears to be branch-and-bound with convex quadratic relaxations.
  • DICOPT is a solver for general Mixed-Integer Non-Linear Programs.  The underlying algorithm is 'outer approximation'.  It is exact when the problem is convex, and heuristic otherwise. 
  • FilMINT is an exact solver for convex Mixed-Integer Non-Linear Programs. The underlying algorithm is 'LP/NLP based branch-and-bound'.
  • LaGO is a solver for general Mixed-Integer Non-Linear Programs, based on Lagrangian Decomposition and Branch-and-Bound.  The algorithm is exact when the problem is convex, and heuristic otherwise.
  • LINDO API now has an exact solver for convex Mixed-Integer Quadratic Programs.  The method used appears to be branch-and-bound with quadratic programming relaxations.
  • MINLPBB is an exact solver for convex Mixed-Integer Non-Linear Programs.  The underlying algorithm appears to be branch-and-bound with convex programming relaxations.
  • MINOPT is a software package for convex Mixed-Integer Non-Linear Programs.  Several exact algorithms are available. 
  • MOSEK now has an exact solver for Mixed-Integer Second-Order Conic Programs.  The method used appears to be branch-and-bound with conic relaxations.
  • SCIP can now solve Mixed-Integer Quadratically-Constrained Programs.  It is not yet clear whether the problem must be convex, or what kind of solution method is used.

Note: BONMIN, COUENNE, LaGO and SCIP are free.

Miscellaneous