Auswahl der wissenschaftlichen Literatur zum Thema „Problème Linéaire en Nombres Entiers“

Dans le cadre des algorithmes numériques introduits et élaborés par les mathématiciens arabes, à partir du ixe siècle, figure l'algorithme de l'extraction de la racine carrée d'un entier naturel. Cet algorithme a été étudié chez plusieurs d'entre eux et surtout bien expliqué par alBaġdādī (mort vers 1037) dans le chapitre « Comment extraire la racine des nombres entiers » de son livre « La complétion du calcul », Al-takmila fī al-ḥisāb 1. Dans ce chapitre, al-Baġdādī expose son travail pédagogiquement en six sections traitant de plusieurs manières différentes le problème de l'extraction de la racine carrée d'un entier 2. À la même époque, dans un texte isolé intitulé « Sur la cause de la racine, de son doublement et de son déplacement 3 », Ibn al-Hayṯam (mort vers 1040) donne une justification géométrique de l'algorithme en se basant sur des notions algébriques précises.

Every positive integer can be written as a sum of Fibonacci numbers; it can also be written as a (finite) sum of (positive and negative) powers of the golden mean φ. We show that there exists a letter-to-letter finite two-tape automaton that maps the Fibonacci representation of any positive integer onto its φ-expansion, provided the latter is folded around the radix point. As a corollary, the set of φ-expansions of the positive integers is a linear context-free language. These results are actually proved in the more general case of quadratic Pisot units. Résumé: Tout nombre entier positif peut s'écrire comme une somme de nombres de Fibonacci; tout entier peut également s'écrire comme une somme (finie) de puissances (positives et négatives) du "nombre d'or" φ. Nous montrons qu'il existe un automate à deux bandes, fini et lettre-à-lettre, qui envoie la représentation d'un entier en base de Fibonacci sur sa représentation dans la base φ modulo le fait qu'on a replié cette dernière autour du point décimal. On en déduit que l'ensemble des représentations des entiers en base φ est un langage context-free linéaire. Tous ces résultats sont en fait établis dans le cas général où la base considérée est un nombre de Pisot quadratique unitaire.

Très souvent, les services techniques ne disposent que du plan du réseau d'assainissement sans le profil en long. Or les cotes radiers sont nécessaires aux simulations hydrauliques effectuées, par exemple, lors des études diagnostic. Pour pallier ce manque, les bureaux d'étude effectuent généralement un relevé sommaire et interpolent linéairement les cotes radier manquantes. Cette interpolation linéaire peut être la source d'erreurs importantes. Nous proposons donc dans cet article une nouvelle méthode d'interpolation permettant de minimiser ces erreurs. Cette méthode utilise trois types d'informations : les données connues, les contraintes et les critères. Les données connues correspondent aux informations disponibles quant au réseau. Les contraintes sont les règles constructives auxquelles tout réseau d'assainissement doit se conformer. Les critères sont les règles d'optimisation construites à partir d'observations sur des réseaux réels. Pour résoudre ce problème d'optimisation sous contraintes, nous utilisons des algorithmes génétiques parce que ces derniers sont capables de travailler avec un grand nombre de variables, des nombres réels et des fonctions non-linéaires. Des tests ont été effectués sur les réseaux des villes d'Annequin, de Bapaume et de Lyon. Dans tous les cas (tronçons longs ou courts, pente forte ou faible), les résultats obtenus avec notre méthode sont meilleurs que ceux obtenus avec la classique interpolation linéaire. Il est même possible de déterminer la présence de contre-pente.

International audience Motivated by the classical Frobenius problem, we introduce the Frobenius poset on the integers $\mathbb{Z}$, that is, for a sub-semigroup $\Lambda$ of the non-negative integers $(\mathbb{N},+)$, we define the order by $n \leq_{\Lambda} m$ if $m-n \in \Lambda$. When $\Lambda$ is generated by two relatively prime integers $a$ and $b$, we show that the order complex of an interval in the Frobenius poset is either contractible or homotopy equivalent to a sphere. We also show that when $\Lambda$ is generated by the integers $\{a,a+d,a+2d,\ldots,a+(a-1)d\}$, the order complex is homotopy equivalent to a wedge of spheres. Motivé par le problème de Frobenius classique, nous introduisons l'ensemble partiellement ordonné de Frobenius sur les entiers $\mathbb{Z}$, c.à.d. que pour un sous-semigroupe $\Lambda$ de les entiers non-négatifs $(\mathbb{N},+)$ nous définissons l'ordre par $n \leq_{\Lambda} m$ si $m-n \in \Lambda$. Quand le $\Lambda$ est engendré par deux nombres $a$ et $b$, relativement premiers entre eux, nous montrons que le complexe des chaînes d'un intervalle quelconque dans l'ensemble partiellement ordonné de Frobenius est soit contractible soit homotopiquement équivalent à une sphère. Nous montrons aussi que dans le cas où $\Lambda$ est engendré par les entiers $\{a,a+d,a+2d,\ldots,a+(a-1)d\}$, le complexe des chaînes a le type de homotopie d'un bouquet de sphères.

