Academic literature on the topic 'Contraintes de cardinalité'

Les contraintes arithmétiques sont largement utilisées dans les langages formels comme les expressions, les grammaires d'arbres et les chemins réguliers. Ces contraintes sont utilisées dans les modéles de contenu des types (XML Schemas) pour imposer des bornes sur le nombre d'occurrences de nœuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les nœuds ayant un nombre limité de nœuds accessibles par une expression de chemin donnée. Les types et chemins étendus avec les contraintes de comptage constituent le prolongement naturel de leurs homologues sans comptage déjà considérés comme des constructions fondamentales dans les langages de programmation et les systèmes de type pour XML. Un des défis majeurs en programmation XML consiste à développer des techniques automatisées permettant d'assurer statiquement un typage correct et des optimisations de programmes manipulant les données XML. À cette fin, il est nécessaire de résoudre certaines tâches de raisonnement qui impliquent des constructions telles que les types et les expressions XPath avec des contraintes de comptage. Dans un futur proche, les compilateurs de programmes XML devront résoudre des problèmes de base tels que le sous-typage afin de s'assurer au moment de la compilation qu'un programme ne pourra jamais générer de documents non valides à l'exécution. Cette thèse étudie les logiques capables d'exprimer des contraintes de comptage sur les structures d'arbres. Il a été montré récemment que le mu-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les nœuds successeurs immédiats est indécidable. Dans cette thèse, nous montrons que, sur les arbres finis, la logique avec contraintes de comptage est décidable en temps exponentiel. En outre, cette logique fournit des opérateurs de comptage selon des chemins plus généraux. En effet, la logique peut exprimer des contraintes numériques sur le nombre de nœuds descendants ou même ascendants. Nous présentons également des traductions linéaires d'expressions XPath et de types XML comportant des contraintes de comptage dans la logique.

Les contraintes arithmétiques sont largement utilisées dans les langages formels comme les expressions, les grammaires d'arbres et les chemins réguliers. Ces contraintes sont utilisées dans les modèles de contenu des types (XML Schemas) pour imposer des bornes sur le nombre d'occurrences de noeuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les noeuds ayant un nombre limité de noeuds accessibles par une expression de chemin donnée. Les types et chemins étendus avec les contraintes de comptage constituent le prolongement naturel de leurs homologues sans comptage déjà considérés comme des constructions fondamentales dans les langages de programmation et les systèmes de type pour XML. Un des défis majeurs en programmation XML consiste à développer des techniques automatisées permettant d'assurer statiquement un typage correct et des optimisations de programmes manipulant les données XML. À cette fin, il est nécessaire de résoudre certaines tâches de raisonnement qui impliquent des constructions telles que les types et les expressions XPath avec des contraintes de comptage. Dans un futur proche, les compilateurs de programmes XML devront résoudre des problèmes de base tels que le sous-typage afin de s'assurer au moment de la compilation qu'un programme ne pourra jamais générer de documents non valides à l'exécution. Cette thèse étudie les logiques capables d'exprimer des contraintes de comptage sur les structures d'arbres. Il a été montré récemment que le μ-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les noeuds successeurs immédiats est indécidable. Dans cette thèse, nous montrons que, sur les arbres finis, la logique avec contraintes de comptage est décidable en temps exponentiel. En outre, cette logique fournit des opérateurs de comptage selon des chemins plus généraux. En effet, la logique peut exprimer des contraintes numériques sur le nombre de noeuds descendants ou même ascendants. Nous présentons également des traductions linéaires d'expressions XPath et de types XML comportant des contraintes de comptage dans la logique.

La richesse de la programmation par contraintes repose sur la très large variété des algorithmes qu’elle utilise en puisant dans les grands domaines de l’Intelligence Artificielle, de la Programmation Logique et de la Recherche Opérationnelle. Cependant, cette richesse, qui offre aux spécialistes une palette quasi-illimitée de configurations possibles pour attaquer des problèmes combinatoires, devient une frein à la diffusion plus large du paradigme, car les outils actuels sont très loin d’une boîte noire, et leur utilisation suppose une bonne connaissance du domaine, notamment en ce qui concerne leur paramétrage. Dans cette thèse, nous proposons d’analyser le comportement des contraintes de cardinalité avec des modèles probabilistes et des outils de dénombrement, pour paramétrer automatiquement les solveurs de contraintes : heuristiques de choix de variables et de choix de valeurs et stratégies de recherche
The main asset of constraint programming is its wide variety of algorithms that comes from the major areas of artificial intelligence, logic programming and operational research. It offers specialists a limitless range of possible configurations to tackle combinatorial problems, but it becomes an obstacle to the wider diffusion of the paradigm. The current tools are very far from being used as a black-box tool, and it assumes a good knowledge of the field, in particular regarding the parametrization of solvers.In this thesis, we propose to analyze the behavior of cardinality constraints with probabilistic models and counting tools, to automatically parameterize constraint solvers: heuristics of choice of variables and choice of values and search strategies

