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 5
66 #define DEFAULT_GENERALINTS FALSE
73 unsigned int randseed;
74 SCIP_Bool generalints;
86 assert( scip != NULL );
87 assert( heur != NULL );
88 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
100 SCIP_HEURDATA* heurdata;
102 assert( heur != NULL );
103 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
104 assert( scip != NULL );
107 heurdata = SCIPheurGetData(heur);
108 assert(heurdata != NULL);
109 SCIPfreeMemory(scip, &heurdata);
110 SCIPheurSetData(heur, NULL);
119 SCIP_HEURDATA* heurdata;
121 assert( heur != NULL );
122 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
125 heurdata = SCIPheurGetData(heur);
126 assert( heurdata != NULL );
129 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
138 SCIP_HEURDATA* heurdata;
140 assert( heur != NULL );
141 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
144 heurdata = SCIPheurGetData(heur);
145 assert( heurdata != NULL );
148 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
158 #if ( (SCIP_VERSION > 321 || SCIP_SUBVERSION > 0) )
159 SCIP_HEURDATA* heurdata;
160 SCIP_RELAX* relaxsdp;
161 SCIP_Real* sdpcandssol;
170 assert( heur != NULL );
171 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
172 assert( scip != NULL );
173 assert( result != NULL );
175 *result = SCIP_DELAYED;
178 if ( ! SCIPisRelaxSolValid(scip) )
182 if ( nodeinfeasible )
185 *result = SCIP_DIDNOTRUN;
188 heurdata = SCIPheurGetData(heur);
189 assert( heurdata != NULL );
192 if ( (! heurdata->generalints) && SCIPgetNIntVars(scip) > 0 )
196 relaxsdp = SCIPfindRelax(scip,
"SDP");
197 if ( relaxsdp == NULL )
201 ncontvars = SCIPgetNContVars(scip) + SCIPgetNImplVars(scip);
204 vars = SCIPgetVars(scip);
205 nvars = SCIPgetNVars(scip);
206 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcands, nvars) );
207 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcandssol, nvars) );
211 for (v = 0; v < nvars; ++v)
215 val = SCIPgetRelaxSolVal(scip, vars[v]);
216 if ( SCIPvarIsIntegral(vars[v]) && ! SCIPisFeasIntegral(scip, val) )
218 sdpcands[nsdpcands] = vars[v];
219 sdpcandssol[nsdpcands] = val;
227 for (v = 0; v < nvars; ++v)
231 val = SCIPgetRelaxSolVal(scip, vars[v]);
232 sdpcands[v] = vars[v];
233 sdpcandssol[v] = val;
234 if ( SCIPvarIsIntegral(vars[v]) && ! SCIPisFeasIntegral(scip, val) )
242 if ( nsdpcands == 0 )
244 SCIPfreeBufferArray(scip, &sdpcandssol);
245 SCIPfreeBufferArray(scip, &sdpcands);
249 *result = SCIP_DIDNOTFIND;
251 SCIPdebugMessage(
"node %"SCIP_LONGINT_FORMAT
") executing SDP randomized rounding heuristic: depth=%d, %d fractionals.\n",
252 SCIPgetNNodes(scip), SCIPgetDepth(scip), nsdpcands);
255 for (iter = 0; iter < heurdata->nrounds; ++iter)
264 if ( ncontvars == 0 )
266 SCIP_CALL( SCIPlinkRelaxSol(scip, heurdata->sol) );
269 for (v = 0; v < nsdpcands; ++v)
272 assert( SCIPvarIsIntegral(var) );
275 if ( SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5 && ! SCIPisFeasIntegral(scip, sdpcandssol[v]) )
277 r = SCIPgetRandomReal(0.0, 1.0, &heurdata->randseed);
280 if ( SCIPfeasFrac(scip, sdpcandssol[v]) <= r )
282 SCIP_CALL( SCIPsetSolVal(scip, heurdata->sol, var, SCIPfeasFloor(scip, sdpcandssol[v])) );
286 SCIP_CALL( SCIPsetSolVal(scip, heurdata->sol, var, SCIPfeasCeil(scip, sdpcandssol[v])) );
292 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, &success) );
295 SCIPdebugMessage(
"Iteration %d: found solution for full binary instance.\n", iter);
297 SCIPdebugMessage(
"Iteration %d: solution not feasible for full binary instance.\n", iter);
302 SCIP_CALL( SCIPstartProbing(scip) );
304 for (v = 0; v < nvars; ++v)
309 val = sdpcandssol[v];
312 if ( SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5 && SCIPvarIsIntegral(var) && ! SCIPisFeasIntegral(scip, val) )
314 r = SCIPgetRandomReal(0.0, 1.0, &heurdata->randseed);
319 SCIP_CALL( SCIPchgVarUbProbing(scip, var, 0.0) );
323 SCIP_CALL( SCIPchgVarLbProbing(scip, var, 1.0) );
327 else if ( SCIPvarIsIntegral(var) && SCIPisFeasIntegral(scip, val) && SCIPisFeasGT(scip, val, SCIPvarGetLbLocal(var)) )
330 SCIP_CALL( SCIPchgVarLbProbing(scip, var, val) );
333 else if ( SCIPvarIsIntegral(var) && SCIPisFeasIntegral(scip, val) && SCIPisFeasLT(scip, val, SCIPvarGetUbLocal(var)) )
336 SCIP_CALL( SCIPchgVarUbProbing(scip, var, val) );
345 SCIPdebugMessage(
"Iteration %d: All variables were fixed or their values were integral -> exit.\n", iter);
350 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
354 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
360 SCIP_CALL( SCIPlinkRelaxSol(scip, heurdata->sol) );
363 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, TRUE, TRUE, TRUE, &success) );
367 SCIPdebugMessage(
"Iteration %d: solution was feasible and good enough.\n", iter);
368 *result = SCIP_FOUNDSOL;
371 SCIPdebugMessage(
"Iteration %d: solution was not feasible.\n", iter);
376 SCIP_CALL( SCIPendProbing(scip) );
378 if ( SCIPisStopped(scip) )
383 SCIPfreeBufferArray(scip, &sdpcandssol);
384 SCIPfreeBufferArray(scip, &sdpcands);
386 SCIPdebugMessage(
"finished randomized rounding heuristic.\n");
391 *result = SCIP_DIDNOTRUN;
407 SCIP_HEURDATA* heurdata;
411 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
412 heurdata->randseed = 0;
415 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
419 assert( heur != NULL );
422 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySdprand) );
423 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSdprand) );
424 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSdprand) );
425 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSdprand) );
428 SCIP_CALL( SCIPaddIntParam(scip,
429 "heuristics/sdprand/nrounds",
430 "number of rounding rounds",
432 SCIP_CALL( SCIPaddBoolParam(scip,
433 "heuristics/sdprand/generalints",
434 "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)