Dissertations / Theses on the topic 'Graphe ordonné'

Nous definissons les ordres de contiguite comme possedant une extension lineaire pour laquelle chaque ensemble de successeurs directs apparait comme un intervalle. Nous etudions cette nouvelle classe d'ordres dont la reconnaissance est lineaire, ainsi que certaines restrictions. Cette classe contient en particulier les ordres d'intervalles et les ordres sans n, ce qui entraine la np-completude de la dimension et du nombre de sauts. Nous montrons que le calcul du nombre d'extensions lineaires de contiguite est p-complet. Concernant les ordres de contiguite de hauteur un, nous prouvons que la dimension est un probleme polynomial. Nous etablissons egalement l'invariance de comparabilite de l'appartenance a la classe des ordres de double contiguite ainsi que la np-completude de la dimension pour les ordres de forte contiguite

Les structures arborescentes (arbres) sont largement étudiées en informatique. Les données semi-structurées en sont un récent champ d'application : il est admis que les arbres ordonnés d'arité non bornée sont un bon modèle pour ces données. Dans certains cas il est intéressant de considérer des arbres non ordonnés. Des formalismes logiques (logiques) sont utilisés pour décrire des requêtes ou vérifier des propriétés sur des données semi-structurées. Il est important d'identifier des logiques représentant un compromis entre expressivité et praticabilité des algorithmes. Des critères pertinents sont la satisfiabilité et la complexité du model checking de la logique. Nous étudions une logique spatiale, LS, qui est à la base d'un langage de requètes pour données semi-structurées modélisées par des arbres non ordonnés. La logique LS est très expressive, incluant des opérateurs spatiaux pour décrire localement la structure d'un arbre, un opérateur de point fixe et permettant de quantifier sur des étiquettes et sur des arbres. Nous établissons des résultats sur la satisfiabilité et la complexité du model checking pour différents fragments de LS. Nous identifions deux fragments syntaxiques de LS à satisfiabilité décidable, montrons que ces fragments sont équivalents aux logiques MSO et PMSO respectivement, et introduisons des classes d'automates d'arbres qui capturent ces deux fragments. Nous montrons que la complexité du mode! checking de LS est dans PSPACE-complet. Si seule la taille de l'arbre est prise en compte, la complexité du model checking va de linéaire à PSP ACE-complet pour les différents fragments de la logique.

La notion d'intervalle dans un graphe, traduit de façon naturelle la notion du segment dans les espaces euclidiens. Par analogie, un ensemble C de sommets est convexe si pour tout couple x, y de sommets de C, l'intervalle entre x et y est inclu dans C. En utilisant la convexité géodésique, Djokovic a caractérisé les graphes isométriquement plongeable dans l'hypercube. Une vingtaine d'années plus tard, Mulder a caractérisé les graphes médians comme des graphes isométriquement plongeable dans l'hypercube et qui sont fermés pour l'opération médian. La comprehension du lien apparent entre ces deux résultats, nous a permis de trouver une nouvelle caractérisation, d'inspiration géométrique, des graphes médians. Cette caractérisation nous a permis à reconnaître les graphes médians qui sont des produits d'arbres ou de chemins. Nous avons donné une caractérisation de ces produits par mineurs convexes exclus. Un autre groupe de résultats concerne des graphes définis naturellement à partir des polyminos. En cherchant le nombre minimum de sommets qui engendrent convexement un tel graphe G, nous avons trouvé que ce nombre est égal au nombre maximum de sommets de degré un d'un arbre obtenu à partir de G par la contraction d'arêtes bien choisies

