Scippy

SCIP

Solving Constraint Integer Programs

branch_multinode.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_multinode.c
17  * @brief mutlinode branching rule for the set-partitioning part in cycle clustering application.
18  * @author Leon Eifler
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 
25 #include "branch_multinode.h"
26 
27 #include "probdata_cyc.h"
28 #include "scip/branch_relpscost.h"
29 
30 
31 #define BRANCHRULE_NAME "multinode"
32 #define BRANCHRULE_DESC "multinode branching creates a child for every variable of a setpartitioning constraint"
33 #define BRANCHRULE_PRIORITY 10000000
34 #define BRANCHRULE_MAXDEPTH -1
35 #define BRANCHRULE_MAXBOUNDDIST 1.0
36 
37 /*
38  * Local methods
39  */
40 
41 /* put your local methods here, and declare them static */
42 
43 /** get the branching candidates viable for multinode branching */
44 static
46  SCIP* scip, /**< SCIP data structure */
47  SCIP_VAR** branchcands, /**< the address of the branching candidates */
48  SCIP_Real* branchcandssol, /**< pointer to solution values of the candidates */
49  SCIP_Real* branchcandsfrac, /**< pointer to fractionalities of the candidates */
50  int* ncands /**< number of branching candidates */
51  )
52 {
53  SCIP_VAR*** binvars;
54  int nbins;
55  int ncluster;
56  int i;
57  int k;
58 
59  nbins = SCIPcycGetNBins(scip);
60  ncluster = SCIPcycGetNCluster(scip);
61  binvars = SCIPcycGetBinvars(scip);
62 
63  /* all binvars that are in the lp, and have fractional values are viable candidates */
64  for( i = 0; i < nbins; ++i )
65  {
66  for( k = 0; k < ncluster; ++k )
67  {
68  if( SCIPvarGetStatus(binvars[i][k]) == SCIP_VARSTATUS_COLUMN
69  && !SCIPisFeasIntegral(scip, SCIPvarGetLPSol(binvars[i][k])) )
70  {
71  (branchcands)[*ncands] = binvars[i][k];
72  (branchcandssol)[*ncands] = SCIPvarGetLPSol(binvars[i][k]);
73  (branchcandsfrac)[*ncands] = MAX(1-(branchcandssol)[*ncands], (branchcandssol)[*ncands]);
74  (*ncands)++;
75  }
76  }
77  }
78 
79  return SCIP_OKAY;
80 }
81 
82 /** branch on a selected bin -> Create at most |Cluster| children */
83 static
85  SCIP* scip, /**< SCIP data structure */
86  int row, /**< the row in the binvar-matrix (not lp-row) to be branched on */
87  SCIP_RESULT* result /**< pointer to store result of branching */
88  )
89 {
90  SCIP_VAR*** binvars;
91  SCIP_Bool* branched;
92  SCIP_Real priority;
93  SCIP_Real estimate;
94  SCIP_Real minestzero = SCIP_INVALID;
95  SCIP_Real tmp;
96  SCIP_NODE* node;
97  int ncands = 0;
98  int k;
99  int ncluster;
100 
101  binvars = SCIPcycGetBinvars(scip);
102  ncluster = SCIPcycGetNCluster(scip);
103  assert(NULL != binvars[row]);
104 
105  SCIP_CALL( SCIPallocClearBufferArray(scip, &branched, ncluster) );
106 
107  /* check all candidates */
108  for( k = 0; k < ncluster; ++k )
109  {
110  if( (SCIPvarGetStatus(binvars[row][k]) == SCIP_VARSTATUS_LOOSE ||
111  SCIPvarGetStatus(binvars[row][k]) == SCIP_VARSTATUS_COLUMN) &&
112  !SCIPisZero(scip, SCIPvarGetLPSol(binvars[row][k])) && !SCIPisEQ(scip, SCIPvarGetLPSol(binvars[row][k]), 1.0) )
113  {
114  ncands++;
115  priority = SCIPcalcNodeselPriority(scip, binvars[row][k], SCIP_BRANCHDIR_UPWARDS, 1.0);
116  estimate = SCIPcalcChildEstimate(scip, binvars[row][k], 1.0);
117  tmp = SCIPcalcChildEstimate(scip, binvars[row][k], 0.0);
118  minestzero = MIN(tmp, minestzero);
119 
120  /* branch all viable candidates upwards */
121  SCIP_CALL( SCIPcreateChild(scip, &node, priority, estimate) );
122  SCIP_CALL( SCIPchgVarLbNode(scip, node, binvars[row][k], 1.0) );
123 
124  branched[k] = TRUE;
125 
126  *result = SCIP_BRANCHED;
127  if( ncands > 2 )
128  break;
129  }
130  }
131 
132  /* create one child, were all the before upwards branched variables are now set to 0. Only do so if at least one
133  * upwards branching was done and if not all the variables were branched upwards
134  */
135  if( ncands > 0 && ncands < ncluster )
136  {
137  SCIP_CALL( SCIPcreateChild(scip, &node, (SCIP_Real)ncands, minestzero) );
138  for( k = 0; k < ncluster; ++k )
139  {
140  if( branched[k] )
141  {
142  SCIP_CALL( SCIPchgVarUbNode(scip, node, binvars[row][k], 0.0) );
143  }
144  }
145  }
146 
147  SCIPfreeBufferArray(scip, &branched);
148 
149  return SCIP_OKAY;
150 }
151 
152 /*
153  * Callback methods of branching rule
154  */
155 
156 /** branching execution method for fractional LP solutions */
157 static
158 SCIP_DECL_BRANCHEXECLP(branchExeclpMultinode)
159 { /*lint --e{715}*/
160  int i;
161  int k;
162  int nbins;
163  int ncluster;
164  int ncands;
165 
166  SCIP_Real* score;
167  SCIP_Real max;
168  int maxrow;
169  SCIP_VAR*** binvars;
170  SCIP_VAR** branchcands;
171  SCIP_Real* branchcandssol;
172  SCIP_Real* branchcandsfrac;
173 
174  binvars = SCIPcycGetBinvars(scip);
175  nbins = SCIPcycGetNBins(scip);
176  ncluster = SCIPcycGetNCluster(scip);
177  *result = SCIP_DIDNOTRUN;
178 
179  assert(nbins > 0);
180  assert(ncluster > 0 && ncluster <= nbins);
181 
182  SCIP_CALL( SCIPallocClearBufferArray(scip, &score, nbins) );
183  SCIP_CALL( SCIPallocClearBufferArray(scip, &branchcands, (SCIP_Longint) nbins * ncluster) );
184  SCIP_CALL( SCIPallocClearBufferArray(scip, &branchcandssol, (SCIP_Longint) nbins * ncluster) );
185  SCIP_CALL( SCIPallocClearBufferArray(scip, &branchcandsfrac, (SCIP_Longint) nbins * ncluster) );
186 
187  ncands = 0;
188  /* get the candidates */
189  SCIP_CALL( getBranchCands( scip, branchcands, branchcandssol, branchcandsfrac, &ncands) );
190  if( ncands != 0 )
191  {
192  /* compute the relpcost for the candidates */
193  SCIP_CALL( SCIPexecRelpscostBranching(scip, branchcands, branchcandssol, branchcandsfrac, ncands, FALSE, result) );
194 
195  assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM);
196 
197  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM )
198  {
199  maxrow = -1;
200  max = -SCIPinfinity(scip);
201 
202  /* compute the best candidate from pseudocostscore */
203  for( i = 0; i < nbins; ++i )
204  {
205  score[i] = 0;
206 
207  for( k = 0; k < ncluster; ++k )
208  {
209  /* Do not branch on variables that are already fixed locally */
210  if( SCIPisEQ(scip, SCIPvarGetUbLocal(binvars[i][k]), SCIPvarGetLbLocal(binvars[i][k])) )
211  {
212  score[i] = -SCIPinfinity(scip);
213  break;
214  }
215 
216  if( SCIPvarGetStatus(binvars[i][k]) == SCIP_VARSTATUS_COLUMN &&
217  !SCIPisZero(scip, SCIPvarGetLPSol(binvars[i][k])) &&
218  !SCIPisEQ(scip, SCIPvarGetLPSol(binvars[i][k]), 1.0) )
219  {
220  score[i] += SCIPgetVarPseudocostScore(scip, binvars[i][k], SCIPvarGetLPSol(binvars[i][k]));
221  }
222  }
223 
224  if( SCIPisLT(scip, max, score[i]) && !SCIPisInfinity(scip, -score[i]) )
225  {
226  max = score[i];
227  maxrow = i;
228  }
229  }
230 
231  if( -1 != maxrow )
232  {
233  SCIP_CALL( branchOnBin(scip, maxrow, result) );
234  }
235  }
236  }
237 
238  /* free memory */
239  SCIPfreeBufferArray(scip, &score);
240  SCIPfreeBufferArray(scip, &branchcands);
241  SCIPfreeBufferArray(scip, &branchcandssol);
242  SCIPfreeBufferArray(scip, &branchcandsfrac);
243 
244  return SCIP_OKAY;
245 }
246 
247 /*
248  * branching rule specific interface methods
249  */
250 
251 /** creates the mutlinode branching rule and includes it in SCIP */
253  SCIP* scip /**< SCIP data structure */
254  )
255 {
256  SCIP_BRANCHRULEDATA* branchruledata;
257  SCIP_BRANCHRULE* branchrule;
258 
259  branchruledata = NULL;
260 
261  /* include branching rule */
262  /* use SCIPincludeBranchruleBasic() plus setter functions if you want to set callbacks one-by-one
263  * and your code should compile independent of new callbacks being added in future SCIP versions
264  */
266  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
267 
268  assert(branchrule != NULL);
269 
270  /* set non fundamental callbacks via setter functions */
271  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMultinode) );
272 
273  return SCIP_OKAY;
274 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
reliable pseudo costs branching rule
static SCIP_RETCODE branchOnBin(SCIP *scip, int row, SCIP_RESULT *result)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4840
#define BRANCHRULE_DESC
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18041
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPincludeBranchruleMultinode(SCIP *scip)
static SCIP_RETCODE getBranchCands(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int *ncands)
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17136
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip_var.c:9031
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:107
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BRANCHRULE_PRIORITY
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:911
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define NULL
Definition: lpi_spx1.cpp:155
multinode branching rule
#define SCIP_CALL(x)
Definition: def.h:370
#define BRANCHRULE_MAXDEPTH
int SCIPcycGetNBins(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
static SCIP_DECL_BRANCHEXECLP(branchExeclpMultinode)
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
problem data for cycle clustering problem
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:938
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
int SCIPcycGetNCluster(SCIP *scip)
#define BRANCHRULE_NAME
#define SCIP_Real
Definition: def.h:163
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_INVALID
Definition: def.h:183
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4884
#define BRANCHRULE_MAXBOUNDDIST
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)