[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Bug-glpk] Dualp simplex method classifies an unbounded problem as "

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Bug-glpk] Dualp simplex method classifies an unbounded problem as "no primal feasible" |

**Date**: |
Thu, 12 Mar 2009 00:17:00 +0300 |

>* I am testing GLPK 4.36. I tried a test case that I have also used with*
>* GLPK 4.19.*
>* Maximize *
>* 40 * x1 + 60 * x2*
>* subject to*
>* 0 <= x1*
>* 0 <= x2*
>* 70 <= 2 * x1 + x2*
>* 40 <= x1 + x2*
>* 90 <= x1 + 3 * x2*
>* This problem is primal feasible. It is unbounded. *
>* In GLPK 4.19, after running the dualp simplex method (GLP_DUALP), the*
>* solution status is unbounded (GLP_UNBND). This is what I expected.*
>* In GLPK 4.36, after running the dualp simplex method (GLP_DUALP), the*
>* solution status is infeasible (GLP_INFEAS). Why doesn't the code find a*
>* feasible solution?*
Thank you for your report.
This is not a bug. Glpk 4.19 has no phase I dual simplex, so if the
initial basis passed to the simplex solver is dual infeasible, it
automatically switches to the primal simplex, and it detects
unboundedness. In glpk 4.36 the dual simplex implements both phases
I and II, and if you specify GLP_DUALP, the phase I dual simplex attempts
to find a dual feasible solution; it does not exist as your instance is
unbounded, so it reports the status of the last basic solution reached,
which is neither primal nor dual feasible.