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

A Novel Logarithmic Method for Integer Programs and Its Applications

黃曜輝(Yao-Huei Huang)

指導教授 ： 黎漢林

國立交通大學/管理學院/資訊管理研究所/博士(2011年)

https://doi.org/10.6842/NCTU.2011.00978

摘要

整數規劃法經常被運用在管理及工程科學領域上，因為其大型問題在數學規劃法上使用了大量的0-1變數，而造成在計算時間的困難。在目前的研究中，用於縮減0-1變數的對數整數規劃法已經被 Li et al. (2009) 及 Vielma and Nemhauser (2009) 等學者提出來，其方法利用了大量額外的不等式做為輔助，使得原本需要$N$ 個0-1變數的整數規劃問題縮減至$leftlceil {{log }_{2}}N
ight
ceil$個。無論如何，這些方法仍然還有改善的空間，例如：過多不等式的問題。因此，本研究提出一個對數新法用於處理大型的整數規劃問題。本研究方法使得整數規劃模型更具精巧，而且嘗試用來處理下列的實際問題： (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 $leftlceil {{log }_{2}}N
ight
ceil$. 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.

並列關鍵字

Mixed integer programming ； Logarithmic method

參考文獻

[2] Aja-Fernandez, S., de Luis-Garcia, R., Martin-Fernandez, M.A., & Alberola-Lopez, C. 2004. A computational TW3 classifier for skeletal maturity assessment-a computing with words approach, Journal of Biomedical Informatics 37(2), 99-107.

[4] Babayev, D.A. 1997. Piece-wise linear approximation of functions of two variables. Journal of Heuristics 2, 313-320.

[5] Bazaraa, M.S., Sherali, H.D., & Shetty, C.M. 1993. Nonlinear Programming: Theory and Algorithms, 2e. Wiley, New York.

[6] Beale, E.M.L., & Forrest, J.J.H. 1976. Global Optimization Using Special Ordered Sets. Mathematical Programming 10(1), 52-69.

[8] Beynon, M.J., & Buchanan, K.L. (2003). An illustration of variable precision rough set theory: The gender classification of the European barn swallow (Hirundo rustica), Bulletin of mathematical biology 65(5), 835-858.