組合（最）優化問題是最優化問題的一類。最優化問題似乎自然地分成兩類：一類是連續變量的問題，另一類是離散變量的問題。具有離散變量的問題，我們稱它為組合的。在連續變量的問題里，一般地是求一組實數，或者一個函數；在組合問題里，是從一個無限集或者可數無限集里尋找一個對象——典型地是一個整數，一個集合，一個排列，或者一個圖。一般地，這兩類問題有相當不同的特色，并且求解它們的方法也是很不同的。
來源：《組合最優化算法和復雜性》，高教社，1988，C.H. Papadimitriou, K. Steiglitz （劉振宏，蔡茂誠 譯）
概念定義
組合優化（Combinatorial 最優化）問題的目標是從組合問題的可行解集中求出最優解，通?？擅枋鰹椋毫瞀?{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）；
最大團問題 等。
這些問題描述非常簡單，并且有很強的工程代表性，但最優化求解很困難，其主要原因是求解這些問題的算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現有計算機上實現，即所謂的“組合爆炸”。正是這些問題的代表性和復雜性激起了人們對組合優化理論與算法的研究興趣。
參考資料 >