[Scip] Setting a primal heuristic solution
Rostislav Stanek
rostislav.stanek at uni-graz.at
Wed Aug 7 17:29:50 MEST 2013
Dear Gerald,
thank you very much again. The program works now well and is much faster
then without setting the heuristic (optimal) initial solution ... :-)
Thanks again.
Best regards,
Rostislav
Dne 7.8.2013 17:21, Gerald Gamrath napsal(a):
> Dear Rostislav,
>
> 1) There are some differences between original and transformed
> solutions, but if you add any of those, the primal bound will be updated
> if the solution is feasible and better than the incumbent. Thus, if your
> heuristic provides the optimal solution, SCIP only needs to prove its
> optimality, so this should normally speed up the solving process. The
> drawback of an original solution is that it won't be used by SCIP's
> improvement heuristics, because they run in the transformed space where
> the solution is not feasible. For optimal solutions, however, this
> should be no problem. :-)
>
> 2) Yes, you can use SCIPsetSolVal() and SCIPtrySolFree() in the same way
> as before. However, for an original solution, you can only set the
> values of original variables by SCIPsetSolVal(). This means, the
> variables that you created in the beginning (or SCIP created when you
> read the instance file). You can get these variables by
> SCIPgetOrigVars() and SCIPgetNOrigVars(), but I guess you somehow stored
> you variables and their meaning at the beginning? Normally, you should
> replace the original variables by the transformed ones using
> SCIPtransformVar() or SCIPtransformVars() at some point, but in this
> special case, you should also keep the original ones.
>
> Best,
> Gerald
>
> On 07.08.2013 17:06, Rostislav Stanek wrote:
>> Dear Gerald and Timo,
>> I thank you for your response. I use no constraint handler and all my
>> constraints are linear. But of course it is possible that SCIP
>> recognise that an optimal solution exists in which the variable is set
>> on an other value than I want to set (in fact, the problem occurs more
>> often if there exist many optimal solutions). I will try to use
>> SCIPcreateOrigSol(), but I have 2 question to this function:
>> 1) If the solution I set is not valid in the transformed space, can I
>> speed up the solving process by setting the optimal solution in this
>> way (in fact, the solutions I find in a heuristic are usually (but not
>> always) optimal and I want that SCIP prove the optimality of find a
>> better solution).
>> 2) If I use the SCIPcreateOrigSol() (and not SCIPcreateSol()) method,
>> can I then use SCIPsetSolVal() and SCIPtrySolFree() methods in the
>> same way as I did?
>> Thank you again for your response.
>> Best regards,
>> Rostislav
>>
>>
>> Dne 7.8.2013 16:56, Gerald Gamrath napsal(a):
>>> Hi Rostislav,
>>>
>>> your issue is quite similar to the one by Daniel discussed on the
>>> mailing list yesterday. If you create a solution during solving by
>>> SCIPcreateSol(), this solution is defined on the active problem
>>> variables and you should only set values for those.
>>> In your case, presolving did some reductions, in particular fixed
>>> x#14#13 to 0. This is probably a dual reduction, so SCIP detected that
>>> there is at least one optimal solution with this variable set to 1.
>>>
>>> It sounds like your heuristic works on the original problem and does not
>>> take into account presolving reductions. If this is the case, you should
>>> create a solution in the original space via SCIPcreateOrigSol(), see
>>> http://scip.zib.de/doc/html/scip_8h.shtml#a84ea192b17b635835e7841762e3281ba
>>>
>>> When you do this, you should set the solution values of the original
>>> variables for this solution. By this, you can ignore any changes on
>>> variables done by presolve, e.g., fixings or (multi)aggregations.
>>>
>>> Best,
>>> Gerald
>>>
>>> On 07.08.2013 16:29, Rostislav Stanek wrote:
>>>> Dear SCIP community,
>>>> I use an initial heuristics which should set an initial solution and
>>>> which is called only once before starting the branching process. I call
>>>> the inherited constructor of the class ObjHeur in the constructor
>>>> definition of my class in the following way:
>>>>
>>>> InitialTourHeuristic::InitialTourHeuristic(
>>>> [my parameters]):
>>>> ObjHeur(
>>>> sCIP,
>>>> [name],
>>>> [description],
>>>> 'I',
>>>> -1000000,
>>>> 0,
>>>> 0,
>>>> 0,
>>>> SCIP_HEURTIMING_BEFORENODE,
>>>> false),
>>>> [other initialisations] {
>>>> [constructor body]
>>>> }.
>>>>
>>>> Then I define
>>>>
>>>> virtual SCIP_DECL_HEUREXEC(scip_exec);
>>>>
>>>> and
>>>>
>>>> SCIP_DECL_HEUREXEC(InitialTourHeuristic::scip_exec) {
>>>> [constructor body]
>>>> }.
>>>>
>>>> Further, I have the initialised references on the variables
>>>>
>>>> std::vector<std::vector<SCIP_VAR *> > &x;.
>>>>
>>>> In the body of the last method I set the solution in the following way:
>>>>
>>>> SCIP_CALL_EXC(SCIPcreateSol(sCIP, &heuristicSolutionSCIP, 0));
>>>>
>>>> [...]
>>>>
>>>> for ([a for cyclus]) {
>>>> SCIP_CALL_EXC(SCIPsetSolVal(
>>>> sCIP,
>>>> heuristicSolutionSCIP,
>>>> x.at([an index]).at([an index]),
>>>> 1));
>>>> }
>>>>
>>>> [...]
>>>>
>>>> SCIP_Bool isTheSolutionFeasible;
>>>> SCIP_CALL_EXC(SCIPtrySolFree(
>>>> sCIP,
>>>> &heuristicSolutionSCIP,
>>>> true,
>>>> true,
>>>> true,
>>>> false,
>>>> &isTheSolutionFeasible));.
>>>>
>>>> And the solving process usually works. But sometimes I get the
>>>> following
>>>> error:
>>>>
>>>> [src/scip/sol.c:921] ERROR: cannot set solution value for variable
>>>> <t_x#14#13> fixed to -0 to different value 1
>>>> [src/scip/scip.c:28611] ERROR: Error <-9> in function call
>>>> An error occurs by computing and by using the SCIP tool!
>>>>
>>>> What I am doing wrong? I am sure that the solution I set is
>>>> feasible; in
>>>> fact it is an (maybe not unique) optimal solution.
>>>>
>>>> Thank you for all your tips.
>>>>
>>>> Yours faithfully,
>>>> Rostislav Stanek
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> http://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list