Re: [Help-glpk] glpksol default settings
> Hello, I have glpk 4.25 installed on my Ubuntu and I am having trouble > with solving some LPs while glpksol solves them fine. I was trying to > reproduce glpksol's behaviour in my C++ program but couldn't do it. > What options should I use with glp_simplex to get the exact same > behaviour as glpksol? You can enable lp presolver (see the second parameter passed to glp_simplex). On api level it is disabled by default. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
Thanks, I changed it and I can kind of reproduce glpsol's behaviour, but now I pinpointed the problem to this LP: http://www.mimuw.edu.pl/~mucha/lpQ_bad.txt glpsol --cpxlp lpQ_bad.txt give UNBOUNDED solution here. However, both glpsol --std --cpxlp lpQ_bad.txt and glpsol --adv --cpxlp lpQ_bad.txt which is kind of weird. Also neither lpx_adv_basis nor lpx_std_basis seem to solve the problem from C++ API level. Could anyone please tell me what I am missing here? Marcin On Tue, Jul 29, 2008 at 1:31 PM, Andrew Makhorin <[EMAIL PROTECTED]> wrote: >> Hello, I have glpk 4.25 installed on my Ubuntu and I am having trouble >> with solving some LPs while glpksol solves them fine. I was trying to >> reproduce glpksol's behaviour in my C++ program but couldn't do it. >> What options should I use with glp_simplex to get the exact same >> behaviour as glpksol? > > You can enable lp presolver (see the second parameter passed to > glp_simplex). On api level it is disabled by default. > > -- Dwell not on close decisions, and thus, when you play against dwellers, you will make reciprocal gains in energy conservation and sanity preservation. Tommy Angelo ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
> Thanks, I changed it and I can kind of reproduce glpsol's behaviour, > but now I pinpointed the problem to this LP: > http://www.mimuw.edu.pl/~mucha/lpQ_bad.txt > glpsol --cpxlp lpQ_bad.txt > give UNBOUNDED solution here. However, both > glpsol --std --cpxlp lpQ_bad.txt > and > glpsol --adv --cpxlp lpQ_bad.txt > which is kind of weird. Probably this happens because your instance is not well conditioned, so due to excessive round-off errors the presolved lp is unbounded while the original lp is not. > Also neither lpx_adv_basis nor lpx_std_basis > seem to solve the problem from C++ API level. Could anyone please tell > me what I am missing here? Could you provide the code returned by glp_simplex? ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
> Probably this happens because your instance is not well conditioned, > so due to excessive round-off errors the presolved lp is unbounded > while the original lp is not. What does "not well conditioned" mean? What can I do about it? > >> Also neither lpx_adv_basis nor lpx_std_basis >> seem to solve the problem from C++ API level. Could anyone please tell >> me what I am missing here? > > Could you provide the code returned by glp_simplex? I'm getting PROBLEM HAS UNBOUNDED SOLUTION glp_simplex: cannot recover undefined or non-optimal solution and glp_simplex returns 11, i.e. GLP_ENODFS (no dual feasible) Marcin ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
>> Probably this happens because your instance is not well conditioned, >> so due to excessive round-off errors the presolved lp is unbounded >> while the original lp is not. > What does "not well conditioned" mean? What can I do about it? Ill-conditioning means, roughly speaking, that small changes in the problem data lead to large changes in the solution. Your instance in fact is ill conditioned. Glpsol 4.29 gives optimal value 12, where all KKT optimality conditions are satisfied: Karush-Kuhn-Tucker optimality conditions: KKT.PE: max.abs.err. = 4.72e-12 on row 95 max.rel.err. = 4.72e-12 on row 95 High quality KKT.PB: max.abs.err. = 7.88e-10 on column 237 max.rel.err. = 7.88e-10 on column 237 High quality KKT.DE: max.abs.err. = 1.71e-13 on column 166 max.rel.err. = 8.53e-14 on column 166 High quality KKT.DB: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality However, if I convert your instance in MPS format and then run glpsol, it crashes: spx_simplex: warning: numerical instability (primal simplex, phase II) 583: objval = 1.232678937e+02 infeas = 1.0e+00 (0) 600: objval = 1.357637434e+02 infeas = 6.333149060e-02 (0) Assertion failed: spx->p != 0 Error detected in file src\glpspx02.c at line 602 Using a newer, more stable version of glp_simplex I managed to solve your instance; now the optimal value is 170, and KKT conditions are still satisfied: Karush-Kuhn-Tucker optimality conditions: KKT.PE: max.abs.err. = 1.91e-06 on row 181 max.rel.err. = 1.91e-06 on row 181 Low quality KKT.PB: max.abs.err. = 7.29e-10 on row 86 max.rel.err. = 7.29e-10 on row 86 High quality KKT.DE: max.abs.err. = 0.00e+00 on column 0 max.rel.err. = 0.00e+00 on column 0 High quality KKT.DB: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality >> >>> Also neither lpx_adv_basis nor lpx_std_basis >>> seem to solve the problem from C++ API level. Could anyone please tell >>> me what I am missing here? >> >> Could you provide the code returned by glp_simplex? > I'm getting > PROBLEM HAS UNBOUNDED SOLUTION > glp_simplex: cannot recover undefined or non-optimal solution > and glp_simplex returns 11, i.e. GLP_ENODFS (no dual feasible) The lp presolver should be disabled; the reason was explained above. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
Thanks, your explanation has been very helpful. I am trying to improve the form of my LPs and it seems to work in most cases. Marcin On Tue, Jul 29, 2008 at 3:53 PM, Andrew Makhorin <[EMAIL PROTECTED]> wrote: >>> Probably this happens because your instance is not well conditioned, >>> so due to excessive round-off errors the presolved lp is unbounded >>> while the original lp is not. >> What does "not well conditioned" mean? What can I do about it? > > Ill-conditioning means, roughly speaking, that small changes in the > problem data lead to large changes in the solution. > > Your instance in fact is ill conditioned. Glpsol 4.29 gives optimal > value 12, where all KKT optimality conditions are satisfied: > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err. = 4.72e-12 on row 95 >max.rel.err. = 4.72e-12 on row 95 >High quality > > KKT.PB: max.abs.err. = 7.88e-10 on column 237 >max.rel.err. = 7.88e-10 on column 237 >High quality > > KKT.DE: max.abs.err. = 1.71e-13 on column 166 >max.rel.err. = 8.53e-14 on column 166 >High quality > > KKT.DB: max.abs.err. = 0.00e+00 on row 0 >max.rel.err. = 0.00e+00 on row 0 >High quality > > However, if I convert your instance in MPS format and then run glpsol, > it crashes: > > spx_simplex: warning: numerical instability (primal simplex, phase II) >583: objval = 1.232678937e+02 infeas = 1.0e+00 (0) >600: objval = 1.357637434e+02 infeas = 6.333149060e-02 (0) > Assertion failed: spx->p != 0 > Error detected in file src\glpspx02.c at line 602 > > Using a newer, more stable version of glp_simplex I managed to solve > your instance; now the optimal value is 170, and KKT conditions are > still satisfied: > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err. = 1.91e-06 on row 181 >max.rel.err. = 1.91e-06 on row 181 >Low quality > > KKT.PB: max.abs.err. = 7.29e-10 on row 86 >max.rel.err. = 7.29e-10 on row 86 >High quality > > KKT.DE: max.abs.err. = 0.00e+00 on column 0 >max.rel.err. = 0.00e+00 on column 0 >High quality > > KKT.DB: max.abs.err. = 0.00e+00 on row 0 >max.rel.err. = 0.00e+00 on row 0 >High quality > >>> Also neither lpx_adv_basis nor lpx_std_basis seem to solve the problem from C++ API level. Could anyone please tell me what I am missing here? >>> >>> Could you provide the code returned by glp_simplex? >> I'm getting > >> PROBLEM HAS UNBOUNDED SOLUTION >> glp_simplex: cannot recover undefined or non-optimal solution > >> and glp_simplex returns 11, i.e. GLP_ENODFS (no dual feasible) > > The lp presolver should be disabled; the reason was explained above. > > -- Dwell not on close decisions, and thus, when you play against dwellers, you will make reciprocal gains in energy conservation and sanity preservation. Tommy Angelo ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
Andrew, Did you plan to include this new version of glp_simplex in 4.30 ? []'s Haroldo On Tue, Jul 29, 2008 at 10:53 AM, Andrew Makhorin <[EMAIL PROTECTED]> wrote: > >> Probably this happens because your instance is not well conditioned, > >> so due to excessive round-off errors the presolved lp is unbounded > >> while the original lp is not. > > What does "not well conditioned" mean? What can I do about it? > > Ill-conditioning means, roughly speaking, that small changes in the > problem data lead to large changes in the solution. > > Your instance in fact is ill conditioned. Glpsol 4.29 gives optimal > value 12, where all KKT optimality conditions are satisfied: > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err. = 4.72e-12 on row 95 >max.rel.err. = 4.72e-12 on row 95 >High quality > > KKT.PB: max.abs.err. = 7.88e-10 on column 237 >max.rel.err. = 7.88e-10 on column 237 >High quality > > KKT.DE: max.abs.err. = 1.71e-13 on column 166 >max.rel.err. = 8.53e-14 on column 166 >High quality > > KKT.DB: max.abs.err. = 0.00e+00 on row 0 >max.rel.err. = 0.00e+00 on row 0 >High quality > > However, if I convert your instance in MPS format and then run glpsol, > it crashes: > > spx_simplex: warning: numerical instability (primal simplex, phase II) >583: objval = 1.232678937e+02 infeas = 1.0e+00 (0) >600: objval = 1.357637434e+02 infeas = 6.333149060e-02 (0) > Assertion failed: spx->p != 0 > Error detected in file src\glpspx02.c at line 602 > > Using a newer, more stable version of glp_simplex I managed to solve > your instance; now the optimal value is 170, and KKT conditions are > still satisfied: > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err. = 1.91e-06 on row 181 >max.rel.err. = 1.91e-06 on row 181 >Low quality > > KKT.PB: max.abs.err. = 7.29e-10 on row 86 >max.rel.err. = 7.29e-10 on row 86 >High quality > > KKT.DE: max.abs.err. = 0.00e+00 on column 0 >max.rel.err. = 0.00e+00 on column 0 >High quality > > KKT.DB: max.abs.err. = 0.00e+00 on row 0 >max.rel.err. = 0.00e+00 on row 0 >High quality > > >> > >>> Also neither lpx_adv_basis nor lpx_std_basis > >>> seem to solve the problem from C++ API level. Could anyone please tell > >>> me what I am missing here? > >> > >> Could you provide the code returned by glp_simplex? > > I'm getting > > > PROBLEM HAS UNBOUNDED SOLUTION > > glp_simplex: cannot recover undefined or non-optimal solution > > > and glp_simplex returns 11, i.e. GLP_ENODFS (no dual feasible) > > The lp presolver should be disabled; the reason was explained above. > > > > ___ > Help-glpk mailing list > Help-glpk@gnu.org > http://lists.gnu.org/mailman/listinfo/help-glpk > -- === Haroldo Gambini Santos http://www.ic.uff.br/~hsantos [EMAIL PROTECTED] Instituto de Computacao - Universidade Federal Fluminense ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
> Did you plan to include this new version of glp_simplex in 4.30 ? I plan to replace implementation of the primal simplex by a new version, however, I am not sure about 4.30, because the new routine is still under development. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
On Tue, Jul 29, 2008 at 3:53 PM, Andrew Makhorin <[EMAIL PROTECTED]> wrote: >>> Probably this happens because your instance is not well conditioned, >>> so due to excessive round-off errors the presolved lp is unbounded >>> while the original lp is not. >> What does "not well conditioned" mean? What can I do about it? > > Ill-conditioning means, roughly speaking, that small changes in the > problem data lead to large changes in the solution. > > Your instance in fact is ill conditioned Could anyone perhaps give me some literature pointers (preferrably freely available on the net) on how to achieve this "well-conditioned" situation, or some examples? I was playing a bit with scaling variables and it seems to improve things a bit, but I am probably reinventing the wheel. Sorry if my question is a bit off topic. Thanks Marcin ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpksol default settings
> Could anyone perhaps give me some literature pointers (preferrably > freely available on the net) > on how to achieve this "well-conditioned" situation, or some examples? > I was playing a bit with > scaling variables and it seems to improve things a bit, but I am > probably reinventing the wheel. > Sorry if my question is a bit off topic. NABD. Try aksing your question on: http://groups.google.com/group/sci.op-research/ . ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
