54 #define BRANCHRULE_NAME "sdpinfobjective"
55 #define BRANCHRULE_DESC "branch on variable with highest product of fractionality/integral-infeasibility and absolute objective of the SDP"
56 #define BRANCHRULE_PRIORITY 2000000
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;
94 assert(branchrule != NULL);
95 assert(strcmp(SCIPbranchruleGetName(branchrule),
BRANCHRULE_NAME) == 0);
107 SCIP_BRANCHRULEDATA* branchruledata;
108 SCIP_VAR** cands = NULL;
110 SCIP_Real* candsscore;
111 SCIP_VAR* maxtargetvar = NULL;
112 SCIP_Real maxtargettarget = -1.0;
113 SCIP_Real maxtargetval = 0.0;
114 SCIP_Real maxtargetscore = 0.0;
115 SCIP_Real currentfrac;
116 SCIP_Real currenttarget;
120 assert( scip != NULL );
121 assert( branchrule != NULL );
122 assert( result != NULL );
124 SCIPdebugMessage(
"Executing External Branching method of SDP-integer-infeasibility-objective!\n");
128 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candssol, &candsscore, &ncands, NULL, NULL, NULL, NULL) );
130 assert( ncands > 0 );
132 SCIPdebugMessage(
"branching candidates for SDP-objective:\n");
135 for (i = 0; i < ncands; i++)
138 if ( SCIPvarGetType(cands[i]) == SCIP_VARTYPE_CONTINUOUS )
140 SCIPdebugMessage(
"skipping continuous variable %s\n", SCIPvarGetName(cands[i]));
144 currentfrac = SCIPfeasFrac(scip, candssol[i]);
145 currenttarget = (currentfrac <= 0.5) ? (currentfrac * REALABS(SCIPvarGetObj(cands[i]))) : ((1.0 - currentfrac) * REALABS(SCIPvarGetObj(cands[i])));
147 SCIPdebugMessage(
"%s, value = %f, objective = %f, objective * integer infeasibility = %f, score = %f\n",
148 SCIPvarGetName(cands[i]), candssol[i], SCIPvarGetObj(cands[i]), currenttarget, candsscore[i]);
154 if ( SCIPisGT(scip, currenttarget, maxtargettarget) ||
155 ( SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisGT(scip, candsscore[i], maxtargetscore) ) ||
156 ( SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisEQ(scip, candsscore[i], maxtargetscore) &&
157 SCIPvarGetIndex(cands[i]) < SCIPvarGetIndex(maxtargetvar) ) )
159 maxtargetvar = cands[i];
160 maxtargettarget = currenttarget;
161 maxtargetval = candssol[i];
162 maxtargetscore = candsscore[i];
167 if ( maxtargettarget == -1.0 )
169 SCIPdebugMessage(
"Skipping SDP-infobj branching rule since all branching variables are continuous\n");
170 *result = SCIP_DIDNOTFIND;
174 assert( SCIPisFeasGE(scip, maxtargettarget, 0.0) );
175 assert( maxtargetvar != NULL );
177 branchruledata = SCIPbranchruleGetData(branchrule);
178 assert( branchruledata != NULL );
182 if ( SCIPisEQ(scip, maxtargettarget, 0.0) && (branchruledata->coupledvars || branchruledata->singlecoupledvars) )
188 SCIP_VAR** varsincons;
189 SCIP_Bool** coupledvars;
190 SCIP_Bool** singlecoupledvars;
195 SCIP_Real currentobj;
203 SCIPdebugMessage(
"All branching candidates have objective 0.0, combined integral infeasibility and objective branching proceeds to check coupled "
204 "variables, updated values for candidates:\n");
206 nvars = SCIPgetNVars(scip);
207 vars = SCIPgetVars(scip);
208 assert( vars != NULL );
209 nconss = SCIPgetNConss(scip);
210 conss = SCIPgetConss(scip);
211 assert( conss != NULL );
214 SCIP_CALL( SCIPallocBufferArray(scip, &ncandsincons, nconss) );
215 for (i = 0; i < nconss; i++)
218 SCIP_CALL( SCIPallocBufferArray(scip, &candsincons, nconss) );
219 for (i = 0; i < nconss; i++)
221 SCIP_CALL( SCIPallocBufferArray(scip, &(candsincons[i]), ncands) );
224 SCIP_CALL( SCIPallocBufferArray(scip, &coupledvars, ncands) );
225 for (i = 0; i < ncands; i++)
227 SCIP_CALL( SCIPallocBufferArray(scip, &(coupledvars[i]), nvars) );
228 for (j = 0; j < nvars; j++)
229 coupledvars[i][j] = FALSE;
231 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
234 for (c = 0; c < nconss; c++)
237 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nvarsincons, &success) );
240 SCIPdebugMessage(
"couldn't get variable information from constraint %s, so ignoring it for computing coupled variables\n", SCIPconsGetName(conss[c]));
245 if ( nvarsincons == 0)
248 SCIP_CALL( SCIPgetConsVars(scip, conss[c], varsincons, nvarsincons, &success) );
250 assert( varsincons != NULL );
252 for (v = 0; v < nvarsincons; v++)
254 for (cand = 0; cand < ncands; cand++)
256 if ( varsincons[v] == cands[cand] )
258 candsincons[c][ncandsincons[c]] = cand;
266 for (candpos = 0; candpos < ncandsincons[c]; candpos++)
268 for (v = 0; v < nvarsincons; v++)
272 coupledvars[candsincons[c][candpos]][SCIPvarGetIndex(varsincons[v]) - nvars] = TRUE;
277 if ( branchruledata->singlecoupledvars )
280 SCIP_CALL( SCIPallocBufferArray(scip, &singlecoupledvars, ncands) );
281 for (i = 0; i < ncands; i++)
283 SCIP_CALL( SCIPallocBufferArray(scip, &(singlecoupledvars[i]), nvars) );
284 for (j = 0; j < nvars; j++)
285 singlecoupledvars[i][j] = FALSE;
288 for (v = 0; v < nvars; v++)
293 for (cand = 0; cand < ncands; cand++)
295 if ( coupledvars[cand][v] )
298 if ( coupledcand == -1 )
313 if ( coupledcand > -1 )
316 singlecoupledvars[coupledcand][v] = TRUE;
322 for (cand = 0; cand < ncands; cand++)
325 for (v = 0; v < nvars; v++)
327 if ( branchruledata->singlecoupledvars && singlecoupledvars[cand][v] )
328 currentobj += REALABS(SCIPvarGetObj(vars[v]));
329 else if ( coupledvars[cand][v] )
330 currentobj += REALABS(SCIPvarGetObj(vars[v]));
334 currentfrac = SCIPfeasFrac(scip, candssol[cand]);
335 currenttarget = (currentfrac <= 0.5) ? (currentfrac * currentobj) : ((1 - currentfrac) * currentobj);
337 assert( SCIPisGE(scip, currentobj, 0.0) );
340 SCIPdebugMessage(
"candidate %s, coupled with ", SCIPvarGetName(cands[cand]));
341 for (v = 0; v < nvars; v++)
343 if (coupledvars[cand][v])
344 SCIPdebugMessage(
"%s, ", SCIPvarGetName(vars[v]));
346 SCIPdebugMessage(
"out of those ");
347 for (v = 0; v < nvars; v++)
349 if (singlecoupledvars[cand][v])
350 SCIPdebugMessage(
"%s, ", SCIPvarGetName(vars[v]));
352 SCIPdebugMessage(
"are only coupled with this candidate, total objective = %f, integral infeasibility = %f, total objective * candidate's fractionality = %f,"
353 "score = %f\n", currentobj, (currentfrac <= 0.5) ? currentfrac : (1 - currentfrac), currenttarget, candsscore[cand]);
360 if ( SCIPisGT(scip, currenttarget, maxtargettarget) ||
361 (SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisGT(scip, candsscore[cand], maxtargetscore)) ||
362 (SCIPisEQ(scip, currenttarget, maxtargettarget) && SCIPisEQ(scip, candsscore[cand], maxtargetscore) &&
363 SCIPvarGetIndex(cands[cand]) < SCIPvarGetIndex(maxtargetvar)) )
365 maxtargetvar = cands[cand];
366 maxtargettarget = currenttarget;
367 maxtargetval = candssol[cand];
368 maxtargetscore = candsscore[cand];
373 if ( branchruledata->singlecoupledvars )
375 for (i = 0; i < ncands; i++)
377 SCIPfreeBufferArray(scip, &(singlecoupledvars[i]));
379 SCIPfreeBufferArray(scip, &singlecoupledvars);
381 SCIPfreeBufferArray(scip, &varsincons);
382 for (i = 0; i < ncands; i++)
384 SCIPfreeBufferArray(scip, &(coupledvars[i]));
386 SCIPfreeBufferArray(scip, &coupledvars);
387 for (i = 0; i < nconss; i++)
389 SCIPfreeBufferArray(scip, &(candsincons[i]));
391 SCIPfreeBufferArray(scip, &candsincons);
392 SCIPfreeBufferArray(scip, &ncandsincons);
396 if ( SCIPisGT(scip, maxtargettarget, 0.0) )
399 SCIPdebugMessage(
"branching on variable %s with value %f, absolute objective * integer infeasibility = %f and score %f\n",
400 SCIPvarGetName(maxtargetvar), maxtargetval, maxtargettarget, maxtargetscore);
401 SCIP_CALL( SCIPbranchVarVal(scip, maxtargetvar, maxtargetval, NULL, NULL, NULL) );
403 *result = SCIP_BRANCHED;
408 *result = SCIP_DIDNOTRUN;
418 SCIP_BRANCHRULEDATA* branchruledata;
421 branchruledata = SCIPbranchruleGetData(branchrule);
422 SCIPfreeMemory(scip, &branchruledata);
423 SCIPbranchruleSetData(branchrule, NULL);
437 SCIP_BRANCHRULEDATA* branchruledata;
438 SCIP_BRANCHRULE* branchrule;
441 SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
449 assert(branchrule != NULL);
452 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopySdpinfobjective) );
453 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextSdpinfobjective) );
454 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeSdpinfobjective) );
457 SCIP_CALL( SCIPaddBoolParam(scip,
458 "branching/sdpinfobjective/coupledvars",
459 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
460 "candidate through constraints ?",
462 SCIP_CALL( SCIPaddBoolParam(scip,
463 "branching/sdpinfobjective/singlecoupledvars",
464 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
465 "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)