《組合最佳化問題的組合：問題、算法和複雜性》是依託清華大學，由王振波擔任項目負責人的面上項目。
基本介紹
- 中文名：組合最佳化問題的組合：問題、算法和複雜性
- 依託單位：清華大學
- 項目負責人：王振波
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
一些經典的組合最佳化問題，如排序問題、網路流問題、網路設計問題、背包問題、裝箱問題、最大割問題等，傳統上都是作為相對獨立的方向而被深入地研究，而實際遇到的問題往往會涉及到多個不同的組合最佳化問題。本項目研究兩個組合最佳化問題的組合，其中一個組合最佳化問題提供約束條件，而另一個組合最佳化問題決定最終最佳化的目標。組合最佳化問題的組合基於一些的經典組合最佳化問題，但又具有全新的結構，在問題、算法和複雜性等方面都蘊含著豐富的研究內容，而在文獻中卻很少相關的研究。本項目的研究將一些彼此獨立的經典最佳化問題有機地聯接在一起，擴大了組合最佳化領域的研究範圍。本項目的研究包含三個主要方面：1. 根據理論和套用的需要，建立不同的最佳化問題的組合模型；2. 通過探索各個最佳化問題的方法和理論之間的聯繫，發現相應的組合問題所具有的內在性質，並建立相應的理論；3.分析組合問題的計算複雜性並設計有效的算法。
結題摘要
本項目研究兩個組合最佳化問題的組合，其中一個組合最佳化問題提供約束條件，而另一個組合最佳化問題決定最終最佳化的目標。組合最佳化問題的組合基於一些的經典組合最佳化問題，但又具有全新的結構，在問題、算法和複雜性等方面都蘊含著豐富的研究內容，而在文獻中卻很少相關的研究。本項目的研究將一些彼此獨立的經典最佳化問題有機地聯接在一起，擴大了組合最佳化領域的研究範圍。本項目的研究成果包含：1. 對於平行機和覆蓋問題的組合問題，我們給出了組合最佳化問題組合的一個統一框架，設計並分析了多個近似算法；2. 研究流水車間排序問題和最短路問題的組合問題；3. 提出了平行機排序和線性規劃的組合問題。