International audience We consider a large family of equivalence relations on permutations in $S_n$ that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, conditional upon the presence of a third element of suitable value and location. For some relations of this type, we compute the number of equivalence classes, determine how many $n$-permutations are equivalent to the identity permutation, or characterise this equivalence class. Although our results include familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and special classes of permutations (layered, connected, and $123$-avoiding), some of the sequences that arise appear to be new. Nous considérons une famille de relations d’équivalence sur l'ensemble $S_n$ des permutations, qui généralisent les relations de Knuth liées à la correspondance Robinson-Schensted. Dans notre contexte général, deux permutations sont considérées comme équivalentes si l'une peut être obtenue de l'autre auprès d'une séquence de remplacements d'un motif par un autre selon des règles précisées. Désormais, nous ne considérons dans l’œuvre actuelle que les motifs qui correspondent à la transposition de deux éléments, conditionné sur la présence d'un élément de valeur et de position approprié. Pour plusieurs exemples de ce problème, nous énumérons les classes d'équivalence, nous déterminons combien de permutations sur $n$ éléments sont équivalentes à l'identité, ou nous précisons la forme des éléments dans cette dernière classe. Bien que nos résultats retrouvent des séquences des entiers très bien connues (nombres de Catalan, de Fibonacci, de Tribonacci...) ainsi que des classes de permutations déjà étudiées (en couches, connexes, sans motif $123$), nous trouvons également des séquences qui paraissent être nouvelles.

L'objet de cette thèse est l'étude et la résolution de problèmes d'optimisation combinatoire dans les graphes : les problèmes de multiflot maximal en nombres entiers et de multicoupe minimale, ainsi que de plusieurs problèmes connexes : les problèmes de coupe et flot multiterminaux, de flots inséparables, de multichemins et de chemins disjoints par les arêtes. Après avoir effectué une étude bibliographique, nous montrons que les problèmes de multiflot et de multicoupe sont polynomiaux dans les arbres orientés puis nous proposons un algorithme de séparation et d 'évaluation afin de résoudre le problème NP-difficile de la multicoupe minimale dans les arbres non orientés. Nous proposons enfin des algorithmes polynomiaux pour les problèmes de coupe et de flot multiterminaux et pour le problème de la multicoupe minimale dans les anneaux
The object of this work is to study and to solve combinatorial optimization problems in graphs : maximum integral multiflow and minimum multicut problems, and some subproblems, as the multiterminal cut and flow, the unspittable flow, the multipath and the edge disjoint path problems are polynomial in directed trees and we propose a polynomial algorithm to solve both problems in rooted trees. We use linear programming and semi-definite programming in a branch and bound algorithm in order to solve the NP-hard minimum multicut problem in undirected trees. We propose also polynomial algorithms for the multiterminal cut and flow problems and for the minimum multicut problem in rings

