應用分散式計算與Hermite Normal Form轉換於線性整數最佳化

Abstract

線性整數最佳化被廣泛的應用在許多組合最佳化的問題上，典型的問題像是，排程、包裝、運輸、旅行的推銷員問題等，不像是一般解連續解的問題，我們無法經由斜率取得任何有關目標值的資訊，以往解這類問題最有效的方法是Branch and Bound，但是Branch and Bound 演算法會消耗不確定的記憶體與時間，本文提出一個新的方法有效地找出線性整數最佳化的可能解，對於一個線性整數最佳化的問題，我們可以先利用基因演算法求得初始解，再應用Hermite Normal Form 演算法取得可能解與目標值所構成類似窗格的關係，最後運用分散式計算的觀念加速可能解檢驗的流程，我們運用了修正後的演算法求Hermite Normal Form，以克服在大型問題上典型Hermite Normal Form 演算法所面臨矩陣值過大的問題。實驗的結果證明，我們可以有效的解決幾個大型的問題，並取得最佳解。

Linear integer programs are extensively applied in many combinational optimization problems. Typical problems of this type include scheduling, knapsack, transformation, traveling salesman problem and more. Unlike continuous programs, we cannot have any information about the objective value of integer programs with gradient. The most well known algorithm for solving linear integer program is branch and bound algorithm, which however consumes uncertain time and memory space. This paper proposed a novel algorithm to efficiently find potential solutions of linear integer programs. For a linear integer program with an initial solution obtained by genetic algorithm or neural network, we may first collect coefficients from objective functions and equality constraints to form a basic matrix. Then, We may utilize Hermite normal form algorithm to gain advance information about the relationship between objective value and individual term of potential solutions in a polynomial time. The advance information will provide a better visibility in finding potential solutions of this linear programming problem. Finally, we utilized a distributed concept to verify those potential solutions in order to gain the final solution efficiently. While expending the size of linear integer programs, we found the original Hermite normal form algorithm has a severe drawback, which the size of items in the basic matrix will grow explosively. We thereby employee another efficient algorithm, LLL Hermite normal form algorithm proposed by Mathew, to overcome the problem that we previously mentioned. Experimental result shows that the proposed algorithm can successfully solve some of the linear integer programs.