A incerteza é um elemento fundamental da realidade. Então, torna-se natural a busca por métodos que nos permitam representar o desconhecido em termos matemáticos. Esses problemas originam uma grande classe de programas probabilísticos reconhecidos como modelos de programação estocástica. Eles são mais realísticos que os modelos determinísticos, e tem por objetivo incorporar a incerteza em suas definições. Essa tese aborda os problemas probabilísticos da classe de problemas de multi-estágio com incerteza e com restrições probabilísticas e com restrições probabilísticas conjuntas. Inicialmente, nós propomos um modelo de administração de ativos e passivos multi-estágio estocástico para a indústria de fundos de pensão brasileira. Nosso modelo é formalizado em conformidade com a leis e políticas brasileiras. A seguir, dada a relevância dos dados de entrada para esses modelos de otimização, tornamos nossa atenção às diferentes técnicas de amostragem. Elas compõem o processo de discretização desses modelos estocásticos Nós verificamos como as diferentes metodologias de amostragem impactam a solução final e a alocação do portfólio, destacando boas opções para modelos de administração de ativos e passivos. Finalmente, nós propomos um “framework” para a geração de árvores de cenário e otimização de modelos com incerteza multi-estágio. Baseados na tranformação de Knuth, nós geramos a árvore de cenários considerando a representação filho-esqueda, irmão-direita o que torna a simulação mais eficiente em termos de tempo e de número de cenários. Nós também formalizamos uma reformulação do modelo de administração de ativos e passivos baseada na abordagem extensiva implícita para o modelo de otimização. Essa técnica é projetada pela definição de um processo de filtragem com “bundles”; e codifciada com o auxílio de uma linguagem de modelagem algébrica. A eficiência dessa metodologia é testada em um modelo de administração de ativos e passivos com incerteza com restrições probabilísticas conjuntas. Nosso framework torna possível encontrar a solução ótima para árvores com um número razoável de cenários. / Uncertainty is a key element of reality. Thus, it becomes natural that the search for methods allows us to represent the unknown in mathematical terms. These problems originate a large class of probabilistic programs recognized as stochastic programming models. They are more realistic than deterministic ones, and their aim is to incorporate uncertainty into their definitions. This dissertation approaches the probabilistic problem class of multistage stochastic problems with chance constraints and joint-chance constraints. Initially, we propose a multistage stochastic asset liability management (ALM) model for a Brazilian pension fund industry. Our model is formalized in compliance with the Brazilian laws and policies. Next, given the relevance of the input parameters for these optimization models, we turn our attention to different sampling models, which compose the discretization process of these stochastic models. We check how these different sampling methodologies impact on the final solution and the portfolio allocation, outlining good options for ALM models. Finally, we propose a framework for the scenario-tree generation and optimization of multistage stochastic programming problems. Relying on the Knuth transform, we generate the scenario trees, taking advantage of the left-child, right-sibling representation, which makes the simulation more efficient in terms of time and the number of scenarios. We also formalize an ALM model reformulation based on implicit extensive form for the optimization model. This technique is designed by the definition of a filtration process with bundles, and coded with the support of an algebraic modeling language. The efficiency of this methodology is tested in a multistage stochastic ALM model with joint-chance constraints. Our framework makes it possible to reach the optimal solution for trees with a reasonable number of scenarios.

The demand for computing power and performance in real-time embedded systems is continuously increasing since new customer requirements and more advanced features are appearing every day. To support these functionalities and handle them in a more efficient way, multi-core computing platforms are introduced. These platforms allow for parallel execution of tasks on multiple cores, which in addition to its benefits to the system's performance introduces a major problem regarding the timing predictability of the system. That problem is reflected in unpredictable inter-core interferences, which occur due to shared resources among the cores, such as the system bus. This thesis investigates the application of different optimization techniques for the offline scheduling of tasks on the individual cores, together with a global scheduling policy for the access to the shared bus. The main effort of this thesis focuses on optimizing the inter-core data propagation delays which can provide a new way of creating optimized schedules. For that purpose, Constraint Programming optimization techniques are employed and a Phased Execution Model of the tasks is assumed. Also, in order to enforce end-to-end timing constraints that are imposed on the system, job-level dependencies are generated prior and subsequently applied during the scheduling procedure. Finally, an experiment with a large number of test cases is conducted to evaluate the performance of the implemented scheduling approach. The obtained results show that the method is applicable for a wide spectrum of abstract systems with variable requirements, but also open for further improvement in several aspects.

One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems

