Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, p. 249-271
@article{RO_2003__37_4_249_0,
     author = {Faye, Alain and Boyer, Olivier},
     title = {Construction de facettes pour le polytope du sac-\`a-dos quadratique en 0-1},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {4},
     year = {2003},
     pages = {249-271},
     doi = {10.1051/ro:2004008},
     zbl = {1092.90030},
     mrnumber = {2064601},
     language = {fr},
     url = {http://www.numdam.org/item/RO_2003__37_4_249_0}
}
Faye, Alain; Boyer, Olivier. Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1. RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, pp. 249-271. doi : 10.1051/ro:2004008. http://www.numdam.org/item/RO_2003__37_4_249_0/

[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. | MR 861711 | Zbl 0623.90054

[2] A. Billionnet et F. Calmels, Linear programming for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. 92 (1996) 310-325. | Zbl 0912.90221

[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. | Zbl 0933.90049

[4] P. Chaillou, P. Hansen et Y. Mahieu, Best network flow bounds for the quadratic knapsack problem. Lect. Notes Math. 1403 (1986) 226-235. | Zbl 0678.90061

[5] S. Elloumi, A. Faye et E. Soutif, Decomposition and linearization for 0-1 quadratic programming. Ann. Oper. Res. 99 (2000) 79-93. | MR 1837733 | Zbl 0990.90073

[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. | MR 1967292 | Zbl 1042.90035

[7] C. Helmberg, F. Rendl et R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim. 4 (2000) 197-215. | MR 1772826 | Zbl 0970.90075

[8] E.J. Johnson, A. Mehrotra et G.L. Nemhauser, Min-cut clustering. Math. Program. 62 (1993) 133-152. | MR 1247611 | Zbl 0807.90117

[9] A. Mehrotra, Cardinality constrained Boolean quadratic polytope. Discrete Appl. Math. 79 (1997) 137-154. | MR 1478248 | Zbl 0898.90092

[10] P. Michelon et L. Veilleux, Lagrangean methods for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. 92 (1996) 326-341. | Zbl 0912.90222

[11] G.L Nemhauser et L.A. Wolsey, Integer and Combinatorial Optimization. Wiley Intersci. Ser. Discrete Math. Optim. (1988). | MR 948455 | Zbl 0652.90067

[12] M. Padberg, The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45 (1989) 139-172. | MR 1017216 | Zbl 0675.90056

[13] D.J. Rader, Valid inequalities and facets of the quadratic 0-1 knapsack polytope. Rutcor Research Report 16-97 (1997) 11 p.

[14] D.J. Rader, Lifting results for the quadratic 0-1 knapsack polytope. Rutcor Research Report 17-97 (1997) 27 p.

[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. | MR 1361340 | Zbl 0843.90068

[16] E. Soutif, Résolution du problème de sac-à-dos quadratique en variables bivalentes. Thèse de doctorat du CNAM Paris (2000).

[17] E. Zemel, Lifting the facets of zero-one polytopes. Math. Program. 15 (1978) 268-277. | MR 514612 | Zbl 0428.90042