No description available.

No description available.

We hypothesize and confirm that probabilistic reasoning is closely related to constraint satisfaction at a formal level, and that this relationship yields effective algorithms for guiding constraint satisfaction and constraint optimization solvers. By taking a unified view of probabilistic inference and constraint reasoning in terms of graphical models, we first associate a number of formalisms and techniques between the two areas. For instance, we characterize search and inference in constraint reasoning as summation and multiplication (or disjunction and conjunction) in the probabilistic space; necessary but insufficient consistency conditions for solutions to constraint problems (like arc-consistency) mirror approximate objective functions over probability distributions (like the Bethe free energy); and the polytope of feasible points for marginal probabilities represents the linear relaxation of a particular constraint satisfaction problem. While such insights synthesize an assortment of existing formalisms from varied research communities, they also yield an entirely novel set of “bias estimation” techniques that contribute to a growing body of research on applying probabilistic methods to constraint problems. In practical terms, these techniques estimate the percentage of solutions to a constraint satisfaction or optimization problem wherein a given variable is assigned a given value. By devising search methods that incorporate such information as heuristic guidance for variable and value ordering, we are able to outperform existing solvers on problems of interest from constraint satisfaction and constraint optimization–-as represented here by the SAT and MaxSAT problems. Further, for MaxSAT we present an equivalent transformation” process that normalizes the weights in constraint optimization problems, in order to encourage prunings of the search tree during branch-and-bound search. To control such computationally expensive processes, we determine promising situations for using them throughout the course of an individual search process. We accomplish this using a reinforcement learning-based control module that seeks a principled balance between the exploration of new strategies and the exploitation of existing experiences.

Basé sur la théorie de cycle endogène, cette thèse de doctorat étudie la question d'instabilité macro-économique et des fluctuations endogènes dans trois économies distinctes : I) avec des effets externes en consommation dans un modèle de Ramsey; II) avec des effets externes en loisir dans un modèle de générations imbriquées; et III) avec imperfection de marché du crédit dans un modèle de croissance endogène monétaire. / Based on the endogenous cycle theory, this doctoral thesis studies the issue of macroeconomic instability and fluctuations in three distinct economies: i) with consumption externalities in Ramsey model; ii) with leisure externalities in an overlapping generations model; and iii) with credit market imperfection in a monetary endogenous growth model.

by Wang Jun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 82-86). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- The polynomial zero-one programming problem --- p.2 / Chapter 1.3 --- Motivation --- p.3 / Chapter 1.4 --- Thesis outline --- p.4 / Chapter 2 --- Literature Survey --- p.6 / Chapter 2.1 --- Lawler and Bell's method --- p.7 / Chapter 2.2 --- The covering relaxation algorithm for polynomial zero-one pro- gramming --- p.8 / Chapter 2.3 --- The method of reducing polynomial integer problems to linear zero- one problems --- p.9 / Chapter 2.4 --- Pseudo-boolean programming --- p.11 / Chapter 2.5 --- The Balasian-based algorithm for polynomial zero-one programming --- p.12 / Chapter 2.6 --- The hybrid algorithm for polynomial zero-one programming --- p.12 / Chapter 3 --- The Balasian-based Algorithm --- p.14 / Chapter 3.1 --- The additive algorithm for linear zero-one programming --- p.15 / Chapter 3.2 --- Some notations and definitions referred to the Balasian-based al- gorithm --- p.17 / Chapter 3.3 --- Identification of all the feasible solutions to the master problem --- p.18 / Chapter 3.4 --- Consistency check of the feasible partial solutions --- p.19 / Chapter 4 --- The p-norm Surrogate Constraint Method --- p.21 / Chapter 4.1 --- Introduction --- p.21 / Chapter 4.2 --- Numerical example --- p.23 / Chapter 5 --- The P-norm Surrogate-constraint Algorithm --- p.26 / Chapter 5.1 --- Main ideas --- p.26 / Chapter 5.2 --- The standard form of the polynomial zero-one programming problem --- p.27 / Chapter 5.3 --- Definitions and notations --- p.29 / Chapter 5.3.1 --- Partial solution in x --- p.29 / Chapter 5.3.2 --- Free term --- p.29 / Chapter 5.3.3 --- Completion --- p.29 / Chapter 5.3.4 --- Feasible partial solution --- p.30 / Chapter 5.3.5 --- Consistent partial solution --- p.30 / Chapter 5.3.6 --- Partial solution in y --- p.30 / Chapter 5.3.7 --- Free variable --- p.31 / Chapter 5.3.8 --- Augmented solution in x --- p.31 / Chapter 5.4 --- Solution concepts --- p.33 / Chapter 5.4.1 --- Fathoming --- p.33 / Chapter 5.4.2 --- Backtracks --- p.41 / Chapter 5.4.3 --- Determination of the optimal solution in y --- p.42 / Chapter 5.5 --- Solution algorithm --- p.42 / Chapter 6 --- Numerical Examples --- p.46 / Chapter 6.1 --- Solution process by the new algorithm --- p.46 / Chapter 6.1.1 --- Example 5 --- p.46 / Chapter 6.1.2 --- Example 6 --- p.57 / Chapter 6.2 --- Solution process by the Balasian-based algorithm --- p.61 / Chapter 6.3 --- Comparison between the p-norm surrogate constraint algorithm and the Balasian-based algorithm --- p.71 / Chapter 7 --- Application to the Set Covering Problem --- p.74 / Chapter 7.1 --- The set covering problem --- p.74 / Chapter 7.2 --- Solving the set covering problem by using the new algorithm . .。 --- p.75 / Chapter 8 --- Conclusions and Future Work --- p.80 / Bibliography --- p.82

We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The <em>global cardinality constraint</em> (GCC) ensures that a value <em>v</em> is assigned to at least <em>l_v</em> variables and to at most <em>u_v</em> variables among a set of given variables where <em>l_v</em> and <em>u_v</em> are non-negative integers such that <em>l_v</em> &le; <em>u_v</em>. The Inter-Distance constraint ensures that all variables, among a set of variables <em>x</em>₁, . . . , <em>x_n</em>, are pairwise distant from <em>p</em>, i. e. |<em>x_i</em> - <em>x_j</em>| &ge; <em>p</em> for all <em>i</em> &ne; <em>j</em>. The All-Different constraint, the GCC, and the Inter-Distance constraint are largely used in scheduling problems. For instance, in scheduling problems where tasks with unit processing time compete for a single resource, we have an All-Different constraint on the starting time variables. When there are <em>k</em> resources, we have a GCC with <em>l_v</em> = 0 and <em>u_v</em> = <em>k</em> over all starting time variables. Finally, if tasks have processing time <em>t</em> and compete for a single resource, we have an Inter-Distance constraint with <em>p</em> = <em>t</em> over all starting time variables. We present new propagators for the All-Different constraint, the GCC, and the Inter-Distance constraint i. e. , new filtering algorithms that reduce the search space according to these constraints. For a given consistency, our propagators outperform previous propagators both in practice and in theory. The gains in performance are achieved through judicious use of advanced data structures combined with novel results on the structural properties of the constraints.

