Hello Andrew, please, find appended a patch that resolves the following issues: * The feasibility pump sets a heuristic solution where the non integers are not set to optimal values with respect to the original objective function. * When the feasibility pump reaches a new integral solution, a constraint is added to increment the objective by 10 % which may be more than the gap to the LP solution.
Best regards Xypron http://www.nabble.com/file/p25872393/glpios10.tar.gz glpios10.tar.gz --- glpk/glpk/trunk/glpk-4.39/src/glpios10.c 2009/10/10 09:46:56 470 +++ glpk/glpk/branches/glpk-4.39-fpump/src/glpios10.c 2009/10/13 12:41:25 478 @@ -74,7 +74,7 @@ GLPCOL *col; glp_smcp parm; int j, k, new_x, nfail, npass, nv, ret, stalling; - double dist, tol; + double best, dist, tol; xassert(glp_get_status(P) == GLP_OPT); /* this heuristic is applied only once on the root level */ if (!(T->curr->level == 0 && T->solved == 1)) goto done; @@ -137,16 +137,13 @@ bound to the original objective function; note that this additional constraint is not violated at the optimal point to LP relaxation */ + bnd = .1 * P->obj_val + .9 * best; + if (T->parm->msg_lev >= GLP_MSG_ALL) + xprintf ("Trying to exceed %f\n",bnd); if (P->dir == GLP_MIN) - { bnd = P->mip_obj - 0.10 * (1.0 + fabs(P->mip_obj)); - if (bnd < P->obj_val) bnd = P->obj_val; glp_set_row_bnds(lp, lp->m, GLP_UP, 0.0, bnd - P->c0); - } else if (P->dir == GLP_MAX) - { bnd = P->mip_obj + 0.10 * (1.0 + fabs(P->mip_obj)); - if (bnd > P->obj_val) bnd = P->obj_val; glp_set_row_bnds(lp, lp->m, GLP_LO, bnd - P->c0, 0.0); - } else xassert(P != P); } @@ -270,6 +267,34 @@ { x[j] = lp->col[j]->prim; if (P->col[j]->kind == GLP_IV) x[j] = floor(x[j] + 0.5); } + /* reset direction and right hand side of objective */ + lp->c0 = P->c0; + lp->dir = P->dir; + /* fix integer variables */ + for (k = 1; k <= nv; k++) + { lp->col[var[k].j]->lb = x[var[k].j]; + lp->col[var[k].j]->ub = x[var[k].j]; + lp->col[var[k].j]->type = GLP_FX; + } + /* copy original objective function */ + for (j = 1; j <= n; j++) + lp->col[j]->coef = P->col[j]->coef; + /* solve original LP and copy result */ + ret = glp_simplex(lp, &parm); + if (ret != 0) + { if (T->parm->msg_lev >= GLP_MSG_ERR) + xprintf("Warning: glp_simplex returned %d\n", ret); + goto done; + } + ret = glp_get_status(lp); + if (ret != GLP_OPT) + { if (T->parm->msg_lev >= GLP_MSG_ERR) + xprintf("Warning: glp_get_status returned %d\n", ret); + goto done; + } + for (j = 1; j <= n; j++) + if (P->col[j]->kind != GLP_IV) x[j] = lp->col[j]->prim; + best = lp->obj_val; ret = glp_ios_heur_sol(T, x); xfree(x); if (ret == 0) -- View this message in context: http://www.nabble.com/GLPSOL-outputs-MIP-solution-that-is-not-LP-optimal-for-fixed-integers-tp25337983p25872393.html Sent from the Gnu - GLPK - Bugs mailing list archive at Nabble.com. _______________________________________________ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk