Python中的約束整數優化

我想最小化一個函數，它將一個3x8矩陣的非負整數作爲輸入。每行指定一個變量，而每列指定系統中的某個時間點。請參閱下面的CSV格式的輸入。Python中的約束整數優化

,Time0,Time1,Time2 
U_i,0,0,0 
U_o,0,0,0 
C_i,0,0,0 
C_o,0,0,0 
T_i,0,0,0 
T_o,0,0,0 
D_i,0,0,0 
D_o,0,0,0

每列的約束條件是：

C_i + T_i >= U_i 
C_o + T_o >= U_o 
D_i <= 15 
D_o <= 15 
D_i = 0 if C_i == 0 
D_o = 0 if C_o == 0

和整個行的整體約束C_i + C_o + T_i + T_o = 5。我看過scipy.optimize，但找不到處理整數的正確方法。有人可以給我一個提示或MWE如何做到這一點？

來源

2015-05-28 pir

你應該知道大多數整數規劃問題都是NP難題。而且，要被最小化的函數的形式很重要：如果它是線性的，它確實使問題更容易。 – cfh

函數的形式是非線性的，儘管我對此不太瞭解。你認爲這個問題很難得到一個好的近似解決方案嗎？對我來說，這似乎是一個相當低的參數/限制數量。 – pir

我不知道。您最好的選擇可能是獲得[Gurobi]（http://www.gurobi.com/resources/getting-started/mip-basics）或CPLEX的評估許可證，並簡單地查看它是否可行。單獨參數的數量並不是解決這些問題的最重要的決定因素。 – cfh

對於較小的問題，AMPL網站有一個免費工具：http://www.ampl.com/TRYAMPL/startup.html。模型文件（*的.mod）上傳將是：

set T; 

var U_i {T} >= 0 integer; 
var U_o {T} >= 0 integer; 
var C_i {T} >= 0 integer; 
var C_o {T} >= 0 integer; 
var T_i {T} >= 0 integer; 
var T_o {T} >= 0 integer; 
var D_i {T} >= 0 integer; 
var D_o {T} >= 0 integer; 

minimize obj: sum {t in T} (U_i[t] + U_o[t] + C_i[t] + C_o[t] + T_i[t] + T_o[t] + D_i[t] + D_o[t]); 
subject to C1 {t in T}: C_i[t] + T_i[t] >= U_i[t]; 
subject to C2 {t in T}: C_o[t] + T_o[t] >= U_o[t]; 
subject to C3 {t in T}: D_i[t] <= 15; 
subject to C4 {t in T}: D_o[t] <= 15; 
subject to C5 {t in T}: D_i[t] <= C_i[t]/1000; 
subject to C6 {t in T}: D_o[t] <= C_o[t]/1000; 
subject to C7 {t in T}: C_i[t] + C_o[t] + T_i[t] + T_o[t] = 5;

的數據文件（* .dat）：

set T := 1 2 3;

既然你沒有指定一個目標函數我把一個線性假人。上傳這兩個文件後，您可以選擇一個求解器;我認爲不幸的是，它們都不是一個整數求解器，但有些是非線性的。通過這種方式，您可能可以找到一個下界，可行的整數解決方案，您可以通過一些四捨五入的啓發式（不是必需的整數最優）從那裏獲得。

或者：Excel求解器？

來源

2015-06-29 18:56:31

Python中的約束整數優化

回答

相關問題