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

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

Alain Billionnet

Published Jan 1, 2005• 0 citations
OpenAlex

Related papers

Reformulations quadratiques convexes pour la programmation quadratique en variables 0-1

Marie-Christine Plateau

Dans ce travail de thèse, nous nous sommes intéressés à la résolution exacte de problèmes d'optimisation en variables 0-1 (notés (Q01)), comportant une fonction objectif quadratique soumise à des contraintes linéaires. Les problèmes de bipartition de graphe, d'affectation quadratique, du sac-à-dos quadratique en sont des exemples très connus et amplement étudiés dans la littérature de l'optimisation combinatoire. On les rencontre également, de façon plus concrète, dans les domaines scientifiques, économiques et industriels tels que le choix d'investissements, la gestion de portefeuilles, la conception de réseaux, le transport, etc. Malgré des travaux pionniers datant de plus de vingt ans, les problèmes non linéaires en variables bivalentes demeurent en général mal résolus. Parvenir à résoudre les programmes (Q01) de grande taille représente donc un enjeu très important. Le but de cette thèse est de proposer des méthodes originales et efficaces de résolution exacte des programmes (Q01). Plus précisément, notre approche prinicpale consiste en une reformulation quadratique convexe du problème initial dans le but d'utiliser les méthodes générales de résolution des programmes quadratiques convexes en variables entières. Cette approche peut être comparée, dans son esprit, à la reformulation de problèmes non linéaires en variables 0-1 par des problèmes linéaires en variables mixtes, technique étudiée depuis longtemps et connue sous le nom de linéarisation. Une partie de notre travail est consacrée à la présentation d'une nouvelle reformulation linéaire des programmes d'optimisation quadratique en 0-1. Dans les deux cas, les problèmes reformulés peuvent être résolus par des solveurs standards de programmes en variables mixtes. Nous présentons également de nombreuses expérimentations de notre reformulation quadratique convexe concernant trois problèmes non convexes classiques de l'optimisation combinatoire (le problème de bipartition, du sous-graphe le plus dense et un problème de minimisation d'échange d'outils). Les expérimentations montrent l'intérêt de l'approche : dans la plupart des cas, sur les instances étudiées, la méthode proposée est nettement plus efficace que les méthodes connues à ce jour. Des résultats expérimentaux sont également présentés, concernant trois problèmes convexes (le problème de plus court chemin probabiliste, un problème d'investissements, un problème d'ordonnancement). Notre approche peut également se révéler, dans certains cas, très intéressante.

•Jan 1, 2006•12 citations

Utilisation de la programmation semidéfinie pour la résolution exacte de programmes quadratiques en variables 0-1

Marie-Christine Plateau

Utilisation de la programmation semidéfinie pour la résolution exacte de programmes quadratiques en variables 0-1

•Jan 1, 2007•0 citations

Satisfaction de contraintes non linéaires en variables 0-1 et outils de la programmation quadratique

Mohamed Ettaouil

Notre travail s'inscrit dans le cadre des études consacrées à la programmation mathématique en nombres entiers. Plus précisément, il concerne la résolution exacte du problème de satisfaction de contraintes non linéaires en variables 0-1. La méthode que nous proposons pour résoudre le problème de satisfaction de contraintes non linéaires a variables bivalentes, se place dans le même ordre d'idée que la méthode fast proposée par Bennaceur et plateau dans le cas linéaire. Elle s'appuie sur la résolution d'une suite de problèmes d'optimisation non linéaires en variables 0-1. Pour résoudre chacun d'eux nous proposons de privilégier les méthodes approchées utilisant les concepts fondamentaux: heuristiques, dualité, réduction et recherche arborescente. L'étude plus spécifique de la programmation quadratique en nombres entiers, a permis de valider la méthode en menant des expériences numériques dans le cadre de la satisfaction de contraintes quadratiques en variables 0-1

•Jan 1, 1994•0 citations

Plénière: Programmation non-linéaire en variables mixtes et applications

Pierre Bonami

