In this paper, we investigate the possibility of improvement of the widely-used filtering algorithm for the linear constraints in constraint satisfaction problems in the presence of the alldifferent constraints. In many cases, the fact that the variables in a linear constraint are also constrained by some alldifferent constraints may help us to calculate stronger bounds of the variables, leading to a stronger constraint propagation. We propose an improved filtering algorithm that targets such cases. We provide a detailed description of the proposed algorithm and prove its correctness. We evaluate the approach on five different problems that involve combinations of the linear and the alldifferent constraints. We also compare our algorithm to other relevant approaches. The experimental results show a great potential of the proposed improvement.
Finally, the idea of combining different types of global constraints in order to improve the constraint propagation is also employed in case of other constraints. For instance, in @cite_1 , the combination of the with two linear constraints is considered. On the other hand, in @cite_22 , the authors consider a combination of an constraint with the .
@cite_1 @cite_22
1505671383 1485061130 2768546550 1484088481
The global cumulative constraint was proposed for modelling cumulative resources in scheduling problems for finite domain (FD) propagation. Since that time a great deal of research has investigated new stronger and faster filtering techniques for cumulative, but still most of these techniques only pay off in limited cases or are not scalable. Recently, the "lazy clause generation" hybrid solving approach has been devised which allows a finite domain propagation engine possible to take advantage of advanced SAT technology, by "lazily" creating a SAT model of an FD problem as computation progresses. This allows the solver to make use of SAT nogood learning and autonomous search capabilities. In this paper we show that using lazy clause generation where we model cumulative constraint by decomposition gives a very competitive implementation of cumulative resource problems. We are able to close a number of open problems from the well-established PSPlib benchmark library of resource-constrained project scheduling problems. Local propagation is often used in graphical user interfaces to solve constraint systems that describe structures and layouts of figures. However, algorithms based on local propagation cannot solve simultaneous constraint systems because local propagation must solve constraints individually. We propose the ‘DETAIL’ algorithm, which efficiently solves systems of constraints with strengths, even if they must be solved simultaneously, by ‘dividing’ them as much as possible. In addition to multi-way constraints, it handles various other types of constraints, for example, constraints solved with the least squares method. Furthermore, it unifies the treatment of different types of constraints in a single system. We implemented a prototype constraint solver based on this algorithm, and evaluated its performance. First-order methods have been popularly used for solving large-scale problems. However, many existing works only consider unconstrained problems or those with simple constraint. In this paper, we develop two first-order methods for constrained convex programs, for which the constraint set is represented by affine equations and smooth nonlinear inequalities. Both methods are based on the classic augmented Lagrangian function. They update the multipliers in the same way as the augmented Lagrangian method (ALM) but employ different primal variable updates. The first method, at each iteration, performs a single proximal gradient step to the primal variable, and the second method is a block update version of the first one. For the first method, we establish its global iterate convergence as well as global sublinear and local linear convergence, and for the second method, we show a global sublinear convergence result in expectation. Numerical experiments are carried out on the basis pursuit denoising and a convex quadratically constrained quadratic program to show the empirical performance of the proposed methods. Their numerical behaviors closely match the established theoretical results. We introduce a new global constraint which combines together the lexicographic ordering constraint with some sum constraints. Lexicographic ordering constraints are frequently used to break symmetry, whilst sum constraints occur in many problems involving capacity or partitioning. Our results show that this global constraint is useful when there is a very large space to explore, such as when the problem is unsatisfiable, or when the search strategy is poor or conflicts with the symmetry breaking constraints. By studying in detail when combining lexicographical ordering with other constraints is useful, we propose a new heuristic for deciding when to combine constraints together.