[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 01:28:36 +0300 |
> 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.
Probably there is some misunderstanding.
"Failure" means that the primal or dual simplex solver is unable to
solve the problem to the end (due to numerical instability, singular
basis matrix, etc.), and the option GLP_DUALP was introduced, since
the primal simplex is more stable that the dual one (in glpk).
However, in your case the dual simplex terminates normally, without
failure, because it has solved the problem to the end.
Note that glp_get_status reports GLP_INFEAS, not GLP_NOFEAS, that
means that the problem probably has a primal feasible solution, however,
such solution was not found by the dual simplex, because it detected
dual infeasibility and thereby proved that no optimal solution exists.
If you need to find a primal feasible solution rather than optimal one,
you should use the primal simplex; the dual simplex can find either an
optimal solution or dual feasible one, and if the latter is non-optimal,
it is always primal infeasible.