整數(shù)規(guī)劃的歷史可以追溯到20世紀(jì)50年代,美國(guó)學(xué)者丹齊格（G.B. Dantzig）首次發(fā)現(xiàn)可以通過(guò)0-1變量來(lái)刻畫(huà)最優(yōu)化模型中的固定費(fèi)用、變量上界、非凸分片線性函數(shù)等.此后, 丹齊格等對(duì)旅行商問(wèn)題(traveling salesman problem,TSP)的研究,成為分支定界法和現(xiàn)代混合整數(shù)規(guī)劃算法的開(kāi)端. 1958年,戈莫里（R.E.Gomory）提出了求解一般整數(shù)線性規(guī)劃模型的收斂算法——割平面方法,至此整數(shù)規(guī)劃成為最優(yōu)化領(lǐng)域的一個(gè)獨(dú)立分支. ?

近年來(lái),隨著整數(shù)規(guī)劃理論和算法的不斷發(fā)展以及計(jì)算機(jī)計(jì)算速度和功能的迅猛提升,整數(shù)規(guī)劃已逐漸成為應(yīng)用最廣泛的最優(yōu)化方法之一,在社會(huì)、軍事、生物、計(jì)算機(jī)以及經(jīng)濟(jì)等各大領(lǐng)域得到了更廣泛的應(yīng)用和長(zhǎng)足的發(fā)展.?

模型和應(yīng)用角度?

整數(shù)規(guī)劃在實(shí)際應(yīng)用中十分廣泛, 很多優(yōu)化問(wèn)題都可以抽象為同一類(lèi)整數(shù)規(guī)劃模型. 如經(jīng)典的旅行商問(wèn)題、背包問(wèn)題 (knapsack problem)、切割下料 (cutting stock problem) 問(wèn)題等.?

其中研究最為廣泛的問(wèn)題為旅行商問(wèn)題, 其在運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)中扮演著非常重要的角色. 目前許多優(yōu)化方法都將其作為一個(gè)測(cè)試基準(zhǔn).?

旅行商問(wèn)題是指給定一系列城市和每對(duì)城市之間的距離, 求解訪問(wèn)每一座城市一次并回到起始城市的最短回路. 旅行商問(wèn)題最初應(yīng)用在交通運(yùn)輸領(lǐng)域, 例如飛機(jī)航線安排、郵件派送、快遞服務(wù)、校車(chē)行進(jìn)路線設(shè)計(jì)等. 隨著時(shí)間的推移, 其應(yīng)用范圍擴(kuò)展到了許多其他領(lǐng)域, 例如電路板印制、晶體結(jié)構(gòu)分析、數(shù)據(jù)串聚類(lèi)等.?

整數(shù)規(guī)劃在背包問(wèn)題方面的研究最早可追溯到1897 年, 至今已經(jīng)延續(xù)了一 個(gè)多世紀(jì). 其問(wèn)題可以描述為：給定一組物品, 每種物品都有自己的重量和價(jià)值, 如何選擇物品才能在限定總重量?jī)?nèi)使得背包內(nèi)物品的總價(jià)值最高.

自從背包問(wèn)題被提出之后, 眾多學(xué)者對(duì)其進(jìn)行了深入細(xì)致的研究和拓展, 關(guān)于背包問(wèn)題理論的文獻(xiàn)和研究也是不計(jì)其數(shù). 同時(shí), 背包問(wèn)題在現(xiàn)實(shí)中也有著廣泛的應(yīng)用, 很多實(shí)際問(wèn)題都被抽象為背包問(wèn)題, 例如股市投資、國(guó)家預(yù)算、資源分配、工業(yè)生產(chǎn)和運(yùn)輸?shù)? 因此, 背包問(wèn)題也是組合優(yōu)化領(lǐng)域中重要的基石之一.?

?

切割下料問(wèn)題是整數(shù)規(guī)劃在生產(chǎn)領(lǐng)域中最經(jīng)典的應(yīng)用之一. 其問(wèn)題可以描述 為：給定一組原材料, 如何通過(guò)切割、剪裁、沖壓等手段, 按照工藝要求將原材料加工成規(guī)定大小的成材, 從而使所用材料最少或利潤(rùn)最大.

此外, 隨著越來(lái)越多的復(fù)雜系統(tǒng)使用數(shù)學(xué)框架建模, 集劃分問(wèn)題 (set partition problem)、選址問(wèn)題 (facility location problem)、網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題 (network design problem) 等一系列整數(shù)規(guī)劃問(wèn)題都廣泛應(yīng)用于生產(chǎn)以及生活的方方面面, 未來(lái)將會(huì)有更多的整數(shù)規(guī)劃應(yīng)用模型被發(fā)掘.?

