[Scip] Computing primal solution after fixing
Andrea Taverna
andrea.taverna at unimi.it
Thu Oct 30 01:03:18 CET 2014
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
More information about the Scip
mailing list