Abstract FR:

Dans cette these, nous nous sommes interesses a l'optimisation des fonctions pseudo booleennes quadratiques sans contrainte. Ce probleme est frequemment designe dans la litterature comme etant celui de la recherche d'une la coupe maximale dans un graphe value ou non (max-cut). C'est un probleme np complet. Le travail propose se decompose en trois parties. Dans la premiere partie, nous essayons d'obtenir de bonnes solutions en utilisant une methode heuristique. Plus particulierement, nous proposons une version de l'algorithme de recuit simule qui permet d'utiliser au mieux les architectures paralleles des nouveaux super-calculateurs, et nous appliquons cet algorithme a notre probleme d'optimisation. Dans la deuxieme partie, nous considerons une modelisation microscopique de l'aimantation par une fonction quadratique en variables bivalentes. Cette modelisation nous permet de realiser etude de la transition de phases de l'endommagement dans un verre de spins a deux dimensions. Dans la troisieme partie nous etudions des relaxations polyedriques de ce probleme. En particulier, nous decrivons de nouvelles familles de facettes du polytope associe a la linearisation de notre probleme, et nous decrivons un algorithme de generation de coupes