Re: [Help-glpk] record_solution
> 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 > http://www.ncc.up.pt/~jpp/mipts). > > 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). ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] record_solution
> Sorry, I did not mention the context of this use of record_solution; I > was writing a version to call after fixing some integer variables with > some heuristics, and doing a branch-and-bound on the remaining. So it > seems that I need to use lpx_get_mip_val, and also lpx_mip_col_val and > lpx_mip_row_val for accessing the variables. An integer feasible solution found with a primal heuristic should be stored in the same way as record_solution does: tree->found = 1; tree->best = ; tree->mip[1,...,m] = ; tree->mip[m+1,...,m+n] = ; Routines lpx_mip_col_val and lpx_mip_row_val should not be used within mip_driver, because corresponding data are copied to the problem object after the search has been finished. During the search these data are available in tree->best and tree->mip and can be accessed directly. Fixing variables should be performed in the same way as fix_by_red_cost does. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] record_solution
> > I am writing a version of the "record_solution" function, defined in > > glpmip2.c, and I got confused; shouldn't the line > > tree->best = lpx_get_obj_val(lp); > > be replaced by > > tree->best = lpx_get_mip_val(lp); > > as we are dealing with MIPs? > > The correct line is the following: > >tree->best = lpx_get_obj_val(lp); > > because the best known MIP solution is optimal solution of LP > relaxation (which lp points to) corresponding to a node of the > b&b tree. Sorry, I did not mention the context of this use of record_solution; I was writing a version to call after fixing some integer variables with some heuristics, and doing a branch-and-bound on the remaining. So it seems that I need to use lpx_get_mip_val, and also lpx_mip_col_val and lpx_mip_row_val for accessing the variables. Thank you, Pedro ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] record_solution
> I am writing a version of the "record_solution" function, defined in > glpmip2.c, and I got confused; shouldn't the line > tree->best = lpx_get_obj_val(lp); > be replaced by > tree->best = lpx_get_mip_val(lp); > as we are dealing with MIPs? The correct line is the following: tree->best = lpx_get_obj_val(lp); because the best known MIP solution is optimal solution of LP relaxation (which lp points to) corresponding to a node of the b&b tree. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] record_solution
Hello, I am writing a version of the "record_solution" function, defined in glpmip2.c, and I got confused; shouldn't the line tree->best = lpx_get_obj_val(lp); be replaced by tree->best = lpx_get_mip_val(lp); as we are dealing with MIPs? Thank you, Pedro ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk