以組合0-1法求解非線性整數規劃問題

Abstract

非線性整數規劃問題普遍存在於許多工業工程與管理中。使用傳統方法線性化一整數函 數 f ( x)，x {1,...,m}， 需要使用m個 0-1 變數。本研究擬提出一組合 0-1 法線性化 f ( x)，僅需 2 log m個零一變數及額外 4 m   個連續變數。本研究可利用此法求解相關非 線性規劃問題，其中函數可表示為 f ( x) , xy 或 xyz ( x, y, z  )。初步的數值實驗結 果顯示所提出的組合0-1 法比傳統方法求解時間更為快速且保證找到最佳解，特別是問 題中的m值越大效果愈顯著。

Using current methods to linearize a nonlinear integer function f ( x) , x {1,...,m}, needs to use m binary variables. This study proposes a hybrid binary method to linearize f ( x) which needs only 2 log m binary variables and additional 4 m   continuous variables. We apply this method to solve the nonlinear integer programs containing f ( x) , xy or xyz where x, y, z  . Numerical experiments demonstrate that the proposed method is much faster than the current methods for finding the exact solution, especially for large m value.