the Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a constraint Satisfa...
详细信息
Traditional constraint-programming systems provide the concept of variable views which implement a view of the type y = f(x) by delegating operations on variable y to variable x. While the traditional support is limit...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Traditional constraint-programming systems provide the concept of variable views which implement a view of the type y = f(x) by delegating operations on variable y to variable x. While the traditional support is limited to bound consistency, this paper offers views that support domain consistency without any limitations. this paper proposes the alternative concept of domain views which delegate all domain operations. Domain views preserve the benefits of variable views, simplify the implementation of value-based propagation, and also support noninjective views compositionally. Experimental results demonstrate the practical benefits of domain views. the paper also reveals a subtle interaction between views and the exploitation of constraint idempotence, which may lead to incomplete propagation.
We consider soft constraint problems where some of the preferences may be unspecified. this models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we ...
详细信息
ISBN:
(纸本)9783540749691
We consider soft constraint problems where some of the preferences may be unspecified. this models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define an algorithm to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, withthe aim to ask the user to reveal as few preferences as possible. Experimental results show that in many cases a necessarily optimal solution can be found without eliciting too many preferences.
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.
Benders Decomposition is a form of hybridisation that allows linear programming to be combined with other kinds of algorithms. It extracts new constraints for one subproblem from the dual values of the other subproble...
详细信息
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 revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of c...
详细信息
ISBN:
(纸本)9783642042430
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of constraint relaxation. Second, we loosen the basic assumption of ICSP that "value acquisition is expensive" by introducing external cost functions of the constraint relaxation and the constraint propagation effort. We also propose a general INTERACTIVE RELAXATION algorithm template that. is designated for CICSP. the effectiveness of this approach is illustrated oil a real-life scenario from the Functional Test Generation problem domain.
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids...
详细信息
ISBN:
(纸本)3540652248
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [12] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [3, 5]. We describe a constraint formulation of the HP-model structure prediction problem, present the basic constraints and search strategy. We then introduce a novel, general technique for excluding geometrical symmetries in constraintprogramming. To our knowledge, this is the first general and declarative technique for excluding symmetries in constraintprogrammingthat can be added to an existing implementation. Finally, we describe a new lower bound on the energy of an HP-protein. Both techniques yield an efficient pruning of the search tree.
this paper introduces a generalization of the nvalue constraintthat bounds the number of distinct values taken by a set of variables. the generalized constraint (called nvector) bounds the number of distinct;vectors....
详细信息
ISBN:
(纸本)9783642042430
this paper introduces a generalization of the nvalue constraintthat bounds the number of distinct values taken by a set of variables. the generalized constraint (called nvector) bounds the number of distinct;vectors. the first contribution of this paper is to show that this global constraint has a significant role to play with continuous domains, by taking the example of simultaneous localization and map building (SLAM). this type of problem arises in the context, of mobile robotics. the second contribution is, to prove that enforcing bound consistency on this constraint is NP-complete. A simple contractor (or propagator) is proposed and applied on a real application.
We present an over-view of a system developed by IBM for generating short-term operations schedules for a large steel manufacturer. the problem addressed by the system was challenging due to the combination of detaile...
详细信息
ISBN:
(纸本)9783540749691
We present an over-view of a system developed by IBM for generating short-term operations schedules for a large steel manufacturer. the problem addressed by the system was challenging due to the combination of detailed resource allocation and scheduling constraints and preferences, sequence dependent setup times, tight minimum and maximum inventory level constraints between processes, and constraints on the minimum and maximum levels of production by shift for each product croup. We have developed a domain-specific decomposition based approach that uses mixed-integer programming to generate a high-level plan for production, and constraintprogramming to generate a schedule at fine level of time granularity taking into account detailed scheduling constraints and preferences. In this paper we give an overview of the problem domain and solution approach, and present a detailed description of the constraintprogramming part of the system. We also discuss the impact the system is having withthe customer on their manufacturing operations.
暂无评论