[Scip] Computing primal solution after fixing

[Andrea Taverna]

Dear Gerald,

I tried looking for some explanations. In order:

> What timing does your heuristic have?

SCIP_HEURTIMING_DURINGPRICINGLOOP. I want it to be performed after the 
master is solved at every iteration.

> Are you sure
> that the solution is suboptimal?

Well, without running the heuristic it performs more iterations. With 
the heuristic it stops at the first one.

The dual bound at the first iteration coincide in both cases and it's 
lower than the primal solution, which is guaranteed to coincide, at 
first iteration, to the master's continuous relaxation.

> Are all your constraints marked to be
> modifiable?

Only the ones which include column variables. What I change in the 
heuristic are those variables' bounds, which are specified via SCIPcreateVar

> Can you please verify whether your pricer is called again after the
> heuristic finished?

Yes. It is. It also adds ~50 columns at first iteration

> Perhaps also enable LP output by setting
> display/lpinfo to TRUE.

Here (1) you can find the logs with (*_heur) and without heuristic 
(_noheur).
I print some messages from the heuristic and the pricer's callbacks. 
They start with '=>'

(1) =  https://docs.zoho.com/file/otj66b6465cb1c0904f4c84bc6c6dc6f60917


thanks a lot

Best,

Andrea

Il 24/10/2014 11:24, Gerald Gamrath ha scritto:
> Dear Andrea,
>
> this sounds strange. SCIP should not consider the heuristic solution a
> valid dual bound. What timing does your heuristic have? Are you sure
> that the solution is suboptimal? Are all your constraints marked to be
> modifiable?
>
> Can you please verify whether your pricer is called again after the
> heuristic finished? Perhaps also enable LP output by setting
> display/lpinfo to TRUE.
>
> With this, we might be able to locate the problem.
>
> Best,
> Gerald
>
> Am 23.10.2014 um 13:57 schrieb Andrea Taverna:
>>
>> Dear Gerald,
>>
>> thanks for the suggestion. Indeed it seems "more correct" now.
>>
>> In my heuristic I do the following:
>>
>> 1) Check the LP has been solved (SCIP_LPSOLSTAT_OPTIMAL)
>> 2) Call SCIPstartProbing
>> 3) Call SCIPlinkLPSol on my previously allocated SCIP_SOL object to
>> create a working copy
>> 4) Call SCIPgetSolVal on the working copy to read current LP solution's
>> var values
>> 5) Call SCIPchgVar[Ub|Lb]Probing on the variables I want to fix to 1/0
>> 6) Call SCIPpropagateProbing and then SCIPsolveProbiingLP
>> 7 Finally call SCIPtrySol and the SCIPendProbing
>>
>> The program now does find a primal heuristic but it also seems that SCIP
>> considers the heuristic solution as a valid dual bound and thus finds
>> that the two bounds coincide and immediately exists the CG loop.
>>
>> Before the primal heuristic it used to find lower dual bounds than the
>> primal heuristic and the CG continued.
>>
>> Am I missing something in the primal heuristic?
>>
>> TIA
>>
>> Best,
>> Andrea
>>
>>
>> Il 23/10/2014 00:58, Gerald Gamrath ha scritto:
>>> Dear Andrea,
>>>
>>> in SCIP a rounding heuristic basically does the following:
>>> 1) get the current LP solution
>>> 2) round all fractional variables to an integer value
>>> 3) check the resulting solution.
>>>
>>> How step 2 is performed influences the probability to find feasible
>>> solutions and also the running time, that's why there are multiple
>>> heuristics of this kind in SCIP.
>>>
>>> So you are right, no further LPs are solved by the heuristic.
>>>
>>> If you want to fix some variables, then optimize the resulting LP, fix
>>> again, solve the LP, and iterate until you found an integer feasible
>>> solution, you should have a look at the diving heuristics in SCIP, which
>>> all use this scheme.
>>>
>>> Best,
>>> Gerald
>>>
>>>
>>> Am 22.10.2014 um 19:04 schrieb Andrea Taverna:
>>>> Dear all,
>>>>
>>>> I'm a bit confused on how to implement a "rounding" heuristic.
>>>>
>>>> I'm working on a column generation algorithm.
>>>> Basically my heuristic fixes some fractional binary variables to 0/1
>>>> by calling SCIPsetSolVal.
>>>>
>>>> What should I do after those fixings to get a feasible solution?
>>>>
>>>> From the examples, e.g. the TSP one, it seems that no LP solver is
>>>> called explicitly on the working copy of the LP solution to generate a
>>>> feasible solution . There are just calls to functions like SCIPtrySol
>>>> or SCIProundSol.
>>>>
>>>> So, if I understand correctly, SCIP reoptimizes in some way the
>>>> working copy of the LP solution to obtain the actual heuristic
>>>> solution. Is that so?
>>>>
>>>> TIA
>>>>
>>>> Andrea
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>