Re: [Help-glpk] good enough solution

[Andrew Makhorin]

> I have been using glpsol to solve various integer
> programs.  It is often hard for the program to 
> prove it has found the optimal solution, but on 
> the other hand I can often use any integer 
> solutions which is "good enough", i.e. has a high 
> or low enough value of the objective fuctions. 
> However, if I  add a cutting plane which just 
> cuts off the polytope at a given value of the 
> objective function the  solver tends to get less 
> efficient.
> 
> Is there some simple way to modify glpsol so that 
> it outputs a solution to an integer program once 
> it has found a solution with a given vaöue of the 
> objective function?

You can change the following fragment (file glpmip2.c, lines 1014-23,
function mip_driver):

      /* if the basic solution satisfies to all integrality conditions,
         it is a new, better integer feasible solution */
      if (tree->curr->ii_cnt == 0)
      {  if (tree->msg_lev >= 3)
            print("New integer feasible solution found");
         record_solution(tree);
         if (tree->msg_lev >= 2) show_progress(tree);
+++      /* check if the desired objective value has been reached */
+++      if (tree->best <= desired_value)
+++      {  ret = MIP_E_TMLIM;
+++         goto done;
+++      }
         /* the current subproblem is fathomed; prune its branch */
         goto fath;
      }

The lines to be added are marked by '+++'. Here tree->best is the
objective value corresponding to the most recent integer feasible
solution. Desired value should be passed from outside as an extern
variable.

Andrew Makhorin