VLSI chips design is becoming increasingly complex and calling for more and more automation. Many chip design problems can be formulated is constraint problems and are potentially amenable to cp techniques. To the bes...
详细信息
ISBN:
(纸本)9783642042430
VLSI chips design is becoming increasingly complex and calling for more and more automation. Many chip design problems can be formulated is constraint problems and are potentially amenable to cp techniques. To the best of our knowledge, though there has been little cp work in this domain to date. We describe a successful application of a cp based tool to a particular pin-assignment problem hi which tens of thousands of phis (i.e.;connection points) belonging to internal units on the chip must be placed within their units so as to satisfy certain constraints and optimize the wirability of the design. Our tool has been tested on read IBM designs and is now being integrated into IBM's chip development environment.
Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. these models do not comply with reality: today's constrai...
详细信息
ISBN:
(纸本)9783642042430
Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. these models do not comply with reality: today's constraint, programming systems actually use non-monotonic propagators. this paper introduces the first realistic model of constraint propagation by assuming it propagator to be weakly monotonic (complying withthe constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. the important insight is that weak monotonicity makes propagation in combination. with search well behaved. A case study suggests that non-monotonicity call be seen as all opportunity for more efficient propagation.
Mobile robots in flexible manufacturing systems can transport components for jobs between machines as well as process jobs on selected machines. While the job shop problem with transportation resources allows encapsul...
详细信息
ISBN:
(纸本)9783030300487
Mobile robots in flexible manufacturing systems can transport components for jobs between machines as well as process jobs on selected machines. While the job shop problem with transportation resources allows encapsulating of transportation, this work concentrates on the extended version of the problem, including the processing by mobile robots. We propose a novel constraintprogramming model for this problem where the crucial part of the model lies in a proper inclusion of the transportation. We have implemented it in the Optimization programming Language using the cp Optimizer, and compare it withthe existing mixed integer programming solver. While both approaches are capable of solving the problem optimally, a new constraintprogramming approach works more efficiently, and it can compute solutions in more than an order of magnitude faster. Given that, the results of more realistic data instances are delivered in real-time, which is very important in a smart factory.
Conditionals are a core concept in all programming languages. they are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. the behaviour of conditionals is compl...
详细信息
ISBN:
(纸本)9783030300487
Conditionals are a core concept in all programming languages. they are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. the behaviour of conditionals is complicated by undefinedness. In this paper we show how to most effectively translate conditional constraints for underlying solvers. We show that the simple translation into implications can be improved, at least in terms of reasoning strength, for bothconstraintprogramming and mixed integer programming solvers. Unit testing shows that the new translations are more efficient, but the benefits are not so clear on full models where the interaction with other features such as learning is more complicated.
We first present a generic pruning technique which aggregates several constraints sharing some variables. the method is derived from an idea called sweep which is extensively used in computational geometry. A first be...
详细信息
this paper describes a filtering algorithm for a type of constraintthat often arises in rostering problems but that also has wider application. Defined on a sequence of variables, the stretch constraint restricts the...
详细信息
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorl...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorly in problems withthese constraints in comparison to constraintprogramming (cp) or mixed integer programming (MIP) solvers. But some problems contain a mix of combinatoric constraints and linear constraints, where encoding to SAT is highly effective. In this paper we define new approaches to encoding linear constraints into SAT, by extending encoding methods for pseudo-Boolean constraints. Experimental results show that these methods are not only better than the state-of-the-art SAT encodings, but also improve on MIP and cp solvers on appropriate problems. Combining the new encoding with lazy decomposition, which during runtime only encodes constraints that are important to the solving process that occurs, gives a robust approach to many highly combinatorial problems involving linear constraints.
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled the problem as a mixed integer p...
详细信息
ISBN:
(纸本)9783030300487
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled the problem as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraintprogramming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings. We show its use in the analysis of real datasets.
Using constraintprogramming (cp) to explore a local-search neighbourhood was first tried in the mid 1990s. the advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly...
详细信息
ISBN:
(纸本)9783030300487
Using constraintprogramming (cp) to explore a local-search neighbourhood was first tried in the mid 1990s. the advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a cp model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. that research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of cp-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a cp model of the neighbourhood. this enables us to lift any cp solver into a local-search backend to MiniZinc. Our prototype is competitive withcp, CBLS, and LNS backends to MiniZinc.
LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates c...
详细信息
ISBN:
(纸本)9783540749691
LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates children to reason with global temporal relations between events possibly distant in a story. this is done through apt exercises and withthe support of a constraintprogramming system. Children can also reinvent the e-story by rearranging its events along a new temporal order;it is the task of the constraint system to determine the consistency of the temporally reorganised story and provide children with feedback. To the best of our knowledge, LODE is the first e-learning tool for Italian deaf children that aims at stimulating global reasoning on whole e-stories.
暂无评论