• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

An adaptive table compression method
for STR algorithms optimization

LI Shaoxing,LI Zhanshan,YU Haihong   

  1. (College of Computer Science and Technology,Jilin University,Changchun 130012,China)
  • Received:2018-06-08 Revised:2018-08-06 Online:2018-12-25 Published:2018-12-25

Abstract:

Table constraint, also called extensional constraint, is the most general form of finite domain constraint in the field of constraint programming. Table compressing methods can greatly reduce space consumption by compact representation of tuple set and accelerate the GAC algorithm. Cartesian product representation and short support are the two most common table compression methods in table constraint. We find that the compression ratio of the two table compression methods on the same problem is the main factor that affects their optimization results, and propose an adaptive table compression method based on STR algorithm. It adaptively selects the table compression method with larger compression ratio when solving the problem. We apply the adaptive table compression method to the STR2 algorithm, and propose an STR2-adaptive algorithm, which can cover the advantages of the two table compression methods. Experimental results show that the STR2-adaptive algorithm can adaptively select the best table compression method on most instances and effectively reduces space cost and CPU running time of the STR2 algorithm. Then we extend the adaptive table compression method to the STRbit algorithm using efficient bit vector representation, and we propose the STRbit-adaptive algorithm. Experimental results show that the efficiency of STRbit-adaptive algorithm generally has higher efficiency than that of the STRbit algorithm.
 

Key words: constraint programming, table constraint, simple tabular reduction, table compression, adaptive selection, bit vector