Les travaux présentés dans cette thèse concernent les nouvelles techniques d'optimisation pour la résolution de certains problèmes importants issus de finance. Il s'agit des problèmes d'optimisation non convexe de grande dimension pour lesquels la recherche des bonnes méthodes de résolution est toujours d'actualité. Notre travail s'appuie principalement sur la programmation DC (Différence de fonctions Convexes) et DCA (DC Algorithmes). Cette démarche est motivée par la robustesse et la performance de la programmation DC et DCA comparée aux autres méthodes. La thèse est divisée en deux parties et est composée de sept chapitres. Dans la première partie intitulée ¡Méthodologie¡ nous présentons des outils théoriques et algorithmiques servant des références aux autres. Le premier chapitre concerne la programmation DC et DCA tandis que le deuxième porte sur les algorithmes par séparation et évaluation. Dans la deuxième partie nous développons la programmation DC et DCA pour la résolution des problèmes en finance. Nous commençons par une introduction à la gestion de portefeuille (le Chapitre 3). Le Chapitre 4 est dédié aux généralisations du modèle moyenne-variance (MV) de Markowitz, où nous étudions le modèle MV sous les contraintes de seuil d'achat, de seuil et de cardinalité. Le Chapitre 5 est consacré à la mesure de risque de baisse et les contraintes de cardinalité. Le Chapitre 6 porte sur le problème de choix de portefeuille avec les fonctions des coûts de transaction en escalier. L'investissement robuste en gestion de portefeuille sous les contraintes de cardinalité est développé dans le dernier chapitre
The topics presented in this thesis are related to new optimization techniques for solving some challenging problems resulting from finance. They are large-scale non convex optimization problems for which finding efficient solving methods is currently the topic of numerous researches. Our work is based mainly on DC (Difference of Convex functions) programming and DCA (DC Algorithm). This approach is motivated by the robustness and efficiency of DC programming and DCA approaches in comparison to the other methods. The thesis is divided into two parts and consists of seven chapters. In the first part entitled Methodology ; we present theoretical tools and algorithms that we are going to use in the thesis. The first chapter is about DC programming and DCA and the second focuses on branch and bound algorithms. In the second part we develop DC programming and DCA for solving some problems in finance. We begin with an introduction to the modern portfolio theory (The Chapter 3). The Chapter 4 is dedicated to the generalizations of the mean variance (MV) model of Markowitz, where we study the MV model under the buy-in threshold constraints, threshold constraints, and cardinality constraints. The Chapter 5 is devoted to the portfolio selection problem under downside risk measure and cardinality constraints. The Chapter 6 deals with the portfolio optimization under step increasing transaction costs functions. Finally, the robust investment strategies with discrete asset choice constraints are developed in the last chapter

Dans ce travail de thèse, nous développons et appliquons des techniques d'optimisation dans la conception et la gestion de l'énergie. Tout d'abord, nous nous concentrons sur l'optimisation bi-niveaux et développons une nouvelle analyse théorique pour les jeux à un seul meneur et plusieurs suiveurs avec des contraintes de cardinalité. Cette analyse est ensuite appliquée à la localisation optimale des stations de recharge pour véhicules électriques. La deuxième partie est consacrée à l'optimisation économique, à long terme et à court terme, des centrales solaires à concentration. Une approche innovante d'optimisation globale combinant la conception optimale du stockage et l'exploitation optimale dans un contexte de marché est développée. Ensuite, dans un perspective à court terme, le contrôle optimal de la production d'énergie d'une centrale solaire est analysé
In this thesis work, we develop and apply optimization techniques in energy design and management. First we focus on bilevel optimization and developed new theoretical analysis for single-leader-multi-follower games with cardinality constraints. It is then applied to optimal location of charging stations for electric vehicles. The second part is dedicated to economic optimization of solar power plants from a long term as well as from a short term perspective. Innovating global optimization approach mixing optimal design of storage and optimal operation in a market context is developed. Then at a short term scale, the optimal control of energy production of a solar power plant is analysed
En este trabajo de tesis, desarrollamos y aplicamos técnicas de optimización en el dise˜no y gestión de energía. En primer lugar, nos enfocamos en la optimización binivel y desarrollamos nuevo análisis teórico para single-leader-multi-follower games con restricciones de cardinalidad. Luego, se aplica a la localización óptima de estaciones de carga por vehículos eléctricos. La segunda parte está dedicada a la optimización económica de plantas solares desde una perspectiva a largo plazo, así como desde una perspectiva a corto plazo. Se desarrolla un enfoque innovador de optimización global que combina el dise˜no óptimo de almacenamiento y la operación óptima en un contexto de mercado. Luego, a escala a corto plazo, se analiza el control óptimo de la producción de energía de una planta solar

