Re: [Bug-glpk] GLPSOL outputs MIP solution that is not LP optimal for fixed integers

[xypron]

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.