Nous présentons quelques schémas pour la relaxation lagrangienne d'un problème de programmation quadratique 0-1 avec des contraintes linéaires. Nous ferons une comparaison théorique des bornes trouvées par les différents schémas
de relaxation.

Linéariser un problème quadratique en variables binaires est une idée qui se présente assez naturellement : cela permet, entre autres choses, de pouvoir aborder sa résolution en utilisant un code standard de programmation linéaire. Nous présenterons ici les techniques de linéarisation proposées dans la littérature. Nous exposerons également un schéma général de linéarisation et montrerons que ces techniques, classiques et anciennes, sont en fait des cas particuliers de ce schéma. Nous proposerons également, à partir de ce schéma général, une nouvelle technique de linéarisation présentant un bon rapport entre le nombre de variables supplémentaires introduites et la qualité de la borne.

Les problèmes d'affectation quadratique (PAQ) sont parmi les problèmes d'optimisation combinatoire les plus complexes. Certaines instances ayant des tailles n >= 30 demeurent ouvertes depuis des décennies. La résolution de ces problèmes nécessite à la fois l'amélioration des techniques d'optimisation et l'utilisation de plate-formes de calcul extrêmement puissantes. Dans cet exposé, nous présentons une nouvelle approche pour la résolution des PAQ basée sur un algorithme de branch-and-bound sophistiqué fonctionnant sur des fédérations de machines massivement distribuées appellées "grid". Les résultats de la résolution de PAQ de grandes tailles incluant nug30, kra30b et tho30 sont présentés.