線性丢番圖方程系統（LDEs）連同其子類--子集和問題--在現實世界有大量且重要的應用。可是當線性番圖方程系統的整數解集被限定在一個有界的多面體中，則此系統屬于NP類問題。同理其子類--子集和問題--也同屬于NP類問題。另一方面，密度（density）接近或等于一的子集和問題已在文獻中被證實爲最難的一類子集和問題，並且現有的針對此最難子集和問題的所有解決方案都不能達到令人滿意的成功率。因此，在這篇論文中，我們旨在提出有效的算法來求解線性番圖方程系統以及其子類問題--密度爲一的子集和問題。 / 我們在此論文中的研究包括：1）基于格理論和LLL算法的性質，采用並改良針對LDEs的格表達式（lattice formulations）；2）提出針對子集和問題的分解（disaggregation）技術；3）創造性地將分解技術與格表達式整合在一起，從而提高求解密度爲一的子集和問題的成功率。 / 數值實驗顯示，我們提出的新整合算法對提高密度爲一的子集和問題的成功率有著顯著的效果。比如，針對維數分別爲20,30和40的密度爲一的子集和問題，對各個維數隨機産生的100個問題，我們的新整合算法均可將成功率提高到100%。同時，針對新整合算法的理論分析顯示，能將短且非0-1的整數解切割掉的分解在達到新整合算法的顯著實驗效果中起到了關鍵作用。 / While systems of linear Diophantine equations (LDEs) with bounded feasible set, including subset sum problem as its special subclass, find wide, and often significant, real-world applications, they unfortunately belong to the NP class in general. Furthermore, the literature has revealed that subset sum problems with their density close to one constitute the hardest subclass of subset sum problems and all the existing solution methods do not perform to a satisfactory level (with low success ratio) even when the problem size is only medium. / We take the challenge in this thesis to investigate lattice formulations for systems of LDEs in which LLL basis reduction algorithm (LLL algorithm) is utilized, propose disaggregation techniques for subset sum problems, and develop a powerful integration of disaggregation techniques with lattice formulations in solving feasible subset sum problems. / More specifically, the contributions in this thesis can be classified into three parts: i) we propose two revised lattice formulations of Aardal et al. (2000) for systems of LDEs to enhance further the computational capability of the LLL algorithm; ii) we study properties related to disaggregation of a single LDE and investigate thoroughly disaggregation schemes based on modular transformations; and iii) we develop a novel version of LLL algorithm by integrating modular disaggregation into the solution process. Promising numerical results have been achieved when applying our newly proposed LLL algorithm in tackling hard subset sum problems with density close to one. For instance, the success ratio can be raised to 100% for 100 randomly generated hard subset sum problems with dimensions 20, 30, and 40, respectively. We carry out theoretical study for possible driving force behind the success of our new algorithm, including dimension reduction of the solution space, information recovering of LDEs, and mechanism in cutting off short non-binary integer solutions when attaching disaggregation with LLL algorithm. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Lu, Bojun. / Thesis (Ph.D.) Chinese University of Hong Kong, 2014. / Includes bibliographical references (leaves 143-153). / Abstracts also in Chinese.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_1077681 |
| Date | January 2014 |
| Contributors | Lu, Bojun (author.), Li, Duan , 1952- (thesis advisor.), Chinese University of Hong Kong Graduate School. Division of Systems Engineering and Engineering Management, (degree granting institution.) |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography, text |
| Format | electronic resource, electronic resource, remote, 1 online resource (x, 153 leaves) : illustrations (some color), computer, online resource |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0025 seconds