Les travaux présentés dans cette thèse concernent les nouvelles techniques d'optimisation pour la résolution de certains problèmes importants issus de finance. Il s'agit des problèmes d'optimisation non convexe de grande dimension pour lesquels la recherche des bonnes méthodes de résolution est toujours d'actualité. Notre travail s'appuie principalement sur la programmation DC (Différence de fonctions Convexes) et DCA (DC Algorithmes). Cette démarche est motivée par la robustesse et la performance de la programmation DC et DCA comparée aux autres méthodes. La thèse est divisée en deux parties et est composée de sept chapitres. Dans la première partie intitulée ¡Méthodologie¡ nous présentons des outils théoriques et algorithmiques servant des références aux autres. Le premier chapitre concerne la programmation DC et DCA tandis que le deuxième porte sur les algorithmes par séparation et évaluation. Dans la deuxième partie nous développons la programmation DC et DCA pour la résolution des problèmes en finance. Nous commençons par une introduction à la gestion de portefeuille (le Chapitre 3). Le Chapitre 4 est dédié aux généralisations du modèle moyenne-variance (MV) de Markowitz, où nous étudions le modèle MV sous les contraintes de seuil d'achat, de seuil et de cardinalité. Le Chapitre 5 est consacré à la mesure de risque de baisse et les contraintes de cardinalité. Le Chapitre 6 porte sur le problème de choix de portefeuille avec les fonctions des coûts de transaction en escalier. L'investissement robuste en gestion de portefeuille sous les contraintes de cardinalité est développé dans le dernier chapitre
The topics presented in this thesis are related to new optimization techniques for solving some challenging problems resulting from finance. They are large-scale non convex optimization problems for which finding efficient solving methods is currently the topic of numerous researches. Our work is based mainly on DC (Difference of Convex functions) programming and DCA (DC Algorithm). This approach is motivated by the robustness and efficiency of DC programming and DCA approaches in comparison to the other methods. The thesis is divided into two parts and consists of seven chapters. In the first part entitled Methodology ; we present theoretical tools and algorithms that we are going to use in the thesis. The first chapter is about DC programming and DCA and the second focuses on branch and bound algorithms. In the second part we develop DC programming and DCA for solving some problems in finance. We begin with an introduction to the modern portfolio theory (The Chapter 3). The Chapter 4 is dedicated to the generalizations of the mean variance (MV) model of Markowitz, where we study the MV model under the buy-in threshold constraints, threshold constraints, and cardinality constraints. The Chapter 5 is devoted to the portfolio selection problem under downside risk measure and cardinality constraints. The Chapter 6 deals with the portfolio optimization under step increasing transaction costs functions. Finally, the robust investment strategies with discrete asset choice constraints are developed in the last chapter

Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.

Pseudo-Boolean and cardinality constraints are a natural generalization of clauses. While a clause expresses that at least one literal must be true, a cardinality constraint expresses that at least n literals must be true and a pseudo-Boolean constraint states that a weighted sum of literals must be greater than a constant. These contraints have a high expressive power, have been intensively studied in 0/1 programming and are close enough to the satisfiability problem to benefit from the recents advances in this field. Besides, optimization problems are naturally expressed in the pseudo-Boolean context. This chapter presents the inference rules on pseudo-Boolean constraints and demonstrates their increased inference power in comparison with resolution. It also shows how the modern satisfiability algorithms can be extended to deal with pseudo-Boolean constraints.