RE: [Bug-glpk] Dualp simplex method classifies an unbounded problem as "no primal feasible"

[Price, David T]

The documentation says:
GLP_PRIMAL-use two-phase primal simplex;
GLP_DUAL -use two-phase dual simplex;
GLP_DUALP -use two-phase dual simplex, and if it fails, switch to the
primal simplex.

Your point is that the dual simplex has solved the dual problem--the
dual problem is infeasible. That is what I thought GLP_DUAL meant.

I read the documentation differently. 
GLP_PRIMAL will solve the primal problem.
GLP_DUAL will solve the dual problem. 
GLP_DUALP will solve the dual problem. If that solution to the dual
problem is insufficient to solve the primal problem, it will then switch
to the primal simplex. When it is done, primal and dual status will both
be known.

You should change the documentation to read:

GLP_DUALP -use two-phase dual simplex, and if it fails to solve the dual
problem, switch to the primal simplex.

-----Original Message-----
From: Andrew Makhorin [mailto:address@hidden 
Sent: Wednesday, March 11, 2009 4:23 PM
To: Price, David T
Cc: address@hidden
Subject: Re: [Bug-glpk] Dualp simplex method classifies an unbounded
problem as "no primal feasible"

>> 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.

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 feasible
solution.