目前, 整數(shù)規(guī)劃應(yīng)用研究的總體發(fā)展趨勢(shì)主要有兩個(gè)方面：?

• 整數(shù)規(guī)劃與管理科學(xué)、網(wǎng)絡(luò)科學(xué)、生命科學(xué)、服務(wù)科學(xué)等學(xué)科的交叉融合日益增強(qiáng);

• 現(xiàn)有算法往往還不能解決交通規(guī)劃、生產(chǎn)調(diào)度、通信、金融投資等領(lǐng)域中出現(xiàn)的大規(guī)?；旌险麛?shù)規(guī)劃模型, 因此整數(shù)規(guī)劃研究正朝著大規(guī)?；旌险麛?shù)規(guī)劃模型的算法設(shè)計(jì)方向發(fā)展.?

  
  

模型求解角度

由于整數(shù)約束使得整數(shù)規(guī)劃模型變得難以求解, 目前整數(shù)規(guī)劃模型求解算法的效率通常比不上求解線性規(guī)劃模型的單純形法.?

影響求解算法計(jì)算時(shí)間的最大因素是整數(shù)變量的數(shù)目, 以及問(wèn)題是否具有容易處理的特殊結(jié)構(gòu).?

在整數(shù)變量數(shù)目一定時(shí), 0-1整數(shù)規(guī)劃模型通常比一般整數(shù)規(guī)劃模型更容易求解. 針對(duì)具有特殊結(jié)構(gòu)的大規(guī)模0-1 整數(shù)規(guī)劃模型, 采用特殊的算法求解通常更加容易; 而不具有特殊結(jié)構(gòu)的問(wèn)題, 即使整數(shù)變量數(shù)目較少也難以求解.?

此外, 基于實(shí)際問(wèn)題建立的整數(shù)規(guī)劃模型通常含有不相關(guān)或冗余信息, 這些信息也會(huì)降低算法求解效率.?

自 20 世紀(jì) 50 年代以來(lái), 針對(duì)整數(shù)線性規(guī)劃的研究一直是整數(shù)規(guī)劃研究的核心內(nèi)容.?一般整數(shù)線性規(guī)劃模型的求解算法主要是基于分支定界的算法.

目前提高分支定界算法效率的主要途徑有兩個(gè)：

• 提高求解線性松弛模型的速度;?

• 利用割平面和有效不等式加快收斂速度.?

  
  

一方面, 分支定界算法需要求解許多可行域不斷縮小的線性規(guī)劃子問(wèn)題, 改進(jìn)的單純形算法(對(duì)偶單純形算法) 可以利用熱啟動(dòng)方法加速求解子問(wèn)題; 另一方面, 自從割平面方法被提出以來(lái), 基于不同問(wèn)題結(jié)構(gòu)性質(zhì)的有效不等式理論得到了很好發(fā)展.?

針對(duì)背包問(wèn)題、旅行商問(wèn)題和網(wǎng)絡(luò)流相關(guān)問(wèn)題等, 通過(guò)許多簡(jiǎn)單或復(fù)雜的強(qiáng)有效不等式以及結(jié)合這些有效不等式的分支切割方法, 大大提高了分支定界算法的速度和效率. 針對(duì)具有特殊結(jié)構(gòu)的大規(guī)模問(wèn)題, 如具有分塊結(jié)構(gòu)的大規(guī)模整數(shù)線性規(guī)劃模型, Dantzig-Wolfe 分解和 Benders 分解 (本德?tīng)査狗纸? 是有效的分解方法, 列生成和 Benders 分解算法分別是求解相應(yīng)分解模型的高效算法策略.?

20 世紀(jì)中期, 迫于實(shí)際需求, 能夠快速求解整數(shù)規(guī)劃模型的啟發(fā)式算法應(yīng)運(yùn)而生. 伴隨近年來(lái)計(jì)算機(jī)技術(shù)的發(fā)展, 如禁忌搜索算法 (tabu search algorithm)、模擬退火算法 (simulated annealing?algorithm)、遺傳算法 (genetic algorithm) 等啟發(fā)式算法取得了巨大的成功.?

