[Scip] including a solution found by an heuristic

Alessia Violin aviolin at ulb.ac.be
Fri Jun 21 16:36:45 MEST 2013


Hello,

it was a problem in the conscheck-callback of my constraint handler for 
the branching, it was not checking the correct solution (the NULL one so 
the LP, instead of the actual one passed as a parameter), so it was him 
saying that solutions were not feasible.

Thanks a lot for all your suggestions and explanations, even if the 
problem was quite banal at the end, I understood much more about how 
scip is working and I fixed some more details in my code.

Have a nice weekend,

Alessia



On 06/21/2013 03:57 PM, michael.winkler at zib.de wrote:
> Hi Alessia,
>
>> 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.
>>
> when you set ask for solution values with "sol==NULL", this means you want
> to have solution values for the LP or pseudo solution. In solving stage no
> such solution exist. If you want to print the best solution you can use
> SCIPprintBestSol() or SCIPprintSol() for printing and SCIPgetBestSol() for
> getting the best solution.
>
>> 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.
>>
> Are you sure that you gave the correct solution to SCIPcheckSol() and
> SCIPcheckSolOrig()? Sorry I have no clue why nothing is printed, is it
> possible that your own constraint handler is not accepting the solution
> and does not print anything?
>
>> 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?)
>>
> What kinds of constraint were not satisfied?
> In SCIP there is no one to one relationship between constraints and rows,
> one constraint can have multiple rows or even no row at all. In the
> standard MIP case one constraint corresponds to one row, but this row does
> not need to be in the current LP. Therefore, "checklprows" set to false
> does not avoid checking constraints. Checking constraints is always
> mandatory to check a solution and therefore cannot be disabled. (If some
> constraint knows that all its information is in the current LP, meaning
> that the row(s) guarantee feasibility, then the constraint handler does
> not need to check this constraint if the "checklprows" was set to false.)
>
>> 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.
>>
>> 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).
>>
>> 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?
>>
> This gives you more information, but probably does not really help you to
> trigger your problem. Hopefully, you might have another idea to finding
> the issue.
>
> Best, Michael
>
>> 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
>>>>
>> --
>> Alessia Violin
>> Service Graphes et Optimisation Mathématique (G.O.M.)
>> Université Libre de Bruxelles
>> C.P. 210/01
>> Boulevard du Triomphe
>> B-1050 BRUXELLES
>> Tel: 02 650 58 80 - Fax: 02 650 59 70
>> Email: aviolin at ulb.ac.be
>> Webpage: http://homepages.ulb.ac.be/~aviolin/
>>
>>

-- 
Alessia Violin
Service Graphes et Optimisation Mathématique (G.O.M.)
Université Libre de Bruxelles
C.P. 210/01
Boulevard du Triomphe
B-1050 BRUXELLES
Tel: 02 650 58 80 - Fax: 02 650 59 70
Email: aviolin at ulb.ac.be
Webpage: http://homepages.ulb.ac.be/~aviolin/



More information about the Scip mailing list