Combinatorial problems are ubiquitous in our society and solving such problems efficiently is often crucial. One technique for solving combinatorial problems is constraint-based local search. Its compositional nature together with its efficiency on large problem instances have made this technique particularly attractive. In this thesis we contribute to simplifying the solving of combinatorial problems using constraint-based local search.To provide higher-level modelling options, we introduce set variables and set constraints in local search by extending relevant local search concepts. We also propose a general scheme to follow in order to define what we call natural and balanced constraint measures, and accordingly define such measures for over a dozen set constraints. However, defining such measures for a new constraint is time-consuming and error-prone. To relieve the user from this, we provide generic measures for any set constraint modelled in monadic existential second-order logic. We also theoretically relate these measures to our proposed general scheme, and discuss implementation issues such as incremental algorithms and their worst-case complexities.To enable higher-level search algorithms, we introduce constraint-directed neighbourhoods in local search by proposing new constraint primitives for representing such neighbourhoods. Based on a constraint, possibly modelled in monadic existential second-order logic, these primitives return neighbourhoods with moves that are known in advance to achieve a decrease (or preservation, or increase) of the constraint measures…
Contents
1 Introduction
1.1 Solving Combinatorial Problems by Searc
1.2 Motivation
1.3 Objectives
1.4 Contributions
1.5 Assumptions and Limitations
1.6 Outline and Relation to Prior Publications
2 Background
2.1 Constraint Satisfaction Problems
2.2 Constraint Programming
2.3 Constraint-Based Local Search
2.4 Natural and Balanced Constraint Measures
2.5 Set Variables
2.6 Incremental Algorithms for Constraint Measures
3 Set Constraints in Local Search
3.1 Moves and Neighbourhoods for Set Variables
3.2 Natural and Balanced Measures for Set Constraints
3.3 Related Work
4 Built-in Set Constraints
4.1 Aset-CSP Model of a Combinatorial Problem
4.2 Max Weighted Sum(S,w,m)
4.3 All Disjoint(X)
4.4 Max Intersect(X,m)
4.5 Implementation
4.6 Related Work
5 Generic Set Constraints
5.1 A Missing Constraint?
5.2 Monadic Existential Second-Order Logic
5.3 ∃MSOConstraintsinLocalSearch
5.3.1 PenaltyFunction
5.3.2 Variable Conflict Function
5.4 Implementation
5.4.1 The Measure DAG of an ∃MSOConstraint
5.4.2 Incremental Algorithmsfor MeasureDAGs
5.4.3 Complexity
5.5 Modelling Issues
5.6 ∃MSOwithCounting
5.7 Expressive Power of MSO
5.8 RelatedWork
6 Constraint Neighbourhoods
6.1 Constraint-Directed Neighbourhoods
6.1.1 ∃MSOConstraints
6.1.2 Built-InConstraints
6.2 Using Constraint-Directed Neighbourhoods
6.2.1 Constraint-DirectedHeuristics
6.2.2 AvoidingNecessaryData-Structures
6.3 Implementation
6.4 RelatedWork
7 Experiments
7.1 Setup
7.2 OrganisingaMarinaParty
7.3 SchedulingaGolfTournament
7.4 ConstructinganAcademicCurriculum
7.5 Using ∃MSOConstraints
7.6 Using Constraint-Directed Neighbourhoods
8 Conclusion
8.1 Summary
8.2 FutureWork
A Built-in Set Constraints
A.1 a S and a / ∈ S
A.2 |S|s ( ∈{<,≤,=, =,≥,>})
A.3 S = T
A.4 S= T
A.5 S T
A.6 T
Bibliography
Author: Agren, Magnus
Source: Uppsala University Library
Download URL 2: Visit Now