Python 中的约束整数优化

Question

我想最小化一个函数，该函数将 3x8 非负整数矩阵作为输入。每行指定一个变量，而每列指定系统中的某个时间点。请参阅下面的 CSV 格式输入。

   ,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 如何做到这一点吗？

Answer 1

对于较小的问题，AMPL 网站有一个免费工具：http://www.ampl.com/TRYAMPL/startup.html。要上传的 model 文件 (*.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;

由于您没有指定 objective 函数，所以我放入了一个线性虚拟对象。上传这两个文件后，您可以 select 解算器；不幸的是，我认为其中 none 是整数求解器，但有些是非线性的。这样你可能会找到一个下限，可行的整数解决方案，你可以通过一些舍入启发式从那里获得（不需要整数最优）。

或者：Excel求解器？

Python 中的约束整数优化

Constrained integer optimization in Python

python

optimization

integer

scipy