Scippy

GCG

Branch-and-Price & Column Generation for Everyone

nodesel_master.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-2021 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 
28 /**@file nodesel_master.c
29  * @ingroup NODESELECTORS
30  * @brief node selector for coordination of master and original formulation
31  * @author Gerald Gamrath
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "nodesel_master.h"
40 #include "cons_origbranch.h"
41 #include "cons_masterbranch.h"
42 #include "pricer_gcg.h"
43 
44 #define NODESEL_NAME "master"
45 #define NODESEL_DESC "orig master coordination"
46 #define NODESEL_STDPRIORITY 0
47 #define NODESEL_MEMSAVEPRIORITY 100000
48 
49 
50 /** node selector data */
52 {
53  SCIP_Longint lastorignodenumber;
54 };
55 
56 /*
57  * Callback methods
58  */
59 
60 #define nodeselCopyMaster NULL
61 
62 /** destructor of node selector to free user data (called when SCIP is exiting) */
63 static
64 SCIP_DECL_NODESELFREE(nodeselFreeMaster)
65 {
66  SCIP_NODESELDATA* nodeseldata;
67 
68  assert(nodesel != NULL);
69 
70  nodeseldata = SCIPnodeselGetData(nodesel);
71  assert(nodeseldata != NULL);
72 
73  SCIPfreeMemory(scip, &nodeseldata);
74 
75  return SCIP_OKAY;
76 }
77 
78 
79 /** initialization method of node selector (called after problem was transformed) */
80 #define nodeselInitMaster NULL
81 
82 
83 /** deinitialization method of node selector (called before transformed problem is freed) */
84 #define nodeselExitMaster NULL
85 
86 
87 /** solving process initialization method of node selector (called when branch and bound process is about to begin) */
88 #define nodeselInitsolMaster NULL
89 
90 
91 /** solving process deinitialization method of node selector (called before branch and bound process data is freed) */
92 #define nodeselExitsolMaster NULL
93 
94 
95 /** node selection method of node selector */
96 static
97 SCIP_DECL_NODESELSELECT(nodeselSelectMaster)
98 {
99  SCIP_NODESELDATA* nodeseldata;
100  SCIP_NODE** nodes;
101  SCIP* origscip;
102  int nnodes;
103  SCIP_Longint orignodenumber;
104 
105  assert(nodesel != NULL);
106  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
107  assert(scip != NULL);
108  assert(selnode != NULL);
109 
110  nodeseldata = SCIPnodeselGetData(nodesel);
111  assert(nodeseldata != NULL);
112 
113  origscip = GCGmasterGetOrigprob(scip);
114 
115  *selnode = NULL;
116 
117  orignodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(origscip));
118 
119  if( orignodenumber != nodeseldata->lastorignodenumber )
120  {
121  SCIP_CONS* origcons = GCGconsOrigbranchGetActiveCons(origscip);
122  SCIP_CONS* parentorigcons = GCGconsOrigbranchGetParentcons(origcons);
123 
124  nodeseldata->lastorignodenumber = orignodenumber;
125 
126  /* check whether the current node is the root node and has no parent */
127  if( parentorigcons == NULL )
128  {
129  assert((GCGconsOrigbranchGetNode(origcons) == SCIPgetRootNode(origscip)) || ( GCGconsOrigbranchGetNode(origcons) == NULL) );
130  assert(GCGconsOrigbranchGetMastercons(origcons) != NULL);
131  assert((GCGconsMasterbranchGetNode(GCGconsOrigbranchGetMastercons(origcons)) == SCIPgetRootNode(scip)) || (GCGconsMasterbranchGetNode(GCGconsOrigbranchGetMastercons(origcons)) == NULL));
132 
133  *selnode = SCIPgetRootNode(scip);
134  SCIPdebugMessage("selected root node in the master program\n");
135  }
136  else
137  {
138 
139  assert(GCGconsOrigbranchGetMastercons(parentorigcons) != NULL);
141 
142  assert(SCIPnodeGetDepth(GCGconsMasterbranchGetNode(GCGconsOrigbranchGetMastercons(parentorigcons))) == SCIPnodeGetDepth(GCGconsOrigbranchGetNode(parentorigcons)));
143  assert( *selnode != NULL );
144  }
145 
146  if( *selnode == NULL )
147  {
148  SCIPerrorMessage("nodesel_master could not find a node corresponding to the current original node!\n");
149  }
150  assert(*selnode != NULL);
151 
152  /* set the dual bound to the lower bound of the corresponding original node */
153  SCIP_CALL( SCIPupdateNodeDualbound(scip, *selnode, SCIPgetNodeLowerbound(origscip, SCIPgetCurrentNode(origscip))) );
154  }
155  else
156  {
157  SCIPdebugMessage("select random node\n");
158 
159  if( SCIPgetNChildren(scip) > 0 )
160  {
161  SCIP_CALL( SCIPgetChildren(scip, &nodes, &nnodes) );
162  *selnode = nodes[0];
163  }
164  else if( SCIPgetNSiblings(scip) > 0 )
165  {
166  SCIP_CALL( SCIPgetSiblings(scip, &nodes, &nnodes) );
167  *selnode = nodes[0];
168  }
169  else if( SCIPgetNLeaves(scip) > 0 )
170  {
171  SCIP_CALL( SCIPgetLeaves(scip, &nodes, &nnodes) );
172  *selnode = nodes[0];
173  }
174  }
175 
176 #ifndef NDEBUG
179 #endif
180 
181  return SCIP_OKAY;
182 }
183 
184 
185 /** node comparison method of node selector */
186 static
187 SCIP_DECL_NODESELCOMP(nodeselCompMaster)
188 {
189  assert(nodesel != NULL);
190  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
191  assert(scip != NULL);
192 
193  if( SCIPnodeGetNumber(node1) < SCIPnodeGetNumber(node2) )
194  return 1;
195  else
196  return -1;
197 }
198 
199 /*
200  * master specific interface methods
201  */
202 
203 /** creates the node selector for depth first search and includes it in SCIP */
205  SCIP* scip /**< SCIP data structure */
206 )
207 {
208  SCIP_NODESELDATA* nodeseldata;
209 
210  /* create master node selector data */
211  SCIP_CALL( SCIPallocMemory(scip, &nodeseldata) );
212 
213  nodeseldata->lastorignodenumber = -1LL;
214 
215  /* include node selector */
216  SCIP_CALL( SCIPincludeNodesel(scip, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
218  nodeselInitsolMaster, nodeselExitsolMaster, nodeselSelectMaster, nodeselCompMaster,
219  nodeseldata) );
220 
221  return SCIP_OKAY;
222 }
223 
SCIP_NODE * GCGconsOrigbranchGetNode(SCIP_CONS *cons)
void GCGconsOrigbranchCheckConsistency(SCIP *scip)
static SCIP_DECL_NODESELSELECT(nodeselSelectMaster)
static SCIP_DECL_NODESELFREE(nodeselFreeMaster)
SCIP_Longint lastorignodenumber
#define nodeselInitMaster
#define NODESEL_MEMSAVEPRIORITY
#define nodeselCopyMaster
GCG variable pricer.
SCIP_NODE * GCGconsMasterbranchGetNode(SCIP_CONS *cons)
SCIP_CONS * GCGconsOrigbranchGetActiveCons(SCIP *scip)
constraint handler for storing the branching decisions at each node of the tree
#define NODESEL_DESC
constraint handler for storing the branching decisions at each node of the tree
SCIP_CONS * GCGconsOrigbranchGetParentcons(SCIP_CONS *cons)
SCIP * GCGmasterGetOrigprob(SCIP *scip)
static SCIP_DECL_NODESELCOMP(nodeselCompMaster)
#define nodeselInitsolMaster
#define NODESEL_NAME
#define nodeselExitMaster
Node selector for coordination of master and original formulation.
#define NODESEL_STDPRIORITY
#define nodeselExitsolMaster
SCIP_RETCODE SCIPincludeNodeselMaster(SCIP *scip)
void GCGconsMasterbranchCheckConsistency(SCIP *scip)
SCIP_CONS * GCGconsOrigbranchGetMastercons(SCIP_CONS *cons)