La décomposition lagrangienne [9] peut améliorer les bornes sur la valeur optimale de certains problèmes d'optimisation quadratique à contraintes linéaires en variables 0–1. Souvent ces problèmes ne sont pas convexes, donc difficiles à résoudre en entiers. Il est possible de les transformer en problèmes linéaires équivalents en 0-1 par linéarisation (et donc convexification). Ceci peut être réalisé de plusieurs façons, sur la base de principes similaires, à partir de produits des contraintes d'origine par chaque variable 0–1 ou son complément. Les deux étapes clés sont alors, pour chaque nouvelle contrainte, (a) de remplacer le carré d'une variable 0–1 par la variable elle-même, et (b) de remplacer chaque produit de deux variables 0–1 distinctes par une nouvelle variable 0-1. L'étape (a) peut déjà renforcer le modèle en utilisant le fait que les variables d'origine sont binaires. L'étape (b) introduit de nouvelles variables et des informations supplémentaires (linéaires) doivent être saisies pour maintenir l'équivalence avec le modèle quadratique d'origine : étant donné deux variables 0–1 x et y, définir une nouvelle variable 0–1 v comme produit de x par y est une équation non linéaire qui ne peut pas être utilisée comme telle dans un modèle linéaire. Fortet [4] et plus tard McCormick [12] ont proposé des ensembles de contraintes linéaires qui forcent la variable v à être égale au produit de deux variables (0,1) x et y, c'est-à-dire à être égale à 0 à moins que x et y ne soient tous les deux égales à 1. Les approches ultérieures itèrent ou s'appuient sur cette propriété. On construit des séquences de modèles de plus en plus grands, équivalents en variables 0–1 et produisant des bornes par programmation linéaire de plus en plus fortes. L'une de ces méthodes est appelée RLT, « Reformulation Linearization Technique » (Adams et Sherali, [2], [13]). Ils ont prouvé que lorsque le niveau (c'est-à-dire le nombre d'itérations) atteint le nombre de variables 0–1 du problème d'origine, la valeur optimale du dernier programme linéaire en continu est égale à la valeur optimale du problème quadratique d'origine en 0–1. La taille du problème augmente toutefois si rapidement que même pour des instances de taille modérée, le calcul des premières limites continues de bas niveau peut être coûteux. Si le modèle d'origine a n variables 0–1 x(i), i dans I, |I| = n, le modèle RLT1, cad le modèle RLT généré au niveau 1, est un programme linéaire avec n2 variables supplémentaires, disons, v(i,j) , représentant le produit de x(i) par x(j). RLT2 a alors n3 variables supplémentaires w(i,j,k), représentant le produit à droite de v(i,j) par x(k), et ainsi de suite. RLT(k) produit des limites par PL plus strictes que RLT(k-1), pour tout k jusqu'à n, mais au prix d'une forte augmentation des coûts de calcul et de stockage créée par l'ajout de nk+1 variables supplémentaires. À l'heure actuelle, à notre connaissance, seules le calcul de bornes RLT des niveaux 1, 2 et 3 a été tenté (voir par exemple [11] pour RLT3). Notre article précédent [8] était basé sur deux idées qui simplifiaient le calcul et augmentaient la qualité des limites RLT1, sans recourir à un modèle de taille RLT2. Nous avons appelé ces modèles «de type RLT1» pour rappeler qu'ils peuvent ne pas correspondre exactement au format RLT1 standard tel que défini dans [13]. Des idées similaires sont apparues dans la littérature, voir par exemple [1] pour le QAP, et [3] pour le QKP. Nous proposons ici d'utiliser pour le modèle RLT1 de [8] une décomposition lagrangienne [9], plutôt qu'une relaxation. La décomposition produit des sous-problèmes jumeaux, qui peuvent être résolus, comme dans [8], à l'aide de la propriété LIP de linéarisation des produits entiers ([5], [6], voir aussi [7]). Cela garantit une borne au moins aussi bonne que la relaxation lagrangienne proposée dans [8]. Nous présentons des résultats sur des instances de sac à dos quadratiques de la littérature.
Références.
[1] Adams W.P. and Johnson T.A., 1994, Discrete Mathematics and Theoretical Computer Science, 16,43-77
[2] Adams W.P. and Sherali H.D., 1986, Management Science 32(10), 1274-1290.
[3] Caprara A., Pisinger D. and Toth, P., 1999, INFORMS Journal on Computing, 11(2), 125-137.
[4] Fortet R., 1959, Cahiers du Centre d'Etudes en Recherche Opérationnelle.
[5] Geoffrion A.M., 1974, Mathematical Programming Study 2, 82-114.
[6] Geoffrion A.M. and McBride, R., 1978, AIIE Transactions, 10(1) 40-47.
[7] Guignard M., 2003, TOP 11(2) 151-228.
[8] Guignard M., 2020, Annals of Operations Research, 286, 173-200.
[9] Guignard M. and Kim S., 1987, Mathematical Programming, 39(2), 215-228.
[10] Guignard M. and Park J., forthcoming report, 2022.
[11] Hahn P.M., Zhu Y.R., Guignard, M. and Hightower W.L., 2012, INFORMS Journal on Computing, 24(2) 202-209. 2012
[12] McCormick 1976, Mathematical Programming, 10, 147-175.
[13] Sherali H.D. and Adams W.P., SIAM J. on Discrete Mathematics, 3(3), 411-430, 1990.