組合最優化（Combinatorial Optimization）是應用數學的一個領域，融合了組合數學、線性規劃和演算法理論中的方法。它一般被應用於解決離散結構（Discrete Structure）中的最優化問題。在組合最優化問題中，我們想要在有限的可行方案中找到最佳的組合方案，這樣的最優解可以用圖像或者表格的形式，具體地表現出來。但是，組合優化問題的難點通常在於，可行方案的數量過於龐大，簡單粗暴的枚舉法通常不適用。整數規劃（Integer Programming）是其中一個行之有效的方法，它通過建立含有整數變數的數學模型來描述並解決組合問題。當然，整數規劃問題的解決難度遠遠在線性規劃（Linear Programming）之上，直接用優化解算器（Optimization Solver）來解決並不容易，所以在整數規劃問題上，我們也需要尋求更有效率的方法。

本篇文章作為導論，將介紹幾個組合與整數優化領域比較經典的實際問題，帶領讀者對組合優化問題有一個具體的認識。

  • 揹包問題 Knapsack Problem
  • 旅行商問題 Traveling Salesman Problem
  • 分配問題 Assignment Problem

揹包問題 Knapsack Problem

揹包問題（Knapsack problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定揹包中。—— [Wikipedia]

一個具體的例子：假設一個遊客到某地觀光，他只背了一個最大承重為3kg的揹包，準備在當地的市場買一些特產回家後在自己的店內轉賣，他需要在10樣特產裏做選擇，以求轉賣後的利潤最大化。特產信息如下：

由於每件特產的利潤都是正的，我們希望可以買回所有的特產，但是10件特產的總重量為7.1kg，遠遠超過了揹包的3kg容量；單買任意一件特產則揹包內仍有剩餘空間可用。所以我們的最佳特產採購方案是在所有都買和只買一件的兩個極端情況中間。如何確定最佳方案呢？

最直接的方法是列舉出所有的可行方案，比較它們的利潤大小，在其中選擇最優。假設我們買與不買一件特產的決定都是互相獨立的，那麼我們一共有 2^{10}=1024 種可能的方案。如果我們使用枚舉法，列舉出1024種方案，剔除其中總重量超過3kg的方案，在剩下的方案中選擇利潤最大的一個，就可以得到最優解。但是，這樣簡單的計算和篩選仍然有一定的成本，並且隨著特產數量的增加，總方案的數量也成爆炸式的指數增長，如果我們用枚舉法從50種特產中進行選擇，就需要分析 2^{50}≈1.13×10^{15} 種可能方案。顯然，我們需要尋找更加高效的方法來解決揹包問題。

假設每件特產的重量為 w_i ，每件特產對應的利潤為 p_i ，對於每一件特產而言，我們要做的判斷是：買或不買，這是一個二選一的決定，所以我們可以引入一個二元變數（Binary Variable） x_i，i=1,...,10 ，用數學的方式描述這個決定：small x_i =egin{cases} 0, & ext{不買特產i}\ 1, & ext{買特產i} end{cases}

尋找最佳特產購買方案，以及與此類似的問題可用一個最優化問題表示，例如：

maximize sum_{i=1}^{10} p_ix_i \ ext{subject to} sum_{i=1}^{10}w_ix_i le 3\ x_i in ext{{0,1}}, i = 1,...,10 \ w_i, p_i in mathbb{R}, i=1,...,10

這樣，我們只需要求解這個最優化問題，而不需要枚舉出所有可能方案再慢慢篩選。

旅行商問題 Traveling Salesman Problem

旅行推銷員問題（最短路徑問題）（英語：Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。它是組合優化中的一個NP困難問題，在運籌學和理論計算機科學中非常重要。 [Wikipedia]

旅行商問題是組合優化課題裏最重要的問題之一，它在物流貨運線路規劃等實際問題中具有非常大的實用意義。我們以歐幾裏得旅行商問題（Euclidean Traveling Salesman Problem）為例，假設有一個集合 V ，其中包括了歐幾裏得平面內所有的點，每個點都有一對 (x,y)坐標。我們知道，兩個坐標分別為 (x_1,y_1) 和 (x_2,y_2) 的點，它們之間的距離為 sqrt{(x_1-x_2)^2+(y_1-y_2)^2} ， 我們想要找到一條最短的迴路，通過集合 V 內的所有點 。

歐幾裏得旅行商問題：

根據歐幾裏得平面內所有點組成的點集 V ，找到一條經過平面內所有點並回到起始點的最短路徑。

假如我們針對這個問題採用枚舉法，即找到所有可能解，從中挑出最短路徑，這樣當然可以保證我們找到最優解。但是如果平面內共有 n 個點，|V|=n ，那麼一共有 (n?1)!/2 種不同的可能需要評估。很明顯，隨著平面內點的數量的增加，枚舉法的工作量也變得繁重，效率隨之降低。為解決歐幾裏得旅行商問題，一個更加高效的演算法——最近鄰居法（Nearest Neighbour Algorithm）被提出，但這個方法並不保證給出的是最優解。

The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. In it, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. It quickly yields a short tour, but usually not the optimal one. [Wikipedia]

這個演算法的基本原理是：在點集 V 中任意選擇一點作為起始點，將距離該點最近且沒有去過的一點作為下一站。重複這一過程直到所有的點被遍歷，而後回到起始點。

最近鄰居演算法（Nearest Neighbour Algorithm）

值得注意的是，雖然我們每一步都取了局部最優解（Locally Optimal），得到的解的整體效果可能很差：一是因為這種方法很容易漏掉某一點，並在後面的步驟花更大的成本來彌補；二是因為這種方法很有可能把路線「逼到角落」，這種情況下又需要一段很長的路徑才能達到下一個距離最近的點。這也是最近鄰居演算法的侷限性。

分配問題 Assignment Problem

分配問題是運籌學領域一個基礎的組合優化，它一般用來處理工人與工作、學生與課題的分配。每配一對都需要付出相應的成本，通常情況下是一對一不重複的。如何達成成本最小的分配計劃是研究的重點。

In its most general form, the problem is as follows:

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized. [Wikipedia]

這裡我們假設成本的計算和其它可能涉及的函數都是線性的。含有非線性項的分配問題要複雜得多。解決線性分配問題的方法可分為兩種：一種是探索問題結構的特殊演算法，比如狄傑斯特拉演算法（Dijkstra』s Alogirthm）等；另一種是構造一個數學模型再求解。以後會有文章詳細介紹這幾種方法和它們的區別。


推薦閱讀：
相關文章