[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: One-off error in the MIP solver?
|
From: |
Hartmut Henkel |
|
Subject: |
Re: One-off error in the MIP solver? |
|
Date: |
Mon, 24 Jan 2022 23:01:06 +0100 (CET) |
Hi Antti,
On Mon, 24 Jan 2022, Antti Lehtila wrote:
> 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.
first, many thanks for checking into this. There is no --tolint
parameter (yet) for glpsol, i didn't know of this one since i haven't
used the C library calls yet.
> 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.
Ok.
> 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
Many thanks for your explanation! It will take me some time to get the
details. For now i have just added a --tolint parameter to the command
line of glpsol (file glpsol.c) here, and with --tolint 1e-6 or lower the
result comes out right. Hopefully this and a few other --tol parameters
will find their way into glpsol. GMPL by glpsol is such a funny and
approachable language for learning and trying out LP/MIP stuff.
Best Regards, Hartmut
> _____________________________________________________________________________________________________
>
> 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