PaperlayerView exact revision on arXiv

Source-linked AI summary

Domain Filtering Consistencies

C. Bessiere, R. Debruyne

arXiv:1106.0671v1cs.AI

TL;DR

Choosing a consistency level requires comparing how much pruning different local consistencies provide, but Figure 4 offers no quantitative information. The paper surveys stronger-than-arc consistencies that remove inconsistent domain values without changing network structure, and compares their pruning and time efficiencies theoretically and experimentally. Neighborhood inverse consistency and singleton restricted path consistency are the most pruningful, while SRPC is time-expensive and NIC has exponential worst-case time complexity.

  • Problem

    Choosing a consistency level requires comparing how much pruning different local consistencies provide, but Figure 4 offers no quantitative information.

    Source: k-RPC · p. 13

  • Method

    The paper surveys stronger-than-arc consistencies that remove inconsistent domain values without changing network structure, and compares their pruning and time efficiencies theoretically and experimentally.

    Source: . Conclusion · p. 24

  • Results

    Neighborhood inverse consistency and singleton restricted path consistency are the most pruningful, while SRPC is time-expensive and NIC has exponential worst-case time complexity.

    Source: . Conclusion · p. 24

  • Takeaways & Limitations

    The most pruningful consistencies are neighborhood inverse consistency and singleton restricted path consistency; SRPC is expensive in time, and NIC has exponential worst-case time complexity.

    Source: . Conclusion · p. 24

    The paper notes that the discussed task is far more difficult than looking for one solution.

    Source: p. 5

Abstract

from arXiv · show

Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them.

AC RPC RPC PIC · NIC NIC SAC SAC · 2-RPC PIC

This subsection characterizes relative strength among local consistencies: one is not stronger than another when the latter deletes a value on a network consistent with the former. Figure 3 gives networks demonstrating some such relations.

PIC 2-RPC PIC Max-RPC

  • A is not stronger than B when B deletes a value on a network consistent with A.The passage states this criterion for a “not stronger” relation.Source: PIC 2-RPC PIC Max-RPC · p. 12
  • Figure 3 presents constraint networks demonstrating some of the mentioned “not stronger” relations.The figure is described as proving these relations between some of the consistencies discussed.Source: PIC 2-RPC PIC Max-RPC · p. 12

Max-RPC

This section examines how local consistencies prune values on constraint networks and how their pruning strength relates to enforcement cost across network structures and densities. It highlights RPC and Max-RPC as relatively inexpensive options to maintain during search, while noting that stronger pruning can entail substantial costs.

k-RPC

  • Because the consistency-relation figure provides no quantitative pruning information, the authors evaluate pruning on random networks with fixed variables and domain sizes as constraints vary.The experiment aims to quantify pruning efficiency across changing network density and constraint tightness.Source: k-RPC · p. 13

Tightness

  • PIC is stronger than RPC, but their pruning efficiencies are close; RPC removes most path-inverse-inconsistent values, while 2-RPC prunes more than PIC.RPC lies between AC and Max-RPC in pruning efficiency, and k-RPC for k > 1 is incomparable with PIC by the stronger relation.Source: Tightness · p. 15
  • SAC and strong PC have nearly identical pruning limits, whereas SRPC is incomparable with strong PC by relation but prunes more values.The pruning limits of SAC and strong PC merge, with a slight difference.Source: Tightness · p. 15
  • On most networks, stronger consistencies delete no values or detect no inconsistency, but propagation from the first deletions often causes a domain wipeout.The section notes that denser networks with loose constraints can make inconsistent values difficult to delete.Source: Tightness · p. 16
  • On sparse networks, polynomial local consistencies approach variable completability; on dense networks, NIC prunes far more than the others.Below density .28, NIC is less pruningful than SRPC, strong PC, and SAC; on complete networks, NIC corresponds to variable completability.Source: Tightness · p. 16
  • Max-RPC often has the best CPU-time performance on arc-inconsistent RLFAP instances, and stronger consistency can wipe out a domain faster than AC when AC needs propagation to expose inconsistency.On some Graph instances, Max-RPC finds inconsistency where AC, RPC, or PIC do not; on others, it wipes out a domain while those methods do not.Source: Tightness · pp. 17–19
  • On many RLFAP problems, pruning differs among consistencies, and greater pruning generally costs more time; AC, RPC, PIC, and Max-RPC remain similar in cost, unlike often much-costlier SAC, SRPC, and NIC.NIC is unstable: exponential blowups can make it prohibitive, and when it runs reasonably its pruning is closer to Max-RPC than SAC.Source: Tightness · pp. 18–19
  • On sparse generated networks, AC, PIC, RPC, and Max-RPC have similar CPU-time and deletion-ratio performance, with PIC slightly ahead on deleted-value ratios.When the constraint graph has few 3-cliques, PIC can cost little more than AC, while RPC is about twice as costly because it seeks two supports per value per constraint.Source: Tightness · p. 20
  • On denser networks, AC, RPC, PIC, and Max-RPC have similar complexity peaks, but PIC adds few values pruned over RPC while costing close to Max-RPC; Max-RPC has one of the best time-per-deleted-value ratios.NIC is the most pruningful on these networks and has the best ratio across a wide range of tightnesses, but some instances take over two hours, and its prohibitive cases grow as density increases.Source: Tightness · p. 20

Discussion

  • Strong path consistency is described as the least interesting filtering technique, compared with SAC, which removes most strong path-inconsistent values.Source: . Discussion · p. 20

6.5 Discussion

  • SAC and SRPC often have among the worst CPU-time-per-deleted-value ratios, especially on sparse constraint networks.The discussion adds that these algorithms are so expensive that improvements are unlikely to make them the most worthwhile filters.Source: . Discussion · p. 23
  • On sparse uniform networks, NIC’s additional pruning over Max-RPC does not offset its extra cost; on dense networks, its runtime can exceed that of search.The authors therefore restrict NIC’s worthwhile use to relatively dense networks, while noting that some instances can still cause combinatorial explosion.Source: . Discussion · p. 23
  • RPC2 and Max-RPC have better CPU time per deleted value than PIC2, except that PIC2 can be cheaper than RPC2 on very sparse networks while adding few deletions.The passage describes PIC2’s CPU-time performance as close to RPC2’s.Source: . Discussion · p. 23
  • RPC and Max-RPC are the most promising consistencies for search: they prune more than arc consistency at relatively low cost and may outperform MAC on very hard problems.The authors cite experiments with Quick, which maintains an adaptation of Max-RPC, as support for the comparison with MAC.Source: . Discussion · p. 23
  • Quick had better CPU-time performance than MAC on large, hard, relatively sparse random networks, and its performance was more stable.The reported stability reflects Quick’s very low standard deviation in CPU-time performance.Source: . Discussion · pp. 23–24

7. Conclusion

  • The paper extends restricted path consistency to k-RPC and Max-RPC, introduces singleton consistencies, and compares local consistencies theoretically and experimentally.Its scope includes consistencies that can be used on large networks while removing more values than arc consistency.Source: . Conclusion · p. 24
  • Neighborhood inverse consistency and SRPC are the most pruningful consistencies, but SRPC is expensive and NIC’s exponential worst-case time makes it unusable on dense networks.For consistencies considered for maintenance during search, the conclusion instead favors RPC and Max-RPC as relatively inexpensive and substantially more pruningful than arc consistency.Source: . Conclusion · p. 24
Loading 1106.0671v1…