This dissertation addresses the development of enhanced formulations for minimax and mixed-integer programming models for certain industrial and logistical systems, along with the design and implementation of efficient algorithmic strategies. We first examine the general class of minimax mixed-integer 0-1 problems of the type that frequently arise in decomposition approaches and in a variety of location and scheduling problems. We conduct an extensive polyhedral analysis of this problem in order to tighten its representation using the Reformulation-Linearization/Convexification Technique (RLT), and demonstrate the benefits of the resulting lifted formulations for several classes of problems. Specifically, we investigate RLT-enhanced Lagrangian dual formulations for the class of minimax mixed-integer 0-1 problems in concert with deflected/conjugate subgradient algorithms. In addition, we propose two general purpose lifting mechanisms for tightening the mathematical programming formulations associated with such minimax optimization problems. Next, we explore novel continuous nonconvex as well as lifted discrete formulations for the notoriously challenging class of job-shop scheduling problems with the objective of minimizing the maximum completion time (i.e., minimizing the makespan). In particular, we develop an RLT-enhanced continuous nonconvex model for the job-shop problem based on a quadratic formulation of the job sequencing constraints on machines. The tight linear programming relaxation that is induced by this formulation is then embedded in a globally convergent branch-and-bound algorithm. Furthermore, we design another novel formulation for the job-shop scheduling problem that possesses a tight continuous relaxation, where the non-overlapping job sequencing constraints on machines are modeled via a lifted asymmetric traveling salesman problem (ATSP) construct, and specific sets of valid inequalities and RLT-based enhancements are incorporated to further tighten the resulting mathematical program. The efficacy of our enhanced models is demonstrated by an extensive computational experiment using classical benchmark problems from the literature. Our results reveal that the LP relaxations produced by the lifted ATSP-based models provide very tight lower bounds, and directly yield a 0\% optimality gap for many benchmark problems, thereby substantially dominating other alternative mixed-integer programming models available for this class of problems. Notably, our lifted ATSP-based formulation produced a 0\% optimality gap via the root node LP relaxation for 50\% of the classical problem instances due to Lawrence. We also investigate enhanced model formulations and specialized, efficient solution methodologies for applications arising in four particular industrial and sports scheduling settings. The first of these was posed to us by a major trucking company (Volvo Logistics North America), and concerns an integrated assembly and routing problem, which is a unique study of its kind in the literature. In this context, we examine the general class of logistical systems where it is desirable to appropriately ascertain the joint composition of the sequences of vehicles that are to be physically connected along with determining their delivery routes. Such assembly-routing problems occur in the truck manufacturing industry where different models of vehicles designed for a network of customers need to be composed into compatible groups (assemblies) and subsequently dispatched via appropriately optimized delivery routes that are restricted by the particular sequence in which the trucks are connected. A similar structure is exhibited in the business of shipping goods via boat-towed barges along inland waterways, or via trains through railroad networks. We present a novel modeling framework and column generation-based optimization approach for this challenging class of joint vehicle assembly-routing problems. In addition, we suggest several extensions to accommodate particular industrial restrictions where assembly sequence-dependent delivery routes are necessary, as well as those where limited driver- and equipment-related resources are available. Computational experience is provided using large-scale realistic data to demonstrate the applicability of our suggested methodology in practice. The second application addressed pertains to a production planning problem faced by a major motorcycle manufacturing firm (Harley-Davidson Motor Company). We consider the problem of partitioning and sequencing the production of different manufactured items in mixed-model assembly lines, where each model has various specific options and designated destinations. We propose a mixed-integer programming formulation (MPSP1) for this problem that sequences the manufactured goods within production batches in order to balance the motorcycle model and destination outputs as well as the load demands on material and labor resources. An alternative (relaxed) formulation (MPSP2) is also presented to model a closely related case where all production decisions and outputs are monitored within a common sequence of batches, which permits an enhanced tighter representation via an additional set of hierarchical symmetry-defeating constraints that impart specific identities amongst batches of products under composition. The latter model inspires a third set partitioning-based formulation in concert with an efficient column generation approach that directly achieves the joint partitioning of jobs into batches along with ascertaining the sequence of jobs within each composed batch. Finally, we investigate a subgradient-based optimization strategy that exploits a non-differentiable optimization formulation, which is prompted by the flexibility in the production process as reflected in the model via several soft-constraints, thereby providing a real-time decision-making tool. Computational experience is presented to demonstrate the relative effectiveness of the different proposed formulations and the associated optimization strategies for solving a set of realistic problem instances. The third application pertains to the problem of matching or assigning subassembly parts in assembly lines, where we seek to minimize the total deviation of the resulting final assemblies from a vector of nominal and mean quality characteristic values. We introduce three symmetry-defeating enhancements for an existing assignment-based model, and highlight the critical importance of using particular types of symmetry-defeating hierarchical constraints that preserve the model structure. We also develop an alternative set partitioning-based formulation in concert with a column generation approach that efficiently exploits the structure of the problem. A special complementary column generation feature is proposed, and we provide insights into its vital role for the proposed column generation strategy, as well as highlight its benefits in the broader context of set partitioning-based formulations that are characterized by columns having relatively dense non-zero values. In addition, we develop several heuristic procedures. Computational experience is presented to demonstrate the relative effectiveness of the different adopted strategies for solving a set of realistic problem instances. Finally, we analyze a doubles tennis scheduling problem in the context of a training tournament as prompted by a tennis club in Virginia, and develop two alternative 0-1 mixed-integer programming models, each with three different objective functions that attempt to balance the partnership and the opponentship pairings among the players. Our analysis and computational experience demonstrate the superiority of one of these models over the other, and reflect the importance of model structure in formulating discrete optimization problems. Furthermore, we design effective symmetry-defeating strategies that impose certain decision hierarchies within the models, which serve to significantly enhance algorithmic performance. In particular, our study provides the insight that the special structure of the mathematical program to which specific tailored symmetry-defeating constraints are appended can greatly influence their pruning effect. We also propose a novel nonpreemptive multi-objective programming strategy in concert with decision hierarchies, and highlight its effectiveness and conceptual value in enhancing problem solvability. Finally, four specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems. Aside from the development of specialized effective models and algorithms for particular interesting and challenging applications arising in different assembly, routing, and scheduling contexts, this dissertation makes several broader contributions that emerge from the foregoing studies, which are generally applicable to solving formidable combinatorial optimization problems. First, we have shown that it is of utmost importance to enforce symmetry-defeating constraints that preserve the structure of mathematical programs to which they are adjoined, so that their pruning effects are most efficiently coupled with the branch-and-bound strategies that are orchestrated within mathematical programming software packages. In addition, our work provides the insight that the concept of symmetry compatible formulations plays a crucial role in the effectiveness of implementing any particular symmetry-defeating constraints. In essence, if the root node LP solution of the original formulation does not conform relatively well with the proposed symmetry-defeating hierarchical constraints, then a significant branching effort might be required to identify a good solution that is compatible with the pattern induced by the selected symmetry-defeating constraints. Therefore, it is advisable to enforce decision hierarchies that conform as much as possible with the problem structure as well as with the initial LP relaxation. Second, we have introduced an alternative concept for defeating symmetry via augmented objective functions. This concept prompts the incorporation of objective perturbation terms that discriminate amongst subsets of originally undistinguishable solution structures and, in particular, leads to the development of a nonpreemptive multiobjective programming approach based on, and combined with, symmetry-defeating constraints. Interestingly, nonpreemptive multiobjective programming approaches that accommodate symmetry-defeating hierarchical objective terms induce a root node solution that is compatible with the imposed symmetry-defeating constraints, and hence affords an automated alternative to the aforementioned concept of symmetry compatible formulations. Third, we have proposed a new idea of complementary column generation in the context of column generation approaches that generally provide a versatile framework for analyzing industrial-related, integrated problems that involve the joint optimization of multiple operational decisions, such as assembly and routing, or partitioning and scheduling. In such situations, we have reinforced the insight that assignment-related problems that involve collections of objects (production batches, final assemblies, etc.) whose permutation yields equivalent symmetric solutions may be judiciously formulated as set partitioning models. The latter can then be effectively tackled via column generation approaches, thereby implicitly obviating the foregoing combinatorial symmetric reflections through the dynamic generation of attractive patterns or columns. The complementary column generation feature we have proposed and investigated in this dissertation proves to be particularly valuable for such set partitioning formulations that involve columns having relatively dense non-zero values. The incorporation of this feature guarantees that every LP iteration (involving the solution of a restricted master program and its associated subproblem) systematically produces a consistent set of columns that collectively qualify as a feasible solution to the problem under consideration. Upon solving the problem to optimality as a linear program, the resultant formulation encompasses multiple feasible solutions that generally include optimal or near-optimal solutions to the original integer-restricted set partitioning formulation, thereby yielding a useful representation for designing heuristic methods as well as exact branch-and-price algorithms. In addition, using duality theory and considering set partitioning problems where the number of patterns needed to collectively compose a feasible solution is bounded, we have derived a lower bound on the objective value that is updated at every LP phase iteration. By virtue of this sequence of lower bounds and the availability of upper bounds via the restricted master program at every LP phase iteration, the LP relaxation of the set partitioning problem is efficiently solved as using a pre-specified optimality tolerance. This yields enhanced algorithmic performance due to early termination strategies that successfully mitigate the tailing-off effect that is commonly witnessed for simplex-based column generation approaches. / Ph. D.

