In integer programming, cut generation is crucial for improving the tightness of the linear relaxation of the problem. this is relevant for weighted constraint satisfaction problems (WCSPs) in which we use approximate...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
In integer programming, cut generation is crucial for improving the tightness of the linear relaxation of the problem. this is relevant for weighted constraint satisfaction problems (WCSPs) in which we use approximate dual feasible solutions to produce lower bounds during search. Here, we investigate using one class of cuts in WCSP: clique cuts. We show that clique cuts are likely to trigger suboptimal behavior in the specialized algorithms that are used in WCSP for generating dual bounds and show how these problems can be corrected. At the same time, the additional structure present in WCSP allows us to slightly generalize these cuts. Finally, we show that cliques exist in instances from several benchmark families and that exploiting them can lead to substantial performance improvement.
We propose a new top down search-based algorithm for compiling AND/OR Multi-Valued Decision Diagrams (AOMDDs), as representations of the optimal set of solutions for constraint optimization problems. the approach is b...
详细信息
ISBN:
(纸本)9783540749691
We propose a new top down search-based algorithm for compiling AND/OR Multi-Valued Decision Diagrams (AOMDDs), as representations of the optimal set of solutions for constraint optimization problems. the approach is based on AND/OR search spaces for graphical models, state-of-the-art AND/OR Branch-and-Bound search, and on decision diagrams reduction techniques. We extend earlier work on AOMDDs by considering general weighted graphs based on cost functions rather than constraints. An extensive experimental evaluation proves the efficiency of the weighted AOMDD data structure.
In most of the constraint-based approaches to planning, the problem is unfolded over a given number of steps. Because this Unfolded CSP encoding is very time mid memory consuming, we propose oil top of: the CNT framew...
详细信息
ISBN:
(纸本)9783642042430
In most of the constraint-based approaches to planning, the problem is unfolded over a given number of steps. Because this Unfolded CSP encoding is very time mid memory consuming, we propose oil top of: the CNT framework (constraint Networks on Timelines) a more efficient slice CSP encoding which allows only a limited number of steps to be considered at each step of the search.
Column Generation is a powerful method used to solve Constrained Set Partitioning problems. this method can be decomposed in two parts:the master problem and the sub-problem. the Master Problem that should be solved i...
ISBN:
(纸本)3540428631
Column Generation is a powerful method used to solve Constrained Set Partitioning problems. this method can be decomposed in two parts:the master problem and the sub-problem. the Master Problem that should be solved in Column Generation is derived from a simple Set Partitioning problem. Depending on the context the subproblem may become a variant of the simple Shortest-Path Problem; applications in scheduling generally present an acyclic graph (since one dimension of the graph is time) as opposed to routing problems that are cyclic by nature. However, most real life applications present resource constrained sub problems, typical resources being time, capacity, money, etc.
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.
Configuration tasks are an important application area in engineering design. the proposed solving techniques use either a constraint based framework or a logic-based approach. We propose a methodology to obtains desir...
详细信息
Symmetries in constraint satisfaction or combinatorial optimization problems can cause considerable difficulties for exact solvers. One way to overcome the problem is to employ sophisticated models with no or at least...
详细信息
In this paper, the embodiment design of an air conditioning system (ACS) in an aircraft is investigated using interval constraint satisfaction techniques. the detailed ACS model is quite complex to solve, since it con...
详细信息
ISBN:
(纸本)9783540749691
In this paper, the embodiment design of an air conditioning system (ACS) in an aircraft is investigated using interval constraint satisfaction techniques. the detailed ACS model is quite complex to solve, since it contains many coupled variables and many constraints corresponding to complex physics phenomena. Some new heuristics and notions based on embodiment design knowledge, are briefly introduced to undertake some embodiment design concepts and to obtain a more relevant and more efficient solving process than classical algorithms. the benefits of using constraintprogramming in embodiment design are discussed and some difficulties for designers using cp tools are shortly detailed.
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc con...
详细信息
ISBN:
(纸本)9783540749691
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc consistency after the assignment of a value to a variable) in order to identify inconsistent pairs of values, until a fixpoint is reached. In this paper, we propose two new algorithms, denoted by sDC2 and sDC3, to enforce (strong) PC following the DC approach. these algorithms can be seen as refinements of Mac Gregor's algorithm as they partially and totally exploit the incrementality of the underlying Arc Consistency algorithm. While sDC3 admits the same interesting worst-case complexities as PC8, sDC2 appears to be the most robust algorithm in practice. Indeed, compared to PC8 and the optimal PC2001, sDC2 is usually around one order of magnitude faster on large instances.
Lattice protein models are used for hierarchical approaches to protein structure prediction, as well as for investigating principles of protein folding. So far, one has the problem that there exists no lattice that ca...
详细信息
暂无评论