48 #define BRANCHRULE_NAME "sdpinfobjective"
49 #define BRANCHRULE_DESC "branch on variable with highest product of fractionality/integral-infeasibility and absolute objective of the SDP"
50 #define BRANCHRULE_PRIORITY -5000
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;
88 assert(branchrule != NULL);
89 assert(strcmp(SCIPbranchruleGetName(branchrule),
BRANCHRULE_NAME) == 0);
103 SCIP_VAR** cands = NULL;
105 SCIP_Real* candsscore;
106 SCIP_VAR* maxtargetvar = NULL;
107 SCIP_Real maxtargettarget;
108 SCIP_Real maxtargetval;
109 SCIP_Real maxtargetscore;
110 SCIP_Real currentfrac;
111 SCIP_Real currenttarget;
112 SCIP_BRANCHRULEDATA* branchruledata;
114 assert( scip != NULL );
115 assert( branchrule != NULL );
116 assert( result != NULL );
118 SCIPdebugMessage(
"Executing External Branching method of SDP-integer-infeasibility-objective!\n");
122 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candssol, &candsscore, &ncands, NULL, NULL, NULL, NULL) );
124 assert( ncands > 0 );
127 printf(
"branching candidates for SDP-objective:\n");
130 maxtargettarget = -1.0;
131 maxtargetscore = 0.0;
135 for (i = 0; i < ncands; i++)
138 currentfrac = SCIPfeasFrac(scip, candssol[i]);
139 currenttarget = (currentfrac <= 0.5) ? (currentfrac * REALABS(SCIPvarGetObj(cands[i]))) : ((1 - currentfrac) * REALABS(SCIPvarGetObj(cands[i])));
142 printf(
"%s, value = %f, objective = %f, objective * integer infeasibility = %f, score = %f\n",
143 SCIPvarGetName(cands[i]), candssol[i], SCIPvarGetObj(cands[i]), currenttarget, candsscore[i]);
149 if ( SCIPisGT(scip, currenttarget, maxtargettarget) ||
150 (SCIPisEQ(scip, currenttarget, maxtargettarget) && candsscore[i] > maxtargetscore) )
152 maxtargetvar = cands[i];
153 maxtargettarget = currenttarget;
154 maxtargetval = candssol[i];
155 maxtargetscore = candsscore[i];
159 assert( SCIPisGE(scip, maxtargettarget, 0.0) );
161 branchruledata = SCIPbranchruleGetData(branchrule);
162 assert( branchruledata != NULL );
166 if ( SCIPisEQ(scip, maxtargettarget, 0.0) && (branchruledata->coupledvars || branchruledata->singlecoupledvars) )
178 SCIP_VAR** varsincons;
179 SCIP_Bool** coupledvars;
180 SCIP_Bool** singlecoupledvars;
185 SCIP_Real currentobj;
187 SCIPdebugMessage(
"All branching candidates have objective 0.0, combined integral infeasibility and objective branching proceeds to check coupled "
188 "variables, updated values for candidates: \n");
190 nvars = SCIPgetNVars(scip);
191 vars = SCIPgetVars(scip);
192 assert( vars != NULL );
193 nconss = SCIPgetNConss(scip);
194 conss = SCIPgetConss(scip);
195 assert( conss != NULL );
198 SCIP_CALL( SCIPallocBufferArray(scip, &ncandsincons, nconss) );
199 for (i = 0; i < nconss; i++)
202 SCIP_CALL( SCIPallocBufferArray(scip, &candsincons, nconss) );
203 for (i = 0; i < nconss; i++)
205 SCIP_CALL( SCIPallocBufferArray(scip, &(candsincons[i]), ncands) );
208 SCIP_CALL( SCIPallocBufferArray(scip, &coupledvars, ncands) );
209 for (i = 0; i < ncands; i++)
211 SCIP_CALL( SCIPallocBufferArray(scip, &(coupledvars[i]), nvars) );
212 for (j = 0; j < nvars; j++)
213 coupledvars[i][j] = FALSE;
215 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
218 for (c = 0; c < nconss; c++)
221 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nvarsincons, &success) );
224 SCIPdebugMessage(
"couldn't get variable information from constraint %s, so ignoring it for computing coupled variables\n", SCIPconsGetName(conss[c]));
228 if ( nvarsincons == 0)
230 SCIP_CALL( SCIPgetConsVars(scip, conss[c], varsincons, nvarsincons, &success) );
232 assert( varsincons != NULL );
233 for (v = 0; v < nvarsincons; v++)
235 for (cand = 0; cand < ncands; cand++)
237 if ( varsincons[v] == cands[cand] )
239 candsincons[c][ncandsincons[c]] = cand;
247 for (candpos = 0; candpos < ncandsincons[c]; candpos++)
249 for (v = 0; v < nvarsincons; v++)
253 coupledvars[candsincons[c][candpos]][SCIPvarGetIndex(varsincons[v]) - nvars] = TRUE;
258 if ( branchruledata->singlecoupledvars )
261 SCIP_CALL( SCIPallocBufferArray(scip, &singlecoupledvars, ncands) );
262 for (i = 0; i < ncands; i++)
264 SCIP_CALL( SCIPallocBufferArray(scip, &(singlecoupledvars[i]), nvars) );
265 for (j = 0; j < nvars; j++)
266 singlecoupledvars[i][j] = FALSE;
269 for (v = 0; v < nvars; v++)
274 for (cand = 0; cand < ncands; cand++)
276 if ( coupledvars[cand][v] )
279 if ( coupledcand == -1 )
294 if ( coupledcand > -1 )
297 singlecoupledvars[coupledcand][v] = TRUE;
303 for (cand = 0; cand < ncands; cand++)
306 for (v = 0; v < nvars; v++)
308 if ( branchruledata->singlecoupledvars && singlecoupledvars[cand][v] )
309 currentobj += REALABS(SCIPvarGetObj(vars[v]));
310 else if ( coupledvars[cand][v] )
311 currentobj += REALABS(SCIPvarGetObj(vars[v]));
315 currentfrac = SCIPfeasFrac(scip, candssol[cand]);
316 currenttarget = (currentfrac <= 0.5) ? (currentfrac * currentobj) : ((1 - currentfrac) * currentobj);
318 assert( SCIPisGE(scip, currentobj, 0.0) );
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, integral infeasibility = %f, total objective * candidate's fractionality = %f,"
334 "score = %f\n", currentobj, (currentfrac <= 0.5) ? currentfrac : (1 - currentfrac), currenttarget, candsscore[cand]);
339 if ( SCIPisGT(scip, currenttarget, maxtargettarget) ||
340 (SCIPisEQ(scip, currenttarget, maxtargettarget) && candsscore[cand] > maxtargetscore) )
342 maxtargetvar = cands[cand];
343 maxtargettarget = currenttarget;
344 maxtargetval = candssol[cand];
345 maxtargetscore = candsscore[cand];
350 if ( branchruledata->singlecoupledvars )
352 for (i = 0; i < ncands; i++)
354 SCIPfreeBufferArray(scip, &(singlecoupledvars[i]));
356 SCIPfreeBufferArray(scip, &singlecoupledvars);
358 SCIPfreeBufferArray(scip, &varsincons);
359 for (i = 0; i < ncands; i++)
361 SCIPfreeBufferArray(scip, &(coupledvars[i]));
363 SCIPfreeBufferArray(scip, &coupledvars);
364 for (i = 0; i < nconss; i++)
366 SCIPfreeBufferArray(scip, &(candsincons[i]));
368 SCIPfreeBufferArray(scip, &candsincons);
369 SCIPfreeBufferArray(scip, &ncandsincons);
373 SCIPdebugMessage(
"branching on variable %s with value %f, absolute objective * integer infeasibility = %f and score %f\n",
374 SCIPvarGetName(maxtargetvar), maxtargetval, maxtargettarget, maxtargetscore);
375 SCIP_CALL( SCIPbranchVarVal(scip, maxtargetvar, maxtargetval, NULL, NULL, NULL) );
377 *result = SCIP_BRANCHED;
386 SCIP_BRANCHRULEDATA* branchruledata;
389 branchruledata = SCIPbranchruleGetData(branchrule);
390 SCIPfreeMemory(scip, &branchruledata);
391 SCIPbranchruleSetData(branchrule, NULL);
405 SCIP_BRANCHRULEDATA* branchruledata;
406 SCIP_BRANCHRULE* branchrule;
409 SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
417 assert(branchrule != NULL);
420 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopySdpinfobjective) );
421 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextSdpinfobjective) );
422 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeSdpinfobjective) );
425 SCIP_CALL( SCIPaddBoolParam(scip,
426 "branching/sdpinfobjective/coupledvars",
427 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
428 "candidate through constraints ?",
430 SCIP_CALL( SCIPaddBoolParam(scip,
431 "branching/sdpinfobjective/singlecoupledvars",
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 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 SCIPSDP
#define DEFAULT_SINGLECOUPLEDVARS
#define BRANCHRULE_MAXBOUNDDIST
#define DEFAULT_COUPLEDVARS
SCIP_RETCODE SCIPincludeBranchruleSdpinfobjective(SCIP *scip)
#define BRANCHRULE_MAXDEPTH
static SCIP_DECL_BRANCHEXECEXT(branchExecextSdpinfobjective)