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中的约束整数优化

回答

相关问题