In formulating discrete optimization problems, it is not only important to have a correct mathematical model, but to have a well structured model that can be solved effectively. Two important characteristics of a general integer or mixed-integer program are its size (the number of constraints and variables in the problem), and its strength or tightness (a measure of how well it approximates the convex hull of feasible solutions). In designing model formulations, it is critical to ensure a proper balance between compactness of the representation and the tightness of its linear relaxation, in order to enhance its solvability. In this dissertation, we consider these issues pertaining to the modeling of mixed-integer 0-1 programming problems in general, as well as in the context of several specific real-world applications, including a telecommunications network design problem and an airspace management problem. We first consider the Reformulation-Linearization Technique (RLT) of Sherali and Adams and explore the generation of reduced first-level representations for mixed-integer 0-1 programs that tend to retain the strength of the full first-level linear programming relaxation. The motivation for this study is provided by the computational success of the first-level RLT representation (in full or partial form) experienced by several researchers working on various classes of problems. We show that there exists a first-level representation having only about half the RLT constraints that yields the same lower bound value via its relaxation. Accordingly, we attempt to a priori predict the form of this representation and identify many special cases for which this prediction is accurate. However, using various counter-examples, we show that this prediction as well as several variants of it are not accurate in general, even for the case of a single binary variable. Since the full first-level relaxation produces the convex hull representation for the case of a single binary variable, we investigate whether this is the case with respect to the reduced first-level relaxation as well, and show similarly that it holds true only for some special cases. Empirical results on the prediction capability of the reduced, versus the full, first-level representation demonstrate a high level of prediction accuracy on a set of random as well as practical, standard test problems. Next, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises. For each case, we identify the indistinguishable objects in the model which create the problem symmetry, and show how imposing certain decision hierarchies within the model significantly enhances its solvability. These hierarchies render an otherwise virtually intractable formulation computationally viable using commercial software. For the first problem, we consider a problem of minimizing the maximum dosage of noise to which workers are exposed while working on a set of machines. We next examine a problem of minimizing the cost of acquiring and utilizing machines designed to cool large facilities or buildings, subject to minimum operational requirements. For each of these applications, we generate realistic test beds of problems. The decision hierarchies allow all previously intractable problems to be solved relatively quickly, and dramatically decrease the required computational time for all other problems. For the third problem, we investigate a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find a placement of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5-13% of the optimal solution. Promising computational results that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs are presented. Following this we turn our attention to the modeling and analysis of several issues related to airspace management. Currently, commercial aircraft are routed along certain defined airspace corridors, where safe minimum separation distances between aircraft may be routinely enforced. However, this mode of operation does not fully utilize the available airspace resources, and may prove to be inadequate under future National Airspace (NAS) scenarios involving new concepts such as Free-Flight. This mode of operation is further compounded by the projected significant increase in commercial air traffic. (Free-Flight is a paradigm of aircraft operations which permits the selection of more cost-effective routes for flights rather than simple traversals between designated way-points, from various origins to different destinations.) We begin our study of Air Traffic Management (ATM) by first developing an Airspace Sector Occupancy Model (AOM) that identifies the occupancies of flights within three dimensional (possibly nonconvex) regions of space called sectors. The proposed iterative procedure effectively traces each flight's progress through nonconvex sector modules which comprise the sectors. Next, we develop an Aircraft Encounter Model (AEM), which uses the information obtained from AOM to efficiently characterize the number and nature of blind-conflicts (i.e., conflicts under no avoidance or resolution maneuvers) resulting from a selected mix of flight-plans. Besides identifying the existence of a conflict, AEM also provides useful information on the severity of the conflict, and its geometry, such as the faces across which an intruder enters and exits the protective shell or envelope of another aircraft, the duration of intrusion, its relative heading, and the point of closest approach. For purposes of evaluation and assessment, we also develop an aggregate metric that provides an overall assessment of the conflicts in terms of their individual severity and resolution difficulty. We apply these models to real data provided by the Federal Aviation Administration (FAA) for evaluating several Free-Flight scenarios under wind-optimized and cruise-climb conditions. We digress at this point to consider a more general collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of Selim and Almohamad, and exhibit the relative effectiveness of solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear translation. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the relative effectiveness of solving a sequence of problems based on applying the latter construct to each time segment. Returning to Air Traffic Management, another future difficulty in airspace resource utilization stems from a projected increase in commercial space traffic, due to the advent of Reusable Launch Vehicle (RLV) technology. Currently, each shuttle launch cordons off a large region of Special Use Airspace (SUA) in which no commercial aircraft are permitted to enter for the specified duration. Of concern to airspace planners is the expense of routinely disrupting air traffic, resulting in circuitous diversions and delays, while enforcing such SUA restrictions. To provide a tool for tactical and planning purposes in such a context within the framework of a coordinated decision making process between the FAA and commercial airlines, we develop an Airspace Planning Model (APM). Given a set of flights for a particular time horizon, along with (possibly several) alternative flight-plans for each flight that are based on delays and diversions due to special-use airspace (SUA) restrictions prompted by launches at spaceports or weather considerations, this model prescribes a set of flight-plans to be implemented. The model formulation seeks to minimize a delay and fuel cost based objective function, subject to the constraints that each flight is assigned one of the designated flight-plans, and that the resulting set of flight-plans satisfies certain specified workload, safety, and equity criteria. These requirements ensure that the workload for air-traffic controllers in each sector is held under a permissible limit, that any potential conflicts which may occur are routinely resolvable, and that the various airlines involved derive equitable levels of benefits from the overall implemented schedule. In order to solve the resulting 0-1 mixed-integer programming problem more effectively using commercial software (CPLEX-MIP), we explore the use of various facetial cutting planes and reformulation techniques designed to more closely approximate the convex hull of feasible solutions to the problem. We also prescribe a heuristic procedure which is demonstrated to provide solutions to the problem that are either optimal or are within 0.01% of optimality. Computational results are reported on several scenarios based on actual flight data obtained from the Federal Aviation Administration (FAA) in order to demonstrate the efficacy of the proposed approach for air traffic management (ATM) purposes. In addition to the evaluation of these various models, we exhibit the usefulness of this airspace planning model as a strategic planning tool for the FAA by exploring the sensitivity of the solution provided by the model to changes both in the radius of the SUA formulated around the spaceport, and in the duration of the launch-window during which the SUA is activated. / Ph. D.

