It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the a...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.
In this paper, we consider the extension of multi-objective constraint optimization algorithms to the case where there are additional tradeoffs, reducing the number of optimal solutions. We focus especially on branch-...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
In this paper, we consider the extension of multi-objective constraint optimization algorithms to the case where there are additional tradeoffs, reducing the number of optimal solutions. We focus especially on branch-and-bound algorithms which use a mini-buckets algorithm for generating the upper bound at each node (in the context of maximizing values of objectives). Since the main bottleneck of these algorithms is the very large size of the guiding upper bound sets we introduce efficient methods for reducing these sets, yet still maintaining the upper bound property. We also propose much faster dominance checks with respect to the preference relation induced by the tradeoffs. Furthermore, we show that our tradeoffs approach which is based on a preference inference technique can also be given an alternative semantics based on the well known Multi-Attribute Utility theory. Our comprehensive experimental results on common multi-objective constraint optimization benchmarks demonstrate that the proposed enhancements allow the algorithms to scale up to much larger problems than before.
this paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraintprogramming which is able to model many realistic operational constra...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
this paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraintprogramming which is able to model many realistic operational constraints. the costs for berth allocation, crane allocation, time windows, breaks and transition times during gang movements are optimized simultaneously. the model is based on a resource view where gangs are consumed by vessel activities. Side constraints are added independently around this core model. the model is richer than the state of the art in the operations research community. Experiments show that the model produces solutions with a cost gap of 1/10 (7,8%) to 1/5 (18,8%) compared to an ideal operational setting where operational constraints are ignored.
Recently, a generic method for identifying and exploiting dominance relations using dominance breaking constraints was proposed. In this method, sufficient conditions for a solution to be dominated are identified and ...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Recently, a generic method for identifying and exploiting dominance relations using dominance breaking constraints was proposed. In this method, sufficient conditions for a solution to be dominated are identified and these conditions are used to generate dominance breaking constraints which prune off the dominated solutions. We propose to use these dominance relations in a different way in order to boost the search for good/optimal solutions. In the new method, which we call dominance jumping, when search reaches a point where all solutions in the current domain are dominated, rather than simply backtrack as in the original dominance breaking method, we jump to the subtree which dominates the current subtree. this new strategy allows the solver to move from a bad subtree to a good one, significantly increasing the speed with which good solutions can be found. Experiments across a range of problems show that the method can be very effective when the original search strategy was not very good at finding good solutions.
Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and constraint...
详细信息
Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and constraintprogramming aim to overcome this limitation, but also impose inconvenient constraints - first and foremost that quantitative information must be encoded by means of total functions. this goes against central knowledge representation principlesthat contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed withthe ultimate goal of providing scientists and practitioners with an alternative to CASP languages that allows for the efficient representation of qualitative and quantitative information in ASP without restricting one's ability to deal with incompleteness or uncertainty. In this paper we present the latest outcome of such research: versions of the language and of the supporting system that allow for practical, industrial-size use and scalability. the applicability of ASP{f} is demonstrated by a case study on an actual industrial application.
Some applications require the interactive resolution of a constraint problem by a human user. In such cases, it is highly desirable that the person who interactively solves the problem is not given the choice to selec...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Some applications require the interactive resolution of a constraint problem by a human user. In such cases, it is highly desirable that the person who interactively solves the problem is not given the choice to select values that do not lead to solutions. We call this property global inverse consistency. Existing systems simulate this either by maintaining arc consistency after each assignment performed by the user or by compiling offline the problem as a multi-valued decision diagram. In this paper, we define several questions related to global inverse consistency and analyse their complexity. Despite their theoretical intractability, we propose several algorithms for enforcing global inverse consistency and we show that the best version is efficient enough to be used in an interactive setting on several configuration and design problems. We finally extend our contribution to the inverse consistency of tuples.
We consider methods for constructing NP-intermediate problems under the assumption that P not equal NP. We generalize Ladner9;s original method for obtaining NP-intermediate problems by using parameters with variou...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We consider methods for constructing NP-intermediate problems under the assumption that P not equal NP. We generalize Ladner's original method for obtaining NP-intermediate problems by using parameters with various characteristics. In particular, this generalization allows us to obtain new insights concerning the complexity of CSP problems. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered. Hereby we generalize a result by Grohe on width parameters and NP-intermediate problems. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages G such that CSP(G) are NP-intermediate. the sets G can have very different properties compared to previous constructions (by, for instance, Bodirsky & Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. this settles an open question posed by Nordh & Zanuttini.
constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. the CONJURE automated constraint modelling system addresses this problem by automatically refining...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. the CONJURE automated constraint modelling system addresses this problem by automatically refining constraint models from problem specifications written in the ESSENCE language. ESSENCE provides familiar mathematical concepts like sets, functions and relations nested to any depth. To date, CONJURE has been able to produce a set of alternative model kernels (i.e. without advanced features such as symmetry breaking or implied constraints) for a given specification. the first contribution of this paper is a method by which CONJURE can break symmetry in a model as it is introduced by the modelling process. this works at the problem class level, rather than just individual instances, and does not require an expensive detection step after the model has been formulated. this allows CONJURE to produce a higher quality set of models. A further limitation of CONJURE has been the lack of a mechanism to select among the models it produces. the second contribution of this paper is to present two such mechanisms, allowing effective models to be chosen automatically.
EnergeTIC is a recent industrial research project carried out in Grenoble on optimizing energy consumption in data-centres. the efficient management of a data-centre involves minimizing energy costs while ensuring ser...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
EnergeTIC is a recent industrial research project carried out in Grenoble on optimizing energy consumption in data-centres. the efficient management of a data-centre involves minimizing energy costs while ensuring service quality. We study the problem formulation proposed by EnergeTIC. First, we focus on a key sub-problem: a bin packing problem with linear costs associated withthe use of bins. We study lower bounds based on Linear programming and extend the bin packing global constraint with cost information. Second, we present a column generation model for computing the lower bound on the original energy management problem where the pricing problem is essentially a cost-aware bin packing with side constraints. third, we show that the industrial benchmark provided so far can be solved to near optimality using a large neighborhood search.
Chemical reactions consist of a rearrangement of bonds so that each atom in an educt molecule appears again in a specific position of a reaction product. In general this bijection between educt and product atoms is no...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Chemical reactions consist of a rearrangement of bonds so that each atom in an educt molecule appears again in a specific position of a reaction product. In general this bijection between educt and product atoms is not reported by chemical reaction databases, leaving the Atom Mapping Problem as an important computational task for many practical applications in computational chemistry and systems biology. Elementary chemical reactions feature a cyclic imaginary transition state (ITS) that imposes additional restrictions on the bijection between educt and product atoms that are not taken into account by previous approaches. We demonstrate that constraintprogramming is well-suited to solving the Atom Mapping Problem in this setting. the performance of our approach is evaluated for a subset of chemical reactions from the KEGG database featuring various ITS cycle layouts and reaction mechanisms.
暂无评论