54 #define BRANCHRULE_NAME "sdpobjective" 55 #define BRANCHRULE_DESC "branch on variable with highest absolute objective of the SDP" 56 #define BRANCHRULE_PRIORITY 1500000 57 #define BRANCHRULE_MAXDEPTH -1 58 #define BRANCHRULE_MAXBOUNDDIST 1.0 59 #define DEFAULT_COUPLEDVARS FALSE 61 #define DEFAULT_SINGLECOUPLEDVARS FALSE 65 struct SCIP_BranchruleData 67 SCIP_Bool coupledvars;
69 SCIP_Bool singlecoupledvars;
95 assert(branchrule != NULL);
96 assert(strcmp(SCIPbranchruleGetName(branchrule),
BRANCHRULE_NAME) == 0);
110 SCIP_VAR** cands = NULL;
112 SCIP_Real* candsscore;
113 SCIP_Real currentfrac;
114 SCIP_Real currentinf;
115 SCIP_VAR* maxobjvar = NULL;
119 SCIP_Real maxobjscore;
120 SCIP_BRANCHRULEDATA* branchruledata;
122 assert(
scip != NULL );
123 assert( branchrule != NULL );
124 assert( result != NULL );
126 SCIPdebugMsg(
scip,
"Executing External Branching method of SDP-objective!\n");
130 SCIP_CALL( SCIPgetExternBranchCands(
scip, &cands, &candssol, &candsscore, &ncands, NULL, NULL, NULL, NULL) );
132 assert( ncands > 0 );
135 SCIPdebugMsg(
scip,
"branching candidates for SDP-objective:\n");
136 for (i = 0; i < ncands; i++)
137 SCIPdebugMsg(
scip,
"%s, value = %f, objective = %f, score = %f\n", SCIPvarGetName(cands[i]), candssol[i], SCIPvarGetObj(cands[i]), candsscore[i]);
146 for (i = 0; i < ncands; i++)
149 if ( SCIPvarGetType(cands[i]) == SCIP_VARTYPE_CONTINUOUS )
151 SCIPdebugMsg(
scip,
"skipping continuous variable %s\n", SCIPvarGetName(cands[i]));
155 currentfrac = SCIPfeasFrac(
scip, candssol[i]);
156 currentinf = (currentfrac <= 0.5) ? currentfrac : 1 - currentfrac;
163 if ( SCIPisGT(
scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) ||
164 (SCIPisEQ(
scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisGT(
scip, candsscore[i], maxobjscore)) ||
165 (SCIPisEQ(
scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisEQ(
scip, candsscore[i], maxobjscore) &&
166 SCIPisFeasGT(
scip, currentinf, maxobjinf)) ||
167 (SCIPisEQ(
scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisEQ(
scip, candsscore[i], maxobjscore) &&
168 SCIPisFeasEQ(
scip, currentinf, maxobjinf) && (SCIPvarGetIndex(cands[i]) < SCIPvarGetIndex(maxobjvar))) )
170 maxobjvar = cands[i];
171 maxobjobj = REALABS(SCIPvarGetObj(cands[i]));
172 maxobjinf = currentinf;
173 maxobjval = candssol[i];
174 maxobjscore = candsscore[i];
179 if ( maxobjobj == -1.0 )
181 SCIPdebugMsg(
scip,
"Skipping SDP-objective branching rule since all branching variables are continuous\n");
182 *result = SCIP_DIDNOTFIND;
186 assert( SCIPisFeasGE(
scip, maxobjobj, 0.0) );
187 assert( maxobjvar != NULL );
189 branchruledata = SCIPbranchruleGetData(branchrule);
190 assert( branchruledata != NULL );
194 if ( SCIPisEQ(
scip, maxobjobj, 0.0) && (branchruledata->coupledvars || branchruledata->singlecoupledvars) )
206 SCIP_VAR** varsincons;
207 SCIP_Bool** coupledvars;
208 SCIP_Bool** singlecoupledvars;
211 SCIP_Real currentobj;
215 SCIPdebugMsg(
scip,
"All branching candidates have objective 0.0, objective branching proceeds to check coupled variables, updated values for candidates: \n");
217 nvars = SCIPgetNVars(
scip);
218 vars = SCIPgetVars(
scip);
219 assert( vars != NULL );
220 nconss = SCIPgetNConss(
scip);
221 conss = SCIPgetConss(
scip);
222 assert( conss != NULL );
225 SCIP_CALL( SCIPallocBufferArray(
scip, &ncandsincons, nconss) );
226 for (i = 0; i < nconss; i++)
229 SCIP_CALL( SCIPallocBufferArray(
scip, &candsincons, nconss) );
230 for (i = 0; i < nconss; i++)
232 SCIP_CALL( SCIPallocBufferArray(
scip, &(candsincons[i]), ncands) );
235 SCIP_CALL( SCIPallocBufferArray(
scip, &coupledvars, ncands) );
236 for (i = 0; i < ncands; i++)
238 SCIP_CALL( SCIPallocBufferArray(
scip, &(coupledvars[i]), nvars) );
239 for (j = 0; j < nvars; j++)
240 coupledvars[i][j] = FALSE;
242 SCIP_CALL( SCIPallocBufferArray(
scip, &varsincons, nvars) );
245 for (c = 0; c < nconss; c++)
248 SCIP_CALL( SCIPgetConsNVars(
scip, conss[c], &nvarsincons, &success) );
251 SCIPdebugMsg(
scip,
"couldn't get variable information from constraint %s, so ignoring it for computing coupled variables\n", SCIPconsGetName(conss[c]));
255 if ( nvarsincons == 0)
257 SCIP_CALL( SCIPgetConsVars(
scip, conss[c], varsincons, nvarsincons, &success) );
259 assert( varsincons != NULL );
260 for (v = 0; v < nvarsincons; v++)
262 for (cand = 0; cand < ncands; cand++)
264 if ( varsincons[v] == cands[cand] )
266 candsincons[c][ncandsincons[c]] = cand;
274 for (candpos = 0; candpos < ncandsincons[c]; candpos++)
276 for (v = 0; v < nvarsincons; v++)
280 coupledvars[candsincons[c][candpos]][SCIPvarGetIndex(varsincons[v]) - nvars] = TRUE;
285 if ( branchruledata->singlecoupledvars )
288 SCIP_CALL( SCIPallocBufferArray(
scip, &singlecoupledvars, ncands) );
289 for (i = 0; i < ncands; i++)
291 SCIP_CALL( SCIPallocBufferArray(
scip, &(singlecoupledvars[i]), nvars) );
292 for (j = 0; j < nvars; j++)
293 singlecoupledvars[i][j] = FALSE;
296 for (v = 0; v < nvars; v++)
301 for (cand = 0; cand < ncands; cand++)
303 if ( coupledvars[cand][v] )
306 if ( coupledcand == -1 )
321 if ( coupledcand > -1 )
324 singlecoupledvars[coupledcand][v] = TRUE;
330 for (cand = 0; cand < ncands; cand++)
333 for (v = 0; v < nvars; v++)
335 if ( branchruledata->singlecoupledvars && singlecoupledvars[cand][v] )
336 currentobj += REALABS(SCIPvarGetObj(vars[v]));
337 else if ( coupledvars[cand][v] )
338 currentobj += REALABS(SCIPvarGetObj(vars[v]));
341 assert( SCIPisGE(
scip, currentobj, 0.0) );
343 currentfrac = SCIPfeasFrac(
scip, candssol[i]);
344 currentinf = (currentfrac <= 0.5) ? currentfrac : 1 - currentfrac;
347 SCIPdebugMsg(
scip,
"candidate %s, coupled with ", SCIPvarGetName(cands[cand]));
348 for (v = 0; v < nvars; v++)
350 if (coupledvars[cand][v])
351 SCIPdebugMsg(
scip,
"%s, ", SCIPvarGetName(vars[v]));
353 SCIPdebugMsg(
scip,
"out of those ");
354 for (v = 0; v < nvars; v++)
356 if (singlecoupledvars[cand][v])
357 SCIPdebugMsg(
scip,
"%s, ", SCIPvarGetName(vars[v]));
359 SCIPdebugMsg(
scip,
"are only coupled with this candidate, total objective = %f, score = %f\n", currentobj, candsscore[cand]);
368 if ( SCIPisGT(
scip, currentobj, maxobjobj) ||
369 (SCIPisEQ(
scip, currentobj, maxobjobj) && SCIPisGT(
scip, candsscore[i], maxobjscore)) ||
370 (SCIPisEQ(
scip, currentobj, maxobjobj) && SCIPisEQ(
scip, candsscore[i], maxobjscore) && SCIPisGT(
scip, currentinf, maxobjinf)) ||
371 (SCIPisEQ(
scip, currentobj, maxobjobj) && SCIPisEQ(
scip, candsscore[i], maxobjscore) && SCIPisEQ(
scip, currentinf, maxobjinf) &&
372 (SCIPvarGetIndex(cands[cand]) < SCIPvarGetIndex(maxobjvar))) )
374 maxobjvar = cands[cand];
375 maxobjobj = currentobj;
376 maxobjinf = currentinf;
377 maxobjval = candssol[cand];
378 maxobjscore = candsscore[cand];
383 if ( branchruledata->singlecoupledvars )
385 for (i = 0; i < ncands; i++)
387 SCIPfreeBufferArray(
scip, &(singlecoupledvars[i]));
389 SCIPfreeBufferArray(
scip, &singlecoupledvars);
391 SCIPfreeBufferArray(
scip, &varsincons);
392 for (i = 0; i < ncands; i++)
394 SCIPfreeBufferArray(
scip, &(coupledvars[i]));
396 SCIPfreeBufferArray(
scip, &coupledvars);
397 for (i = 0; i < nconss; i++)
399 SCIPfreeBufferArray(
scip, &(candsincons[i]));
401 SCIPfreeBufferArray(
scip, &candsincons);
402 SCIPfreeBufferArray(
scip, &ncandsincons);
406 if ( SCIPisGT(
scip, maxobjobj, 0.0) )
409 SCIPdebugMsg(
scip,
"branching on variable %s with value %f, absolute objective %f and score %f\n", SCIPvarGetName(maxobjvar), maxobjval, maxobjobj, maxobjscore);
410 SCIP_CALL( SCIPbranchVarVal(
scip, maxobjvar, maxobjval, NULL, NULL, NULL) );
412 *result = SCIP_BRANCHED;
417 *result = SCIP_DIDNOTRUN;
427 SCIP_BRANCHRULEDATA* branchruledata;
430 branchruledata = SCIPbranchruleGetData(branchrule);
431 SCIPfreeMemory(
scip, &branchruledata);
432 SCIPbranchruleSetData(branchrule, NULL);
446 SCIP_BRANCHRULEDATA* branchruledata;
447 SCIP_BRANCHRULE* branchrule;
450 SCIP_CALL( SCIPallocMemory(
scip, &branchruledata) );
458 assert(branchrule != NULL);
461 SCIP_CALL( SCIPsetBranchruleCopy(
scip, branchrule, branchCopySdpobjective) );
462 SCIP_CALL( SCIPsetBranchruleExecExt(
scip, branchrule, branchExecextSdpobjective) );
463 SCIP_CALL( SCIPsetBranchruleFree(
scip, branchrule, branchFreeSdpobjective) );
466 SCIP_CALL( SCIPaddBoolParam(
scip,
467 "branching/sdpobjective/coupledvars",
468 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the " 469 "candidate through constraints ?",
471 SCIP_CALL( SCIPaddBoolParam(
scip,
472 "branching/sdpobjective/singlecoupledvars",
473 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the " 474 "candidate through constraints in which no other candidate appears ?",
static SCIP_DECL_BRANCHFREE(branchFreeSdpobjective)
#define DEFAULT_SINGLECOUPLEDVARS
#define DEFAULT_COUPLEDVARS
highest absolute objective branching rule for SCIP-SDP
static SCIP_DECL_BRANCHCOPY(branchCopySdpobjective)
#define BRANCHRULE_MAXBOUNDDIST
SCIP_RETCODE SCIPincludeBranchruleSdpobjective(SCIP *scip)
#define BRANCHRULE_PRIORITY
static SCIP_DECL_BRANCHEXECEXT(branchExecextSdpobjective)
#define BRANCHRULE_MAXDEPTH