[Scip] including a solution found by an heuristic

Gregor Hendel hendel at zib.de
Fri Jun 21 15:22:56 MEST 2013


Hi Alessia,

yes, changing the branching rule can lead to unexspected trouble. :)


Am 21.06.2013 14:58, schrieb Alessia Violin:
> Hello,
>
> thanks to all of you for all the suggestions.
>
> What I have found is:
> Adding the flag OPT=dbg in fact changes things. I have this error
> [src/scip/scip.c:390] ERROR: cannot call method 
> <SCIPgetSolVal(sol==NULL)> in problem solved stage
> [src/scip/scip.c:28742] ERROR: Error <-8> in function call
> just after the problem is solved, when I try to print out the best solution.
Have you seen that there is a method SCIPprintBestSol()?
http://scip.zib.de/doc-2.0.2/html_devel/scip_8c.html#a2d0d56545651587e0becf282706860e0
This releaves you from checking manually which stage you are in.
>
> This made me discover that also the best solution of my whole problem 
> found during the solving (with a default rounding heuristic) is 
> considered not feasible, both from the original and the transformed 
> problem, for instance with the functions  SCIPcheckSol and 
> SCIPcheckSolOrig. Again, even if all the flag of those functions are set 
> to TRUE, I don't get printed any reason of non-feasibility. This 
> solution is still taken as primal bound during the solving and printed 
> out as best solution. I manually checked the values for a couple of 
> small instances, and they are correct.
>
> I added some print inside the function SCIPcheckSol and I get that all 
> those solutions (from default and from my own heuristic) are not 
> satisfying constraints. What is also strange is that even if I set the 
> flag "checkLProws" to false, constraints are still checked... (LP rows 
> are the constraints right?)
This is often not the case. Of course, a standard LP with general linear
constraints normally has such a 1-to-1 correspondence
between rows and constraints. The story changes for constraints with
"initial"-flag set to FALSE. They will enter the LP when violated,
The idea of the constraint handlers is to have a much more flexible tool
than just LP rows to express constraints.
>
> This happens in my problem after I had implemented my own branching rule 
> with a constraint handler, in the previous version when I didn't have a 
> branching rule but I was using the default one (as I was adding 
> additional binary variables) I didn't have this problem and both optimal 
> solutions and solutions found with heuristics were feasible.
Your own constraint handler might render the solution infeasible itself
via the conscheck-callback?
>
> About my heuristic I checked that the solution found and that I would 
> like to add is feasible also for the constraints added at the current 
> node. About the default heuristics I don't know how they work (for my 
> problem the simplerounding heuristics find solutions).
All rounding heuristics work on the LP-rows of the problem. If the
problem contains constraints which are not initial (something similar
might be the case for modifiable constraints) and the constraint has not
yet entered the LP as a row, the rounding heuristics can fail to find
feasible
solutions.

My question: Can you verify whether your own constraints appear in the
LP, and whether the violation is caused by your own constraints?

Cheers,
Gregor
>
> Finally, Valgrind is not pointing out any additional error.
>
> About the output display I have set it to the maximum in my main
> SCIP_CALL( SCIPsetIntParam(scip, "display/verblevel", 5) );
> is it enough?
>
> I hope this might help and that my explanations are clear enough, I am 
> quite confused now,
>
> Alessia
>
>
>
>
>
>
>
> On 06/20/2013 10:40 AM, michael.winkler at zib.de wrote:
>> Hi Alessia,
>>
>>>> - adding #define SCIP_DEBUG to sol.c does not give any additional output
>> At least some output you should see, did you compile SCIP itself with the
>> correct OPT flag (e.g. OPT=dbg)
>>
>> Additionally to what Ambros already said and if you still have no clue
>> what's going on, you can also try valgrind by calling "valgrind yourBinary
>> flags problem". This might show you invalid reads and writes or
>> uninitialized variables during the run. For this purpose you need to
>> compile in dbg mode(, or at least add "-g" flag to the OPTFLAGS).
>>
>> Best, Michael
>>
>>> Hi Alessia,
>>>
>>> this sounds strange and I also don't understand.  I can only recommend
>>> you to add more printf's to SCIPsolCheck() to trace down exactly where
>>> the feasible flag changes to FALSE.
>>>
>>> Ambros
>>>
>>>
>>>
>>> Am 19.06.2013 12:25, schrieb Alessia Violin:
>>>> Hello,
>>>>
>>>> yes, the solution is for the transformed problem, and with the function
>>>> SCIPgetSolTransObj(scip,sol) I get the correct value for the objective
>>>> function in the transformed space, or with SCIPgetSolOrigObj(scip,sol)
>>>> in the original space.
>>>>
>>>> I tried your suggestions:
>>>> - adding #define SCIP_DEBUG to sol.c does not give any additional output
>>>> - printing out the return of solOfInterest() in SCIPprimalTrySolFree()
>>>> gives me TRUE. Then I tried to add another printf to check the value
>>>> "feasible" after the call of SCIPsolCheck and I get FALSE, so I suppose
>>>> the problem is here, but I don't understand as I don't get any printing
>>>> of violating constraints/bounds etc and I checked that it's better than
>>>> the current one and feasible.
>>>>
>>>> Thanks again,
>>>>
>>>> best,
>>>>
>>>> Alessia
>>>>
>>>>
>>>>
>>>>
>>>> On 06/18/2013 05:37 PM, Ambros Gleixner wrote:
>>>>> Hi Alessia,
>>>>>
>>>>> I suppose the solution lives in the transformed problem, does it?
>>>>>
>>>>> Maybe you can get some additional information if you add
>>>>>
>>>>> #define SCIP_DEBUG
>>>>>
>>>>> at the very top of src/scip/sol.c and recompile.  If not, you could
>>>>> add a manual debug printf to SCIPprimalTrySolFree() in primal.c to see
>>>>> whether solOfInterest() returns TRUE.
>>>>>
>>>>> Ambros
>>>>>
>>>>>
>>>>>
>>>>> Am 18.06.2013 16:59, schrieb Alessia Violin:
>>>>>> Hello,
>>>>>>
>>>>>> I am trying to implement a simple heuristic into my branch-and-price,
>>>>>> and I am having some troubles when adding the new solution found with
>>>>>> the function SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, TRUE,
>>>>>> &success).
>>>>>>
>>>>>> The "success" parameter after this call is always false, even if I
>>>>>> don't
>>>>>> get any violation of constraints/bounds etc printed out. I also
>>>>>> manually
>>>>>> checked the solution found by the heuristic, and it's feasible, not
>>>>>> violating the branching constraints in the current node, and better
>>>>>> that
>>>>>> the current primal bound. So I don't know where/what to search more to
>>>>>> avoid this and to make scip using this new solution...
>>>>>>
>>>>>> If needed I can of course provide more details on my implementation.
>>>>>>
>>>>>> Thanks in advance for any help,
>>>>>>
>>>>>> best,
>>>>>>
>>>>>> Alessia
>>>>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>



More information about the Scip mailing list