[Coin-discuss] feeding Symphony solutions on the fly

[Ted Ralphs]

Michael Hennebry wrote:

>>I have added the ability for a user to apply primal heuristics and
>>generate solutions on the fly by adding an additional argument to the
>>callback function user_is_feasible(). Check the file
>>Template/LP/user_lp.c for the following function stub:
>>
>>int user_is_feasible(void *user, double lpetol, int varnum,
>>                      int *indices, double *values, int *feasible,
>>                      double *objval, char branching,
>>                      double *heur_solution)
>>{
>>}
>>
>>The relaxed solution is passed in sparse format, as before, through the
>>arrays arguments indices[] and values[]. If the relaxed solution is
>>found to be infeasible, it can be rounded or otherwise perturbed to
>>produce a new feasible solution.  If such a solution is found, it can be
>>passed back to SYMPHONY in the array heur_solution[]. You also need to
>>set *objval to the value of the solution in this case, as well as setting
> 
> 
> Is the array in dense format?

Yes, the array is in dense format.

> 
>>*feasible = IP_HEUR_FEASIBLE;
> 
> 
> I think we have a data flow problem here.
> Unless the new objective value is at most the old,
> user_is_feasible still should give an indication of
> whether the passed in data is feasible.

I made the implicit assumption that if the passed-in solution is 
feasible, the user will indicate this by setting

*feasible = IP_FEASIBLE;

and will not additionally generate a heuristic solution, since the 
passed-in solution must be optimal for the subproblem in that case. It 
is possible that the user would be able to use the feasible solution to 
generate a better heuristic solution (which would have to be infeasible 
for the current subproblem). This is actually OK, though, as long as the 
return value from user_is_feasible() is USER_SUCCESS. The user can still 
set

*feasible = IP_HEUR_FEASIBLE;

and set *objval to the value of the solution found and SYMPHONY should 
accept this solution, even though the objective value differs from that 
found by solving the LP relaxation. The only situation in which there 
could be a problem would be if the passed-in solution is feasible *and* 
the the user generates a heuristic solution *and* the user also requests 
SYMPHONY to determine whether the solution is feasible by returning 
USER_DEFAULT from user_is_feasible(). From the user's perspective, the 
solution is to always return USER_SUCCESS if a heuristic solution is 
found. I will put in a sanity check to make sure the user is doing this.

>>If you determine that the solution SYMPHONY passed is feasible as it is,
>>then simply set
>>
>>*feasible = IP_FEASIBLE;
>>
>>Even in this case, you can set the objective function value to the true
>>value if desired to account for roundoff error. Note that SYMPHONY has
>>two built-in primal heuristics (adapted from CBC) that can be run by
>>setting the parameter "do_primal_heuristic" to TRUE. If you do a CVS
>>update, you should see these changes. Note that this is not very well
>>tested yet. Please give it a try and let me know if you run into any
>>problems.
> 
> 
> What happends if I do a CVS update in a copy of Template, say one named Tsp05?

In theory, it should just make the proper updates, even though you have 
modified the template functions, as long as you haven't modified the 
original function templates themselves.

Cheers,

Ted
-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2

"An optimist is someone who thinks
'It doesn't get any better than this.'
A pessimist is someone who's afraid that's true."