Patches for simplex routines
Chris Matrakidis <[email protected]>
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <CAEaJ3S6_5WjbHRWMJu83bCP1SmvyAUL6ecUCjwpdTbZ8s8y85w@mail.gmail.com> |
Andrew, I'm attaching two patches for the simplex routines. The first one is just your idea [1] for restoring the objective limit check in dual simplex when perturbation is enabled, which considerably improves branch and bound performance. This is just to make sure it is not forgotten. The second patch changes two asserts into errors (one in primal and one in dual). I managed to trigger the second one, but I'm changing the first one just in case. Best Regards, Chris Matrakidis PS. In addition to the patch [2] you mentioned a few days ago, in May I sent another patch as well [3] for an mps reading bug. [1] http://lists.gnu.org/archive/html/help-glpk/2016-04/msg00006.html [2] http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg00006.html [3] http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg00001.html _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
simplex1.patch
(text/x-patch, 832 B)
diff --git a/src/simplex/spydual.c b/src/simplex/spydual.c
index e41baf2..d33ebb1 100644
--- a/src/simplex/spydual.c
+++ b/src/simplex/spydual.c
@@ -1374,13 +1374,15 @@ loop: /* main loop starts here */
check_accuracy(csa);
#endif
/* check if the objective limit has been reached */
-#if PERTURB
- /* FIXME */
- if (!perturb)
-#endif
if (csa->phase == 2 && csa->obj_lim != DBL_MAX
&& spx_eval_obj(lp, beta) >= csa->obj_lim)
- { if (csa->beta_st != 1)
+ { if (perturb)
+ { /* remove perturbation */
+ perturb = 0;
+ memcpy(csa->lp->c, csa->orig_c, (1+n) * sizeof(double));
+ csa->phase = csa->d_st = 0;
+ }
+ if (csa->beta_st != 1)
csa->beta_st = 0;
if (csa->d_st != 1)
csa->d_st = 0;
simplex2.patch
(text/x-patch, 1.5 KB)
diff --git a/src/simplex/spxprim.c b/src/simplex/spxprim.c
index 4a5e7aa..1f4aac8 100644
--- a/src/simplex/spxprim.c
+++ b/src/simplex/spxprim.c
@@ -963,7 +963,13 @@ loop: /* main loop starts here */
else
spx_nt_prod(lp, nt, trow, 1, -1.0, rho);
/* FIXME: tcol[p] and trow[q] should be close to each other */
- xassert(trow[csa->q] != 0.0);
+ if (trow[csa->q] == 0.0)
+ { if (msg_lev >= GLP_MSG_ERR)
+ xprintf("Error: trow[q] == 0.0\n");
+ csa->p_stat = csa->d_stat = GLP_UNDEF;
+ ret = GLP_EFAIL;
+ goto fini;
+ }
/* update reduced costs of non-basic variables for adjacent
* basis */
if (spx_update_d(lp, d, csa->p, csa->q, trow, tcol) <= 1e-9)
diff --git a/src/simplex/spydual.c b/src/simplex/spydual.c
index d33ebb1..c8350d2 100644
--- a/src/simplex/spydual.c
+++ b/src/simplex/spydual.c
@@ -1632,7 +1632,13 @@ loop: /* main loop starts here */
t_pivcol += timer() - t_start;
#endif
/* FIXME: tcol[p] and trow[q] should be close to each other */
- xassert(csa->tcol.vec[csa->p] != 0.0);
+ if (csa->tcol.vec[csa->p] == 0.0)
+ { if (msg_lev >= GLP_MSG_ERR)
+ xprintf("Error: tcol[p] == 0.0\n");
+ csa->p_stat = csa->d_stat = GLP_UNDEF;
+ ret = GLP_EFAIL;
+ goto fini;
+ }
/* update values of basic variables for adjacent basis */
k = head[csa->p]; /* x[k] = xB[p] */
p_flag = (l[k] != u[k] && beta[csa->p] > u[k]);