組合最佳化

組合（最）最佳化問題是最最佳化問題的一類。最最佳化問題似乎自然地分成兩類：一類是連續變數的問題，另一類是離散變數的問題。具有離散變數的問題，我們稱它為組合的。在連續變數的問題里，一般地是求一組實數，或者一個函式；在組合問題里，是從一個無限集或者可數無限集裡尋找一個對象——典型地是一個整數，一個集合，一個排列，或者一個圖。一般地，這兩類問題有相當不同的特色，並且求解它們的方法也是很不同的。 來源：《組合最最佳化算法和複雜性》，高等教育出版社，1988，C.H. Papadimitriou, K. Steiglitz （劉振宏，蔡茂誠 譯）

概念定義

組合最佳化（Combinatorial Optimization）問題的目標是從組合問題的可行解集中求出最優解，通常可描述為：令Ω={s1，s2，…，sn}為所有狀態構成的解空間，C(si)為狀態si對應的目標函式值，要求尋找最優解s*，使得對於所有的si∈Ω，有C(s*)=minC(si)。組合最佳化往往涉及排序、分類、篩選等問題，它是運籌學的一個重要分支。

問題分類

典型的組合最佳化問題有：

旅行商問題（Traveling Salesman Problem－TSP）；

加工調度問題（Scheduling Problem，如Flow-Shop，Job-Shop）；

0-1背包問題（Knapsack Problem）；

裝箱問題（Bin Packing Problem）；

圖著色問題（Graph Coloring Problem）；

聚類問題（Clustering Problem）；

最大團問題 等。

這些問題描述非常簡單，並且有很強的工程代表性，但最最佳化求解很困難，其主要原因是求解這些問題的算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現有計算機上實現，即所謂的“組合爆炸”。正是這些問題的代表性和複雜性激起了人們對組合最佳化理論與算法的研究興趣。