CPLEX出現(xiàn)'q1' is not convex？
不知道大家在寫CPLEX的時候遇到過這個問題沒有？
其實有過經(jīng)驗的小伙伴都知道該怎么處理了，但是小編決定還是寫一下避免剛?cè)胄械男』锇閭儾瓤印?/p>
這個錯誤呢查了ibm knowledge center顯示如下：
里面講了一堆想必大家也懶得去看了，我來講講這類問題的解決方案吧~出現(xiàn)這個錯誤的原因不是編程上的問題，而是建模方式上的問題。簡單來說就是目標函數(shù)或者約束上出現(xiàn)了非線性的數(shù)學表達式。
那么什么是線性和非線性呢？我這里引一下百度知道上一個非常通俗易懂的解釋：
兩個變量之間的關(guān)系是一次函數(shù)關(guān)系的——圖象是直線，這樣的兩個變量之間的關(guān)系就zhi是“線性關(guān)系”；如果不是一次函數(shù)關(guān)系的——圖象不是直線，就是“非線性關(guān)系”。比如說y=kx 就是線形的 而y=x^2就是非線形的線形的圖形一般是一條直線。?
?
“非線性”的意思就是“所得非所望”。一個線性關(guān)系中的量是成比例的：十枚橘子的價錢是一枚的十倍。非線性意味著批發(fā)價格是不成比例的：一大箱橘子的價錢比一枚的價錢乘以橘子的個數(shù)要少。這里重要的觀念是“反饋”——折扣的大小反過來又影響顧客購買的數(shù)量。
也就是說你的模型中很可能出現(xiàn)了多個變量相乘的情況，例如下面這種情景：
要解決這個問題，首先就得想你的模型給linearlized了。而最常用的做法就是“大M”法了，通過增加一個充分大的數(shù)，將多個相乘的變量給拆開，從而達到線性化的目的。
不過像上圖那種情況就非常麻煩（其實是我建模建錯了），今天就先不討論。舉個簡單的例子，VRP的arc-flow模型中貨物流常見的約束如下：
其中和為決策變量，表示車輛離開客戶以后的載重量，而為1表示車輛走過邊()，否則為0。這條約束的含義是非常明了的，如果車輛經(jīng)過邊()，那么該車輛離開客戶的載重量必須大于等于車輛離開客戶的載重量加上客戶的需求量，這是貨物流平衡。
可以看到不等式右邊出現(xiàn)了變量和變量相乘的情況，這就造成了我們剛剛說的“非線性”問題，那么這個模型放進cplex中肯定會報“not convex”的錯誤。為了讓cplex能求解該模型，我們需要將非線性的約束轉(zhuǎn)成線性的。
常見的一個辦法是引入一個充分大的數(shù)，我們都喜歡叫它大M。當然這個數(shù)具體要多大，是不是越大越好，也不一定，后面我再講。
先觀察約束(8)右端的式子，發(fā)現(xiàn)只有當為1時，才需要，當為0時，就無所謂了。這是一個非常明顯的if else約束。因此可以考慮將提取出來，和一個大M相乘：
我們現(xiàn)在來檢驗上面這個約束含義是否和之前的保持一致。首先當為1時，,約束變成，這個沒問題。然后當為0時，，這個約束就被松弛掉了，也就是說取其定義域內(nèi)任意值都能滿足，也和之前的保持一致。
這樣，我們就將兩個相乘的變量通過一個大M將其拆開了。將其他非線性約束改成非線性約束，就能放進CPLEX跑了。當然了，小編才疏學淺，目前只知道這種方法，不過已經(jīng)夠小編用了，就沒繼續(xù)往下深究。關(guān)于大M法將if else類的約束線性化，我這里貼一個知乎上的回答：
如果有多個變量相乘，那可能就得引入多個大M。不過呢，到這里還沒有結(jié)束。下面我們聊聊關(guān)于大M的取值與CPLEX的精度可能造成的BUG。這種BUG是非常可怕的，如果不了解這一點，可能要走很多很多彎路哦，而且書本上才不會告訴你這些。
還是下面這條式子：
關(guān)鍵就在于CPLEX可能會存在精度損失，比如為0-1的決策變量有可能求解之后是這樣的：
也就是說當或者當，本應該為0的此刻都不是0了。那么這就很有可能造成約束失效，從而使模型無法滿足所有約束。
不過注意，我上面說的是有可能造成約束失效，而非一定。和，它們和1相差的值都在小數(shù)點的后九位。也就是說當M設(shè)置得足夠大的時候（比如），也會足夠大，大到影響約束原本的作用。而當M不那么大的時候（比如），也是小數(shù)點后4位，對原約束可以認為是沒有影響的。
當然這個沒有影響是相對于和而言，因為他們要求為整數(shù)并且大于等于0，就相當于你有1000萬，那么丟幾塊錢對你來說除了有點小小的不爽以外，基本上也是沒影響的。
那么M取什么值比較合適呢，這就需要大家去做一個簡單的bound了，簡單判斷下影響約束的一個upper bound或者lower bound，只需要大致估算一個值即可。比如上面那個貨物流平衡，可以取，其中為車輛的容量。
好了，以上就是今天分享的內(nèi)容了。可以關(guān)注我們，不定時分享一下小編踩過的雷，這樣你就不會在漫漫科研路上踩到相同的雷啦。
來都來了，不點個在看嗎？
