为什么 MIP 对这个问题最好是无限的?
Why is MIP best bound infinite for this problem?
我有以下 MIP 问题。 pre_6_0
的上限不应是无限的,因为它是根据 inp1
、inp2
、inp3
和 inp4
计算得出的,所有这些都在两边都有界.
Maximize
obj: pre_6_0
Subject To
c1: inp0 >= -84
c2: inp0 <= 174
c3: inp1 >= -128
c4: inp1 <= 128
c5: inp2 >= -128
c6: inp2 <= 128
c7: inp3 >= -128
c8: inp3 <= 128
c9: inp4 >= -128
c10: inp4 <= 128
c11: pre_6_0 + 0.03125 inp1 - 0.0078125 inp2 - 0.00390625 inp3
+ 0.00390625 inp4 = -2.5
c12: - 0.0078125 inp0 + pre_6_1 = -2.5
c13: - 0.00390625 inp0 - 0.01171875 inp3 + pre_6_2 = 6.5
c14: - 0.0078125 inp0 + pre_6_3 = -1.5
c15: - 0.00390625 inp0 - 0.0078125 inp3 + pre_6_4 = 6.5
Bounds
pre_6_0 Free
inp0 Free
inp1 Free
inp2 Free
inp3 Free
inp4 Free
pre_6_1 Free
pre_6_2 Free
pre_6_3 Free
pre_6_4 Free
Generals
pre_6_0 inp0 inp1 inp2 inp3 inp4 pre_6_1 pre_6_2 pre_6_3 pre_6_4
MIP 最佳边界是无限的,因为不存在可行的 整数 解。
事实上,您的 ILP 中的所有变量都被限制为一般整数值(Generals 部分)。
这里有一个使用GLPK求解ILP的例子
15 rows, 10 columns, 25 non-zeros
10 integer variables, none of which are binary
...
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
5 rows, 10 columns, 15 non-zeros
0: obj = -8.000000000e+00 inf = 1.631e+01 (5)
5: obj = -3.750000000e-01 inf = 0.000e+00 (0)
* 8: obj = 3.000000000e+00 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+ 8: mip = not found yet <= +inf (1; 0)
+ 8: mip = not found yet <= tree is empty (0; 3)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used: 0.0 secs
Memory used: 0.1 Mb (63069 bytes)
我有以下 MIP 问题。 pre_6_0
的上限不应是无限的,因为它是根据 inp1
、inp2
、inp3
和 inp4
计算得出的,所有这些都在两边都有界.
Maximize
obj: pre_6_0
Subject To
c1: inp0 >= -84
c2: inp0 <= 174
c3: inp1 >= -128
c4: inp1 <= 128
c5: inp2 >= -128
c6: inp2 <= 128
c7: inp3 >= -128
c8: inp3 <= 128
c9: inp4 >= -128
c10: inp4 <= 128
c11: pre_6_0 + 0.03125 inp1 - 0.0078125 inp2 - 0.00390625 inp3
+ 0.00390625 inp4 = -2.5
c12: - 0.0078125 inp0 + pre_6_1 = -2.5
c13: - 0.00390625 inp0 - 0.01171875 inp3 + pre_6_2 = 6.5
c14: - 0.0078125 inp0 + pre_6_3 = -1.5
c15: - 0.00390625 inp0 - 0.0078125 inp3 + pre_6_4 = 6.5
Bounds
pre_6_0 Free
inp0 Free
inp1 Free
inp2 Free
inp3 Free
inp4 Free
pre_6_1 Free
pre_6_2 Free
pre_6_3 Free
pre_6_4 Free
Generals
pre_6_0 inp0 inp1 inp2 inp3 inp4 pre_6_1 pre_6_2 pre_6_3 pre_6_4
MIP 最佳边界是无限的,因为不存在可行的 整数 解。
事实上,您的 ILP 中的所有变量都被限制为一般整数值(Generals 部分)。
这里有一个使用GLPK求解ILP的例子
15 rows, 10 columns, 25 non-zeros
10 integer variables, none of which are binary
...
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
5 rows, 10 columns, 15 non-zeros
0: obj = -8.000000000e+00 inf = 1.631e+01 (5)
5: obj = -3.750000000e-01 inf = 0.000e+00 (0)
* 8: obj = 3.000000000e+00 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+ 8: mip = not found yet <= +inf (1; 0)
+ 8: mip = not found yet <= tree is empty (0; 3)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used: 0.0 secs
Memory used: 0.1 Mb (63069 bytes)