La programmation linéaire en nombres entiers (PLNE) connait une utilisation de plus en plus importante pour la modélisation et la résolution des problèmes pratiques. Par ailleurs, à cause de certains problèmes complexes et fortement combinatoires, les méthodes de résolution issues de la PLNE peuvent perdre de leur efficacité. Dans nos travaux de recherche, nous nous intéresserons à la réduction de l’exhaustivité des procédures de la PLNE afin d’échapper à l’explosion combinatoire à laquelle nous serons confrontés. En effet, nous montrons comment la PLNE peut contribuer efficacement à la résolution de deux problèmes de l’optimisation combinatoire, NP-difficiles : le problème de placement en trois dimensions (3D-SBSBPP) et une variante de la famille des problèmes de knapsack (MMKP). Le premier problème est issu du monde industriel, en particulier de la logistique où l’on se propose, par exemple, de résoudre un problème de chargement de conteneurs (colis, palettes, etc. ) dans le processus d’une chaine logistique. Le deuxième problème intervient aujourd’hui dans diverses applications pratiques de grande importance comme l’allocation des ressources dans un réseau informatique et, dans la modélisation du problème d’adaptation dynamique des ressources d’un système multimédia pour assurer la qualité de service nécessaire pour le trafic multimédia. Une première partie est consacrée à l’étude du problème 3D-SBSBPP. Dans un premier temps, nous proposons une modélisation sous forme d’un PLNE. Ensuite, afin de déterminer un encadrement efficace des bornes inférieures (minorants), nous proposons de nouvelles contraintes valides pour le programme mathématique. Dans la continuité de ce travail, nous proposons de nouvelles heuristiques, puis une méthode augmentée qui est basée sur une technique de ré-optimisation. Finalement, en s’appuyant sur certains paramètres de pénalité sur des contraintes, d’autres méthodes hybrides sont aussi proposées. La deuxième partie de nos travaux de recherche consiste en l’étude du problème MMKP. Dans un premier temps, nous proposons un modèle équivalent pour le problème MMKP. Ce modèle est construit à partir d’une solution (admissible ou non-admissible) obtenue par une relaxation Lagrangienne. Le but du modèle proposé est double: il permet de répondre à l’existence d’une solution admissible pour le MMKP et, de le résoudre à l’optimum. Nous montrons aussi que ce modèle est de complexité théorique moins importante que celle du modèle original. Dans un deuxième temps, nous proposons une autre méthode exacte combinant le modèle équivalent et une méthode par séparation et évaluation. Finalement, nous proposons l’adaptation des deux approches résultantes afin de résoudre des instances de grande taille
This thesis deals with Integer Linear Programming (ILP) : an effective approach for modeling and solving combinatorial optimization problems. ILP is becoming more and more important for treating practical problems in recent research. Despite the fact that the problem has often a complex and highly combinatorial structure, ILP-based resolution methods may lose their effectiveness. The main goal of our framework is to reduce the completeness of ILP-based method by exploiting the problem's particular properties. In order to show how the ILP could contribute effectively to solving combinatorial optimization problems, we consider two NP-hard problems : 3D Single Bin-Size Bin Packing Problem and Multi-dimensional Multi-choice Multiple Knapsack Problem. The first problem comes from the industrial world, particularly in logistics processes where it is proposed to solve, for example, a problem of optimal allocation of boxes with a set of available containers (parcels, pallets, etc. ) in the process of a supply chain. The second problem can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions

Les méthodes intérieures apparaissent depuis peu comme étant utile dans le cadre de la programmation linéaire en nombres entiers. De même, les méta-heuristiques sont apparues afin de permettre la résolution de certains problèmes en nombres entiers. Le travail poursuivi dans cette thèse consiste à présenter les différentes méthodes de programmation linéaire en nombres entiers avant de proposer de les coordonner dans une nouvelle méthode hybride destinée à résoudre des problèmes linéaires en nombres entiers de grande taille et denses. La méthode hybride proposée dans cette thèse combine une méthode intérieure irréalisable, un algorithme génétique et l'exploitation de coupes économiques. La méthode intérieure trouve rapidement des solutions à composantes réelles appelées points d'ancrage. L'algorithme génétique explore le voisinage de ces points d'ancrage afin de trouver des solutions réalisables à composantes entières satisfaisantes. Les coupes permettent de trouver de nouveaux points d'ancrage recentrés situés à l'intérieur de l'espace admissible initial. Cette approche est présentée puis expérimentée sur 50 problèmes différents allant de 50 variables 50 contraintes à 1000 variables 100 contraintes.