La programmation non-linéaire en variable mixtes consiste à minimiser une fonction non-linéaire sur un ensemble de solutions décrit par des fonctions non-linéaires et des contraintes d'intégrité portant sur tout ou partie des variables. Depuis une dizaine d'année de nombreux travaux se sont intéressé aux aspects théoriques et algorithmiques de la résolution de ces problèmes. Ces travaux ont donné lieu à la réalisation de plusieurs solveurs open-source ou commerciaux. Dans cette présentation, nous décrirons les principales classes de problèmes et les idées algorithmiques implémentées dans les logiciels de résolutions actuels. Nous nous intéresserons en particulier au cas où la relaxation continue naturelle du problème est un problème convexe et au cas ou seule la fonction objective est non-linéaire et est quadratique. Nous nous appuierons en particulier sur les exemples du solveur Bonmin et du solveur global de programmation quadratique non-convexe récemment introduit dans le logiciel CPLEX.

•Feb 26, 2014•0 citations

Optimisation non lineaire en variables bivalentes et applications

Rouquia Djabali

Le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sous une contrainte lineaire est np-difficile. Par consequent, l'obtention de bornes inferieures est importante. Nous avons etudie differentes methodes pour calculer des bornes inferieures de la solution optimale et nous montrons que le calcul de ces bornes revient a la resolution de programmes lineaires continus. La principale originalite de nos travaux, est qu'ils generalisent les bornes proposees pour le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sans contraintes. Nous avons ensuite applique le calcul des bornes proposees a des problemes particuliers ; la bipartition minimale d'un graphe, l'ensemble stable de cardinal maximal d'un graphe et le sac a dos quadratique. Pour chaque probleme nous avons mis en evidence des proprietes interessantes qui permettent de simplifier le calcul des bornes et des coupes qui permettent d'ameliorer la qualite des bornes proposees. En outre, pour reduire le temps de resolution des programmes lineaires continus consideres, nous avons elabore une methode de coupes qui permet de resoudre des programmes lineaires continus de maniere approchee. Enfin, pour chaque probleme particulier, nous avons integre notre methode de coupes dans un algorithme de resolution exacte (branch and cut). Nous nous sommes egalement interesse a un probleme d'optimisation lie a l'architecture des futurs reseaux numeriques urbains. Le probleme est de determiner une topologie en anneau de cout minimal qui respecte un certain nombre de contraintes. Nous avons modelise ce probleme a l'aide de la programmation mathematique et montre qu'une methode de resolution fondee sur la programmation lineaire en nombres entiers et les methodes de coupes permet de traiter des problemes reels avec un temps de calcul raisonnable.

•Jan 1, 1998•2 citations

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

Serigne Guèye, Philippe Yves Paul Michelon

