Dissertations / Theses on the topic 'Constraint programming'
To see the other types of publications on this topic, follow the link: Constraint programming.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Constraint programming.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Duong, Khanh-Chuong. "Constrained clustering by constraint programming." Thesis, Orléans, 2014. http://www.theses.fr/2014ORLE2049/document.
Full textAbstract:
La classification non supervisée, souvent appelée par le terme anglais de clustering, est une tâche importante en Fouille de Données. Depuis une dizaine d'années, la classification non supervisée a été étendue pour intégrer des contraintes utilisateur permettant de modéliser des connaissances préalables dans le processus de clustering. Différents types de contraintes utilisateur peuvent être considérés, des contraintes pouvant porter soit sur les clusters, soit sur les instances. Dans cette thèse, nous étudions le cadre de la Programmation par Contraintes (PPC) pour modéliser les tâches de clustering sous contraintes utilisateur. Utiliser la PPC a deux avantages principaux : la déclarativité, qui permet d'intégrer aisément des contraintes utilisateur et la capacité de trouver une solution optimale qui satisfait toutes les contraintes (s'il en existe). Nous proposons deux modèles basés sur la PPC pour le clustering sous contraintes utilisateur. Les modèles sont généraux et flexibles, ils permettent d'intégrer des contraintes d'instances must-link et cannot-link et différents types de contraintes sur les clusters. Ils offrent également à l'utilisateur le choix entre différents critères d'optimisation. Afin d'améliorer l'efficacité, divers aspects sont étudiés. Les expérimentations sur des bases de données classiques et variées montrent qu'ils sont compétitifs par rapport aux approches exactes existantes. Nous montrons que nos modèles peuvent être intégrés dans une procédure plus générale et nous l'illustrons par la recherche de la frontière de Pareto dans un problème de clustering bi-critère sous contraintes utilisateurCluster analysis is an important task in Data Mining with hundreds of different approaches in the literature. Since the last decade, the cluster analysis has been extended to constrained clustering, also called semi-supervised clustering, so as to integrate previous knowledge on data to clustering algorithms. In this dissertation, we explore Constraint Programming (CP) for solving the task of constrained clustering. The main principles in CP are: (1) users specify declaratively the problem in a Constraint Satisfaction Problem; (2) solvers search for solutions by constraint propagation and search. Relying on CP has two main advantages: the declarativity, which enables to easily add new constraints and the ability to find an optimal solution satisfying all the constraints (when there exists one). We propose two models based on CP to address constrained clustering tasks. The models are flexible and general and supports instance-level constraints and different cluster-level constraints. It also allows the users to choose among different optimization criteria. In order to improve the efficiency, different aspects have been studied in the dissertation. Experiments on various classical datasets show that our models are competitive with other exact approaches. We show that our models can easily be embedded in a more general process and we illustrate this on the problem of finding the Pareto front of a bi-criterion optimization process
2
Achterberg, Tobias. "Constraint integer programming /." München : Verl. Dr. Hut, 2008. http://bvbr.bib-bvb.de:8991/F?func=service&doc_library=BVB01&doc_number=017108806&line_number=0001&func_code=DB_RECORDS&service_type=MEDIA.
Full text
3
Achterberg, Tobias. "Constraint integer programming." München Verl. Dr. Hut, 2007. http://d-nb.info/992163366/04.
Full text
4
Jefferson, Christopher. "Representations in constraint programming." Thesis, University of York, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.445465.
Full text
5
McDonald, Iain. "Symmetry in constraint programming." Thesis, University of St Andrews, 2004. http://hdl.handle.net/10023/14983.
Full textAbstract:
Constraint programming is an invaluable tool for solving many of the complex NP-complete problems that we need solutions to. These problems can be easily described as Constraint Satisfaction Problems (CSPs) and then passed to constraint solvers: complex pieces of software written to solve general CSPs efficiently. Many of the problems we need solutions to are real world problems: planning (e.g. vehicle routing), scheduling (e.g. job shop schedules) and timetabling problems (e.g. staff rotas) to name but a few. In the real world, we place structure on objects to make them easier to deal with. This manifests itself as symmetry. The symmetry in these real world problems make them easier to deal with for humans. However, they lead to a great deal of redundancy when using computational methods of problem solving. Thus, this thesis examines some of the many aspects of utilising the symmetry of CSPs to reduce the amount of computation needed by constraint solvers. In this thesis we look at the ease of use of previous symmetry breaking methods. We introduce a new and novel method of describing the symmetries of CSPs. We look at previous methods of symmetry breaking and show how we can drastically reduce their computation while still breaking all symmetry. We give the first detailed investigation into the behaviour of breaking only subsets of all symmetry. We look at how this affects the performance of constraint solvers before discovering the properties of a good symmetry. We then present an original method for choosing the best symmetries to use. Finally, we look at areas of redundant computation in constraint solvers that no other research has examined. New ways of dealing with this redundancy are proposed with results of an example implementation which improves efficiency by several orders of magnitude.
6
Backeman, Peter. "Propagating the nVector Constraint : Haplotype Inference using Constraint Programming." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-211862.
Full textAbstract:
Genetics research is a wide field and needs computer aid in many different areas. One such problem is the haplotype inference problem by pure parsimony (HIPP). In this thesis the HIPP problem is attacked with a constraint programming (CP) model based on the nVector constraint, for which a new propagator is designed. The results show that the current state-of-the-art model based on SAT-solvers are in general the most efficient, but that the CP approach in some cases finds a better solution when time is limited.
7
Hnich, Brahim. "Function Variables for Constraint Programming." Doctoral thesis, Uppsala University, Department of Information Science, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3143.
Full textAbstract:
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.
8
Jägare, Peter. "Airspace Sectorisation using Constraint Programming." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-155783.
Full textAbstract:
Given a set of cells and a set of flight routes passing through these cells, we need to cluster cells into a given number of sectors, ensuring an even workload over all sectors, and fulfilling several other constraints on the wellformedness of sectors. The sectorisation is done by using constraint programming. Several propagators are designed to ensure the correctness of the sectorisation.
9
Olive, Xavier. "Symmetries in Distributed Constraint Programming." 京都大学 (Kyoto University), 2011. http://hdl.handle.net/2433/142134.
Full text
10
Wetsel, Gerhard. "Abductive and constraint logic programming." Thesis, Imperial College London, 1997. http://hdl.handle.net/10044/1/7212.
Full text
11
Edqvist, Samuel. "Scheduling Physicians using Constraint Programming." Thesis, Uppsala universitet, Avdelningen för datalogi, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-139606.
Full text
12
Olarte, Carlos. "Universal Temporal Concurrent Constraint Programming." Phd thesis, Palaiseau, Ecole polytechnique, 2009. http://pastel.archives-ouvertes.fr/pastel-00005492/en/.
Full text
13
Yang, Xiangxiu. "Examination scheduling by constraint programming." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/MQ65594.pdf.
Full text
14
Petrie, Karen E. "Constraint programming, search and symmetry." Thesis, University of Huddersfield, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.430277.
Full text
15
Garara, Ilyass. "Tourist Scheduler Using Constraint Programming." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-306959.
Full textAbstract:
Planning a trip in present time still requires a significant amount of time and effort. With the absence of a single service that manages the planning aspect of a trip, tourists have to explore multiple sources of data, both online and offline, in order to prepare their schedules. Therefore, the following master thesis project introduces a system that generates a schedule for tourists who would like to visit the city of Stockholm. The system communicates with a mobile application to receive user-defined data such as mobility, budget and points of interest in order to find the best schedule by combining the efficiency and flexibility of constraint programming with real-time data sources and a routing algorithm.
16
Wang, Tianze. "Machine Learning for Constraint Programming." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-254660.
Full textAbstract:
It is well established that designing good heuristics for solving Constraint Programming models requires years of domain experience and a huge amount of trial and error. In this thesis project, we conduct an empirical study of whether Machine Learning and Deep Learning techniques have the potential to help the design of constraint solving heuristics.Specifically, this thesis project examines the potential of Machine Learning and Deep Learning models for the regression task of predicting the makespan and solving time of a Job-Shop Scheduling Problem without actually solving the given Job-Shop Scheduling Problem instance. Several Machine Learning models are tested with manually designed features as input. Different Deep Learning architectures are explored with either just the Job-Shop Scheduling Problem instance as input or with an additional input of the previously designed features.××Results of the experiments justify the potential of several proposed models in predicting the makespan and solving time. For predicting the makespan (unit: machine time unit), the best Random Forest regression model achieves a Mean Squared Error of 0.78 on the test set. The best Deep Learning model achieves a Mean Squared Error of 0.74 on the test set. For predicting the solving time (unit: milliseconds) of a Job-Shop Scheduling Problem, the best Random Forest regression model achieves a Mean Squared Error of 2.12 107 on the test set. The best Deep Learning model achieves a Mean Squared Error of 5.19 107 on the test set.Discussions of the reason behind the difference of different Machine Learning and Deep Learning models are provided and future directions are proposed.Det är väl etablerat att det kräver många års erfarenhet av domänexpertis och mycket experimentell felsökning för att utforma en bra sökheuristik för villkorsprogrammeringsmodeller. I denna avhandling beskriver vi genomförandet av en empirisk studie med syftet att utreda potentialen av maskininlärningstekniker för att underlätta framtagandet av villkorsprogrammeringslösare.Mer specifikt undersöker vi maskininlärningsmodellers regressionsförmåga att förutse makespanöch lösningstid för "Job-Shop Scheduling Problem"utan att för den delen lösa den givna "Job-Shop Scheduling Problem"instansen. Flertalet maskininlärningsmodeller testas med manuellt framtagna särdrag som indata. Olika djupmaskininlärningsarkitekturer utforskas med antingen bara "Job-Shop Scheduling Problem-instanser som indata eller med ytterliggare indata i form av de manuellt framtagna särdragen.××Experimentresultaten motiverar användandet av flertalet av de föreslagna maskininlärningsmodellerna för att förutse makespanöch lösningstid. För förutsägandet av makespan"(enhet: maskintidsenhet) uppnår den bästa Random Forestregressionsmodellen ett medelkvadratfel på 0,78 på testdatamängden. Den bästa djupmaskininlärningsmodellen uppnår ett medelkvadratfel på 0,74 på testdatamängden. För förutsägandet av lösningstiden (enhet: millisekund) av "Job-Shop Scheduling Problem"uppnår den bästa Random Forestregressionsmodellen ett medelkvadratfel på 2.12 107 på testdatamängden. Den bästa djupmaskininlärningsmodellen uppnår ett medelkvadratfel på 5.19 107 på testdatamängden.Skillnadsorsakerna rörande de olika maskininlärningsmodellernas prestanda diskuteras i avhandlingen samt framtida forskningsinriktningar.
17
Amadini, Roberto <1984>. "Portfolio Approaches in Constraint Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6933/1/thesis.pdf.
Full textAbstract:
Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance.
In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core.
We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.
18
Amadini, Roberto <1984>. "Portfolio Approaches in Constraint Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6933/.
Full textAbstract:
Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance.
In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core.
We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.
19
Liu, Tong <1988>. "Innovative Applications of Constraint Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amsdottorato.unibo.it/9068/1/main.pdf.
Full textAbstract:
Constraint programming (CP) is a declarative paradigm that enables us to model a problem in the form of constraints to be satisfied. It offers powerful constraint solvers which, by implementing general-purpose search techniques, are fast and robust to address complex constraint models automatically. Constraint programming has attracted the attention of people from various domains. By separating the definition of a problem from its solution, it is more natural for people to implement the program directly from the problem specification, reducing the cost of development and future maintenance significantly. Furthermore, CP provides the flexibility of choosing a suitable solver for a problem of a given nature, which overcomes the limitations of a unique solver. Thanks to this, CP has allowed many non-domain experts to solve emerging problems efficiently.
This thesis studies the innovative applications of CP by examining two topics: constraint modeling for several novel problems, and automatic solver selection. For the modeling, we explored two case studies, namely the (sub)group activity optimization problem, and the service function chaining deployment problem that comes from the Software Defined Network (SDN) domain. Concerning the solver selection, we improved an algorithm selection technique called “SUNNY”, which generates a schedule of solvers for a given problem instance. In this work, we demonstrate with empirical experiments that the procedure we have designed to configure SUNNY parameters is effective, and it makes SUNNY scalable to an even broader range of algorithm selection problems not restricted to CP.
20
Bistarelli, Stefano. "Semirings for soft constraint solving and programming /." Berlin [u.a.] : Springer, 2004. http://www.loc.gov/catdir/enhancements/fy0818/2004044967-d.html.
Full text
21
Egri, László. "The complexity of constraint satisfaction problems and symmetric Datalog /." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101843.
Full textAbstract:
Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1, x2,..., x n and a list of constraints of the form "(x 7, x2,..., x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class.In recent years, logical and algebraic perspectives have been particularly successful in classifying CSPs. A major weapon in the arsenal of the logical perspective is the database-theory-inspired logic programming language called Datalog. A Datalog program can be used to solve a restricted class of CSPs by either accepting or rejecting a (suitably encoded) set of input constraints. Inspired by Dalmau's work on linear Datalog and Reingold's breakthrough that undirected graph connectivity is in logarithmic space, we use a new restriction of Datalog called symmetric Datalog to identify a class of CSPs solvable in logarithmic space. We establish that expressibility in symmetric Datalog is equivalent to expressibility in a specific restriction of second order logic called Symmetric Restricted Krom Monotone SNP that has already received attention for its close relationship with logarithmic space.
We also give a combinatorial description of a large class of CSPs lying in L by showing that they are definable in symmetric Datalog. The main result of this thesis is that directed st-connectivity and a closely related CSP cannot be defined in symmetric Datalog. Because undirected st-connectivity can be defined in symmetric Datalog, this result also sheds new light on the computational differences between the undirected and directed st-connectivity problems.
22
Nightingale, Peter. "Consistency and the quantified constraint satisfaction problem /." St Andrews, 2007. http://hdl.handle.net/10023/759.
Full text
23
Anestos, Nikolaos-Ektoras. "Cloud Service Orchestration Using Constraint Programming." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-194507.
Full textAbstract:
Cloud applications and services are frequently built using multiple tiers and current trends such as micro-services further increase componentization, allowing us to place each component in a different physical machine in a distributed cloud. Ericsson owns and manages very large networks, which offer diverse infrastructure in terms of computational power, storage but most importantly position in the network. Typically, a machine which is closer to the edge of the network (closer to the end user) will have limited resources but it will offer less latency, for a higher price. At the same time, several enterprise/industrial areas expect to benefit from the cloud business model in a large-scale distributed environment. These types of applications have very diverse end-2-end Service-Level Agreements (SLA) to be fulfilled, while at the same time the cloud environment needs to optimize processing, storage, and networking costs. Moreover, customers might want to change and adjust SLAs/requirements themselves using selfmanagement portals. The objective of this project is to model the network and services offered by Ericsson. Then, given the SLA, finding a valid solution of the problem, using a constraint solver. A solution is a set of physical machines that host the components the required service is composed from. This approach has many challenges since the same service can be composed from different sets of components. The connected components form a connectivity graph, where nodes in the graph are connected by physical links. But, since the connection is described by higher level components (composed by simpler components), this graph can also be expressed as a tree. Leaves in the tree are the nodes that compose the higher-level services and the ones that must be hosted in the infrastructure. The characteristics of each leaf-node depend on its parent and/or siblings in the component tree. Finally, since the components are normally connected, the physical connection between nodes in the network must be taken into consideration. The proposed model is evaluated in several cases, in order to identify how the number of the software components and the infrastructure topology affect the solution finding. The results are promising, showing fast resolution of the problem instances, varying for each test case, from a few seconds to a couple of minutes.Molnapplikationer och tjänster är ofta byggda med flera nivåer och nuvarande trender såsom mikro-tjänster ökar ytterligare komponentiseringen, vilket tillåter oss att placera varje komponent i en annan fysisk maskin på ett distribuerat moln. Ericsson äger och förvaltar väldigt stora nätverk som erbjuder varierande infrastruktur när det gäller beräkningskraft , lagring och framför allt position i nätverket. Typiskt kommer en maskin som är närmare kanten av nätet (närmare slutanvändaren) att ha begränsade resurser, men det kommer att erbjuda mindre latens till ett högre pris. Samtidigt räknar flera företag / industriområden med att dra nytta av moln affärsmodelltjänster i en storskalig och distribuerad miljö. Den här typen av applikationer har väldigt olika end-to-end varierande servicenivåavtal (SLA) som skall uppfyllas, medan moln miljön behöver optimera bearbetnings, lagrings och nätverks kostnader. Dessutom, kan kunden komma att vilja ändra och justera SLA / krav själva med hjälp av självhantering portaler. Målet för detta projekt är att modellera nät och tjänster som erbjuds av Ericsson. Sedan, givet ett SLA, att hitta en giltig lösning på problemet, med hjälp av en villkorslösare. En lösning är en uppsättning av fysiska maskiner som är värdar för komponenterna från vilka den efterfrågade tjänsten är sammansatt. Detta tillvägagångssätt är förenat med många utmaningar eftersom samma tjänst kan bestå av olika uppsättningar av komponenter. De anslutna komponenterna bildar ett förbindelseschema, där noder i grafen är anslutna med fysiska länkar. Men eftersom anslutningen beskrivs av komponenter högre nivå (bestående av enklare komponenter), denna graf kan också uttryckas som ett träd. Löv i trädet är noderna som utgör de högre nivå tjänster och de som måste finnas i infrastrukturen. Egenskaperna hos varje löv-nod att bero på dess förälder och / eller syskon i komponentträdet. Slutligen, eftersom komponenterna i normal fall är anslutna, måste den fysiska anslutningen mellan noder i nätet tas i beaktande. Den föreslagna modellen utvärderas i flera fall, för att identifiera hur antalet programvarukomponenter och infrastrukturens topologi påverkar resultatet av lösningen. Resultaten är lovande och visar snabb lösning av problemets instanser, varierande för varje testfall, från några sekunder till ett par minuter.
24
Pellerin, Clément. "Taskell : a concurrent constraint programming language." Thesis, McGill University, 1991. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=61089.
Full textAbstract:
Taskell is an instance of the concurrent constraint programming framework cc. The framework is parameterized by a choice of constraint system. The constraint system of Taskell is the set of finite trees with equality. The choice of constraint system makes Taskell similar to concurrent logic programming languages. When computing with partial information the notion of reading and writing memory becomes incoherent. The framework replaces these operations by ask and tell respectively. We hope to understand this new paradigm by studying implementations of cc languages. Taskell is a parallel implementation of a cc language written in Concurrent ML.
25
Samual, John Francis. "Constraint programming in user interface construction." Thesis, Queen Mary, University of London, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.243303.
Full text
26
Hassani, Bijarbooneh Farshid. "Constraint Programming for Wireless Sensor Networks." Doctoral thesis, Uppsala universitet, Avdelningen för datalogi, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-241378.
Full textAbstract:
In recent years, wireless sensor networks (WSNs) have grown rapidly and have had a substantial impact in many applications. A WSN is a network that consists of interconnected autonomous nodes that monitor physical and environmental conditions, such as temperature, humidity, pollution, etc. If required, nodes in a WSN can perform actions to affect the environment. WSNs present an interesting and challenging field of research due to the distributed nature of the network and the limited resources of the nodes. It is necessary for a node in a WSN to be small to enable easy deployment in an environment and consume as little energy as possible to prolong its battery lifetime. There are many challenges in WSNs, such as programming a large number of nodes, designing communication protocols, achieving energy efficiency, respecting limited bandwidth, and operating with limited memory. WSNs are further constrained due to the deployment of the nodes in indoor and outdoor environments and obstacles in the environment. In this dissertation, we study some of the fundamental optimisation problems related to the programming, coverage, mobility, data collection, and data loss of WSNs, modelled as standalone optimisation problems or as optimisation problems integrated with protocol design. Our proposed solution methods come from various fields of research including constraint programming, integer linear programming, heuristic-based algorithms, and data inference techniques.ProFuN
27
Smith, Alan William. "Scheduling a steelplant using constraint programming." Thesis, University of Leeds, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.250754.
Full text
28
Calhau, João Pedro Figueira Galhardo. "Digital forensics research using constraint programming." Master's thesis, Universidade de Évora, 2018. http://hdl.handle.net/10174/24257.
Full textAbstract:
In this dissertation we present a new and innovative approach to Digital Forensics analysis, based on Declarative
Programming approaches, more specifically Constraint Programming methodologies, to describe and solve
Digital Forensics problems. With this approach we allow for an intuitive, descriptive and more efficient method
to analyze digital equipment data.
The work described herein enables the description of a Digital Forensics Problem (DFP) as a Constraint Satisfaction
Problem (CSP) and, with the help of a CSP solver, reach a solution to such problem, if it exists, which can
be a set of elements or evidences that match the initial problem description; Sumário:
Pesquisa em Forense Digital Utilizando Programação
por Restrições
Nesta dissertação apresentamos uma nova e inovadora abordagem à análise de Forense Digital, baseada em
técnicas de Programação Declarativa, mais especificamente em metodologias de Programação por Restrições,
para descrever e resolver problemas de Forense Digital. Com esta abordagem, é nos permitida a utilização de
um método mais intuitivo, mais descritivo e mais eficiente para analisar dados de equipamentos digitais.
O trabalho aqui descrito permite a descrição de um Problema de Forense Digital (PFD) como um Problema de
Satisfação de Restrições (PSR) e, com a ajuda de um ”Solver” de PSRs, chegar a uma solução, se existir, que pode
ser um conjunto de elementos ou evidências que correspondem à descrição inicial do problema.
29
Pedro, Vasco Fernando de Figueiredo Tavares. "Constraint programming on hierarchical multiprocessor systems." Doctoral thesis, Universidade de Évora, 2012. http://hdl.handle.net/10174/14184.
Full textAbstract:
The work reported in this thesis is about constraint processing in the context of hierarchical
multiprocessor systems, including distributed systems. More speci cally, it develops
techniques and a system to help bringing the power available in today's multiprocessing
networked systems into the constraint processing eld.
Solving constraint speci ed problems is a process which lends itself naturally to
parallelisation, as it usually implies going through very large search spaces, looking for
a solution. Parallel constraint solving draws on the idea of dividing the search space
among several workers, so the search may proceed faster, and thanks to the declarative
nature of constraint programming, the parallelisation happens transparently as far as
the user is concerned. However, to fully take advantage of the parallel computing power
available, techniques must be developed to help ensure that the workers executing the
search are kept busy at all times, which is an issue tackled by this work; RESUMO: Esta tese debruça-se sobre a programação por restrições no contexto dos sistemas multiprocessador
hierárquicos, incluindo os sistemas distribuídos. Mais especificamente, o
trabalho elaborado desenvolve as técnicas de resolução de problemas de satisfação de
restrições recorrendo ao paralelismo.
A actualidade do tema prende-se com a cada vez maior divulgação de que são objecto
os sistemas multiprocessador que, juntamente com a omnipresença das redes de
computadores, põe à nossa disposição uma capacidade de cálculo que necessita de ser
posta a uso, o que tarda em acontecer. Nesta tese desenvolve-se um sistema que permite
tirar partido desses recursos através do processamento de restrições
A programação por restrições é um paradigma declarativo, em que o utilizador não
tem de se preocupar com o controlo da computação, e a introdução de paralelismo nesta
área pode realizar-se transparentemente. Por outro lado, o processo de pesquisa de
soluções para problemas especificados por restrições adapta-se particularmente bem a
ser paralelizado.
Este tese apresenta uma abordagem _à resolução paralela de restrições, que junta
paralelismo local, sob a forma de trabalhadores, com paralelismo distribuído, em que os
actores são as equipas. O sistema construído, destinado a sistemas distribuídos de larga
escala, que _é descrito e os seus resultados apresentados, inclui distribuição de trabalho,
através de roubo de trabalho. Este funciona, localmente, sem a colaboração do roubado
e, remotamente, com colaboração, num ambiente em que todas as equipas cooperam na
procura da solução.
30
Rodosek, Robert. "Generation and comparison of constraint-based heuristics using structure of constraints." Thesis, Imperial College London, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.266590.
Full text
31
Piesker, Björn. "Constraint-basierte Generierung realitätsnaher Eisenbahnnetze." Master's thesis, Universität Potsdam, 2007. http://opus.kobv.de/ubp/volltexte/2007/1532/.
Full textAbstract:
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.
32
Heipcke, Susanne. "Combined modelling and problem solving in mathematical programming and constraint programming." Thesis, University of Buckingham, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.297665.
Full text
33
Easton, Kelly King. "Using integer programming and constraint programming to solve sports scheduling problems." Diss., Georgia Institute of Technology, 2002. http://hdl.handle.net/1853/25795.
Full text
34
Sellmann, Meinolf. "Reduction techniques in constraint programming and combinatorial optimization." [S.l. : s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=96852656X.
Full text
35
Bohlin, Markus. "Design and implementation of a graph-based constraint model for local search /." Västerås : Mälardalen University, 2004. http://www.mrtc.mdh.se/publications/0754.pdf.
Full text
36
Schrijvers, Tom. "Overview of the monadic constraint programming framework." Universität Potsdam, 2010. http://opus.kobv.de/ubp/volltexte/2010/4141/.
Full textAbstract:
A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program.
The Monadic Constraint Programming framework gives a monadic definition of constraint programming where the solver is defined as a monad threaded through the monadic search tree. Search and search strategies can then be defined as firstclass objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible.
37
Lindqvist, Joakim. "Implementing a Physician Roster Using Constraint Programming." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-204896.
Full textAbstract:
A successful rostering of physicians to different activities demands satisfying the minimal allocation of physicians to each activity, following regulations and hospital guidelines in regard to workload, and adhering to the preferences of the physicians. Keeping track of all of the constraints, ensuring that they are not violated, is a complicated task, which is still often done manually. This thesis uses constraint programming to propose a general model to the problem, with which a solution can be found by incrementally tighten the constraints through an iterative interaction with a user. An implementation of the model was, to a great extent, successful in handling generated instances of these iterations.
38
Belaid, Mohamed-Bachir. "Declarative Itemset Mining Based on Constraint Programming." Thesis, Montpellier, 2020. http://www.theses.fr/2020MONTS004.
Full textAbstract:
La fouille de données est l'art de découvrir des informations à partir de bases de données.L'utilisateur spécifie le type de motifs à extraire et le spécialiste utilise des techniques pour trouver les motifs requis.De nombreuses techniques ont été introduites pour l'extraction des motifs classiques tels que les motifs fréquents, les règles d'association, etc.Cependant, l'extraction des motifs avec des propriétés supplémentaires restent un problème pour les spécialistes car des efforts algorithmiques sont requises pour gérer ces propriétés.Récemment, les chercheurs ont profité de la flexibilité de la programmation par contraintes pour modéliser plusieurs problèmes de la fouille de données.En termes de temps d'exécution, les méthodes basées sur la programmation par contraintes ne sont pas encore concurrentes avec les algorithmes spécialisées.Cependant, leur flexibilité permet la modélisation des requêtes complexes sans la nécessité de réviser le processus de résolution.Dans cette thèse, nous proposons d’utiliser la programmation par contraintes pour résoudre des problèmes de la fouille de données.Notre première contribution est un modèle basé sur la programmation par contraintes pour l'extraction des règles d'association.Pour mettre en œuvre notre modèle, nous introduisons une nouvelle contrainte globale,CONFIDENT, pour assurer la confiance des règles.Nous prouvons que propager complètement CONFIDENT est NP-difficile.Nous fournissons donc un propagateur non-complet et une décomposition pour la contrainte CONFIDENT.Nous capturons également les règles minimales non redondantes, une représentation condensée des règles d'association, en introduisant la contrainte globale GENERATOR. GENERATOR est utilisé pour extraire des motifs qui sont des générateurs. Pour cette contrainte, nous proposons un propagateur polynomial complet.Notre deuxième contribution est un model générique basé sur la programmation par contraintes permettant l'extraction des deux frontières des motifs fréquents, à savoir la frontière positive ou les motifs maximaux fréquents et la frontière négative ou les motifs minimaux infréquents.Il est facile de choisir la frontière à extraire en fixant un simple paramètre.Pour cela, nous introduisons deux nouvelles contraintes globales, FREQUENTSUBS et INFREQUENTSUPERS,avec des propagateurs polynomiaux complets.Nous examinons ensuite le problème de l'extraction des frontières avec des contraintes supplémentaires.Nous prouvons que ce problème est coNP-difficile. Cela implique qu’il n’existe aucun CSP représentant ce problème (sauf si coNP est dans NP)Data mining is the art of discovering knowledge from databases. The user specifies the type of patterns to be mined, and the miner uses techniques to find the required patterns. Many techniques have been introduced for mining traditional patterns like frequent itemsets, association rules, etc. However, mining patterns with additional properties remains a bottleneck for specialists nowadays due to the algorithmic effort needed to handle these properties.Recently, researchers have taken advantage of the flexibility of constraint programming to model various data mining problems. In terms of CPU time, constraint programming-based methods have not yet competed with ad hoc algorithms. However, their flexibility allows the modeling of complex user queries without revising the solving process.In this thesis we propose to use constraint programming for modeling and solving some well known data mining problems.Our first contribution is a constraint programming model for mining association rules. To implement our model, we introduce a new global constraint, CONFIDENT, for ensuring the confidence of rules.We prove that completely propagating CONFIDENT is NP-hard. We thus provide a non-complete propagator and a decomposition for CONFIDENT. We also capture the minimal non-redundant rules, a condensed representation of association rules, by introducing the global constraint GENERATOR. GENERATOR is used for mining itemsets that are generators. For this constraint, we propose a complete polynomial propagator.Our second contribution is a generic framework based on constraint programming to mine both borders of frequent itemsets, i.e. the positive border or maximal frequent itemsets and the negative border or minimal infrequent itemsets. One can easily decide which border to mine by setting a simple parameter. For this, we introduce two new global constraints, FREQUENTSUBS and INFREQUENTSUPERS, with complete polynomial propagators. We then consider the problem of mining borders with additional constraints. We prove that this problem is coNP-hard, ruling out the hope for the existence of a single CSP solving this problem (unless coNP is in NP)
39
Cortes, Antonio. "Enhancing test data generation using constraint programming." To access this resource online via ProQuest Dissertations and Theses @ UTEP, 2008. http://0-proquest.umi.com.lib.utep.edu/login?COPT=REJTPTU0YmImSU5UPTAmVkVSPTI=&clientId=2515.
Full text
40
Almas, Luís Pedro Parreira Galito Pimenta. "DSM-PM2 adequacy for distributed constraint programming." Master's thesis, Universidade de Évora, 2007. http://hdl.handle.net/10174/16454.
Full textAbstract:
As Redes de alta velocidade e o melhoramento rápido da performance dos microprocessadores fazem das redes de computadores um veículo apelativo para computação paralela. Não é preciso hardware especial para usar computadores paralelos e o sistema resultante é extensível e facilmente alterável. A programação por restrições é um paradigma de programação em que as relações entre as variáveis pode ser representada por restrições. As restrições diferem das primitivas comuns das outras linguagens de programação porque, ao contrário destas, não específica uma sequência de passos a executar mas antes a definição das propriedades para encontrar as soluções de um problema específico. As bibliotecas de programação por restrições são úteis visto elas não requerem que os programadores tenham que aprender novos skills para uma nova linguagem mas antes proporcionam ferramentas de programação declarativa para uso em sistemas convencionais. A tecnologia de Memoria Partilhada Distribuída (Distributed Shared Memory) apresenta-se como uma ferramenta para uso em aplicações distribuídas em que a informação individual partilhada pode ser acedida diretamente. Nos sistemas que suportam esta tecnologia os dados movem-se entre as memórias principais dos diversos nós de um cluster. Esta tecnologia poupa o programador às preocupações de passagem de mensagens onde ele teria que ter muito trabalho de controlo do comportamento do sistema distribuído. Propomos uma arquitetura orientada para a distribuição de Programação por Restrições que tenha os mecanismos da propagação e da procura local como base sobre um ambiente CC-NUMA distribuído usando memória partilhada distribuída. Os principais objetivos desta dissertação podem ser sumarizados em: - Desenvolver um sistema resolvedor de restrições, baseado no sistema AJ ACS [3], usando a linguagem ”C', linguagem nativa da biblioteca de desenvolvimento paralelo experimentada: O PM2 [4] - Adaptar, experimentar e avaliar a adequação deste sistema resolvedor de restrições usando DSM-PM2 [1] a um ambiente distribuído assente numa arquitetura CC-NUMA; /ABSTRACT - High-speed networks and rapidly improving microprocessor performance make networks of workstations an increasingly appealing vehicle for parallel computing. No special hardware is required to use this solution as a parallel computer, and the resulting system can be easily maintained, extended and upgraded. Constraint programming is a programming paradigm where relations between variables can be stated in the form of constraints. Constraints differ from the common primitives of other programming languages in that they do not specify a step or sequence of steps to execute but rather the properties of a solution to be found. Constraint programming libraries are useful as they do not require the developers to acquire skills for a new language, providing instead declarative programming tools for use within conventional systems. Distributed Shared Memory presents itself as a tool for parallel application in which individual shared data items can be accessed directly. In systems that support Distributed Shared Memory, data moves between main memories of different nodes. The Distributed Shared Memory spares the programmer the concerns of massage passing, where he would have to put allot of effort to control the distributed system behavior. We propose an architecture aimed for Distributed Constraint Programming Solving that relies on propagation and local search over a CC-NUMA distributed environment using Distributed Shared Memory. The main objectives of this thesis can be summarized as: - Develop a Constraint Solving System, based on the AJ ACS [3] system, in the C language, the native language of the experimented Parallel library - PM2 [4]; - Adapt, experiment and evaluate the developed constraint solving system distributed suitability by using DSM-PM2 [1] over a CC-NUMA architecture distributed environment;
41
CATTAFI, Massimiliano. "LOGIC AND CONSTRAINT PROGRAMMING FOR COMPUTATIONAL SUSTAINABILITY." Doctoral thesis, Università degli studi di Ferrara, 2012. http://hdl.handle.net/11392/2388775.
Full textAbstract:
Computational Sustainability is an interdisciplinary field that aims to develop computational
and mathematical models and methods for decision making concerning
the management and allocation of resources in order to help solve environmental
problems.
This thesis deals with a broad spectrum of such problems (energy efficiency, water
management, limiting greenhouse gas emissions and fuel consumption) giving
a contribution towards their solution by means of Logic Programming (LP) and
Constraint Programming (CP), declarative paradigms from Artificial Intelligence
of proven solidity.
The problems described in this thesis were proposed by experts of the respective
domains and tested on the real data instances they provided. The results are encouraging
and show the aptness of the chosen methodologies and approaches.
The overall aim of this work is twofold: both to address real world problems
in order to achieve practical results and to get, from the application of LP and
CP technologies to complex scenarios, feedback and directions useful for their
improvement.
42
Thornton, John. "Constraint Weighting Local Search for Constraint Satisfaction." Thesis, Griffith University, 2000. http://hdl.handle.net/10072/367954.
Full textAbstract:
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 problemsThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Science, Environment, Engineering and Technology
Full Text
43
Kiziltan, Zeynep. "Symmetry Breaking Ordering Constraints." Doctoral thesis, Uppsala : Univ., Department of Information Science, 2004. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3991.
Full text
44
Karatas, Ahmet Serkan. "Analysis Of Extended Feature Models With Constraint Programming." Phd thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/3/12612082/index.pdf.
Full textAbstract:
In this dissertation we lay the groundwork of automated analysis of extended feature models with constraint programming. Among different proposals, feature modeling has proven to be very effective for modeling and managing variability in Software Product Lines. However, industrial experiences showed that feature models often grow too large with hundreds of features and complex cross-tree relationships, which necessitates automated analysis support. To address this issue we present a mapping from extended feature models, which may include complex feature-feature, feature-attribute and attribute-attribute cross-tree relationships as well as global constraints, to constraint logic programming over finite domains. Then, we discuss the effects of including complex feature attribute relationships on various analysis operations defined on the feature models. As new types of variability emerge due to the inclusion of feature attributes in cross-tree relationships, we discuss the necessity of reformulation of some of the analysis operations and suggest a revised understanding for some other. We also propose new analysis operations arising due to the nature of the new variability introduced. Then we propose a transformation from extended feature models to basic/cardinality-based feature models that may be applied under certain circumstances and enables using SAT or BDD solvers in automated analysis of extended feature models. Finally, we discuss the role of the context information in feature modeling, and propose to use context information in staged configuration of feature-models.
45
Fahle, Torsten. "Integrating concepts from constraint programming and operations research algorithms." [S.l. : s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=968544851.
Full text
46
Policella, Nicola. "Scheduling with Uncertainty: A Proactive Approach using Partial Order Schedules." Doctoral thesis, La Sapienza, 2005. http://hdl.handle.net/11573/917059.
Full text
47
Thornton, John Richard, and n/a. "Constraint Weighting Local Search for Constraint Satisfaction." Griffith University. School of Computing and Information Technology, 2000. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20050901.142439.
Full textAbstract:
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
48
Vigerske, Stefan. "Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2013. http://dx.doi.org/10.18452/16704.
Full textAbstract:
Diese Arbeit leistet Beiträge zu zwei Gebieten der mathematischen Programmierung: stochastische Optimierung und gemischt-ganzzahlige nichtlineare Optimierung (MINLP). Im ersten Teil erweitern wir quantitative Stetigkeitsresultate für zweistufige stochastische gemischt-ganzzahlige lineare Programme auf Situationen in denen Unsicherheit gleichzeitig in den Kosten und der rechten Seite auftritt, geben eine ausführliche Übersicht zu Dekompositionsverfahren für zwei- und mehrstufige stochastische lineare und gemischt-ganzzahlig lineare Programme, und diskutieren Erweiterungen und Kombinationen des Nested Benders Dekompositionsverfahrens und des Nested Column Generationsverfahrens für mehrstufige stochastische lineare Programme die es erlauben die Vorteile sogenannter rekombinierender Szenariobäume auszunutzen. Als eine Anwendung dieses Verfahrens betrachten wir die optimale Zeit- und Investitionsplanung für ein regionales Energiesystem unter Einbeziehung von Windenergie und Energiespeichern. Im zweiten Teil geben wir eine ausführliche Übersicht zum Stand der Technik bzgl. Algorithmen und Lösern für MINLPs und zeigen dass einige dieser Algorithmen innerhalb des constraint integer programming Softwaresystems SCIP angewendet werden können. Letzteres erlaubt uns die Verwendung schon existierender Technologien für gemischt-ganzzahlige linear Programme und constraint Programme für den linearen und diskreten Teil des Problems. Folglich konzentrieren wir uns hauptsächlich auf die Behandlung der konvexen und nichtkonvexen nichtlinearen Nebenbedingungen mittels Variablenschrankenpropagierung, äußerer Approximation und Reformulierung. In einer ausführlichen numerischen Studie untersuchen wir die Leistung unseres Ansatzes anhand von Anwendungen aus der Tagebauplanung und des Aufbaus eines Wasserverteilungssystems und mittels verschiedener Vergleichstests. Die Ergebnisse zeigen, dass SCIP ein konkurrenzfähiger Löser für MINLPs geworden ist.This thesis contributes to two topics in mathematical programming: stochastic optimization and mixed-integer nonlinear programming (MINLP). In the first part, we extend quantitative continuity results for two-stage stochastic mixed-integer linear programs to include situations with simultaneous uncertainty in costs and right-hand side, give an extended review on decomposition algorithm for two- and multistage stochastic linear and mixed-integer linear programs, and discuss extensions and combinations of the Nested Benders Decomposition and Nested Column Generation methods for multistage stochastic linear programs to exploit the advantages of so-called recombining scenario trees. As an application of the latter, we consider the optimal scheduling and investment planning for a regional energy system including wind power and energy storages. In the second part, we give a comprehensive overview about the state-of-the-art in algorithms and solver technology for MINLPs and show that some of these algorithm can be applied within the constraint integer programming framework SCIP. The availability of the latter allows us to utilize the power of already existing mixed integer linear and constraint programming technologies to handle the linear and discrete parts of the problem. Thus, we focus mainly on the domain propagation, outer-approximation, and reformulation techniques to handle convex and nonconvex nonlinear constraints. In an extensive computational study, we investigate the performance of our approach on applications from open pit mine production scheduling and water distribution network design and on various benchmarks sets. The results show that SCIP has become a competitive solver for MINLPs.
49
Suy, Franch Josep. "A satisfiability modulo theories approach to constraint programming." Doctoral thesis, Universitat de Girona, 2012. http://hdl.handle.net/10803/98302.
Full textAbstract:
In this thesis we focus on solving CSPs using SMT. Essentially, what we do is reformulating CSPs into SMT. The obtained results allow us to conclude that state-of-the-art SMT solvers are a robust tool to solve CSPs. We tackle not only decisional CSPs, but also Constraint Optimization Problems and Weighted Constraint Satisfaction Problems. For solving these problems we have used SMT in conjunction with appropriated algorithms: search algorithms and UNSAT core-based algorithms. We have provided support for meta-constraints that is, constraints on constraints. Meta-constraints can be very helpful in the modelling process. Once verified that SMT is a good generic approximation for CP, we tested how algorithms built on top of an SMT solver can have equal or better performance than ad-hoc programs designed specifically for a given problem. The problem that we have selected to make this test is the RCPSP, obtaining highly competitive results.Aquesta tesi es centra en la resolució de CSPs utilitzant SMT. En essència, es reformulen els CSPs a fórmules SMT. Els resultats obtinguts permeten concloure que els millors solucionadors actuals d'SMT són una eina sòlida per a resoldre CSPs. No només s'aborden els CSP decisionals, sinó també problemes d'optimització de restriccions i problemes de satisfactibilitat de restriccions amb pesos. Per a resoldre aquests problemes s'ha utilitzat SMT juntament amb els algorismes apropiats: algorismes de cerca i algorismes basats en nuclis d'insatisfactibilitat. També es dóna suport a meta-restriccions, és a dir, restriccions sobre restriccions. Un cop vist que SMT és una molt bona aproximació genèrica per a CP, s'ha comprovat com algorismes basats en SMT poden tenir un rendiment igual o millor que els programes dissenyats específicament per a un determinat problema. El problema seleccionat per a dur a terme aquesta comprovació ha estat el RCPSP, obtenint uns resultats altament competitius.
50
Pan, Xiaoyue. "Haplotype Inference by Pure Parsimony with Constraint Programming." Thesis, Uppsala University, Department of Information Technology, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-110544.
Full textAbstract:
Haplotype inference by pure parsimony problem (HIPP) is a computational problem in bioinformatics. It is a relatively new NP-hard problem and it has been thoroughly explored using integer programming, SAT-based programming and answer set programming. The state of the art approach is the SAT-based model. Constraint programming has been used as an optimisation tool in the SAT-based model but it has not been used as the modelling tool to solve the problem. This thesis models the HIPP problem using constraint programming. The constraint models are not as efficient as the SAT-based model but provides an alternative of modelling the problem.