Dans cette thèse, nous étudions des Hoist Scheduling Problems (HSP) qui se posent fréquemment dans des lignes automatiques de traitement de surface. Dans ces lignes, des ponts roulants sont utilisés pour transporter les pièces entre les bains. Ainsi, les ponts roulants jouent un rôle essentiel dans la performance de ces lignes ; et un ordonnancement optimal de leurs mouvements est un facteur déterminant pour garantir la qualité des produits et maximiser la productivité. Les lignes que nous étudions comportent un seul pont roulant mais peuvent être des lignes de base ou des lignes étendues (où des bains sont à fonctions et/ou capacités multiples). Nous examinons trois Hoist Scheduling Problems : l’optimisation robuste d’un HSP cyclique, l’ordonnancement dynamique d’une ligne étendue de type job shop et l’ordonnancement cyclique d’une telle ligne.Pour l’optimisation robuste d’un HSP cyclique, nous définissons la robustesse comme la marge dans le temps de déplacement du pont roulant. Nous formulons le problème en programmation linéaire en nombres mixtes à deux objectifs pour optimiser simultanément le temps de cycle et la robustesse. Nous démontrons que le temps de cycle minimal augmente avec la robustesse, et que par conséquent la frontière Pareto est constituée d’une infinité de solutions. Les valeurs minimales et maximales des deux objectifs sont établies. Les résultats expérimentaux à partir de benchmarks et d’instances générées aléatoirement montrent l’efficacité de l’approche proposée.Nous étudions ensuite un problème d’ordonnancement dynamique dans une ligne étendue de type job shop. Nous mettons en évidence une erreur de formulation dans une un modèle existant pour un problème similaire mais sans bains multi-fonctions. Cette erreur peut rendre l’ordonnancement obtenu sous-optimal voire irréalisable. Nous construisons un nouveau modèle qui corrige cette erreur. De plus il est plus compact et s’applique au cas avec des bains à la fois à capacités et à fonctions multiples. Les résultats expérimentaux menés sur des instances avec ou sans bains multi-fonctions montrent que le modèle proposé conduit toujours à une solution optimale et plus efficace que le modèle existant.Nous nous focalisons enfin sur l’ordonnancement cyclique d’une ligne étendue de type job shop avec des bains à fonctions et capacités multiples. Nous construisons un modèle mathématique en formulant les contraintes de capacité du pont roulant, les intervalles des durées opératoires, et les contraintes de capacité des bains. Nous établissons également des contraintes valides. Les expériences réalisées sur des instances générées aléatoirement montrent l’efficacité du modèle proposé
This thesis studies hoist scheduling problems (HSPs) arising in automated electroplating lines. In such lines, hoists are often used for material handing between tanks. These hoists play a crucial role in the performance of the lines and an optimal schedule of the hoist operations is a key factor in guaranteeing product quality and maximizing productivity. We focus on extended lines (i.e. with multi-function and/or multi-capacity tanks) with a single hoist. This research investigates three hoist scheduling problems: robust optimization for cyclic HSP, dynamic jobshop HSP in extended lines and cyclic jobshop HSP in extended lines.We first study the robust optimization for a cyclic HSP. The robustness of a cyclic hoist schedule is defined in terms of the free slacks in hoist traveling times. A bi-objective mixed-integer linear programming (MILP) model is developed to optimize the cycle time and the robustness simultaneously. It is proved that the optimal cycle time strictly increases with the robustness, thus there is an infinite number of Pareto optimal solutions. We established lower and upper bounds of these two objectives. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can effectively solve the problem.We then examine a dynamic jobshop HSP with multifunction and multi-capacity tanks. We demonstrate that an existing model for a similar problem can lead to suboptimality. To deal with this issue, a new MILP model is developed to generate an optimal reschedule. It can handle the case where a multi-function tank is also multi-capacity. Computational results on instances with and without multifunction tanks indicate that the proposed model always yields optimal solutions, and is more compact and effective than the existing one.Finally, we investigate a cyclic jobshop HSP with multifunction and multi-capacity tanks. An MILP model is developed for the problem. The key issue is to formulate the time-window constraints and the tank capacity constraints. We adapt the formulation of time-window constraints for a simpler cyclic HSP to the jobshop case. The tank capacity constraints are handled by dealing with the relationships between hoist moves so that there is always an empty processing slot for new parts. Computational experiments on numerical examples and randomly generated instances indicate that the proposed model can effectively solve the problem

Cette thèse aborde la gestion des ressources humaines dans un centre d'appels. Plus spécifiquement, nous nous intéressons aux problèmes de dimensionnement et de planification. L'objectif sous-jacent est d'assurer la meilleure qualité de service au client (par exemple minimiser le délai d'attente) avec un coût salarial minimum pour l'entreprise. Ces problématiques sont généralement modélisées dans la littérature par le problème de construction de vacation (shift-scheduling problem). Pour appréhender ce problème, nous introduisons le paradigme de chaîne d'activités. Ce paradigme nous permet de représenter la grande diversité des environnements et des contraintes de gestion des ressources humaines dans un centre d'appels. Nous traduisons ensuite ce paradigme en programme linéaire en nombres entiers pour résoudre les problèmes de dimensionnement et de planification. Nous proposons enfin une méthode pour intégrer au programme linéaire en nombres entiers un objectif de qualité de service non linéaire.

