there is no standard modelling language for constraintprogramming (CP) problems. Most solvers have their own modelling language. this makes it difficult for modellers to experiment with different solvers for a proble...
详细信息
ISBN:
(纸本)9783540749691
there is no standard modelling language for constraintprogramming (CP) problems. Most solvers have their own modelling language. this makes it difficult for modellers to experiment with different solvers for a problem. In this paper we present MiniZinc, a simple but expressive CP modelling language which is suitable for modelling problems for a range of solvers and provides a reasonable compromise between many design possibilities. Equally importantly, we also propose a low-level solver-input language called FlatZinc, and a straight forward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. this lets a solver writer support MiniZinc with a minimum of effort-they only need to provide a simple FlatZinc front-end to their solver, and then combine it with an existing MiniZinc-to-FlatZinc translator. Such a front-end may then serve as a stepping stone towards a full MiniZine implementation that;is more tailored to the particular solver. A standard language for modelling CP problems will encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect-no standard modelling language will be-we believe its simplicity, expressiveness, and case of implementation make it a practical choice for a standard language.
this paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic kappa-dimensional objects subject to various geometrical and time constraints. the constraint kernel is ...
详细信息
ISBN:
(纸本)9783540749691
this paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic kappa-dimensional objects subject to various geometrical and time constraints. the constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. these constraints are handled globally by the kernel. We first illustrate how to model several placement problems withthe constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.
Alcatel-Lucent is a major player in the field of telecommunications. One of the products it offers to network operators is wireless infrastructure such as base stations. Such equipment is delivered in cabinets. these ...
详细信息
ISBN:
(纸本)9783540749691
Alcatel-Lucent is a major player in the field of telecommunications. One of the products it offers to network operators is wireless infrastructure such as base stations. Such equipment is delivered in cabinets. these cabinets are packed with various pieces of electronics: filters, amplifiers, circuit packs, etc. the exact configuration of a cabinet is dependent upon the circumstances it is being placed in, and some 20 product groups can be distinguished. However, the variation in cabinets is large, even within one product group. For this reason, they are built to order. In order to improve cost, yield and delivery performance, lean manufacturing concepts were applied to change the layout of the factory to one based on cells. these cells focus on improving manufacturing through standardised work, limited changeovers between product groups and better utilisation of test equipment. A key component in the implementation of these improvements is a system which schedules the cells to satisfy customer request dates in an efficient sequence. this paper describes the transformation and the tool that was built to support the new method of operations. the implementation has achieved significant improvements in manufacturing interval, work in process inventory, first test yield, headcount, quality (i.e. fewer defects are found during the testing stage) and delivery performance. Although these benefits are mainly achieved because of the change to a cell layout, the scheduling tool is crucial in realising the full potential of it.
Motivated by the performance improvements made to SAT solvers in recent years, a number of different encodings of constraints into SAT have been proposed. Concrete examples are the different SAT encodings for <= 1 ...
详细信息
ISBN:
(纸本)9783540749691
Motivated by the performance improvements made to SAT solvers in recent years, a number of different encodings of constraints into SAT have been proposed. Concrete examples are the different SAT encodings for <= 1 (x(1),..., x(n)) constraints. the most widely used encoding is known as the pairwise encoding, which is quadratic in the number of variables in the constraint. Alternative encodings are in general linear, and require using additional auxiliary variables. In most settings, the pairwise encoding performs acceptably well, but can require unacceptably large Boolean formulas. In contrast, linear encodings yield much smaller Boolean formulas, but in practice SAT solvers often perform unpredictably. this lack of predictability is mostly due to the large number of auxiliary variables that need to be added to the resulting Boolean formula. this paper studies one specific encoding for <= 1 (x(1),...,x(n)) constraints, and shows how a state-of-the-art SAT solver can be adapted to overcome the problem of adding additional auxiliary variables. Moreover, the paper shows that a SAT solver may essentially ignore the existence of auxiliary variables. Experimental results indicate that the modified SAT solver becomes significantly more robust on SAT encodings involving <= 1 (x(1),...,x(n)) constraints.
As a first attempt to exploit symmetries in continuous constraint problems, we focus on permutations of the variables consisting of one single cycle. We propose a procedure that takes advantage of these symmetries by ...
详细信息
this talk consists of two interwoven stories. the Happy Story presents a technical solution to the problem of optimizing for cost instead of the more normal metric of duration. We describe a mechanism whereby the opti...
详细信息
Topology optimization of continuum structures is a relatively new branch of the structural optimization field. Since the basic principles were first proposed by Bendsoe and Kikuchi in 1988, most of the work has been d...
详细信息
ISBN:
(纸本)9781845640705
Topology optimization of continuum structures is a relatively new branch of the structural optimization field. Since the basic principles were first proposed by Bendsoe and Kikuchi in 1988, most of the work has been devoted to the so-called maximum stiffness (or minimum compliance) formulations. However, for the past few years a growing effort is being invested in the possibility of stating, and solving these kinds of problems in terms of minimum weight with stress (and/or or displacement) constraints formulations because some major drawbacks of the maximum stiffness statements can be avoided. Unfortunately, this also gives rise to more complex mathematical programming problems, since a large number of highly non-linear (local) constraint at the element level must be taken into account. In an attempt to reduce the computational requirements of these problems, the use of a single so-called global conistraint has been proposed. In this paper, we create a suitable class of global type conistraints by grouping the elements into blocks. then, the local constraints corresponding to all the elements within each block are combined to produce a single aggregated constraintthat limits the maximum stress within all the elements in the blcock. thus, the number of constraints can be drastically reduced. Finally, we compare the results obtained by our block aggregation technique withthe usual global constraint formulation in several application examples.
the proceedings contain 61 papers. the topics discussed include: global optimization of probabilistically constrained linear programs;algorithms and constraintprogramming;infinite qualitative simulations by means of ...
详细信息
ISBN:
(纸本)3540462678
the proceedings contain 61 papers. the topics discussed include: global optimization of probabilistically constrained linear programs;algorithms and constraintprogramming;infinite qualitative simulations by means of constraintprogramming;graph-properties based filtering;an algebraic characterization of complexity for valued constraints;typed guarded decompositions for constraint satisfaction;the minimum spanning tree constraint;performance prediction and automated tuning of randomized and parametric algorithms;adaptive clause weight redistribution;localization of an underwater robot using interval constraint propagation;approximability of integer programming with generalized constraints;generalized arc consistency for positive table constraints;and stochastic allocation and scheduling for conditional task graphs in MPSoCs.
In this paper we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possi...
详细信息
暂无评论