[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