Dans ce travail de thèse, nous avons étudié deux types de problèmes d'ordonnancement. La majeure partie concerne le problème d'ordonnancement de projet à moyens limités (RCPSP). Le problème d'ordonnancement des opérations de manutention dans un entrepôt de transbordement ("crossdocking") est également traité avec une moindre importance. Dans une première partie (la plus étendue), nous abordons le RCPSP. À partir de modélisations utilisant la programmation linéaire en nombres entiers, nous avons proposé deux nouvelles formulations de ce problème, utilisant des variables indicées par des événements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le début de l'exécution de chaque activité et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisée. Elle identifie les événements après lesquels l'activité reste en cours ou débute son exécution. De façon générale, comparées à d'autres modèles de la littérature sur divers types d'instances, nos propositions affichent des résultats plus intéressants sur les instances contenant des activités aux durées disparates et associées à de longs horizons d'ordonnancement. En particulier, sur ces mêmes types d'instances mais hautement cumulatives (caractéristiques de base du RCPSP), elles sont également les plus performantes. Nous avons également abordé la résolution d'une extension du RCPSP consistant à prendre en compte des ressources particulières, qui peuvent être consommées en début d'exécution de chaque activité, mais aussi produites à leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison expérimentale entre différents modèles, nous avons proposé une adaptation de nos formulations basées événements, des formulations à temps discret de Pritsker et de Christofides, et de la formulation à temps continu basée sur les flots (proposé par Artigues sur la base des travaux de Balas). Globalement, les résultats mon trent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. Dans la seconde partie (plus réduite), nous avons également proposé un branch-and-bound utilisant des coupes basées sur la frontière de Pareto, pour la résolution du problème d'ordonnancement des opérations de manutention au sein d'un entrepôt de transbordement ("crossdocking"). Les excellents résultats obtenus ont renforcé nos interrogations sur la complexité non-prouvée de ce problème, et ont permis d'établir par la suite que le problème est de complexité polynomiale.

Dans cette thèse, nous traitons le problème de gestion des flux de trafic aérien. Nous présentons un nouveau programme linéaire en nombres entiers qui prend en compte toutes les phases d'un vol. Il prend en compte également le réacheminement des vols. Nous proposons également un algorithme de fourmi «Max-Min». Pour montrer l'efficacité de notre nouvelle formulation et de notre approche, des simulations numériques appliquées à des données réelles sont présentées. Nous traitons également le problème datterrissage d'avions dans le cas statique. Nous proposons une formulation quadratique et nous proposons un changement de variables pour linéariser le modèle. Le deuxième objectif de ce travail est de résoudre effectivement ce modèle. Pour cela, nous proposons une méthode exacte basée sur l'algorithme de séparation et évaluation et un algorithme de colonies de fourmis pour résoudre les instances de grandes tailles. Pour confirmer ce travail, des simulations numériques pour la métaheuristique et la méthode exacte sont présentées
In this thesis, we adress the Air Traffic Flow Management Problem (TFMP). We present a new Integer Linear Program which takes into account all phases of flight. We purpose also a Max-Min ant system algorithm to resolve the TFMP. Numerical simulations are applied to real data to show the effectiveness of our new formulation and our approach. We adress also the static Aircraft Landing Problem (ALP). We propose a quadratic integer program and propose a change of variables to linearize the model. Second objective is to resolve effectivly this model. Therefore, an exact method based on Branch and Bound algorithm is presented. We propose also an Ant Colony System to resolve the instances with a big size. To confirm this work, simulation and computer modeling results for both of the heuristic and exact algorithm are presented

Dans un graphe non orienté, le Problème de Coloration de Graphe (PCG) consiste à assigner à chaque sommet du graphe une couleur de telle sorte qu'aucune paire de sommets adjacents n'aient la même couleur et le nombre total de couleurs est minimisé. DSATUR est un algorithme exact efficace pour résoudre le PCG. Un de ses défauts est qu'une borne inférieure est calculée une seule fois au noeud racine de l'algorithme de branchement, et n'est jamais mise à jour. Notre nouvelle version de DSATUR surpasse l'état de l'art pour un ensemble d'instances aléatoires à haute densité, augmentant significativement la taille des instances résolues. Nous étudions trois formulations PLNE pour le Problème de la Somme Chromatique Minimale (PSCM). Chaque couleur est représentée par un entier naturel. Le PSCM cherche à minimiser la somme des cardinalités des sous-ensembles des sommets recevant la même couleur, pondérés par l'entier correspondant à la couleur, de telle sorte que toute paire de sommets adjacents reçoive des couleurs différentes. Nous nous concentrons sur l'étude d'une formulation étendue et proposons un algorithme de Branch-and-Price
Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR is an effective exact algorithm for the VCP. We introduce new lower bounding techniques enabling the computing of a lower bound at each node of the branching scheme. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of solvable instances. Similar results can be achieved for a subset of high density DIMACS instances. We study three ILP formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. We focus on studying an extended formulation and devise a complete Branch-and-Price algorithm

Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P). Tout d’abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d’une relaxation L&P pour qu’elle coïncide avec celle d’une relaxation SRL*. Nous montrons aussi que toute relaxation S&A s’obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2. Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité. Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d’utiliser des relaxations L&P partielles.