La propriete de projection a ete introduite par ernest corominas pour les ensembles ordonnes : un ensemble ordonne est 2-projectif si les projections sont ses seules operations binaires, croissantes et identiques sur la diagonale. L'objet de cette these est l'etude d'extensions de cette notion, a des operations d'arite superieure (projectivite de hamming finie et projectivite cartesienne infinie) et a des structures plus generales. Notre etude des proprietes de projection de hamming (relatives a des operations regulieres par rapport a chaque argument) est fondee sur des idees de topologie algebrique de base. Nous introduisons divers complexes de chaines, dont les proprietes nous fournissent des criteres de projectivite. Ainsi, nous etablissons par exemple, qu'un graphe fini, connexe, sans sommet pendant, est hamming 2-projectif des qu'il n'a ni triangle ni carre, et plus generalement pour n>2, qu'il est hamming n-projectif, quand il n'a pas cycle de longueur inferieure ou egale a n + 1 et qu'il n'est pas lui-meme un cycle. En particulier, cela fournit les premiers exemples de graphes verifiant la propriete de 3-projection de hamming. Notre point de vue va egalement nous permettre d'introduire les proprietes de n-projection simple et double. Notre approche des proprietes de projection infinies (relatives a des operations infinitaires) est de nature plus ensembliste. Nous montrons en particulier, qu'un graphe projectif de diametre fini est denombrablement projectif, des qu'il n'est pas compact pour les systemes atomiques a un nombre fini d'inconnues. Cette these est partagee en sept chapitres regroupes en trois parties. La premiere est consacree a l'expose de generalites. Nous y etablissons egalement la projectivite de certaines structures homogenes, qui nous permettront d'illustrer la suite de notre propos. Dans une seconde partie, nous mettons en place un cadre algebrique pour l'etude des proprietes de projection de hamming. Dans la troisieme, nous etudions des proprietes de projection infinie, que nous illustrons notamment par les exemples des shift-graphs et des structures homogenes.

Le travail présenté dans cette thèse concerne d'une part, l'étude qualitative d'ensembles et d'autre part, celui de l'étude de la stabilité d'un système dynamique. Les méthodes numériques proposées combinent le calcul par intervalles et la théorie des graphes.<br /><br />De nombreux problèmes, comme l'étude de l'espace des configurations d'un robot, se ramènent à une étude qualitative d'ensembles. Ici, la ``taille'' de l'ensemble importe peu, ce qui compte, c'est sa ``topologie''. Les méthodes proposées calculent des invariants topologiques d'ensembles. Les ensembles considérés sont décrits à l'aide d'inégalités $\mathcal{C}^{\infty}$. L'idée maîtresse est de décomposer un ensemble donné en parties contractiles et d'utiliser l'homologie de \v Cech.<br /><br />La seconde partie de la thèse concerne l'étude de point<br />asymptotiquement stables des systèmes dynamiques (linéaires ou non). Plus largement, on propose une méthode pour approcher le bassin d'attraction d'un point asymptotiquement stable. Dans un premier temps, on utilise la théorie de Lyapunov et le calcul par intervalle<br />pour trouver effectivement un voisinage inclus dans le bassin d'attraction d'un point prouvé asymptotiquement stable. Puis, on combine, une fois de plus, la théorie des graphes et les méthodes d'intégration d'équations différentielles ordinaires pour améliorer ce voisinage et ainsi construire un ensemble inclus dans le bassin<br />d'attraction de ce point.

Nos travaux se situent dans le cadre de l'analyse conceptuelle des donnees. Notre objectif est de generaliser les representations par variables binaires ou nominales en y adjoignant la modelisation de structures internes. Le probleme est de ne pas perdre en complexite algorithmique ce qui est gagne en puissance de representation. Selon ces considerations, decrire les donnees et les classes de donnees par des structures arborescentes est un bon compromis. Le systeme de representation que nous proposons s'appuie sur un modele algebrique: les magmas. Il permet de construire des termes assimilables a des arborescences finies, etiquetees et typees. Leur interpretation est intuitive et ils autorisent les descriptions recursives. Une relation d'ordre naturel, la generalisation, induit un treillis sur les termes. Nous etudions ce treillis et montrons qu'il possede des proprietes proches de celles d'un treillis booleen. En particulier, nous montrons que l'on peut construire un treillis de galois mettant en correspondance des ensembles d'objets et leur description par des termes

L'algorithmique des ensembles ordonnes occupe une place grandissante en informatique. Elle est etudiee ici sous divers aspects: - etude de la complexite concrete d'algorithmes de fermeture et reduction transitive de graphes sans circuit dans des cas particuliers; - etude du probleme de la dimension des ordres d'intervalles: trois nouvelles bornes sont obtenues ainsi qu'un encadrement a deux pres par le nombre chromatique d'un diagramme associe. Etude du nombre chromatique des diagrammes sur des classes particulieres. - modelisation a l'aide d'ensembles ordonnes de systemes distribues et utilisation du modele pour l'etude de mesures de concurrence; - etude des extensions d'intervalle minimales d'un ensemble ordonne. Caracterisation. Invariance de comparabilite. Algorithmes de generation