•Jan 1, 2002•0 citations
Dans ce travail de thèse, nous nous sommes intéressés à la résolution exacte de problèmes d'optimisation en variables 0-1 (notés (Q01)), comportant une fonction objectif quadratique soumise à des contraintes linéaires. Les problèmes de bipartition de graphe, d'affectation quadratique, du sac-à-dos quadratique en sont des exemples très connus et amplement étudiés dans la littérature de l'optimisation combinatoire. On les rencontre également, de façon plus concrète, dans les domaines scientifiques, économiques et industriels tels que le choix d'investissements, la gestion de portefeuilles, la conception de réseaux, le transport, etc. Malgré des travaux pionniers datant de plus de vingt ans, les problèmes non linéaires en variables bivalentes demeurent en général mal résolus. Parvenir à résoudre les programmes (Q01) de grande taille représente donc un enjeu très important. Le but de cette thèse est de proposer des méthodes originales et efficaces de résolution exacte des programmes (Q01). Plus précisément, notre approche prinicpale consiste en une reformulation quadratique convexe du problème initial dans le but d'utiliser les méthodes générales de résolution des programmes quadratiques convexes en variables entières. Cette approche peut être comparée, dans son esprit, à la reformulation de problèmes non linéaires en variables 0-1 par des problèmes linéaires en variables mixtes, technique étudiée depuis longtemps et connue sous le nom de linéarisation. Une partie de notre travail est consacrée à la présentation d'une nouvelle reformulation linéaire des programmes d'optimisation quadratique en 0-1. Dans les deux cas, les problèmes reformulés peuvent être résolus par des solveurs standards de programmes en variables mixtes. Nous présentons également de nombreuses expérimentations de notre reformulation quadratique convexe concernant trois problèmes non convexes classiques de l'optimisation combinatoire (le problème de bipartition, du sous-graphe le plus dense et un problème de minimisation d'échange d'outils). Les expérimentations montrent l'intérêt de l'approche : dans la plupart des cas, sur les instances étudiées, la méthode proposée est nettement plus efficace que les méthodes connues à ce jour. Des résultats expérimentaux sont également présentés, concernant trois problèmes convexes (le problème de plus court chemin probabiliste, un problème d'investissements, un problème d'ordonnancement). Notre approche peut également se révéler, dans certains cas, très intéressante.
Notre travail s'inscrit dans le cadre des études consacrées à la programmation mathématique en nombres entiers. Plus précisément, il concerne la résolution exacte du problème de satisfaction de contraintes non linéaires en variables 0-1. La méthode que nous proposons pour résoudre le problème de satisfaction de contraintes non linéaires a variables bivalentes, se place dans le même ordre d'idée que la méthode fast proposée par Bennaceur et plateau dans le cas linéaire. Elle s'appuie sur la résolution d'une suite de problèmes d'optimisation non linéaires en variables 0-1. Pour résoudre chacun d'eux nous proposons de privilégier les méthodes approchées utilisant les concepts fondamentaux: heuristiques, dualité, réduction et recherche arborescente. L'étude plus spécifique de la programmation quadratique en nombres entiers, a permis de valider la méthode en menant des expériences numériques dans le cadre de la satisfaction de contraintes quadratiques en variables 0-1
La programmation non-linéaire en variable mixtes consiste à minimiser une fonction non-linéaire sur un ensemble de solutions décrit par des fonctions non-linéaires et des contraintes d'intégrité portant sur tout ou partie des variables. Depuis une dizaine d'année de nombreux travaux se sont intéressé aux aspects théoriques et algorithmiques de la résolution de ces problèmes. Ces travaux ont donné lieu à la réalisation de plusieurs solveurs open-source ou commerciaux. Dans cette présentation, nous décrirons les principales classes de problèmes et les idées algorithmiques implémentées dans les logiciels de résolutions actuels. Nous nous intéresserons en particulier au cas où la relaxation continue naturelle du problème est un problème convexe et au cas ou seule la fonction objective est non-linéaire et est quadratique. Nous nous appuierons en particulier sur les exemples du solveur Bonmin et du solveur global de programmation quadratique non-convexe récemment introduit dans le logiciel CPLEX.
Le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sous une contrainte lineaire est np-difficile. Par consequent, l'obtention de bornes inferieures est importante. Nous avons etudie differentes methodes pour calculer des bornes inferieures de la solution optimale et nous montrons que le calcul de ces bornes revient a la resolution de programmes lineaires continus. La principale originalite de nos travaux, est qu'ils generalisent les bornes proposees pour le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sans contraintes. Nous avons ensuite applique le calcul des bornes proposees a des problemes particuliers ; la bipartition minimale d'un graphe, l'ensemble stable de cardinal maximal d'un graphe et le sac a dos quadratique. Pour chaque probleme nous avons mis en evidence des proprietes interessantes qui permettent de simplifier le calcul des bornes et des coupes qui permettent d'ameliorer la qualite des bornes proposees. En outre, pour reduire le temps de resolution des programmes lineaires continus consideres, nous avons elabore une methode de coupes qui permet de resoudre des programmes lineaires continus de maniere approchee. Enfin, pour chaque probleme particulier, nous avons integre notre methode de coupes dans un algorithme de resolution exacte (branch and cut). Nous nous sommes egalement interesse a un probleme d'optimisation lie a l'architecture des futurs reseaux numeriques urbains. Le probleme est de determiner une topologie en anneau de cout minimal qui respecte un certain nombre de contraintes. Nous avons modelise ce probleme a l'aide de la programmation mathematique et montre qu'une methode de resolution fondee sur la programmation lineaire en nombres entiers et les methodes de coupes permet de traiter des problemes reels avec un temps de calcul raisonnable.