Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 4, pp. 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},
     pages = {249--271},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {4},
     year = {2003},
     doi = {10.1051/ro:2004008},
     mrnumber = {2064601},
     zbl = {1092.90030},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ro:2004008/}
}
TY  - JOUR
AU  - Faye, Alain
AU  - Boyer, Olivier
TI  - Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2003
SP  - 249
EP  - 271
VL  - 37
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2004008/
DO  - 10.1051/ro:2004008
LA  - fr
ID  - RO_2003__37_4_249_0
ER  - 
%0 Journal Article
%A Faye, Alain
%A Boyer, Olivier
%T Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2003
%P 249-271
%V 37
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2004008/
%R 10.1051/ro:2004008
%G fr
%F 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, Tome 37 (2003) no. 4, pp. 249-271. doi : 10.1051/ro:2004008. http://www.numdam.org/articles/10.1051/ro:2004008/

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

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

[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

[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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :