Scippy

SCIP

Solving Constraint Integer Programs

heur_indicatordiving.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-2024 Zuse Institute Berlin (ZIB) */
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 heur_indicatordiving.c
26  * @ingroup DEFPLUGINS_HEUR
27  * @brief LP diving heuristic that fixes indicator variables controlling semicontinuous variables
28  * @author Katrin Halbig
29  * @author Alexander Hoen
30  *
31  * A diving heuristic iteratively rounds some fractional variables or variables determined by constraint handlers,
32  * and resolves the LP relaxation. Thereby simulating a depth-first-search in the tree.
33  *
34  * Indicatordiving focuses on indicator variables, which control semicontinuous variables.
35  * If the semicontinuous variable is unbounded, the indicator constraint is not part of the LP and,
36  * therefore, the indicator variable is not set to an useful value in the LP solution.
37  *
38  * For these indicator variables the score depends on the LP value and the bounds of the corresponding semicontinuous variable.
39  * If parameter usevarbounds=TRUE, also varbound constraints modeling semicontinuous variables are considered.
40  * For all other variables the Farkas score (scaled) is returned.
41  */
42 
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 
45 #include <assert.h>
46 
47 #include "scip/cons_indicator.h"
48 #include "scip/cons_varbound.h"
50 #include "scip/heuristics.h"
51 #include "scip/pub_cons.h"
52 #include "scip/pub_heur.h"
53 #include "scip/pub_message.h"
54 #include "scip/pub_misc.h"
55 #include "scip/pub_var.h"
56 #include "scip/scip_cons.h"
57 #include "scip/scip_heur.h"
58 #include "scip/scip_mem.h"
59 #include "scip/scip_numerics.h"
60 #include "scip/scip_param.h"
61 #include "scip/scip_probing.h"
62 #include "scip/scip_sol.h"
63 #include "scip/scip_tree.h"
64 #include "scip/scip_prob.h"
65 #include "scip/scip_message.h"
66 
67 #define HEUR_NAME "indicatordiving"
68 #define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables"
69 #define HEUR_DISPCHAR 'I'
70 #define HEUR_PRIORITY -150000
71 #define HEUR_FREQ 0
72 #define HEUR_FREQOFS 0
73 #define HEUR_MAXDEPTH -1
74 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
75 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
76 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
77 #define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
78 
79 
80 /*
81  * Default parameter settings
82  */
83 
84 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
85 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
86 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
87 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
88 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
89  * where diving is performed (0.0: no limit) */
90 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
91  * where diving is performed (0.0: no limit) */
92 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
93 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
94 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
95 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
96 #define DEFAULT_LPSOLVEFREQ 30 /**< LP solve frequency for diving heuristics */
97 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
98  * more general constraint handler diving variable selection? */
99 #define DEFAULT_RANDSEED 11 /**< initial seed for random number generation */
100 
101 /*
102  * Heuristic specific parameters
103  */
104 #define DEFAULT_ROUNDINGFRAC 0.5 /**< default setting for parameter roundingfrac */
105 #define DEFAULT_ROUNDINGMODE 0 /**< default setting for parameter roundingmode */
106 #define DEFAULT_SEMICONTSCOREMODE 0 /**< default setting for parameter semicontscoremode */
107 #define DEFAULT_USEVARBOUNDS TRUE /**< default setting for parameter usevarbounds */
108 #define DEFAULT_RUNWITHOUTSCINDS FALSE /**< default setting for parameter runwithoutscinds */
111 {
114 };
117 /** data structure to store information of a semicontinuous variable
118  *
119  * For a variable x (not stored in the struct), this stores the data of nbnds implications
120  * bvars[i] = 0 -> x = vals[i]
121  * bvars[i] = 1 -> lbs[i] <= x <= ubs[i]
122  * where bvars[i] are binary variables.
123  */
124 struct SCVarData
125 {
126  SCIP_Real* vals0; /**< values of the variable when the corresponding bvars[i] = 0 */
127  SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */
128  SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */
129  SCIP_VAR** bvars; /**< the binary variables on which the variable domain depends */
130  int nbnds; /**< number of suitable on/off bounds the var has */
131  int bndssize; /**< size of the arrays */
132 };
133 typedef struct SCVarData SCVARDATA;
135 
136 /** locally defined heuristic data */
137 struct SCIP_HeurData
138 {
139  SCIP_SOL* sol; /**< working solution */
140  SCIP_CONSHDLR* indicatorconshdlr; /**< indicator constraint handler */
141  SCIP_CONSHDLR* varboundconshdlr; /**< varbound constraint handler */
142  SCIP_HASHMAP* scvars; /**< hashmap to store semicontinuous variables */
143  SCIP_HASHMAP* indicatormap; /**< hashmap to store indicator constraints of binary variables */
144  SCIP_HASHMAP* varboundmap; /**< hashmap to store varbound constraints of binary variables */
145  SCIP_Real roundingfrac; /**< in violation case all fractional below this value are fixed to constant */
146  int roundingmode; /**< decides which roundingmode is selected (0: conservative (default), 1: aggressive) */
147  int semicontscoremode; /**< which values of semi-continuous variables should get a high score? (0: low (default), 1: middle, 2: high) */
148  SCIP_Bool usevarbounds; /**< should varbound constraints be considered? */
149  SCIP_Bool runwithoutscinds; /**< should heur run if there are no indicator constraints modeling semicont. vars? */
150  SCIP_Bool gotoindconss; /**< can we skip the candidate var until indicator conss handler determines the candidate var? */
151  SCIP_Bool containsviolindconss;/**< contains current solution violated indicator constraints? (only unbounded) */
152  SCIP_Bool newnode; /**< are we at a new probing node? */
153  int probingdepth; /**< current probing depth */
154 };
155 
156 /*
157  * Local methods
158  */
159 
160 /** checks if constraint is violated but not fixed, i.e., it will be a diving candidate variable */
161 static
163  SCIP* scip, /**< SCIP data structure */
164  SCIP_SOL* sol, /**< pointer to solution */
165  SCIP_CONS* cons /**< pointer to indicator constraint */
166  )
167 {
168  SCIP_VAR* binvar;
169  SCIP_Real solval;
170 
171  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "indicator") == 0);
172 
173  if( !SCIPisViolatedIndicator(scip, cons, sol) )
174  return FALSE;
175 
176  binvar = SCIPgetBinaryVarIndicator(cons);
177  solval = SCIPgetSolVal(scip, sol, binvar);
178 
179  return (SCIPisFeasIntegral(scip, solval) && SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5);
180 }
181 
182 /** releases all data from given hashmap filled with SCVarData and the hashmap itself */
183 static
185  SCIP* scip, /**< SCIP data structure */
186  SCIP_HASHMAP* hashmap /**< hashmap to be freed */
187  )
188 {
189  SCIP_HASHMAPENTRY* entry;
190  SCVARDATA* data;
191  int c;
192 
193  if( hashmap != NULL )
194  {
195  for( c = 0; c < SCIPhashmapGetNEntries( hashmap ); c++ )
196  {
197  entry = SCIPhashmapGetEntry( hashmap, c);
198  if( entry != NULL )
199  {
200  data = (SCVARDATA*) SCIPhashmapEntryGetImage(entry);
201  SCIPfreeBlockMemoryArray(scip, &data->ubs1, data->bndssize);
202  SCIPfreeBlockMemoryArray(scip, &data->lbs1, data->bndssize);
203  SCIPfreeBlockMemoryArray(scip, &data->vals0, data->bndssize);
204  SCIPfreeBlockMemoryArray(scip, &data->bvars, data->bndssize);
205  SCIPfreeBlockMemory(scip, &data);
206  }
207  }
208  SCIPhashmapFree(&hashmap);
209  assert(hashmap == NULL);
210  }
211 
212  return SCIP_OKAY;
213 }
214 
215 /** checks if variable is indicator variable and stores corresponding indicator constraint; additionally, if we are at a
216  * new probing node, it checks whether there are violated but not fixed indicator constraints
217  */
218 static
220  SCIP* scip, /**< SCIP data structure */
221  SCIP_VAR* cand, /**< candidate variable */
222  SCIP_HASHMAP* map, /**< pointer to hashmap containing indicator conss */
223  SCIP_CONS** cons, /**< pointer to store indicator constraint */
224  SCIP_Bool* isindicator, /**< pointer to store whether candidate variable is indicator variable */
225  SCIP_Bool* containsviolindconss,/**< pointer to store whether there are violated and not fixed (unbounded) indicator constraints */
226  SCIP_Bool newnode, /**< are we at a new probing node? */
227  SCIP_SOL* sol, /**< pointer to solution */
228  SCIP_CONSHDLR* conshdlr /**< constraint handler */
229  )
230 {
231  assert(scip != NULL);
232  assert(cand != NULL);
233  assert(map != NULL);
234  assert(cons != NULL);
235  assert(isindicator != NULL);
236  assert(sol != NULL);
237 
238  *cons = NULL;
239  *isindicator = FALSE;
240 
241  *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand);
242  if( *cons != NULL )
243  *isindicator = TRUE;
244 
245  /* since we are at a new probing node, check if there are violated and not fixed indicator constraints */
246  if( newnode )
247  {
248  SCIP_CONS** indicatorconss;
249  int nconss;
250  int c;
251 
252  indicatorconss = SCIPconshdlrGetConss(conshdlr);
253  nconss = SCIPconshdlrGetNActiveConss(conshdlr);
254  *containsviolindconss = FALSE;
255 
256  for( c = 0; c < nconss; c++ )
257  {
258  *containsviolindconss = *containsviolindconss || isViolatedAndNotFixed(scip, sol, indicatorconss[c]);
259 
260  if( *containsviolindconss )
261  break;
262  }
263  }
264 }
265 
266 /** checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint */
267 static
269  SCIP* scip, /**< SCIP data structure */
270  SCIP_VAR* cand, /**< candidate variable */
271  SCIP_HASHMAP* map, /**< pointer to hashmap containing varbound conss */
272  SCIP_CONS** cons, /**< pointer to store varbound constraint */
273  SCIP_Bool* isvarbound /**< pointer to store whether candidate variable is indicator variable */
274  )
275 {
276  assert(scip != NULL);
277  assert(cand != NULL);
278  assert(map != NULL);
279  assert(cons != NULL);
280  assert(isvarbound != NULL);
281 
282  *cons = NULL;
283  *isvarbound = FALSE;
284 
285  if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
286  return;
287 
288  *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand);
289  if( *cons != NULL )
290  *isvarbound = TRUE;
291 }
292 
293 /** adds an indicator to the data of a semicontinuous variable */
294 static
296  SCIP* scip, /**< SCIP data structure */
297  SCVARDATA* scvdata, /**< semicontinuous variable data */
298  SCIP_VAR* indicator, /**< indicator to be added */
299  SCIP_Real val0, /**< value of the variable when indicator == 0 */
300  SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */
301  SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */
302  )
303 {
304  int newsize;
305  int i;
306  SCIP_Bool found;
307  int pos;
308 
309  assert(scvdata != NULL);
310  assert(indicator != NULL);
311 
312  /* find the position where to insert */
313  if( scvdata->bvars == NULL )
314  {
315  assert(scvdata->nbnds == 0 && scvdata->bndssize == 0);
316  found = FALSE;
317  pos = 0;
318  }
319  else
320  {
321  found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos);
322  }
323 
324  if( found )
325  return SCIP_OKAY;
326 
327  /* ensure sizes */
328  if( scvdata->nbnds + 1 > scvdata->bndssize )
329  {
330  newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1);
331  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) );
332  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) );
333  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) );
334  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) );
335  scvdata->bndssize = newsize;
336  }
337  assert(scvdata->nbnds + 1 <= scvdata->bndssize);
338  assert(scvdata->bvars != NULL);
339 
340  /* move entries if needed */
341  for( i = scvdata->nbnds; i > pos; --i )
342  {
343  /* coverity[var_deref_op] */
344  scvdata->bvars[i] = scvdata->bvars[i-1];
345  scvdata->vals0[i] = scvdata->vals0[i-1];
346  scvdata->lbs1[i] = scvdata->lbs1[i-1];
347  scvdata->ubs1[i] = scvdata->ubs1[i-1];
348  }
349 
350  scvdata->bvars[pos] = indicator;
351  scvdata->vals0[pos] = val0;
352  scvdata->lbs1[pos] = lb1;
353  scvdata->ubs1[pos] = ub1;
354  ++scvdata->nbnds;
355 
356  return SCIP_OKAY;
357 }
358 
359 /** checks if a variable is semicontinuous and stores it data in the hashmap scvars
360  *
361  * A variable x is semicontinuous if its bounds depend on at least one binary variable called the indicator,
362  * and indicator == 0 => x == x^0 for some real constant x^0.
363  */
364 static
366  SCIP* scip, /**< SCIP data structure */
367  SCIP_VAR* var, /**< the variable to check */
368  SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
369  SCIP_Real constant, /**< value which should be equal to the constant */
370  SCIP_Bool* result /**< buffer to store whether var is semicontinuous */
371  )
372 {
373  SCIP_Real lb0;
374  SCIP_Real ub0;
375  SCIP_Real lb1;
376  SCIP_Real ub1;
377  SCIP_Real glb;
378  SCIP_Real gub;
379  SCIP_Bool exists;
380  int c;
381  int pos;
382  SCIP_VAR** vlbvars;
383  SCIP_VAR** vubvars;
384  SCIP_Real* vlbcoefs;
385  SCIP_Real* vubcoefs;
386  SCIP_Real* vlbconstants;
387  SCIP_Real* vubconstants;
388  int nvlbs;
389  int nvubs;
390  SCVARDATA* scvdata;
391  SCIP_VAR* bvar;
392 
393  assert(scip != NULL);
394  assert(var != NULL);
395  assert(scvars != NULL);
396  assert(result != NULL);
397 
398  scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
399  if( scvdata != NULL )
400  {
401  *result = TRUE;
402  return SCIP_OKAY;
403  }
404 
405  vlbvars = SCIPvarGetVlbVars(var);
406  vubvars = SCIPvarGetVubVars(var);
407  vlbcoefs = SCIPvarGetVlbCoefs(var);
408  vubcoefs = SCIPvarGetVubCoefs(var);
409  vlbconstants = SCIPvarGetVlbConstants(var);
410  vubconstants = SCIPvarGetVubConstants(var);
411  nvlbs = SCIPvarGetNVlbs(var);
412  nvubs = SCIPvarGetNVubs(var);
413  glb = SCIPvarGetLbGlobal(var);
414  gub = SCIPvarGetUbGlobal(var);
415 
416  pos = -1;
417 
418  *result = FALSE;
419 
420  /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1.
421  * Then check if there is an upper bound with this vlbvar and save ub0 and ub1.
422  * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0,
423  * save vlbvar and val0 to scvdata.
424  */
425  for( c = 0; c < nvlbs; ++c )
426  {
427  if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY )
428  continue;
429 
430  bvar = vlbvars[c];
431 
432  lb0 = MAX(vlbconstants[c], glb);
433  lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb);
434 
435  /* look for bvar in vubvars */
436  if( vubvars != NULL )
437  exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos);
438  else
439  exists = FALSE;
440 
441  if( exists )
442  {
443  /* save the upper bounds */
444  ub0 = MIN(vubconstants[pos], gub);
445  ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub);
446  }
447  else
448  {
449  /* if there is no upper bound with vubvar = bvar, use global var bounds */
450  ub0 = gub;
451  ub1 = gub;
452  }
453 
454  /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
455  if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
456  {
457  if( scvdata == NULL )
458  {
459  SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
460  }
461  SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
462  }
463  }
464 
465  /* look for vubvars that have not been processed yet */
466  assert(vubvars != NULL || nvubs == 0);
467  for( c = 0; c < nvubs; ++c )
468  {
469  /* coverity[var_deref_op] */
470  if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/
471  continue;
472 
473  bvar = vubvars[c]; /*lint !e613*/
474 
475  /* skip vars that are in vlbvars */
476  if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) )
477  continue;
478 
479  lb0 = glb;
480  lb1 = glb;
481  ub0 = MIN(vubconstants[c], gub);
482  ub1 = MIN(vubconstants[c] + vubcoefs[c], gub);
483 
484  /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
485  if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
486  {
487  if( scvdata == NULL )
488  {
489  SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
490  }
491 
492  SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
493  }
494  }
495 
496  if( scvdata != NULL )
497  {
498 #ifdef SCIP_DEBUG
499  SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub);
500  for( c = 0; c < scvdata->nbnds; ++c )
501  {
502  SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]);
503  }
504 #endif
505  SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) );
506  *result = TRUE;
507  }
508 
509  return SCIP_OKAY;
510 }
511 
512 /** checks if there are unfixed indicator variables modeling semicont. vars */
513 static
515  SCIP* scip, /**< SCIP data structure */
516  SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */
517  SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
518  SCIP_Bool* hasunfixedscindconss /**< pointer to store if there are unfixed indicator variables modeling semicont. vars */
519  )
520 {
521  SCIP_CONS** indicatorconss;
522  SCIP_VAR** consvars;
523  SCIP_Real* consvals;
524  int nconss;
525  int i;
526 
527  *hasunfixedscindconss = FALSE;
528  indicatorconss = SCIPconshdlrGetConss(conshdlr);
529  nconss = SCIPconshdlrGetNConss(conshdlr);
530  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
531  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
532 
533  for( i = 0; i < nconss; i++ )
534  {
535  SCIP_VAR *binvar;
536  SCIP_VAR* semicontinuousvar;
537  SCIP_CONS* lincons;
538  SCIP_Real rhs;
539  int nconsvars;
540  SCIP_Bool success;
541  int v;
542 
543  binvar = SCIPgetBinaryVarIndicator(indicatorconss[i]);
544 
545  /* check if indicator variable is unfixed */
546  if( SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5 )
547  {
548  lincons = SCIPgetLinearConsIndicator(indicatorconss[i]);
549  rhs = SCIPconsGetRhs(scip, lincons, &success);
550  SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) );
551 
552  /* check if constraint contains only two variables with finite rhs */
553  /* TODO: allow also indicators for lower bounds */
554  if( nconsvars == 2 && !SCIPisInfinity(scip, rhs) )
555  {
556  SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) );
557  SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) );
558 
559  for( v = 0; v < nconsvars ; v++ )
560  {
561  if( consvars[v] == SCIPgetSlackVarIndicator(indicatorconss[i]) ) /* note that we have exact two variables */
562  continue;
563 
564  semicontinuousvar = consvars[v];
565  SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, scvars, rhs, &success) );
566 
567  /* check if semicontinuous variable */
568  if( success )
569  {
570  *hasunfixedscindconss = TRUE;
571  break;
572  }
573  }
574  if( *hasunfixedscindconss )
575  break;
576  }
577  }
578  }
579  SCIPfreeBufferArray(scip, &consvals);
580  SCIPfreeBufferArray(scip, &consvars);
581  return SCIP_OKAY;
582 }
583 
584 /** creates and initializes hashmaps
585  *
586  * indicatormap: binary var -> indicator constraint
587  * varboundmap: binary var -> varbound constraint
588  *
589  * Currently exactly one constraint is assigned to a binary variable (per hashmap),
590  * but a binary variable can also control more than one constraint.
591  * TODO: Allow more than one corresponding indicator/varbound constraint per binary variable.
592  */
593 static
595  SCIP* scip, /**< SCIP data structure */
596  SCIP_CONSHDLR* indicatorconshdlr, /**< indicator constraint handler */
597  SCIP_CONSHDLR* varboundconshdlr, /**< varbound constraint handler */
598  SCIP_Bool usevarbounds, /**< should varbound constraints be considered? */
599  SCIP_HASHMAP** indicatormap, /**< hashmap to store indicator constraints of binary variables */
600  SCIP_HASHMAP** varboundmap /**< hashmap to store varbound constraints of binary variables */
601  )
602 {
603  SCIP_CONS** conss;
604  int nconss;
605  int i;
606 
607  assert(strcmp(SCIPconshdlrGetName(indicatorconshdlr), "indicator") == 0);
608  assert(strcmp(SCIPconshdlrGetName(varboundconshdlr), "varbound") == 0);
609 
610  /* indicator constraints */
611  nconss = SCIPconshdlrGetNConss(indicatorconshdlr);
612  conss = SCIPconshdlrGetConss(indicatorconshdlr);
613  SCIP_CALL( SCIPhashmapCreate(indicatormap, SCIPblkmem(scip), nconss) );
614  for( i = 0; i < nconss; i++ )
615  {
616  if( !SCIPhashmapExists(*indicatormap, SCIPgetBinaryVarIndicator(conss[i])) )
617  {
618  SCIP_CALL( SCIPhashmapInsert(*indicatormap, SCIPgetBinaryVarIndicator(conss[i]), conss[i]) );
619  }
620  }
621 
622  /* varbound constraints */
623  if( usevarbounds )
624  {
625  nconss = SCIPconshdlrGetNConss(varboundconshdlr);
626  conss = SCIPconshdlrGetConss(varboundconshdlr);
627  SCIP_CALL( SCIPhashmapCreate(varboundmap, SCIPblkmem(scip), nconss) );
628  for( i = 0; i < nconss; i++ )
629  {
630  if( !SCIPhashmapExists(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i])) )
631  {
632  SCIP_CALL( SCIPhashmapInsert(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i]), conss[i]) );
633  }
634  }
635  }
636  return SCIP_OKAY;
637 }
638 
639 #define MIN_RAND 1e-06
640 #define MAX_RAND 1e-05
641 
642 /** calculate score and preferred rounding direction for the candidate variable */
643 static
645  SCIP* scip, /**< SCIP data structure */
646  SCIP_DIVESET* diveset, /**< diving settings */
647  SCIP_VAR* cand, /**< candidate variable */
648  SCIP_Real candsfrac, /**< fractional part of solution value of candidate variable */
649  SCIP_Bool* roundup, /**< pointer to store whether the preferred rounding direction is upwards */
650  SCIP_Real* score /**< pointer for diving score value */
651  )
652 {
653  SCIP_RANDNUMGEN* randnumgen;
654  SCIP_Real obj;
655 
656  randnumgen = SCIPdivesetGetRandnumgen(diveset);
657  assert(randnumgen != NULL);
658 
659  obj = SCIPvarGetObj(cand);
660 
661  /* dive towards the pseudosolution, at the same time approximate the contribution to
662  * a potential Farkas-proof (infeasibility proof) by y^TA_i = c_i.
663  */
664  if( SCIPisNegative(scip, obj) )
665  *roundup = TRUE;
666  else if( SCIPisPositive(scip, obj) )
667  *roundup = FALSE;
668  else
669  {
670  if( SCIPisEQ(scip, candsfrac, 0.5) )
671  *roundup = !SCIPrandomGetInt(randnumgen, 0, 1);
672  else
673  *roundup = (candsfrac > 0.5);
674  }
675 
676  /* larger score is better */
677  *score = REALABS(obj) + SCIPrandomGetReal(randnumgen, MIN_RAND, MAX_RAND);
678 
679  /* prefer decisions on binary variables */
680  if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
681  *score = -1.0 / *score;
682 }
683 
684 
685 /*
686  * Callback methods
687  */
688 
689 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
690 static
691 SCIP_DECL_HEURCOPY(heurCopyIndicatordiving)
692 { /*lint --e{715}*/
693  assert(scip != NULL);
694  assert(heur != NULL);
695  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
696 
697  /* call inclusion method of primal heuristic */
699 
700  return SCIP_OKAY;
701 }
702 
703 
704 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
705 static
706 SCIP_DECL_HEURFREE(heurFreeIndicatordiving)
707 { /*lint --e{715}*/
708  SCIP_HEURDATA* heurdata;
710  assert(heur != NULL);
711  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
712  assert(scip != NULL);
713 
714  /* free heuristic data */
715  heurdata = SCIPheurGetData(heur);
716  assert(heurdata != NULL);
717 
718  SCIPfreeBlockMemory(scip, &heurdata);
719  SCIPheurSetData(heur, NULL);
720 
721  return SCIP_OKAY;
722 }
723 
724 
725 /** initialization method of primal heuristic (called after problem was transformed) */
726 static
727 SCIP_DECL_HEURINIT(heurInitIndicatordiving)
728 { /*lint --e{715}*/
729  SCIP_HEURDATA* heurdata;
731  assert(heur != NULL);
732  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
733  assert(scip != NULL);
734 
735  /* get heuristic data */
736  heurdata = SCIPheurGetData(heur);
737  assert(heurdata != NULL);
738 
739  /* create working data */
740  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
741  SCIP_CALL( SCIPhashmapCreate( &heurdata->scvars, SCIPblkmem( scip ), SCIPgetNVars(scip) ));
742 
743  heurdata->indicatorconshdlr = SCIPfindConshdlr(scip, "indicator");
744  heurdata->varboundconshdlr = SCIPfindConshdlr(scip, "varbound");
745 
746  return SCIP_OKAY;
747 }
748 
749 
750 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
751 static
752 SCIP_DECL_HEUREXIT(heurExitIndicatordiving)
753 { /*lint --e{715}*/
754  SCIP_HEURDATA* heurdata;
756  assert(heur != NULL);
757  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
758  assert(scip != NULL);
759 
760  /* get heuristic data */
761  heurdata = SCIPheurGetData(heur);
762  assert(heurdata != NULL);
763 
764  /* free working data */
765  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
766  SCIP_CALL( releaseSCHashmap(scip, heurdata->scvars) );
767 
768  return SCIP_OKAY;
769 }
770 
771 
772 /** execution method of primal heuristic */
773 static
774 SCIP_DECL_HEUREXEC(heurExecIndicatordiving)
775 { /*lint --e{715}*/
776  SCIP_HEURDATA* heurdata;
777  SCIP_DIVESET* diveset;
778  SCIP_Bool hasunfixedscindconss; /* are there unfixed indicator variables modeling a semicont. variable? */
779 
780  heurdata = SCIPheurGetData(heur);
781  assert(heurdata != NULL);
782 
783  assert(SCIPheurGetNDivesets(heur) > 0);
784  assert(SCIPheurGetDivesets(heur) != NULL);
785  diveset = SCIPheurGetDivesets(heur)[0];
786  assert(diveset != NULL);
787 
788  assert(result != NULL);
789  *result = SCIP_DIDNOTRUN;
790 
791  /* check if there are unfixed indicator variables modeling semicont. vars */
792  SCIP_CALL( hasUnfixedSCIndicator(scip, heurdata->indicatorconshdlr, heurdata->scvars, &hasunfixedscindconss) );
793 
794  /* skip heuristic if problem doesn't contain unfixed indicator variables,
795  * or if there are no varbound constraints which should be considered
796  */
797  if( !hasunfixedscindconss && (!heurdata->runwithoutscinds || !heurdata->usevarbounds || SCIPconshdlrGetNConss(heurdata->varboundconshdlr) == 0) )
798  return SCIP_OKAY;
799 
800  SCIPdebugMsg(scip, "call heurExecIndicatordiving at depth %d \n", SCIPgetDepth(scip));
801 
802  /* create and initialize hashmaps */
803  SCIP_CALL( createMaps(scip, heurdata->indicatorconshdlr, heurdata->varboundconshdlr, heurdata->usevarbounds, &heurdata->indicatormap, &heurdata->varboundmap) );
804 
805  /* (re-)set flags */
806  heurdata->gotoindconss = FALSE;
807  heurdata->containsviolindconss = FALSE;
808  heurdata->newnode = TRUE;
809  heurdata->probingdepth = -1;
810 
811  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
812 
813  /* free hashmaps since constraints can get removed/modified till the next call */
814  if( heurdata->usevarbounds )
815  SCIPhashmapFree(&heurdata->varboundmap);
816  SCIPhashmapFree(&heurdata->indicatormap);
817 
818  SCIPdebugMsg(scip, "leave heurExecIndicatordiving\n");
819 
820  return SCIP_OKAY;
821 }
822 
823 
824 /** calculate score and preferred rounding direction for the candidate variable */
825 static
826 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving)
827 { /*lint --e{715}*/
828  SCIP_HEUR* heur;
829  SCIP_HEURDATA* heurdata;
830  SCIP_RANDNUMGEN* randnumgen;
831  SCIP_VAR** consvars;
832  SCIP_CONS* indicatorcons;
833  SCIP_CONS* varboundcons;
834  SCIP_CONS* lincons;
835  SCIP_VAR* nonoptionvar; /* second variable in linear cons which is not the option variable (indicator: slackvar, varbound: binary var) */
836  SCIP_VAR* semicontinuousvar;
837  SCIP_Real lpsolsemicontinuous;
838  SCVARDATA* scdata;
839  SCIP_Real* consvals;
840  SCIP_Real side;
841  int nconsvars;
842  int idxbvars; /* index of bounding variable in hashmap scdata */
843  SCIP_Bool isindicatorvar;
844  SCIP_Bool isvbdvar; /* variable bounding variable in varbound */
845  SCIP_Bool issemicont; /* indicates whether variable has (maybe) required semicont. properties */
846  SCIP_Bool fixconstant; /* should we fix the semicontinuous variable to its constant? */
847  SCIP_Bool success;
848  int v;
849  int b;
850 
851  varboundcons = NULL;
852  semicontinuousvar = NULL;
853  scdata = NULL;
854  lpsolsemicontinuous = 0.0;
855  idxbvars = -1;
856  isvbdvar = FALSE;
857  issemicont = TRUE;
858 
859  heur = SCIPdivesetGetHeur(diveset);
860  assert(heur != NULL);
861  heurdata = SCIPheurGetData(heur);
862  assert(heurdata != NULL);
863 
864  randnumgen = SCIPdivesetGetRandnumgen(diveset);
865  assert(randnumgen != NULL);
866 
867  /* check if we are at a new probing node; since diving heuristics backtrack at most one probing node, we are at a new
868  * node iff the probing depth increased */
869  if( heurdata->probingdepth < SCIPgetProbingDepth(scip) )
870  heurdata->newnode = TRUE;
871  else
872  {
873  assert(heurdata->probingdepth == SCIPgetProbingDepth(scip));
874  heurdata->newnode = FALSE;
875  }
876  heurdata->probingdepth = SCIPgetProbingDepth(scip);
877 
878  /* skip if current candidate can not be determined by the indicator constraint handler and violated indicator
879  * constraints still exists */
880  if( !(SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5)
881  && heurdata->gotoindconss )
882  {
883  *score = SCIP_REAL_MIN;
884  *roundup = FALSE;
885  return SCIP_OKAY;
886  }
887  else
888  heurdata->gotoindconss = FALSE;
889 
890  /* check if candidate variable is indicator variable */
891  checkAndGetIndicator(scip, cand, heurdata->indicatormap, &indicatorcons, &isindicatorvar,
892  &heurdata->containsviolindconss, heurdata->newnode, heurdata->sol, heurdata->indicatorconshdlr);
893 
894  /* skip candidate in next calls since we have violated indicator constraints but current candidate is not determined
895  * by the indicator constraint handler */
896  if( heurdata->containsviolindconss &&
897  !((SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5) && isindicatorvar) )
898  {
899  heurdata->gotoindconss = TRUE;
900  *score = SCIP_REAL_MIN;
901  *roundup = FALSE;
902  return SCIP_OKAY;
903  }
904 
905  /* check if candidate variable is bounding variable */
906  if( heurdata->usevarbounds && !isindicatorvar )
907  {
908  checkAndGetVarbound(scip, cand, heurdata->varboundmap, &varboundcons, &isvbdvar);
909  }
910 
911  /* Return
912  * - if candidate variable is neither a indicator variable nor a variable bounding variable
913  * - or if candidate variable is not an indicator variable but there will be indicator variables as candidates
914  * - or if candidate variable is not an indicator variable and varbound constraints are not considered.
915  */
916  if( !isindicatorvar && (!isvbdvar || heurdata->containsviolindconss || !heurdata->usevarbounds) )
917  {
918  *score = SCIP_REAL_MIN;
919  *roundup = FALSE;
920 
921  if( !heurdata->containsviolindconss && !isvbdvar )
922  {
923  getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
924  *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
925  }
926  return SCIP_OKAY;
927  }
928 
929  SCIPdebugMsg(scip, "cand: %s, candsol: %.2f, candobjcoeff: %f\n", SCIPvarGetName(cand), candsol, SCIPvarGetObj(cand));
930 
931  if( isindicatorvar ) /* prefer indicator constraint */
932  {
933  SCIP_Real rhs;
934 
935  lincons = SCIPgetLinearConsIndicator(indicatorcons);
936  nonoptionvar = SCIPgetSlackVarIndicator(indicatorcons);
937  rhs = SCIPconsGetRhs(scip, lincons, &success);
938  issemicont = SCIPisInfinity(scip, -SCIPconsGetLhs(scip, lincons, &success)); /* TODO: allow also indicators for lower bounds */
939  side = rhs;
940  }
941  else
942  {
943  SCIP_Real rhs;
944  SCIP_Real lhs;
945 
946  assert(isvbdvar);
947 
948  lincons = varboundcons;
949  nonoptionvar = SCIPgetVbdvarVarbound(scip, varboundcons);
950  rhs = SCIPconsGetRhs(scip, lincons, &success);
951  lhs = SCIPconsGetLhs(scip, lincons, &success);
952  side = SCIPisInfinity(scip, rhs) ? lhs : rhs;
953  assert(!SCIPisInfinity(scip, side));
954  }
955  SCIPdebugPrintCons(scip, lincons, NULL);
956 
957  SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) );
958 
959  if( nconsvars != 2 || !issemicont )
960  {
961  getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
962  *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
963  return SCIP_OKAY;
964  }
965 
966  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) );
967  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
968  SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) );
969  SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) );
970 
971  issemicont = FALSE;
972  for( v = 0; v < nconsvars ; v++ )
973  {
974  if( consvars[v] == nonoptionvar ) /* note that we have exact two variables */
975  continue;
976 
977  semicontinuousvar = consvars[v];
978  lpsolsemicontinuous = SCIPvarGetLPSol( semicontinuousvar );
979  SCIPdebugMsg(scip, "%s lp sol %f %f\n", SCIPvarGetName( semicontinuousvar ), lpsolsemicontinuous,
980  consvals[v] );
981  SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, heurdata->scvars, side, &success) );
982 
983  /* only allow semicontinuous variables */
984  if( success )
985  {
986  assert(SCIPhashmapExists(heurdata->scvars, (void*) semicontinuousvar));
987  scdata = (SCVARDATA*) SCIPhashmapGetImage(heurdata->scvars, (void*) semicontinuousvar);
988  assert(scdata != NULL);
989 
990  for( b = 0; b < scdata->nbnds; b++ )
991  {
992  if( (scdata->bvars[b] == cand || (SCIPvarIsNegated(cand) && scdata->bvars[0] == SCIPvarGetNegationVar(cand)))
993  && SCIPisEQ(scip, side, scdata->vals0[b]) )
994  {
995  /* TODO: handle also more general variables;
996  * currently we handle only variables with domain vals0 < lb1 <= ub1 */
997  if( SCIPisGE(scip, lpsolsemicontinuous, scdata->vals0[b]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[b]) )
998  {
999  issemicont = TRUE;
1000  idxbvars = b;
1001  break;
1002  }
1003  }
1004  }
1005  }
1006  }
1007 
1008  /* only continue if semicontinuous variable */
1009  if( !issemicont )
1010  {
1011  getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
1012  *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
1013  SCIPfreeBufferArray(scip, &consvals);
1014  SCIPfreeBufferArray(scip, &consvars);
1015  return SCIP_OKAY;
1016  }
1017  assert(idxbvars >= 0);
1018  assert(scdata != NULL);
1019 
1020  /* Case: Variable is in range [lb1,ub1] */
1021  if( SCIPisGE(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[idxbvars]))
1022  {
1023  *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0);
1024  fixconstant = FALSE;
1025  }
1026  /* Case: Variable is equal to constant */
1027  else if( SCIPisEQ(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) )
1028  {
1029  *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0);
1030  fixconstant = TRUE;
1031  }
1032  /* Case: Variable is between constant and lb1 */
1033  else
1034  {
1035  SCIP_Real shiftedlpsolsemicontinuous = lpsolsemicontinuous;
1036  SCIP_Real shiftedlbs1 = scdata->lbs1[idxbvars];
1037 
1038  assert(SCIPisGT(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) && SCIPisLT(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]));
1039 
1040  /* handle case if constant of semicont. var is not zero -> shift values */
1041  if( !SCIPisZero(scip, scdata->vals0[idxbvars]) )
1042  {
1043  shiftedlpsolsemicontinuous -= scdata->vals0[idxbvars];
1044  shiftedlbs1 -= scdata->vals0[idxbvars];
1045  }
1046 
1047  *score = 100 * (shiftedlbs1 - shiftedlpsolsemicontinuous) / shiftedlbs1;
1048  assert(*score>0);
1049 
1050  switch( (INDICATORDIVINGROUNDINGMODE)heurdata->roundingmode )
1051  {
1052  case ROUNDING_CONSERVATIVE:
1053  fixconstant = (*score > (1 - heurdata->roundingfrac) * 100);
1054  break;
1055  case ROUNDING_AGGRESSIVE:
1056  fixconstant = (*score <= (1 - heurdata->roundingfrac) * 100);
1057  break;
1058  default:
1059  return SCIP_INVALIDDATA;
1060  }
1061 
1062  switch( heurdata->semicontscoremode )
1063  {
1064  case 0:
1065  break;
1066  case 1:
1067  if( shiftedlpsolsemicontinuous < shiftedlbs1 * heurdata->roundingfrac )
1068  *score = 100 * (shiftedlpsolsemicontinuous / (heurdata->roundingfrac * shiftedlbs1));
1069  else
1070  *score = 100 * (-shiftedlpsolsemicontinuous / ((1 - heurdata->roundingfrac) * shiftedlbs1) + (1 / (1 - heurdata->roundingfrac)) );
1071  break;
1072  case 2:
1073  *score = 100 - *score;
1074  break;
1075  default:
1076  return SCIP_INVALIDDATA;
1077  }
1078  assert(*score>0);
1079  }
1080 
1081  /* Set roundup depending on whether we have an indicator constraint or a varbound constraint:
1082  * - indicator constraint: roundup == fix to constant
1083  * - varbound constraint: roundup == push to range
1084  */
1085  *roundup = isindicatorvar ? fixconstant : !fixconstant; /*lint !e644*/
1086 
1087  /* free memory */
1088  SCIPfreeBufferArray(scip, &consvals);
1089  SCIPfreeBufferArray(scip, &consvars);
1090 
1091  return SCIP_OKAY;
1092 }
1093 
1094 
1095 /** callback to check preconditions for diving, e.g., if an incumbent solution is available */
1096 static
1097 SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving)
1098 {
1099  /* Skip if problem doesn't contain indicator constraints.
1100  * If varbound constraints should be considered, skip only if there are also no varbound constraints.
1101  */
1102  *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "indicator")) == 0;
1103 
1104  if( !*available )
1105  {
1106  SCIP_HEUR* heur;
1107  SCIP_HEURDATA* heurdata;
1108 
1109  heur = SCIPdivesetGetHeur(diveset);
1110  assert(heur != NULL);
1111  heurdata = SCIPheurGetData(heur);
1112  assert(heurdata != NULL);
1113 
1114  if( heurdata->runwithoutscinds && heurdata->usevarbounds )
1115  {
1116  *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "varbound")) == 0;
1117  }
1118  }
1119 
1120  return SCIP_OKAY;
1121 }
1122 
1123 /*
1124  * heuristic specific interface methods
1125  */
1126 
1127 /** creates the indicatordiving heuristic and includes it in SCIP */
1129  SCIP* scip /**< SCIP data structure */
1130  )
1132  SCIP_HEURDATA* heurdata;
1133  SCIP_HEUR* heur;
1134 
1135  /* create indicatordiving primal heuristic data */
1136  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1137 
1138  heur = NULL;
1139 
1140  /* include primal heuristic */
1141  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1143  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIndicatordiving, heurdata) );
1144 
1145  assert(heur != NULL);
1146 
1147  /* set non fundamental callbacks via setter functions */
1148  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIndicatordiving) );
1149  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIndicatordiving) );
1150  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIndicatordiving) );
1151  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIndicatordiving) );
1152 
1153  /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
1157  DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreIndicatordiving, divesetAvailableIndicatordiving) );
1158 
1159  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundingfrac",
1160  "in violation case all fractional below this value are fixed to constant",
1161  &heurdata->roundingfrac, FALSE, DEFAULT_ROUNDINGFRAC, 0.0, 1.0, NULL, NULL) );
1162 
1163  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/roundingmode",
1164  "decides which roundingmode is selected (0: conservative, 1: aggressive)",
1165  &heurdata->roundingmode, FALSE, DEFAULT_ROUNDINGMODE, 0, 1, NULL, NULL) );
1166 
1167  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/semicontscoremode",
1168  "which values of semi-continuous variables should get a high score? (0: low, 1: middle, 2: high)",
1169  &heurdata->semicontscoremode, FALSE, DEFAULT_SEMICONTSCOREMODE, 0, 2, NULL, NULL) );
1170 
1171  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarbounds",
1172  "should varbound constraints be considered?",
1173  &heurdata->usevarbounds, FALSE, DEFAULT_USEVARBOUNDS, NULL, NULL) );
1174 
1175  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/runwithoutscinds",
1176  "should heur run if there are no indicator constraints modeling semicont. vars?",
1177  &heurdata->runwithoutscinds, FALSE, DEFAULT_RUNWITHOUTSCINDS, NULL, NULL) );
1178 
1179  return SCIP_OKAY;
1180 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define DEFAULT_RUNWITHOUTSCINDS
SCIP_Bool SCIPisViolatedIndicator(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:112
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18293
#define NULL
Definition: def.h:267
public methods for SCIP parameter handling
Constraint handler for variable bound constraints .
#define HEUR_NAME
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18271
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_PRIORITY
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:48
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1651
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define DEFAULT_ROUNDINGFRAC
enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE
constraint handler for indicator constraints
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4595
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
IndicatorDivingRoundingMode
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_RETCODE varIsSemicontinuous(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Real constant, SCIP_Bool *result)
methods commonly used by primal heuristics
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18313
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXRELDEPTH
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
public methods for problem variables
#define DEFAULT_MAXDIVEAVGQUOT
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
SCIP_VAR ** bvars
#define HEUR_TIMING
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18283
SCIP_Real * lbs1
#define DEFAULT_MAXDIVEUBQUOT
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool ispublic, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)))
Definition: scip_heur.c:318
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
static void checkAndGetVarbound(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isvarbound)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17905
#define DEFAULT_RANDSEED
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
static SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving)
public methods for numerical tolerances
static SCIP_DECL_HEUREXIT(heurExitIndicatordiving)
SCIP_Real * ubs1
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
public methods for the branch-and-bound tree
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:416
SCIP_VAR * SCIPgetSlackVarIndicator(SCIP_CONS *cons)
#define HEUR_DISPCHAR
static SCIP_DECL_HEUREXEC(heurExecIndicatordiving)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving)
public methods for managing constraints
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
#define DIVESET_ISPUBLIC
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * vals0
#define DEFAULT_ROUNDINGMODE
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18345
SCIP_SOL * sol
Definition: struct_heur.h:71
static SCIP_DECL_HEURFREE(heurFreeIndicatordiving)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
static SCIP_DECL_HEURCOPY(heurCopyIndicatordiving)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
static SCIP_Bool isViolatedAndNotFixed(SCIP *scip, SCIP_SOL *sol, SCIP_CONS *cons)
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
#define REALABS(x)
Definition: def.h:197
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18453
#define DEFAULT_MAXLPITERQUOT
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18303
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18335
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1661
#define DEFAULT_SEMICONTSCOREMODE
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
public methods for primal heuristic plugins and divesets
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4638
public methods for constraint handler plugins and constraints
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define MIN_RAND
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:91
static SCIP_DECL_HEURINIT(heurInitIndicatordiving)
static SCIP_RETCODE addSCVarIndicator(SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:720
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8236
#define MIN(x, y)
Definition: def.h:243
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
#define HEUR_USESSUBSCIP
#define HEUR_DESC
static SCIP_RETCODE releaseSCHashmap(SCIP *scip, SCIP_HASHMAP *hashmap)
#define DEFAULT_USEVARBOUNDS
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define MAX_RAND
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4672
#define DIVESET_DIVETYPES
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
#define SCIP_REAL_MIN
Definition: def.h:175
static SCIP_RETCODE createMaps(SCIP *scip, SCIP_CONSHDLR *indicatorconshdlr, SCIP_CONSHDLR *varboundconshdlr, SCIP_Bool usevarbounds, SCIP_HASHMAP **indicatormap, SCIP_HASHMAP **varboundmap)
SCIP_VAR ** b
Definition: circlepacking.c:65
#define DEFAULT_MAXLPITEROFS
#define MAX(x, y)
Definition: def.h:239
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeHeurIndicatordiving(SCIP *scip)
public methods for solutions
public methods for the probing mode
static void getScoreOfFarkasDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_VAR *cand, SCIP_Real candsfrac, SCIP_Bool *roundup, SCIP_Real *score)
public methods for message output
static SCIP_RETCODE hasUnfixedSCIndicator(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HASHMAP *scvars, SCIP_Bool *hasunfixedscindconss)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
#define SCIP_Real
Definition: def.h:173
#define HEUR_FREQ
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
Definition: misc_linear.c:179
public methods for message handling
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18325
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_MINRELDEPTH
#define DEFAULT_LPSOLVEFREQ
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
public methods for primal heuristics
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
LP diving heuristic that fixes indicator variables controlling semicontinuous variables.
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
SCIP_CONS * SCIPgetLinearConsIndicator(SCIP_CONS *cons)
public methods for global and local (sub)problems
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
static void checkAndGetIndicator(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isindicator, SCIP_Bool *containsviolindconss, SCIP_Bool newnode, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr)
#define HEUR_FREQOFS
#define DEFAULT_BACKTRACK
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17575
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184