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