Ingest: Dynamic Variable Ordering In CSPs (Bacchus and van Run, CP-95)

Type: types/ingest-report.md

Classification

This is a peer-reviewed conference paper (CP-95, LNCS 976). It combines an implementation method, theorems with proofs (some abridged for space), and a benchmark over 24 algorithm variants. Author: Fahiem Bacchus is an established constraint-satisfaction and planning researcher; Paul van Run was his co-author from industry. The venue is a primary specialist venue for the field.

Summary

The paper studies dynamic variable ordering (DVO) in tree search for binary constraint satisfaction problems. It separates two things that earlier work had merged: DVO, the general technique of choosing the next variable per branch, and MRV (minimum remaining values), the specific heuristic of committing next the variable with the fewest values still compatible with prior assignments. It gives a simple method for adding DVO to any tree-search algorithm: keep the search-tree depth (node index) distinct from the variable index. It then proves that under MRV, standard backjumping never jumps further than one step (Theorem 2), and that backtracking-family algorithms with MRV computed by forward-checking pruning cost between 1x and 2KN times the consistency checks of forward checking with MRV (Theorem 3). The stated mechanism is fail-first: MRV "promot[es] future failures to the next variable", so dead ends surface immediately. In experiments on Zebra, n-Queens, and random binary CSPs, measured in consistency checks, MRV-based DVO beat the same algorithms under static orders in every reported test except all-solutions n-Queens. Forward checking with MRV (FCvar) was within 5% of the best algorithm tested. The authors name where the approach stops paying: large, easy problems with exponentially many solutions, where local search such as GSAT is better. They also report a conjecture from Prosser that MRV may be misled when variables start with very different domain sizes. All results concern exact binary CSPs, check counts as the cost measure, uniform domain sizes in the reported tests, and MRV as the only dynamic heuristic compared.

Quotes

No source quotes have been retained yet.

Connections Found

The source's main role is as the formal and empirical anchor, from another field, for Solve low-degree-of-freedom subproblems first to avoid blocking better designs. That note's four-step rule is MRV with dynamic reordering. Its step 3, "recompute feasible sets for remaining choices", corresponds to forward-checking pruning. Its only current support is Alexander's kitchen example. The source both supports the rule and complicates it. It supports the rule because MRV-based ordering gave large gains over static orders in nearly every reported test. It complicates the rule because the CSP rationale is fail-first (surface dead ends early and back up cheaply), while the note's rationale is optionality preservation (avoid consuming the few viable options of a constrained choice). The two mechanisms coincide when commitments can be undone cheaply. They can diverge when commitments are hard to reverse, which is the note's design setting. The source tests only the reversible, exact-check setting, so it is evidence for the ordering rule, not for the optionality rationale.

The source is also a counterpoint and data point for the KB's search-control notes. Theorem 2 and the small CBJ gain give a formal case for a failure explanation becomes search control only when it changes a later branch decision: under MRV, standard backjumping retains correct failure information yet changes no later branch decision, because the ordering has already placed the conflicting variable next. It supplies source grounding for the "conflict-directed backtracking" family in Cost-sensitive formalisms for tentative theory search, which has no ordering family and whose Scope says its families need source grounding. It compares with An assumption-based TMS on how a search system avoids redundant work after a contradiction: the ATMS retains nogoods, while this source shows a good ordering makes some retained failure structure redundant.

Extractable Value

