Backtracking CSP solvers provide a powerful framework for search and reasoning. The aim of constraint learning is increase global reasoning power by learning new constraints to boost reasoning and hopefully reduce search effort. In this thesis constraint learning is developed in several ways to make it faster and more powerful. First, lazy explanation generation is introduced, where explanations are generated as needed rather than continuously during propagation. This technique is shown to be effective is reducing the number of explanations generated substantially and consequently reducing the amount of time taken to complete a search, over a wide selection of benchmarks. Second, a series of experiments are undertaken investigating constraint forgetting, where constraints are discarded to avoid time and space costs associated with learning new constraints becoming too large. A major empirical investigation into the overheads introduced by unbounded constraint learning in CSP is conducted. This is the first such study in either CSP or SAT. Two significant results are obtained. The first is that typically a small percentage of learnt constraints do most propagation. While this is conventional wisdom, it has not previously been the subject of empirical study. The second is that even constraints that do no effective propagation can incur significant time overheads. Finally, the use of forgetting techniques from the literature is shown to significantly improve the performance of modern learning CSP solvers, contradicting some previous research. Finally, learning is generalised to use disjunctions of arbitrary constraints, where before only disjunctions of assignments and disassignments have been used in practice (g-nogood learning). The details of the implementation undertaken show that major gains in expressivity are available, and this is confirmed by a proof that it can save an exponential amount of search in practice compared with g-nogood learning. Experiments demonstrate the promise of the technique.

Die mobile Robotik stellt ein sehr junges und komplexes Forschungsfelder unserer Zeit dar. Innerhalb der letzten Jahrzehnte wurde es Robotern möglich, sich innerhalb ihrer Umgebung zu bewegen, zu navigieren und mit ihrer Umwelt zu interagieren. Aufgrund der Tatsache, dass die Welt von Unsicherheit geprägt ist und ein Roboter immer nur partielle Information über sie erhalten kann, wurden probabilistische Navigationsverfahren entwickelt, mit denen sich Roboter lokalisieren und Objekte ihrer Umgebung modellieren können. Weiterhin wurden in letzter Zeit Verfahren untersucht, die die kooperative Exploration der Umgebung durch eine Gruppe von Robotern zum Ziel haben. In der vorliegenden Arbeit wird ein neuartiges Konzept, welches sich Perzeptrelationen für die kooperative Umweltmodellierung zu Nutze macht, vorgestellt und evaluiert. Einen zweiten Beitrag der Arbeit stellen constraintbasierte Lokalisierungstechniken dar, die es einem oder mehreren Robotern auf effiziente Art und Weise ermöglichen, sich zu lokalisieren und ihre Umwelt zu modellieren. / Mobile autonomous robotics is a very young and complex field of research. Only in recent decades have robots become able to explore, to move, navigate and to interact with their environment. Since the world is uncertain and since robots can only gain partial information about it, probabilistic navigation algorithms have become very popular whenever a robot has to localize itself or surrounding objects. Furthermore, cooperative exploration and localization approaches have become very relevant lately, as robots begin to act not just alone but in groups. Within this thesis a new approach using the concept of spatial percept-relations for cooperative environment modeling is presented and evaluated. As a second contribution, constraint based localization techniques will be introduced for having a robot or a group of robots efficiently localized and to model their environment.

Dans cette thèse, nous étudions des approches basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) pour la programmation mathématique avec des contraintes d'équilibre, notée MPEC (Mathematical Programming with Equilibrum Constraints en anglais). Etant un sujet classique et difficile de la programmation mathématique et de la recherche opérationnelle, et de par ses diverses applications importantes, MPEC a attiré l'attention de nombreux chercheurs depuis plusieurs années. La thèse se compose de quatre chapitres principaux. Le chapitre 2 étudie une classe de programmes mathématiques avec des contraintes de complémentarité linéaire. En utilisant quatre fonctions de pénalité, nous reformulons le problème considéré comme des problèmes DC standard, i.e minimisation d'une fonction DC sous les contraintes convexes. Nous développons ensuite des algorithmes appropriés basés sur DCA pour résoudre les problèmes DC résultants. Deux d'entre eux sont reformulés encore sous la forme des problèmes DC généraux (i.e. minimisation d'une fonction DC sous des contraintes DC) pour que les sous-problèmes convexes dans DCA soient plus faciles à résoudre. Après la conception de DCA pour le problème considéré, nous développons ces schémas DCA pour deux cas particuliers: la programmation quadratique avec des contraintes de complémentarité linéaire, et le problème de complémentarité aux valeurs propres. Le chapitre 3 aborde une classe de programmes mathématiques avec des contraintes d'inégalité variationnelle. Nous utilisons une technique de pénalisation pour reformuler le problème considéré comme un programme DC. Une variante de DCA et sa version accélérée sont proposées pour résoudre ce programme DC. Comme application, nous résolvons le problème de détermination du prix de péages dans un réseau de transport avec des demandes fixes (" the second-best toll pricing problem with fixed demands" en anglais). Le chapitre 4 se concentre sur une classe de problèmes d'optimisation à deux niveaux avec des variables binaires dans le niveau supérieur. En utilisant une fonction de pénalité exacte, nous reformulons le problème considéré comme un programme DC standard pour lequel nous développons un algorithme efficace basé sur DCA. Nous appliquons l'algorithme proposé pour résoudre le problème d'interdiction de flot maximum dans un réseau ("maximum flow network interdiction problem" en anglais). Dans le chapitre 5, nous nous intéressons au problème de conception de réseau d'équilibre continu ("continuous equilibrium network design problem" en anglais). Il est modélisé sous forme d'un programme mathématique avec des contraintes de complémentarité, brièvement nommé MPCC (Mathematical Program with Complementarity Constraints en anglais). Nous reformulons ce problème MPCC comme un programme DC général et proposons un schéma DCA approprié pour le problème résultant / In this dissertation, we investigate approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) for mathematical programs with equilibrium constraints. Being a classical and challenging topic of nonconvex optimization, and because of its many important applications, mathematical programming with equilibrium constraints has attracted the attention of many researchers since many years. The dissertation consists of four main chapters. Chapter 2 studies a class of mathematical programs with linear complementarity constraints. By using four penalty functions, we reformulate the considered problem as standard DC programs, i.e. minimizing a DC function on a convex set. The appropriate DCA schemes are developed to solve these four DC programs. Two among them are reformulated again as general DC programs (i.e. minimizing a DC function under DC constraints) in order that the convex subproblems in DCA are easier to solve. After designing DCA for the considered problem, we show how to develop these DCA schemes for solving the quadratic problem with linear complementarity constraints and the asymmetric eigenvalue complementarity problem. Chapter 3 addresses a class of mathematical programs with variational inequality constraints. We use a penalty technique to recast the considered problem as a DC program. A variant of DCA and its accelerated version are proposed to solve this DC program. As an application, we tackle the second-best toll pricing problem with fixed demands. Chapter 4 focuses on a class of bilevel optimization problems with binary upper level variables. By using an exact penalty function, we express the bilevel problem as a standard DC program for which an efficient DCA scheme is developed. We apply the proposed algorithm to solve a maximum flow network interdiction problem. In chapter 5, we are interested in the continuous equilibrium network design problem. It was formulated as a Mathematical Program with Complementarity Constraints (MPCC). We reformulate this MPCC problem as a general DC program and then propose a suitable DCA scheme for the resulting problem

La santé est un domaine particulier au sein duquel les intérêts humains sont confrontés à la réalité du coût de la délivrance de soins. Dans ce contexte, il faut alors s'interroger sur une question particulière qu'est la gestion du risque pénal par les établissements de santé. Cette problématique est essentielle car la protection de la santé et la préservation de l'intégrité corporelle des patients, mais également des personnels et de tout intervenant extérieur, sont au cœur de leur activité. Leur objectif est alors de soigner en faisant face à un grand nombre de contraintes, sanitaires mais aussi économiques, en évitant la réalisation du risque pénal, et même en maintenant le niveau de ce dernier au minimum et ainsi éviter l'engagement d'une quelconque responsabilité pénale. / The health is a particular domain within which the human interests are confronted with the reality of the cost of the delivery of care. In this context, it is then necessary to wonder about a particular question that is the management of the penal risk by the establishments of health. This problem is essential because the protection of the health and the conservation of the physical integrity of the patient, but also the staffs and every outside person, are at the heart of their activity. Their objective is then to look after by facing a large number of constraints, sanitary but also economic, by avoiding the realization of the penal risk, and same by maintaining the level of the latter at least and so avoid the commitment of any penal responsibility.

Differential-algebraic equations (DAEs) consist of mixed systems of ordinary differential equations (ODEs) coupled with linear or nonlinear equations. Such systems may be viewed as ODEs with integral curves lying in a manifold. DAEs appear frequently in applications such as classical mechanics and electrical circuits. This thesis concentrates on systems of index 2, originally index 3, and mixed index 2 and 3. Fast and efficient numerical solvers for DAEs are highly desirable for finding solutions. We focus primarily on the class of Gauss-Lobatto SPARK methods. However, we also introduce an extension to methods proposed by Murua for solving index 2 systems to systems of mixed index 2 and 3. An analysis of these methods is also presented in this thesis. We examine the existence and uniqueness of the proposed numerical solutions, the influence of perturbations, and the local error and global convergence of the methods. When applied to index 2 DAEs, SPARK methods are shown to be equivalent to a class of collocation type methods. When applied to originally index 3 and mixed index 2 and 3 DAEs, they are equivalent to a class of discontinuous collocation methods. Using these equivalences, (s,s)--Gauss-Lobatto SPARK methods can be shown to be superconvergent of order 2s. Symplectic SPARK methods applied to Hamiltonian systems with holonomic constraints preserve well the total energy of the system. This follows from a backward error analysis approach. SPARK methods and our proposed EMPRK methods are shown to be Lagrange-d'Alembert integrators. This thesis also presents some numerical results for Gauss-Lobatto SPARK and EMPRK methods. A few problems from mechanics are considered.

In der vorliegenden Arbeit wird eine Studie zum mentalen Lexikon bei Kindern mit Williams-Beuren-Syndrom (WBS) präsentiert. Das Lexikon junger WBS-Kinder entwickelt sich verzögert (Mervis & Robinson, 2000). Trotzdem gilt das Lexikon jugendlicher WBS-Probanden im Vergleich zu Probanden mit anderen Syndromen als elaboriert (Wang et al. 1995). Dies könnte auf sich spät entwickelnde Sprachfähigkeiten hindeuten. Es wird vermutet, dass ab 11 Jahren Veränderungen stattfinden, durch die das typische Profil des WBS erst entsteht (Rossen et al. 1996). Ziel der vorliegenden Arbeit ist es, sich der Aufholphase zu nähern, indem die lexikalischen Fähigkeiten vor dem kritischen Alter untersucht werden. Dazu werden zwei lexical constraints untersucht, die Markman (1989) für den ungestörten Lexikonerwerb postuliert. Whole object constraint (WOC): Das Kind nimmt an, dass sich ein unfamiliäres Wort auf ein ganzes Objekt bezieht. Mutual exclusivity constraint (MEC): Das Kind nimmt eine beidseitig exklusive Beziehung zwischen Wortform und Referenten an. Zum WBS gibt es eine einzige Studie zu den constraints (Stevens & Karmiloff-Smith 1997). Die WBS-Probanden sind zu alt (7;5 bis 31;5), um Aussagen über die Sprachfähigkeiten in der Zeit des Spurts machen zu können. Markman postuliert die constraints als Teil des universalen Wissens von Kindern. Dementsprechend ist die Hypothese, dass die constraints auch bei WBS-Kindern aktiv sind und in experimentellen Situationen zur Anwendung kommen. Zentral für die Hypothese ist die Untersuchung von Vorschulalkindern. Es werden 5 WBS-Kinder (3;2-7;0) und 98 chronologisch gematchte Kontrollkinder im WOC bzw. 97 im MEC untersucht. Es wird jeweils ein Versuch zum WOC (n=9) und zum MEC (n=12) durchgeführt. Beim WOC-Versuch wählen WBS-Kinder und Kontrollkinder am häufigsten das Zielitem. Die WBS-Kinder wählen häufig das Teilablenkerbild. Im Einzelfallvergleich sind 4 der 5 WBS-Kinder im Vergleich zu ihrer Kontrollgruppe auffällig. Im MEC-Versuch zeigen die ungestörten Kinder signifikant häufiger auf das Bild mit dem phonologischen Ablenker als die WBS-Kinder. In der Einzelfallanalyse liegen 4 von 5 WBS-Kindern bei der Auswahl des Zielitems oberhalb des Mittelwertes ihrer Kontrollgruppe. Insgesamt ergeben sich durch das Verhalten der WBS-Kinder in den Versuchen eher Hinweise auf defizitäre perzeptuelle Einflüsse auf die Anwendung der lexikalischen constraints als auf ihr Fehlen. Als Ursache für das Verhalten der WBS-Kinder wird die Detailpräferenzhypothese postuliert. Majerus et al.s (2003)Hypothese wird um die visuelle Verarbeitung erweitert. Diese findet lokal statt und kann nur bedingt Gattungsbegriffe aufbauen. Den überspezifizierten Wortformen stehen Teilrepräsentationen gegenüber. Die entstehenden semantischen Repräsentationen sind an konkreten Erfahrungen orientiert und verbleiben auf einer überspezifizierten Form. Mit der Hypothese der generellen Detailpräferenz wird zum ersten Mal eine einheitliche Wurzel für das Verhalten von WBS-Kindern im Vorschulalter in verschiedenen psychologischen Fakultäten aufgestellt. Majerus, S., Van der Linden, M., Mulder, L., Meulemans, T., & Peters, F. (2003). Verbal short-term memory reflects the sublexical organization of the phonological language network: evidence from an incidental phonotactic learning paradigm. Journal of Memory and Language, 51, 297-306. Markman, E. (1989). Categorization and naming in children. Cambridge MA: MIT Press. Mervis, C. B. & Robinson, B. F. (2000). Expressive vocabulary ability of toddlers with Williams syndrome or Down syndrome: a comparison. Developmental Neuropsychology, 17, 11-126. Rossen, M., Klima, E., Bellugi, U., Bihrle, A., & Jones, W. (1996). Interaction between language and cognition: evidence from Williams syndrome. In J. H. Beitchman, N. Cohen, M. Konstantareas, & R. Tannock (Eds.), Language, learning and behavior disorders: developmental, biological, and clinical perspectives. (367-392). New York: Cambridge University Press. Stevens, T. & Karmiloff-Smith, A. (1997). Word learning in a special population: do individuals with Williams syndrome obey lexical constraints? Journal of Child Language, 24, 737-765. Wang, P. P., Doherty, S., Rourke, S. B., & Bellugi, U. (1995). Unique profile of visuo-perceptual skills in a genetic syndrome. Brain and Cognition, 29, 54-65. / This thesis presents a study on two lexical constraints in german children with Williams syndrome (WS). The lexicon ist known to be delayed in WS, however in adults the lexicon is said to be elaborated (Wang et al. 1995). This might be a hint for late developing language compenteces. Rossen et al. (1996) see a performance growth in fluency in WS children older than 11 years. The aim of the current study is to examine the lexical learning mechanisms in WS children in kindergarden age. Five WS children are matched to 97 normal children on chronological age. Two experiments (whole object constraint, mutual exclusivity constraints) are designed, following the argumentations of Markman (1989). The results show that both lexical constraints are active in WS children but act on different inputinformations than in other children. In the discussion, the detail preference hypothesis is drawn, which postulates for the first time a unique perceptual deficit which influences language acquisition without also implying a primary language disorder. Markman, E. (1989). Categorization and naming in children. Cambridge MA: MIT Press. Wang, P. P., Doherty, S., Rourke, S. B., & Bellugi, U. (1995). Unique profile of visuo-perceptual skills in a genetic syndrome. Brain and Cognition, 29, 54-65.

Multi-antenna relay beamforming is a promising candidate in the next generation wireless communication systems. The assumption of sum power constraint at the relay in previous work is often unrealistic in practice, since each antenna of the relay is limited by its own front-end power amplifier and thus has its own individual power constraint. In this thesis, given per-antenna power constraints, we obtain the semi-closed form solution for the optimal relay beamforming design in the two-hop amplify-and-forward relay beamforming and establish its duality with the point-to-point single-input multiple-output (SIMO) beamforming system. Simulation results show that the per-antenna power constraint case has much lower per-antenna peak power and much smaller variance of per-antenna power usage than the sum-power constraint case. A heuristic iterative algorithm to minimize the total power of relay network is proposed.

Multi-antenna relay beamforming is a promising candidate in the next generation wireless communication systems. The assumption of sum power constraint at the relay in previous work is often unrealistic in practice, since each antenna of the relay is limited by its own front-end power amplifier and thus has its own individual power constraint. In this thesis, given per-antenna power constraints, we obtain the semi-closed form solution for the optimal relay beamforming design in the two-hop amplify-and-forward relay beamforming and establish its duality with the point-to-point single-input multiple-output (SIMO) beamforming system. Simulation results show that the per-antenna power constraint case has much lower per-antenna peak power and much smaller variance of per-antenna power usage than the sum-power constraint case. A heuristic iterative algorithm to minimize the total power of relay network is proposed.

In electricity markets of modern electric power systems, many generation companies, as major market participants, aim to maximize their profits by supplying the electrical load in a competitive manner. This thesis is devoted to investigate the price based unit commitment problem which is used to optimize generation schedules of these companies in deregulated electricity markets. The solution algorithm developed is based on Dynamic Programming and Lagrange Relaxation methods and solves the optimization problem for a generation company having many generating units with different cost characteristics. Moreover, unit constraints including ramp-rate limits, minimum ON/OFF times, generation capacities of individual units and system constraints such as total energy limits, reserve requirements are taken into account in the problem formulation. The verification of the algorithm has been carried out by comparing the results of some sample cases with those in the literature. The effectiveness of the algorithm has been tested on several test systems. Finally, the possible utilization of the method by a generation company in Turkish Electricity Market to develop bidding strategies is also examined based on some case studies.

In this dissertation we study several non-convex and stochastic optimization problems. The common theme is the use of mixed-integer programming (MIP) techniques including valid inequalities and reformulation to solve these problems. We first study a strategic capacity planning model which captures the trade-off between the incentive to delay capacity installation to wait for improved technology and the need for some capacity to be installed to meet current demands. This problem is naturally formulated as a MIP with a bilinear objective. We develop several linear MIP formulations, along with classes of strong valid inequalities. We also present a specialized branch-and-cut algorithm to solve a compact concave formulation. Computational results indicate that these formulations can be used to solve large-scale instances. We next study methods for optimization with joint probabilistic constraints. These problems are challenging because evaluating solution feasibility requires multidimensional integration and the feasible region is not convex. We propose and analyze a Monte Carlo sampling scheme to simplify the probabilistic structure of such problems. Computational tests of the approach indicate that it can yield good feasible solutions and reasonable bounds on their quality. Next, we study a MIP formulation of the non-convex sample approximation problem. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. Computational results indicate that large-scale instances can be solved using the strengthened formulations. Finally, we study optimization problems with stochastic dominance constraints. A stochastic dominance constraint states that a random outcome which depends on the decision variables should stochastically dominate a given random variable. We present new formulations for both first and second order stochastic dominance which are significantly more compact than existing formulations. Computational tests illustrate the benefits of the new formulations.