臺灣博碩士論文加值系統

在計算機科學領域中，子集和問題(subset-sum problem)在複雜度理論(complexity theory)以及密碼學的研究上都是一個重要的經典問題。有非常多組合數學上的最佳化問題都與子集和問題有關，例如:裝箱問題(bin-packing problem)、背包問題(knapsack problem)、k-分割問題(k-partition problem)、虛擬布林規劃(pseudo Boolean constraint)、對稱性編碼(symmetry encoding)等等。但據我們所知，目前並不存在一個具有足夠一般性(generality)的框架能適用於所有相關的問題及其變型且能對特定的問題結構作有效的求解。在這篇論文中，我們藉由一般化原本的子集和問題為多重集約束(multiset constraint)，進而發展出一個可用於求解各種多重集約束的一般性框架。我們所採用的一般化方法如下:首先，除了子集和問題中存在的相等關係，我們也同時考慮了其他的非相等關係。其次，我們允許多重集約束中存在多個需被同時滿足的目標。這使得需要作滿足性確認的多重算數約束(multiple arithmetic constraint)可以被執行。第三，我們討論了具有相等關係的子集積約束(subset-product constraint)。對於各種的多重集約束，我們也提出了一個基於搜尋的決策程序(decision procedure)。利用所提出的約束真值表(constraint table)，我們便能求解具有多個目標的多重集約束。另外，一些減少搜尋空間或是化簡約束真值表的改善技術也能增進求解的效率。最後，多重集約束的重要應用展示了我們框架的一般性，而實驗結果也顯示了求解的效率和改善技術的有效性。

In computer science, the subset-sum problem is an important classical problem in complexity theory and cryptography.
There are many combinatorial optimization problems, such as bin-packing, knapsack, k-partition, pseudo Boolean constraint, symmetry encoding and others, related to the subset-sum problem. Nevertheless, to the best of our knowledge, there is no a general framework that encompasses all the variant problems and yet explores specific problem structures for effective solving. In this thesis, we propose a general framework for solving various multiset constraints.
Our generalization includes the following.
First, inequality relations, besides the equality relation in the subset-sum problem, are allowed.
Second, multiple summation targets, instead of a signal target, are allowed.
It enables the specification of multiple arithmetic constraints for satisfaction checking.
Third, subset-product constraints with equality relation are also discussed.
For the considered multiset constraints, an effective and efficient search-based decision procedure is proposed.
By searching in the proposed constraint table, the constraints with multiple targets to be satisfied simultaneously can be solved.
Some techniques including search space pruning and table simplification are introduced to improve efficiency.
Formulations of important applications show the generality of our solving framework, and experimental results demonstrate their solving efficiency and the effects of our proposed improvements.

Acknowledgements i
Chinese Abstract ii
Abstract iv
List of Figures ix
List of Tables x
1 Introduction 1
1.1 Our Contributions 4
1.2 Thesis Organization 5
2 Preliminaries 7
2.1 Sets and Multisets 7
2.2 Symmetry Encoding 10
3 Multiset Constraints 12
3.1 Multiset Constraints 13
3.1.1 The Subset-sum Problem and Subset-product Problem 13
3.1.2 Subset-sum Constraints and Subset-product Constraints 14
3.1.3 Multiple Targets and Multiple Constraints 15
3.2 The Constraint Table 17
3.2.1 Basic Case Analysis 17
3.2.2 Table Properties and Negative Elements 22
3.2.3 Subset-product Constraint Table 28
3.3 Constraint System and Additional Constraints 34
4 Our Search Algorithm 36
4.1 Preprocessing 37
4.2 Computation Overview 42
4.3 The Search Procedure 46
4.4 Improvements 50
4.4.1 Search Space Pruning 50
4.4.2 Table Simpli_cation 55
5 Applications 58
5.1 k-partitioning 59
5.2 Bin-packing 59
5.3 Knapsack Problem Solving 61
5.4 Pseudo Boolean Constraint Solving 62
5.5 Symmetry Encoding 63
6 Experimental Results 65
6.1 Results of k-partitioning 65
6.2 Results of Bin-Packing 69
6.3 Results of Symmetry Encoding 72
6.4 Evaluation of Improvements 76
7 Conclusions and Future Work 80
7.1 Conclusions 80
7.2 Future Work 81

[1] F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah. Generic ILP versus Specialized 0-1 ILP: An Update. In Proceedings of International Conference on Computer Aided Design, pp. 450-457 2002.

[2] A. Biere, M. Heule, H. van Maaren, and T. Walsh (editors). Handbook of Satisfiability, IOS Press, 2009.

[3] E. G. Co_man Jr., M. R. Garey and D. S. Johnson. Approximation algorithm for bin packing: a survey. Approximation algorithms for NP-hard problems, pp.
46-93, 1979.

[4] D. Chai and A. Kuehlmann. A Fast Pseudo-Boolean Constraint Solver. In Proceedings of Design Automation Conference, pp. 830-835, 2003.

[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, MIT Press, 2001.

[6] S. A. Cook. The complexity of theorem proving procedures. In Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, pp. 151-158, 1971.

[7] GLPK (GNU linear programming tool kit) o_cail website:
http://www.gnu.org/software/glpk/

[8] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, 1979.

[9] B. Hayes. The Easiest Hard Problem. In American Scientist, 2002.

[10] D. Knuth. Sorting and Searching. The Art of Computer Programming, Vol. 3,Addison-Wesley, 1998.

[11] M.-Y. Li. Psuedo-Boolean Constraint Formulation of Symmetry Boolean Encoding for Multi-Valued Function, Master Thesis, National Taiwan University,2011.

[12] S. Mertens. The Easiest Hard Problem: Number Partitioning. Computational complexity and statistical physics, Oxford University Press, 2006.

[13] S. Martello and P. Toth. Knapsack problems: Algorithms and computer interpretations., Wiley-Interscience, 1990.

[14] G. L. Nemhauser and L. A. Wolsey. Integer and combinatorial optimization,Wiley, 1988.

[15] Python programming language o_cail website: http://www.python.org/

[16] K.-L. Yuan, C.-Y. Kuo, J.-H. Jiang, and M.-Y. Li. Encoding Multi-Valued Functions for Symmetry. To appear in Proceedings of International Conference on Computer-Aided Design, 2013.