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)) );
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 SCIPdebugMessage(
"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 SCIPdebugMessage(
"Iteration %d: found solution for full binary instance.\n", iter);
300 SCIPdebugMessage(
"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 SCIPdebugMessage(
"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 SCIPdebugMessage(
"Iteration %d: solution was feasible and good enough.\n", iter);
371 *result = SCIP_FOUNDSOL;
374 SCIPdebugMessage(
"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 SCIPdebugMessage(
"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)