We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning...
详细信息
ISBN:
(纸本)9783030300487
We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes boththe graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.
the recent improvements in solving Maximum Satisfiability (MaxSAT) problems has allowed the usage of MaxSAT in several application domains. However, it has been observed that finding an optimal solution in a reasonabl...
详细信息
ISBN:
(纸本)9783030300487
the recent improvements in solving Maximum Satisfiability (MaxSAT) problems has allowed the usage of MaxSAT in several application domains. However, it has been observed that finding an optimal solution in a reasonable amount of time remains a challenge. Moreover, in many applications it is enough to provide a good approximation of the optimum. Recently, new local search algorithms have been shown to be successful in approximating the optimum in MaxSAT problems. Nevertheless, these local search algorithms fail in finding feasible solutions to highly constrained instances. In this paper, we propose two constraint-based techniques for improving local search MaxSAT solvers. Firstly, an unsatisfiability-based algorithm is used to guide the local search solver into the feasible region of the search space. Secondly, given a partial assignment, we perform Minimal Correction Subsets (MCS) enumeration in order to improve upon the best solution found by the local search solver. Experimental results using a large set of instances from the MaxSAT evaluation 2018 show the effectiveness of our approach.
Pseudo-Boolean (PB) constraints often have a critical role in constraint satisfaction and optimisation problems. Encoding PB constraints to SAT has proven to be an efficient approach in many applications, however care...
详细信息
ISBN:
(纸本)9783030300487
Pseudo-Boolean (PB) constraints often have a critical role in constraint satisfaction and optimisation problems. Encoding PB constraints to SAT has proven to be an efficient approach in many applications, however care must be taken to encode them compactly and with good propagation properties. It has been shown that at-most-one (AMO) and exactly-one (EO) relations over subsets of the variables can be exploited in various encodings of PB constraints, improving their compactness and solving performance. In this paper we detect AMO and EO relations completely automatically and exploit them to improve SAT encodings that are based on Multi-Valued Decision Diagrams (MDDs). Our experiments show substantial reductions in encoding size and dramatic improvements in solving time thanks to automatic AMO and EO detection.
Large neighbourhood search, a meta-heuristic, has proven to be successful on a wide range of optimisation problems. the algorithm repeatedly generates and searches through a neighbourhood around the current best solut...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Large neighbourhood search, a meta-heuristic, has proven to be successful on a wide range of optimisation problems. the algorithm repeatedly generates and searches through a neighbourhood around the current best solution. thus, it finds increasingly better solutions by solving a series of simplified problems, all of which are related to the current best solution. In this paper, we show that significant benefits can be obtained by simulating local-search behaviour in constraintprogramming by using phase saving based on the best solution found so far during the search, activity-based search (VSIDS), and nogood learning. the approach is highly effective despite its simplicity, improving the highest scoring solver, Chuffed, in the free category of the MiniZinc Challenge 2017, and can be easily integrated into modern constraintprogramming solvers. We validated the results on a wide range of benchmarks from the competition library, comparing against seventeen state-of-the-art solvers.
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version o...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version of AES. In [7], Liu et al. revisited their results and introduced a TASCA-cp model that delivers solutions to this 1-round relaxation with orders of magnitude improvement in both solving time and memory consumption. this paper extends the result and considers TASCA for the full 10-rounds AES algorithm. Two approaches are introduced: staged and integrated. the staged approach uses TASCA-cp as a spring board to enumerate and check its candidate solutions against the requirements of subsequent rounds. the integrated model formulates all the rounds of AES together with side-channel constraints on all rounds within a single unified optimization model. Empirical results shows both approaches are suitable to find the correct key of AES while the integrated model dominates the staged both in simplicity and solving time.
We consider the Cumulative Scheduling Problem (CuSP) in which a set of n jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraintprogramming, the CuSP is modeled...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
We consider the Cumulative Scheduling Problem (CuSP) in which a set of n jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraintprogramming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning [1] with a complexity of O(n(3)) and edge-finding [21] with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n(2) log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n(2)) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades.
the proceedings contain 36 papers. the special focus in this conference is on theory and practice of Natural Computing. the topics include: A linear constrained optimization benchmark for probabilistic search algorith...
ISBN:
(纸本)9783030040697
the proceedings contain 36 papers. the special focus in this conference is on theory and practice of Natural Computing. the topics include: A linear constrained optimization benchmark for probabilistic search algorithms: the rotated klee-minty problem;the design of (almost) disjunct matrices by evolutionary algorithms;how the “Baldwin Effect” can guide evolution in dynamic environments;landscape-aware constraint handling applied to differential evolution;fuel efficient truck platooning with time restrictions and multiple speeds solved by a particle swarm optimisation;automated design of genetic programming classification algorithms for financial forecasting using evolutionary algorithms;optimizing fleet staging of air ambulances in the Province of Ontario;a Hierarchical approach to grammar-guided genetic programming: the case of scheduling in heterogeneous networks;multi-memetic mind evolutionary computation algorithm based on the landscape analysis;computing preimages and ancestors in reaction systems;DNA-guided assembly of nanocellulose meshes;classically time-controlled quantum automata;mortal organisms rescue immortal organisms from evolutionary inertness: Perspective of the programmed self-decomposition model;integrative biological, cognitive and affective modeling of a drug-therapy for a post-traumatic stress disorder;symbolic analysis of machine behaviour and the emergence of the machine language;it is time to dissolve old dichotomies in order to grasp the whole picture of cognition;network-oriented modeling of the interaction of adaptive joint decision making, bonding and mirroring;network reification as a unified approach to represent network adaptation principles within a network;relating an adaptive network’s structure to its emerging behaviour for Hebbian learning;on capacity with incremental learning by simplified chaotic neural network.
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express r...
详细信息
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraintprogramming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17thinternational Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15thinternational Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12thinternationalconference on the principles and practice of constraintprogramming (cp 2006), 2006, pp. 182-197] for efficiency. Finally, three case st
We describe a large neighbourhood search (LNS) solver based on a constraintprogramming (cp) model for a real-world rich vehicle routing problem with compartments arising in the context of fuel delivery. Our solver su...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We describe a large neighbourhood search (LNS) solver based on a constraintprogramming (cp) model for a real-world rich vehicle routing problem with compartments arising in the context of fuel delivery. Our solver supports both single-day and multi-day scenarios and a variety of real-world aspects including time window constraints, compatibility constraints, and split deliveries. It can be used both to plan the daily delivery operations, and to inform decisions on the long-term fleet composition. We show experimentally the viability of our approach.
In integer programming, cut generation is crucial for improving the tightness of the linear relaxation of the problem. this is relevant for weighted constraint satisfaction problems (WCSPs) in which we use approximate...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
In integer programming, cut generation is crucial for improving the tightness of the linear relaxation of the problem. this is relevant for weighted constraint satisfaction problems (WCSPs) in which we use approximate dual feasible solutions to produce lower bounds during search. Here, we investigate using one class of cuts in WCSP: clique cuts. We show that clique cuts are likely to trigger suboptimal behavior in the specialized algorithms that are used in WCSP for generating dual bounds and show how these problems can be corrected. At the same time, the additional structure present in WCSP allows us to slightly generalize these cuts. Finally, we show that cliques exist in instances from several benchmark families and that exploiting them can lead to substantial performance improvement.
暂无评论