Cette thèse aborde la reformulation dans des discussions entre jeunes Libanais francophones. Après une approche lexicologique de formuler/reformuler/reformulation qui vise à faire émerger leurs spécificités par rapport à dire/redire, énoncer/réénoncer, etc., et une tentative de trouver une unité à l’objet discursif qu’est la reformulation, une double approche des reformulations du corpus est engagée. La première, linguistique, dresse une typologie de ce phénomène dans le corpus. Se voulant globale, elle prend en compte des critères linguistiques (phonologique, sémantique, lexical, morphosyntaxiques) et d’autres qui relèvent de la dimension interactive dans laquelle s’inscrivent les reformulations (instances, initiation et rôle de la reformulation dans le discours). Le principal apport de cette approche qualitative et quantitative est d’avoir montré l’aspect central de la morphosyntaxe dans le marquage des reformulations nuançant ainsi les approches du phénomène à travers les marqueurs lexicaux et les connecteurs. La deuxième approche se centre sur les locuteurs et sur leur statut de non-natifs en s’interrogeant sur le potentiel des reformulations à nous renseigner sur leur compétence de communication. De plus, le travail se penche sur des phénomènes de contacts de langues dans le cadre de l’activité reformulatoire des locuteurs dans le corpus. Cette thèse se consacre enfin, dans le cadre théorique de la grammaticalisation/pragmaticalisation, à l’étude d’un marqueur discursif du dialecte libanais «jæʕne» qui fait irruption dans le discours des locuteurs et témoigne, entre autres emplois, de celui de marqueur de reformulation. Les emplois de jæʕne sont considérés aussi comme des phénomènes de contacts de langue d’une part dans le cadre d’alternance codique et d’autre part, à travers des calques opérés par les locuteurs sur c’est-à-dire. / This PhD thesis approaches reformulation in conversations between young francophone Lebanese. It starts with a lexicological approach of the words formulate/reformulate/reformulation in order to emphasize their differences with say/say again, utter/utter again and goes on with a deep analysis of reformulation as a discursive object, followed by a two-fold approach of the occurrences in the corpus. The first approach is a linguistic one and also deals with the interactional dimension of reformulations. Quantitative and qualitative analyses emphasize the role of morphosyntax in marking reformulations, completing the approaches based on discourse markers and connectives. The second approach, focusing on the speakers, takes into account their non-native speaker status. We are questioning here the way in which reformulations can provide information about their communicative competence. Reformulation is seen as a communicative strategy they use in order to solve communication problems. Our work ends with the analysis of a Lebanese French discourse marker, jæʕne, used by the speakers to indicate reformulation (among other things). The first part of the analysis draws a typology of all its uses within the grammaticalization/pragmaticalization framework while the second one studies it as a language contact phenomenon.