1. Formal and empirical support for committing the most-constrained decision first -- MRV-based DVO beat static ordering in every reported test except all-solutions n-Queens, often by orders of magnitude in consistency checks (for example BT 3859k vs BTvar 1.1k checks on Zebra first solution). This is the strongest external evidence the KB has for the low-DoF note's rule. The comparison is MRV-based DVO against Prosser's 450 static orderings and fixed static orders, not against other dynamic heuristics, so it shows that constraint-aware dynamic ordering beats arbitrary static ordering, not that MRV is the best dynamic heuristic. [quick-win]
2. Fail-first as a rival mechanism to optionality preservation -- the source's mechanism is that MRV makes failures surface at the next level, so search does not spend exponential work before reaching a doomed variable. The low-DoF note gives only optionality preservation. A revision can state both and say when each applies: fail-first pays when commitments can be undone and checking is cheap; optionality preservation is the argument when commitments are hard to reverse. This source does not test the second setting. [quick-win]
3. Where the ordering rule stops helping -- the source names four boundaries. (a) On large, easy problems with exponentially many solutions, forward checking's pruning is expensive and guided random search (GSAT) is better. (b) When enumerating all solutions to n-Queens, static-order backmarking outperformed its DVO counterpart, although FCvar still beat it by about 15%. (c) The paper reports a conjecture, from Prosser, that MRV may be misled when variables start with very different domain sizes, the setting the reported tests exclude. (d) The heuristic has a cost: computing MRV consumes at least as many checks as forward checking (Theorem 3), and the paper states that its costs are not guaranteed to be worthwhile. These give the low-DoF note concrete scope conditions it currently lacks. [quick-win]
4. An answer, in one setting, to the note's open question on explicit degree-of-freedom estimates -- the low-DoF note asks whether degree-of-freedom estimates can be made explicit enough for deterministic schedulers. In exact CSPs they can: MRV_FC is a count of remaining pruned domain values, maintained incrementally at the cost of forward checking. That estimate depends on exact, cheap pairwise consistency checks, which natural-language design choices do not have. [just-a-reference]
5. Good ordering and retained failure explanations partly substitute for each other -- under MRV, standard backjumping is exactly redundant (Theorem 2), and conflict-directed backjumping added at most 5% in the reported tests; the authors explain this by MRV clustering conflicted variables together. So the value of retained failure analysis depends on how weak the ordering is. This is a candidate scope condition for the failure-explanation note and a candidate complexity question for the cost-sensitive catalogue. It is shown only for exact binary CSPs with identical domain sizes. [experiment]
6. Heuristic authority widening into the algorithm -- the authors restrict MRV to returning only the next variable, and show that sharing pruned domains or wipeouts with the search leads to an algorithm identical to forward checking. This is a formal instance of where an ordering heuristic's role ends and inference begins, relevant to lightweight search control allocates further search without licensing adoption. [just-a-reference]
7. Separate the ordering technique from the ordering heuristic -- the paper's node/variable distinction and its DVO/MRV distinction are a reusable framing: whether order can vary per branch is a separate choice from which rule picks the next commitment. KB notes that discuss "ordering" can keep these apart. [just-a-reference]

Limitations (our opinion)

The evidence is narrow in setting. All problems are binary CSPs with exact, cheap consistency checks and undoable commitments, and the cost measure is constraint-check count, not wall-clock time or memory. The reported tests use identical domain sizes, so the case where MRV is conjectured to fail (heterogeneous domains) was not tested. MRV is the only dynamic heuristic compared, so the experiments cannot separate "most-constrained-first" from "any constraint-aware dynamic order"; tie-breaking and degree-based alternatives are absent. The benchmark set is small (Zebra, n-Queens, four random classes of 30 instances each), and random instances are drawn from Frost and Dechter's 50%-solvable region, the hard region where fail-first ordering is expected to help most. The proofs of Theorems 3 and 4 are abridged or omitted. The paper dismisses Frost and Dechter's contrary FCvar result by citing a suspected bug reported in personal communication, which is not independently verified.

Transfer to the low-DoF note needs care. That note's setting is design decomposition, where "feasible set size" is a judgment rather than a count, checks are expensive and fallible, and some commitments cannot be undone. A simpler account of the source's gain is that any static order chosen without regard to constraints is poor, and MRV wins mainly by avoiding late discovery of wipeouts; that account supports fail-first and says nothing about optionality preservation. The source should be cited as evidence for the ordering rule in reversible exact search and as the origin of the fail-first mechanism, not as confirmation of the note's optionality rationale.

Recommended Next Action

Revise Solve low-degree-of-freedom subproblems first to avoid blocking better designs: add fail-first beside optionality preservation as a second mechanism, cite this ingest as evidence for the rule in reversible exact search, add a short scope paragraph naming where the rule stops helping (large easy problems with many solutions, all-solution enumeration, heterogeneous initial feasible-set sizes, and the ordering computation's own cost), and answer the first open question for the exact-check case.