Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Formulations linéaires miniaturisées pour problèmes quadratiques en variables binaires

Serigne Guèye, Philippe Yves Paul Michelon

Published Jan 1, 2002• 0 citations
OpenAlex

Related papers

Un schéma de linéarisation pour les problèmes quadratiques en variables binaires

Serigne Guèye, Philippe Yves Paul Michelon

•Jan 1, 2002•0 citations

Programmation quadratique en variables binaires

Brossard, Nicolas

•Jan 1, 1995•0 citations

Résolution de programmes non linéaires en variables 0-1 par la programmation linéaire et la programmation quadratique convexe

Alain Billionnet

•Jan 1, 2005•0 citations

Optimisation quadratique en variables 0-1

Alain Billionnet

•Jan 1, 2005•2 citations

Résolution du problème de suites binaires avec faible autocorrélation à l'aide d'une reformulation quadratique convexe

Amélie Lambert, Sourour Elloumi, Arnaud Lazare

•Feb 12, 2018•0 citations

Linéarisation et relaxation lagrangienne pour problèmes quadratiques en variables binaires

Serigne Guèye

Un probleme quadratique en variables binaires est un probleme d'optimisation en variables binaires consistant a minimiser une fonction objectif quadratique sous des contraintes lineaires. Dans cas general, c'est un probleme dificile a resoudre de maniere exacte (NP- difficile), trouvant de nombreuses applications pratiques. La resolution exacte du probleme passe par determination de bornes inferieures qu'il convient d'integrer dans des schemas de separation et evaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de programmation semi-definie positive a l'optimisation globale, sont utilisees pour determiner ces bornes. Nous nous sommes particulierement interesses aux methodes lagrangiennes et aux techniques de linearisation. Nous avons traite dans cette these deux instances particulieres du probleme : la bipolarisation de graphes avec contrainte de cardinalite et le probleme quadratique en variables binaires sans contrainte. Pour bipartition de graphes, nous avons propose une demarche hybride melant relaxation lagrangienne et linearisation de probleme. Les tests numeriques, issus de l'algorithme resultant, ont montre des ameliorations significatives par rapport a certaines techniques existantes. Pour probleme quadratique en variables binaires sans contrainte, des etudes sur les techniques de linearisation ont ete effectuees. Elles consistent a remplacer fonction objectif quadratique par une forme lineaire, grâce a l'ajout de variables permettant de remplacer les parties quadratiques de fonction. L'ajout de ces variables entrainent [sic] aussi l'ajout de contraintes visant a s'assurer de validite du remplacement. Apres etude et tests des linearisations existantes, nous unifions ces techniques dans un schema general de linearisation. De nouveaux modeles ont, grâce a ce schema , vu jour et ameliorent significativement les resultats numeriques des formulations lineaires precedentes

•Jan 1, 2002•4 citations
Un probleme quadratique en variables binaires est un probleme d'optimisation en variables binaires consistant a minimiser une fonction objectif quadratique sous des contraintes lineaires. Dans cas general, c'est un probleme dificile a resoudre de maniere exacte (NP- difficile), trouvant de nombreuses applications pratiques. La resolution exacte du probleme passe par determination de bornes inferieures qu'il convient d'integrer dans des schemas de separation et evaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de programmation semi-definie positive a l'optimisation globale, sont utilisees pour determiner ces bornes. Nous nous sommes particulierement interesses aux methodes lagrangiennes et aux techniques de linearisation. Nous avons traite dans cette these deux instances particulieres du probleme : la bipolarisation de graphes avec contrainte de cardinalite et le probleme quadratique en variables binaires sans contrainte. Pour bipartition de graphes, nous avons propose une demarche hybride melant relaxation lagrangienne et linearisation de probleme. Les tests numeriques, issus de l'algorithme resultant, ont montre des ameliorations significatives par rapport a certaines techniques existantes. Pour probleme quadratique en variables binaires sans contrainte, des etudes sur les techniques de linearisation ont ete effectuees. Elles consistent a remplacer fonction objectif quadratique par une forme lineaire, grâce a l'ajout de variables permettant de remplacer les parties quadratiques de fonction. L'ajout de ces variables entrainent [sic] aussi l'ajout de contraintes visant a s'assurer de validite du remplacement. Apres etude et tests des linearisations existantes, nous unifions ces techniques dans un schema general de linearisation. De nouveaux modeles ont, grâce a ce schema , vu jour et ameliorent significativement les resultats numeriques des formulations lineaires precedentes