52 #define BRANCHRULE_NAME "sdpinfobjective"
53 #define BRANCHRULE_DESC "branch on variable with highest product of fractionality/integral-infeasibility and absolute objective of the SDP"
54 #define BRANCHRULE_PRIORITY 2000000
55 #define BRANCHRULE_MAXDEPTH -1
56 #define BRANCHRULE_MAXBOUNDDIST 1.0
57 #define DEFAULT_COUPLEDVARS FALSE
59 #define DEFAULT_SINGLECOUPLEDVARS FALSE
63 struct SCIP_BranchruleData
65 SCIP_Bool coupledvars;
67 SCIP_Bool singlecoupledvars;
92 assert(branchrule != NULL);
93 assert(strcmp(SCIPbranchruleGetName(branchrule),
BRANCHRULE_NAME) == 0);
105 SCIP_BRANCHRULEDATA* branchruledata;
106 SCIP_VAR** cands = NULL;
108 SCIP_Real* candsscore;
109 SCIP_VAR* maxtargetvar = NULL;
110 SCIP_Real maxtargettarget = -1.0;
111 SCIP_Real maxtargetval = 0.0;
112 SCIP_Real maxtargetscore = 0.0;
113 SCIP_Real currentfrac;
114 SCIP_Real currenttarget;
118 assert( scip != NULL );
119 assert( branchrule != NULL );
120 assert( result != NULL );
122 SCIPdebugMessage(
"Executing External Branching method of SDP-integer-infeasibility-objective!\n");
126 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candssol, &candsscore, &ncands, NULL, NULL, NULL, NULL) );
128 assert( ncands > 0 );
130 SCIPdebugMessage(
"branching candidates for SDP-objective:\n");
133 for (i = 0; i < ncands; i++)
136 currentfrac = SCIPfeasFrac(scip, candssol[i]);
137 currenttarget = (currentfrac <= 0.5) ? (currentfrac * REALABS(SCIPvarGetObj(cands[i]))) : ((1.0 - currentfrac) * REALABS(SCIPvarGetObj(cands[i])));
139 SCIPdebugMessage(
"%s, value = %f, objective = %f, objective * integer infeasibility = %f, score = %f\n",
140 SCIPvarGetName(cands[i]), candssol[i], SCIPvarGetObj(cands[i]), currenttarget, candsscore[i]);
146 if ( SCIPisGT(scip, currenttarget, maxtargettarget) ||
147 ( SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisGT(scip, candsscore[i], maxtargetscore) ) ||
148 ( SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisEQ(scip, candsscore[i], maxtargetscore) &&
149 SCIPvarGetIndex(cands[i]) < SCIPvarGetIndex(maxtargetvar) ) )
151 maxtargetvar = cands[i];
152 maxtargettarget = currenttarget;
153 maxtargetval = candssol[i];
154 maxtargetscore = candsscore[i];
158 assert( SCIPisGE(scip, maxtargettarget, 0.0) );
160 branchruledata = SCIPbranchruleGetData(branchrule);
161 assert( branchruledata != NULL );
165 if ( SCIPisEQ(scip, maxtargettarget, 0.0) && (branchruledata->coupledvars || branchruledata->singlecoupledvars) )
171 SCIP_VAR** varsincons;
172 SCIP_Bool** coupledvars;
173 SCIP_Bool** singlecoupledvars;
178 SCIP_Real currentobj;
186 SCIPdebugMessage(
"All branching candidates have objective 0.0, combined integral infeasibility and objective branching proceeds to check coupled "
187 "variables, updated values for candidates:\n");
189 nvars = SCIPgetNVars(scip);
190 vars = SCIPgetVars(scip);
191 assert( vars != NULL );
192 nconss = SCIPgetNConss(scip);
193 conss = SCIPgetConss(scip);
194 assert( conss != NULL );
197 SCIP_CALL( SCIPallocBufferArray(scip, &ncandsincons, nconss) );
198 for (i = 0; i < nconss; i++)
201 SCIP_CALL( SCIPallocBufferArray(scip, &candsincons, nconss) );
202 for (i = 0; i < nconss; i++)
204 SCIP_CALL( SCIPallocBufferArray(scip, &(candsincons[i]), ncands) );
207 SCIP_CALL( SCIPallocBufferArray(scip, &coupledvars, ncands) );
208 for (i = 0; i < ncands; i++)
210 SCIP_CALL( SCIPallocBufferArray(scip, &(coupledvars[i]), nvars) );
211 for (j = 0; j < nvars; j++)
212 coupledvars[i][j] = FALSE;
214 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
217 for (c = 0; c < nconss; c++)
220 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nvarsincons, &success) );
223 SCIPdebugMessage(
"couldn't get variable information from constraint %s, so ignoring it for computing coupled variables\n", SCIPconsGetName(conss[c]));
228 if ( nvarsincons == 0)
231 SCIP_CALL( SCIPgetConsVars(scip, conss[c], varsincons, nvarsincons, &success) );
233 assert( varsincons != NULL );
235 for (v = 0; v < nvarsincons; v++)
237 for (cand = 0; cand < ncands; cand++)
239 if ( varsincons[v] == cands[cand] )
241 candsincons[c][ncandsincons[c]] = cand;
249 for (candpos = 0; candpos < ncandsincons[c]; candpos++)
251 for (v = 0; v < nvarsincons; v++)
255 coupledvars[candsincons[c][candpos]][SCIPvarGetIndex(varsincons[v]) - nvars] = TRUE;
260 if ( branchruledata->singlecoupledvars )
263 SCIP_CALL( SCIPallocBufferArray(scip, &singlecoupledvars, ncands) );
264 for (i = 0; i < ncands; i++)
266 SCIP_CALL( SCIPallocBufferArray(scip, &(singlecoupledvars[i]), nvars) );
267 for (j = 0; j < nvars; j++)
268 singlecoupledvars[i][j] = FALSE;
271 for (v = 0; v < nvars; v++)
276 for (cand = 0; cand < ncands; cand++)
278 if ( coupledvars[cand][v] )
281 if ( coupledcand == -1 )
296 if ( coupledcand > -1 )
299 singlecoupledvars[coupledcand][v] = TRUE;
305 for (cand = 0; cand < ncands; cand++)
308 for (v = 0; v < nvars; v++)
310 if ( branchruledata->singlecoupledvars && singlecoupledvars[cand][v] )
311 currentobj += REALABS(SCIPvarGetObj(vars[v]));
312 else if ( coupledvars[cand][v] )
313 currentobj += REALABS(SCIPvarGetObj(vars[v]));
317 currentfrac = SCIPfeasFrac(scip, candssol[cand]);
318 currenttarget = (currentfrac <= 0.5) ? (currentfrac * currentobj) : ((1 - currentfrac) * currentobj);
320 assert( SCIPisGE(scip, currentobj, 0.0) );
323 SCIPdebugMessage(
"candidate %s, coupled with ", SCIPvarGetName(cands[cand]));
324 for (v = 0; v < nvars; v++)
326 if (coupledvars[cand][v])
327 SCIPdebugMessage(
"%s, ", SCIPvarGetName(vars[v]));
329 SCIPdebugMessage(
"out of those ");
330 for (v = 0; v < nvars; v++)
332 if (singlecoupledvars[cand][v])
333 SCIPdebugMessage(
"%s, ", SCIPvarGetName(vars[v]));
335 SCIPdebugMessage(
"are only coupled with this candidate, total objective = %f, integral infeasibility = %f, total objective * candidate's fractionality = %f,"
336 "score = %f\n", currentobj, (currentfrac <= 0.5) ? currentfrac : (1 - currentfrac), currenttarget, candsscore[cand]);
343 if ( SCIPisGT(scip, currenttarget, maxtargettarget) ||
344 (SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisGT(scip, candsscore[cand], maxtargetscore)) ||
345 (SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisEQ(scip, candsscore[cand], maxtargetscore) &&
346 SCIPvarGetIndex(cands[cand]) < SCIPvarGetIndex(maxtargetvar)) )
348 maxtargetvar = cands[cand];
349 maxtargettarget = currenttarget;
350 maxtargetval = candssol[cand];
351 maxtargetscore = 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 if ( SCIPisGT(scip, maxtargettarget, 0.0) )
382 SCIPdebugMessage(
"branching on variable %s with value %f, absolute objective * integer infeasibility = %f and score %f\n",
383 SCIPvarGetName(maxtargetvar), maxtargetval, maxtargettarget, maxtargetscore);
384 SCIP_CALL( SCIPbranchVarVal(scip, maxtargetvar, maxtargetval, NULL, NULL, NULL) );
386 *result = SCIP_BRANCHED;
391 *result = SCIP_DIDNOTRUN;
401 SCIP_BRANCHRULEDATA* branchruledata;
404 branchruledata = SCIPbranchruleGetData(branchrule);
405 SCIPfreeMemory(scip, &branchruledata);
406 SCIPbranchruleSetData(branchrule, NULL);
420 SCIP_BRANCHRULEDATA* branchruledata;
421 SCIP_BRANCHRULE* branchrule;
424 SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
432 assert(branchrule != NULL);
435 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopySdpinfobjective) );
436 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextSdpinfobjective) );
437 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeSdpinfobjective) );
440 SCIP_CALL( SCIPaddBoolParam(scip,
441 "branching/sdpinfobjective/coupledvars",
442 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
443 "candidate through constraints ?",
445 SCIP_CALL( SCIPaddBoolParam(scip,
446 "branching/sdpinfobjective/singlecoupledvars",
447 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
448 "candidate through constraints in which no other candidate appears ?",
static SCIP_DECL_BRANCHCOPY(branchCopySdpinfobjective)
#define BRANCHRULE_PRIORITY
static SCIP_DECL_BRANCHFREE(branchFreeSdpinfobjective)
combined infeasibility and absolute objective branching rule for SCIP-SDP
#define DEFAULT_SINGLECOUPLEDVARS
#define BRANCHRULE_MAXBOUNDDIST
#define DEFAULT_COUPLEDVARS
SCIP_RETCODE SCIPincludeBranchruleSdpinfobjective(SCIP *scip)
#define BRANCHRULE_MAXDEPTH
static SCIP_DECL_BRANCHEXECEXT(branchExecextSdpinfobjective)