Cette étude s'inscrit dans le champ de la didactique du français et porte sur l'analyse d'interactions langagières au cours de séances de révision de textes narratifs au CM2. Cette recherche se propose de réfléchir aux modalités d'une interaction qui favoriserait l'engagement des élèves dans la tâche. Elle se centre principalement sur l'activité du maître lors de séquences de "révisions interactives". La méthodologie s'appuie sur l'analyse de corpus oraux. Une étude empirique impliquant trois enseignantes ayant une ancienneté différente dans le métier nous permet de comparer les modes de communication pédagogique et d'examiner leur pertinence pour le développement de compétences évaluatives chez les élèves. Les résultats nous permettent de dégager quelques paramètres décisifs et d'esquisser un profil interactionnel des enseignantes lors de la révision de textes. L'étayage de l'enseignant est abordé sous différents angles : la posture assumée tout au long des échanges, les thèmes discutés, le degré d'adhésion par rapport aux propositions des élèves, la prise en compte des interventions par les reformulations mais aussi le rythme des échanges imposé. Nous prolongeons notre étude par l'analyse des stratégies inductrices de "bonnes réponses", c'est-à-dire tous les comportements verbaux du maître qui permettent d'influencer la réponse de l'élève et qui s'apparentent à une posture de contre-étayage. Cette étude permet de mettre en évidence la typicalité de l'expérience interactionnelle de l'enseignant dans le domaine de la révision de texte et d'ouvrir la voie à une didactique de l'écrit à l'école primaire fondée sur les interactions à l'oral. / This study belongs to the didactics of French and focuses on oral interactions analysis during revision sessions of narrative texts at the last year of primary school. The purpose of this study is to investigate how the oral interactions can improve pupils' commitment to the task. This research focuses more precisely on the activity of the teacher during interactive revision sessions. The methodological framework is based on oral resources. Our study implies three teachers at different levels of career and allows us to compare different modes of pedagogical communication in order to examine their pertinence for the development of the pupils' evaluative abilities. Results allow to bring out some decisive parameters and to suggest an interactional profile of teachers during texts revision. The teacher's scaffolding is approached from different points of view : the position held by the teacher throughout the exchanges, the discussed topics, the degree of joining to pupils' proposals, the consideration of pupils' interventions by reformulations and the interactional rhythm required by the teacher. The research will be extended by the analysis of the strategies which lead to the "right response" of the "expected response", in other words, all verbal communications which influence the response of the pupil and which correspond to wrong or inappropriate scaffolding. This study allows us to highlight the specificities of the interactional experience of the teacher in the field of the text revision and to pave the way to didactics of writing in primary school based on oral interactions.

