Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1

 Access to full text

 Full (PDF)

1. [1] W.P. Adams et H.D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problem. Manage. Sci. 32 (1986) 1274-1289. Zbl0623.90054MR861711
2. [2] A. Billionnet et F. Calmels, Linear programming for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. 92 (1996) 310-325. Zbl0912.90221
3. [3] A. Billionnet, A. Faye et E. Soutif, A new upper bound for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. 112 (1999) 664-672. Zbl0933.90049
4. [4] P. Chaillou, P. Hansen et Y. Mahieu, Best network flow bounds for the quadratic knapsack problem. Lect. Notes Math. 1403 (1986) 226-235. Zbl0678.90061
5. [5] S. Elloumi, A. Faye et E. Soutif, Decomposition and linearization for 0-1 quadratic programming. Ann. Oper. Res. 99 (2000) 79-93. Zbl0990.90073MR1837733
6. [6] L.F. Escudero, A. Garin et G. Pérez, An O(nlogn) procedure for identifying facets of the knapsack polytope. Oper. Res. Lett. 31 (2003) 211-218. Zbl1042.90035MR1967292
7. [7] C. Helmberg, F. Rendl et R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim. 4 (2000) 197-215. Zbl0970.90075MR1772826
8. [8] E.J. Johnson, A. Mehrotra et G.L. Nemhauser, Min-cut clustering. Math. Program. 62 (1993) 133-152. Zbl0807.90117MR1247611
9. [9] A. Mehrotra, Cardinality constrained Boolean quadratic polytope. Discrete Appl. Math. 79 (1997) 137-154. Zbl0898.90092MR1478248
10. [10] P. Michelon et L. Veilleux, Lagrangean methods for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. 92 (1996) 326-341. Zbl0912.90222
11. [11] G.L Nemhauser et L.A. Wolsey, Integer and Combinatorial Optimization. Wiley Intersci. Ser. Discrete Math. Optim. (1988). Zbl0652.90067MR948455
12. [12] M. Padberg, The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45 (1989) 139-172. Zbl0675.90056MR1017216
13. [13] D.J. Rader, Valid inequalities and facets of the quadratic 0-1 knapsack polytope. Rutcor Research Report 16-97 (1997) 11 p. 
14. [14] D.J. Rader, Lifting results for the quadratic 0-1 knapsack polytope. Rutcor Research Report 17-97 (1997) 27 p. 
15. [15] M.G.C. Resende, K.G. Ramakrishnan et Z. Drezner, Computing Lower Bounds for the Quadratic assignment problem with an interior point algorithm for linear programming. Oper. Res. 43 (1995) 781-791. Zbl0843.90068MR1361340
16. [16] E. Soutif, Résolution du problème de sac-à-dos quadratique en variables bivalentes. Thèse de doctorat du CNAM Paris (2000). 
17. [17] E. Zemel, Lifting the facets of zero-one polytopes. Math. Program. 15 (1978) 268-277. Zbl0428.90042MR514612