[Scip] Fwd: Re: Computing primal solution after fixing
Andrea Taverna
andrea.taverna at unimi.it
Wed Nov 5 17:03:38 CET 2014
-------- Messaggio originale --------
Oggetto: Re: [Scip] Computing primal solution after fixing
Data: Fri, 31 Oct 2014 19:35:39 +0100
Mittente: Andrea Taverna <andrea.taverna at unimi.it>
Organizzazione: Università degli Studi di Milano
A: Gerald Gamrath <gamrath at zib.de>
Dear Gerald,
thanks a lot. Indeed that seems to solve the problem on my tests.
Best regards,
Andrea
Il 31/10/2014 18:12, Gerald Gamrath ha scritto:
> Dear Andrea,
>
> I think I found a bug in SCIP that might cause the trouble.
>
> Can you please modify tree.c, line 6308 (in the SCIP 3.1 sources)
> from
> else if( tree->focuslpconstructed && SCIPlpIsRelax(lp) )
> to
> else if( tree->focuslpconstructed && SCIPlpIsRelax(lp) &&
> SCIPprobAllColsInLP(transprob, set, lp) )
> and try whether this helps.
>
> It looks like nobody ever did a diving heuristic with timing
> SCIP_HEURTIMING_DURINGPRICINGLOOP before. :-) Independently of the bug,
> I would recommend to check whether you really want to run your heuristic
> with that timing, because as the timing is called quite often, it was
> supposed to be mainly for very fast heuristics.
>
> Please tell me about your experience with the fix.
>
> Best,
> Gerald
>
>
> Am 30.10.2014 um 01:03 schrieb Andrea Taverna:
>> Dear SCIP Mailing List members,
>>
>> let me first thank those who tried to solve the issue.
>>
>> I tried to recompile the program with SCIP 3.0.1 to see if it was due
>> to some mysterious bug, but the problem is still there
>>
>> I hope the logs provided were comprehensible.
>>
>> I still can't come up with an explanation for this strange behavior.
>>
>> Here I attach the implementation of the heuristic and the pieces of
>> the program's main where it is initialized and added to the SCIP
>> object. Hope it helps.
>>
>> Best regards,
>>
>> Andrea
>>
>>
>> -------%<-------%<-------%<-------%<-------%<-------%<-------%<-------%<-------%<
>>
>> //----- Heuristic implementation (*.cpp)
>> // EXPLANATION: columns represent plants' scheduling. We have F
>> different plants. Each plant has a set of columns.
>> // The rounding heuristics chooses for each plant f the highest prized
>> scheduling, i.e. the column with the binary selection variable alpha
>> at hightest fractional value in the master relaxation solution, fixing
>> it to one, while others, for the same plant, are fixed to 0.
>> // The solution thus obtained is guaranteed to be feasible.
>>
>> #include "UCPPrimal.h"
>>
>>
>> using namespace ucp;
>> using namespace std;
>>
>>
>> /*
>> * Local methods
>> */
>>
>>
>> /*
>> * Callback methods of primal heuristic
>> */
>>
>> void UCPPrimal::init (UCPData *_data, MasterSolver* _solver) {
>> data = _data;
>> solver = _solver;
>> }
>>
>> /** destructor of primal heuristic to free user data (called when SCIP
>> is exiting) */
>> SCIP_DECL_HEURFREE(UCPPrimal::scip_free)
>> {
>> return SCIP_OKAY;
>> }
>>
>> /** initialization method of primal heuristic (called after problem
>> was transformed) */
>> SCIP_DECL_HEURINIT(UCPPrimal::scip_init)
>> {
>>
>> /* create heuristic data */
>> SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
>>
>> assert(data != NULL);
>>
>> return SCIP_OKAY;
>> }
>>
>> /** deinitialization method of primal heuristic (called before
>> transformed problem is freed) */
>> SCIP_DECL_HEUREXIT(UCPPrimal::scip_exit)
>> {
>> /* free everything which was created in scip_init */
>> SCIP_CALL( SCIPfreeSol(scip, &sol) );
>>
>> return SCIP_OKAY;
>> }
>>
>> /** solving process initialization method of primal heuristic (called
>> when branch and bound process is about to begin)
>> *
>> * This method is called when the presolving was finished and the
>> branch and bound process is about to begin.
>> * The primal heuristic may use this call to initialize its branch and
>> bound specific data.
>> *
>> */
>> SCIP_DECL_HEURINITSOL(UCPPrimal::scip_initsol)
>> {
>> return SCIP_OKAY;
>> }
>>
>> /** solving process deinitialization method of primal heuristic
>> (called before branch and bound process data is freed)
>> *
>> * This method is called before the branch and bound process is freed.
>> * The primal heuristic should use this call to clean up its branch
>> and bound data.
>> */
>> SCIP_DECL_HEUREXITSOL(UCPPrimal::scip_exitsol)
>> {
>> return SCIP_OKAY;
>> }
>>
>> /** execution method of primal heuristic */
>> SCIP_DECL_HEUREXEC(UCPPrimal::scip_exec)
>> { /*lint --e{715}*/
>> SCIP_Bool success;
>> int alphaBest;
>> double maxAlpha;
>> unsigned int cutoff;
>> unsigned int lperror;
>> unsigned int retstat;
>> list<Column*>::const_iterator it;
>>
>> *result = SCIP_DIDNOTRUN;
>> printf("\n=>Primal Heuristic called.\n");
>>
>> /* only call heuristic, if an optimal LP solution is at hand */
>> // if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
>> return SCIP_OKAY;
>>
>> SCIP_CALL( SCIPstartProbing(scip) );
>>
>> /* copy the current LP solution to the working solution */
>> SCIP_CALL( SCIPlinkLPSol(scip, sol) );
>>
>> *result = SCIP_DIDNOTFIND;
>>
>> // choose which variables to set to 1
>> for(f = 0; f < data->F, f++) {
>> maxAlpha = 0;
>> for(it = solver->cols[f].begin(); it != solver->cols[f].end();
>> ++it) {
>> if (SCIPgetSolVal(scip, sol, (*it)->var) > maxAlpha) {
>> maxAlpha = SCIPgetSolVal(scip, sol,(*it)->var);
>> };
>> };
>> alphaBest = -1;
>> for(it = solver->cols[f].begin(); it != solver->cols[f].end();
>> ++it) {
>> if (SCIPgetSolVal(scip, sol, (*it)->var) == maxAlpha) {
>> alphaBest = (*it)->idx;
>> break;
>> };
>> };
>> // change variables
>> for(it = solver->cols[f].begin(); it != solver->cols[f].end();
>> ++it) {
>> if ((*it)->idx == (alphaBest+5 % solver->cols[f].size())) {
>> SCIP_CALL( SCIPchgVarLbProbing(scip, (*it)->var, 1.0));
>> } else {
>> // SCIP_CALL(SCIPsetSolVal(scip, sol, (*it)->var, 0.0));
>> SCIP_CALL( SCIPchgVarUbProbing(scip, (*it)->var, 0.0));
>> };
>> };
>> };
>> // compute new solution
>>
>> // SCIP_CALL( SCIProundSol(scip, sol, &success) );
>> SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
>> if( !cutoff )
>> {
>> retstat = SCIPsolveProbingLP(scip, -1, &lperror, &cutoff);
>> if( retstat != SCIP_OKAY )
>> {
>> SCIPwarningMessage(scip, "Error while solving LP in Fracdiving
>> heuristic; LP solve terminated with code <%d>\n",retstat);
>> }
>> };
>> // add it to SCIP
>> SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE,
>> &success) );
>> if( success ) {
>> *result = SCIP_FOUNDSOL;
>> printf("=> Heuristic successfully completed. New sol = %g",
>> SCIPgetSolOrigObj(scip, sol));
>> };
>> printf("\n");
>> SCIP_CALL ( SCIPendProbing(scip));
>>
>> return SCIP_OKAY;
>> }
>>
>> /** clone method which will be used to copy a objective plugin */
>> SCIP_DECL_HEURCLONE(scip::ObjCloneable* UCPPrimal::clone)
>> {
>> return new UCPPrimal(scip);
>>
>> }
>>
>> //--- Usage in main
>> int main (...){
>> ...
>> UCPPrimal heur (scip, "BestCol", "UCP rounding heuristic", 'U',
>> 1000000, 0, 0, -1,
>> SCIP_HEURTIMING_DURINGPRICINGLOOP);//|SCIP_HEURTIMING_BEFORENODE);
>> ..
>> heur.init(&data, &master);
>>
>> ...
>> SCIP_CALL( SCIPincludeMyPlugins(scip));
>> SCIP_CALL( SCIPreadParams(scip, argv[5]) );
>> SCIP_CALL( SCIPincludeObjHeur(scip, &heur, FALSE) );
>> ..
>> SCIP_CALL( SCIPcreateObjProb( scip, "UCP", &master, 0 ) );
>> ...
>> SCIP_CALL(SCIPsolve(scip));
>> }
>>
>>
>> -------%<-------%<-------%<-------%<-------%<-------%<-------%<
>>
>> Il 24/10/2014 17:43, Andrea Taverna ha scritto:
>>> 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
>>>>
>>>
>>> _______________________________________________
>>> 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
>
More information about the Scip
mailing list