Measuring graph similarity is a key issue in many applications. We propose a new constraint-based modeling language for defining graph similarity measures by means of constraints. It covers measures based on univalent...
详细信息
ISBN:
(纸本)9783642042430
Measuring graph similarity is a key issue in many applications. We propose a new constraint-based modeling language for defining graph similarity measures by means of constraints. It covers measures based on univalent matchings, such that each node is matched with at most one node, as well as multivalent matchings, such that a node may be matched with a set of nodes. this language is designed on top of Comet, a programming language Supporting bothconstraintprogramming (cp) and constraint-Based Local Search (CBLS). Starting from the constraint-based description of the measure, we automatically generate a Comet program for computing the measure. Depending on the measure characteristics, this program either uses cp-which is better suited for computing exact measures such as (sub)graph isomorphism- or CBLS-which is better suited for computing error-tolerant measures such as graph edit distances. First experimental results show the feasibility Of Our approach.
We consider a generic binary CSP solver parameterized by high-level design choices, i.e., backtracking mechanisms, constraint propagation levels, and variable ordering heuristics. We experimentally compare 24 differen...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We consider a generic binary CSP solver parameterized by high-level design choices, i.e., backtracking mechanisms, constraint propagation levels, and variable ordering heuristics. We experimentally compare 24 different configurations of this generic solver on a benchmark of around a thousand instances. this allows us to understand the complementarity of the different search mechanisms, with an emphasis on Backtracking with Tree Decomposition (BTD). then, we use a per-instance algorithm selector to automatically select a good solver for each new instance to be solved. We introduce a new strategy for selecting the solvers of the portfolio, which aims at maximizing the number of instances for which the portfolio contains a good solver, independently from a time limit.
Finding the largest clique in a given graph is one of the fundamental NP-hard problems. We take a widely used branch and bound algorithm for the maximum clique problem, and discuss an alternative way of understanding ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Finding the largest clique in a given graph is one of the fundamental NP-hard problems. We take a widely used branch and bound algorithm for the maximum clique problem, and discuss an alternative way of understanding the algorithm which closely resembles a constraint model. By using this view, and by taking measurements inside search, we provide a new explanation for the success of the algorithm: one of the intermediate steps, by coincidence, often approximates a "smallest domain first" heuristic. We show that replacing this step with a genuine "smallest domain first" heuristic leads to a reduced branching factor and a smaller search space, but longer runtimes. We then introduce a "domains of size two first" heuristic, which integrates cleanly into the algorithm, and which both reduces the size of the search space and gives a reduction in runtimes.
the job shop scheduling problem (JSSP) is an abstraction of industrial scheduling and has been studied since the dawn of the computer era. Its combinatorial nature makes it easily expressible as a constraint satisfact...
详细信息
ISBN:
(纸本)9783030300487
the job shop scheduling problem (JSSP) is an abstraction of industrial scheduling and has been studied since the dawn of the computer era. Its combinatorial nature makes it easily expressible as a constraint satisfaction problem. Nevertheless, in the last decade, there has been a hiatus in the research on this topic from the constraint community;even when this problem is addressed, the target instances are from benchmarks that are more than 20 years old. And yet, constraint solvers have continued to evolve and the standards of today's industry have drastically changed. Our aim is to close this research gap by testing the capabilities of the best available cp solvers on the JSSP. We target not only the classic benchmarks from the literature but also a new benchmark of large-scale instances reflecting nowadays industrial scenarios. Furthermore, we analyze different encodings of the JSSP to measure the impact of high-level structures (such as interval variables and no-overlap constraints) on the problem solution. the solvers considered are OR-Tools, Google's open-source solver and winner of the last MiniZinc Challenge, and IBM's cp Optimizer, a proprietary solver targeted towards industrial scheduling problems.
We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an a...
详细信息
ISBN:
(纸本)9783540749691
We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an associated classical CSP instance. Where it is smaller, we can successfully exploit the additional symmetries using conditional symmetry breaking. We demonstrate, in a case-study of graph colouring, that eliminating the symmetry of the soft CSP combined with conditional symmetry breaking can lead to huge reductions in the search effort to find an optimal solution to the soft CSP.
the presence of uncertainty in the real world makes robustness a desirable property of solutions to constraint Satisfaction Problems (CSP). A solution is said to be robust if it can be easily repaired when unexpected ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
the presence of uncertainty in the real world makes robustness a desirable property of solutions to constraint Satisfaction Problems (CSP). A solution is said to be robust if it can be easily repaired when unexpected events happen. this has already been addressed in the frameworks of Boolean satisfiability (SAT) and constraintprogramming (cp). In this paper we consider the unaddressed problem of robustness in weighted MaxSAT, by showing how robust solutions to weighted MaxSAT instances can be effectively obtained via reformulation into pseudo-Boolean formulae. Our encoding provides a reasonable balance between increase in size and performance. We also consider flexible robustness for problems having some unrepairable breakage, in other words, problems for which there does not exist a robust solution.
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing relational consistency by exploiting the property that the constraints of the dual encoding of a CSP are piecewise functional. this property allows us to partition a CSP relation into blocks of equivalent tuples at varying levels of granularity. Our new algorithm dynamically exploits those partitions. Our experiments show a significant improvement of the processing time for enforcing relational consistency.
Resource Constrained Project;Scheduling Problem is a very important problem in project management, manufacturing and resource optimization. We focus on a variant of RcpSP with time lags and variable activity durations...
详细信息
ISBN:
(纸本)9783642042430
Resource Constrained Project;Scheduling Problem is a very important problem in project management, manufacturing and resource optimization. We focus on a variant of RcpSP with time lags and variable activity durations. the solving approach is based on Precedence constraint Posting that adds new precedence constraints to the original project graph so that all resource Conflicts are solved and a consisteut assignment of start times can be computed for whatever combination of activity durations. We propose a novel method for computing resource conflicts based on the minimum flow on the resource graph and we use it in an efficient complete search strategy. We experiment the approach on instances coming from the scheduling of parallel applications on multi processor systems on chip.
We show that existing constraint manipulation technology incorporated in the paradigm of symbolic model checking with rich assertional languages [KMM+97], can be successfully applied to the verification of client-serv...
详细信息
暂无评论