Research Of Consistency Algorithms For Negative Table Constraint Based On Cartesian Product Compression

Constraint programming is an important branch of artificial intelligence,which is widely used in product configuration?task scheduling and combinatorial optimization.Constraint programming provides a simple and effective solution for practical problems.Firstly,the practical problem is abstracted into a unified constraint model by constraint modeling,and then the model is solved by constraint solving technology.Backtracking search combined with consistency techniques is one of the main methods of constraint solving.Pruning backtracking search process through consistency techniques can improve the efficiency of problem solving.Table constraint is an important representation of constraint,expressed as a table by enumerating support or disallowed tuples.The purpose of table constraint processing is to maintain the consistency on constraint networks.Table constraint processing has a great influence on the efficiency of constraint solving.The generalized arc consistency(GAC)is the most widely used.Simple tabular reduction algorithm(STR)and its optimization(STR2 and STR3)are efficient algorithms to maintain generalized arc consistency on table constraints.The STR2 algorithm optimizes the STR algorithm in two ways.On the one hand,it only performs validity checks on variables whose domain has been changed;on the other hand,it skips variables whose values are all consistent in current domain.STR3 algorithm changes the representation of table constraint into dual table and maintains consistency on dual table.However,as the number of variables increases,the scale of table may increase exponentially,and the efficiency of table constraint processing will decrease.Some scholars use cartesian product compression method to compress the positive table,and put forward STR2-C and STR3-C,which maintain generalized arc consistency on the compressed positive table and are more time-saving and space-saving when the compression ratio is relatively high?The negative table of the constraint is the complementary representation of the positive table,and it's the set of all disallowed tuples.When the scale of negative table is smaller than the positive,processing of negative table is more efficient.STR-N is a simple tabular reduction algorithm which maintains consistency directly on the negative table.STR-N algorithm checks the consistency of constraint network by calculating the difference between valid tuples and valid disallowed tuples.STR-N judges whether the value in the domain satisfies generalized arc consistency according to whether the difference is zero.However,STR-N algorithm needs to traverse negative table when maintaining the consistency of constraint network,and its efficiency is low when the scale of negative table is large.Therefore,inspired by STR2-C and STR3-C,this paper optimizes STR-N algorithm.Firstly,We compress the negative table to the compressed negative table by cartesian product compression method,and propose the STRC-N algorithm to maintain generalized arc consistency on the compressed negative table.STRC-N algorithm also checks the consistency of constraint network by the difference between valid tuples and valid disallowed tuples.However,STRC-N algorithm calculates the number of valid disallowed tuples differently.STRC-N algorithm deals directly with valid compressed disallowed tuples,and the traversal of a valid compressed disallowed tuple can count multiple valid standard disallowed tuples.After the cartesian product compression,the space of the compressed negative table is smaller,so the STRC-N algorithm is more space-saving.STRC-N algorithm is faster and more efficient than STR-N due to the reduction of the size of negative compression table...