branch_empty.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 /*#define SCIP_DEBUG*/
37 #include <assert.h>
38 #include <string.h>
39 
40 #include "branch_empty.h"
41 #include "relax_gcg.h"
42 #include "gcg.h"
43 #include "branch_orig.h"
44 #include "cons_masterbranch.h"
45 #include "cons_origbranch.h"
46 #include "scip/branch_allfullstrong.h"
47 #include "scip/branch_fullstrong.h"
48 #include "scip/branch_inference.h"
49 #include "scip/branch_mostinf.h"
50 #include "scip/branch_leastinf.h"
51 #include "scip/branch_pscost.h"
52 #include "scip/branch_random.h"
53 #include "scip/branch_relpscost.h"
54 #include "scip/cons_varbound.h"
55 #include "type_branchgcg.h"
56 
57 #define BRANCHRULE_NAME "empty"
58 #define BRANCHRULE_DESC "branching rule for the original problem while real branching is applied in the master"
59 #define BRANCHRULE_PRIORITY 1000000
60 #define BRANCHRULE_MAXDEPTH -1
61 #define BRANCHRULE_MAXBOUNDDIST 1.0
62 
63 
64 /*
65  * Callback methods for enforcing branching constraints
66  */
67 
71 static
73  SCIP* scip
74 )
75 {
76  assert(scip != NULL);
77 
78  SCIP_CALL( SCIPincludeBranchruleAllfullstrong(scip) );
79  SCIP_CALL( SCIPincludeBranchruleFullstrong(scip) );
80  SCIP_CALL( SCIPincludeBranchruleInference(scip) );
81  SCIP_CALL( SCIPincludeBranchruleMostinf(scip) );
82  SCIP_CALL( SCIPincludeBranchruleLeastinf(scip) );
83  SCIP_CALL( SCIPincludeBranchrulePscost(scip) );
84  SCIP_CALL( SCIPincludeBranchruleRandom(scip) );
85  SCIP_CALL( SCIPincludeBranchruleRelpscost(scip) );
86 
87  return SCIP_OKAY;
88 }
89 
93 static
95  SCIP* scip,
96  SCIP_NODE* childnode,
97  SCIP_CONS* masterbranchchildcons
98 )
99 {
100  char* consname;
101  SCIP_BRANCHRULE* branchrule;
102  GCG_BRANCHDATA* branchdata;
103  SCIP_CONS* origcons;
104  SCIP_CONS** origbranchconss;
105  int norigbranchconss;
106 
107  int i;
108 
109  assert(scip != NULL);
110  assert(masterbranchchildcons != NULL);
111 
112  /* get name and branching information from the corresponding masterbranch constraint */
113  consname = GCGconsMasterbranchGetName(masterbranchchildcons);
114  branchrule = GCGconsMasterbranchGetBranchrule(masterbranchchildcons);
115  branchdata = GCGconsMasterbranchGetBranchdata(masterbranchchildcons);
116 
117  /* create an origbranch constraint and add it to the node */
118  SCIPdebugMessage("Create original branching constraint %s\n", consname);
119  SCIP_CALL( GCGcreateConsOrigbranch(scip, &origcons, consname, childnode,
120  GCGconsOrigbranchGetActiveCons(scip), branchrule, branchdata) );
121  if( branchdata == NULL )
122  {
123  SCIPdebugMessage("origbranch with no branchdata created\n");
124  }
125  SCIP_CALL( SCIPaddConsNode(scip, childnode, origcons, NULL) );
126 
127  /* add those constraints to the node that enforce the branching decision in the original problem */
128  origbranchconss = GCGconsMasterbranchGetOrigbranchConss(masterbranchchildcons);
129  norigbranchconss = GCGconsMasterbranchGetNOrigbranchConss(masterbranchchildcons);
130  for( i = 0; i < norigbranchconss; ++i )
131  {
132  SCIP_CALL( SCIPaddConsNode(scip, childnode, origbranchconss[i], NULL) );
133  }
134 
135  /* notify the original and master branching constraint about each other */
136  GCGconsOrigbranchSetMastercons(origcons, masterbranchchildcons);
137  GCGconsMasterbranchSetOrigcons(masterbranchchildcons, origcons);
138 
139  SCIP_CALL( SCIPreleaseCons(scip, &origcons) );
140 
141  /* release array of original branching constraints */
142  SCIP_CALL( GCGconsMasterbranchReleaseOrigbranchConss(GCGgetMasterprob(scip), scip, masterbranchchildcons) );
143 
144  return SCIP_OKAY;
145 }
146 
147 /* apply a branching decision on the original variables to the corresponding node */
148 static
150  SCIP* scip,
151  SCIP_NODE* childnode,
152  SCIP_CONS* masterbranchchildcons
153  )
154 {
155  GCG_BRANCHDATA* branchdata;
156  SCIP_VAR* boundvar;
157  GCG_BOUNDTYPE boundtype;
158  SCIP_Real newbound;
159 
160  /* get branching decision */
161  branchdata = GCGconsMasterbranchGetBranchdata(masterbranchchildcons);
162  assert(branchdata != NULL);
163  boundvar = GCGbranchOrigGetOrigvar(branchdata);
164  boundtype = GCGbranchOrigGetBoundtype(branchdata);
165  newbound = GCGbranchOrigGetNewbound(branchdata);
166 
167  assert(boundvar != NULL);
168  assert(boundtype == GCG_BOUNDTYPE_LOWER || boundtype == GCG_BOUNDTYPE_UPPER || boundtype == GCG_BOUNDTYPE_FIXED);
169 
170  if( boundtype == GCG_BOUNDTYPE_LOWER || boundtype == GCG_BOUNDTYPE_FIXED )
171  {
172  SCIP_CALL( SCIPchgVarLbNode(scip, childnode, boundvar, newbound) );
173  }
174 
175  if( boundtype == GCG_BOUNDTYPE_UPPER || boundtype == GCG_BOUNDTYPE_FIXED )
176  {
177  SCIP_CALL( SCIPchgVarUbNode(scip, childnode, boundvar, newbound) );
178  }
179 
180  if( GCGvarGetBlock(boundvar) == -1 )
181  {
182  SCIP_CALL( GCGconsMasterbranchAddCopiedVarBndchg(GCGgetMasterprob(scip), masterbranchchildcons,
183  boundvar, boundtype, newbound) );
184  }
185 
186  return SCIP_OKAY;
187 }
188 
190 static
192  SCIP* scip,
193  SCIP_RESULT* result
194 )
195 {
196  SCIP* masterscip;
197  SCIP_BRANCHRULE* branchrule;
198  SCIP_CONS* masterbranchcons;
199  int nchildnodes;
200  SCIP_Bool enforcebycons;
201 
202  int i;
203 
204  assert(scip != NULL);
205  assert(result != NULL);
206 
207  *result = SCIP_DIDNOTRUN;
208 
209  /* get master problem */
210  masterscip = GCGgetMasterprob(scip);
211  assert(masterscip != NULL);
212 
213  /* get masterbranch constraint at the current node */
214  masterbranchcons = GCGconsMasterbranchGetActiveCons(masterscip);
215 
216  /* @todo: Why should this happen? */
217  if( masterbranchcons == NULL )
218  return SCIP_OKAY;
219 
220  /* get the children of the current node */
221  nchildnodes = GCGconsMasterbranchGetNChildconss(masterbranchcons);
222 
223  /* check if the focus node of the master problem has children */
224  if( nchildnodes <= 0 && SCIPgetStage(masterscip) != SCIP_STAGE_SOLVED && SCIPgetNChildren(masterscip) >= 1 )
225  {
226  SCIP_NODE* child;
227 
228  SCIPdebugMessage("create dummy child in origprob, because there is also a child in the master\n");
229 
230  /* create dummy child */
231  SCIP_CALL( SCIPcreateChild(scip, &child, 0.0, SCIPgetLocalTransEstimate(scip)) );
232 
233  *result = SCIP_BRANCHED;
234  return SCIP_OKAY;
235  }
236 
237  if( nchildnodes <= 0 )
238  {
239  SCIPdebugMessage("node cut off, since there is no successor node\n");
240 
241  *result = SCIP_CUTOFF;
242  return SCIP_OKAY;
243  }
244 
245  SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/enforcebycons", &enforcebycons) );
246 
247  /* for each child, create a corresponding node in the original problem as well as an origbranch constraint */
248  for( i = 0; i < nchildnodes; ++i )
249  {
250  SCIP_NODE* childnode;
251  SCIP_CONS* masterbranchchildcons = GCGconsMasterbranchGetChildcons(masterbranchcons, i);
252  assert(masterbranchchildcons != NULL);
253 
254  /* create a child node and an origbranch constraint holding the branching decision */
255  SCIP_CALL( SCIPcreateChild(scip, &childnode, 0.0, SCIPgetLocalTransEstimate(scip)) );
256  SCIP_CALL( createOrigbranchConstraint(scip, childnode, masterbranchchildcons) );
257 
258  /* get branching rule */
259  branchrule = GCGconsMasterbranchGetBranchrule(masterbranchchildcons);
260 
261  /* If a branching decision on an original variable was made, apply it */
262  if( !enforcebycons && branchrule != NULL && strcmp(SCIPbranchruleGetName(branchrule), "orig") == 0 )
263  {
264  SCIP_CALL( applyOriginalBranching(scip, childnode, masterbranchchildcons) );
265  }
266 
267  /* @fixme: this should actually be an assertion */
269  {
270  #ifdef SCIP_DEBUG
271  SCIPwarningMessage(scip, "norignodes = %lld; nmasternodes = %lld\n",
274  #endif
275  }
276  }
277 
278  *result = SCIP_BRANCHED;
279 
280  assert(nchildnodes > 0);
281 
282  return SCIP_OKAY;
283 }
284 
285 
287 static
288 SCIP_DECL_BRANCHCOPY(branchCopyEmpty)
289 {
290  assert(branchrule != NULL);
291  assert(scip != NULL);
292 
293  /* SubSCIPs are solved with SCIP rather than GCG;
294  * therefore, only the default SCIP branching rules are included into the subSCIP.
295  */
296  SCIP_CALL( includeSCIPBranchingRules(scip) );
297 
298  return SCIP_OKAY;
299 }
300 
302 #define branchFreeEmpty NULL
303 
305 #define branchInitEmpty NULL
306 
308 #define branchExitEmpty NULL
309 
311 #define branchInitsolEmpty NULL
312 
314 #define branchExitsolEmpty NULL
315 
317 static
318 SCIP_DECL_BRANCHEXECLP(branchExeclpEmpty)
319 { /*lint --e{715}*/
320  assert(branchrule != NULL);
321  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
322  assert(scip != NULL);
323  assert(result != NULL);
324 
325  SCIP_CALL( createBranchNodesInOrigprob(scip, result) );
326 
327  return SCIP_OKAY;
328 }
329 
331 static
332 SCIP_DECL_BRANCHEXECEXT(branchExecextEmpty)
333 { /*lint --e{715}*/
334  assert(branchrule != NULL);
335  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
336  assert(scip != NULL);
337  assert(result != NULL);
338 
339  SCIP_CALL( createBranchNodesInOrigprob(scip, result) );
340 
341  return SCIP_OKAY;
342 }
343 
345 static
346 SCIP_DECL_BRANCHEXECPS(branchExecpsEmpty)
347 { /*lint --e{715}*/
348  assert(branchrule != NULL);
349  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
350  assert(scip != NULL);
351  assert(result != NULL);
352 
353  SCIP_CALL( createBranchNodesInOrigprob(scip, result) );
354 
355  return SCIP_OKAY;
356 }
357 
358 
359 /*
360  * branching specific interface methods
361  */
362 
365  SCIP* scip
366 )
367 {
368  SCIP_BRANCHRULEDATA* branchruledata;
369 
370  /* create inference branching rule data */
371  branchruledata = NULL;
372 
373  /* include branching rule */
374  SCIP_CALL( SCIPincludeBranchrule(scip, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
377  branchExitsolEmpty, branchExeclpEmpty, branchExecextEmpty, branchExecpsEmpty,
378  branchruledata) );
379 
380  return SCIP_OKAY;
381 }
#define branchInitEmpty
Definition: branch_empty.c:305
int GCGconsMasterbranchGetNChildconss(SCIP_CONS *cons)
#define BRANCHRULE_MAXDEPTH
Definition: branch_empty.c:60
SCIP_BRANCHRULE * GCGconsMasterbranchGetBranchrule(SCIP_CONS *cons)
branching rule for original problem in GCG
branching rule for original problem in GCG while real branching is in the master
static SCIP_RETCODE applyOriginalBranching(SCIP *scip, SCIP_NODE *childnode, SCIP_CONS *masterbranchchildcons)
Definition: branch_empty.c:149
GCG interface methods.
SCIP_NODE * GCGconsOrigbranchGetNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeBranchruleEmpty(SCIP *scip)
Definition: branch_empty.c:364
static SCIP_RETCODE createOrigbranchConstraint(SCIP *scip, SCIP_NODE *childnode, SCIP_CONS *masterbranchchildcons)
Definition: branch_empty.c:94
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
static SCIP_RETCODE createBranchNodesInOrigprob(SCIP *scip, SCIP_RESULT *result)
Definition: branch_empty.c:191
SCIP_VAR * GCGbranchOrigGetOrigvar(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:950
#define BRANCHRULE_NAME
Definition: branch_empty.c:57
SCIP_CONS ** GCGconsMasterbranchGetOrigbranchConss(SCIP_CONS *cons)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
static SCIP_DECL_BRANCHEXECPS(branchExecpsEmpty)
Definition: branch_empty.c:346
enum GCG_BoundType GCG_BOUNDTYPE
SCIP_CONS * GCGconsMasterbranchGetChildcons(SCIP_CONS *cons, int childnr)
SCIP_Real GCGbranchOrigGetNewbound(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:970
void GCGconsOrigbranchSetMastercons(SCIP_CONS *cons, SCIP_CONS *mastercons)
static SCIP_DECL_BRANCHEXECLP(branchExeclpEmpty)
Definition: branch_empty.c:318
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_empty.c:61
#define BRANCHRULE_PRIORITY
Definition: branch_empty.c:59
SCIP_CONS * GCGconsOrigbranchGetActiveCons(SCIP *scip)
GCG relaxator.
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
char * GCGconsMasterbranchGetName(SCIP_CONS *cons)
static SCIP_RETCODE includeSCIPBranchingRules(SCIP *scip)
Definition: branch_empty.c:72
SCIP_RETCODE GCGcreateConsOrigbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
#define branchInitsolEmpty
Definition: branch_empty.c:311
GCG_BOUNDTYPE GCGbranchOrigGetBoundtype(GCG_BRANCHDATA *branchdata)
Definition: branch_orig.c:960
SCIP_NODE * GCGconsMasterbranchGetNode(SCIP_CONS *cons)
type definitions for branching rules in GCG projects
static SCIP_DECL_BRANCHCOPY(branchCopyEmpty)
Definition: branch_empty.c:288
constraint handler for storing the branching decisions at each node of the tree
int GCGconsMasterbranchGetNOrigbranchConss(SCIP_CONS *cons)
#define branchExitsolEmpty
Definition: branch_empty.c:314
GCG_BRANCHDATA * GCGconsMasterbranchGetBranchdata(SCIP_CONS *cons)
SCIP_RETCODE GCGconsMasterbranchReleaseOrigbranchConss(SCIP *masterscip, SCIP *origscip, SCIP_CONS *cons)
constraint handler for storing the branching decisions at each node of the tree
#define branchFreeEmpty
Definition: branch_empty.c:302
static SCIP_DECL_BRANCHEXECEXT(branchExecextEmpty)
Definition: branch_empty.c:332
#define branchExitEmpty
Definition: branch_empty.c:308
void GCGconsMasterbranchSetOrigcons(SCIP_CONS *cons, SCIP_CONS *origcons)
SCIP_RETCODE GCGconsMasterbranchAddCopiedVarBndchg(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, GCG_BOUNDTYPE boundtype, SCIP_Real newbound)
#define BRANCHRULE_DESC
Definition: branch_empty.c:58