不同于整數(shù)線性規(guī)劃, 對(duì)于整數(shù)非線性規(guī)劃的研究始于 20 世紀(jì) 80 年代, 兩者無(wú)論從理論的系統(tǒng)性還是算法的有效性上都有很大的差距. 整數(shù)非線性規(guī)劃的 研究策略和途徑往往依賴于問(wèn)題的特殊結(jié)構(gòu)和性質(zhì), 一些求解整數(shù)線性規(guī)劃模型的基本方法 (例如分支定界法、動(dòng)態(tài)規(guī)劃和 0-1 隱枚舉法, 其中最常用的是分支定界法) 也可以被用于求解整數(shù)非線性規(guī)劃模型.?

20 世紀(jì) 90 年代, 半定規(guī)劃內(nèi)點(diǎn)算法的提出給二次 0-1 整數(shù)規(guī)劃的研究提供了有力的工具, 給該領(lǐng)域注入了新的活力. 針對(duì)最大割問(wèn)題、二次指派問(wèn)題和其他特殊二次 0-1 整數(shù)規(guī)劃問(wèn)題, 半定規(guī)劃松弛和隨機(jī)化算法取得了巨大的成功. 本質(zhì)上, 整數(shù)規(guī)劃只能使用隱枚舉法或枚舉法的思想來(lái)求解問(wèn)題的最優(yōu)解. 隨著問(wèn)題規(guī)模的擴(kuò)大, 算法的計(jì)算時(shí)間也迅猛增加, 而最簡(jiǎn)單的連續(xù)優(yōu)化問(wèn)題的 可行解也可以達(dá)到無(wú)窮多個(gè). 盡管存在理論上的困難性, 應(yīng)用領(lǐng)域?qū)φ麛?shù)規(guī)劃的需求還是推動(dòng)它不斷前進(jìn)和發(fā)展.?

近年來(lái), 隨著整數(shù)規(guī)劃算法技術(shù)和商業(yè)求解軟件的發(fā)展和推廣, 許多原來(lái)不能解決的大規(guī)模整數(shù)規(guī)劃模型, 都可以在合理的時(shí)間內(nèi)使用新算法以及更快速的計(jì)算機(jī)來(lái)解決. 然而, 由于對(duì)整數(shù)規(guī)劃模型認(rèn)識(shí)的不足和數(shù)學(xué)工具的局限, 許多整數(shù)規(guī)劃模型仍不能得到很好的求解，亟需針對(duì)具體的整數(shù)規(guī)劃模型設(shè)計(jì)高效算法.?

——以上內(nèi)容摘自由殷允強(qiáng)、王杜娟、余玉剛主編的《整數(shù)規(guī)劃：基礎(chǔ)、擴(kuò)展及應(yīng)用》

內(nèi)容簡(jiǎn)介

? ??本書(shū)主要聚焦于大規(guī)模整數(shù)規(guī)劃模型的求解方法和策略, 深入淺出地闡明了求解大規(guī)模整數(shù)規(guī)劃模型主流方法的基本思想、原理、執(zhí)行步驟以及在實(shí)際問(wèn)題中的應(yīng)用, 共分為引言、整數(shù)規(guī)劃建模、線性規(guī)劃、精確離散優(yōu)化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders 分解算法和啟發(fā)式算法九章. 每種算法和分析都注重結(jié)合問(wèn)題實(shí)際, 加入眾多現(xiàn)實(shí)案例, 并配有相應(yīng)習(xí)題. 書(shū)中還附有相關(guān)閱讀材料, 以便有興趣的讀者進(jìn)一步鉆研探索.

? ? 作為一本研究性與教學(xué)性并重的專業(yè)教材, 本書(shū)既可以作為高等院校經(jīng)濟(jì)管理類(lèi)和理工類(lèi)等專業(yè)本科生、研究生的必修教材, 又可作為研究人員、專業(yè)人員的自學(xué)及參考用書(shū).

本書(shū)特色

? ?

??? 與已有教材相比, 本書(shū)主要聚焦于大規(guī)模整數(shù)規(guī)劃模型的求解方法和策略, 深入淺出地闡明了求解大規(guī)模整數(shù)規(guī)劃模型主流方法的基本思想、原理、執(zhí)行步驟以及在實(shí)際問(wèn)題中的應(yīng)用. 每種算法和分析都注重結(jié)合問(wèn)題實(shí)際, 加入眾多現(xiàn)實(shí)案例, 并配有相應(yīng)習(xí)題, 符合 “新工科” 人才培養(yǎng)的理念與要求, 是一部新穎且具有較強(qiáng)實(shí)踐指導(dǎo)性的教材. 書(shū)中還附有相關(guān)閱讀材料, 以便有興趣的讀者進(jìn)一步鉆研探索.

? ? ?