Cutting planes for RLT relaxations of mixed 0- polynomial programs

详细信息    查看全文

• 作者：Franklin Djeumou Fomeni ; Konstantinos Kaparis…
• 关键词：Polynomial optimisation ; Cutting planes ; Mixed ; integer nonlinear programming ; Quadratic knapsack problem ; 90C26 ; 90C27
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：151
• 期：2
• 页码：639-658
• 全文大小：473 KB
• 参考文献：1.Adams, W.P., Guignard, M., Hahn, P.M., Hightower, W.L.: A level-2 reformulation–linearization technique bound for the quadratic assignment problem. Eur. J. Oper. Res. 180, 983-96 (2007)View Article MATH MathSciNet
  2.Barahona, F., Jünger, M., Reinelt, G.: Experiments in quadratic 0- programming. Math. Program. 44, 127-37 (1989)View Article MATH
  3.Billionnet, A., Calmels, F.: Linear programming for the 0- quadratic knapsack problem. Eur. J. Oper. Res. 92, 310-25 (1996)View Article MATH
  4.Bonami, P., Minoux, M.: Using rank-1 lift-and-project closures to generate cuts for 0- MIPs, a computational investigation. Discrete Optim. 2, 288-07 (2005)View Article MATH MathSciNet
  5.Caprara, A., Pisinger, D., Toth, P.: Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11, 125-37 (1998)View Article MathSciNet
  6.Christof, T., Loebl, A.: PORTA (polyhedron representation transformation algorithm). Software package, available for download at http://?www.?iwr.?uni-heidelberg.?de/?groups/?comopt/?software
  7.Floudas, C.A.: Deterministic Global Optimization: Theory, Algorithms and Applications. Kluwer, Dordrecht (1999)
  8.Fukuda, K.: cdd (C double description program). Software package, available for download at: http://?www.?cs.?mcgill.?ca/?~fukuda/?soft/?cdd_?home
  9.Gallo, G., Hammer, P.L., Simeone, B.: Quadratic knapsack problems. Math. Program. Stud. 12, 132-49 (1980)View Article MATH MathSciNet
  10.Gr?tschel, M., Lovász, L., Schrijver, A.J.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)View Article MATH
  11.Hahn, P.M., Zhu, Y.-R., Guignard, M., Hightower, W.L., Saltzman, M.J.: A level-3 reformulation–linearization technique-based bound for the quadratic assignment problem. INFORMS J. Comput. 24, 202-09 (2012)View Article MathSciNet
  12.Helmberg, C., Rendl, F.: Solving quadratic (0, 1)-programs by semidefinite programs and cutting planes. Math. Program. 82, 291-15 (1998)MATH MathSciNet
  13.Hunting, M., Faigle, U., Kern, W.: A Lagrangean relaxation approach to the edge-weighted clique problem. Eur. J. Oper. Res. 131, 119-31 (2001)View Article MATH MathSciNet
  14.Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796-17 (2001)View Article MATH MathSciNet
  15.Lovász, L., Schrijver, A.J.: Cones of matrices and set-functions and 0- optimization. SIAM J. Optim. 1, 166-90 (1991)View Article MATH MathSciNet
  16.Padberg, M.W.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139-72 (1989)View Article MATH MathSciNet
  17.Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293-20 (2003)View Article MATH MathSciNet
  18.Pisinger, D.: The quadratic knapsack problem—a survey. Discrete Appl. Math. 155, 623-48 (2007)View Article MATH MathSciNet
  19.Saito, H., Fujie, T., Matsui, T., Matuura, S.: A study of the quadratic semi-assignment polytope. Discrete Optim. 6, 37-0 (2009)View Article MATH MathSciNet
  20.Sherali, H.D., Adams, W.: A hierarchy of relaxations between the continuous and convex hull representations for 0- programming problems. SIAM J. Discrete Math. 3, 411-30 (1990)View Article MATH MathSciNet
  21.Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation–linearization technique. J. Glob. Optim. 2, 101-12 (1992)View Article MATH MathSciNet
  22.Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52, 83-06 (1994)View Article MATH MathSciNet
  23.Sherali, H.D., Lee, Y.: Tighter representations for set partitioning problems. Discrete Appl. Math. 68, 153-67 (1996)View Article MATH MathSciNet
  24.Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1998)
  25.Sherali, H.D.: RLT: A unified approach for discrete and continuous nonconvex optimization. Ann. Oper. Res. 149, 185-93 (2007)View Article MATH MathSciNet
  26.Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Kluwer, Dortrecht (2003)
  27.Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Glob. Optim. 13, 151-70 (1998)View Article MATH MathSciNet
  
• 作者单位：Franklin Djeumou Fomeni (1)
  Konstantinos Kaparis (1)
  Adam N. Letchford (1)
  
  1. Department of Management Science, Lancaster University Management School, Lancaster, LA1 4YX, UK
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

The reformulation–linearization technique, due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0- polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the hierarchy, by optimally weakening linear inequalities that are valid at any given higher level. Computational experiments, conducted on instances of the quadratic knapsack problem, indicate that the cutting planes can close a significant proportion of the integrality gap.