[pt] A presente dissertação tem por objetivo analisar o fenômeno da constitucionalização do Direito Administrativo e a conseqüente releitura de dois princípios basilares deste ramo do direito: os princípios da legalidade e da legitimidade administrativas. Após algumas considerações introdutórias e a apresentação do tema no capítulo I, o trabalho analisará, no capítulo II, o nascimento e a evolução do Direito Administrativo, com o intuito de demonstrar que a concepção clássica deste ramo do Direito deve passar por uma leitura constitucional, em tempos de constitucionalização do ordenamento jurídico. No capítulo III, o enfoque será o estudo do princípio da legalidade e a sua evolução ao longo dos tempos. A concepção liberal deste princípio, consagrado no Estado Liberal de Direito, entra em crise. A lei deixa de ocupar o papel de protagonista do ordenamento jurídico para dar lugar à Constituição. O desprestígio do Parlamento, bem como a celeridade e complexidade da vida moderna, acabam por gerar a ampliação do poder normativo das entidades administrativas localizadas fora do Poder Legislativo. Com isso, institutos como a deslegalização e a reserva da administração, bem como a figura do regulamento autônomo, ganham destaque no debate jurídico atual. Ao invés do respeito apenas à lei formal, a atuação administrativa deve adequar-se ao ordenamento jurídico como um todo, o que acarreta a consagração do princípio da juridicidade. Em seguida, no capítulo IV, o estudo tecerá considerações sobre as concepções clássicas de legitimidade e demonstrará a necessidade de se reforçar a legitimidade democrática da Administração Pública através de instrumentos efetivos de participação do cidadão na tomada de decisões e elaboração de normas administrativas. O capítulo V, por sua vez, demonstrará que a releitura dos princípios da legalidade e da legitimidade administrativas pode ser verificada, com mais exatidão, na formatação das agências reguladoras. A discussão em relação à constitucionalidade do modelo regulatório adotado pelo ordenamento jurídico pátrio passa necessariamente pela compatibilidade com os princípios em comento. Por fim, no capítulo VI, a titulo de conclusão, o trabalho apontará a importância do princípio da juridicidade no âmbito do estado Democrático de Direito. / [en] The main goal of this dissertation is to analyze the phenomena of constitutionalization in Administrative law and the resulting reconsideration of two basic pilars underpinning this field of Law: the principles of legality and of administrative legitimacy. After some introductory considerations followed by the presentation of the main theme in the first Chapter, the author will review, in the second Chapter, the emergence and evolution of Administrative Law in order to demonstrate that, in view of the current constitutionalization of the legal system, the constitutional perspective should be added to the classic conception of Administrative Law. The third Chapter will focus on the study of the legality principle and how it evolved through times. The liberal view of this principle, the cornerstone of the Liberal Rule of Law, comes to a crisis. The Law becomes less and less the leading agent of the legal order while this role is assigned to the Constitution. The decreasing prestige of Parliament as well as the complexity and the ever-faster pace of modern life end up extending the normative power to administrative entities found outside the realm of the Legislative Branch. Therefore, institutes such as the de-legalization and the administrative reserve, as well as the institute of -autonomous regulation-, gain prominence in the current public debate. Instead of owing respect only to the formal Law, the administrative arena should also adjust itself to the legal order as a whole, which means that the -principle of jurisdicity- becomes paramount. Subsequently, in the fourth Chapter, the study will discuss the classic conceptions of legality and will demonstrate the need to reinforce the democratic legitimacy in Public Administration by means of effective instruments allowing citizens to be part of the decision-making process and of the development of administrative norms. The fifth chapter, in turn, will demonstrate how the re- consideration of the principles of legality and administrative legitimacy can be more accurately verified in the way regulatory agencies were formatted. Any discussion on the constitutionality of the regulatory model adopted by the legal order in Brazil necessarily includes compatibility with the principles under discussion The sixth chapter will conclude the study pointing out the importance of the -principle of jurisdicity- under the Democratic Rule of Law.

