[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] record_solution

From: Andrew Makhorin
Subject: Re: [Help-glpk] record_solution
Date: Thu, 19 Jan 2006 23:09:30 +0300

> I have been using the GLPK software on some programs with heuristics
> for MIP.  I fix some integer variables with the heuristics, and
> determine the remaining and the continuous ones with lpx_integer (I
> have put a tabu search software based in this approach on
> Currently, I am fixing the variables with the api routines,
> lpx_set_col_bnds, and using lpx_integer for determining the other (not
> fixed) variables.
> As in many cases the heuristic quickly finds a feasible solution, I
> have been considering writing another version of lpx_integer that
> would take as an additional argument the currently best found solution
> (if some feasible solution has been found).  This could be used for
> the purpose of stopping the search if there is no hope of finding an
> improving solution, for the current setting of fixed variables.

Yes, this feature should be definitely added. I think there should be
a control parameter, say, LPX_K_MIPOBJ, which specifies an incumbent
objective value corresponding to an integer feasible solution found by
a primal heuristic.

> My first tentative did not meet my needs: I was writing the best found
> solution on tree->found, tree->best, and tree->mip, but that was (of
> course!) returned as the optimal solution for the current setting.
> Instead, I would need a function which would return something like
> LPX_I_BNDED, together with the best bound for the current setting of
> fixed variables, as soon as the best bound for this setting is worse
> that the solution supplied (and hence we are sure that no improving
> solution can be found).
> Do you have any advice for its implementation?

You can set tree->best to a value which is a bit worse (greater) than
the objective value detected by heuristic.

> Any comment from you would be very welcome.
> One more question: is it safe to use the new lpx_intopt instead of
> lpx_integer when some variables have been fixed?

Yes, it is completely compatible with lpx_integer (with the only
exception that it does not require optimal basis of LP relaxation).

reply via email to

[Prev in Thread] Current Thread [Next in Thread]