多重集約束求解及其應用

在計算機科學領域中，子集和問題(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)，我們便能求解具有多個目標的多重集約束。另外，一些減少搜尋空間或是化簡約束真值表的改善技術也能增進求解的效率。最後，多重集約束的重要應用展示了我們框架的一般性，而實驗結果也顯示了求解的效率和改善技術的有效性。

關鍵字

多重集；子集和(積)問題；決策程序；裝箱問題；背包問題； k-分割問題；虛擬布林規劃；對稱性編碼

並列摘要

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.

並列關鍵字

multiset ； subset-sum (product) problem ； decision procedure ； bin-packing problem ； knapsack problem ； k-partition problem ； pseudo Boolean constraint ； symmetry encoding

參考文獻

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

46-93, 1979.

[7] GLPK (GNU linear programming tool kit) o_cail website:

[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.

國際替代計量

多重集約束求解及其應用

全文下載

主題瀏覽