Rozprawy doktorskie na temat „Constraint Satisfaction Programming”
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 45 najlepszych rozpraw doktorskich naukowych na temat „Constraint Satisfaction Programming”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj rozprawy doktorskie z różnych dziedzin i twórz odpowiednie bibliografie.
Nightingale, Peter. "Consistency and the quantified constraint satisfaction problem /". St Andrews, 2007. http://hdl.handle.net/10023/759.
Pełny tekst źródłaEgri, 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.
Pełny tekst źródłaIn 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.
Thornton, John. "Constraint Weighting Local Search for Constraint Satisfaction". Thesis, Griffith University, 2000. http://hdl.handle.net/10072/367954.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Science, Environment, Engineering and Technology
Full Text
Thornton, John Richard, i 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.
Pełny tekst źródłaPadmanabhuni, 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.
Pełny tekst źródłaZhang, 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.
Pełny tekst źródłaThorstensen, 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.
Pełny tekst źródłaNightingale, Peter William. "Consistency and the Quantified Constraint Satisfaction Problem". Thesis, University of St Andrews, 2007. http://hdl.handle.net/10023/759.
Pełny tekst źródłaNilsson, 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.
Pełny tekst źródłaMed 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ö.
Gharbi, Nebras. "On compressing and parallelizing constraint satisfaction problems". Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0406/document.
Pełny tekst źródłaConstraint 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
Hewson, John Aubrey. "Constraint-based specifications for system configuration". Thesis, University of Edinburgh, 2013. http://hdl.handle.net/1842/8267.
Pełny tekst źródłaWinter, 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.
Pełny tekst źródłaKiziltan, 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.
Pełny tekst źródłaLikeman, 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.
Pełny tekst źródłaAndersson, 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.
Pełny tekst źródłaWu, Yi. "The Approximability of Learning and Constraint Satisfaction Problems". Research Showcase @ CMU, 2010. http://repository.cmu.edu/dissertations/24.
Pełny tekst źródłaMaloberti, Jérôme. "Improving inductive logic programming with constraint satisfaction techniques : applications to frequent query discovery". Paris 11, 2005. http://www.theses.fr/2005PA112139.
Pełny tekst źródłaThe 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
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.
Pełny tekst źródłaLu, 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.
Pełny tekst źródłaEast, Deborah J. "DATALOG WITH CONTRAINTS: A NEW ANSWER-SET PROGRAMMING FORMALISM". UKnowledge, 2001. http://uknowledge.uky.edu/gradschool_diss/322.
Pełny tekst źródłaZhao, 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.
Pełny tekst źródłaNumera 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.
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.
Pełny tekst źródłaCoordenaçã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
Pivkina, Inna Valentinovna. "REVISION PROGRAMMING: A KNOWLEDGE REPRESENTATION FORMALISM". Lexington, Ky. : [University of Kentucky Libraries], 2001. http://lib.uky.edu/ETD/ukycosc2001d00022/pivkina.pdf.
Pełny tekst źródłaTitle from document title page. Document formatted into pages; contains vii, 121 p. : ill. Includes abstract. Includes bibliographical references (p. 116-119).
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.
Pełny tekst źródłaDaoudi, Abderrazak. "Acquisition de contraintes par apprentissage de structures". Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT316/document.
Pełny tekst źródłaConstraint 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
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.
Pełny tekst źródłaConstraint 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
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.
Pełny tekst źródłaParis, Nicolas. "Intégration de techniques CSP pour la résolution du problème WCSP". Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0405/document.
Pełny tekst źródłaThis 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
Tybon, Robert, i 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.
Pełny tekst źródłaTybon, Robert. "Generating Solutions to the Jigsaw Puzzle Problem". Thesis, Griffith University, 2004. http://hdl.handle.net/10072/366062.
Pełny tekst źródłaThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Management
Faculty of Commerce and Management
Full Text
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.
Pełny tekst źródłaThis 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
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.
Pełny tekst źródłaChadim, 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.
Pełny tekst źródłaVautard, 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.
Pełny tekst źródła"Quantified weighted constraint satisfaction problems". 2011. http://library.cuhk.edu.hk/record=b5894615.
Pełny tekst źródłaThesis (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
"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.
Pełny tekst źródłaThesis (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
Raja, Basalat Ali. "Programming using a constraint satisfaction system for robotics". Thesis, 1992. http://hdl.handle.net/1911/13623.
Pełny tekst źródłaHebrard, 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.
Pełny tekst źródłaYeh, Chieh-Jung, i 葉杰榮. "The Development of Timetabling System Using Constraint Satisfaction Programming". Thesis, 2002. http://ndltd.ncl.edu.tw/handle/89326291752260315097.
Pełny tekst źródła國立高雄第一科技大學
資訊管理系
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.
"Consistency techniques for linear global cost functions in weighted constraint satisfaction". 2012. http://library.cuhk.edu.hk/record=b5549068.
Pełny tekst źródła我們定義了一類可被建構為整數線性規劃的多元價值函數,並稱它們為多項式線性投影安全(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
"Increasing symmetry breaking by preserving target symmetries and eliminating eliminated symmetries in constraint satisfaction". 2012. http://library.cuhk.edu.hk/record=b5549127.
Pełny tekst źródła給與一個約束滿足問題,一個對稱被一個約束保留當且僅當該對稱仍然是新的約束滿足問題的對稱。這個新的約束滿足問題是有原問題加上該約束組成的。我們給出定律和例子,以表明發佈儘量保留目標對稱以及限制它的副作用發生在非目標對稱上的破壞約束是有利的。這些好處來自于被破壞的對稱數目以及一個對稱被破壞(或消除)的程度,并導致一個較小的解集和搜索空間。但是,對稱不一定會被保留。我們顯示,旨在一個已經被消除的目標對稱的破壞對稱約束仍然可以被發佈。我們建議根據問題的約束以及其他破壞對稱約束來選擇破壞對稱約束,以繼續消除更多的對稱。我們進行了廣泛的實驗來確認我們的建議的可行性與效率。
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
Viola, Caterina. "Valued Constraint Satisfaction Problems over Infinite Domains". 2020. https://tud.qucosa.de/id/qucosa%3A71507.
Pełny tekst źródłaStevenson, Lynette. "Modal satisifiability in a constraint logic environment". Thesis, 2007. http://hdl.handle.net/10500/2030.
Pełny tekst źródłaComputing
M.Sc. (Computer Science)
Georgiou, Konstantinos. "Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations". Thesis, 2010. http://hdl.handle.net/1807/26271.
Pełny tekst źródłaDavies, Jessica. "Solving MAXSAT by Decoupling Optimization and Satisfaction". Thesis, 2013. http://hdl.handle.net/1807/43539.
Pełny tekst źródła