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.
Conflict-Driven Clause-Learning (CDCL) SAT solvers can automatically solve very large real-world problems. To go beyond, and in particular in order to solve and optimize problems involving linear arithmetic constraint...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Conflict-Driven Clause-Learning (CDCL) SAT solvers can automatically solve very large real-world problems. To go beyond, and in particular in order to solve and optimize problems involving linear arithmetic constraints, here we introduce IntSat, a generalization of CDCL to Integer Linear programming (ILP). Our simple 1400-line C++ prototype IntSat implementation already shows some competitiveness with commercial solvers such as CPLEX or Gurobi. Here we describe this new IntSat ILP solving method, show how it can be implemented efficiently, and discuss a large list of possible enhancements and extensions.
We present a parallel solver for numerical constraint satisfaction problems (NCSPs) that can scale on a number of cores. Our proposed method runs worker solvers on the available cores and simultaneously the workers co...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We present a parallel solver for numerical constraint satisfaction problems (NCSPs) that can scale on a number of cores. Our proposed method runs worker solvers on the available cores and simultaneously the workers cooperate for the search space distribution and balancing. In the experiments, we attained up to 119-fold speedup using 256 cores of a parallel computer.
Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the CP community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is prefe...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the CP community, this approach is unfortunately not used anymore by steel producers since last century. Continuous casting is preferred instead, allowing higher throughput and better steel quality. this paper presents a CP model related to scheduling of operations for steel making with continuous casting. Activities considered range from the extraction of iron in the furnace to its casting in continuous casters. We describe the problem, detail a CP scheduling model that is finally used to solve real-life instances of some of the PSI Metals' customers.
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.
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.
Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented wi...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.
We establish optimal bounds on the number of nested propagation steps in k-consistency tests. It is known that local consistency algorithms such as arc-, path- and k-consistency are not efficiently parallelizable. the...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We establish optimal bounds on the number of nested propagation steps in k-consistency tests. It is known that local consistency algorithms such as arc-, path- and k-consistency are not efficiently parallelizable. their inherent sequential nature is caused by long chains of nested propagation steps, which cannot be executed in parallel. this motivates the question "What is the minimum number of nested propagation steps that have to be performed by k-consistency algorithms on (binary) constraint networks with n variables and domain size d?" It was known before that 2-consistency requires Omega(nd) and 3-consistency requires Omega(n(2)) sequential propagation steps. We answer the question exhaustively for every k >= 2: there are binary constraint networks where any k-consistency procedure has to perform Omega( n(k-1)d(k-1)) nested propagation steps before local inconsistencies were detected. this bound is tight, because the overall number of propagation steps performed by k-consistency is at most n(k-1)d(k-1).
We present a method for solving weighted constraint Satisfaction Problems, based on translation into a constraint Optimization Problem and iterative calls to an SMT solver, with successively tighter bounds of the obje...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We present a method for solving weighted constraint Satisfaction Problems, based on translation into a constraint Optimization Problem and iterative calls to an SMT solver, with successively tighter bounds of the objective function. the novelty of the method herewith described lies in representing the bound constraint as a shared Binary Decision Diagram, which in turn is translated into SAT. this offers two benefits: first, BDDs built for previous bounds can be used to build the BDDs for new (tighter) bounds, considerably reducing the BDD construction time;second, as a by-product, many clauses asserted to the solver in previous iterations can be reused. the reported experimentation on the WSimply system shows that this technique has better performance in general than other methods implemented in the system. Moreover, withthe new technique WSimply outperforms some state-of-the-art solvers in most of the studied instances.
We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems which are then solved independently by workers. EPS performed well on multicores machines (40), but some issues arise when using more cores in a datacenter. Here, we identify the decomposition as the cause of the degradation and propose a parallel decomposition to address this issue. thanks to it, EPS gives almost linear speedup and outperforms work stealing by orders of magnitude using the Gecode solver.
暂无评论