DiscreteOptimization課程筆記(4)—前沿與工具-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)建站是一家專業(yè)提供蒙城企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站建設(shè)、HTML5、小程序制作等業(yè)務(wù)。10年已為蒙城眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計公司優(yōu)惠進行中。

1.大規(guī)模鄰域搜索(Large Neighborhood Search)

Case1: 帶時間窗的非對稱TSP(Asymmetric TSP with Time Windows)

2.列生成算法(Column Generation)

Case2:?Cutting Stock

3.優(yōu)化工具匯總

1.大規(guī)模鄰域搜索(Large Neighborhood Search)

大規(guī)模鄰域搜索是局部搜索和CP/MIP的結(jié)合，例如CP和局部搜索結(jié)合：

從一個可行解開始(CP)
選擇鄰域(LS)
優(yōu)化鄰域(CP)
重復(fù)第二步

局部搜索能解決大規(guī)模問題，而約束規(guī)劃適合找到一個可行解和優(yōu)化小規(guī)模的組合空間，將兩者結(jié)合，用約束規(guī)劃來優(yōu)化每一次局部搜索的大規(guī)模鄰域從而找到最佳的某個鄰域解。如何找到大規(guī)模鄰域？可以固定某些變量子集的取值，只改變其它變量生成鄰域，這個子集的確定依賴于問題的結(jié)構(gòu)。

Case1: 帶時間窗的非對稱TSP(Asymmetric TSP with Time Windows)

有一些需要到達的地方，每個位置有一個服務(wù)時間，其到達時間也有一個時間窗限制，某些位置之間的距離可能非對稱，要求找到哈密爾頓回路，能滿足時間窗要求并且最小化總距離。在CP模型中，增加每個activity開始和結(jié)束時間約束，用調(diào)度表可以表示如右圖，橫段代表時間窗，用LNS求解ATSPTW，則先固定某些點的位置，更改其它點的位置生成大規(guī)模的鄰域，這些點可以是一起的，也可以是隨機的。通過TSP benchmark，和branch cuts算法相比，LNS能更短時間內(nèi)找到差不多解。

2.列生成算法(Column Generation)

總結(jié)MIP算法，以下均基于線性松弛

branch and bound：分支定界
cutting plane：割平面法
branch and cuts：分支割平面，BB+cut，按需在節(jié)點處對線性松弛切割
branch and price：分支定價，BB+列生成(CG)，在節(jié)點生成列獲得增強松弛

接下來通過Cutting Stock問題介紹列生成算法，該問題是由Gilmore and Gomory提出，Gomory提出了割平面算法中的Gomory切割

先回顧一下Reduced Cost 和?Dual Variables，根據(jù)LP的矩陣表示推導(dǎo)，目標(biāo)函數(shù) $cx=c_{B}^{T}B^{-1}b+(c_{N}^{T}-c_{B}^{T}B^{-1}N)x_{N}$ ，其中 $c_{N}^{T}-c_{B}^{T}B^{-1}N$ 稱為Reduced Cost，如果存在某個非基變量Xn使其對應(yīng)的Reduced Cost<0，那么增加Xn的值就能使目標(biāo)值再降低，表明還有優(yōu)化空間，因此找到的解能實現(xiàn)Reduced Cost>=0時，證明找到了最優(yōu)解

假設(shè)原問題最優(yōu)解為 $[x_{B},0]$ ，如下圖推導(dǎo)可知 $c_{B}^{T}B^{-1}$ 為對偶問題最優(yōu)解，因此可以得到Reduced Cost與對偶變量的關(guān)系， $reduced cost=c_{N}^{T}-c_{B}^{T}B^{-1}N=c_{N}^{T}-dual*N$

Case2:?Cutting Stock

假設(shè)需要長度為3,7,9,16米的鋼管各25,30,14,8根,目前只有長度為20米的鋼管若干，請安排合理地切割方案，使得消耗的鋼管數(shù)量最少。有兩種建模思路

常規(guī)思路：0/1變量表示為是否使用某根鋼管，這種建模存在對稱問題，線性松弛解不好
列生成思路：不考慮是否選擇某根鋼管，而是決定某種切割模式(configuration)使用次數(shù)，這樣建模沒有容量約束，也沒有決策變量對稱性問題

切割組合有很多，不可能一次性枚舉所有的組合集合，也沒有必要，因此有些切割模式可能用不到，那么如何找到好的切割模式？?

用列生成求解cutting stock problem?

（1）首先給定初始的切割模式，求解模型得到對偶變量取值 $\lambda _{i}$

（2）加入新的切割模式 $p_{new}$ 能優(yōu)化目標(biāo)函數(shù)值，說明變量 $z_{new}$ 的reduced cost<0，即 $reduced cost=c_{n}^{T}-c_{B}^{T}B^{-1}n=c_{n}^{T}-dual*n$ ，在本問題中， $c_{n}^{T}=1$ ，dual取值為前面的 $\lambda _{i}$ ，n為變量 $z_{new}$ 的系數(shù)矩陣，也就是新切割模式每種長度的數(shù)量，因此 $reduced cost=1-\sum \lambda _{i}c_{ipnew}<0$ ，選擇reduced cost最小的切割模式加入集合中

（3）重新構(gòu)造一個子問題，找到reduced cost最小的組合，同時滿足長度約束，大程度優(yōu)化目標(biāo)值

綜上可知，列生成的思路：和沒有加入新切割的模型相比，可以看做 $z_{pnew}=0$ ，因此即便在約束中沒有體現(xiàn)也無關(guān)，通過子問題找到reduced cost最小的切割組合，重新優(yōu)化模型，完整的實例求解過程如下：?

3.優(yōu)化工具匯總

Constraint Programming Solvers	CHOCO - java庫，開源 Gecode - c++，免費 ILog - binary，使用學(xué)術(shù)許可證免費 JACOP - java，開源 MiniZinc / G12 - binary，學(xué)生免費 or-tools - C++，開源，APIs - Java，Python和.NET
Mixed Integer Programming Solvers	BCP - c++，開源 CBC - c++，開源 CPlex - binary，使用學(xué)術(shù)許可證免費 GLPK - c，開源 gurobi - binary，使用學(xué)術(shù)許可證免費 LPSolve - c，開源 SCIP - binary，使用學(xué)術(shù)許可證免費
Linear Programming Solvers	CLP - c++，開源 SimplexSolver - java，開源
Local Search Solvers	Local Solver - binary，使用學(xué)術(shù)許可證免費 OptaPlanner - java，開源
SAT Solvers	cryptominisat - c++，開源 Glucose - c，開源 Lingeling - c，開源 MiniSat - binary，開源 UBCSAT - c，開源
Hybrid Solvers	SCIP - binary，學(xué)術(shù)使用免費

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：DiscreteOptimization課程筆記(4)—前沿與工具-創(chuàng)新互聯(lián)
文章鏈接：http://weahome.cn/article/doiphh.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

DiscreteOptimization課程筆記(4)—前沿與工具-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管