[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? David T. Price (david.t.pr...@bankofamerica.com) Principal Global Markets Group Analytics US Bank of America, Chicago 312-234-2519 ___ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk
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. ___ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk
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. ___ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk
RE: [Bug-glpk] Dualp simplex method classifies an unbounded problem as no primal feasible
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:m...@gnu.org] Sent: Wednesday, March 11, 2009 4:23 PM To: Price, David T Cc: bug-glpk@gnu.org 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. ___ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk
Re: [Bug-glpk] Dualp simplex method classifies an unbounded problem as no primal feasible
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. ___ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk
