In some recent works, a general framework for finite domains constraint satisfaction has been defined, where classical CSPs, fuzzy CSPs: weighted CSFs, partial CSPs and others can be easily cast. this framework, based...
详细信息
ISBN:
(纸本)3540652248
In some recent works, a general framework for finite domains constraint satisfaction has been defined, where classical CSPs, fuzzy CSPs: weighted CSFs, partial CSPs and others can be easily cast. this framework, based on a semiring structure: allows, under certain conditions: to compute are-consistency. Restricting to that case and integrating semiring-based constraint solving in the constraint Logic programming paradigm, we have implemented a generic language, clp(FD,S): for semiring-based constraint satisfaction. In this paper, we describe the kernel of the language: the SFD system and our implementation of clp(FD,S). We also give some performance results on various examples.
We study a global constraint, the "inter-distance constraint" that ensures that the distance between any pair of variables is at least equal to a given value. When this value is 1, the inter-distance constra...
详细信息
ISBN:
(纸本)3540292381
We study a global constraint, the "inter-distance constraint" that ensures that the distance between any pair of variables is at least equal to a given value. When this value is 1, the inter-distance constraint reduces to the all-different constraint. We introduce an algorithm to propagate this constraint and we show that, when domains of the variables are intervals, our algorithm achieves arc-B-consistency. It provides tighter bounds than generic scheduling constraint propagation algorithms (like edge-finding) that could be used to capture this constraint. the worst case complexity of the algorithm is cubic but it behaves well in practice and it drastically reduces the search space. Experiments on special Job-Shop problems and on an industrial problem are reported.
Research on constraint propagation has primarily focused on designing polynomial-time propagators sometimes at the cost of a weaker filtering. Interestingly, the evolution of constraintprogramming over sets have been...
详细信息
ISBN:
(纸本)9783642153952
Research on constraint propagation has primarily focused on designing polynomial-time propagators sometimes at the cost of a weaker filtering. Interestingly, the evolution of constraintprogramming over sets have been diametrically different. the domain representations are becoming increasingly expensive computationally and theoretical results appear to question the wisdom of these research directions. this paper explores this apparent contradiction by pursuing even more complexity in the domain representation and the filtering algorithms. It shows that;the product of the length-lex and subset-bound domains improves filtering and produces orders of magnitude improvements over existing approaches on standard benchmarks. Moreover, the paper proposes exponential-time algorithms for NP-hard intersection constraints and demonstrates that they bring significant performance improvements and speeds up constraint propagation considerably.
We argue that turning a logic program into a set of completed definitions can be sometimes thought of as the "reverse engineering" process of generating a set of conditions that could serve as a specificatio...
详细信息
We argue that turning a logic program into a set of completed definitions can be sometimes thought of as the "reverse engineering" process of generating a set of conditions that could serve as a specification for it. Accordingly, it may be useful to define completion for a large class of Answer Set programming (ASP) programs and to automate the process of generating and simplifying completion formulas. Examining the output produced by this kind of software may help programmers to see more clearly what their program does, and to what degree its behavior conforms withtheir expectations. As a step toward this goal, we propose here a definition of program completion for a large class of programs in the input language of the ASP grounder gringo, and study its properties.
FLUX is a CLP-approach for programming agents that reason about actions under incomplete state knowledge. FLUX is based on the solution to the fundamental frame problem in the fluent calculus. the core is a set of Con...
详细信息
ISBN:
(纸本)3540292381
FLUX is a CLP-approach for programming agents that reason about actions under incomplete state knowledge. FLUX is based on the solution to the fundamental frame problem in the fluent calculus. the core is a set of constraint Handling Rules for the constraints that are used to encode state knowledge. In order to allow for efficient constraint solving, the original expressiveness of state representations in FLUX has been carefully restricted. In this paper, we enhance the expressiveness by adding both implication and universal quantification constraints. We do so without losing the computational merits of FLUX. We present a set of constraint Handling Rules for these new constraints and prove their correctness against the fluent calculus.
Feature modeling has been found very effective for modeling and managing variability in Software Product Lines. the nature of feature models invites, sometimes even requires, the use of global constraints. this paper ...
详细信息
ISBN:
(纸本)9783642153952
Feature modeling has been found very effective for modeling and managing variability in Software Product Lines. the nature of feature models invites, sometimes even requires, the use of global constraints. this paper lays the groundwork for the inclusion of global constraints in automated reasoning on feature models. We present a mapping from extended feature models to constraint logic programming over finite domains, and show that this mapping enables using global constraints on feature attributes, as well as features, for a variety of analysis operations on feature models. We also present performance test results and discuss the benefits of using global constraints.
Evacuation planning algorithms are critical tools for assisting authorities in orchestrating large-scale evacuations while ensuring optimal utilization of resources. To be deployed in practice, these algorithms must i...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Evacuation planning algorithms are critical tools for assisting authorities in orchestrating large-scale evacuations while ensuring optimal utilization of resources. To be deployed in practice, these algorithms must include a number of constraints that dramatically increase their complexity. this paper considers the zone-based non-preemptive evacuation planning problem in which each evacuation zone is assigned a unique evacuation path to safety and the flow of evacuees over time for a given zone follows one of a set of specified response curves. the starting point of the paper is the recognition that the first and only optimization algorithm previously proposed for zone-based non-preemptive evacuation planning may produce non-elementary paths, i.e., paths that visit the same node multiple times over the course of the evacuation. Since non-elementary paths are undesirable in practice, this paper proposes a column-generation algorithm where the pricing subproblem is a least-cost path under constraints. the paper investigates a variety of algorithms for solving the subproblem as well as their hybridization. Experimental results on a real-life case study show that the new algorithm produces evacuation plans with elementary paths of the same quality as the earlier algorithm in terms of the number of evacuees reaching safety and the completion time of the evacuation, at the expense of a modest increase in CPU time.
this article presents a case study of using a constraintprogramming solver in a system level synthesis framework called SYLVA. the solver is used to find the repetition vector of a synchronous data flow graph and ser...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
this article presents a case study of using a constraintprogramming solver in a system level synthesis framework called SYLVA. the solver is used to find the repetition vector of a synchronous data flow graph and serving as the design space exploration engine, which rapidly finds qualified system implementations by solving a constraint satisfaction optimization problem. Each system implementation is a combination of a number of function implementation instances and their cycle accurate execution schedules. the problem to be solved is automatically generated based on the user inputs: 1) a system model to be synthesized, 2) a library containing all the usable function implementations, 3) the performance/cost constraints, and 4) the optimization objectives. Use of constraints programming technique enabled a low cost development of design space exploration engine in addition to gaining ease of use.
We combine mixed integer linear programming (MILP) and constraintprogramming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are...
详细信息
ISBN:
(纸本)3540292381
We combine mixed integer linear programming (MILP) and constraintprogramming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CR We also obtain much better solutions for problems that cannot be solved to optimality.
Many production planning problems call for the minimization of stocking/storage costs. this paper introduces a new global constraint StockingCost ([X-1,..., X-n], [d(1),..., d(n)], H, c) that holds when each item X-i ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Many production planning problems call for the minimization of stocking/storage costs. this paper introduces a new global constraint StockingCost ([X-1,..., X-n], [d(1),..., d(n)], H, c) that holds when each item X-i is produced on or before its due date d(i), the capacity c of the machine is respected, and H is an upper bound on the stocking cost. We propose a linear time algorithm to achieve bound consistency on the StockingCost constraint. On a version of the Discrete Lot Sizing Problem, we demonstrate experimentally the pruning and time efficiency of our algorithm compared to other state-of-the-art approaches.
暂无评论