Building facets for the quadratic 0-1 knapsack polytope

Alain Faye; Olivier Boyer

RAIRO - Operations Research (2010)

  • Volume: 37, Issue: 4, page 249-271
  • ISSN: 0399-0559

Abstract

top
We build facets of the quadratic 0-1 knapsack polytope following two different approaches. The quadratic 0-1 knapsack polytope is included in the Boolean quadric polytope introduced by Padberg [12] for unconstrained 0-1 quadratic problem. So in a first approach, we ask the question which are the facets of the Boolean quadric polytope that are still facets of the quadratic 0-1 knapsack polytope. Results for this problem are given for the cut inequality introduced by Padberg [12]. We give necessary and sufficient conditions for which the cut inequality induces a facet of the quadratic 0-1 knapsack polytope and when these conditions are not satisfied we give a lifting of the inequality. In a different way, following the linearization technique of Adams and Sherali [1], we build facets of the quadratic 0-1 knapsack polytope from facets of the linear 0-1 knapsack polytope multiplying a linear inequality by a variable xi or x ¯ i =1-xi. We show that this approach gives facets of the quadratic 0-1 knapsack polytope and we extend it to multiplying an inequality that induces a facet of the quadratic 0-1 knapsack polytope. To conclude, we give numerical results of a cutting plane algorithm involving cuts built following these two schemes.

How to cite

top

Faye, Alain, and Boyer, Olivier. "Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1." RAIRO - Operations Research 37.4 (2010): 249-271. <http://eudml.org/doc/105294>.

@article{Faye2010,
abstract = { Nous construisons des familles de facettes du polytope du sac-à-dos quadratique en 0-1 selon les deux approches suivantes. Le Boolean quadric polytope (introduit dans le cas sans contraintes par Padberg [12]) contenant le polytope du sac-à-dos quadratique, une première approche consiste à se demander sous quelles conditions une facette du premier est aussi une facette du second et quand ces conditions ne sont pas remplies quels liftings permettent d'en faire une facette. Des réponses à ces questions sont données dans le cas de l'inégalité "coupe" introduite par Padberg. Dans une seconde approche, suivant la méthode de linéarisation d'Adams et Sherali [1], nous multiplions par une variable directe ou complémentée une facette du polytope du sac-à-dos linéaire. Nous montrons que cette approche permet d'obtenir des facettes du polytope du sac-à-dos quadratique et nous l'étendons par la suite à la multiplication de facettes du sac-à-dos quadratique lui-même. Des résultats numériques illustrent la mise en oeuvre dans un algorithme de coupes, d'inégalités ainsi obtenues. },
author = {Faye, Alain, Boyer, Olivier},
journal = {RAIRO - Operations Research},
keywords = { Polytope du sac-à-dos quadratique en 0-1; méthodes polyédriques.},
language = {fre},
month = {3},
number = {4},
pages = {249-271},
publisher = {EDP Sciences},
title = {Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1},
url = {http://eudml.org/doc/105294},
volume = {37},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 4
SP - 249
EP - 271
AB - Nous construisons des familles de facettes du polytope du sac-à-dos quadratique en 0-1 selon les deux approches suivantes. Le Boolean quadric polytope (introduit dans le cas sans contraintes par Padberg [12]) contenant le polytope du sac-à-dos quadratique, une première approche consiste à se demander sous quelles conditions une facette du premier est aussi une facette du second et quand ces conditions ne sont pas remplies quels liftings permettent d'en faire une facette. Des réponses à ces questions sont données dans le cas de l'inégalité "coupe" introduite par Padberg. Dans une seconde approche, suivant la méthode de linéarisation d'Adams et Sherali [1], nous multiplions par une variable directe ou complémentée une facette du polytope du sac-à-dos linéaire. Nous montrons que cette approche permet d'obtenir des facettes du polytope du sac-à-dos quadratique et nous l'étendons par la suite à la multiplication de facettes du sac-à-dos quadratique lui-même. Des résultats numériques illustrent la mise en oeuvre dans un algorithme de coupes, d'inégalités ainsi obtenues.
LA - fre
KW - Polytope du sac-à-dos quadratique en 0-1; méthodes polyédriques.
UR - http://eudml.org/doc/105294
ER -

References

top
  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 .  
  2. A. Billionnet et F. Calmels, Linear programming for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res.92 (1996) 310-325 .  
  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 .  
  4. P. Chaillou, P. Hansen et Y. Mahieu, Best network flow bounds for the quadratic knapsack problem. Lect. Notes Math.1403 (1986) 226-235.  
  5. S. Elloumi, A. Faye et E. Soutif, Decomposition and linearization for 0-1 quadratic programming. Ann. Oper. Res.99 (2000) 79-93.  
  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 .  
  7. C. Helmberg, F. Rendl et R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim.4 (2000) 197-215 .  
  8. E.J. Johnson, A. Mehrotra et G.L. Nemhauser, Min-cut clustering. Math. Program.62 (1993) 133-152 .  
  9. A. Mehrotra, Cardinality constrained Boolean quadratic polytope. Discrete Appl. Math.79 (1997) 137-154 .  
  10. P. Michelon et L. Veilleux, Lagrangean methods for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res.92 (1996) 326-341 .  
  11. G.L Nemhauser et L.A. Wolsey, Integer and Combinatorial Optimization. Wiley Intersci. Ser. Discrete Math. Optim. (1988).  
  12. M. Padberg, The boolean quadric polytope: some characteristics, facets and relatives. Math. Program.45 (1989) 139-172 .  
  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 .  
  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 .  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.