52 #define BRANCHRULE_NAME "sdpobjective"
53 #define BRANCHRULE_DESC "branch on variable with highest absolute objective of the SDP"
54 #define BRANCHRULE_PRIORITY 1500000
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;
93 assert(branchrule != NULL);
94 assert(strcmp(SCIPbranchruleGetName(branchrule),
BRANCHRULE_NAME) == 0);
108 SCIP_VAR** cands = NULL;
110 SCIP_Real* candsscore;
111 SCIP_Real currentfrac;
112 SCIP_Real currentinf;
113 SCIP_VAR* maxobjvar = NULL;
117 SCIP_Real maxobjscore;
118 SCIP_BRANCHRULEDATA* branchruledata;
120 assert( scip != NULL );
121 assert( branchrule != NULL );
122 assert( result != NULL );
124 SCIPdebugMessage(
"Executing External Branching method of SDP-objective!\n");
128 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candssol, &candsscore, &ncands, NULL, NULL, NULL, NULL) );
130 assert( ncands > 0 );
133 SCIPdebugMessage(
"branching candidates for SDP-objective:\n");
134 for (i = 0; i < ncands; i++)
135 SCIPdebugMessage(
"%s, value = %f, objective = %f, score = %f\n", SCIPvarGetName(cands[i]), candssol[i], SCIPvarGetObj(cands[i]), candsscore[i]);
144 for (i = 0; i < ncands; i++)
146 currentfrac = SCIPfeasFrac(scip, candssol[i]);
147 currentinf = (currentfrac <= 0.5) ? currentfrac : 1 - currentfrac;
154 if ( SCIPisGT(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) ||
155 (SCIPisEQ(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisGT(scip, candsscore[i], maxobjscore)) ||
156 (SCIPisEQ(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisEQ(scip, candsscore[i], maxobjscore) &&
157 SCIPisFeasGT(scip, currentinf, maxobjinf)) ||
158 (SCIPisEQ(scip, REALABS(SCIPvarGetObj(cands[i])), maxobjobj) && SCIPisEQ(scip, candsscore[i], maxobjscore) &&
159 SCIPisFeasEQ(scip, currentinf, maxobjinf) && (SCIPvarGetIndex(cands[i]) < SCIPvarGetIndex(maxobjvar))) )
161 maxobjvar = cands[i];
162 maxobjobj = REALABS(SCIPvarGetObj(cands[i]));
163 maxobjinf = currentinf;
164 maxobjval = candssol[i];
165 maxobjscore = candsscore[i];
169 assert( SCIPisGE(scip, maxobjobj, 0.0) );
171 branchruledata = SCIPbranchruleGetData(branchrule);
172 assert( branchruledata != NULL );
176 if ( SCIPisEQ(scip, maxobjobj, 0.0) && (branchruledata->coupledvars || branchruledata->singlecoupledvars) )
188 SCIP_VAR** varsincons;
189 SCIP_Bool** coupledvars;
190 SCIP_Bool** singlecoupledvars;
193 SCIP_Real currentobj;
197 SCIPdebugMessage(
"All branching candidates have objective 0.0, objective branching proceeds to check coupled variables, updated values for candidates: \n");
199 nvars = SCIPgetNVars(scip);
200 vars = SCIPgetVars(scip);
201 assert( vars != NULL );
202 nconss = SCIPgetNConss(scip);
203 conss = SCIPgetConss(scip);
204 assert( conss != NULL );
207 SCIP_CALL( SCIPallocBufferArray(scip, &ncandsincons, nconss) );
208 for (i = 0; i < nconss; i++)
211 SCIP_CALL( SCIPallocBufferArray(scip, &candsincons, nconss) );
212 for (i = 0; i < nconss; i++)
214 SCIP_CALL( SCIPallocBufferArray(scip, &(candsincons[i]), ncands) );
217 SCIP_CALL( SCIPallocBufferArray(scip, &coupledvars, ncands) );
218 for (i = 0; i < ncands; i++)
220 SCIP_CALL( SCIPallocBufferArray(scip, &(coupledvars[i]), nvars) );
221 for (j = 0; j < nvars; j++)
222 coupledvars[i][j] = FALSE;
224 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
227 for (c = 0; c < nconss; c++)
230 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nvarsincons, &success) );
233 SCIPdebugMessage(
"couldn't get variable information from constraint %s, so ignoring it for computing coupled variables\n", SCIPconsGetName(conss[c]));
237 if ( nvarsincons == 0)
239 SCIP_CALL( SCIPgetConsVars(scip, conss[c], varsincons, nvarsincons, &success) );
241 assert( varsincons != NULL );
242 for (v = 0; v < nvarsincons; v++)
244 for (cand = 0; cand < ncands; cand++)
246 if ( varsincons[v] == cands[cand] )
248 candsincons[c][ncandsincons[c]] = cand;
256 for (candpos = 0; candpos < ncandsincons[c]; candpos++)
258 for (v = 0; v < nvarsincons; v++)
262 coupledvars[candsincons[c][candpos]][SCIPvarGetIndex(varsincons[v]) - nvars] = TRUE;
267 if ( branchruledata->singlecoupledvars )
270 SCIP_CALL( SCIPallocBufferArray(scip, &singlecoupledvars, ncands) );
271 for (i = 0; i < ncands; i++)
273 SCIP_CALL( SCIPallocBufferArray(scip, &(singlecoupledvars[i]), nvars) );
274 for (j = 0; j < nvars; j++)
275 singlecoupledvars[i][j] = FALSE;
278 for (v = 0; v < nvars; v++)
283 for (cand = 0; cand < ncands; cand++)
285 if ( coupledvars[cand][v] )
288 if ( coupledcand == -1 )
303 if ( coupledcand > -1 )
306 singlecoupledvars[coupledcand][v] = TRUE;
312 for (cand = 0; cand < ncands; cand++)
315 for (v = 0; v < nvars; v++)
317 if ( branchruledata->singlecoupledvars && singlecoupledvars[cand][v] )
318 currentobj += REALABS(SCIPvarGetObj(vars[v]));
319 else if ( coupledvars[cand][v] )
320 currentobj += REALABS(SCIPvarGetObj(vars[v]));
323 assert( SCIPisGE(scip, currentobj, 0.0) );
325 currentfrac = SCIPfeasFrac(scip, candssol[i]);
326 currentinf = (currentfrac <= 0.5) ? currentfrac : 1 - currentfrac;
329 SCIPdebugMessage(
"candidate %s, coupled with ", SCIPvarGetName(cands[cand]));
330 for (v = 0; v < nvars; v++)
332 if (coupledvars[cand][v])
333 SCIPdebugMessage(
"%s, ", SCIPvarGetName(vars[v]));
335 SCIPdebugMessage(
"out of those ");
336 for (v = 0; v < nvars; v++)
338 if (singlecoupledvars[cand][v])
339 SCIPdebugMessage(
"%s, ", SCIPvarGetName(vars[v]));
341 SCIPdebugMessage(
"are only coupled with this candidate, total objective = %f, score = %f\n", currentobj, candsscore[cand]);
350 if ( SCIPisGT(scip, currentobj, maxobjobj) ||
351 (SCIPisEQ(scip, currentobj, maxobjobj) && SCIPisGT(scip, candsscore[i], maxobjscore)) ||
352 (SCIPisEQ(scip, currentobj, maxobjobj) && SCIPisEQ(scip, candsscore[i], maxobjscore) && SCIPisGT(scip, currentinf, maxobjinf)) ||
353 (SCIPisEQ(scip, currentobj, maxobjobj) && SCIPisEQ(scip, candsscore[i], maxobjscore) && SCIPisEQ(scip, currentinf, maxobjinf) &&
354 (SCIPvarGetIndex(cands[cand]) < SCIPvarGetIndex(maxobjvar))) )
356 maxobjvar = cands[cand];
357 maxobjobj = currentobj;
358 maxobjinf = currentinf;
359 maxobjval = candssol[cand];
360 maxobjscore = candsscore[cand];
365 if ( branchruledata->singlecoupledvars )
367 for (i = 0; i < ncands; i++)
369 SCIPfreeBufferArray(scip, &(singlecoupledvars[i]));
371 SCIPfreeBufferArray(scip, &singlecoupledvars);
373 SCIPfreeBufferArray(scip, &varsincons);
374 for (i = 0; i < ncands; i++)
376 SCIPfreeBufferArray(scip, &(coupledvars[i]));
378 SCIPfreeBufferArray(scip, &coupledvars);
379 for (i = 0; i < nconss; i++)
381 SCIPfreeBufferArray(scip, &(candsincons[i]));
383 SCIPfreeBufferArray(scip, &candsincons);
384 SCIPfreeBufferArray(scip, &ncandsincons);
388 if ( SCIPisGT(scip, maxobjobj, 0.0) )
391 SCIPdebugMessage(
"branching on variable %s with value %f, absolute objective %f and score %f\n", SCIPvarGetName(maxobjvar), maxobjval, maxobjobj, maxobjscore);
392 SCIP_CALL( SCIPbranchVarVal(scip, maxobjvar, maxobjval, NULL, NULL, NULL) );
394 *result = SCIP_BRANCHED;
399 *result = SCIP_DIDNOTRUN;
409 SCIP_BRANCHRULEDATA* branchruledata;
412 branchruledata = SCIPbranchruleGetData(branchrule);
413 SCIPfreeMemory(scip, &branchruledata);
414 SCIPbranchruleSetData(branchrule, NULL);
428 SCIP_BRANCHRULEDATA* branchruledata;
429 SCIP_BRANCHRULE* branchrule;
432 SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
440 assert(branchrule != NULL);
443 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopySdpobjective) );
444 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextSdpobjective) );
445 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeSdpobjective) );
448 SCIP_CALL( SCIPaddBoolParam(scip,
449 "branching/sdpobjective/coupledvars",
450 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
451 "candidate through constraints ?",
453 SCIP_CALL( SCIPaddBoolParam(scip,
454 "branching/sdpobjective/singlecoupledvars",
455 "if all branching candidates have objective zero, should we use the sum of the absolute objectives of all continuous variables coupled with the "
456 "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