We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The <em>global cardinality constraint</em> (GCC) ensures that a value <em>v</em> is assigned to at least <em>l_v</em> variables and to at most <em>u_v</em> variables among a set of given variables where <em>l_v</em> and <em>u_v</em> are non-negative integers such that <em>l_v</em> &le; <em>u_v</em>. The Inter-Distance constraint ensures that all variables, among a set of variables <em>x</em>₁, . . . , <em>x_n</em>, are pairwise distant from <em>p</em>, i. e. |<em>x_i</em> - <em>x_j</em>| &ge; <em>p</em> for all <em>i</em> &ne; <em>j</em>. The All-Different constraint, the GCC, and the Inter-Distance constraint are largely used in scheduling problems. For instance, in scheduling problems where tasks with unit processing time compete for a single resource, we have an All-Different constraint on the starting time variables. When there are <em>k</em> resources, we have a GCC with <em>l_v</em> = 0 and <em>u_v</em> = <em>k</em> over all starting time variables. Finally, if tasks have processing time <em>t</em> and compete for a single resource, we have an Inter-Distance constraint with <em>p</em> = <em>t</em> over all starting time variables. We present new propagators for the All-Different constraint, the GCC, and the Inter-Distance constraint i. e. , new filtering algorithms that reduce the search space according to these constraints. For a given consistency, our propagators outperform previous propagators both in practice and in theory. The gains in performance are achieved through judicious use of advanced data structures combined with novel results on the structural properties of the constraints.

Diese Arbeit befasst sich mit der Entwicklung einer Applikation, welche Infrastrukturdaten über Eisenbahnnetze generiert. Dabei bildet die Erzeugung der topologischen Informationen den Schwerpunkt dieser Arbeit. Der Anwender charakterisiert hierfür vorab das gewünschte Eisenbahnnetz, wobei die geforderten Eigenschaften die Randbedingungen darstellen, die bei der Synthese zu beachten sind. Zur Einhaltung dieser Bedingungen wird die Constraint-Programmierung eingesetzt, welche durch ihr spezielles Programmierparadigma konsistente Lösungen effizient erzeugt. Dies wird u.a. durch die Nachnutzung so genannter globaler Constraints erreicht. Aus diesem Grund wird insbesondere auf den Einsatz der Constraint-Programmierung bei der Modellierung und Implementierung der Applikation eingegangen. / This work deals with the development of an application, which generates infrastructure data of railway networks. The focus of this work concentrates on the generation process of topological information. As input for the application a characterization of the intended railway network is given as attributes, which are handled as constraints in the generation process. To satisfy these restrictions constraint programming, a special programming paradigm, which is able to search efficently consistent solutions, is applied. In particular, the use of so-called global constraints improves the computation. For that reason the role of constraint-programming in modelling and implementing these application is discussed in more detail.

We hypothesize and confirm that probabilistic reasoning is closely related to constraint satisfaction at a formal level, and that this relationship yields effective algorithms for guiding constraint satisfaction and constraint optimization solvers. By taking a unified view of probabilistic inference and constraint reasoning in terms of graphical models, we first associate a number of formalisms and techniques between the two areas. For instance, we characterize search and inference in constraint reasoning as summation and multiplication (or disjunction and conjunction) in the probabilistic space; necessary but insufficient consistency conditions for solutions to constraint problems (like arc-consistency) mirror approximate objective functions over probability distributions (like the Bethe free energy); and the polytope of feasible points for marginal probabilities represents the linear relaxation of a particular constraint satisfaction problem. While such insights synthesize an assortment of existing formalisms from varied research communities, they also yield an entirely novel set of “bias estimation” techniques that contribute to a growing body of research on applying probabilistic methods to constraint problems. In practical terms, these techniques estimate the percentage of solutions to a constraint satisfaction or optimization problem wherein a given variable is assigned a given value. By devising search methods that incorporate such information as heuristic guidance for variable and value ordering, we are able to outperform existing solvers on problems of interest from constraint satisfaction and constraint optimization–-as represented here by the SAT and MaxSAT problems. Further, for MaxSAT we present an equivalent transformation” process that normalizes the weights in constraint optimization problems, in order to encourage prunings of the search tree during branch-and-bound search. To control such computationally expensive processes, we determine promising situations for using them throughout the course of an individual search process. We accomplish this using a reinforcement learning-based control module that seeks a principled balance between the exploration of new strategies and the exploitation of existing experiences.

Lic.-avh. Västerås : Mälardalens högskola, 2004. / S. 129-136: Bibliografi.