整數規劃之高效率求解方法及其運用

Abstract

許多非線性問題需要逐段線性技術(Piecewise Linearization)將原始問題線性化以求得全域最佳解，而這過程需要加入許多二進位變數。近四十年來發展許多逐段線性之技術，而本研究就是發展出一套二進位變數的超級展現法(SRB)以便降低逐段線性技術所需之二進位變數其限制式。當一個擁有m+1個中斷點的線性化函數時，現有之逐段線性技術必須用m個二進位變數及4m個限制式，而本研究提出之方法只需log_2 m 個二進位變數及8+8*(log_2 m) 個限制式。同時本研究也展現數個實際問題之應用以證明它的高效率。