<p>Quite often modelers with constraint programming (CP) use the same modelling patterns for different problems, possibly from different domains. This results in recurring idioms in constraint programs. Our approach can be seen as a three-step approach. First, we identify some of these recurring patterns in constraint programs. Second, we propose a general way of describing these patterns by introducing proper constructs that would cover a wide range of applications. Third, we propose automating the process of reproducing these idioms from these higher-level descriptions. The whole process can be seen as a way of encapsulating some of the expertise and knowledge often used by CP modelers and making it available in much simpler forms. Doing so, we are able to extend current CP languages with high-level abstractions that open doors for automation of some of the modelling processes.</p><p>In particular, we introduce function variables and allow the statement of constraints on these variables using function operations. A <i>function variable</i> is a decision variable that can take a value from a set of functions as opposed to an <i>integer variable</i> that ranges over integers, or a <i>set variable</i> that ranges over a set of sets. We show that a function variable can be mapped into different representations in terms of integer and set variables, and illustrate how to map constraints stated on a function variable into constraints on integer and set variables. As a result, a function model expressed using function variables opens doors to the automatic generation of alternate CP models. These alternate models either use a different variable representation, or have extra implied constraints, or employ different constraint formulation, or combine different models that are linked using channelling constraints. A number of heuristics are also developed that allow the comparison of different constraint formulations. Furthermore, we present an extensive theoretical comparison of models of injection problems supported by asymptotic and empirical studies. Finally, a practical modelling tool that is built based on a high-level language that allows function variables is presented and evaluated. The tool helps users explore different alternate CP models starting from a function model that is easier to develop, understand, and maintain.</p>

<p>Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. Existing methods have difficulty in dealing with the super-exponential number of symmetries in a problem with row and column symmetry. We therefore propose some ordering constraints which can effectively break such symmetries. To use these constraints in practice, we develop some efficient linear time propagators. We demonstrate the effectiveness of these symmetry breaking ordering constraints on a wide range of problems. We also show how such ordering constraints can be used to deal with partial symmetries, as well as value symmetries.</p>

Quite often modelers with constraint programming (CP) use the same modelling patterns for different problems, possibly from different domains. This results in recurring idioms in constraint programs. Our approach can be seen as a three-step approach. First, we identify some of these recurring patterns in constraint programs. Second, we propose a general way of describing these patterns by introducing proper constructs that would cover a wide range of applications. Third, we propose automating the process of reproducing these idioms from these higher-level descriptions. The whole process can be seen as a way of encapsulating some of the expertise and knowledge often used by CP modelers and making it available in much simpler forms. Doing so, we are able to extend current CP languages with high-level abstractions that open doors for automation of some of the modelling processes. In particular, we introduce function variables and allow the statement of constraints on these variables using function operations. A function variable is a decision variable that can take a value from a set of functions as opposed to an integer variable that ranges over integers, or a set variable that ranges over a set of sets. We show that a function variable can be mapped into different representations in terms of integer and set variables, and illustrate how to map constraints stated on a function variable into constraints on integer and set variables. As a result, a function model expressed using function variables opens doors to the automatic generation of alternate CP models. These alternate models either use a different variable representation, or have extra implied constraints, or employ different constraint formulation, or combine different models that are linked using channelling constraints. A number of heuristics are also developed that allow the comparison of different constraint formulations. Furthermore, we present an extensive theoretical comparison of models of injection problems supported by asymptotic and empirical studies. Finally, a practical modelling tool that is built based on a high-level language that allows function variables is presented and evaluated. The tool helps users explore different alternate CP models starting from a function model that is easier to develop, understand, and maintain.

Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. Existing methods have difficulty in dealing with the super-exponential number of symmetries in a problem with row and column symmetry. We therefore propose some ordering constraints which can effectively break such symmetries. To use these constraints in practice, we develop some efficient linear time propagators. We demonstrate the effectiveness of these symmetry breaking ordering constraints on a wide range of problems. We also show how such ordering constraints can be used to deal with partial symmetries, as well as value symmetries.

In this thesis, we define a new problem area for assembly lines. In the literature, there are various studies on assembly line balancing, but none of them consider multi-manned tasks, task to which at least two operators have to be assigned. Two mathematical models and one constraint programming model are developed for both Type-I and Type-II ALB problems. The objective of Type-I problem is to minimize the number of stations whereas the objective of Type-II problem is to minimize the cycle time. In addition to this, valid inequalities are introduced to make models more efficient. Moreover, heuristic algorithms for both types are developed for large-sized problems. All formulations are applied to a real case study and then experimental analysis are conducted for all formulations to see the effects of problem parameters on performance measures. Exact models are compared each other and performance of heuristic algorithms are compared against the lower bounds.

Thesis (M. Sc.)--University of Canterbury, 2009. / Typescript (photocopy). "January 2009." Includes bibliographical references (leaves 110-115). Also available via the World Wide Web.

Thesis (Ph. D.)--University of Oregon, 2001. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 124-127). Also available for download via the World Wide Web; free to University of Oregon users.