[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] good enough solution

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] good enough solution |

**Date**: |
Mon, 5 Jun 2006 21:28:05 +0400 |

>* 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