Le Système Électrique est soumis ces dernières années à plusieurs évolutions, depuis la dérégulationdu marché d'énergie à l'intégration de plus en plus importante de Générateurs Dispersés (GED). Ainsi,dans le cadre du concept de Smart Grid, les nouvelles technologies de l'information et de lacommunication (NTIC) offrent de nouvelles perspectives pour la gestion et l'exploitation des réseauxde distribution.Dans ce contexte, de nouveaux outils sont étudiés. Encore appelés Fonctions Avancéesd’Automatisation (FAA), le but principal de ces outils est d’utiliser tous les composants du réseau dedistribution de manière coordonnée en vue de les rendre plus actifs, flexibles et d’augmenter leurefficacité opérationnelle. Dans notre cas, nous avons étudié les fonctions associées à la reconfigurationen régime normal, du réglage de la tension et l’hybridation de ces deux derniers, tout en tenant comptede la présence des GED. En partant du comportement physique inhérent aux composants du réseau,plusieurs modèles ont été proposés. Certains sont tirés de la théorie des graphes et d’autres sur l’outilpuissant de la reformulation mathématique pour « convexifier » nos modèles. Cette modélisationadoptée répond à la fois à la nécessité de prendre en compte tous les moyens de réglages qui peuventêtre discrets (prises des transformateurs avec régleurs en charge ou des gradins de condensateurs),binaires (état de connectivité des composants) et continues (puissance réactive de la DG) et par lechoix des outils et des algorithmes d'optimisation mixte. En effet, la complexité de ces problèmes sonttelles que nous avons exploré à la fois des algorithmes méta-heuristiques (ACF : Algorithme desColonies de Fourmis) que déterministes (Décomposition de Benders Généralisée, Algorithme duBranch and Cut). / The Electric Power System is undergoing a lot of evolutions in recent years, including the energymarket deregulation and the increasing integration of Dispersed Generators (DG). Therefore, withinthe framework of Smart Grid concept, the New Information and Communication Technologies (NICT)provide new perspectives to manage and operate distribution networks.In this context, new tools, called Advanced Distribution Automation functions (ADA, are beingstudied). The main objective of these tools is to use all the distribution network components in acoordinated manner to make them more active and flexible, in addition to increasing their operationalefficiency. In our case, we studied the functions associated with the reconfiguration problem, thevoltage control problem and the hybridization of these two, while taking into account the presence ofthe DG. Based on the inherent components of network physical models, several models have beenproposed. Some are derived from the graph theory and others use powerful mathematicalreformulation to make our models convex. The adopted models answer to the necessity of taking intoaccount all regulation means, which can be discrete (On Load Tap-Changer and capacitor banks),binary (components connectivity such as lines or transformers) and continuous (DG reactive power ),and by the choice of tools and algorithms of mixed optimization. Indeed, the complexity of theseproblems is such that we have explored both algorithms: meta-heuristic (ACA, Ant Colony Algorithm)and deterministic (Generalized Benders Decomposition, Branch and Cut Algorithm).

Dans cette thèse nous explorons les aspects de la gravité d'Einstein qui sont propres à la dimension quatre.L'une des propriétés surprenantes liées à cette dimension est la possibilité de formuler la gravité de manière 'Chirale'. Dans ce type de reformulations, typiquement, la métrique perd son rôle centrale. La correspondance entre espace-temps et espace des twisteurs est un autre aspect propre à la dimension quatre. Ces formulations, Chirale et Twistorielle, semblent très différentes. Dans la première partie de cette thèse nous montrons qu'elles sont en fait intimement liées: en particulier nous proposons une nouvelle preuve du `théorème du graviton non-linéaire', due à Penrose, dont le cœur est la géométrie des SU(2)-connections (plutôt qu'une métrique). Dans la seconde partie de cette thèse nous montrons que la gravité en trois et quatre dimensions est liée à des théories d'une nature complètement différentes en dimension six et sept. Ces théories, due à Hitchin, sont des théories de trois-formes différentielles invariantes sous difféomorphismes. En dimensions sept, nous rencontrons seulement un succès partiel puisque la théorie 4D qui en résulte est une version modifiée de la gravité. Cependant nous prouvons au passage que les solutions d'une déformation particulière de la gravité ont, en 7D, l’interprétation de variétés avec holonomies G2.Par contre, en réduisant la théorie de six à trois dimensions nous obtenons précisément la gravité 3D. Nous présentons aussi de nouvelles fonctionnelles pour les formes différentielles en six dimensions. Toutes sont invariantes sous difféomorphismes et deux d’entre elles sont topologiques. / In this thesis we take Einstein theory in dimension four seriously, and explore the special aspects of gravity in this number of dimension.Among the many surprising features in dimension four, one of them is the possibility of `Chiral formulations of gravity' - they are surprising as they typically do not rely on a metric. Another is the existence of the Twistor correspondence. The Chiral and Twistor formulations might seems different in nature. In the first part of this thesis we demonstrate that they are in fact closely related. In particular we give a new proof for Penrose's `non-linear graviton theorem' that relies on the geometry of SU(2)-connections only (rather than on metric).In the second part of this thesis we describe partial results towards encoding the full GR in the total space of some fibre bundle over space-time. We indeed show that gravity theory in three and four dimensions can be related to theories of a completely different nature in six and seven dimension respectively. This theories, first advertised by Hitchin, are diffeomorphism invariant theories of differential three-forms.Starting with seven dimensions, we are only partially succesfull: the resulting theory is some deformed version of gravity. We however found that solutions to a particular gravity theory in four dimension have a seven dimensional interpretation as G2 holonomy manifold. On the other hand by going from six to three dimension we do recover three dimensional gravity. As a bonus, we describe new diffeomorphism invariant functionnals for differential forms in six dimension and prove that two of them are topological.

Cette thèse a pour objet la résolution exacte d’un problème d’optimisation des flux de puissance (OPF) dans un réseau électrique. Dans l’OPF, on doit planifier la production et la répartition des flux de puissances électriques permettant de couvrir, à un coût minimal, la consommation en différents points du réseau. Trois variantes du problème de l’OPF sont étudiées dans ce manuscrit. Nous nous concentrerons principalement sur la résolution exacte des deux problèmes (OPF − L) et (OPF − Q), puis nous montrerons comment notre approche peut naturellement s’´étendre à la troisième variante (OPF − UC). Cette thèse propose de résoudre ces derniers à l’aide d’une méthode de reformulation que l’on appelle RC-OPF. La contribution principale de cette thèse réside dans l’étude, le développement et l’utilisation de notre méthode de résolution exacte RC-OPF sur les trois variantes d’OPF. RC-OPF utilise également des techniques de contractions de bornes, et nous montrons comment ces techniques classiques peuvent être renforcées en utilisant des résultats issus de notre reformulation optimale. / Alternative Current Optimal Power Flow (ACOPF) is naturally formulated as a non-convex problem. In that context, solving (ACOPF) to global optimality remains a challenge when classic convex relaxations are not exact. We use semidefinite programming to build a quadratic convex relaxation of (ACOPF). We show that this quadratic convex relaxation has the same optimal value as the classical semidefinite relaxation of (ACOPF) which is known to be tight. In that context, we build a spatial branch-and-bound algorithm to solve (ACOPF) to global optimality that is based on a quadratic convex programming bound.

Cette thèse s'intéresse à la résolution de très grands problèmes d'optimisation combinatoire stochastique. Les recherches sont appliquées au problème de planification des arrêts pour rechargement des centrales nucléaires. Compte-tenu de la part prépondérante de celles-ci dans le mix-électrique, ce problème structure fortement la chaîne de management d’énergie d'EDF. Une première partie propose une formulation étendue bi-niveau dans laquelle les décisions de premier niveau fixent les plannings d’arrêt et des profils de production des centrales, et celles de second niveau évaluent le coût de satisfaction de la demande associé. Cette formulation permet la résolution à l'optimum d'instances industrielles déterministes par un solveur en PLNE. Dans le cas stochastique, une telle résolution directe du problème n'est plus possible. Nous proposons une formulation permettant d’en résoudre la relaxation linéaire par génération de colonnes et de coupes, correspondant respectivement aux reformulations de Danzig-Wolfe du premier niveau et de Benders du second. Une phase heuristique permet ensuite de déterminer des solutions entières de bonne qualité pour des instances, jusqu'à une cinquantaine de scénarios représentatifs de l’incertitude sur les données. L’apport de l’approche est estimé en utilisant les outils industriels exploités par EDF pour évaluer les plannings. Une seconde partie porte sur l'intégration de méthodes d'optimisation robuste pour la prise en compte d’aléas sur la disponibilité des centrales. Nous nous plaçons dans un cadre où les recours possibles sur les dates d'arrêts ne sont pas exercés. Nous comparons des méthodes bi-objectif et probabiliste permettant de rendre le planning robuste pour les contraintes opérationnelles dont la relaxation est envisageable. Pour les autres, nous proposons une méthode basée sur un budget d’incertitude. Cette méthode permet de renforcer la stabilité du planning en limitant les besoins de réorganisation futurs. La prise en compte d’une loi de probabilité de l’aléa permet d’affiner le contrôle du prix de cette robustesse. / The purpose of this Ph.D. thesis is to study optimization techniques for large-scale stochastic combinatorial problems. We apply those techniques to the problem of scheduling EDF nuclear power plant maintenance outages, which is of significant importance due to the major part of the nuclear energy in the French electricity system. We build on a two-stages extended formulation, the first level of which fixes nuclear outage dates and production profiles for nuclear plants, while the second evaluates the cost to meet the demand. This formulation enables the solving of deterministic industrial instances to optimality, by using a MIP solver. However, the computational time increases significantly with the number of scenarios. Hence, we resort to a procedure combining column generation of a Dantzig-Wolfe decomposition with Benders’ cut generation, to account for the linear relaxation of stochastic instances. We then obtain integer solutions of good quality via a heuristic, up to fifty scenarios. We further assume that outage durations are uncertain and that unexpected shutdowns of plants may occur. We investigate robust optimization methods in this context while ignoring possible recourse on power plants outage dates. We report on several approaches, which use bi-objective or probabilistic methods, to ensure the satisfaction of constraints which might be relaxed in the operating process. For other constraints, we apply a budget uncertainty-based approach to limit future re-organizations of the scheduling. Adding probabilistic information leads to better control of the price of the robustness.

La recherche sémantique de l'information a connu un nouvel essor avec les nouvelles technologies du Web sémantique. Des langages standards permettent aujourd'hui aux logiciels de communiquer par le biais de données écrites dans le vocabulaire d'ontologies de domaine décrivant une sémantique explicite. Cet accès ''sémantique'' à l'information requiert la disponibilité de bases de connaissances décrivant les instances des ontologies de domaine. Cependant, ces bases de connaissances, bien que de plus en plus riches, contiennent relativement peu d'information par comparaison au volume des informations contenu dans les documents du Web.La recherche sémantique de l'information atteint ainsi certaines limites par comparaison à la recherche classique de l'information qui exploite plus largement ces documents. Ces limites se traduisent explicitement par l'absence d'instances de concepts et de relations dans les bases de connaissances construites à partir des documents du Web. Dans cette thèse nous étudions deux directions de recherche différentes afin de permettre de répondre à des requêtes sémantiques dans de tels cas. Notre première étude porte sur la reformulation des requêtes sémantiques des utilisateurs afin d'atteindre des parties de document pertinentes à la place des faits recherchés et manquants dans les bases de connaissances. La deuxième problématique que nous étudions est celle de l'enrichissement des bases de connaissances par des instances de relations.Nous proposons deux solutions pour ces problématiques en exploitant des documents semi-structurés annotés par des concepts ou des instances de concepts. Un des points clés de ces solutions est qu'elles permettent de découvrir des instances de relations sémantiques sans s'appuyer sur des régularités lexico-syntaxiques ou structurelles dans les documents. Nous situons ces deux approches dans la littérature et nous les évaluons avec plusieurs corpus réels extraits du Web. Les résultats obtenus sur des corpus de citations bibliographiques, des corpus d'appels à communication et des corpus géographiques montrent que ces solutions permettent effectivement de retrouver de nouvelles instances relations à partir de documents hétérogènes tout en contrôlant efficacement leur précision.