Considérons les systèmes à évènements discrets qui sont modélisables par des réseaux de Pétri du type "graphes d'évènements temporisés", Ils ont un comportement optimal (fonctionnement au plus tôt) qui peut-être calculé sans simulation par un système dynamique qui est linéaire dans l'algèbre des dïodes (max,+) ou (min,+). Le comportement asymptotique d'un tel système à évènements discrets est cyclique et les caractéristiques de ce cycle (période, délai, motif) sont analysables par un calcul de valeur propre sur la matrice de dynamique. À partir de cette formulation linéaire, une représentation externe (fonction de transfert) peut-être obtenue grâce à un calcul formel sur des séries à coefficients dans les dïodes, la fonction de transfert d'un tel système est rationnelle au sens des dïoides et est factorisable en une expression finie de polynômes.

Les grammaires attribuées offrent un formalisme très adapté à la détection du parallélisme et à la parallélisation. Les graphes de dépendances associés à chaque production correspondent en effet à des graphes de flot de contrôle. Grâce aux grammaires attribuées (\it l)-ordonnées, il est possible de calculer statiquement un ordre total sur les attributs des non-terminaux qui soit compatible avec l'ordre partiel induit par les graphes de dépendances, ce qui évite grand nombre de synchronisations dynamiques. Toutefois, il apparaît que le parallélisme inhérent à ces graphes est beaucoup trop important en pratique pour supporter une parallélisation complète. Notre but a été de montrer qu'il est possible de sélectionner le parallélisme pour obtenir une parallélisation efficace en pratique. Pour cela, l'évaluateur parallèle a été implanté dans un système réel de traitement des grammaires attribuées qu'est le système (\sc FNC-2) et porté sur plusieurs plateformes (KSR1, Multimax et Sequent). Plusieurs types d'implantations ont été effectués afin d'étudier l'influence de la méthode d'évaluation sur la parallélisation. Les méthodes que nous avons utilisées s'appliquent à des architectures à mémoire partagée. Sur les machines testées, les résultats obtenus sont très encourageants malgré l'absence d'utilisation de caractéristiques propres à chaque machine. Un deuxième problème soulevé par le parallélisme est l'explosion mémoire qui a lieu pendant l'évaluation. En séquentiel, cette consommation a été largement limitée par l'utilisation d'un optimiseur mémoire qui permet le partage des instances d'attributs en dehors de l'arbre. Deux structures sont utilisées\,: la variable globale et la pile. Nous avons proposé une méthode pour étendre cette optimisation mémoire au cas parallèle ce qui permet d'une part de sortir les attributs de l'arbre même en parallèle et d'autre part d'éliminer de nombreuses règles de copie.

