整數規劃之對數新法及其運用

Abstract

整數規劃法經常被運用在管理及工程科學領域上，因為其大型問題在數學規劃法上使用了大量的0-1變數，而造成在計算時間的困難。在目前的研究中，用於縮減0-1變數的對數整數規劃法已經被 Li et al. (2009) 及 Vielma and Nemhauser (2009) 等學者提出來，其方法利用了大量額外的不等式做為輔助，使得原本需要$N$ 個0-1變數的整數規劃問題縮減至$\left\lceil {{\log }_{2}}N \right\rceil$個。無論如何，這些方法仍然還有改善的空間，例如：過多不等式的問題。因此，本研究提出一個對數新法用於處理大型的整數規劃問題。本研究方法使得整數規劃模型更具精巧，而且嘗試用來處理下列的實際問題： (1)任務配置問題、(2)逐段線性法問題、(3)分類法問題及(4)投資組合問題。經處理這些實際的整數規劃問題得知，本研究所提出的方法更是優於目前的對數法

The mixed integer programming (MIP) problem occurs frequently in management and engineering science. Since a large MIP problem involves many binary variables, it is hard to find its exact solution in a reasonable computation time. Recently, some logarithmic MIP methods (Li et al. 2009; Vielma and Nemhauser 2009) have been developed; which reformulated MIP problems by adding some inequalities to reduce the number of binary variables from $N$ to $\left\lceil {{\log }_{2}}N \right\rceil$. However, these current methods can still be improved to compress the constraints set. This paper therefore proposes a novel logarithmic method to solve large scale MIP problems. Theoretically, the proposed method is substantially compacter than the current methods. The proposed method has been used to solve following applications: (1) Task assignment problems, (2) Piecewise linearization problems, (3) Classification problems and (4) portfolio selection problem. All these applications demonstrate that the proposed method is much faster than the current logarithmic methods for solving the practical MIP problems.