Dissertations / Theses on the topic 'Constraint Satisfaction Programming'
To see the other types of publications on this topic, follow the link: Constraint Satisfaction Programming.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 45 dissertations / theses for your research on the topic 'Constraint Satisfaction 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
Nightingale, Peter. "Consistency and the quantified constraint satisfaction problem /." St Andrews, 2007. http://hdl.handle.net/10023/759.
Full text
2
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.
3
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
4
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
5
Padmanabhuni, Srinivas. "Logic programming with stable models for constraint satisfaction." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0009/NQ60011.pdf.
Full text
6
Zhang, Lixi. "Solving the timetabling problem using constraint satisfaction programming." Access electronically, 2005. http://www.library.uow.edu.au/adt-NWU/public/adt-NWU20051104.155838/index.html.
Full text
7
Thorstensen, Evgenij. "Hybrid tractability of constraint satisfaction problems with global constraints." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:05707b54-69e3-40eb-97e7-63b1a178c701.
Full textAbstract:
A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or intensionally, whether by an equation, propositional logic formula, or other means. Intensionally represented constraints, known as global constraints, are a powerful modelling technique, and many modern CSP solvers provide them. We give examples to show how problems that deal with product configuration can be modelled with such constraints, and how this approach relates to other modelling formalisms. The complexity of CSPs with extensionally represented constraints is well understood, and there are several known techniques that can be used to identify tractable classes of such problems. For CSPs with global constraints, however, many of these techniques fail, and far fewer tractable classes are known. In order to remedy this state of affairs, we undertake a systematic review of research into the tractability of CSPs. In particular, we look at CSPs with extensionally represented constraints in order to understand why many of the techniques that give tractable classes for this case fail for CSPs with global constraints. The above investigation leads to two discoveries. First, many restrictions on how the constraints of a CSP interact implicitly rely on a property of extensionally represented constraints to guarantee tractability. We identify this property as being a bound on the number of solutions in key parts of the instance, and find classes of global constraints that also possess this property. For such classes, we show that many known tractability results apply. Furthermore, global constraints allow us to treat entire CSP instances as constraints. We combine this observation with the above result, and obtain new tractable classes of CSPs by dividing a CSP into smaller CSPs drawn from known tractable classes. Second, for CSPs that simply do not possess the above property, we look at how the constraints of an instance overlap, and how assignments to the overlapping parts extend to the rest of the problem. We show that assignments that extend in the same way can be identified. Combined with a new structural restriction, this observation leads to a second set of tractable classes. We conclude with a summary, as well as some observations about potential for future work in this area.
8
Nightingale, Peter William. "Consistency and the Quantified Constraint Satisfaction Problem." Thesis, University of St Andrews, 2007. http://hdl.handle.net/10023/759.
Full textAbstract:
Constraint satisfaction is a very well studied and fundamental artificial intelligence technique. Various forms of knowledge can be represented with constraints, and reasoning techniques from disparate fields can be encapsulated within constraint reasoning algorithms. However, problems involving uncertainty, or which have an adversarial nature (for example, games), are difficult to express and solve in the classical constraint satisfaction problem. This thesis is concerned with an extension to the classical problem: the Quantified Constraint Satisfaction Problem (QCSP). QCSP has recently attracted interest. In QCSP, quantifiers are allowed, facilitating the expression of uncertainty. I examine whether QCSP is a useful formalism. This divides into two questions: whether QCSP can be solved efficiently; and whether realistic problems can be represented in QCSP. In attempting to answer these questions, the main contributions of this thesis are the following: - the definition of two new notions of consistency; - four new constraint propagation algorithms (with eight variants in total), along with empirical evaluations; - two novel schemes to implement the pure value rule, which is able to simplify QCSP instances; - a new optimization algorithm for QCSP; - the integration of these algorithms and techniques into a solver named Queso; - and the modelling of the Connect 4 game, and of faulty job shop scheduling, in QCSP. These are set in context by a thorough review of the QCSP literature.
9
Nilsson, Josefin. "Generating Playback Sequences of Songs with Constraint Satisfaction Programming." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-279298.
Full textAbstract:
With the right songs at the right time, a playback sequence of songs can fulfil the two fundamentals of a good music listening experience: the desire for repetition and the desire for surprise. Many businesses play continuous music in their locations with automatic playback generation, and for them, a good music experience can improve the overall customer satisfaction as well as increase sales. This is something that Soundtrack Your Brand, a Stockholm based mu- sic streaming company, seize by offering their clients music tailored for their business. One way of generating playback sequences of songs given a playlist and at the same time define criteria that the sequence should fulfil is by modelling it as a Constraint Satisfaction Problem. The problem can be defined as given a playlist of songs as input, generate a playback sequence of the songs such as a set of constraints over the attributes of the songs in the playback is satisfied. This thesis investigates if Constraint Satisfaction Programming is a viable approach for generating playback sequences and if so, how efficiently it can be done. A Constraint Satisfaction Programming sequencer is implemented which models three types of constraints and uses a Hill Climbing approach to solve the playback problem. The proposed sequencer is benchmarked against the current solution at Soundtrack Your Brand, which is a greedy algorithm, as well as a purely random shuffle. The results show that the proposed sequencer outperforms both the current solution and a random shuffle with regards to how well they satisfied the stated constraints. The efficiency of the sequencer is measured with regards to run-time and memory usage in different scenarios where the results indicate a viable performance when the size of the playlist increases. When comparing the proposed sequencer to the current solution, it is found that the sequencer has a short run-time for each of the playlist size that was tested. By combining the benchmarking- and efficiency evaluation results, the thesis concludes that it is possible to generate playback sequences with Constraint Satisfaction Programming and that it can be done efficiently enough for it to be run in a production environment.Med rätt låt vid rätt tidpunkt kan uppspelningssekvenser av låtar uppfylla de två grundläggande egenskaperna av en bra musiklyssningsupplevelse: önskan för upprepning och önskan för överraskningar. Många företag spelar musik kontinuerligt i sina lokaler med automatisk uppspelningsordning, och för dem kan en bra musikupplevelse förbättra den generella kundbelåtenheten samt öka försäljningen. Det här är något som Soundtrack Your Brand, ett musik- streamingföretag baserat i Stockholm, utnyttjar genom att erbjuda sina kunder musik skräddarsydd för deras företag. Ett sätt att generera uppspelningssekvenser av låtar givet en spellista och samtidigt definiera kriterier sekvensen ska uppfylla är genom att modellera det som ett villkorsproblem. Problemet kan definieras som att givet en spellista av låtar som indata, generera en uppspelningssekvens av låtar så att en mängd villkor över låtarna i sekvensens attribut är uppfyllda. Det här examensarbetet undersöker om Constraint Satisfaction Programming är en möjlig lösning för att generera uppspelningssekvenser och i så fall, hur effektivt det går att göra det. En Constraint Satisfaction Programming-sekvenserare implementeras som modellerar tre olika typer av villkor och an- vänder ett Hill Climbing-tillvägagångssätt för att lösa uppspelningsproblemet. Den föreslagna sekvenseraren jämförs med den nuvarande lösningen på Soundtrack Your Brand, som är en girig algoritm, samt en matematiskt slump- mässig blandning. Resultaten visar att den föreslagna lösningen presterar bättre än både den nuvarande lösningen och den slumpmässiga blandningen när det kommer till hur väl de uppfyller de definierade villkoren. Sekvenserarens effektivitets mäts med avseende på körtid om minnesanvändning i olika scenarion där resultaten indikerar bra prestanda när storleken på spellistan ökar. När den föreslagna sekvenseraren jämförs med den nuvarande lösningen har sekvenseraren kortare körtid för alla storlekar av spellistor som testades. Genom att kombinera resultaten av jämförelsen och effektivitetsutvärderingen slår det här examensarbetet fast att det är möjligt att generera uppspelningssekvenser med Constraint Satisfaction Programming och att det kan göras tillräckligt effektivt för att köras i en produktionsmiljö.
10
Gharbi, Nebras. "On compressing and parallelizing constraint satisfaction problems." Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0406/document.
Full textAbstract:
La programmation par contraintes est un cadre puissant utilisé pour modéliser et résoudre des problèmes combinatoires, employant des techniques d'intelligence artificielle, de la recherche opérationnelle, de théorie des graphes,..., etc. L'idée de base de la programmation par contraintes est que l'utilisateur exprime ses contraintes et qu'un solveur de contraintes cherche une ou plusieurs solutions.Les problèmes de satisfaction de contraintes (CSP), sont au cœur de la programmation par contraintes. Ce sont des problèmes de décision où nous recherchons des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Ces problèmes de décision revoient vrai, si le problème admet une solution, faux, sinon. Les problèmes de satisfaction de contraintes sont le sujet de recherche intense tant en recherche opérationnelle qu'en intelligence artificielle. Beaucoup de CSPs exigent la combinaison d'heuristiques et de méthode d'inférences combinatoires pour les résoudre dans un temps raisonnable.Avec l'amélioration des ordinateurs, la résolution de plus grands problèmes devient plus facile. Bien qu'il y ait plus de capacités offertes par la nouvelle génération de machines, les problèmes industriels deviennent de plus en plus grand ce qui implique un espace _norme pour les stocker et aussi plus de temps pour les résoudre.Cette thèse s'articule autour des techniques d'optimisation de la résolution des CSPs en raisonnant sur plusieurs axes.Dans la première partie, nous traitons la compression des contraintes table. Nous proposons deux méthodes différentes pour la compression des contraintes de table. Les deux approches sont basées sur la recherche des motifs fréquents pour éviter la redondance. Cependant, la façon de définir un motif, la détection des motifs fréquents et la nouvelle représentation compacte diffère significativement. Nous présentons pour chacune des approches un algorithme de filtrage.La seconde partie est consacrée à une autre façon d'optimiser la résolution de CSP qui est l'utilisation d'une architecture parallèle. Nous proposons une méthode où nous utilisons une architecture parallèle pour améliorer le processus de résolution en établissant des cohérences parallèles. En fait, les esclaves envoient à leur maître le résultat obtenu après avoir établi la cohérence partielle en tant que nouveaux faits. Le maître, à son tour essaye de profiter d'eux en enlevant les valeurs correspondantesConstraint Programming (CP) is a powerful paradigm used for modelling and solving combinatorial constraint problems that relies on a wide range of techniques coming from artificial intelligence, operational research, graph theory,..., etc. The basic idea of constraint programming is that the user expresses its constraints and a constraint solver seeks a solution. Constraint Satisfaction Problems (CSP), is a framework at the heart of CP problems. They correspond to decision problems where we seek for states or objects satisfying a number of constraints or criteria. These decision problems have two answers to the question they encode: true, if the problem admits a solution, false, otherwise. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require the combination of heuristics and combinatorial optimization methods to solve them in a reasonable time.With the improvement of computers, larger and larger problems can be solved. However, the size of industrial problems grow faster which requires a vast amount of memory space to store them and entail great difficulties to solve them. In this thesis, our contributions can be divided into two main parts. In the first part, we deal with the most used kind of constraints, which are table constraints. We proposed two compressed forms of table constraints. Both of them are based on frequent patterns search in order to avoid redundancy. However, the manner of defining pattern, the patterns-detecting process and the new compact representation differ significantly. For each form, we propose a filtering algorithm. In the second part, we explore another way to optimize CSP solving which is the use of a parallel architecture. In fact, we enhance the solving process by establishing parallel consistencies. Different workers send to their master the result of establishing partial consistencies as new discovered facts. The master, in its turns tries to benefit from them by removing corresponding values
11
Hewson, John Aubrey. "Constraint-based specifications for system configuration." Thesis, University of Edinburgh, 2013. http://hdl.handle.net/1842/8267.
Full textAbstract:
Declarative, object-oriented configuration management systems are widely used, and there is a desire to extend such systems with automated analysis and decision-making. This thesis introduces a new formulation for configuration management problems based on the tools and techniques of constraint programming, which enables automated decision-making. We present ConfSolve, an object-oriented declarative configuration language, in which logical constraints on a system can be specified. Verification, impact analysis, and the generation of valid configurations can then be performed. This is achieved via translation to the MiniZinc constraint programming language, which is in turn solved via the Gecode constraint solver. We formally define the syntax, type system, and semantics of ConfSolve, in order to provide it with a rigorous foundation. Additionally we show that our implementation outperforms previous work, which utilised an SMT solver, while adding new features such as optimisation. We next develop an extension of the ConfSolve language, which facilitates not only one-off configuration tasks, but also subsequent re-configurations in which the previous state of the system is taken into account. In a practical setting one does not wish for a re-configuration to deviate too far from the existing state, unless the benefits are substantial. Re-configuration is of crucial importance if automated configuration systems are to gain industry adoption. We present a novel approach to incorporating state-change into ConfSolve while remaining declarative and providing acceptable performance.
12
Winter, Mark J. "Knowledge refinement in constraint satisfaction and case classification problems." Thesis, University of Aberdeen, 1999. http://digitool.abdn.ac.uk/R?func=search-advanced-go&find_code1=WSN&request1=AAIU106810.
Full textAbstract:
Knowledge-Base Refinement (KBR) systems are an attempt to help with the difficulties of detecting and correcting errors in a knowledge-base. This thesis investigates Knowledge-Base Refinement within the two problem solving paradigms of Case-Based Reasoning and Constraint Based Reasoning. Case-Based Reasoners make use of cases which represent previous problem solving incidents. Constraint Satisfaction Problems are represented by a set of variables, the possible values these variables can take and a set of constraints further restricting their possible values. This thesis argues that if the problem-solving paradigms of Case-Based Reasoning and Constraint-Based Reasoning are to become truly viable, then research has to be directed at providing support for knowledge-base refinement, but aimed at the knowledge representation formalisms used by the two paradigms rather than more traditional rule-based representations. The CRIMSON system has been developed within the context of an industrial inventory management problem and uses constraint satisfaction techniques. The system makes use of design knowledge to form a constraint satisfaction problem (CSP) which is solved to determine which items from an inventory are suitable for a given problem. Additionally, the system is equipped with a KBR facility allowing the designer to criticise the results of the CSP, leading to knowledge being refined. The REFINER systems are knowledge-base refinement systems that detect and help remove inconsistencies in case-bases. The systems detect and report inconsistencies to domain expert together with a set of refinements which, if implemented would remove the appropriate inconsistency. REFINER+ attempts to overcome the problems associated with REFINER, mainly its inefficiency with large case-bases. The systems can make use of background knowledge to aid in the refinement process, although they can function without any. However, care must be taken to ensure that any background knowledge that is used is correct. If this is not the case, then the refinement process may be adversely affected. Countering this problem is the main aim of BROCKER, which further extends the ideas of REFINER+ to include a facility allowing incorrect background knowledge used to be refined in response to expert criticism of the system's performance. The systems were mainly developed making use of a medical dataset.
13
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
14
Likeman, Martin. "A study of centralised and distributed problem solving applied to water supply scheduling." Thesis, University of Reading, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.241628.
Full text
15
Andersson, Jakob. "Automatic Invoice Data Extraction as a Constraint Satisfaction Problem." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-411596.
Full textAbstract:
Invoice processing has traditionally been heavily dependent onmanual labor, where the task is to identify and move certaininformation from an origin to a destination. A time demandingtask with a high interest of automation to reduce time ofexecution, fault-risk and cost.With the evergrowing interest in automation and ArtificialIntelligence (AI), this thesis will explore the possibilities ofautomating the task of extracting and mapping information ofinterest by defining the problem as a Constraint OptimizationProblem (COP) using numeric relations between present information.The problem is then solved by extracting the numericalvalues in a document and utilizing it as an input space whereeach combination of numeric values are tested using a backendsolver.Several different models were defined, using different approachesand constraints on relations between possible existingfields. A solution to an invoice was considered correct if thetotal, tax, net and rounding amounts were estimated correctly.The final best achieved results were 84.30% correct and8.77% incorrect solutions on a set of 1400 various types of invoices.The achieved results show a promising alternative route toproposed solutions using e.g. machine learning or other intelligentsolutions using graphical or positional data. While only regardingthe numerical values present in each document, the proposedsolution becomes decentralized and therefor can be implementedand ran on any set of invoices without any pre-training phase.
16
Wu, Yi. "The Approximability of Learning and Constraint Satisfaction Problems." Research Showcase @ CMU, 2010. http://repository.cmu.edu/dissertations/24.
Full textAbstract:
An α-approximation algorithm is an algorithm guaranteed to output a solutionthat is within an α ratio of the optimal solution. We are interested in thefollowing question: Given an NP-hard optimization problem, what is the bestapproximation guarantee that any polynomial time algorithm could achieve?
We mostly focus on studying the approximability of two classes of NP-hardproblems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems.
For CSPs, we mainly study the approximability of MAX CUT, MAX 3-CSP,MAX 2-LINR, VERTEX-PRICING, as well as serval variants of the UNIQUEGAMES.• The problem of MAX CUT is to find a partition of a graph so as to maximizethe number of edges between the two partitions. Assuming theUnique Games Conjecture, we give a complete characterization of the approximationcurve of the MAX CUT problem: for every optimum value ofthe instance, we show that certain SDP algorithm with RPR2 roundingalways achieve the optimal approximation curve.• The input to a 3-CSP is a set of Boolean constraints such that each constraintcontains at most 3 Boolean variables. The goal is to find an assignmentto these variables to maximize the number of satisfied constraints.We are interested in the case when a 3-CSP is satisfiable, i.e.,there does exist an assignment that satisfies every constraint. Assumingthe d-to-1 conjecture (a variant of the Unique Games Conjecture), weprove that it is NP-hard to give a better than 5/8-approximation for theproblem. Such a result matches a SDP algorithm by Zwick which givesa 5/8-approximation problem for satisfiable 3-CSP. In addition, our resultalso conditionally resolves a fundamental open problem in PCP theory onthe optimal soundness for a 3-query nonadaptive PCP system for NP withperfect completeness.• The problem of MAX 2-LINZ involves a linear systems of integer equations;these equations are so simple such that each equation contains atmost 2 variables. The goal is to find an assignment to the variables so asto maximize the total number of satisfied equations. It is a natural generalizationof the Unique Games Conjecture which address the hardness ofthe same equation systems over finite fields. We show that assuming theUnique Games Conjecture, for a MAX 2-LINZ instance, even that thereexists a solution that satisfies 1−ε of the equations, it is NP-hard to findone that satisfies ² of the equations for any ε > 0.
17
Maloberti, Jérôme. "Improving inductive logic programming with constraint satisfaction techniques : applications to frequent query discovery." Paris 11, 2005. http://www.theses.fr/2005PA112139.
Full textAbstract:
Le travail presente vise a l'integration d'algorithmes de problemes de satisfaction de contraintes (psc) en programmation logique inductive (pli) et en fouille de donnees relationnelles. Cette integration est fondee sur le fait que le test de theta-subsomption, intensivement utilise pour evaluer des hypotheses et des requetes relationnelles, est equivalent a un psc. Trois algorithmes sont presentes : django, un algorithme de theta-subsomption qui combine des procedures (forward checking, coherence par arc, ordonnancement dynamique des variables) et des heuristiques (first fail principle) classiques en psc, jivaro, base sur django, permet la reduction d'une clause en utilisant la theta-subsomption de cette clause sur elle-meme, et jimi, construit sur jivaro et django, recherche iterativement les motifs frequents dans une base de donnees en datalog. Les psc et la theta-subsomption ayant tous les deux une complexite dans le pire cas exponentielle, django est evalue en utilisant le cadre de la transition de phase, qui a ete initialement decouverte dans les psc (cheeseman et kanefsky 1991), giordana et saitta (2000) ayant montre que la transition de phase etait egalement presente den pli. Dans ce cadre experimental, le probleme est deplace d'une analyse dans le pire cas, vers une analyse statistique. Des experimentations sur des problemes de grande taille artificiellement engendres ainsi que des problemes reels, montrent une amelioration sur l'etat de l'art d'un ou plusieurs ordres de grandeurThe work presented aims at a principled integration of constraint satisfaction problems (csp) algorithms for inductive logic programming (ilp) and relational data-mining, based on the fact that the theta-subsumption test, intensively used for assessing relational hypotheses and queries, is equivalent to a csp problem. Three algorithms are presented: django, which combines prominent csp procedures (forward checking, arc consistency, dynamic variable ordering) and heuristics (first fail principle) to achieve theta-subsumption, jivaro, built on the top of django, achieves clause reduction by exploiting the theta-subsumption of the clause by itself, and jimi, built on the top of jivaro and django, ensures a non-redundant search for frequent queries in a datalog database. Csp and theta-subsumption both have an exponential worst casecomplexity, thus django is evaluated after the so-called phase transition framework, which has been imported from the csp (cheeseman and kanefsky 1991) to the ilp setting by giordana and saitta(2000). In this framework, the focus is shifted from a worst-case complexity analysis to a statistical complexity analysis. Experiments on large-size artificial, and real-world datasets, show an improvement on the state of the art by two or more orders of magnitude
18
Fu, Ser-Geon. "Genetic and evolutionary protocols for solving distributed asymmetric constraint satisfaction problems." Auburn, Ala., 2007. http://repo.lib.auburn.edu/2007%20Spring%20Dissertations/FU_SER-GEON_10.pdf.
Full text
19
Lu, Wei. "Integer Programming-based Methods for Computing Minimum Reaction Modifications of Metabolic Networks for Constraint Satisfaction." 京都大学 (Kyoto University), 2015. http://hdl.handle.net/2433/199436.
Full text
20
East, Deborah J. "DATALOG WITH CONTRAINTS: A NEW ANSWER-SET PROGRAMMING FORMALISM." UKnowledge, 2001. http://uknowledge.uky.edu/gradschool_diss/322.
Full textAbstract:
Knowledge representation and search are two fundamental areas of artificial intelligence. Knowledge representation is the area of artificial intelligence which deals with capturing, in a formal language, the properties of objects and the relationships between objects. Search is a systematic examination of all possible candidate solutions to a problem that is described as a theory in some knowledge representation formalism. We compare traditional declarative programming formalisms such as PROLOG and DATALOG with answer-set programming formalisms such as logic programming with stable model semantic. In this thesis we develop an answer-set formalism we can DC. The logic of DC is based on the logic of prepositional schemata and a version of Closed World Assumption. Two important features of the DC logic is that it supports modeling of the cardinalities of sets and Horn clauses. These two features facilitate modeling of search problems. The DC system includes and implementation of a grounder and a solver. The grounder for the DC system grounds instances of problems retaining the structure of the cardinality of sets. The resulting theories are thus more concise. In addition, the solver for the DC system utilizes the structure of cardinality of sets to perform more efficient search. The second feature, Horn clauses, are used when transitive closure will eliminate the need for additional variables. The semantics of the Horn clauses are retained in the grounded theories. This also results in more concise theories. Our goal in developing DC is to provide the computer science community with a system which facilitates modeling of problems, is easy to use, is efficient and captures the class of problems in NP-search. We show experimental results comparing DC to other systems. These results show that DC is always competitive with state-of-the-art answer-set programming systems and for many problems DC is more efficient.
21
Zhao, Zhengyang. "Optimizing Task Sequence and Cell Layout for Dual Arm Robot Assembly Using Constraint Programming." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186593.
Full textAbstract:
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.
22
SILVA, Marcos Aurélio Almeida da. "CHORD: constraint handling object-oriented rules with disjunctions." Universidade Federal de Pernambuco, 2009. https://repositorio.ufpe.br/handle/123456789/1955.
Full textAbstract:
Made available in DSpace on 2014-06-12T15:53:28Z (GMT). No. of bitstreams: 2
arquivo1916_1.pdf: 1434494 bytes, checksum: 1b590044040a8dcd13c8953148aade5a (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2009Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
Constraint Handling Object-oriented Rules with Disjunctions (CHORD), é uma extensão orientada a objetos (OO) de CHRv, uma linguagem relacional baseada em regras que foi inicialmente desenhada para a especificação em caixa branca de resolvedores de restrições mas veio a mostrar-se uma linguagem bastante flexível. Flexibilidade esta que vêm sendo demonstrada nos últimos anos pelo grande número de serviços de raciocínio e algoritmos que foram descritos concisamente por meio desta linguagem. Para definir a sintaxe de nossa extensão, nós nos baseamos na abordagem seguida na extensão de Prolog realizada por Frame Logic que é similar à nossa, na qual, a sintaxe de frames foi introduzida para representar construtores OO em cima dos relacionais originais. Além disso, em vez de forçar o usuário (programador) a se adequar à uma semântica pré-definida para esses novos construtores, nós escolhemos uma estratégia inovadora: desacoplar a sintaxe da semântica da linguagem permitindo que o conjunto de hipóteses semânticas seja totalmente configurável. Estes avanços claramente contribuem para o domínio do Raciocínio Automático e da Representação do Conhecimento (AR/KR), dentro do qual CHRv é a linguagem de representa ção do conhecimento mais versátil. Este trabalho também permite a integração dos serviços de raciocínio já providos por CHRv ao estado da arte em linguagens orientadas a objetos reduzindo a quebra de paradigma entre elas. Há também contribuições a outros domínios: em programação declarativa, ao disponibilizar a primeira linguagem a integrar as formas mais poderosas de programação orientada a objetos, baseada em regras e baseada em restrições. No domínio da Web Semântica, nós mostramos que nossa linguagem generaliza a semântica de três dos mais importantes padrões de linguagem de representação do conhecimento, provendo uma solução para o problema recorrente de integração nesta área. No domínio da engenharia guiado por modelos (MDE), este trabalho provê o primeiro mapeamento semântico para modelos UML/OCL, MOF/OCL e transformações de modelo explícitamente configurável e com fundamentação axiomática declarativa e operacional em CFOL. Neste trabalho nós apresentamos as sintaxes abstrata e contreta de CHORD, suas semânticas operacional e declarativa em CFOL, e uma ontologia de hipóteses semânticas para herança. Para validá-lo, nós apresentamos três estudos de caso mostrando que CHORD generaliza UML/OCL, Frame Logic e OWL
23
Pivkina, Inna Valentinovna. "REVISION PROGRAMMING: A KNOWLEDGE REPRESENTATION FORMALISM." Lexington, Ky. : [University of Kentucky Libraries], 2001. http://lib.uky.edu/ETD/ukycosc2001d00022/pivkina.pdf.
Full textAbstract:
Thesis (Ph. D.)--University of Kentucky, 2001.Title from document title page. Document formatted into pages; contains vii, 121 p. : ill. Includes abstract. Includes bibliographical references (p. 116-119).
24
Park, Vincent Se-jin. "AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1193.
Full textAbstract:
Many real life problems can be formulated as constraint satisfaction problems (CSPs). Backtracking search algorithms are usually employed to solve CSPs and in backtracking search the choice of branching strategies can be critical since they specify how a search algorithm can instantiate a variable and how a problem can be reduced into subproblems; that is, they define a search tree. In spite of the apparent importance of the branching strategy, there have been only a few empirical studies about different branching strategies and they all have been tested exclusively for numerical constraints. In this thesis, we employ the three most commonly used branching strategies in solving finite domain CSPs. These branching strategies are described as follows: first, a branching strategy with strong commitment assigns its variables in the early stage of the search as in k-Way branching; second, 2-Way branching guides a search by branching one side with assigning a variable and the other with eliminating the assigned value; third, the domain splitting strategy, based on the least commitment principle, branches by dividing a variable's domain rather than by assigning a single value to a variable. In our experiments, we compared the efficiency of different branching strategies in terms of their execution times and the number of choice points in solving finite domain CSPs. Interestingly, our experiments provide evidence that the choice of branching strategy for finite domain problems does not matter much in most cases--provided we are using an effective variable ordering heuristic--as domain splitting and 2-Way branching end up simulating k-Way branching. However, for an optimization problem with large domain size, the branching strategy with the least commitment principle can be more efficient than the other strategies. This empirical study will hopefully interest other practitioners to take different branching schemes into consideration in designing heuristics.
25
Daoudi, Abderrazak. "Acquisition de contraintes par apprentissage de structures." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT316/document.
Full textAbstract:
La Programmation par contraintes est un cadre général utilisé pour modéliser et résoudre des problèmes combinatoires complexes. Cependant, la modélisation d'un problème sous forme d’un réseau de contraintes nécessite une bonne expertise dans le domaine. Ce niveau d'expertise est un obstacle majeur pour une large diffusion de la programmation de contraintes. Pour remédier à ce problème, plusieurs systèmes d'acquisition de contraintes ont été proposés pour aider l'utilisateur dans la tâche de modélisation. Dans ces systèmes, l'utilisateur ne répond qu'à des questions très simples. L'inconvénient est que lorsqu'aucune connaissance de base n’est fournie, l'utilisateur peut avoir besoin de répondre à un grand nombre de questions pour apprendre toutes les contraintes. Dans cette thèse, nous montrons que l'utilisation de la structure du problème peut améliorer considérablement le processus d'acquisition. Pour ce faire, nous proposons plusieurs techniques. Tout d'abord, nous introduisons le concept de requête de généralisation basée sur une agrégation de variables sous forme detypes. Deuxièmement, pour faire face aux requêtes de généralisation, nous proposons un algorithme de généralisation de contraintes, nommé GENACQ, ainsi que plusieurs stratégies. Troisièmement, pour rendre la construction de requêtes de généralisation totalement indépendante de l'utilisateur, nous proposons l'algorithme MINE&ASK, qui est en mesure d'apprendre la structure au cours du processus d'acquisition de contraintes, et d'utiliser la structure apprise pour générer des requêtes de généralisation. Quatrièmement, pour aller vers un concept générique de requête, nous introduisons la requête de recommandation basée sur la prédiction de liens dans le graphe de contraintes apprises jusqu’à présent. Cinquièmement, nous proposons un algorithme de recommandation de contraintes, ppelé PREDICT&ASK, qui demande à l’utilisateur de classifier des requêtes de recommandation chaque fois que la structure du graphe courant a été modifiée. Enfin, nous intégrons toutes ces nouvelles techniques dans l’algorithme QUACQ, menant à trois nouvelles versions, à savoir G-QUACQ, M- QUACQ, et P-QUACQ. Pour évaluer toutes ces techniques, nous avons fait des expérimentations sur plusieurs jeux de données. Les résultats montrent que les versions étendues améliorent considérablement le QUACQ de baseConstraint Programming is a general framework used to model and solve complex combinatorial problems.However, modeling a problem as a constraint network requires significant expertise in the field.Such level of expertise is a bottleneck to the broader uptake of the constraint technology.To alleviate this issue, several constraint acquisition systems have been proposed to assist thenon-expert user in the modeling task. Nevertheless, in these systems the user is only asked to answervery basic questions. The drawback is that when no background knowledge is provided,the user may need to answer a large number of such questions to learn all the constraints.In this thesis, we show that using the structure of the problem under consideration may improvethe acquisition process a lot. To this aim, we propose several techniques.Firstly, we introduce the concept of generalization query based on an aggregation of variables into types.Secondly, to deal with generalization queries, we propose a constraint generalization algorithm, named GENACQ, together with several strategies. Thirdly, to make the build of generalization queries totally independent of the user, we propose the algorithm MINE&ASK, which is able to learn the structure, during the constraint acquisition process, and to use the learned structure to generate generalization queries. Fourthly, toward a generic concept of query, we introduce the recommendation query based on the link prediction on the current constraint graph. Fifthly, we propose a constraint recommender algorithm, called PREDICT&ASK, that asks recommendation queries, each time the structure of the current graph has been modified. Finally, we incorporate all these new generic techniques into QUACQ algorithm leading to three boosted versions, G-QUACQ, M- QUACQ, and P-QUACQ. To evaluate all these techniques, we have made experiments on several benchmarks. The results show that the extended versions improve drastically the basic QUACQ
26
Blet, Loïc. "Configuration automatique d’un solveur générique intégrant des techniques de décomposition arborescente pour la résolution de problèmes de satisfaction de contraintes." Thesis, Lyon, INSA, 2015. http://www.theses.fr/2015ISAL0085/document.
Full textAbstract:
La programmation par contraintes intègre des algorithmes de résolution génériques dans des langages de modélisation déclaratifs basés sur les contraintes : ces langages permettent de décrire des problèmes combinatoires sous la forme d’un ensemble de variables devant prendre leurs valeurs dans des domaines en satisfaisant des contraintes. Nous introduisons dans cette thèse un algorithme de résolution générique paramétré par : — une stratégie d’exploration de l’espace de recherche, à choisir parmi, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, et backtracking with tree decomposition ; — une heuristique de choix de variables, à choisir parmi, min-domain/ddeg et min-domain/wdeg ; — une technique de propagation de contraintes, à choisir parmi, forward checking et maintaining arc consistency. Ainsi, cet algorithme générique s’instancie en vingt-quatre configurations différentes ; certaines correspondant à des algorithmes connus, d’autres étant nouvelles. Ces vingt- quatre configurations ont été comparées expérimentalement sur un benchmark de plus de mille instances, chaque configuration étant exécutée plusieurs fois sur chaque instance pour tenir compte du non déterminisme des exécutions. Des tests statistiques sont utilisés pour comparer les performances. Cette évaluation expérimentale a permis de mieux comprendre la complémentarité des différents mécanismes de résolution, avec une attention particulière portée sur la capacité à tirer parti de la structure des instances pour accélérer la résolution. Nous identifions notamment treize configurations complémentaires telles que chaque instance de notre benchmark est bien résolue par au moins une des treize configurations. Une deuxième contribution de la thèse est d’introduire un sélecteur capable de choisir automatiquement la meilleure configuration de notre algorithme générique pour chaque nouvelle instance à résoudre : nous décrivons chaque instance par un ensemble de descripteurs et nous utilisons des techniques d’apprentissage automatique pour construire un modèle de choix de configuration à partir de ces descripteurs. Sachant que l’apprentissage est généralement plus difficile quand il y a beaucoup de configurations, nous exprimons le problème du choix du sous-ensemble de configurations pouvant être sélectionnées comme un problème de couverture d’ensemble et nous comparons deux critères de choix : le premier vise à maximiser le nombre d’instances résolues par au moins une configuration et le second vise à maximiser le nombre d’instances pour lesquelles il y a une bonne configuration disponible. Nous montrons expérimentalement que la seconde stratégie obtient généralement de meilleurs résultats, et que le sélecteur obtient de meilleures performances que chacune de nos vingt-quatre configurations initialesConstraint programming integrates generic solving algorithms within declarative languages based on constraints : these languages allow us to describe combinatorial problems as a set of variables which have to take their values in domains while satisfying constraints. Numerous real-life problems can be modelled in such a way, as for instance, planification problems, scheduling problems, . . . These problems are NP-complete in the general case of finite domains. We introduce in this work a generic solving algorithm parameterized by : — a strategy for exploring the search space, to be chosen from the following six, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, and backtracking with tree decomposition ; — a variable ordering heuristic, to be chosen from the following two, min-domain/ddeg and min-domain/wdeg ; — a constraint propagation technique, to be chosen from the following two, forward checking and maintaining arc consistency. Thus, this algorithm leads to 24 different configurations ; some corresponding to already known algorithms, others being new. These 24 configurations have been com- pared experimentally on a benchmark of more than a thousand instances, each configuration being executed several times to take into account the non-determinism of the executions, and a statistical test has been used to compare performances. This experimental evaluation allowed us to better understand the complementarity of the different solving mechanisms, with a focus on the ability to exploit the structure of the instances to speed up the solving process. We identify 13 complementary configurations such that every instance of our benchmark is well solved by at least one of the 13 configurations. A second contribution of this work is to introduce a selector able to choose automatically the best configuration of our generic solver for each new instance to be solved : we describe each instance by a set of features and we use machine learning techniques to build a model to choose a configuration based on these features. Knowing that the learning process is generally harder when there are many configurations to choose from, we state the problem of choosing a subset of configurations that can be picked as a set covering problem and we compare two criterion : the first one aims to maximize the number of instances solved by at least one configuration and the second one aims to maximize the number of instances for which there is a good configuration available. We show experimentally that the second strategy obtains generally better results and that the selector obtains better performances than each of the 24 initial configurations
27
Olofsson, Emil. "Improved algorithm for weighted matching of employees." Thesis, Linköpings universitet, Databas och informationsteknik, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-122763.
Full textAbstract:
This report gives the reader a detailed description of a computer engineering master thesis work done at the company Netlight Consulting AB. Netlight Consulting AB is a growing IT consulting company based in Stockholm with offices in major cities across Europe. One of their key success factors is their focus on personal and professional development amongst all employees. An essential part of this development program consist of reoccurring evaluation periods, where every employee receives written constructive feedback from some of their co-workers. This thesis’ focus lies in improving the algorithm that organizes which employee should evaluate who. The original algorithm turned out to harbor a number of flaws, e.g. it was not always able to deliver a satisfactory matching where every participant received the minimum number of evaluations. In this thesis a new matching algorithm has been implemented that is platform independent and that facilitates future modifications with accessible source code written in Java. The input data for the matching algorithm, i.e. the set of all potential evaluation pairs, is of importance to obtain satisfactory matching results. The number of potential evaluation pairs determines the number of possible matching combinations, which in turn increases the probability to find a satisfactory matching. In this thesis the input data has been extended by utilizing a data mining technique known as SONAR. Two different data mining sources were evaluated, and one of them is shown to extend the number of potential evaluation pairs in the matching input by 20%. Finally, a new feature to support assignment of different evaluation sizes was added to the matching algorithm.
28
Paris, Nicolas. "Intégration de techniques CSP pour la résolution du problème WCSP." Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0405/document.
Full textAbstract:
Cette thèse se situe dans le contexte de la programmation par contraintes (CP). Plus précisément, nous nous sommes intéressés au problème de satisfaction de contraintes pondérées (WCSP). De nombreuses approches ont été proposées pour traiter ce problème d’optimisation. Les méthodes les plus efficaces utilisent des cohérences locales souples sophistiquées comme par exemple la cohérence d’arc directionnelle complète FDAC∗, la cohérence d’arc directionnelle existentielle EDAC∗, etc. Établies grâce à des opérations de transferts de coût préservant l’équivalence des réseaux, l’utilisation de ces cohérences permet généralement d’accélérer la résolution en réduisant l’espace de recherche via la suppression de valeurs et le calcul de bornes inférieures utiles en pratique. Cependant, l’utilisation de ces méthodes pose un problème lorsque l’arité des contraintes augmente de manière significative. L’efficacité des techniques du cadre du problème de satisfaction de contraintes (CSP) étant avérée, nous pensons que l’intégration de techniques CSP peut être très utile à la résolution d’instances WCSP. Dans cette thèse, nous proposons tout d’abord un algorithme de filtrage établissant la cohérence d’arc souple généralisée GAC∗ sur des contraintes tables souples de grande arité. Cette approche combine la technique de réduction tabulaire simple (STR), issue du cadre CSP, et le principe de transfert de coûts. Notre approche qui est polynomiale calcule efficacement pour chaque valeur les coûts minimaux dans les tuples explicites et implicites des contraintes tables souples. Ces coûts minimaux sont ensuite utilisés pour transférer les coûts afin d’établir GAC∗. Dans un second temps, nous proposons une approche alternative aux méthodes de résolution habituelles du problème WCSP. Elle consiste à résoudre une instance WCSP en résolvant une séquence d’instances CSP classiques obtenues depuis cette instance WCSP. À partir d’une instance CSP dans laquelle toutes les contraintes de l’instanceWCSP d’origine sont durcies au maximum, les instances CSP suivantes correspondent à un relâchement progressif de contraintes de l’instance WCSP déterminées par l’extraction de noyaux insatisfaisables minimaux (MUC) depuis les réseaux insatisfaisables de la séquence. Nos résultats expérimentaux montrent que notre première approche est compétitive avec l’état de l’art, tandis que la deuxième représente une approche alternative aux méthodes de résolutionhabituelles d’instances WCSPThis thesis is in the context of constraint programming (CP). Specifically, we are interested in the Weighted Constraint Satisfaction Problem (WCSP). Many approaches have been proposed to handle this optimization problem. The most effective methods use sophisticated soft local consistencies such as, for example, full directional arc consistency FDAC∗, existential directional arc consistency EDAC∗, etc. Established by equivalence preserving transformations (cost transfer operations), the use of these consistencies generally allows both to accelerate the resolution by reducing the search space through the elimination of values and to compute lower bounds useful in practice. However, these methods reach theirlimits when the arity of constraints increases significantly. The techniques of the Constraint Satisfaction Problem framework (CSP) having proved efficienty, we believe that the integration of CSP techniques can be very useful for solving WCSP instances. In this thesis, we first propose a filtering algorithm to enforce a soft version of generalized arc consistency (GAC∗) on soft table constraints of large arity. This approach combines the techniques of simple tabular reduction (STR), from the CSP framework, with the techniques of cost transfer. Our approach, proved polynomial, efficiently calculates for each value the minimum cost of the explicit and implicit tuples from soft table constraints. The minimum costs are thenused to transfer costs to establish GAC∗. In a second step, we propose an alternative approach to the usual techniques to solve WCSP. The principle is to solve a WCSP instance by solving a sequence of classical CSP instances obtained from this WCSP instance. From a CSP instance containing all the constraints hardened to the maximum from the WCSP instance, the next CSP instances correspond to a progressive relaxation of constraints defined by extraction of minimal unsatisfiable cores (MUC) from unsatisfiable networks of the sequence. Our experimental results show that our first approach is competitive with the state-of-the-art, whereas the second one represents an alternative approach to the usual methods to solve WCSP instances
29
Tybon, Robert, and n/a. "Generating Solutions to the Jigsaw Puzzle Problem." Griffith University. School of Management, 2004. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20041101.085937.
Full textAbstract:
This thesis examines the problem of the automated re-assembly of jigsaw puzzles. The objectives of this research are as follows: to provide a clear statement of the jigsaw puzzle re-assembly problem; to find out which solution technique is best suited to this problem; to determine the level of sensitivity of the proposed solution technique when solving different variations of this problem; and to explore solution methods for solving incomplete jigsaw puzzles (puzzles with missing pieces). The jigsaw puzzle re-assembly problem has been investigated only intermittently in the research literature. This work presents an extensive examination of the suitability and efficiency of the standard solution techniques that can be applied to this problem. A detailed comparison between different solution methods including Genetic Algorithms, Simulated Annealing, Tabu Search and Constraint Satisfaction Programming, shows that a constraint-based approach is the most efficient method of generating solutions to the jigsaw puzzle problem. The proposed re-assembly algorithm is successful. Consequently, it can be used in development of automated solution generators for other problems in the same domain, thus creating new theoretical and applied directions in this field of research. One potential theoretical line of research concerns jigsaw puzzles that do not have a complete set of puzzle pieces. These incomplete puzzles represent a difficult aspect of this problem that is outlined but can not be resolved in the current research. The computational experiments conducted in this thesis demonstrate that the proposed algorithm being optimised to re-assemble the jigsaw puzzles is not efficient when applied to the puzzles with missing pieces. Further work was undertaken to modify the proposed algorithm to enable efficient re-assembly of incomplete jigsaw puzzles. Consequently, an original heuristic strategy, termed Empty Slot Prediction, was developed to support the proposed algorithm, and proved successful when applied to certain sub-classes of this problem. The results obtained indicate that no one algorithm can be used to solve the multitude of possible scenarios involved in the re-assembly of incomplete jigsaw puzzles. Other variations of the jigsaw puzzle problem that still remain unsolved are presented as avenues for future research. The solution of this problem involves a number of procedures with significant applications in other computer-related areas such as pattern recognition, feature and shape description, boundary-matching, and heuristic modelling. It also has more practical applications in robotic vision and reconstruction of broken artefacts in archaeology.
30
Tybon, Robert. "Generating Solutions to the Jigsaw Puzzle Problem." Thesis, Griffith University, 2004. http://hdl.handle.net/10072/366062.
Full textAbstract:
This thesis examines the problem of the automated re-assembly of jigsaw puzzles. The objectives of this research are as follows: to provide a clear statement of the jigsaw puzzle re-assembly problem; to find out which solution technique is best suited to this problem; to determine the level of sensitivity of the proposed solution technique when solving different variations of this problem; and to explore solution methods for solving incomplete jigsaw puzzles (puzzles with missing pieces). The jigsaw puzzle re-assembly problem has been investigated only intermittently in the research literature. This work presents an extensive examination of the suitability and efficiency of the standard solution techniques that can be applied to this problem. A detailed comparison between different solution methods including Genetic Algorithms, Simulated Annealing, Tabu Search and Constraint Satisfaction Programming, shows that a constraint-based approach is the most efficient method of generating solutions to the jigsaw puzzle problem. The proposed re-assembly algorithm is successful. Consequently, it can be used in development of automated solution generators for other problems in the same domain, thus creating new theoretical and applied directions in this field of research. One potential theoretical line of research concerns jigsaw puzzles that do not have a complete set of puzzle pieces. These incomplete puzzles represent a difficult aspect of this problem that is outlined but can not be resolved in the current research. The computational experiments conducted in this thesis demonstrate that the proposed algorithm being optimised to re-assemble the jigsaw puzzles is not efficient when applied to the puzzles with missing pieces. Further work was undertaken to modify the proposed algorithm to enable efficient re-assembly of incomplete jigsaw puzzles. Consequently, an original heuristic strategy, termed Empty Slot Prediction, was developed to support the proposed algorithm, and proved successful when applied to certain sub-classes of this problem. The results obtained indicate that no one algorithm can be used to solve the multitude of possible scenarios involved in the re-assembly of incomplete jigsaw puzzles. Other variations of the jigsaw puzzle problem that still remain unsolved are presented as avenues for future research. The solution of this problem involves a number of procedures with significant applications in other computer-related areas such as pattern recognition, feature and shape description, boundary-matching, and heuristic modelling. It also has more practical applications in robotic vision and reconstruction of broken artefacts in archaeology.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Management
Faculty of Commerce and Management
Full Text
31
Boukadida, Haykel. "Création automatique de résumés vidéo par programmation par contraintes." Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S074/document.
Full textAbstract:
Cette thèse s’intéresse à la création automatique de résumés de vidéos. L’idée est de créer de manière adaptative un résumé vidéo qui prenne en compte des règles définies sur le contenu audiovisuel d’une part, et qui s’adapte aux préférences de l’utilisateur d’autre part. Nous proposons une nouvelle approche qui considère le problème de création automatique de résumés sous forme d’un problème de satisfaction de contraintes. La solution est basée sur la programmation par contraintes comme paradigme de programmation. Un expert commence par définir un ensemble de règles générales de production du résumé, règles liées au contenu multimédia de la vidéo d’entrée. Ces règles de production sont exprimées sous forme de contraintes à satisfaire. L’utilisateur final peut alors définir des contraintes supplémentaires (comme la durée souhaitée du résumé) ou fixer des paramètres de haut niveau des contraintes définies par l’expert. Cette approche a plusieurs avantages. Elle permet de séparer clairement les règles de production des résumés (modélisation du problème) de l’algorithme de génération de résumés (la résolution du problème par le solveur de contraintes). Le résumé peut donc être adapté sans qu’il soit nécessaire de revoir tout le processus de génération des résumés. Cette approche permet par exemple aux utilisateurs d’adapter le résumé à l’application cible et à leurs préférences en ajoutant une contrainte ou en modifiant une contrainte existante, ceci sans avoir à modifier l’algorithme de production des résumés. Nous avons proposé trois modèles de représentation des vidéos qui se distinguent par leur flexibilité et leur efficacité. Outre les originalités liées à chacun des trois modèles, une contribution supplémentaire de cette thèse est une étude comparative de leurs performances et de la qualité des résumés résultants en utilisant des mesures objectives et subjectives. Enfin, et dans le but d’évaluer la qualité des résumés générés automatiquement, l’approche proposée a été évaluée par des utilisateurs à grande échelle. Cette évaluation a impliqué plus de 60 personnes. Ces expériences ont porté sur le résumé de matchs de tennisThis thesis focuses on the issue of automatic video summarization. The idea is to create an adaptive video summary that takes into account a set of rules defined on the audiovisual content on the one hand, and that adapts to the users preferences on the other hand. We propose a novel approach that considers the problem of automatic video summarization as a constraint satisfaction problem. The solution is based on constraint satisfaction programming (CSP) as programming paradigm. A set of general rules for summary production are inherently defined by an expert. These production rules are related to the multimedia content of the input video. The rules are expressed as constraints to be satisfied. The final user can then define additional constraints (such as the desired duration of the summary) or enter a set of high-level parameters involving to the constraints already defined by the expert. This approach has several advantages. This will clearly separate the summary production rules (the problem modeling) from the summary generation algorithm (the problem solving by the CSP solver). The summary can hence be adapted without reviewing the whole summary generation process. For instance, our approach enables users to adapt the summary to the target application and to their preferences by adding a constraint or modifying an existing one, without changing the summaries generation algorithm. We have proposed three models of video representation that are distinguished by their flexibility and their efficiency. Besides the originality related to each of the three proposed models, an additional contribution of this thesis is an extensive comparative study of their performance and the quality of the resulting summaries using objective and subjective measures. Finally, and in order to assess the quality of automatically generated summaries, the proposed approach was evaluated by a large-scale user evaluation. This evaluation involved more than 60 people. All these experiments have been performed within the challenging application of tennis match automatic summarization
32
Cervoni, Laurent. "Méthodologies et techniques de résolution de problèmes avec contraintes. Application en programmation logique avec objets : cooxi." Rouen, 1994. http://www.theses.fr/1994ROUES032.
Full textAbstract:
Cette thèse se présente tout d'abord comme une étude exploratoire des techniques, des méthodes et des systèmes de résolution de problèmes avec contraintes, basée sur un retour d'expérience industriel. Devant l'émergence, ces dernières années, de nouvelles techniques ou outils pour résoudre les problèmes fortement combinatoires, ce document se propose de restituer plus précisément le contexte de la résolution de ces problèmes complexes en : passant en revue les approches disponibles, collectant le maximum de techniques, les comparant ; précisant les liens entre recherche opérationnelle et programmation par contraintes. Une méthodologie répondant de manière efficace à ces problèmes complexes (dits avec contraintes) est alors suggérée. Enfin, la dernière partie étudie les perspectives de quelques techniques au travers d'une structure d'accueil en programmation logique
33
Chadim, Petr. "Automatické jazzové aranžmá." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2011. http://www.nusl.cz/ntk/nusl-237040.
Full textAbstract:
This Thesis is focused on the arranging of the melody, which is accompanied by jazz chords. It deals with creating a more harmonious voices using Block Voicing method. Distribution to target notes and passing notes is made using techniques of constraint programming (CSP). Passing notes are reharmonized by dominant seventh chord or by parallel chord. Using CSP a bass part is also created. To solve CSP is used Gecode library. The harmonious voices are arranged by Four Part Close Voicing. The application result is a tool for the music arranger.
34
Vautard, Jérémie. "Modélisation et résolution de problèmes de décision et d'optimisation hiérarchiques en utilisant des contraintes quantifiées." Phd thesis, Université d'Orléans, 2010. http://tel.archives-ouvertes.fr/tel-00486721.
Full textAbstract:
Cette thèse s'inscrit dans le cadre de la programmation par contraintes quantifiées, un formalisme étendantla programmation par contraintes classique en ajoutant aux variables des quantificateurs existentiels ouuniversels, ce qui apporte en théorie une expressivité suffisante pour modéliser des problèmes avec adversaireou incertitude sur certains paramètres sous forme de problèmes appelés QCSP (Quantified Constraintsatisfaction Problem).Nous commençons par apporter une réponse aux difficultés de modélisation de problèmes réels dont estfrappée la programmation par contraintes quantifiées en introduisant une extension aux QCSP permettantd'expliciter les actions possibles de l'agent principal et de son adversaire. Puis, nous décrivons différentproblèmes grâce à ce formalisme, et discutons de la place de cette extension parmi les formalismes voisins créésen réponse à cette même difficulté de modélisation. Enfin, nous nous intéressons à la notion d'optimisationdans le cas des contraintes quantifiées, et apportons un formalisme d'optimisation de contraintes quantifiéespermettant d'exprimer des problèmes multi-niveaux non linéaires.
35
"Quantified weighted constraint satisfaction problems." 2011. http://library.cuhk.edu.hk/record=b5894615.
Full textAbstract:
Mak, Wai Keung Terrence.Thesis (M.Phil.)--Chinese University of Hong Kong, 2011.
Includes bibliographical references (p. 100-104).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Constraint Satisfaction Problems --- p.1
Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.2
Chapter 1.3 --- Quantified Constraint Satisfaction Problems --- p.3
Chapter 1.4 --- Motivation and Goal --- p.4
Chapter 1.5 --- Outline of the Thesis --- p.6
Chapter 2 --- Background --- p.7
Chapter 2.1 --- Constraint Satisfaction Problems --- p.7
Chapter 2.1.1 --- Backtracking Tree Search --- p.9
Chapter 2.1.2 --- Local Consistencies for solving CSPs --- p.11
Node Consistency (NC) --- p.13
Arc Consistency (AC) --- p.14
Searching by Maintaining Arc Consistency --- p.16
Chapter 2.1.3 --- Constraint Optimization Problems --- p.17
Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.19
Chapter 2.2.1 --- Branch and Bound Search (B&B) --- p.23
Chapter 2.2.2 --- Local Consistencies for WCSPs --- p.25
Node Consistency --- p.26
Arc Consistency --- p.28
Chapter 2.3 --- Quantified Constraint Satisfaction Problems --- p.32
Chapter 2.3.1 --- Backtracking Free search --- p.37
Chapter 2.3.2 --- Consistencies for QCSPs --- p.38
Chapter 2.3.3 --- Look Ahead for QCSPs --- p.45
Chapter 3 --- Quantified Weighted CSPs --- p.48
Chapter 4 --- Branch & Bound with Consistency Techniques --- p.54
Chapter 4.1 --- Alpha-Beta Pruning --- p.54
Chapter 4.2 --- Consistency Techniques --- p.57
Chapter 4.2.1 --- Node Consistency --- p.62
Overview --- p.62
Lower Bound of A-Cost --- p.62
Upper Bound of A-Cost --- p.66
Projecting Unary Costs to Cθ --- p.67
Chapter 4.2.2 --- Enforcing Algorithm for NC --- p.68
Projection Phase --- p.69
Pruning Phase --- p.69
Time Complexity --- p.71
Chapter 4.2.3 --- Arc Consistency --- p.73
Overview --- p.73
Lower Bound of A-Cost --- p.73
Upper Bound of A-Cost --- p.75
Projecting Binary Costs to Unary Constraint --- p.75
Chapter 4.2.4 --- Enforcing Algorithm for AC --- p.76
Projection Phase --- p.77
Pruning Phase --- p.77
Time complexity --- p.79
Chapter 5 --- Performance Evaluation --- p.83
Chapter 5.1 --- Definitions of QCOP/QCOP+ --- p.83
Chapter 5.2 --- Transforming QWCSPs into QCOPs --- p.90
Chapter 5.3 --- Empirical Evaluation --- p.91
Chapter 5.3.1 --- Random Generated Problems --- p.92
Chapter 5.3.2 --- Graph Coloring Game --- p.92
Chapter 5.3.3 --- Min-Max Resource Allocation Problem --- p.93
Chapter 5.3.4 --- Value Ordering Heuristics --- p.94
Chapter 6 --- Concluding Remarks --- p.96
Chapter 6.1 --- Contributions --- p.96
Chapter 6.2 --- Limitations and Related Works --- p.97
Chapter 6.3 --- Future Works --- p.99
Bibliography --- p.100
36
"Integration of constraint programming and linear programming techniques for constraint satisfaction problem and general constrained optimization problem." 2001. http://library.cuhk.edu.hk/record=b5890598.
Full textAbstract:
Wong Siu Ham.Thesis (M.Phil.)--Chinese University of Hong Kong, 2001.
Includes bibliographical references (leaves 131-138).
Abstracts in English and Chinese.
Abstract --- p.ii
Acknowledgments --- p.vi
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Motivation for Integration --- p.2
Chapter 1.2 --- Thesis Overview --- p.4
Chapter 2 --- Preliminaries --- p.5
Chapter 2.1 --- Constraint Programming --- p.5
Chapter 2.1.1 --- Constraint Satisfaction Problems (CSP's) --- p.6
Chapter 2.1.2 --- Satisfiability (SAT) Problems --- p.10
Chapter 2.1.3 --- Systematic Search --- p.11
Chapter 2.1.4 --- Local Search --- p.13
Chapter 2.2 --- Linear Programming --- p.17
Chapter 2.2.1 --- Linear Programming Problems --- p.17
Chapter 2.2.2 --- Simplex Method --- p.19
Chapter 2.2.3 --- Mixed Integer Programming Problems --- p.27
Chapter 3 --- Integration of Constraint Programming and Linear Program- ming --- p.29
Chapter 3.1 --- Problem Definition --- p.29
Chapter 3.2 --- Related works --- p.30
Chapter 3.2.1 --- Illustrating the Performances --- p.30
Chapter 3.2.2 --- Improving the Searching --- p.33
Chapter 3.2.3 --- Improving the representation --- p.36
Chapter 4 --- A Scheme of Integration for Solving Constraint Satisfaction Prob- lem --- p.37
Chapter 4.1 --- Integrated Algorithm --- p.38
Chapter 4.1.1 --- Overview of the Integrated Solver --- p.38
Chapter 4.1.2 --- The LP Engine --- p.44
Chapter 4.1.3 --- The CP Solver --- p.45
Chapter 4.1.4 --- Proof of Soundness and Completeness --- p.46
Chapter 4.1.5 --- Compared with Previous Work --- p.46
Chapter 4.2 --- Benchmarking Results --- p.48
Chapter 4.2.1 --- Comparison with CLP solvers --- p.48
Chapter 4.2.2 --- Magic Squares --- p.51
Chapter 4.2.3 --- Random CSP's --- p.52
Chapter 5 --- A Scheme of Integration for Solving General Constrained Opti- mization Problem --- p.68
Chapter 5.1 --- Integrated Optimization Algorithm --- p.69
Chapter 5.1.1 --- Overview of the Integrated Optimizer --- p.69
Chapter 5.1.2 --- The CP Solver --- p.74
Chapter 5.1.3 --- The LP Engine --- p.75
Chapter 5.1.4 --- Proof of the Optimization --- p.77
Chapter 5.2 --- Benchmarking Results --- p.77
Chapter 5.2.1 --- Weighted Magic Square --- p.77
Chapter 5.2.2 --- Template design problem --- p.78
Chapter 5.2.3 --- Random GCOP's --- p.79
Chapter 6 --- Conclusions and Future Work --- p.97
Chapter 6.1 --- Conclusions --- p.97
Chapter 6.2 --- Future work --- p.98
Chapter 6.2.1 --- Detection of implicit equalities --- p.98
Chapter 6.2.2 --- Dynamical variable selection --- p.99
Chapter 6.2.3 --- Analysis on help of linear constraints --- p.99
Chapter 6.2.4 --- Local Search and Linear Programming --- p.99
Appendix --- p.101
Proof of Soundness and Completeness --- p.101
Proof of the optimization --- p.126
Bibliography --- p.130
37
Raja, Basalat Ali. "Programming using a constraint satisfaction system for robotics." Thesis, 1992. http://hdl.handle.net/1911/13623.
Full textAbstract:
Programming robots is a difficult task, especially for autonomous robots that must operate in an open, unstructured environment. A programmer building such a system should have a number of sophisticated tools at his/her disposal. In this thesis, we provide the basic framework for the development of a programming language that can be used to program an autonomous robot. The programming language is based on a constraint system. We describe our implementation of the constraint system, as well as our research done into developing a language based on this system.
38
Hebrard, Emmanuel Computer Science & Engineering Faculty of Engineering UNSW. "Robust solutions for constraint satisfaction and optimisation under uncertainty." 2007. http://handle.unsw.edu.au/1959.4/40765.
Full textAbstract:
We develop a framework for finding robust solutions of constraint programs. Our approach is based on the notion of fault tolerance. We formalise this concept within constraint programming, extend it in several dimensions and introduce some algorithms to find robust solutions efficiently. When applying constraint programming to real world problems we often face uncertainty. Whilst reactive methods merely deal with the consequences of an unexpected change, taking a more proactive approach may guarantee a certain level of robustness. We propose to apply the fault tolerance framework, introduced in [Ginsberg 98], to constraint programming: A robust solution is one such that a small perturbation only requires a small response. We identify, define and classify a number of abstract problems related to stability within constraint satisfaction or optimisation. We propose some efficient and effective algorithms for solving these problems. We then extend this framework by allowing the repairs and perturbations themselves to be constrained. Finally, we assess the practicality of this framework on constraint satisfaction and scheduling problems.
39
Yeh, Chieh-Jung, and 葉杰榮. "The Development of Timetabling System Using Constraint Satisfaction Programming." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/89326291752260315097.
Full textAbstract:
碩士國立高雄第一科技大學
資訊管理系
90
The timetabling problem is generally considered as a resources allocation problem in OR, where resources of teachers, students, classrooms, and courses are to be allocated into timeslots of a weekly timetable to achieve an objective function; while subject to constraints among resources. The objective function is to offer a course schedule that can satisfy the needs of students in taking both required and elective courses, fulfill the teaching responsibility of teachers, and, at the same time, minimize slack timeslots within a timetable or maximize the freedom of course selection. The heart of the problem is the constraints that exist as regulations, within each resource, and between resources; and have exhibited the unwelcome nature of combinatorial problems. While there have been many optimization solution approaches suggested in the past, the increasing need to offer a working environment with humanity has forced the management to take into consideration many additional soft constraints. With the understanding that it is impossible to satisfy all personal needs of teaching staff, one needs to look for new solution approaches that can satisfy all hard constraints and as many soft constraints as possible. This study focuses on the application of Constraint Satisfaction Programming to develop a class timetable, which consists of hard constraints that must be satisfied to produce a feasible solution, and soft constraints that represent the ideal cognitive model of teaching staff. The actual course scheduling needs of the Department of Information Management of National Kaoshuing First University of Science and Technology is used for this study.
40
"Consistency techniques for linear global cost functions in weighted constraint satisfaction." 2012. http://library.cuhk.edu.hk/record=b5549068.
Full textAbstract:
在加權約束滿足問題中使用多元價值函數需要強大的一致相容性技術，而在多元價值函數中維護一致相容性並不是一項簡單的工作。能在多項式時間內找出多元價值函數的最少價值，而且不被投影及擴展操作所破壞，是讓該多元價值函數實用的主要條件。但是，有很多有用的多元價值函數尚未有多項式時間的算法找出其最少價值，因而未能在加權約束滿足問題中實用地使用它們。我們定義了一類可被建構為整數線性規劃的多元價值函數，並稱它們為多項式線性投影安全(PLPS)價值函數。該類價值函數的最少價值能由解答整數線性規劃中找出，而這個特性並不會被投影及擴展操作所影響。線性鬆馳能讓我們找出一個最少價值的接近值，並避免了解答整數線性規劃的NP-難困難性。該最少價值的接近值能作為最少價值的下限以供維護鬆馳一致相容性概念。
在實踐中我們示範了使用PLPS價值函數的組合的好處。我們定義了整數多項式線性投影安全(IPLPS)價值函數作為PLPS價值函數的一個子類，並讓我們表示組合該類價值函數的好處。在一個加權約束滿足問題的一致相容性α中，我們表示了在IPLPS價值函數的組合中維護鬆馳α比在單獨的IPLPS價值函數中維護α強大。這結果可用在能在多項式時間中找出最少價值，但不能在多項式時間中找出它們的組合的最少價值的IPLPS價值函數中。基於流量投影安全(flow-based projection-safe)及可多項式分解(polynomially decomposable)價值函數的一個重要的子類屬於這一類的IPLPS價值函數。
在實驗中我們展示了我們的方法的可行性和效率。無論在時間或搜索空間的改進上，與現有的方法相比，在使用PLPS價值函數的組合和 IPLPS價值函數的組合時我們觀察到一個數量級的改進。
The solving of Weighted CSP (WCSP) with global cost functions relies on powerful consistency techniques, but enforcing these consistencies on global cost functions is not a trivial task. Lee and Leung suggest that a global cost function can be used practically if we can find its minimum cost and perform projections/extensions on it in polynomial time, and at the same time projections and extensions should not destroy those conditions. However, there are many useful cost functions with no known polynomial time algorithms to compute the minimum costs yet.
We propose a special class of global cost functions which can be modeled as integer linear programs, called polynomially linear projection-safe (PLPS) cost functions. We show that their minimum cost can be computed by integer programming and this property is unaffected by projections/extensions. By linear relaxation we can avoid the possible NP-hard time taken to solve the integer programs, as the approximation of their actual minimum costs can be obtained to serve as a good lower bound in enforcing the relaxed forms of common consistencies.
We show the benets of using the conjunctions of PLPS cost functions empir-ically in terms of runtime. We introduce integral polynomially linear projection-safe (IPLPS) cost functions as a subclass of PLPS cost functions whose allow us to characterize the benets of using the conjunctions of them. Given a standard WCSP consistency α, we give theorems showing that maintaining relaxed α on a conjunction of IPLPS cost functions is stronger than maintaining α on the individual cost functions. A useful application of our method is on some IPLPS global cost functions, whose minimum cost computations are tractable and yet those for their conjunctions are not. We show that an important subclass of flow-based projection-safe and polynomially decomposable cost functions falls into this category.
Experiments are conducted to demonstrate the feasibility and efciency of our framework. We observe orders of magnitude in runtime and search space improvements by using the conjunctions of PLPS and IPLPS cost functions with relaxed consistencies when compared with the existing approaches.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Shum, Yu Wai.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2012.
Includes bibliographical references (leaves 87-92).
Abstracts also in Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Weighted Constraint Satisfaction Problems --- p.2
Chapter 1.2 --- Motivation and Goal --- p.2
Chapter 1.3 --- Outline of the Thesis --- p.4
Chapter 2 --- Related Work --- p.6
Chapter 2.1 --- Soft Constraint Frameworks --- p.6
Chapter 2.2 --- Integer Linear Programming --- p.8
Chapter 2.3 --- Global Cost Functions in WCSP --- p.8
Chapter 3 --- Background --- p.11
Chapter 3.1 --- Weighted Constraint Satisfaction Problems --- p.11
Chapter 3.1.1 --- Branch and Bound Search --- p.14
Chapter 3.1.2 --- Local consistencies in WCSP --- p.15
Chapter 3.1.3 --- Global Cost Functions --- p.30
Chapter 3.2 --- Integer Linear Programming --- p.31
Chapter 4 --- Polynomially Linear Projection-Safe Cost Functions --- p.33
Chapter 4.1 --- Non-tractable Global Cost Functions in WCSPs --- p.34
Chapter 4.2 --- Polynomially Linear Projection-Safe Cost Functions --- p.37
Chapter 4.3 --- Relaxed Consistencies on Polynomially Linear Projection-Safe Cost Functions --- p.44
Chapter 4.4 --- Conjoining Polynomially Linear Projection-Safe Cost Functions --- p.50
Chapter 4.5 --- Modeling Global Cost Functions as Polynomially Linear Projection- Safe Cost Functions --- p.53
Chapter 4.5.1 --- The SOFT SLIDINGSUM{U+1D48}{U+1D52}{U+1D9C} Cost Function --- p.53
Chapter 4.5.2 --- The SOFT EGCC{U+1D5B}{U+1D43}{U+02B3} Cost Function --- p.54
Chapter 4.5.3 --- The SOFT DISJUNCTIVE/CUMULATIVE Cost Function --- p.56
Chapter 4.6 --- Implementation Issues --- p.59
Chapter 4.7 --- Experimental Results --- p.60
Chapter 4.7.1 --- Generalized Car Sequencing Problem --- p.62
Chapter 4.7.2 --- Magic Series Problem --- p.63
Chapter 4.7.3 --- Weighted Tardiness Scheduling Problem --- p.65
Chapter 5 --- Integral Polynomially Linear Projection-Safe Cost Functions --- p.68
Chapter 5.1 --- Integral Polynomially Linear Projection-Safe Cost Functions --- p.69
Chapter 5.2 --- Conjoining Global Cost Functions as IPLPS --- p.72
Chapter 5.3 --- Experimental Results --- p.76
Chapter 5.3.1 --- Car Sequencing Problem --- p.77
Chapter 5.3.2 --- Examination Timetabling Problem --- p.78
Chapter 5.3.3 --- Fair Scheduling --- p.79
Chapter 5.3.4 --- Comparing WCSP Approach with Integer Linear programming Approach --- p.81
Chapter 6 --- Conclusions --- p.83
Chapter 6.1 --- Contributions --- p.83
Chapter 6.2 --- Future Work --- p.85
Bibliography --- p.87
41
"Increasing symmetry breaking by preserving target symmetries and eliminating eliminated symmetries in constraint satisfaction." 2012. http://library.cuhk.edu.hk/record=b5549127.
Full textAbstract:
在約束滿足問題中，破壞指數量級數量的所有對稱通常過於昂貴。在實踐中，我們通常只有效地破壞對稱的一個子集。我們稱之為目標對稱。在靜態對稱破壞中，我們的目標是發佈一套約束去破壞這些目標對稱，以達到減少解集以及搜索空間的效果。一個問題中的所有對稱之間是互相交織的。一個旨在特定對稱的破壞對稱約束几乎總會產生副作用，而不僅僅破壞了預期的對稱。破壞相同目標對稱的不同約束可以有不同的副作用。傳統智慧告訴我們應該選擇一個破壞更多對稱從而有更多副作用的破壞對稱約束。雖然這樣的說法在許多方面上都是有效的，我們應該更加注意副作用發生的地方。給與一個約束滿足問題，一個對稱被一個約束保留當且僅當該對稱仍然是新的約束滿足問題的對稱。這個新的約束滿足問題是有原問題加上該約束組成的。我們給出定律和例子，以表明發佈儘量保留目標對稱以及限制它的副作用發生在非目標對稱上的破壞約束是有利的。這些好處來自于被破壞的對稱數目以及一個對稱被破壞（或消除）的程度，并導致一個較小的解集和搜索空間。但是，對稱不一定會被保留。我們顯示，旨在一個已經被消除的目標對稱的破壞對稱約束仍然可以被發佈。我們建議根據問題的約束以及其他破壞對稱約束來選擇破壞對稱約束，以繼續消除更多的對稱。我們進行了廣泛的實驗來確認我們的建議的可行性與效率。
Breaking the exponential number of all symmetries of a constraint satisfaction problem is often too costly. In practice, we often aim at breaking a subset of the symmetries efficiently, which we call target symmetries. In static sym-metry breaking, the goal is to post a set of constraints to break these target symmetries in order to reduce the solution set and thus also the search space. Symmetries of a problem are all intertwined. A symmetry breaking constraint intended for a particular symmetry almost always breaks more than just the intended symmetry as a side-effect. Different constraints for breaking the same target symmetry can have different side-effects. Conventional wisdom suggests that we should select a symmetry breaking constraint that has more side-effects by breaking more symmetries. While this wisdom is valid in many ways, we should be careful where the side-effects take place.
A symmetry σ of a CSP P =(V, D, C) is preserved by a set of symmetry breaking constraints C{U+02E2}{U+1D47} i σ is a symmetry of P¹ =(V, D, CU C{U+02E2}{U+1D47}). We give theorems and examples to demonstrate that it is beneficial to post symmetry breaking constraints that preserve the target symmetries and restrict the side-effects to only non-target symmetries as much as possible. The benefits are in terms of the number of symmetries broken and the extent to which a symmetry is broken (or eliminated), resulting in a smaller solution set and search space. However, symmetry preservation may not always hold. We illustrate that symmetry breaking constraints, which aim at a target symmetry that is already eliminated, can still be posted. To continue eliminating more symmetries, we suggest to select symmetry breaking constraints based on problem constraints and other symmetry breaking constraints. Extensive experiments are also conducted to confirm the feasibility and efficiency of our proposal empirically.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Li, Jingying.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2012.
Includes bibliographical references (leaves 101-112).
Abstracts also in Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Constraint Satisfaction Problems --- p.1
Chapter 1.2 --- Motivation and Goals --- p.3
Chapter 1.3 --- Outline of Thesis --- p.5
Chapter 2 --- Background --- p.8
Chapter 2.1 --- Constraint Satisfaction Problems --- p.8
Chapter 2.1.1 --- Backtracking Search --- p.9
Chapter 2.1.2 --- Consistency Techniques --- p.12
Chapter 2.1.3 --- Local Consistencies with Backtracking Search --- p.15
Chapter 2.2 --- Symmetry Breaking in CSPs --- p.16
Chapter 2.2.1 --- Symmetry Classes --- p.18
Chapter 2.2.2 --- Breaking Symmetries --- p.22
Chapter 2.2.3 --- Variable and Value Symmetries --- p.23
Chapter 2.2.4 --- Symmetry Breaking Constraints --- p.26
Chapter 3 --- Effects of Symmetry Breaking Constraints --- p.29
Chapter 3.1 --- Removing Symmetric Search Space --- p.29
Chapter 3.1.1 --- Properties --- p.30
Chapter 3.1.2 --- Canonical Variable Orderings --- p.31
Chapter 3.1.3 --- Regenerating All Solutions --- p.33
Chapter 3.1.4 --- Remaining Solution Set Sizes --- p.36
Chapter 3.2 --- Constraint Interactions in Propagation --- p.43
Chapter 4 --- Choices of Symmetry Breaking Constraints --- p.45
Chapter 4.1 --- Side-Effects --- p.45
Chapter 4.2 --- Symmetry Preservation --- p.50
Chapter 4.2.1 --- De nition and Properties --- p.50
Chapter 4.2.2 --- Solution Reduction --- p.54
Chapter 4.2.3 --- Preservation Examples --- p.55
Chapter 4.2.4 --- Preserving Order --- p.64
Chapter 4.3 --- Eliminating Eliminated Symmetries --- p.65
Chapter 4.3.1 --- Further Elimination --- p.65
Chapter 4.3.2 --- Aggressive Elimination --- p.71
Chapter 4.4 --- Interactions with Problem Constraints --- p.72
Chapter 4.4.1 --- Further Simplification --- p.72
Chapter 4.4.2 --- Increasing Constraint Propagation --- p.73
Chapter 5 --- Experiments --- p.75
Chapter 5.1 --- Symmetry Preservation --- p.75
Chapter 5.1.1 --- Diagonal Latin Square Problem --- p.76
Chapter 5.1.2 --- NN-Queen Problem --- p.77
Chapter 5.1.3 --- Error Correcting Code - Lee Distance (ECCLD) --- p.78
Chapter 5.2 --- Eliminating Eliminated Symmetries --- p.80
Chapter 5.2.1 --- Equidistance Frequency Permutation Array Problem --- p.80
Chapter 5.2.2 --- Cover Array Problem --- p.82
Chapter 5.2.3 --- Sports League Scheduling Problem --- p.83
Chapter 6 --- Related Work --- p.86
Chapter 6.1 --- Symmetry Breaking Approaches --- p.86
Chapter 6.2 --- Reducing Overhead and Increasing Propagation --- p.90
Chapter 6.3 --- Selecting and Generating Choices --- p.91
Chapter 6.3.1 --- Reducing Conflict with Search Heuristic --- p.92
Chapter 6.3.2 --- Choosing the Subset of Symmetries --- p.93
Chapter 6.4 --- Detecting Symmetries --- p.93
Chapter 7 --- Conclusion and Remarks --- p.95
Chapter 7.1 --- Conclusion --- p.95
Chapter 7.2 --- Discussions --- p.97
Chapter 7.3 --- Future Work --- p.99
Bibliography --- p.101
42
Viola, Caterina. "Valued Constraint Satisfaction Problems over Infinite Domains." 2020. https://tud.qucosa.de/id/qucosa%3A71507.
Full textAbstract:
The object of the thesis is the computational complexity of certain combinatorial optimisation problems called \emph{valued constraint satisfaction problems}, or \emph{VCSPs} for short. The requirements and optimisation criteria of these problems are expressed by sums of \emph{(valued) constraints} (also called \emph{cost functions}). More precisely, the input of a VCSP consists of a finite set of variables, a finite set of cost functions that depend on these variables, and a cost $u$; the task is to find values for the variables such that the sum of the cost functions is at most $u$.
By restricting the set of possible cost functions in the input, a great variety of computational optimisation problems can be modelled as VCSPs. Recently, the computational complexity of all VCSPs for finite sets of cost functions over a finite domain has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain.
We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear (PL) and piecewise linear homogeneous (PLH) cost functions.
The VCSP for a finite set of PLH cost functions can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We
show this by (polynomial-time many-one) reducing the problem to a finite-domain VCSP which can be solved using a linear programming relaxation. We apply this result to show the polynomial-time tractability of VCSPs for {\it submodular} PLH cost functions, for {\it convex} PLH cost functions, and for {\it componentwise increasing} PLH cost functions; in fact, we show that submodular PLH functions and componentwise increasing PLH functions form maximally tractable classes of PLH cost functions.
We define the notion of {\it expressive power} for sets of cost functions over arbitrary domains, and discuss the relation between the expressive power and the set of fractional operations improving the same set of cost functions over an arbitrary countable domain.
Finally, we provide a polynomial-time algorithm solving the restriction of the VCSP for {\it all} PL cost functions to a fixed number of variables.
43
Stevenson, Lynette. "Modal satisifiability in a constraint logic environment." Thesis, 2007. http://hdl.handle.net/10500/2030.
Full textAbstract:
The modal satisfiability problem has to date been solved using either a specifically
designed algorithm, or by translating the modal logic formula into a different class
of problem, such as a first-order logic, a propositional satisfiability problem or a constraint
satisfaction problem. These approaches and the solvers developed to support
them are surveyed and a synthesis thereof is presented.
The translation of a modal K formula into a constraint satisfaction problem,
as developed by Brand et al. [18], is further enhanced. The modal formula, which
must be in conjunctive normal form, is translated into layered propositional formulae.
Each of these layers is translated into a constraint satisfaction problem and solved
using the constraint solver ECLiPSe. I extend this translation to deal with reflexive
and transitive accessibility relations, thereby providing for the modal logics KT and
S4. Two of the difficulties that arise when these accessibility relations are added
are that the resultant formula increases considerably in complexity, and that it is
no longer in conjunctive normal form (CNF). I eliminate the need for the conversion
of the formula to CNF and deal instead with formulae that are in negation normal
form (NNF). I apply a number of enhancements to the formula at each modal layer
before it is translated into a constraint satisfaction problem. These include extensive
simplification, the assignment of a single value to propositional variables that occur
only positively or only negatively, and caching the status of the formula at each node
of the search tree. All of these significantly prune the search space. The final results
I achieve compare favorably with those obtained by other solvers.Computing
M.Sc. (Computer Science)
44
Georgiou, Konstantinos. "Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations." Thesis, 2010. http://hdl.handle.net/1807/26271.
Full textAbstract:
The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.
45
Davies, Jessica. "Solving MAXSAT by Decoupling Optimization and Satisfaction." Thesis, 2013. http://hdl.handle.net/1807/43539.
Full textAbstract:
Many problems that arise in the real world are difficult to solve partly because they present computational challenges. Many of these challenging problems are optimization problems. In the real world we are generally interested not just in solutions but in the cost or benefit of these solutions according to different metrics. Hence, finding optimal solutions is often highly desirable and sometimes even necessary. The most effective computational approach for solving such problems is to first model them in a mathematical or logical language, and then solve them by applying a suitable algorithm.
This thesis is concerned with developing practical algorithms to solve optimization problems modeled in a particular logical language, MAXSAT. MAXSAT is a generalization of the famous Satisfiability (SAT) problem, that associates finite costs with falsifying various desired conditions where these conditions are expressed as propositional clauses. Optimization problems expressed in MAXSAT typically have two interacting components: the logical relationships between the variables expressed by the clauses, and the optimization component involving minimizing the falsified clauses. The interaction between these components greatly contributes to the difficulty of solving MAXSAT.
The main contribution of the thesis is a new hybrid approach, MaxHS, for solving MAXSAT. Our hybrid approach attempts to decouple these two components so that
each can be solved with a different technology. In particular, we develop a hybrid solver that exploits two sophisticated technologies with divergent strengths: SAT for solving the logical component, and Integer Programming (IP) solvers for solving the optimization component. MaxHS automatically and incrementally splits the MAXSAT problem into two parts that are given to the SAT and IP solvers, which work together in a complementary way to find a MAXSAT solution. The thesis investigates several improvements to the MaxHS approach and provides empirical analysis of its behaviour in practise. The result is a new solver, MaxHS, that is shown to be the most robust existing solver for MAXSAT.