50 #define HEUR_NAME "sdprand" 51 #define HEUR_DESC "randomized rounding heuristic for SDPs" 52 #define HEUR_DISPCHAR '~' 53 #define HEUR_PRIORITY -1001000 55 #define HEUR_FREQOFS 0 56 #define HEUR_MAXDEPTH -1 57 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 58 #define HEUR_USESSUBSCIP FALSE 65 #define DEFAULT_NROUNDS 2 66 #define DEFAULT_GENERALINTS FALSE 67 #define DEFAULT_RANDSEED 211 74 SCIP_RANDNUMGEN* randnumgen;
75 SCIP_Bool generalints;
87 assert(
scip != NULL );
88 assert( heur != NULL );
89 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
101 SCIP_HEURDATA* heurdata;
103 assert( heur != NULL );
104 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
105 assert(
scip != NULL );
108 heurdata = SCIPheurGetData(heur);
109 assert(heurdata != NULL);
110 SCIPfreeMemory(
scip, &heurdata);
111 SCIPheurSetData(heur, NULL);
120 SCIP_HEURDATA* heurdata;
122 assert( heur != NULL );
123 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
126 heurdata = SCIPheurGetData(heur);
127 assert( heurdata != NULL );
130 SCIP_CALL( SCIPcreateSol(
scip, &heurdata->sol, heur) );
131 SCIP_CALL( SCIPcreateRandom(
scip, &(heurdata->randnumgen), SCIPinitializeRandomSeed(
scip,
DEFAULT_RANDSEED), TRUE) );
140 SCIP_HEURDATA* heurdata;
142 assert( heur != NULL );
143 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
146 heurdata = SCIPheurGetData(heur);
147 assert( heurdata != NULL );
150 SCIP_CALL( SCIPfreeSol(
scip, &heurdata->sol) );
151 SCIPfreeRandom(
scip, &(heurdata->randnumgen));
161 #if ( (SCIP_VERSION > 321 || SCIP_SUBVERSION > 0) ) 162 SCIP_HEURDATA* heurdata;
163 SCIP_RELAX* relaxsdp;
164 SCIP_Real* sdpcandssol;
173 assert( heur != NULL );
174 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
175 assert(
scip != NULL );
176 assert( result != NULL );
178 *result = SCIP_DELAYED;
181 if ( ! SCIPisRelaxSolValid(
scip) )
185 if ( nodeinfeasible )
188 *result = SCIP_DIDNOTRUN;
191 heurdata = SCIPheurGetData(heur);
192 assert( heurdata != NULL );
195 if ( (! heurdata->generalints) && SCIPgetNIntVars(
scip) > 0 )
199 relaxsdp = SCIPfindRelax(
scip,
"SDP");
200 if ( relaxsdp == NULL )
204 ncontvars = SCIPgetNContVars(
scip) + SCIPgetNImplVars(
scip);
207 vars = SCIPgetVars(
scip);
208 nvars = SCIPgetNVars(
scip);
209 SCIP_CALL( SCIPallocBufferArray(
scip, &sdpcands, nvars) );
210 SCIP_CALL( SCIPallocBufferArray(
scip, &sdpcandssol, nvars) );
214 for (v = 0; v < nvars; ++v)
218 val = SCIPgetRelaxSolVal(
scip, vars[v]);
219 if ( SCIPvarIsIntegral(vars[v]) && ! SCIPisFeasIntegral(
scip, val) )
221 sdpcands[nsdpcands] = vars[v];
222 sdpcandssol[nsdpcands] = val;
230 for (v = 0; v < nvars; ++v)
234 val = SCIPgetRelaxSolVal(
scip, vars[v]);
235 sdpcands[v] = vars[v];
236 sdpcandssol[v] = val;
237 if ( SCIPvarIsIntegral(vars[v]) && ! SCIPisFeasIntegral(
scip, val) )
245 if ( nsdpcands == 0 )
247 SCIPfreeBufferArray(
scip, &sdpcandssol);
248 SCIPfreeBufferArray(
scip, &sdpcands);
252 *result = SCIP_DIDNOTFIND;
254 SCIPdebugMsg(
scip,
"node %"SCIP_LONGINT_FORMAT
") executing SDP randomized rounding heuristic: depth=%d, %d fractionals.\n",
255 SCIPgetNNodes(
scip), SCIPgetDepth(
scip), nsdpcands);
258 for (iter = 0; iter < heurdata->nrounds; ++iter)
267 if ( ncontvars == 0 )
269 SCIP_CALL( SCIPlinkRelaxSol(
scip, heurdata->sol) );
272 for (v = 0; v < nsdpcands; ++v)
275 assert( SCIPvarIsIntegral(var) );
278 if ( SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5 && ! SCIPisFeasIntegral(
scip, sdpcandssol[v]) )
280 r = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
283 if ( SCIPfeasFrac(
scip, sdpcandssol[v]) <= r )
285 SCIP_CALL( SCIPsetSolVal(
scip, heurdata->sol, var, SCIPfeasFloor(
scip, sdpcandssol[v])) );
289 SCIP_CALL( SCIPsetSolVal(
scip, heurdata->sol, var, SCIPfeasCeil(
scip, sdpcandssol[v])) );
295 SCIP_CALL( SCIPtrySol(
scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
298 SCIPdebugMsg(
scip,
"Iteration %d: found solution for full binary instance.\n", iter);
300 SCIPdebugMsg(
scip,
"Iteration %d: solution not feasible for full binary instance.\n", iter);
305 SCIP_CALL( SCIPstartProbing(
scip) );
307 for (v = 0; v < nvars; ++v)
312 val = sdpcandssol[v];
315 if ( SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5 && SCIPvarIsIntegral(var) && ! SCIPisFeasIntegral(
scip, val) )
317 r = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
322 SCIP_CALL( SCIPchgVarUbProbing(
scip, var, 0.0) );
326 SCIP_CALL( SCIPchgVarLbProbing(
scip, var, 1.0) );
330 else if ( SCIPvarIsIntegral(var) && SCIPisFeasIntegral(
scip, val) && SCIPisFeasGT(
scip, val, SCIPvarGetLbLocal(var)) )
333 SCIP_CALL( SCIPchgVarLbProbing(
scip, var, val) );
336 else if ( SCIPvarIsIntegral(var) && SCIPisFeasIntegral(
scip, val) && SCIPisFeasLT(
scip, val, SCIPvarGetUbLocal(var)) )
339 SCIP_CALL( SCIPchgVarUbProbing(
scip, var, val) );
348 SCIPdebugMsg(
scip,
"Iteration %d: All variables were fixed or their values were integral -> exit.\n", iter);
353 SCIP_CALL( SCIPpropagateProbing(
scip, 0, &cutoff, NULL) );
357 SCIP_CALL( SCIPsolveProbingRelax(
scip, &cutoff) );
363 SCIP_CALL( SCIPlinkRelaxSol(
scip, heurdata->sol) );
366 SCIP_CALL( SCIPtrySol(
scip, heurdata->sol, FALSE, TRUE, TRUE, TRUE, TRUE, &success) );
370 SCIPdebugMsg(
scip,
"Iteration %d: solution was feasible and good enough.\n", iter);
371 *result = SCIP_FOUNDSOL;
374 SCIPdebugMsg(
scip,
"Iteration %d: solution was not feasible.\n", iter);
379 SCIP_CALL( SCIPendProbing(
scip) );
381 if ( SCIPisStopped(
scip) )
386 SCIPfreeBufferArray(
scip, &sdpcandssol);
387 SCIPfreeBufferArray(
scip, &sdpcands);
389 SCIPdebugMsg(
scip,
"finished randomized rounding heuristic.\n");
394 *result = SCIP_DIDNOTRUN;
410 SCIP_HEURDATA* heurdata;
414 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
417 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
421 assert( heur != NULL );
424 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySdprand) );
425 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSdprand) );
426 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSdprand) );
427 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSdprand) );
430 SCIP_CALL( SCIPaddIntParam(scip,
431 "heuristics/sdprand/nrounds",
432 "number of rounding rounds",
434 SCIP_CALL( SCIPaddBoolParam(scip,
435 "heuristics/sdprand/generalints",
436 "Should randomized rounding also be applied if there are general integer variables and not only binary variables ?",
static SCIP_DECL_HEUREXEC(heurExecSdprand)
static SCIP_DECL_HEURFREE(heurFreeSdprand)
SCIP_RETCODE SCIPincludeHeurSdpRand(SCIP *scip)
SCIP_Bool SCIPrelaxSdpSolvedProbing(SCIP_RELAX *relax)
#define DEFAULT_GENERALINTS
static SCIP_DECL_HEURINIT(heurInitSdprand)
randomized rounding heuristic for SDPs
static SCIP_DECL_HEURCOPY(heurCopySdprand)
static SCIP_DECL_HEUREXIT(heurExitSdprand)
SCIP_Bool SCIPrelaxSdpIsFeasible(SCIP_RELAX *relax)