Re: Solver delivers wrong answer when 2 constraints are close
I suspect the best value for eps might be sqrt(DBL_EPSILON), usually 2**-26, roughly 1.6*10**-8 . If a model requires distinguishing between 1-eps and 1+eps, another model might be in order. Not a lot of generic advice can be given, that said, X >= L1, X>= L2 can always become X>=max(L1, L2). -- Michael henne...@web.cs.ndsu.nodak.edu "Sorry but your password must contain an uppercase letter, a number, a haiku, a gang sign, a heiroglyph, and the blood of a virgin." -- someeecards
Re: Solver delivers wrong answer when 2 constraints are close
Using LP_SOLVE as solver with glpsol (experimental) also produce the stated expected value for "min_bound = 1e-09": glpsol --lpsolve -m test_1e_4_2.mod GLPSOL: GLPK LP/MIP Solver, v4.65-ex, glp_double size 8 Parameter(s) specified in the command line: --lpsolve -m test_1e_4_2.mod Reading model section from test_1e_4_2.mod... 15 lines were read test_1e_4_2.mod:19: warning: unexpected end of file; missing end statement inserted 19 lines were read Generating y... Generating LIM_INF_X... Generating PART_MIN_X... Solve callback called Model name: 'test_1e_4_2' - run #1 Objective: Minimize(y) SUBMITTED Model size: 2 constraints, 1 variables, 2 non-zeros. Sets: 0 GUB, 0 SOS. Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2. The primal and dual simplex pricing strategy set to 'Devex'. Optimal solution 1.1 after 2 iter. Relative numeric accuracy ||*|| = 0 MEMO: lp_solve version 5.5.2.5 for 64 bit OS, with 64 bit REAL variables. In the total iteration count 2, 0 (0.0%) were bound flips. There were 0 refactorizations, 0 triggered by time and 0 by density. ... on average 2.0 major pivots per refactorization. The largest [LUSOL v2.2.1.0] fact(B) had 3 NZ entries, 1.0x largest basis. The constraint matrix inf-norm is 1, with a dynamic range of 1. Time to load data was 0.001 seconds, presolve used 0.000 seconds, ... 0.000 seconds in simplex solver, in total 0.001 seconds. Model has been successfully processed Display statement at line 16 min_bound = 1e-09 Display statement at line 17 x.val = 1.1 Model has been successfully generated On 4/3/21 18:19, Thiago Neves wrote: Thank you so much for the explanation Antti. You are right, this seems more like a "design flaw" than a "bug". I'm sorry for the misconception. Why does "eps" need to be so big (1e-3)? Is there a way to set a fixed threshold in the command line (glpsol) or at least the 1e-3 part? In the case (1), wouldn't it be better to choose max(l[q], l'[q])? Att, *Thiago H. Neves* (31) 98608-0666 -- Forwarded message - De: *Antti Lehtila* mailto:antti.leht...@vtt.fi>> Date: qui., 4 de mar. de 2021 às 12:44 Subject: Re: Solver delivers wrong answer when 2 constraints are close To: mailto:help-glpk@gnu.org>> Hi, I think it works fully as documented, and so *per design*. Singleton rows are treated as column bounds by the preprocessor. See documentation for *npp_implied_lower*: *--- * Processing implied column lower bound l'[q] includes the following * cases: * * 1) if l'[q] < l[q] + eps, implied lower bound is redundant; * * 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound * l[q] can be strengthened by replacing it with l'[q]. If in this * case new column lower bound becomes close to current column upper * bound u[q], the column can be fixed on its upper bound; * * 3) if l'[q] > u[q] + eps, implied lower bound violates current * column upper bound u[q], in which case the problem has no primal * feasible solution. */ *--- The lower bound can have only a single value, but if you define multiple values for a column lower bound, they must of course be processed in some order. In this case, the lower bound is first defined l(q)=0, then l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus considered *redundant*, as per design, and so the second value l(q)=1 remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 * fabs(q->lb)). I guess it may be a considered a design flaw, but I think it should not be called a bug, as it is working as designed and documented. Besides, I think one should use the Bounds section for bounds, instead of using multiple constraints for defining a single lower bound. Best, Antti ___ On 04.03.2021 11:38, Domingo Alvarez Duarte wrote: > > Testing this problem I discover that if we change the order of > constraint declarations it seems to give the expected answer as stated > by Thiago (what I think could be another bug). > > > > /param min_bound default 0;/ > /var x >= 0; > > minimize y: x;/ > * > */*s.t. PART_MIN_X: x >= 1 + min_bound;* > / > /*s.t. LIM_INF_X: x >= 1; > * > / > /solve; > display min_bound; > display x; # EXPECTED RESULT: X == 1.0001 > > data; > param min_bound := 1e-4; > end;/ > > > > Output: > > > > x.val = 1.0001 > > > > On 3/3/21 19:19, Thiago Neves wrote: >> Hi. >> I've found a strange behaviour in glpk which I don't know how to fix >> nor how to contour it. It seems like GLPK can't dis
Re: Solver delivers wrong answer when 2 constraints are close
Looking through the code I can see that it seems to be a mismatch in
checking for lower/upper bound in other places too (see bellow).
Also testing in AMPL it only returns 'x = 1' for 'min_bound = 1e-06',
and it works for 'min_bound = 1e-05' and return 'x = 1.1'.
===
int npp_implied_value(NPP *npp, NPPCOL *q, glp_double s)
{
...
/* check current column lower bound */
if (q->lb != -GLP_DBL_MAX)
{ eps = (q->is_int ? GLP_NPP_EPS5 : GLP_NPP_EPS_5_8_fabs(q->lb));
...
/* check current column upper bound */
if (q->ub != +GLP_DBL_MAX)
{ eps = (q->is_int ? GLP_NPP_EPS5 : GLP_NPP_EPS_5_8_fabs(q->ub));
...
}
...
int npp_implied_lower(NPP *npp, NPPCOL *q, glp_double l)
{ /* process implied column lower bound */
...
/* check current column lower bound */
if (q->lb != -GLP_DBL_MAX)
{ eps = (q->is_int ? GLP_NPP_EPS : GLP_NPP_EPS_3_6_fabs(q->lb));
...
/* check current column upper bound */
if (q->ub != +GLP_DBL_MAX)
{ eps = (q->is_int ? GLP_NPP_EPS5 : GLP_NPP_EPS_5_8_fabs(q->ub));
...
}
...
int npp_implied_upper(NPP *npp, NPPCOL *q, glp_double u)
{ int ret;
...
/* check current column upper bound */
if (q->ub != +GLP_DBL_MAX)
{ eps = (q->is_int ? GLP_NPP_EPS : GLP_NPP_EPS_3_6_fabs(q->ub));
...
/* check current column lower bound */
if (q->lb != -GLP_DBL_MAX)
{ eps = (q->is_int ? GLP_NPP_EPS5 : GLP_NPP_EPS_5_8_fabs(q->lb));
...
}
===
Cheers !
On 4/3/21 18:19, Thiago Neves wrote:
Thank you so much for the explanation Antti.
You are right, this seems more like a "design flaw" than a "bug". I'm
sorry for the misconception.
Why does "eps" need to be so big (1e-3)? Is there a way to set a fixed
threshold in the command line (glpsol) or at least the 1e-3 part?
In the case (1), wouldn't it be better to choose max(l[q], l'[q])?
Att,
*Thiago H. Neves*
(31) 98608-0666
------ Forwarded message -----
De: *Antti Lehtila* mailto:antti.leht...@vtt.fi>>
Date: qui., 4 de mar. de 2021 às 12:44
Subject: Re: Solver delivers wrong answer when 2 constraints are close
To: mailto:help-glpk@gnu.org>>
Hi,
I think it works fully as documented, and so *per design*. Singleton
rows are treated as column bounds by the preprocessor. See documentation
for *npp_implied_lower*:
*---
* Processing implied column lower bound l'[q] includes the following
* cases:
*
* 1) if l'[q] < l[q] + eps, implied lower bound is redundant;
*
* 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound
* l[q] can be strengthened by replacing it with l'[q]. If in this
* case new column lower bound becomes close to current column upper
* bound u[q], the column can be fixed on its upper bound;
*
* 3) if l'[q] > u[q] + eps, implied lower bound violates current
* column upper bound u[q], in which case the problem has no primal
* feasible solution. */
*---
The lower bound can have only a single value, but if you define multiple
values for a column lower bound, they must of course be processed in
some order. In this case, the lower bound is first defined l(q)=0, then
l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus
considered *redundant*, as per design, and so the second value l(q)=1
remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 *
fabs(q->lb)).
I guess it may be a considered a design flaw, but I think it should not
be called a bug, as it is working as designed and documented. Besides,
I think one should use the Bounds section for bounds, instead of using
multiple constraints for defining a single lower bound.
Best,
Antti
___
On 04.03.2021 11:38, Domingo Alvarez Duarte wrote:
>
> Testing this problem I discover that if we change the order of
> constraint declarations it seems to give the expected answer as stated
> by Thiago (what I think could be another bug).
>
>
>
> /param min_bound default 0;/
> /var x >= 0;
>
> minimize y: x;/
> *
> */*s.t. PART_MIN_X: x >= 1 + min_bound;*
> /
> /*s.t. LIM_INF_X: x >= 1;
> *
> /
> /solve;
> display min_bound;
> display x; # EXPECTED RESULT: X == 1.0001
>
> data;
> param min_bound := 1e-4;
> end;/
>
>
>
> Output:
>
>
>
> x.val = 1.0001
>
>
>
> On 3/3/21 19:19, Thiago Neves wrote:
>> Hi.
>> I've found a strange behaviour in glpk which I don't know how to fix
>> nor how to contour it. It seems like GLPK can't distinguish
>> constraints that differs from about 1e-4.
>>
>> Follows simple examples that explain and reproduce the problem.**
>> *
>> *
>> *The
Re: Solver delivers wrong answer when 2 constraints are close
I just tested with using symmetric checks for both lower/upper bounds
and testing almost all examples give the expected results, and with
Thiago example with/without change the constraint order the result is
the stated as expected.
Before:
===
/* check current column lower bound */
if (q->lb != -DBL_MAX)
{ eps = (q->is_int ? 1e-3 : 1e-3 + 1e-6 * fabs(q->lb));
if (l < q->lb + eps)
{ ret = 0; /* redundant */
goto done;
}
}
/* check current column upper bound */
if (q->ub != +DBL_MAX)
{ eps = (q->is_int ? 1e-5 : 1e-5 + 1e-8 * fabs(q->ub));
if (l > q->ub + eps)
{ ret = 4; /* infeasible */
goto done;
}
/* if l'[q] is close to u[q], fix column at its upper bound */
if (l > q->ub - 1e-3 * eps)
{ q->lb = q->ub;
ret = 3; /* fixed */
goto done;
}
===
After:
===
/* check current column lower bound */
if (q->lb != -DBL_MAX)
{ eps = (q->is_int ? 1e-5 : 1e-5 + 1e-8 * fabs(q->lb));
<<< changed here
if (l < q->lb + eps)
{ ret = 0; /* redundant */
goto done;
}
}
/* check current column upper bound */
if (q->ub != +DBL_MAX)
{ eps = (q->is_int ? 1e-5 : 1e-5 + 1e-8 * fabs(q->ub));
if (l > q->ub + eps)
{ ret = 4; /* infeasible */
goto done;
}
/* if l'[q] is close to u[q], fix column at its upper bound */
if (l > q->ub - 1e-3 * eps)
{ q->lb = q->ub;
ret = 3; /* fixed */
goto done;
}
===
On 4/3/21 18:19, Thiago Neves wrote:
Thank you so much for the explanation Antti.
You are right, this seems more like a "design flaw" than a "bug". I'm
sorry for the misconception.
Why does "eps" need to be so big (1e-3)? Is there a way to set a fixed
threshold in the command line (glpsol) or at least the 1e-3 part?
In the case (1), wouldn't it be better to choose max(l[q], l'[q])?
Att,
*Thiago H. Neves*
(31) 98608-0666
-- Forwarded message -
De: *Antti Lehtila* mailto:antti.leht...@vtt.fi>>
Date: qui., 4 de mar. de 2021 às 12:44
Subject: Re: Solver delivers wrong answer when 2 constraints are close
To: mailto:help-glpk@gnu.org>>
Hi,
I think it works fully as documented, and so *per design*. Singleton
rows are treated as column bounds by the preprocessor. See documentation
for *npp_implied_lower*:
*---
* Processing implied column lower bound l'[q] includes the following
* cases:
*
* 1) if l'[q] < l[q] + eps, implied lower bound is redundant;
*
* 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound
* l[q] can be strengthened by replacing it with l'[q]. If in this
* case new column lower bound becomes close to current column upper
* bound u[q], the column can be fixed on its upper bound;
*
* 3) if l'[q] > u[q] + eps, implied lower bound violates current
* column upper bound u[q], in which case the problem has no primal
* feasible solution. */
*---
The lower bound can have only a single value, but if you define multiple
values for a column lower bound, they must of course be processed in
some order. In this case, the lower bound is first defined l(q)=0, then
l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus
considered *redundant*, as per design, and so the second value l(q)=1
remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 *
fabs(q->lb)).
I guess it may be a considered a design flaw, but I think it should not
be called a bug, as it is working as designed and documented. Besides,
I think one should use the Bounds section for bounds, instead of using
multiple constraints for defining a single lower bound.
Best,
Antti
___
On 04.03.2021 11:38, Domingo Alvarez Duarte wrote:
>
> Testing this problem I discover that if we change the order of
> constraint declarations it seems to give the expected answer as stated
> by Thiago (what I think could be another bug).
>
>
>
> /param min_bound default 0;/
> /var x >= 0;
>
> minimize y: x;/
> *
> */*s.t. PART_MIN_X: x >= 1 + min_bound;*
> /
> /*s.t. LIM_INF_X: x >= 1;
> *
> /
> /solve;
> display min_bound;
> display x; # EXPECTED RESULT: X == 1.0001
>
> data;
> param min_bound := 1e-4;
> end;/
>
>
>
> Output:
>
>
>
> x.val = 1.0001
>
>
>
> On 3/3/21 19:19, Thiago Neves wrote:
>> Hi.
>> I've found a strange behaviour in glpk which I don't know how to fix
>> nor how to contour it. It seems like GLPK
Re: Solver delivers wrong answer when 2 constraints are close
5 iterations and 0.01 seconds
*
*
Optimal objective 3.360308548e+09
Bests,
--
João Flávio de Freitas Almeida
Em qui., 4 de mar. de 2021 às 14:20, Thiago Neves
mailto:thiagoneve...@gmail.com>> escreveu:
Thank you so much for the explanation Antti.
You are right, this seems more like a "design flaw" than a "bug".
I'm sorry for the misconception.
Why does "eps" need to be so big (1e-3)? Is there a way to set a
fixed threshold in the command line (glpsol) or at least the 1e-3
part?
In the case (1), wouldn't it be better to choose max(l[q], l'[q])?
Att,
*Thiago H. Neves*
(31) 98608-0666
-- Forwarded message -
De: *Antti Lehtila* mailto:antti.leht...@vtt.fi>>
Date: qui., 4 de mar. de 2021 às 12:44
Subject: Re: Solver delivers wrong answer when 2 constraints are close
To: mailto:help-glpk@gnu.org>>
Hi,
I think it works fully as documented, and so *per design*. Singleton
rows are treated as column bounds by the preprocessor. See
documentation
for *npp_implied_lower*:
*---
* Processing implied column lower bound l'[q] includes the following
* cases:
*
* 1) if l'[q] < l[q] + eps, implied lower bound is redundant;
*
* 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound
* l[q] can be strengthened by replacing it with l'[q]. If in this
* case new column lower bound becomes close to current column
upper
* bound u[q], the column can be fixed on its upper bound;
*
* 3) if l'[q] > u[q] + eps, implied lower bound violates current
* column upper bound u[q], in which case the problem has no primal
* feasible solution. */
*---
The lower bound can have only a single value, but if you define
multiple
values for a column lower bound, they must of course be processed in
some order. In this case, the lower bound is first defined
l(q)=0, then
l'(q)=1, and finally l'(q)=1.0001. The third value for the bound
is thus
considered *redundant*, as per design, and so the second value l(q)=1
remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 *
fabs(q->lb)).
I guess it may be a considered a design flaw, but I think it
should not
be called a bug, as it is working as designed and documented.
Besides,
I think one should use the Bounds section for bounds, instead of
using
multiple constraints for defining a single lower bound.
Best,
Antti
___
On 04.03.2021 11:38, Domingo Alvarez Duarte wrote:
>
> Testing this problem I discover that if we change the order of
> constraint declarations it seems to give the expected answer as
stated
> by Thiago (what I think could be another bug).
>
>
>
> /param min_bound default 0;/
> /var x >= 0;
>
> minimize y: x;/
> *
> */*s.t. PART_MIN_X: x >= 1 + min_bound;*
> /
> /*s.t. LIM_INF_X: x >= 1;
> *
> /
> /solve;
> display min_bound;
> display x; # EXPECTED RESULT: X == 1.0001
>
> data;
> param min_bound := 1e-4;
> end;/
>
>
>
> Output:
>
>
>
> x.val = 1.0001
>
>
>
> On 3/3/21 19:19, Thiago Neves wrote:
>> Hi.
>> I've found a strange behaviour in glpk which I don't know how
to fix
>> nor how to contour it. It seems like GLPK can't distinguish
>> constraints that differs from about 1e-4.
>>
>> Follows simple examples that explain and reproduce the problem.**
>> *
>> *
>> *The first model gives the desired answer (x = 1.0001):*
>> /
>> param min_bound default 0;/
>> /var x >= 0;
>>
>> minimize y: x;/
>> /*
>> s.t. PART_MIN_X: x >= 1 + min_bound;*
>>
>> solve;
>> display min_bound;
>> display x; # EXPECTED RESULT: X == 1.0001
>>
>> data;
>> param min_bound := 1e-4;
>> end;
>> /
>> /_/
>> /OUTPUT:/
>> /x.val = 1.0001/
>> /_ /
>>
>> *Now, if I add a second constraint "close" to the first one, the
>> solver will deliver an answer that is actually infeasible:*
>>
>> /param min_bound default 0;/
>> /var x >= 0;
>>
>> minimize y: x;/
>>
Re: Solver delivers wrong answer when 2 constraints are close
ts, -- João Flávio de Freitas Almeida Em qui., 4 de mar. de 2021 às 14:20, Thiago Neves escreveu: > Thank you so much for the explanation Antti. > You are right, this seems more like a "design flaw" than a "bug". I'm > sorry for the misconception. > > Why does "eps" need to be so big (1e-3)? Is there a way to set a fixed > threshold in the command line (glpsol) or at least the 1e-3 part? > > In the case (1), wouldn't it be better to choose max(l[q], l'[q])? > > Att, > > *Thiago H. Neves* > (31) 98608-0666 > > > > ------ Forwarded message - > De: Antti Lehtila > Date: qui., 4 de mar. de 2021 às 12:44 > Subject: Re: Solver delivers wrong answer when 2 constraints are close > To: > > > Hi, > > I think it works fully as documented, and so *per design*. Singleton > rows are treated as column bounds by the preprocessor. See documentation > for *npp_implied_lower*: > *--- > * Processing implied column lower bound l'[q] includes the following > * cases: > * > * 1) if l'[q] < l[q] + eps, implied lower bound is redundant; > * > * 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound > * l[q] can be strengthened by replacing it with l'[q]. If in this > * case new column lower bound becomes close to current column upper > * bound u[q], the column can be fixed on its upper bound; > * > * 3) if l'[q] > u[q] + eps, implied lower bound violates current > * column upper bound u[q], in which case the problem has no primal > * feasible solution. */ > *--- > The lower bound can have only a single value, but if you define multiple > values for a column lower bound, they must of course be processed in > some order. In this case, the lower bound is first defined l(q)=0, then > l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus > considered *redundant*, as per design, and so the second value l(q)=1 > remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 * > fabs(q->lb)). > > I guess it may be a considered a design flaw, but I think it should not > be called a bug, as it is working as designed and documented. Besides, > I think one should use the Bounds section for bounds, instead of using > multiple constraints for defining a single lower bound. > > Best, > Antti > ___ > On 04.03.2021 11:38, Domingo Alvarez Duarte wrote: > > > > Testing this problem I discover that if we change the order of > > constraint declarations it seems to give the expected answer as stated > > by Thiago (what I think could be another bug). > > > > > > > > /param min_bound default 0;/ > > /var x >= 0; > > > > minimize y: x;/ > > * > > */*s.t. PART_MIN_X: x >= 1 + min_bound;* > > / > > /*s.t. LIM_INF_X: x >= 1; > > * > > / > > /solve; > > display min_bound; > > display x; # EXPECTED RESULT: X == 1.0001 > > > > data; > > param min_bound := 1e-4; > > end;/ > > > > > > > > Output: > > > > > > > > x.val = 1.0001 > > > > > > > > On 3/3/21 19:19, Thiago Neves wrote: > >> Hi. > >> I've found a strange behaviour in glpk which I don't know how to fix > >> nor how to contour it. It seems like GLPK can't distinguish > >> constraints that differs from about 1e-4. > >> > >> Follows simple examples that explain and reproduce the problem.** > >> * > >> * > >> *The first model gives the desired answer (x = 1.0001):* > >> / > >> param min_bound default 0;/ > >> /var x >= 0; > >> > >> minimize y: x;/ > >> /* > >> s.t. PART_MIN_X: x >= 1 + min_bound;* > >> > >> solve; > >> display min_bound; > >> display x; # EXPECTED RESULT: X == 1.0001 > >> > >> data; > >> param min_bound := 1e-4; > >> end; > >> / > >> /_/ > >> /OUTPUT:/ > >> /x.val = 1.0001/ > >> /_ / > >> > >> *Now, if I add a second constraint "close" to the first one, the > >> solver will deliver an answer that is actually infeasible:* > >> > >> /param min_bound default 0;/ > >> /var x >= 0; > >> > >> minimize y: x;/ > >> > >> *s.t. LIM_INF_X: x >= 1; > >> > >> */*s.t. PART_MIN_X: x >= 1 + min_bound;* > >> > >> solve; > >> display min_bound; > >> display x; # EXPECTED RESULT: X == 1.0001 > >> > >> data; > >> param min_bound := 1e-4; > >> end;/ > >> /_/ > >> /OUTPUT:/ > >> x.val = 1 > >> /_ / > >> > >> *If I change the "min_bound" parameter to 1e-2, the second model > >> works as expected (x = 1.01):* > >> > >> /param min_bound default 0;/ > >> / > >> / > >> /var x >= 0; > >> > >> minimize y: x;/ > >> * > >> * > >> *s.t. LIM_INF_X: x >= 1; > >> > >> */*s.t. PART_MIN_X: x >= 1 + min_bound;* > >> > >> solve;/ > >> / > >> display x; # EXPECTED RESULT: X == 1.01 > >> > >> data; > >> param min_bound := 1e-2; > >> end;/ > >> /_/ > >> /OUTPUT:/ > >> x.val = 1.01 > >> /_ / > >> / > >> / > >> > >> Att, > >> > >> *Thiago H. Neves* > >> (31) 98608-0666 > >> > > >
Re: Solver delivers wrong answer when 2 constraints are close
When I test the provided sample with AMPL I get the stated expected result independent of the order of the constraints. Doesn't seem reasonable to somehow fix the behavior of GLPK/GLPSOL ? Cheers ! On 4/3/21 18:19, Andrew Makhorin wrote: Both 1e-3 and 1e-5 are good enough. If the result is sensitive to such small deviations, this only tells that the model is badly formulated.
Re: Solver delivers wrong answer when 2 constraints are close
Thank you so much for the explanation Antti. You are right, this seems more like a "design flaw" than a "bug". I'm sorry for the misconception. Why does "eps" need to be so big (1e-3)? Is there a way to set a fixed threshold in the command line (glpsol) or at least the 1e-3 part? In the case (1), wouldn't it be better to choose max(l[q], l'[q])? Att, *Thiago H. Neves* (31) 98608-0666 -- Forwarded message - De: Antti Lehtila Date: qui., 4 de mar. de 2021 às 12:44 Subject: Re: Solver delivers wrong answer when 2 constraints are close To: Hi, I think it works fully as documented, and so *per design*. Singleton rows are treated as column bounds by the preprocessor. See documentation for *npp_implied_lower*: *--- * Processing implied column lower bound l'[q] includes the following * cases: * * 1) if l'[q] < l[q] + eps, implied lower bound is redundant; * * 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound * l[q] can be strengthened by replacing it with l'[q]. If in this * case new column lower bound becomes close to current column upper * bound u[q], the column can be fixed on its upper bound; * * 3) if l'[q] > u[q] + eps, implied lower bound violates current * column upper bound u[q], in which case the problem has no primal * feasible solution. */ *--- The lower bound can have only a single value, but if you define multiple values for a column lower bound, they must of course be processed in some order. In this case, the lower bound is first defined l(q)=0, then l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus considered *redundant*, as per design, and so the second value l(q)=1 remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 * fabs(q->lb)). I guess it may be a considered a design flaw, but I think it should not be called a bug, as it is working as designed and documented. Besides, I think one should use the Bounds section for bounds, instead of using multiple constraints for defining a single lower bound. Best, Antti ___ On 04.03.2021 11:38, Domingo Alvarez Duarte wrote: > > Testing this problem I discover that if we change the order of > constraint declarations it seems to give the expected answer as stated > by Thiago (what I think could be another bug). > > > > /param min_bound default 0;/ > /var x >= 0; > > minimize y: x;/ > * > */*s.t. PART_MIN_X: x >= 1 + min_bound;* > / > /*s.t. LIM_INF_X: x >= 1; > * > / > /solve; > display min_bound; > display x; # EXPECTED RESULT: X == 1.0001 > > data; > param min_bound := 1e-4; > end;/ > > > > Output: > > > > x.val = 1.0001 > > > > On 3/3/21 19:19, Thiago Neves wrote: >> Hi. >> I've found a strange behaviour in glpk which I don't know how to fix >> nor how to contour it. It seems like GLPK can't distinguish >> constraints that differs from about 1e-4. >> >> Follows simple examples that explain and reproduce the problem.** >> * >> * >> *The first model gives the desired answer (x = 1.0001):* >> / >> param min_bound default 0;/ >> /var x >= 0; >> >> minimize y: x;/ >> /* >> s.t. PART_MIN_X: x >= 1 + min_bound;* >> >> solve; >> display min_bound; >> display x; # EXPECTED RESULT: X == 1.0001 >> >> data; >> param min_bound := 1e-4; >> end; >> / >> /_/ >> /OUTPUT:/ >> /x.val = 1.0001/ >> /_ / >> >> *Now, if I add a second constraint "close" to the first one, the >> solver will deliver an answer that is actually infeasible:* >> >> /param min_bound default 0;/ >> /var x >= 0; >> >> minimize y: x;/ >> >> *s.t. LIM_INF_X: x >= 1; >> >> */*s.t. PART_MIN_X: x >= 1 + min_bound;* >> >> solve; >> display min_bound; >> display x; # EXPECTED RESULT: X == 1.0001 >> >> data; >> param min_bound := 1e-4; >> end;/ >> /_/ >> /OUTPUT:/ >> x.val = 1 >> /_ / >> >> *If I change the "min_bound" parameter to 1e-2, the second model >> works as expected (x = 1.01):* >> >> /param min_bound default 0;/ >> / >> / >> /var x >= 0; >> >> minimize y: x;/ >> * >> * >> *s.t. LIM_INF_X: x >= 1; >> >> */*s.t. PART_MIN_X: x >= 1 + min_bound;* >> >> solve;/ >> / >> display x; # EXPECTED RESULT: X == 1.01 >> >> data; >> param min_bound := 1e-2; >> end;/ >> /_/ >> /OUTPUT:/ >> x.val = 1.01 >> /_ / >> / >> / >> >> Att, >> >> *Thiago H. Neves* >> (31) 98608-0666 >>
Re: Solver delivers wrong answer when 2 constraints are close
On Thu, 2021-03-04 at 17:47 +0100, Heinrich Schuchardt wrote: > On 3/4/21 4:44 PM, Antti Lehtila wrote: > > Hi, > > > > I think it works fully as documented, and so *per design*. Singleton > > rows are treated as column bounds by the preprocessor. See > > documentation > > for *npp_implied_lower*: > > *--- > > * Processing implied column lower bound l'[q] includes the > > following > > * cases: > > * > > * 1) if l'[q] < l[q] + eps, implied lower bound is redundant; > > * > > * 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower > > bound > > In this line an apostrophe is missing. > > 2) if l[q] + eps <= l'[q] <= u[q] + eps, current column lower bound > > > * l[q] can be strengthened by replacing it with l'[q]. If in > > this > > * case new column lower bound becomes close to current column > > upper > > * bound u[q], the column can be fixed on its upper bound; > > It is this strengthening that fails: > > src/npp/npp3.c:567 > eps = (q->is_int ? 1e-3 : 1e-3 + 1e-8 * fabs(q->lb)); > > Set eps to 1E-5 and you are fine. > > Or run with --nopresol. > > @Andrew: > Shouldn't 1E-5 be good enough? > Why do we need eps > 0? Both 1e-3 and 1e-5 are good enough. If the result is sensitive to such small deviations, this only tells that the model is badly formulated. > > Best regards. > > Heinrich > > > * > > * 3) if l'[q] > u[q] + eps, implied lower bound violates current > > * column upper bound u[q], in which case the problem has no > > primal > > * feasible solution. */ > > *--- > > The lower bound can have only a single value, but if you define > > multiple > > values for a column lower bound, they must of course be processed in > > some order. In this case, the lower bound is first defined l(q)=0, > > then > > l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is > > thus > > considered *redundant*, as per design, and so the second value > > l(q)=1 > > remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 * > > fabs(q->lb)). > > > > I guess it may be a considered a design flaw, but I think it should > > not > > be called a bug, as it is working as designed and documented. > > Besides, > > I think one should use the Bounds section for bounds, instead of > > using > > multiple constraints for defining a single lower bound. > > > > Best, > > Antti > > ___ > > On 04.03.2021 11:38, Domingo Alvarez Duarte wrote: > > > > > > Testing this problem I discover that if we change the order of > > > constraint declarations it seems to give the expected answer as > > > stated > > > by Thiago (what I think could be another bug). > > > > > > > > > > > > /param min_bound default 0;/ > > > /var x >= 0; > > > > > > minimize y: x;/ > > > * > > > */*s.t. PART_MIN_X: x >= 1 + min_bound;* > > > / > > > /*s.t. LIM_INF_X: x >= 1; > > > * > > > / > > > /solve; > > > display min_bound; > > > display x; # EXPECTED RESULT: X == 1.0001 > > > > > > data; > > > param min_bound := 1e-4; > > > end;/ > > > > > > > > > > > > Output: > > > > > > > > > > > > x.val = 1.0001 > > > > > > > > > > > > On 3/3/21 19:19, Thiago Neves wrote: > > > > Hi. > > > > I've found a strange behaviour in glpk which I don't know how to > > > > fix > > > > nor how to contour it. It seems like GLPK can't distinguish > > > > constraints that differs from about 1e-4. > > > > > > > > Follows simple examples that explain and reproduce the > > > > problem.** > > > > * > > > > * > > > > *The first model gives the desired answer (x = 1.0001):* > > > > / > > > > param min_bound default 0;/ > > > > /var x >= 0; > > > > > > > > minimize y: x;/ > > > > /* > > > > s.t. PART_MIN_X: x >= 1 + min_bound;* > > > > > > > > solve; > > > > display min_bound; > > > > display x; # EXPECTED RESULT: X == 1.0001 > > > > > > > > data; > > > > param min_bound := 1e-4; > > > > end; > > > > / > > > > /_/ > > > > /OUTPUT:/ > > > > /x.val = 1.0001/ > > > > /_ / > > > > > > > > *Now, if I add a second constraint "close" to the first one, the > > > > solver will deliver an answer that is actually infeasible:* > > > > > > > > /param min_bound default 0;/ > > > > /var x >= 0; > > > > > > > > minimize y: x;/ > > > > > > > > *s.t. LIM_INF_X: x >= 1; > > > > > > > > */*s.t. PART_MIN_X: x >= 1 + min_bound;* > > > > > > > > solve; > > > > display min_bound; > > > > display x; # EXPECTED RESULT: X == 1.0001 > > > > > > > > data; > > > > param min_bound := 1e-4; > > > > end;/ > > > > /_/ > > > > /OUTPUT:/ > > > > x.val = 1 > > > > /_ / > > > > > > > > *If I change the "min_bound" parameter to 1e-2, the second model > > > > works as expected (x = 1.01):* > > > > > > > > /param min_bound default 0;/ > > > > / > > > > / > > > > /var x >= 0; > > > > > > > > minimize y: x;/ > > > > * > > > > * > > > > *s.t.
Re: Solver delivers wrong answer when 2 constraints are close
On 3/4/21 4:44 PM, Antti Lehtila wrote: Hi, I think it works fully as documented, and so *per design*. Singleton rows are treated as column bounds by the preprocessor. See documentation for *npp_implied_lower*: *--- * Processing implied column lower bound l'[q] includes the following * cases: * * 1) if l'[q] < l[q] + eps, implied lower bound is redundant; * * 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound In this line an apostrophe is missing. 2) if l[q] + eps <= l'[q] <= u[q] + eps, current column lower bound * l[q] can be strengthened by replacing it with l'[q]. If in this * case new column lower bound becomes close to current column upper * bound u[q], the column can be fixed on its upper bound; It is this strengthening that fails: src/npp/npp3.c:567 eps = (q->is_int ? 1e-3 : 1e-3 + 1e-8 * fabs(q->lb)); Set eps to 1E-5 and you are fine. Or run with --nopresol. @Andrew: Shouldn't 1E-5 be good enough? Why do we need eps > 0? Best regards. Heinrich * * 3) if l'[q] > u[q] + eps, implied lower bound violates current * column upper bound u[q], in which case the problem has no primal * feasible solution. */ *--- The lower bound can have only a single value, but if you define multiple values for a column lower bound, they must of course be processed in some order. In this case, the lower bound is first defined l(q)=0, then l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus considered *redundant*, as per design, and so the second value l(q)=1 remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 * fabs(q->lb)). I guess it may be a considered a design flaw, but I think it should not be called a bug, as it is working as designed and documented. Besides, I think one should use the Bounds section for bounds, instead of using multiple constraints for defining a single lower bound. Best, Antti ___ On 04.03.2021 11:38, Domingo Alvarez Duarte wrote: Testing this problem I discover that if we change the order of constraint declarations it seems to give the expected answer as stated by Thiago (what I think could be another bug). /param min_bound default 0;/ /var x >= 0; minimize y: x;/ * */*s.t. PART_MIN_X: x >= 1 + min_bound;* / /*s.t. LIM_INF_X: x >= 1; * / /solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end;/ Output: x.val = 1.0001 On 3/3/21 19:19, Thiago Neves wrote: Hi. I've found a strange behaviour in glpk which I don't know how to fix nor how to contour it. It seems like GLPK can't distinguish constraints that differs from about 1e-4. Follows simple examples that explain and reproduce the problem.** * * *The first model gives the desired answer (x = 1.0001):* / param min_bound default 0;/ /var x >= 0; minimize y: x;/ /* s.t. PART_MIN_X: x >= 1 + min_bound;* solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end; / /_/ /OUTPUT:/ /x.val = 1.0001/ /_ / *Now, if I add a second constraint "close" to the first one, the solver will deliver an answer that is actually infeasible:* /param min_bound default 0;/ /var x >= 0; minimize y: x;/ *s.t. LIM_INF_X: x >= 1; */*s.t. PART_MIN_X: x >= 1 + min_bound;* solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end;/ /_/ /OUTPUT:/ x.val = 1 /_ / *If I change the "min_bound" parameter to 1e-2, the second model works as expected (x = 1.01):* /param min_bound default 0;/ / / /var x >= 0; minimize y: x;/ * * *s.t. LIM_INF_X: x >= 1; */*s.t. PART_MIN_X: x >= 1 + min_bound;* solve;/ / display x; # EXPECTED RESULT: X == 1.01 data; param min_bound := 1e-2; end;/ /_/ /OUTPUT:/ x.val = 1.01 /_ / / / Att, *Thiago H. Neves* (31) 98608-0666
Re: Solver delivers wrong answer when 2 constraints are close
Hello Antti ! Thanks for the explanation ! What's your opinion of a possible solution for this "design flaw" ? Cheers ! On 4/3/21 16:44, Antti Lehtila wrote: I guess it may be a considered a design flaw, but I think it should not be called a bug, as it is working as designed and documented. Besides, I think one should use the Bounds section for bounds, instead of using multiple constraints for defining a single lower bound.
Re: Solver delivers wrong answer when 2 constraints are close
Hi, I think it works fully as documented, and so *per design*. Singleton rows are treated as column bounds by the preprocessor. See documentation for *npp_implied_lower*: *--- * Processing implied column lower bound l'[q] includes the following * cases: * * 1) if l'[q] < l[q] + eps, implied lower bound is redundant; * * 2) if l[q] + eps <= l[q] <= u[q] + eps, current column lower bound * l[q] can be strengthened by replacing it with l'[q]. If in this * case new column lower bound becomes close to current column upper * bound u[q], the column can be fixed on its upper bound; * * 3) if l'[q] > u[q] + eps, implied lower bound violates current * column upper bound u[q], in which case the problem has no primal * feasible solution. */ *--- The lower bound can have only a single value, but if you define multiple values for a column lower bound, they must of course be processed in some order. In this case, the lower bound is first defined l(q)=0, then l'(q)=1, and finally l'(q)=1.0001. The third value for the bound is thus considered *redundant*, as per design, and so the second value l(q)=1 remains in effect. This is because *eps* is defined as 1e-3 + 1e-6 * fabs(q->lb)). I guess it may be a considered a design flaw, but I think it should not be called a bug, as it is working as designed and documented. Besides, I think one should use the Bounds section for bounds, instead of using multiple constraints for defining a single lower bound. Best, Antti ___ On 04.03.2021 11:38, Domingo Alvarez Duarte wrote: Testing this problem I discover that if we change the order of constraint declarations it seems to give the expected answer as stated by Thiago (what I think could be another bug). /param min_bound default 0;/ /var x >= 0; minimize y: x;/ * */*s.t. PART_MIN_X: x >= 1 + min_bound;* / /*s.t. LIM_INF_X: x >= 1; * / /solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end;/ Output: x.val = 1.0001 On 3/3/21 19:19, Thiago Neves wrote: Hi. I've found a strange behaviour in glpk which I don't know how to fix nor how to contour it. It seems like GLPK can't distinguish constraints that differs from about 1e-4. Follows simple examples that explain and reproduce the problem.** * * *The first model gives the desired answer (x = 1.0001):* / param min_bound default 0;/ /var x >= 0; minimize y: x;/ /* s.t. PART_MIN_X: x >= 1 + min_bound;* solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end; / /_/ /OUTPUT:/ /x.val = 1.0001/ /_ / *Now, if I add a second constraint "close" to the first one, the solver will deliver an answer that is actually infeasible:* /param min_bound default 0;/ /var x >= 0; minimize y: x;/ *s.t. LIM_INF_X: x >= 1; */*s.t. PART_MIN_X: x >= 1 + min_bound;* solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end;/ /_/ /OUTPUT:/ x.val = 1 /_ / *If I change the "min_bound" parameter to 1e-2, the second model works as expected (x = 1.01):* /param min_bound default 0;/ / / /var x >= 0; minimize y: x;/ * * *s.t. LIM_INF_X: x >= 1; */*s.t. PART_MIN_X: x >= 1 + min_bound;* solve;/ / display x; # EXPECTED RESULT: X == 1.01 data; param min_bound := 1e-2; end;/ /_/ /OUTPUT:/ x.val = 1.01 /_ / / / Att, *Thiago H. Neves* (31) 98608-0666
Re: Solver delivers wrong answer when 2 constraints are close
Testing this problem I discover that if we change the order of constraint declarations it seems to give the expected answer as stated by Thiago (what I think could be another bug). /param min_bound default 0;/ /var x >= 0; minimize y: x;/ * */*s.t. PART_MIN_X: x >= 1 + min_bound;* / /*s.t. LIM_INF_X: x >= 1; * / /solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end;/ Output: x.val = 1.0001 On 3/3/21 19:19, Thiago Neves wrote: Hi. I've found a strange behaviour in glpk which I don't know how to fix nor how to contour it. It seems like GLPK can't distinguish constraints that differs from about 1e-4. Follows simple examples that explain and reproduce the problem.** * * *The first model gives the desired answer (x = 1.0001):* / param min_bound default 0;/ /var x >= 0; minimize y: x;/ /* s.t. PART_MIN_X: x >= 1 + min_bound;* solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end; / /_/ /OUTPUT:/ /x.val = 1.0001/ /_ / *Now, if I add a second constraint "close" to the first one, the solver will deliver an answer that is actually infeasible:* /param min_bound default 0;/ /var x >= 0; minimize y: x;/ *s.t. LIM_INF_X: x >= 1; */*s.t. PART_MIN_X: x >= 1 + min_bound;* solve; display min_bound; display x; # EXPECTED RESULT: X == 1.0001 data; param min_bound := 1e-4; end;/ /_/ /OUTPUT:/ x.val = 1 /_ / *If I change the "min_bound" parameter to 1e-2, the second model works as expected (x = 1.01):* /param min_bound default 0;/ / / /var x >= 0; minimize y: x;/ * * *s.t. LIM_INF_X: x >= 1; */*s.t. PART_MIN_X: x >= 1 + min_bound;* solve;/ / display x; # EXPECTED RESULT: X == 1.01 data; param min_bound := 1e-2; end;/ /_/ /OUTPUT:/ x.val = 1.01 /_ / / / Att, *Thiago H. Neves* (31) 98608-0666
