[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] Dualp simplex method classifies an unbounded problem as "
Re: [Bug-glpk] Dualp simplex method classifies an unbounded problem as "no primal feasible"
Thu, 12 Mar 2009 00:22:58 +0300
>> I am testing GLPK 4.36. I tried a test case that I have also used with
>> GLPK 4.19.
>> 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.
You may check the dual status reported by glp_get_dual_stat, which
must be GLP_NOFEAS in your case (no dual feasible solution exists);
that means that the problem is either unbounded or has no primal