以對數變換法求解非線性背包問題

Abstract

非線性背包問題(NKP)是最佳化研究中的經典問題。本研究所解之NKP 問題為在n 個物件中選取m 個以極大化, , n i j k i j k i j k a x x x < < Σ ，其中i x 為0-1 變數，而i, j ,k a 為常數。以傳統方法求解此NKP 以求得全域最佳解等同於處理一包含n 個0-1 變數及O(n3 )個不等式的線性規劃問題。本研究提出一對數轉換法將原NKP 轉換為0-1 線性規劃問題，其中之0-1 變數及限制式數均為2 mlog n。由於減少了許多的0-1 變數及不等式因而大大提高計算效率，尤其當n 很大而m 相對小時。本研究為期二年，各期之重點如下：第一年： 回顧經典背包問題之解法，並提出對數轉換法理論第二年： 發展對數變換演算法，加速解題效率，並應用對數轉換法求解大尺度相關問題。

Solving a nonlinear knapsack problem of maximizing , , n i j k i j k i j k a x x x < < Σ , where 1 n i i x m = Σ = and i x are binary variables, by current methods is equivalent to solve a linear 0-1 program containing n binary variables and O(n3 ) linear inequalities. This study proposes a logarithmic method to convert the same problem into a linear 0-1 program with only 2 mlog n binary variables and 2 mlog n inequalities. The proposed method is expected to be more computationally efficient than current methods. This research project will last for two years: #1; The first year focuses on the literature review and theoretical propositions of the proposed method. #1; The second year focuses on testing the computational efficiency of our method, comparing with existing algorithms of nonlinear knapsack programs, and resolving practically large scale management and engineering problems.