Spelling suggestions: "subject:"constraint aptimization"" "subject:"constraint foptimization""
1 |
A novel approach to computer-aided configuration design based on constraint satisfaction paradigmLi, Jingxin 28 February 2005
The trend in todays manufacturing industry is changing from mass production to mass customization. The companies which win the markets are those which can deliver highly customized products at the fastest rate and allow for life-cycle participation of customers regardless of where they are and when they participate. One of the strategies for implementing the mass customization paradigm is to implement the product development according to the assemble-to-order (ATO) pattern. Under the ATO pattern, the design of a product becomes the determination of a configuration which contains a set of pre-developed components configuration design for short. The configuration design problem can be well treated as a constraint satisfaction problem (CSP). The mature methods are available for CSP, but there are several limitations with CSP for configuration design.
This thesis proposes a novel approach to configuration design. This approach is based on a CSP but adds a wrapper (product data model, PDM for short) over the CSP model. Consequently, both the customer and the other life cycle development programs only communicate with the PDM, and a more intelligent and user-friendly computer system for configuration design can then be implemented. Both the conceptual design and implementation of such a wrapper are discussed in this thesis. A computer prototype system for elevator design is developed for demonstrating the effectiveness of this approach.
|
2 |
A novel approach to computer-aided configuration design based on constraint satisfaction paradigmLi, Jingxin 28 February 2005 (has links)
The trend in todays manufacturing industry is changing from mass production to mass customization. The companies which win the markets are those which can deliver highly customized products at the fastest rate and allow for life-cycle participation of customers regardless of where they are and when they participate. One of the strategies for implementing the mass customization paradigm is to implement the product development according to the assemble-to-order (ATO) pattern. Under the ATO pattern, the design of a product becomes the determination of a configuration which contains a set of pre-developed components configuration design for short. The configuration design problem can be well treated as a constraint satisfaction problem (CSP). The mature methods are available for CSP, but there are several limitations with CSP for configuration design.
This thesis proposes a novel approach to configuration design. This approach is based on a CSP but adds a wrapper (product data model, PDM for short) over the CSP model. Consequently, both the customer and the other life cycle development programs only communicate with the PDM, and a more intelligent and user-friendly computer system for configuration design can then be implemented. Both the conceptual design and implementation of such a wrapper are discussed in this thesis. A computer prototype system for elevator design is developed for demonstrating the effectiveness of this approach.
|
3 |
Comparação de algoritmos para otimização de restrições distribuídas em um cenário de controle semafórico / Comparing distributed constraint optimization algorithms in a traffic control scenarioJunges, Robert January 2007 (has links)
Problemas de otimização de restrições distribuídas (DCOP - Distributed Constraint Optimization Problem) formam uma classe de problemas de grande interesse de estudo na ciência da computação em função da complexidadecomputacionaL O presente trabalho tem o objetivo de comparar os três algoritmos mais populares em DCOP (ADOPT, OptAPO e DPOP) em termos de eficiência computacional e de solução proposta. Para tal estudo, é utilizado como domínio um problema de controle semafórico. Esse tipo de problema de controle é de fundamental importânciapara que se tenha uma administração eficiente do fluxo de veículos em uma malha viária. Além disso, envolve muitas interdependências entre variáveis da rede, como ocupação das vias e tempos de sinal verde dos semáforos, para que sejam determinadas as melhores configurações de controle. Nesse sentido, as estratégias devem fornecer bons resultados em nível de aplicação, e também em nível de computação, no que diz respeito ao uso da infra-estrutura computacional disponível, o que casa perfeitamente com os objetivos das implementações de DCOP. Ao longo deste trabalho, os temas relacionados à coordenação em sistemas multiagentes, otimização de restrições e controle de semáforos são estudados. Os modelos DCOP são utilizados com a finalidade de comparar os algoritmos.No que diz respeito aos resultados, percebe-se uma melhora no controle, obtida com o uso dos algoritmos DCOP em relação ao uso de controle fixo sincronizado e não sincronizado. Isso é verificado em nível de utilização das vias da rede. Além disso, outro tipo de resultado é verificado na execução dos algoritmos, tratando de questões como o tempo de execução. Foi possível estabelecer um comparativo entre os algoritmos e frente ao aumento do problema em quantidade de semáforos. / Distributed Constraint Optimization Problems (DCOP) have a significant importance in ComputerScience, due to its computationalcomplexity. The objective of this work is to compare the three most popular algorithms for DCOP (ADOPT,OptAPO and DPOP) in terms of computational efficiency and quality of the proposed solution. In arder to do that, a trafficcontrol scenario is used. This kind of problem is very important when considering an efficientadministration of the trafficnetwork,which involvesa lot of interdependencies among variables such as the occupation of the links and the split of the lights. The control strategies should be able to provide good results in terms of the domain application and consider the computational infrastructure available,matching exactly the objectives of the DCOP implementations. The present work is related to multiagent systems, constraint optimization and traffic light controI. The DCOP models are used in order to perfarm the comparison among the algorithms. The results show that is possible to improve the efficiency of the control over the c1assicapproaches of fixed traffic light timing. This is verifiedconsidering the utilization leveIof the network and the occurrence of trafficjams. Besides that, some computational issues are considered to compare the algorithms, for instance, the execution time.
|
4 |
Comparação de algoritmos para otimização de restrições distribuídas em um cenário de controle semafórico / Comparing distributed constraint optimization algorithms in a traffic control scenarioJunges, Robert January 2007 (has links)
Problemas de otimização de restrições distribuídas (DCOP - Distributed Constraint Optimization Problem) formam uma classe de problemas de grande interesse de estudo na ciência da computação em função da complexidadecomputacionaL O presente trabalho tem o objetivo de comparar os três algoritmos mais populares em DCOP (ADOPT, OptAPO e DPOP) em termos de eficiência computacional e de solução proposta. Para tal estudo, é utilizado como domínio um problema de controle semafórico. Esse tipo de problema de controle é de fundamental importânciapara que se tenha uma administração eficiente do fluxo de veículos em uma malha viária. Além disso, envolve muitas interdependências entre variáveis da rede, como ocupação das vias e tempos de sinal verde dos semáforos, para que sejam determinadas as melhores configurações de controle. Nesse sentido, as estratégias devem fornecer bons resultados em nível de aplicação, e também em nível de computação, no que diz respeito ao uso da infra-estrutura computacional disponível, o que casa perfeitamente com os objetivos das implementações de DCOP. Ao longo deste trabalho, os temas relacionados à coordenação em sistemas multiagentes, otimização de restrições e controle de semáforos são estudados. Os modelos DCOP são utilizados com a finalidade de comparar os algoritmos.No que diz respeito aos resultados, percebe-se uma melhora no controle, obtida com o uso dos algoritmos DCOP em relação ao uso de controle fixo sincronizado e não sincronizado. Isso é verificado em nível de utilização das vias da rede. Além disso, outro tipo de resultado é verificado na execução dos algoritmos, tratando de questões como o tempo de execução. Foi possível estabelecer um comparativo entre os algoritmos e frente ao aumento do problema em quantidade de semáforos. / Distributed Constraint Optimization Problems (DCOP) have a significant importance in ComputerScience, due to its computationalcomplexity. The objective of this work is to compare the three most popular algorithms for DCOP (ADOPT,OptAPO and DPOP) in terms of computational efficiency and quality of the proposed solution. In arder to do that, a trafficcontrol scenario is used. This kind of problem is very important when considering an efficientadministration of the trafficnetwork,which involvesa lot of interdependencies among variables such as the occupation of the links and the split of the lights. The control strategies should be able to provide good results in terms of the domain application and consider the computational infrastructure available,matching exactly the objectives of the DCOP implementations. The present work is related to multiagent systems, constraint optimization and traffic light controI. The DCOP models are used in order to perfarm the comparison among the algorithms. The results show that is possible to improve the efficiency of the control over the c1assicapproaches of fixed traffic light timing. This is verifiedconsidering the utilization leveIof the network and the occurrence of trafficjams. Besides that, some computational issues are considered to compare the algorithms, for instance, the execution time.
|
5 |
Comparação de algoritmos para otimização de restrições distribuídas em um cenário de controle semafórico / Comparing distributed constraint optimization algorithms in a traffic control scenarioJunges, Robert January 2007 (has links)
Problemas de otimização de restrições distribuídas (DCOP - Distributed Constraint Optimization Problem) formam uma classe de problemas de grande interesse de estudo na ciência da computação em função da complexidadecomputacionaL O presente trabalho tem o objetivo de comparar os três algoritmos mais populares em DCOP (ADOPT, OptAPO e DPOP) em termos de eficiência computacional e de solução proposta. Para tal estudo, é utilizado como domínio um problema de controle semafórico. Esse tipo de problema de controle é de fundamental importânciapara que se tenha uma administração eficiente do fluxo de veículos em uma malha viária. Além disso, envolve muitas interdependências entre variáveis da rede, como ocupação das vias e tempos de sinal verde dos semáforos, para que sejam determinadas as melhores configurações de controle. Nesse sentido, as estratégias devem fornecer bons resultados em nível de aplicação, e também em nível de computação, no que diz respeito ao uso da infra-estrutura computacional disponível, o que casa perfeitamente com os objetivos das implementações de DCOP. Ao longo deste trabalho, os temas relacionados à coordenação em sistemas multiagentes, otimização de restrições e controle de semáforos são estudados. Os modelos DCOP são utilizados com a finalidade de comparar os algoritmos.No que diz respeito aos resultados, percebe-se uma melhora no controle, obtida com o uso dos algoritmos DCOP em relação ao uso de controle fixo sincronizado e não sincronizado. Isso é verificado em nível de utilização das vias da rede. Além disso, outro tipo de resultado é verificado na execução dos algoritmos, tratando de questões como o tempo de execução. Foi possível estabelecer um comparativo entre os algoritmos e frente ao aumento do problema em quantidade de semáforos. / Distributed Constraint Optimization Problems (DCOP) have a significant importance in ComputerScience, due to its computationalcomplexity. The objective of this work is to compare the three most popular algorithms for DCOP (ADOPT,OptAPO and DPOP) in terms of computational efficiency and quality of the proposed solution. In arder to do that, a trafficcontrol scenario is used. This kind of problem is very important when considering an efficientadministration of the trafficnetwork,which involvesa lot of interdependencies among variables such as the occupation of the links and the split of the lights. The control strategies should be able to provide good results in terms of the domain application and consider the computational infrastructure available,matching exactly the objectives of the DCOP implementations. The present work is related to multiagent systems, constraint optimization and traffic light controI. The DCOP models are used in order to perfarm the comparison among the algorithms. The results show that is possible to improve the efficiency of the control over the c1assicapproaches of fixed traffic light timing. This is verifiedconsidering the utilization leveIof the network and the occurrence of trafficjams. Besides that, some computational issues are considered to compare the algorithms, for instance, the execution time.
|
6 |
Estimating Costs of Reducing Environmental Emissions From a Dairy Farm: Multi-objective epsilon-constraint Optimization Versus Single Objective Constrained OptimizationEbadi, Nasim 08 July 2020 (has links)
Agricultural production is an important source of environmental emissions. While water quality concerns related to animal agriculture have been studied extensively, air quality issues have become an increasing concern. Due to the transfer of nutrients between air, water, and soil, emissions to air can harm water quality. We conduct a multi-objective optimization analysis for a representative dairy farm with two different approaches: nonlinear programming (NLP) and ϵ-constraint optimization to evaluate trade-offs among reduction of multiple pollutants including nitrogen (N), phosphorus (P), greenhouse gas (GHG), and ammonia. We evaluated twenty-six different scenar- ios in which we define incremental reductions of N, P, ammonia, and GHG from five to 25% relative to a baseline scenario. The farm entails crop production, livestock production (dairy and broiler), and manure management activities. Results from NLP optimization indicate that reducing P and ammonia emissions is relatively more expen- sive than N and GHG. This result is also confirmed by the ϵ-constraint optimization. However, the latter approach provides limited evidence of trade-offs among reduction of farm pollutants and net returns, while the former approach includes different re- duction scenarios that make trade-offs more evident. Results from both approaches indicate changes in crop rotation and land retirement are the best strategies to reduce N and P emissions while cow diet changes involving less forage represents the best strategy to reduce ammonia and GHG emissions. / Master of Science / Human activities often damage and deplete the environment. For instance, nutrient pollution into air and water, which mostly comes from agricultural and industrial activ- ities, results in water quality degradation. Thus, mitigating the detrimental impacts of human activities is an important step toward environmental sustainability. Reducing environmental impacts of nutrient pollution from agriculture is a complicated problem, which needs a comprehensive understanding of types of pollution and their reduction strategies. Reduction strategies need to be both feasible and financially viable. Con- sequently, practices must be carefully selected to allow farmers to maximize their net return while reducing pollution levels to reach a satisfactory level. Thus, this paper conducts a study to evaluate the trade-offs associated with farm net return and re- ducing the most important pollutants generated by agricultural activities. The results of this study show that reducing N and GHG emissions from a representative dairy farm is less costly than reducing P and ammonia emissions, respectively. In addition, reducing one pollutant may result in reduction of other pollutants. In general, for N and P emissions reduction land retirement and varying crop rotations are the most effective strategies. However, for reducing ammonia and GHG emissions focusing on cow diet changes involving less forage is the most effective strategy.
|
7 |
Semantics-based Summarization of Entities in Knowledge GraphsGunaratna, Kalpa 31 May 2017 (has links)
No description available.
|
8 |
Learning during search / Apprendre durant la recherche combinatoireArbelaez Rodriguez, Alejandro 31 May 2011 (has links)
La recherche autonome est un nouveau domaine d'intérêt de la programmation par contraintes, motivé par l'importance reconnue de l'utilisation de l'apprentissage automatique pour le problème de sélection de l'algorithme le plus approprié pour une instance donnée, avec une variété d'applications, par exemple: Planification, Configuration d'horaires, etc. En général, la recherche autonome a pour but le développement d'outils automatiques pour améliorer la performance d'algorithmes de recherche, e.g., trouver la meilleure configuration des paramètres pour un algorithme de résolution d'un problème combinatoire. Cette thèse présente l'étude de trois points de vue pour l'automatisation de la résolution de problèmes combinatoires; en particulier, les problèmes de satisfaction de contraintes, les problèmes d'optimisation de combinatoire, et les problèmes de satisfiabilité (SAT).Tout d'abord, nous présentons domFD, une nouvelle heuristique pour le choix de variable, dont l'objectif est de calculer une forme simplifiée de dépendance fonctionnelle, appelée dépendance-relaxée. Ces dépendances-relaxées sont utilisées pour guider l'algorithme de recherche à chaque point de décision.Ensuite, nous révisons la méthode traditionnelle pour construire un portefeuille d'algorithmes pour le problème de la prédiction de la structure des protéines. Nous proposons un nouveau paradigme de recherche-perpétuelle dont l'objectif est de permettre à l'utilisateur d'obtenir la meilleure performance de son moteur de résolution de contraintes. La recherche-perpétuelle utilise deux modes opératoires: le mode d'exploitation utilise le modèle en cours pour solutionner les instances de l'utilisateur; le mode d'exploration réutilise ces instances pour s'entraîner et améliorer la qualité d'un modèle d'heuristiques par le biais de l'apprentissage automatique. Cette deuxième phase est exécutée quand l'unit\'e de calcul est disponible (idle-time). Finalement, la dernière partie de cette thèse considère l'ajout de la coopération au cours d'exécution d'algorithmes de recherche locale parallèle. De cette façon, on montre que si on partage la meilleure configuration de chaque algorithme dans un portefeuille parallèle, la performance globale peut être considérablement amélioré. / Autonomous Search is a new emerging area in Constraint Programming, motivated by the demonstrated importance of the application of Machine Learning techniques to the Algorithm Selection Problem, and with potential applications ranging from planning and configuring to scheduling. This area aims at developing automatic tools to improve the performance of search algorithms to solve combinatorial problems, e.g., selecting the best parameter settings for a constraint solver to solve a particular problem instance. In this thesis, we study three different points of view to automatically solve combinatorial problems; in particular Constraint Satisfaction, Constraint Optimization, and SAT problems.First, we present domFD, a new Variable Selection Heuristic whose objective is to heuristically compute a simplified form of functional dependencies called weak dependencies. These weak dependencies are then used to guide the search at each decision point. Second, we study the Algorithm Selection Problem from two different angles. On the one hand, we review a traditional portfolio algorithm to learn offline a heuristics model for the Protein Structure Prediction Problem. On the other hand, we present the Continuous Search paradigm, whose objective is to allow any user to eventually get his constraint solver to achieve a top performance on their problems. Continuous Search comes in two modes: the functioning mode solves the user's problem instances using the current heuristics model; the exploration mode reuses these instances to training and improve the heuristics model through Machine Learning during the computer idle time. Finally, the last part of the thesis, considers the question of adding a knowledge-sharing layer to current portfolio-based parallel local search solvers for SAT. We show that by sharing the best configuration of each algorithm in the parallel portfolio on regular basis and aggregating this information in special ways, the overall performance can be greatly improved.
|
9 |
Optimizing Task Sequence and Cell Layout for Dual Arm Robot Assembly Using Constraint ProgrammingZhao, Zhengyang January 2015 (has links)
Nowadays, assembly robots are increasingly used in the manufacturing industry to replace or collaborate with human labors. This is the goal of the dual arm assembly robot developed by ABB. With the rapid upgrading in consumer electronics products, the lifetime of an assembly line could be only a few months. However, even for experienced programmers, to manually construct a good enough assembly sequence is time consuming, and the quality of the generated assembly sequence is not guaranteed. Moreover, a good robot assembly sequence is important to the throughput of an assembly line. For dual arm robots, it is also important to obtain a balance between the two arms, as well as handling scheduling conflicts and avoiding collisions in a crowded environment. In this master thesis, a program is produced to automatically generate the optimal assembly sequence for a class of real-world assembly cases. The solution also takes the layout of the assembly cell into account, thus constructing the best combination of cell layout, workload balancing, task sequence and task scheduling. The program is implemented using Google OR-Tools – an open-source support library for combinatorial optimization. A customized search strategy is proposed and a comparison between this strategy and the built-in search strategy of Google OR-Tools is done. The result shows that the used approach is effective for the problem study case. It takes about 4 minutes to find the optimal solution and 32 minutes to prove its optimality. In addition, the result also shows that the customized search strategy works consistently with good performance for different problem cases. Moreover, the customized strategy is more efficient than built-in search strategy in many cases. / Numera används monteringsrobotar alltmer inom tillverkningsindustrin för att ersätta eller samarbeta med människor. Detta är måluppgiften för den tvåarmiga monteringsroboten, YuMi, som utvecklats av ABB. Med den korta produktlivslängden för hemelektronikprodukter kan livslängden för en monteringslinje vara ett fåtal månader. Även för erfarna robotprogrammerare är det svårt och tidsödande att manuellt konstruera en tillräckligt bra monteringsordning, och dessutom kan resultatets kvalitet inte garanteras. En bra monteringsordning är nödvändig för genomströmningen i en monteringslinje. För tvåarmiga robotar, är det också viktigt att få en balans mellan de två armarna, samt hantering av schemakrockar och undvika kollisioner i en trång miljö. I detta examensarbete har ett program skrivits, som automatiskt genererar optimala lösningar för en klass av verkliga monteringsfall. Lösningen tar hänsyn till utformningen av monteringscellen och arrangerar cellen på bästa sätt, balanserar arbetsbelastningen, ordnar och tidsbestämmer uppgifter. Programmet använder sig av Google OR-Tools – ett öppet kodbibliotek för kombinatorisk optimering. Dessutom föreslås en skräddarsydd sökstrategi, som jämförs med Google OR-Tools inbyggda sökstrategi. Resultatet visar att den använda metoden är effektiv för problemtypen. Det tar ungefär 4 minuter att hitta den optimala lösningen och 32 minuter för att bevisa optimalitet. Dessutom visar resultatet att den anpassade sökstrategin konsekvent har en bra prestanda för olika problemfall. Dessutom är den anpassade strategin effektivare än den inbyggda sökstrategin i många fall.
|
10 |
Black Box Optimization Framework for Reinsurance of Large ClaimsMozayyan, Sina January 2022 (has links)
A framework for optimization of reinsurance strategy is proposed for an insurance company with several lines of business (LoB), maximizing the Economic Value of purchasing reinsurance. The economic value is defined as the sum of the average ceded loss, the deducted risk premium, and the reduction in the cost of capital. The framework relies on simulated large claims per LoB rather than specific distributions, which gives more degrees of freedom to the insurance company. Three models are presented, two non non-linear optimization models and a benchmark model. One non-linear optimization model is on individual LoB level and the other one is on company level with additional constraints using space bounded black box algorithms. The benchmark model is a Brute Force method using quantile discretization of potential retention levels, that helps to visualize the optimization surface. The best results are obtained by a two-stage optimization using a mixture of global and local optimization algorithms. The economic value is maximized by 30% and reinsurance premium is halved if the optimization is made at the company level, by putting more emphasis on reduction in the cost of capital and less to average ceded loss. The results indicate an over-fitting when using VaR as the risk measure, impacting reduction in the cost of capital. As an alternative, Average VaR is recommended being numerically more robust.
|
Page generated in 0.2157 seconds