[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: One-off error in the MIP solver?
|
From: |
Antti Lehtila |
|
Subject: |
Re: One-off error in the MIP solver? |
|
Date: |
Mon, 24 Jan 2022 20:26:24 +0200 |
|
User-agent: |
Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 |
Hi Hartmut,
Please find below my attempt to explain
what's happening there.
I think the integrality tolerance is
parm->tol_int = 1e-5; (hard-coded), at least it was so a few
years ago.
And indeed, the solution for the LP
relaxation already happens to satisfy the tolerances. The LP
solution is as follows:
------------------------
No. Row
name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- -------------
-------------
1 slack B 0
2 cs1 NU 131072
131072 < eps
3 cs2 B 131072 131072
No. Column name St Activity Lower bound Upper
bound Marginal
------ ------------ -- ------------- ------------- -------------
-------------
1 x[1] NU 1 0
1 < eps
2 x[2] NU 1 0
1 < eps
3 x[3] NU 1 0
1 < eps
4 x[4] NU 1 0
1 < eps
5 x[5] NU 1 0
1 < eps
6 x[6] NU 1 0
1 < eps
7 x[7] NU 1 0
1 < eps
8 x[8] NU 1 0
1 < eps
9 x[9] NU 1 0
1 < eps
10 x[10] NU 1 0
1 < eps
11 x[11] NU 1 0
1 < eps
12 x[12] NU 1 0
1 < eps
13 x[13] NU 1 0
1 < eps
14 x[14] NU 1 0
1 < eps
15 x[15] NU 1 0
1 < eps
16 x[16] NU 1 0
1 < eps
17 x[17] NU 1 0
1 < eps
18 x[18] B 7.62939e-06 0 1
19 x[19] NL 0 0
1 < eps
20 x[20] NL 0 0
1 < eps
21 e NL 0
0 1
------------------------
As you can see, the variable x[18] is
basic at the value of 7.63e-6, which nicely satisfies the
integrality tolerance. The Karush-Kuhn-Tucker conditions also all
have high quality in the LP relaxation solution. So, it appears
that when entering the MIP algorithm, this initial LP solution is
immediately accepted as the optimal MIP solution. But then, it
seems that Glpk rounds off the levels of the binary variables, and
as a result, in the final solution x[18] has zero value and the
second constraint is actually shown violated. Indeed, the MIP
solution is listed showing the constraint violation and low
quality for KKT.PB, as follows:
No. Row
name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 slack 0
2 cs1 131071 131072
3 cs2 131071 131072
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x[1] * 1 0 1
2 x[2] * 1 0 1
3 x[3] * 1 0 1
4 x[4] * 1 0 1
5 x[5] * 1 0 1
6 x[6] * 1 0 1
7 x[7] * 1 0 1
8 x[8] * 1 0 1
9 x[9] * 1 0 1
10 x[10] * 1 0 1
11 x[11] * 1 0 1
12 x[12] * 1 0 1
13 x[13] * 1 0 1
14 x[14] * 1 0 1
15 x[15] * 1 0 1
16 x[16] * 1 0 1
17 x[17] * 1 0 1
18 x[18] * 0 0 1
19 x[19] * 0 0 1
20 x[20] * 0 0 1
21 e 0 0
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 1.00e+00 on row 3
max.rel.err = 7.63e-06 on row 3
Low quality
On 24.01.2022 11:46, Hartmut Henkel
wrote:
Hi,
here seems to be some one-off error in gmpl/glpk (5.0, debian Linux):
param v := 131072;
param n := 20; # number of bits
set J := 1..n; # set of all bits
var x{j in J}, binary;
var e, >= 0;
minimize slack: e;
s.t. cs1: sum{j in J} (2**(j - 1) * x[j]) - v <= e;
s.t. cs2: sum{j in J} (2**(j - 1) * x[j]) - v >= -e;
solve;
printf "v: %d\nv: ", v;
for {j in J} printf "%d", x[n - j + 1];
printf "\n";
printf "v: %d\n", sum{j in J} (2**(j - 1) * x[j]);
printf "e: %d\n", e;
end;
Here it prints:
v: 131072
v: 0011111111111111111
v: 131071
e: 0
With v = 131071 or v = 131073 or v = 65536 it works fine. Also fine with
larger numbers like v = 888888. Same problem when solving the exported
.lp file, which looks ok., confirmed by another solver. Seems not to be
a general int limitation or printing issue. Do you have any idea what's
happening here?
Best Regards, Hartmut
.