Propagation Redundancy for Permutation Channels
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1370-1370.
© 2003 International Joint Conferences on Artificial Intelligence
Abstract
- [Abdennadher and Rigotti, 2002] S. Abdennadher and C. Rigotti. Automatic generation of rule-based solvers for intentionally defined constraints. IJTAI, 11(2):283-302, 2002.
- K. Apt and E. Monfroy. Constraint programming viewed as rule-based programming. TPLP, I (6):713-750, 2001.
- [Cheng et al., 1999] B.M.W. Cheng, K.M.F. Choi, J.H.M. Lee, and J.C.K. Wu. Increasing constraint propagation by redundant modelling: an experience report. Constraints, 4(2):167-192, 1999.
- [Choi and Lee, 2002] C.W. Choi and J.H.M. Lee. On the pruning behaviour of minimal combined models for per- mutation CSPs. In International Workshop on Reformu- lating Constraint Satisfaction Problems, 2002.
- [Schulte and Stuckey, 2001] C. Schulte and P. J. Stuckey. When do bounds and domain propagation lead to the same search space. In PPDP 2001, pages 115-126,2001.
- [Smith, 2000] B. M. Smith. Modelling a permutation prob- lem. Research Report 2000.18, School of Computer Stud- ies, University of Leeds, 2000.
- [Walsh, 2001] T. Walsh. Permutation problems and chan- nelling constraints. In LPAR 2001, pages 377-391,2001 .
- [Gomes et al., 2002] C. Gomes and D. B. Shmoys. The promise of LP to Boost CSP Techniques for Combinato- rial Problems. In Proc. ofCPAIOR'02, Le Croisic, March 2002.
- [Gomes et al., 2002] C. Gomes and D. B. Shmoys. Com- pleting Quasi groups or Latin Squares: A Structured Graph Coloring Problem In Proc. Computational Symposium on Graph Coloring and Generalizations, 2002.
- [Walsh, 2001] T. Walsh. Permutation Problems and Chan- neling Constraints. TR 26, APES Group, 2001.
- [Colbourn, 1984] C. Colbourn. The complexity of complet- ing partial latin squares. In Discrete applied Mathematics, (8):25-30, 1984.
- [Cheng et al., 1996] B.M.W. Cheng, J.H.M. Lee, and J.C.K Wu. Speeding up constraint propagation by redundant modeling. In 2nd Int. Conf on Principles and Practice of Constraint Programming, pp. 91-103, 1996.
- [Bessiere, Regin, 1996] C.Bessiere and J.C.Regin Mac and combined heuristics: two reason to forsake FC (and CBJ?) on hard problemss. In CP'96, pp. 61-75, Cambridge MA.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Finding a good model of a constraint satisfaction problem (CSP) is a challenging task. A modeller must specify a set of constraints that capture the definitions of the problem, and the model should also have strong propagation. In other words, the model should be able to quickly reduce the domains of the variables of the problem, and the implementation of these propagators should be efficient, and the search space should not be too large.
A problem can be modelled differently from two view points using two different sets of variables. In redundant modelling [Cheng eta!., 1999], we connect the two differ ent models with channelling constraints, which relates valu ations in the two different models stronger propagation be haviour can be observed. However, the additional variables and constraints impose extra computation overhead may out weigh the gain of reduction in search space.
In this paper we consider redundant models connected by permutation channels, which commonly arise when the un derlying problem is some form of assignment problem. Since each model is complete and only admits the solutions of the problem, each model is logically redundant with respect to the other model plus the permutation channel. In order to keep the benefits of redundant modelling without paying all the costs, We give a theorem which allows us to determine when we can eliminate constraints in the mutually redundant models that do not give extra propagation. Due to space lim itations, we state the theorem without proof.
2 Reasoning about Domain Propagation
We consider integer constraint solving with constraint propa gation and tree search.
An integer valuation B is a mapping of variables to integer values, written {x1 >-+ d1 , ... , Xn >-+ dn}. Let vars be the function that returns the set of variables appearing in a con straint or valuation. A constraint c defines a set of valuations solns(c) each mapping the same set of variables vars(c). We
*We thank Barbara Smith and the anonymous referees for their constructive comments. The work described in this paper was sub stantially supported by a grant from the Research Grants Coun ci l of the Hong Kong Special Administrative Region (Project no. CUHK4204/0IE).
P.J.Stuckey
Dept. of Comp. Sci. & Soft. Eng. University of Melbourne, 3010 Australia
pjs@cs.mu.oz.au
call solns (c) the solutions of c. A constraint c is logically re dundant with respect to a set of constraints C iff= C --+ c.
A domain D is a complete mapping from a fixed (count able) set of variables V to finite sets of integers. A false do main D is a domain with D( x) = 0 for some x. A domain D1 is stronger than a domain D2, written D1 ~ D2, if Dt is a false domain or D1 ( x) ~ D2 ( x) for all variables J; . The initial domain D;nit gives the initial values possible for each variable, allows us to restrict attention to domains D such that DC D;nit ·
We adopt the notion of propagation solver and domain consistency' from Schulte and Stuckey [200 1]. A propaga tor f is a monotonically decreasing function from domains to domains. A propagation solver for a set of propagators F and current domain D, solv(F, D), repeatedly applies all the propagators in F starting from domain D until there is no further change in resulting domain. A domain D is domain consistent if D is the least domain containing all solutions of c in D. Define the domain consistency propagator dom(c) for a constraint c such that solv(dom(c), D) is always do main consistent for c.
For all domains D C Dinit, a set of propagator F2 is made propagation redunda~ by a set of propagators F1 , written F1 » F2 , if solv(F1 ,D) ~ solv(F2,D), and is equivalent to F1, written F1 ~ F2, if solv(F1, D) = solv(F2, D) .
It is well known that in general the domain propagation of a conjunction of constraints is not equivalent to applying the domain propagators individually. But there are cases where propagation of a conjunction is equivalent to propagation on the individual conjuncts.
Lemma 1 If c1 and c2 share at most one variable x, then {dom(cl) , dom(c2 )} ~ {dom(ctl\ c2)}.
An atomic constraint is one of x; = d or x; :f. d where x; E V and dis an integer. An atomic constraint represents the basic changes in domain that occur during propagation.
A propagation rule is of the form C ,__.. c where C is a conjunction of atomic constraints, c is an atomic constraint and ~ C --+ c. Note our propagation rules are similar to the "membership rules" of Apt and Monfroy [200 1] except we allow equations on the right hand side.
A propagator f implements a propagation rule C ,__.. c if for each D ~ Dinit whenever f= D --+ C, then f= f(D) -+c.
1 Equivalently, hyper-arc or generalized arc consistent.
We can characterize a propagator f in terms of the propaga tion rules that it implements. Let rules(!) be the set of rules implemented by f. Then prop(!) ~ rules(!) are a set of propagation rules such that every r E rules(!) is subsumed by a rule r' E prop(!).
3 Permutation Channels
A common form of redundant modelling is when we con sider two viewpoints to a permutation problem. We can view the problem as finding a bipartite matching between two sets of objects of the same size. For notational conve nience, let the two viewpoints as having the set of variables X= {xo , ... , xn}, andY= {yo, ... , Yn} respectively.
The permutation channel Ci>l is defined by the conjunction of constraints /\7=o l\j=0 (x; = j {::} Yi = i). The permuta tion channel propagator FM maintains domain consistency of each individual hi-implication, that is U7=o Uj=O {dam (x; = j {::} Yj = i)}.
Smith [2000] first observes that the permutation channel makes each of the disequations between variables in either model propagation redundant. Walsh [200 1] proves this holds for other notions of consistency.
Lemma 2 (Walsh, 2001) FM » { dom(x; :f. xk)}
Related to eM is the permutation channel function t><l which is a bijection between atomic constraints in X to atomic con straints in Y, t><l (x; = j) = (Yj = i), and t><l (x; :f. j) = (Yj :f. i). We extend t><l to map conjunctions of constraints in the obvious manner t><l(C1 1\ C2) =t><l( C!)/\ t><l( C2).
The fundamental theorem states that a constraint in Y is propagation redundant if there exist a constraint in X when COnjunctS With CM logically imply every propagation rules implemented by the constraint in Y. Since t><l is bijective, the theorem is valid when X and Y are reversed.
Theorem 3 Let fy be a propagator on Y, and ex be a con straint on X. ifF (Din it 1\ c x 1\ t><l (C)) ---+ t><l (c) for all (C ,_.c) E prop(fy ), then { dom(cx)} U FM » {fy }.
Example 4 Smith [2000] suggests two ways to model the Langford's problem as a permutation problem and how to combine them with the permutation channel. She points out that the so-called minimal combined model, which includes only X model and the permutation channel, gives as much pruning as the full combined model. This is proved in an ad hoc manner by Choi and Lee [2002] . We prove this formally using our generic approaches. 2
The disequality constraints are propagation redundant by Lemma 2. Consider the separation constraints cy = Yj = 3i {::} YJ+(i+2) = 3i+ 1. The propagation rules for dom(cy) are (rl) Yj = 3i ,_. YJ+(i+2) = 3i + 1, (r2) YJ+(i+2) = 3i + 1 ,_. Yj = 3i, (r3) Yj ::j:. 3i ,_. YJ+(i+2) ::j:. 3i + 1, and (r4) YH(i+2) :f. 3i + 1 ,_. Yi :f. 3i. We have that for ex= X3i+l = X3;+(i+2), F (Dinitl\cxl\ t><l(C))---+ t><l(c) for all propagation rules above. For example (rl) is mapped to x3; = j ,_. x3i+l = j + i + 2. Hence the conditions of Theorem 3 hold and dam ( cy) is propagation redundant.
2 The complete description of the two permutation models for the Langford's Problem can be found in [Choi and Lee, 2002].
Note the importance of equational propagation rules such as Yj = 3i ,_. YJ+(i+2) = 3i + 1. If we only allowed dis equations on the right hand side, we would replace this with rules Yi = 3i ,_. Yi+(i+2) :f. k , 0 ::; k :f. 3i + 1 ::; n . It is impossible to prove that the translated versions are implied by Dini t 1\ ex .
We can similarly show that each of the constraints c~ = Yj = 3i {::} YJ+2(i+2) = 3i + 2 are propagation redundant using ex 1\ c~, where c~ = x3;+2 = x3i+l + (i + 2) by Theorem 3. Although model Mx does not include a domain propagator for c x 1\ c~, we can still show propagation redun dancy since { dom(cx ), dom(c~)} ~ { dom(cx 1\ c~)} by Lemma I .
Similar reasoning applies to show that each constraint Yi f. 3i where 0 ::; i ::; 8 and 27 - 2 ( i + 2) ::; j ::; 26 is made propagationredundantby (x3i+l = x3;+(i+2)) 1\ (x3i+2 = X3i+l + (i + 2)) 1\ (0::; X3i+2::; 26) . 0
4 Conclusion
We have extend our approach to other types of channelling constraints and lead to significantly faster models that do not increase the search space. Although we have illustrated the use of the theorems herein by hand, the approach can clearly be automated. We can constructs the propagation rules automatically using the approach of Abdennadher and Rig otti [2002] . We are interested in extending the work to reason bounds propagation. Another direction is to study a weaker notion of propagation redundancy which allows removal of constraints without affecting the search space given a specific search heuristic.
References
[Abdennadher and Rigotti, 2002] S. Abdennadher and C. Rigotti. Automatic generation of rule-based solvers for intentionally defined constraints. IJTAI, 11(2):283-302, 2002.
[Apt and Monfroy, 2001] K. Apt and E. Monfroy. Constraint programming viewed as rule-based programming. TPLP, I (6):713- 750, 2001.
[Cheng et al., 1999] B.M.W. Cheng, K.M.F. Choi, J.H.M. Lee, and J.C.K. Wu. Increasing constraint propagation by redundant modelling: an experience report. Constraints, 4(2):167-192, 1999.
[Choi and Lee, 2002] C.W. Choi and J.H.M. Lee. On the pruning behaviour of minimal combined models for per mutation CSPs. In International Workshop on Reformu lating Constraint Satisfaction Problems, 2002.
[Schulte and Stuckey, 2001] C. Schulte and P. J. Stuckey. When do bounds and domain propagation lead to the same search space. In PPDP 2001, pages 115- 126,2001.
[Smith, 2000] B. M. Smith. Modelling a permutation prob lem. Research Report 2000.18, School of Computer Stud ies, University of Leeds, 2000.
[Walsh, 2001] T. Walsh. Permutation problems and chan nelling constraints. In LPAR 2001, pages 377-391,2001 .
Channeling Constraints and Value Ordering in the QuasiGroup Completion Problem
I van Doh! and Alvaro del Val and Manuel Cebrian Departamento de Ingenierfa Informatica Universidad Aut6noma de Madrid
- Primal Model: This model has a variable Xi,j for each cell of the latin square, with i and j its coordinates. Their possible values are the colors of the cell.
- Row Dual Model: This is the first dual model, it repre sents the colors in each row; the dual variable r; k is the k-th color in the i-th row, and the values it can take are the columns where it can be placed.
- Column Dual Model: This one models the colors in each column; the dual variable Cj,k represents the k-th color in the j-th column, with rows as its possible values.
The primal and dual not-equal constraints specify that the col ors in a row or column must all be different. While these are sufficient to capture the problem (and in fact redundantly so), it is known that these models can be improved by connecting them through channeling constraints:
- Row Channeling Constraints: Constraints for the n row permutation constraints, linking the primal model with the row dual model: Xi,j = k {:} Ti,k = j.
- Column Channeling Constraints: Corresponding to the n column permutation constraints, they link the primal and dual column models : Xi,j = k {:} Cj,k = i.
- Triangular Channeling Constraints: These (novel) con straints link both dual models, closing a "triangle" among the three models: Cj,k = i {:} r;,k = j.
It's easy to show that the first two kinds of channeling con straint fully capture a QCP (see also [Walsh, 2001]), making the primal and dual constraints redundant.
3 Value Ordering
Key to our results is a new value ordering heuristic, which we might call the min-domain value selection heuristic. Once a primal or dual variable is selected, we need to choose a value for it. Since any such value corresponds to one spe cific variable from each of the two other models, we select the value whose corresponding two variables have a minimal "combined" domain. Specifically, say we have chosen Xi,j · Then we choose a color k from its currently active domain for which the sum of the current domain sizes of r i,k and Cj,k is minimal among the currently available colors for Xi,j·
4 Results
We focused our experiments on solvable instances. To make our results comparable with those reported in [Gomes et al.,
1 Introduction
The Quasigroup Completion Problem (QCP) is a very chal lenging benchmark among combinatorial problems, and a fo cus of much recent interest in the area of constraint program ming. It has numerous practical applications [Gomes et al., 2002]; it has been put forward as a benchmark which can bridge the gap between purely random instances and highly structured problems [Gomes et al., 2002]; and its structure as a multiple permutation problem [Walsh, 2001] is common to many other important problems in constraint satisfaction.
[Gomes et al., 2002] reports that QCPs of order 40 could not be solved by pure constraint programming approaches, but could sometimes be solved by hybrid approaches com bining constraint programming with mixed integer program ming techniques from operations research. In this paper, we show that the pure constraint satisfaction approach can solve many problems of order 45 in the transition phase, which cor responds to the peak of difficulty. Our solution combines a number of known ideas -the use of redundant modeling [Cheng et al., 1996] with primal and dual models of the prob lem connected by channeling constraints [Walsh, 2001]- with some novel aspects, as well as a new and very effective value ordering heuristic.
2 Models for QCPs
A quasigroup is an ordered pair (Q, ·),where Q is a set and ·is a binary operation on Q such that the equations a. x = b andy· a = bare uniquely solvable for every pair of elements a, bin Q [Gomes et al., 2002]. The order n of the quasigroup is the cardinality of the set Q. A quasigroup can be seen as an n x n multiplication table defining a Latin Square, which must be filled with "colors" so that the colors of each row are all distinct, and similarly for columns. A QCP is the problem of coloring a partially filled Latin square, which is known to be NP-Complete [Colboum, 1984].
Each row and column of a Latin Square defines a permu tation problem, i.e. a constraint satisfaction problem with the same number of variables as values, where a solution is a permutation of the values [Walsh, 2001] . The QCP is a mul tiple permutation problem with 2n intersecting permutation constraints (n row permutation constraints and n column per mutation constraints). In order to represent those permutation problems we have implemented three models:

2002], we used the same generator 1 , and considered only "balanced" instances, which are known to be the hardest. We used an (AC3-based) Generalized Arc Consistency algorithm based on van Beek's CPLAN implementation (http:ai.uwaterloo.ca/rvvanbeek!software/software.html),
with a few improvements. We considered various (complete) combinations of all the above mentioned constraints, and found that adding the primal and dual "not-equal" constraints never helped performance in the presence of row and column channeling constraints, and yielded even worse results in their absence. Most of the results discussed below therefore use a model with only row and column channeling con straints; they also use "MAC" (mantaining arc consistency [Bessiere, Regin, 1996]). Since our preliminary tests showed that CBJ and nogood learning seem to never help in these problems, and are often a source of significant overhead, we discarded them. We also considered various variable selec tion heuristics. We found the min-domain heuristic, which selects a variable with smallest domain to be uniformly the best among the alternatives we tried, which included more sophisticated heuristics such as dom+degree, dom/degree, and variants of the above which took into account the (primal or dual) model to which variables belong, e.g. selecting only among primal variables, etc.
With only row and column channeling constraints, our im plementation outperforms classical approaches, in that we can solve a considerable amount of instances of order 40 in a reasonable time. As mentioned above, this was very recently considered as out of reach for pure constraint programming approaches [Gomes et al., 2002], which ours is (in fact, we don't even use global or non-binary constraints). The results when this model was used with the min-domain value order ing heuristic were quite surprising, as it outperformed previ ous tests in three orders of magnitude in some cases. For ex ample, for the instance bqwh-35-405-5.pls (balanced instance of order 35 and 60% preassigned) it took 2905 sees without value ordering and only 0.40 sees with it. In Figure 1 we present a comparison of our results with and without value ordering for quasigroups of order 30,35 and 40, and 60% pre assignment, close to the phase transition [Gomes et al., 2002] .
1 Generator lsencode, kindly provided by Carla Gomes.
Encouraged by this performance, we generated some in stances of order 45 and 60% preassignment. Again the value ordering heuristic turns out to be so efficient that we were able to solve a great number of instances in a reasonable amount of time. The next table shows median and mean time in sec onds (the latter taken only over solved instances) and percent of solved instances, using value ordering for problems in the transition phase.
| I order I | mean | I median | I % solved | I timeout |
|---|---|---|---|---|
| 30 | 148.84 | 174.11 | 68% | 1000 |
| 35 | 533.43 | 163.48 | 84% | 3600 |
| 40 | 690.85 | 842.11 | 68% | 5000 |
| 45 | 1090.10 | 2971.40 | 56% | 6000 |
Fmally, we are currently explonng the effect of adding "tri angular" channeling constraints; our preliminary results sug gest that they can improve performance by an additional 3035%, using in this case only forward checking (e.g. from 902 to 666 seconds in one order 45/60% preassigned instance). The idea is that they provably allow forward checking to per form as much pruning as arc-consistency, while saving many useless checks; in fact, as many as 60% fewer checks, even though the savings in time are not as great due to effects we are currently exploring.
5 Conclusions and Future Work
We have shown that a pure CSP approach can handle quasi group completion problems significantly larger than was thought possible, using appropriate models and value order ing heuristics, and even in the absence of global alldiff con straints. Yet our results are preliminary, and no doubt it would be interesting to consider other value ordering heuristics and ways to make the triangular channeling constraints most ef fective.
@inproceedings{ijcai2003p202,
title = {Propagation Redundancy for Permutation Channels},
author = {Choi, Chiu Wo and Lee, Jimmy Ho-Man and Stuckey, Peter J.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob and Toby Walsh},
pages = {1370--1370},
year = {2003},
url = {https://ijcai.org/proceedings/2003/202},
}
TY - CPAPER TI - Propagation Redundancy for Permutation Channels AU - Choi, Chiu Wo AU - Lee, Jimmy Ho-Man AU - Stuckey, Peter J. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1370 EP - 1370 UR - https://ijcai.org/proceedings/2003/202 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: