48 #define BRANCHRULE_NAME "sdpobjective"
49 #define BRANCHRULE_DESC "branch on variable with highest absolute objective of the SDP"
50 #define BRANCHRULE_PRIORITY 0
51 #define BRANCHRULE_MAXDEPTH -1
52 #define BRANCHRULE_MAXBOUNDDIST 1.0
53 #define DEFAULT_COUPLEDVARS FALSE
55 #define DEFAULT_SINGLECOUPLEDVARS FALSE
59 struct SCIP_BranchruleData
61 SCIP_Bool coupledvars;
63 SCIP_Bool singlecoupledvars;
89 assert(branchrule != NULL);
90 assert(strcmp(SCIPbranchruleGetName(branchrule),
BRANCHRULE_NAME) == 0);
104 SCIP_VAR** cands = NULL;
106 SCIP_Real* candsscore;
107 SCIP_Real currentfrac;
108 SCIP_Real currentinf;
109 SCIP_VAR* maxobjvar = NULL;
113 SCIP_Real maxobjscore;
114 SCIP_BRANCHRULEDATA* branchruledata;
116 assert( scip != NULL );
117 assert( branchrule != NULL );
118 assert( result != NULL );
120 SCIPdebugMessage(
"Executing External Branching method of SDP-objective!\n");
124 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candssol, &candsscore, &ncands, NULL, NULL, NULL, NULL) );
126 assert( ncands > 0 );
129 printf(
"branching candidates for SDP-objective:\n");
130 for (i = 0; i < ncands; i++)
131 printf(
"%s, value = %f, objective = %f, score = %f\n", SCIPvarGetName(cands[i]), candssol[i], SCIPvarGetObj(cands[i]), candsscore[i]);
140 for (i = 0; i < ncands; i++)
142 currentfrac = SCIPfeasFrac(scip, candssol[i]);
143 currentinf = (currentfrac <= 0.5) ? currentfrac : 1 - currentfrac;
149 if ( SCIPisGT(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) ||
150 (SCIPisEQ(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisGT(scip, candsscore[i], maxobjscore)) ||
151 (SCIPisEQ(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisEQ(scip, candsscore[i], maxobjscore) && currentinf > maxobjinf ) )
153 maxobjvar = cands[i];
154 maxobjobj = REALABS(SCIPvarGetObj(cands[i]));
155 maxobjinf = currentinf;
156 maxobjval = candssol[i];
157 maxobjscore = candsscore[i];
161 assert( SCIPisGE(scip, maxobjobj, 0.0) );
163 branchruledata = SCIPbranchruleGetData(branchrule);
164 assert( branchruledata != NULL );
168 if ( SCIPisEQ(scip, maxobjobj, 0.0) && (branchruledata->coupledvars || branchruledata->singlecoupledvars) )
180 SCIP_VAR** varsincons;
181 SCIP_Bool** coupledvars;
182 SCIP_Bool** singlecoupledvars;
185 SCIP_Real currentobj;
189 SCIPdebugMessage(
"All branching candidates have objective 0.0, objective branching proceeds to check coupled variables, updated values for candidates: \n");
191 nvars = SCIPgetNVars(scip);
192 vars = SCIPgetVars(scip);
193 assert( vars != NULL );
194 nconss = SCIPgetNConss(scip);
195 conss = SCIPgetConss(scip);
196 assert( conss != NULL );
199 SCIP_CALL( SCIPallocBufferArray(scip, &ncandsincons, nconss) );
200 for (i = 0; i < nconss; i++)
203 SCIP_CALL( SCIPallocBufferArray(scip, &candsincons, nconss) );
204 for (i = 0; i < nconss; i++)
206 SCIP_CALL( SCIPallocBufferArray(scip, &(candsincons[i]), ncands) );
209 SCIP_CALL( SCIPallocBufferArray(scip, &coupledvars, ncands) );
210 for (i = 0; i < ncands; i++)
212 SCIP_CALL( SCIPallocBufferArray(scip, &(coupledvars[i]), nvars) );
213 for (j = 0; j < nvars; j++)
214 coupledvars[i][j] = FALSE;
216 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
219 for (c = 0; c < nconss; c++)
222 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nvarsincons, &success) );
225 SCIPdebugMessage(
"couldn't get variable information from constraint %s, so ignoring it for computing coupled variables\n", SCIPconsGetName(conss[c]));
229 if ( nvarsincons == 0)
231 SCIP_CALL( SCIPgetConsVars(scip, conss[c], varsincons, nvarsincons, &success) );
233 assert( varsincons != NULL );
234 for (v = 0; v < nvarsincons; v++)
236 for (cand = 0; cand < ncands; cand++)
238 if ( varsincons[v] == cands[cand] )
240 candsincons[c][ncandsincons[c]] = cand;
248 for (candpos = 0; candpos < ncandsincons[c]; candpos++)
250 for (v = 0; v < nvarsincons; v++)
254 coupledvars[candsincons[c][candpos]][SCIPvarGetIndex(varsincons[v]) - nvars] = TRUE;
259 if ( branchruledata->singlecoupledvars )
262 SCIP_CALL( SCIPallocBufferArray(scip, &singlecoupledvars, ncands) );
263 for (i = 0; i < ncands; i++)
265 SCIP_CALL( SCIPallocBufferArray(scip, &(singlecoupledvars[i]), nvars) );
266 for (j = 0; j < nvars; j++)
267 singlecoupledvars[i][j] = FALSE;
270 for (v = 0; v < nvars; v++)
275 for (cand = 0; cand < ncands; cand++)
277 if ( coupledvars[cand][v] )
280 if ( coupledcand == -1 )
295 if ( coupledcand > -1 )
298 singlecoupledvars[coupledcand][v] = TRUE;
304 for (cand = 0; cand < ncands; cand++)
307 for (v = 0; v < nvars; v++)
309 if ( branchruledata->singlecoupledvars && singlecoupledvars[cand][v] )
310 currentobj += REALABS(SCIPvarGetObj(vars[v]));
311 else if ( coupledvars[cand][v] )
312 currentobj += REALABS(SCIPvarGetObj(vars[v]));
315 assert( SCIPisGE(scip, currentobj, 0.0) );
317 currentfrac = SCIPfeasFrac(scip, candssol[i]);
318 currentinf = (currentfrac <= 0.5) ? currentfrac : 1 - currentfrac;
321 printf(
"candidate %s, coupled with ", SCIPvarGetName(cands[cand]));
322 for (v = 0; v < nvars; v++)
324 if (coupledvars[cand][v])
325 printf(
"%s, ", SCIPvarGetName(vars[v]));
327 printf(
"out of those ");
328 for (v = 0; v < nvars; v++)
330 if (singlecoupledvars[cand][v])
331 printf(
"%s, ", SCIPvarGetName(vars[v]));
333 printf(
"are only coupled with this candidate, total objective = %f, score = %f\n", currentobj, candsscore[cand]);
343 if ( SCIPisGT(scip, currentobj, maxobjobj) ||
344 (SCIPisEQ(scip, currentobj, maxobjobj) && SCIPisGT(scip, candsscore[i], maxobjscore)) ||
345 (SCIPisEQ(scip, currentobj, maxobjobj) && SCIPisEQ(scip, candsscore[i], maxobjscore) && currentinf > maxobjinf ) )
347 maxobjvar = cands[cand];
348 maxobjobj = currentobj;
349 maxobjinf = currentinf;
350 maxobjval = candssol[cand];
351 maxobjscore = candsscore[cand];
356 if ( branchruledata->singlecoupledvars )
358 for (i = 0; i < ncands; i++)
360 SCIPfreeBufferArray(scip, &(singlecoupledvars[i]));
362 SCIPfreeBufferArray(scip, &singlecoupledvars);
364 SCIPfreeBufferArray(scip, &varsincons);
365 for (i = 0; i < ncands; i++)
367 SCIPfreeBufferArray(scip, &(coupledvars[i]));
369 SCIPfreeBufferArray(scip, &coupledvars);
370 for (i = 0; i < nconss; i++)
372 SCIPfreeBufferArray(scip, &(candsincons[i]));
374 SCIPfreeBufferArray(scip, &candsincons);
375 SCIPfreeBufferArray(scip, &ncandsincons);
379 SCIPdebugMessage(
"branching on variable %s with value %f, absolute objective %f and score %f\n", SCIPvarGetName(maxobjvar), maxobjval, maxobjobj, maxobjscore);
380 SCIP_CALL( SCIPbranchVarVal(scip, maxobjvar, maxobjval, NULL, NULL, NULL) );
382 *result = SCIP_BRANCHED;
391 SCIP_BRANCHRULEDATA* branchruledata;
394 branchruledata = SCIPbranchruleGetData(branchrule);
395 SCIPfreeMemory(scip, &branchruledata);
396 SCIPbranchruleSetData(branchrule, NULL);
410 SCIP_BRANCHRULEDATA* branchruledata;
411 SCIP_BRANCHRULE* branchrule;
414 SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
422 assert(branchrule != NULL);
425 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopySdpobjective) );
426 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextSdpobjective) );
427 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeSdpobjective) );
430 SCIP_CALL( SCIPaddBoolParam(scip,
431 "branching/sdpobjective/coupledvars",
432 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
433 "candidate through constraints ?",
435 SCIP_CALL( SCIPaddBoolParam(scip,
436 "branching/sdpobjective/singlecoupledvars",
437 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
438 "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 SCIPSDP
static SCIP_DECL_BRANCHCOPY(branchCopySdpobjective)
#define BRANCHRULE_MAXBOUNDDIST
SCIP_RETCODE SCIPincludeBranchruleSdpobjective(SCIP *scip)
#define BRANCHRULE_PRIORITY
static SCIP_DECL_BRANCHEXECEXT(branchExecextSdpobjective)
#define BRANCHRULE_MAXDEPTH