L'optimisation combinatoire est un domaine des mathématiques dans lequel un problème consiste à trouver une solution optimale dans un ensemble fini d'objets. Elle a des applications cruciales dans de nombreux domaines. Le branch-and-cut est l'un des algorithmes les plus utilisés pour résoudre exactement des problèmes d'optimisation combinatoire. Dans cette thèse, nous nous concentrons sur les aspects informatiques du branch-and-cut et plus particulièrement, sur deux aspects importants de l'optimisation combinatoire: l'équité des solutions et l'intégration de l'apprentissage automatique. Dans la partie I, nous étudions deux approches courantes pour traiter la question de l'équité dans l'optimisation combinatoire, qui a fait l'objet d'une attention particulière au cours des dernières décennies. La première approche est l'optimisation combinatoire équilibrée, qui trouve une solution équitable en minimisant la différence entre les plus grands et les plus petits composants utilisés. En raison des difficultés à délimiter ces composants, aucun cadre général exact basé sur la programmation linéaire en nombres entiers mixtes (MILP) n'a été proposé pour l'optimisation combinatoire équilibrée. Pour combler cette lacune, nous présentons au chapitre 3 une nouvelle classe de plans de coupe locaux adaptés aux problèmes d'optimisation combinatoire équilibrée pour l'algorithme du branch-and-cut. Nous démontrons l'efficacité de la méthode proposée dans la cadre du problème du voyageur de commerce équilibré. Notamment, nous introduisons des algorithmes pour trouver des bornes et des mécanismes pour la détermination des variables afin d'accélérer un peu plus les performances. Une deuxième approche pour traiter l'équité est l'optimisation combinatoire Ordered Weighted Average (OWA), qui utilise l'opérateur OWA dans la fonction objectif. En raison de l'opérateur d'ordonnancement, l'optimisation combinatoire OWA est non linéaire, même si ses contraintes d'origine sont linéaires. Deux formulations MILP de tailles différentes ont été introduites dans la littérature pour linéariser l'opérateur OWA. Cependant, la formulation la plus performante pour l'optimisation combinatoire OWA reste incertaine, car l'intégration des méthodes de linéarisation peut introduire des difficultés supplémentaires. Dans le chapitre 4, nous fournissons des comparaisons théoriques et empiriques des deux formulations MILP pour l'optimisation combinatoire OWA. En particulier, nous prouvons que les formulations sont équivalentes en termes de relaxation de programmation linéaire. Nous montrons empiriquement que pour les problèmes d'optimisation combinatoire OWA, la formulation avec le plus de variables peut être résolue plus rapidement avec le branch-and-cut. Dans la partie II, nous développons des méthodes d'application de l'apprentissage automatique pour améliorer les problèmes de décision fondamentaux du branch-and-cut, en mettant l'accent sur la génération de coupes. Ce dernier problème se réfère à la décision de générer des coupes ou des branches à chaque nœud de l'arbre de recherche. Nous démontrons empiriquement que cette décision a un impact significatif sur les performances du branch-and-cut, en particulier pour les coupes combinatoires qui exploitent les faces de la coque convexe des solutions réalisables. Nous proposons ensuite un cadre général combinant l'apprentissage supervisé et l'apprentissage par renforcement afin d'apprendre des stratégies efficaces pour générer des coupes combinatoires dans la méthode branch-and-cut. Notre cadre comporte deux composantes : un détecteur de coupes pour prédire l'existence de coupes et un évaluateur de coupes pour choisir entre la génération de coupes et le branchement. Enfin, nous fournissons des résultats expérimentaux montrant que la méthode proposée est plus performante que les stratégies couramment utilisées pour la génération de coupes, même sur des instances plus grandes que celles utilisées pour l'apprentissage<br>Combinatorial optimization is a field of mathematics that searches for an optimal solution in a finite set of objects. It has crucial applications in many fields, including applied mathematics, software engineering, theoretical computer science, and machine learning. extit{Branch-and-cut} is one of the most widely-used algorithms for solving combinatorial optimization problems exactly. In this thesis, we focus on the computational aspects of branch-and-cut when studying two critical dimensions of combinatorial optimization: extit{the fairness of solutions} and extit{the integration of machine learning}.In Partef{part:1} (Chaptersef{chap:bnc-btsp} andef{chap:owa}), we study two common approaches to deal with the issue of fairness in combinatorial optimization, which has gained significant attention in the past decades. The first approach is extit{balanced combinatorial optimization}, which finds a fair solution by minimizing the difference between the largest and smallest components used. Due to the difficulties in bounding these components, to the best of our knowledge, no general exact framework based on mixed-integer linear programming (MILP) has been proposed for balanced combinatorial optimization. To address this gap, in Chapteref{chap:bnc-btsp}, we present a branch-and-cut algorithm and a novel class of local cutting planes tailored for balanced combinatorial optimization problems. We demonstrate the effectiveness of the proposed framework in the Balanced Traveling Salesman Problem. Additionally, we introduce bounding algorithms and mechanisms to fix variables to accelerate performance further.The second approach to handling the issue of fairness is extit{Ordered Weighted Average (OWA) combinatorial optimization}, which integrates the OWA operator into the objective function. Due to the ordering operator, OWA combinatorial optimization is nonlinear, even if its original constraints are linear. Two MILP formulations of different sizes have been introduced in the literature to linearize the OWA operator. However, which formulation performs best for OWA combinatorial optimization remains uncertain, as integrating the linearization methods may introduce additional difficulties. In Chapteref{chap:owa}, we provide theoretical and empirical comparisons of the two MILP formulations for OWA combinatorial optimization. In particular, we prove that the formulations are equivalent in terms of the linear programming relaxation. We empirically show that for OWA combinatorial optimization problems, the formulation with more variables can be solved faster with branch-and-cut.In Partef{part:2} (Chapteref{chap:mlbnc}), we develop methods for applying machine learning to enhance fundamental decision problems in branch-and-cut, with a focus on cut generation. Cut generation refers to the decision of whether to generate cuts or to branch at each node of the search tree. We empirically demonstrate that this decision significantly impacts branch-and-cut performance, especially for combinatorial cuts that exploit the facial structure of the convex hull of feasible solutions. We then propose a general framework combining supervised and reinforcement learning to learn effective strategies for generating combinatorial cuts in branch-and-cut. Our framework has two components: a cut detector to predict cut existence and a cut evaluator to choose between generating cuts and branching. Finally, we provide experimental results showing that the proposed method outperforms commonly used strategies for cut generation, even on instances larger than those used for training