Optimisation - Useful Links

Last Updated on Saturday, 08 May 2010 12:33

This page contains some pointers to the literature and also links to some relevant web sites.

A bibtex file, containing details of the books and papers, is under construction. (We highly recommend Jabref for viewing/editing such files.)

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, to appear.
• 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 (2010) Lifting for conic mixed-integer programming. Mathematical Programming, to appear.
• 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.
• M. Giandomenico & A.N. Letchford (2006) Exploring the relationship between max-cut and stable set relaxations. Mathematical Programming, 106, 159-175.
• 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 (2009) Integer quadratic quasi-polyhedra. To appear in F. Eisenbrand & B. Shepherd (eds.) Integer Programming and Combinatorial Optimization XIV. Lecture Notes in Computer Science. 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.
• 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

• Joint CMU-IBM site on Mixed-Integer Non-Linear Programming. 
• GAMS page on Mixed-Integer Non-Linear Programming.
• Non-Convex Mixed-Integer Non-Linear Programming project at DFG Research Center Matheon.
• The Semidefinite Programming page of Helmberg.
• The Semidefinite Programming page of Wolkowicz.