混合整數規劃轉換成非線性規劃方法研究

A methodology for converting mixed integer programming to nonlinear programming

黃鈺馨(Yu-Hsin Huang)

指導教授 ： 洪宗乾

國立屏東科技大學/管理學院/工業管理系所/碩士(2013年)

https://doi.org/10.6346/NPUST.2013.00186

摘要

許多工程類或管理類的最佳化問題其決策變數都包含了整數變數及連續變數兩種，這類最佳化問題被稱為混合整數規劃問題。除了一些有特殊解法的混合整數規劃問題外，大部分的求解過程都是複雜性高且耗時(NP-hard問題)，為了讓求解混合整數規劃問題能有更多有效率的求解方法可以使用，本論文跳脫了以前直接對混合整數規劃問題求解的方式，開發了一套將混合整數規劃問題轉換成相等非線性規劃或線性規劃問題的方法(在非線性規劃問題中只包含連續變數)。經轉換成非線性規劃或線性規劃問題後，求解非線性規劃或線性規劃問題的許多著名且有效率的技術也成了逼近混合整數規劃問題最佳解的選項，而且在非線性規劃或線性規劃的可行解空間為一連續空間時將有較多的資訊來逼近或搜尋最佳解(例如：方向導數等)。本論文除了詳述混合整數規劃問題轉換成非線性規劃問題的過程外，也提供兩個例子來介紹轉換的過程並同時呈現轉換成非線性規劃問題後如何有效的簡化原有的問題及求解程序，並經由實驗一個典型的機械設計問題，顯示此轉換方法所執行的結果較其他四個解決混合整數規劃問題的方法好。

關鍵字

混合整數規劃 ； 非線性規劃 ； 多項式最佳化

並列摘要

A mixed integer programming problem is an optimization problem including both integer decision variables and continuous variables. Many optimization problems in the field of engineering and management are mixed integer programming problems. However, solving a mixed integer programming problem often takes time and is complicated. For including more efficient techniques to solve mixed integer programming problems, this research develops a method for converting a mixed integer programming problem to an equivalent nonlinear programming problem or a linear programming problem. Through this methodology, these well developed tools for solving nonlinear programming problems or linear programming problems also can be used to approach the optimal solutions of mixed integer programming problems. In addition, the feasible solution set of a nonlinear programming, a continuous space, contains more useful information to approach the optimal solution (i.e., the directional derivative) than the one of a mixed integer programming problem, a discrete space. Finally, this research provides two examples to show the converting procedures and, meanwhile, to demonstrate the possible advantage from converting a mixed integer programming problem to a nonlinear programming problem or a linear programming problem. Then, the conversion methodology combines a nonlinear programming solver, the differential evolutionary algorithm, to solve a mechanical design problem. The result shows that our solution is better than other four published mixed integer programming solvers.

並列關鍵字

mixed integer programming ； nonlinear programming ； polynomial optimization

參考文獻

2. 林豐澤，「演化式計算上篇：演化式演算法的三種理論模式」，智慧科技與應用統計學報，民國94年，第3卷第1期，第1-28頁。

3. 楊曜榮，「以蟻群演算法動態選擇最佳供應商」，興國學報，民國99年，第12期，第41-54頁。

4. 廖麗滿、黃敬仁、林志諭，「穩健多目標基因演算法應用於流程型工廠之排程研究」，技術學刊，民國100年，第26卷第1期，第65-71頁。 

5. Bazaraa, M. S., Sherali, H. D. and Shetty, C. M. (3rd Edition) (2006). Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, New York.

6. Bishop, E. (1961). A generalization of the Stone-Weierstrass theorem. Pacific J. Math, 11 (3): 777-783.