Scippy

SCIP

Solving Constraint Integer Programs

heur_vbounds.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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_vbounds.c
17  * @brief LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood
18  * @author Timo Berthold
19  * @author Stefan Heinz
20  * @author Jens Schulz
21  * @author Gerald Gamrath
22  *
23  * @todo allow smaller fixing rate for probing LP?
24  * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)?
25  *
26  * More details about the heuristic can be found in@n
27  * Structure-Based Primal Heuristics for Mixed Integer Programming@n
28  * Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler@n
29  * Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53@n
30  * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>.
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <assert.h>
36 #include <string.h>
37 
38 #include "scip/scip.h"
39 #include "scip/scipdefplugins.h"
40 #include "scip/heur_vbounds.h"
41 #include "scip/heur_locks.h"
42 
43 #ifdef SCIP_STATISTIC
44 #include "scip/clock.h"
45 #endif
46 
47 #define VBOUNDVARIANT_NOOBJ 0x001u
48 #define VBOUNDVARIANT_BESTBOUND 0x002u
49 #define VBOUNDVARIANT_WORSTBOUND 0x004u
50 
51 #define HEUR_NAME "vbounds"
52 #define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
53 #define HEUR_DISPCHAR 'V'
54 #define HEUR_PRIORITY 2500
55 #define HEUR_FREQ 0
56 #define HEUR_FREQOFS 0
57 #define HEUR_MAXDEPTH -1
58 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
59 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
60 
61 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
62 #define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */
63 #define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimuskipobjm percentage of variables that have to be fixed within sub-SCIP
64  * (integer and continuous) */
65 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which vbounds heuristic should at least improve the
66  * incumbent */
67 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
68 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
69 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
70 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
71 #define DEFAULT_MAXBACKTRACKS 10 /**< maximum number of backtracks during the fixing process */
72 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied to
73  * constraints of the subscip? */
74 #define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if
75  * the fixing rate was not reached?
76  */
77 
78 /** which variants of the vbounds heuristic that try to stay feasible should be called? */
79 #define DEFAULT_FEASVARIANT (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
80 
81 /** which tightening variants of the vbounds heuristic should be called? */
82 #define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
83 
84 
85 /*
86  * Data structures
87  */
88 
89 /** primal heuristic data */
90 struct SCIP_HeurData
91 {
92  SCIP_VAR** vbvars; /**< topological sorted variables with respect to the variable bounds */
93  SCIP_BOUNDTYPE* vbbounds; /**< topological sorted variables with respect to the variable bounds */
94  int nvbvars; /**< number of variables in variable lower bound array */
95  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
96  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
97  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
98  SCIP_Longint usednodes; /**< nodes already used by vbounds heuristic in earlier calls */
99  SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */
100  SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP
101  * (integer and continuous) */
102  SCIP_Real minimprove; /**< factor by which vbounds heuristic should at least improve the incumbent */
103  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
104  SCIP_Real cutoffbound;
105  int maxproprounds; /**< maximum number of propagation rounds during probing */
106  int maxbacktracks; /**< maximum number of backtracks during the fixing process */
107  int feasvariant; /**< which variants of the vbounds heuristic that try to stay feasible
108  * should be called? */
109  int tightenvariant; /**< which tightening variants of the vbounds heuristic should be called? */
110  SCIP_Bool initialized; /**< is the candidate list initialized? */
111  SCIP_Bool applicable; /**< is the heuristic applicable? */
112  SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
113  * subproblem? */
114  SCIP_Bool uselockfixings; /**< should more variables be fixed based on variable locks if
115  * the fixing rate was not reached?
116  */
117 
118 
119 };
120 
121 /**@name Heuristic defines
122  *
123  * @{
124  *
125  * The heuristic works on indices representing a bound of a variable. This index will be called bound index in the
126  * following. For a given active variable with problem index i (note that active variables have problem indices
127  * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
128  * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
129  * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
130  * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
131  */
132 #define getLbIndex(idx) (2*(idx))
133 #define getUbIndex(idx) (2*(idx)+1)
134 #define getVarIndex(idx) ((idx)/2)
135 #define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
136 #define isIndexLowerbound(idx) ((idx) % 2 == 0)
137 #define getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)
140 /*
141  * Local methods
142  */
143 
144 /** reset heuristic data structure */
145 static
146 void heurdataReset(
147  SCIP_HEURDATA* heurdata /**< structure containing heurdata */
148  )
149 {
150  heurdata->vbvars = NULL;
151  heurdata->vbbounds = NULL;
152  heurdata->nvbvars = 0;
153  heurdata->initialized = FALSE;
154  heurdata->applicable = FALSE;
155 }
156 
157 
158 /** performs depth-first-search in the implicitly given directed graph from the given start index */
159 static
161  SCIP* scip, /**< SCIP data structure */
162  int startnode, /**< node to start the depth-first-search */
163  SCIP_Shortbool* visited, /**< array to store for each node, whether it was already visited */
164  int* dfsstack, /**< array of size number of nodes to store the stack;
165  * only needed for performance reasons */
166  int* stacknextedge, /**< array of size number of nodes to store the number of adjacent nodes
167  * already visited for each node on the stack; only needed for
168  * performance reasons */
169  int* stacknextcliquevar, /**< array of size number of nodes to store the number of variables
170  * already evaluated for the clique currently being evaluated */
171  int* cliqueexit, /**< exit node when entering a clique */
172  int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse
173  * dfs order */
174  int* ndfsnodes /**< pointer to store number of nodes that can be reached starting at
175  * startnode */
176  )
177 {
178  SCIP_VAR** vars;
179  SCIP_VAR* startvar;
180  SCIP_VAR** vbvars;
181  SCIP_Real* coefs;
182  SCIP_Bool lower;
183  SCIP_Bool found;
184  int maxstacksize;
185  int stacksize;
186  int curridx;
187  int idx;
188  int nvbvars;
189  int i;
190 
191  assert(startnode >= 0);
192  assert(startnode < 2 * SCIPgetNVars(scip));
193  assert(visited != NULL);
194  assert(visited[startnode] == FALSE);
195  assert(dfsstack != NULL);
196  assert(dfsnodes != NULL);
197  assert(ndfsnodes != NULL);
198 
199  vars = SCIPgetVars(scip);
200 
201  /* put start node on the stack */
202  dfsstack[0] = startnode;
203  stacknextcliquevar[0] = 0;
204  stacknextedge[0] = 0;
205  maxstacksize = 1;
206  stacksize = 1;
207  idx = -1;
208 
209  /* we run until no more bounds indices are on the stack */
210  while( stacksize > 0 )
211  {
212  /* get next node from stack */
213  curridx = dfsstack[stacksize - 1];
214 
215  /* mark current node as visited */
216  assert(visited[curridx] == (stacknextedge[stacksize - 1] != 0));
217  visited[curridx] = TRUE;
218  found = FALSE;
219 
220  startvar = vars[getVarIndex(curridx)];
221  lower = isIndexLowerbound(curridx);
222 
223  if( stacknextedge[stacksize - 1] >= 0 )
224  {
225  /* go over edges corresponding to varbounds */
226  if( lower )
227  {
228  vbvars = SCIPvarGetVlbVars(startvar);
229  coefs = SCIPvarGetVlbCoefs(startvar);
230  nvbvars = SCIPvarGetNVlbs(startvar);
231  }
232  else
233  {
234  vbvars = SCIPvarGetVubVars(startvar);
235  coefs = SCIPvarGetVubCoefs(startvar);
236  nvbvars = SCIPvarGetNVubs(startvar);
237  }
238 
239  /* iterate over all vbounds for the given bound */
240  for( i = stacknextedge[stacksize - 1]; i < nvbvars; ++i )
241  {
242  if( !SCIPvarIsActive(vbvars[i]) )
243  continue;
244 
245  idx = (SCIPisPositive(scip, coefs[i]) == lower) ? getLbIndex(SCIPvarGetProbindex(vbvars[i])) : getUbIndex(SCIPvarGetProbindex(vbvars[i]));
246  assert(idx >= 0);
247 
248  /* break when the first unvisited node is reached */
249  if( !visited[idx] )
250  break;
251  }
252 
253  /* we stopped because we found an unhandled node and not because we reached the end of the list */
254  if( i < nvbvars )
255  {
256  assert(!visited[idx]);
257 
258  /* put the adjacent node onto the stack */
259  dfsstack[stacksize] = idx;
260  stacknextedge[stacksize] = 0;
261  stacknextcliquevar[stacksize] = 0;
262  stacknextedge[stacksize - 1] = i + 1;
263  stacksize++;
264  assert(stacksize <= 2* SCIPgetNVars(scip));
265 
266  /* restart while loop, get next index from stack */
267  continue;
268  }
269  }
270 
271  stacknextedge[stacksize - 1] = -1;
272 
273  /* treat cliques */
274  if( SCIPvarIsBinary(startvar) )
275  {
276  SCIP_CLIQUE** cliques = SCIPvarGetCliques(startvar, !lower);
277  int ncliques = SCIPvarGetNCliques(startvar, !lower);
278  int j;
279 
280  /* iterate over all not yet handled cliques and search for an unvisited node */
281  for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
282  {
283  SCIP_VAR** cliquevars;
284  SCIP_Bool* cliquevals;
285  int ncliquevars;
286 
287  /* the first time we evaluate this clique for the current node */
288  if( stacknextcliquevar[stacksize - 1] == 0 )
289  {
290  if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] > 0 )
291  {
292  if( !visited[cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1] &&
293  cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1 != curridx )
294  {
295  stacknextedge[stacksize - 1] = -j - 2;
296  stacknextcliquevar[stacksize - 1] = 0;
297  idx = cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1;
298  cliqueexit[SCIPcliqueGetIndex(cliques[j])] = -1;
299  found = TRUE;
300  }
301  else
302  continue;
303  }
304  else if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] == 0 )
305  {
306  cliqueexit[SCIPcliqueGetIndex(cliques[j])] = getOtherBoundIndex(curridx) + 1;
307  }
308  else
309  continue;
310  }
311  if( !found )
312  {
313  cliquevars = SCIPcliqueGetVars(cliques[j]);
314  cliquevals = SCIPcliqueGetValues(cliques[j]);
315  ncliquevars = SCIPcliqueGetNVars(cliques[j]);
316 
317  for( i = 0; i < ncliquevars; ++i )
318  {
319  if( cliquevars[i] == startvar )
320  continue;
321 
322  if( SCIPvarGetIndex(cliquevars[i]) < 0 )
323  continue;
324 
325  if( cliquevals[i] )
326  idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i]));
327  else
328  idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i]));
329 
330  assert(idx >= 0 && idx < 2 * SCIPgetNVars(scip));
331 
332  /* break when the first unvisited node is reached */
333  if( idx >= 0 && !visited[idx] )
334  {
335  if( i < ncliquevars - 1 )
336  {
337  stacknextedge[stacksize - 1] = -j - 1;
338  stacknextcliquevar[stacksize - 1] = i + 1;
339  }
340  else
341  {
342  stacknextedge[stacksize - 1] = -j - 2;
343  stacknextcliquevar[stacksize - 1] = 0;
344  }
345  found = TRUE;
346  break;
347  }
348  }
349  }
350  if( found )
351  {
352  assert(!visited[idx]);
353 
354  /* put the adjacent node onto the stack */
355  dfsstack[stacksize] = idx;
356  stacknextedge[stacksize] = 0;
357  stacknextcliquevar[stacksize] = 0;
358  stacksize++;
359  assert(stacksize <= 2* SCIPgetNVars(scip));
360 
361  break;
362  }
363  }
364  /* restart while loop, get next index from stack */
365  if( found )
366  continue;
367  }
368 
369  maxstacksize = MAX(maxstacksize, stacksize);
370 
371  /* the current node was completely handled, remove it from the stack */
372  stacksize--;
373 
374  if( (maxstacksize > 1) && SCIPvarGetType(startvar) != SCIP_VARTYPE_CONTINUOUS )
375  {
376  /* store node in the sorted nodes array */
377  dfsnodes[(*ndfsnodes)] = curridx;
378  (*ndfsnodes)++;
379  }
380  else
381  visited[curridx] = FALSE;
382  }
383 
384  return SCIP_OKAY;
385 }
386 
387 
388 /** sort the bounds of variables topologically */
389 static
391  SCIP* scip, /**< SCIP data structure */
392  int* vbvars, /**< array to store variable bounds in topological order */
393  int* nvbvars /**< pointer to store number of variable bounds in the graph */
394  )
395 {
396  int* dfsstack;
397  int* stacknextedge;
398  int* stacknextcliquevar;
399  int* cliqueexit;
400  SCIP_Shortbool* visited;
401  int nbounds;
402  int i;
403 
404  assert(scip != NULL);
405 
406  nbounds = 2 * SCIPgetNVars(scip);
407 
408  SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
409  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
410  SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) );
411  SCIP_CALL( SCIPallocClearBufferArray(scip, &cliqueexit, SCIPgetNCliques(scip)) );
412  SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) );
413 
414 
415  /* while there are unvisited nodes, run dfs on the inverse graph starting from one of these nodes; the dfs orders are
416  * stored in the topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which
417  * gives us a topological order
418  */
419  for( i = 0; i < nbounds; ++i )
420  {
421  if( !visited[i] )
422  {
423  SCIP_CALL( dfs(scip, i, visited, dfsstack, stacknextedge, stacknextcliquevar, cliqueexit, vbvars, nvbvars) );
424  }
425  }
426  assert(*nvbvars <= nbounds);
427 
428  SCIPfreeBufferArray(scip, &visited);
429  SCIPfreeBufferArray(scip, &cliqueexit);
430  SCIPfreeBufferArray(scip, &stacknextcliquevar);
431  SCIPfreeBufferArray(scip, &stacknextedge);
432  SCIPfreeBufferArray(scip, &dfsstack);
433 
434  return SCIP_OKAY;
435 }
436 
437 /** initialize candidate lists */
438 static
440  SCIP* scip, /**< original SCIP data structure */
441  SCIP_HEURDATA* heurdata /**< structure containing heurdata */
442  )
443 {
444  SCIP_VAR** vars;
445  int* vbs;
446  int nvars;
447  int nvbs;
448  int v;
449 
450  SCIPdebugMsg(scip, "initialize variable bound heuristic (%s)\n", SCIPgetProbName(scip));
451 
452  vars = SCIPgetVars(scip);
453  nvars = SCIPgetNIntVars(scip) + SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip);
454  nvbs = 0;
455 
456  /* initialize data */
457  heurdata->usednodes = 0;
458  heurdata->initialized = TRUE;
459 
460  if( nvars == 0 )
461  return SCIP_OKAY;
462 
463  /* allocate memory for the arrays of the heurdata */
464  SCIP_CALL( SCIPallocBufferArray(scip, &vbs, 2 * nvars) );
465 
466  /* create the topological sorted variable array with respect to the variable bounds */
467  SCIP_CALL( topologicalSort(scip, vbs, &nvbs) );
468 
469  /* check if the candidate list contains enough candidates */
470  if( nvbs > 0 && nvbs >= 0.1 * heurdata->minintfixingrate * nvars )
471  {
472  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbvars, nvbs) );
473  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbbounds, nvbs) );
474 
475  /* capture variable candidate list */
476  for( v = 0; v < nvbs; ++v )
477  {
478  heurdata->vbvars[v] = vars[getVarIndex(vbs[v])];
479  heurdata->vbbounds[v] = getBoundtype(vbs[v]);
480  assert(SCIPvarIsIntegral(heurdata->vbvars[v]));
481 
482  SCIP_CALL( SCIPcaptureVar(scip, heurdata->vbvars[v]) );
483  }
484 
485  heurdata->nvbvars = nvbs;
486  heurdata->applicable = TRUE;
487  }
488 
489  /* free buffer arrays */
490  SCIPfreeBufferArray(scip, &vbs);
491 
492  SCIPstatisticMessage("vbvars %.3g (%s)\n",
493  (nvbs * 100.0) / nvars, SCIPgetProbName(scip));
494 
495  /* if there is already a solution, add an objective cutoff */
496  if( SCIPgetNSols(scip) > 0 )
497  {
498  SCIP_Real upperbound;
499  SCIP_Real minimprove;
500  SCIP_Real cutoffbound;
501 
502  minimprove = heurdata->minimprove;
503  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
504 
505  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
506 
507  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
508  {
509  cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * SCIPgetLowerbound(scip);
510  }
511  else
512  {
513  if( SCIPgetUpperbound ( scip ) >= 0 )
514  cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
515  else
516  cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
517  }
518  heurdata->cutoffbound = MIN(upperbound, cutoffbound);
519  }
520  else
521  heurdata->cutoffbound = SCIPinfinity(scip);
522  return SCIP_OKAY;
523 }
524 
525 /** apply variable bound fixing during probing */
526 static
528  SCIP* scip, /**< original SCIP data structure */
529  SCIP_HEURDATA* heurdata, /**< structure containing heurdata */
530  SCIP_VAR** vars, /**< variables to fix during probing */
531  int nvbvars, /**< number of variables in the variable bound graph */
532  SCIP_Bool tighten, /**< should variables be fixed to cause other fixings? */
533  int obj, /**< should the objective be taken into account? */
534  SCIP_Bool* allobj1, /**< pointer to store whether all variables were fixed according to obj=1 scheme */
535  SCIP_Bool* allobj2, /**< pointer to store whether all variables were fixed according to obj=2 scheme */
536  SCIP_Bool* backtracked, /**< was backtracking performed at least once? */
537  SCIP_Bool* infeasible /**< pointer to store whether propagation detected infeasibility */
538  )
539 {
540  SCIP_VAR* lastvar;
541  SCIP_VAR* var;
542  SCIP_Real lastfixval;
543  SCIP_Bool lastfixedlb;
544  SCIP_Bool fixtolower;
546  int nbacktracks = 0;
547  int v;
548 
549  /* loop over variables in topological order */
550  for( v = 0; v < nvbvars && !(*infeasible); ++v )
551  {
552  var = vars[v];
553  bound = heurdata->vbbounds[v];
554 
555  /*SCIPdebugMsg(scip, "topoorder[%d]: %s(%s) (%s) [%g,%g] (obj=%g)\n", v,
556  bound == SCIP_BOUNDTYPE_UPPER ? "ub" : "lb", SCIPvarGetName(var),
557  SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ? "c" : "d",
558  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetObj(var));*/
559 
560  /* only check integer or binary variables */
562  continue;
563 
564  /* skip variables which are already fixed */
565  if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) )
566  continue;
567 
568 
569  /* there are two cases for tighten:
570  * 1) tighten == TRUE: we go through the list of variables and fix variables to force propagation;
571  * this is be obtained by fixing the variable to the other bound (which means
572  * that the current bound is changed and so, much propagation is triggered
573  * since we are starting with the bounds which are most influential).
574  * 2) tighten == FALSE: we fix variables to avoid too much propagation in order to avoid reaching
575  * infeasibility. Therefore, we fix the variable to the current bound, so that
576  * this bound is not changed and does not propagate. The other bound is changed
577  * and propagates, but is later in the order, so less influential.
578  */
579  fixtolower = (tighten == (bound == SCIP_BOUNDTYPE_UPPER));
580 
581  /* if we want to take into account the objective function coefficients, we only perform a fixing if the variable
582  * would be fixed to its best bound; otherwise, we just continue
583  */
584  if( ((SCIPvarGetObj(var) >= 0) != fixtolower) )
585  {
586  if( obj == 1 )
587  continue;
588  else
589  *allobj1 = FALSE;
590  }
591  /* if we want to take into account the objective function coefficients but reverted, we only perform a fixing if the variable
592  * would be fixed to its worst bound; otherwise, we just continue
593  */
594  if( ((SCIPvarGetObj(var) >= 0) == fixtolower) )
595  {
596  if( obj == 2 )
597  continue;
598  else
599  *allobj2 = FALSE;
600  }
601  lastvar = var;
602 
603  /* fix the variable to its bound */
604  if( fixtolower )
605  {
606  /* we cannot fix to infinite bounds */
607  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
608  continue;
609 
610  /* only open a new probing node if we will not exceed the maximal tree depth */
611  if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
612  {
613  SCIP_CALL( SCIPnewProbingNode(scip) );
614  }
615 
616  /* fix variable to lower bound */
617  SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) );
618  SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to lower bound <%g> (%d pseudo cands)\n",
620  lastfixedlb = TRUE;
621  lastfixval = SCIPvarGetLbLocal(var);
622  }
623  else
624  {
625  /* we cannot fix to infinite bounds */
626  if( SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
627  continue;
628 
629  /* only open a new probing node if we will not exceed the maximal tree depth */
630  if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
631  {
632  SCIP_CALL( SCIPnewProbingNode(scip) );
633  }
634 
635  /* fix variable to upper bound */
636  SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
637  SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to upper bound <%g> (%d pseudo cands)\n",
639  lastfixedlb = FALSE;
640  lastfixval = SCIPvarGetUbLocal(var);
641  }
642 
643  /* check if problem is already infeasible */
644  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
645 
646  /* probing detected infeasibility: backtrack */
647  if( *infeasible )
648  {
649  assert(lastvar != NULL);
650 
652  ++nbacktracks;
653  *infeasible = FALSE;
654 
655  /* increase the lower bound of the variable which caused the infeasibility */
656  if( lastfixedlb && lastfixval + 0.5 < SCIPvarGetUbLocal(lastvar) )
657  {
658  if( lastfixval + 0.5 > SCIPvarGetLbLocal(lastvar) )
659  {
660  SCIP_CALL( SCIPchgVarLbProbing(scip, lastvar, lastfixval + 1.0) );
661  }
662  }
663  else if( !lastfixedlb && lastfixval - 0.5 > SCIPvarGetLbLocal(lastvar) )
664  {
665  if( lastfixval - 0.5 < SCIPvarGetUbLocal(lastvar) )
666  {
667  SCIP_CALL( SCIPchgVarUbProbing(scip, lastvar, lastfixval - 1.0) );
668  }
669  }
670  /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a valid
671  * global bound for the last fixed variable that conflicts with applying the reverse bound change after backtracking;
672  * in that case, we ran into a deadend and stop
673  */
674  else
675  {
676  *infeasible = TRUE;
677  }
678  lastvar = NULL;
679 
680  if( !(*infeasible) )
681  {
682  /* propagate fixings */
683  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
684 
685  SCIPdebugMessage("backtrack %d was %sfeasible\n", nbacktracks, (*infeasible ? "in" : ""));
686  }
687 
688  if( *infeasible )
689  {
690  SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks);
691 
692  break;
693  }
694  else if( nbacktracks > heurdata->maxbacktracks )
695  {
696  SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks);
697  break;
698  }
699  }
700  }
701 
702  *backtracked = (nbacktracks > 0);
703 
704  return SCIP_OKAY;
705 }
706 
707 /** creates a new solution for the original problem by copying the solution of the subproblem */
708 static
710  SCIP* scip, /**< original SCIP data structure */
711  SCIP* subscip, /**< SCIP structure of the subproblem */
712  SCIP_VAR** subvars, /**< the variables of the subproblem */
713  SCIP_SOL* newsol, /**< working solution */
714  SCIP_SOL* subsol, /**< solution of the subproblem */
715  SCIP_Bool* success /**< used to store whether new solution was found or not */
716  )
717 {
718  SCIP_VAR** vars; /* the original problem's variables */
719  int nvars;
720  SCIP_Real* subsolvals; /* solution values of the subproblem */
721 
722  assert( scip != NULL );
723  assert( subscip != NULL );
724  assert( subvars != NULL );
725  assert( subsol != NULL );
726 
727  /* get variables' data */
728  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
729 
730  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
731  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
732  */
733  assert( nvars <= SCIPgetNOrigVars(subscip) );
734 
735  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
736 
737  /* copy the solution */
738  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
739 
740  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
741 
742  /* try to add new solution to scip and free it immediately */
743  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
744 
745  SCIPfreeBufferArray(scip, &subsolvals);
746 
747  return SCIP_OKAY;
748 }
749 
750 /** copy problem to sub-SCIP, solve it, and add solutions */
751 static
753  SCIP* scip, /**< original SCIP data structure */
754  SCIP* subscip, /**< SCIP structure of the subproblem */
755  SCIP_HEURDATA* heurdata, /**< heuristic data */
756  SCIP_VAR** vars, /**< variables of the main SCIP */
757  int nvars, /**< number of variables of the main SCIP */
758  SCIP_SOL* sol, /**< working solution */
759  SCIP_Longint nstallnodes, /**< stalling node limit for the sub-SCIP */
760  SCIP_Real lowerbound, /**< lower bound of the main SCIP / current subproblem */
761  int* nprevars, /**< pointer to store the number of presolved variables */
762  SCIP_Bool* wasfeas, /**< pointer to store if a feasible solution was found */
763  SCIP_RESULT* result /**< pointer to store the result */
764  )
765 {
766  SCIP_VAR** subvars;
767  SCIP_HASHMAP* varmap;
768  int i;
769 
770  assert(scip != NULL);
771  assert(subscip != NULL);
772  assert(heurdata != NULL);
773 
774  /* create the variable mapping hash map */
775  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
776 
777  SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_vbounds", NULL, NULL, 0, FALSE, FALSE, TRUE, NULL) );
778 
779  if( heurdata->copycuts )
780  {
781  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
782  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
783  }
784 
785  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
786 
787  for( i = 0; i < nvars; i++ )
788  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
789 
790  /* free hash map */
791  SCIPhashmapFree(&varmap);
792 
793  /* do not abort subproblem on CTRL-C */
794  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
795 
796 #ifdef SCIP_DEBUG
797  /* for debugging, enable full output */
798  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
799  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
800 #else
801  /* disable statistic timing inside sub SCIP and output to console */
802  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
803  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
804 #endif
805 
806  /* set limits for the subproblem */
807  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
808  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
809  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
810 
811  /* speed up sub-SCIP by not checking dual LP feasibility */
812  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
813 
814  /* forbid call of heuristics and separators solving sub-CIPs */
815  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
816 
817  /* disable cutting plane separation */
819 
820  /* disable expensive presolving */
822 
823  /* use inference branching */
824  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
825  {
826  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
827  }
828 
829  /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
830  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
831  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
832  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
833  * made for the original SCIP
834  */
835  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
836  {
837  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
838  }
839 
840  /* set a cutoff bound */
841  if( SCIPgetNSols(scip) > 0 )
842  {
843  SCIP_Real upperbound;
844  SCIP_Real minimprove;
845  SCIP_Real cutoffbound;
846 
847  minimprove = heurdata->minimprove;
848  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
849 
850  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
851 
852  if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
853  {
854  cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
855  }
856  else
857  {
858  if( SCIPgetUpperbound ( scip ) >= 0 )
859  cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
860  else
861  cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
862  }
863  heurdata->cutoffbound = MIN(upperbound, cutoffbound);
864  }
865 
866  if( !SCIPisInfinity(scip, heurdata->cutoffbound) )
867  {
868  SCIP_CALL( SCIPsetObjlimit(subscip, heurdata->cutoffbound) );
869  SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", heurdata->cutoffbound);
870  }
871 
872  SCIPdebugMsg(scip, "starting solving vbound-submip at time %g\n", SCIPgetSolvingTime(scip));
873 
874  /* solve the subproblem */
875  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
876  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
877  */
878  SCIP_CALL_ABORT( SCIPpresolve(subscip) );
879 
880  SCIPdebugMsg(scip, "vbounds heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n",
881  SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip),
882  ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
883 
884  *nprevars = SCIPgetNVars(subscip);
885 
886  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
887  * to ensure that not only the MIP but also the LP relaxation is easy enough
888  */
889  if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate )
890  {
891  SCIP_SOL** subsols;
892  SCIP_Bool success;
893  int nsubsols;
894 
895  SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
896 
897  SCIP_CALL_ABORT( SCIPsolve(subscip) );
898 
899  SCIPdebugMsg(scip, "ending solving vbounds-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
900 
901  /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
902  * try all solutions until one was accepted
903  */
904  nsubsols = SCIPgetNSols(subscip);
905  subsols = SCIPgetSols(subscip);
906  success = FALSE;
907  *wasfeas = FALSE;
908 
909  for( i = 0; i < nsubsols && !success; ++i )
910  {
911  SCIP_CALL( createNewSol(scip, subscip, subvars, sol, subsols[i], &success) );
912  if( !(*wasfeas) )
913  {
914  SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, wasfeas) );
915  if( (*wasfeas) )
916  SCIPdebugMsg(scip, "found feasible solution in sub-MIP: %16.9g\n", SCIPgetSolOrigObj(scip, sol));
917  }
918  }
919  if( success )
920  {
921  *result = SCIP_FOUNDSOL;
922  }
923  }
924 
925 #ifdef SCIP_DEBUG
926  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
927 #endif
928 
929  /* free subproblem */
930  SCIPfreeBufferArray(scip, &subvars);
931 
932  return SCIP_OKAY;
933 }
934 
935 /** main procedure of the vbounds heuristic */
936 static
938  SCIP* scip, /**< original SCIP data structure */
939  SCIP_HEUR* heur, /**< heuristic */
940  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
941  SCIP_VAR** vbvars, /**< variables to fix during probing */
942  int nvbvars, /**< number of variables to fix */
943  SCIP_Bool tighten, /**< should variables be fixed to cause other fixings? */
944  int obj, /**< should the objective be taken into account? */
945  SCIP_Bool* skipobj1, /**< pointer to store whether the run with obj=1 can be skipped, or NULL */
946  SCIP_Bool* skipobj2, /**< pointer to store whether the run with obj=2 can be skipped, or NULL */
947  SCIP_RESULT* result /**< pointer to store the result */
948  )
949 {
950  SCIPstatistic( SCIP_CLOCK* clock; )
951  SCIP_VAR** vars;
952  SCIP_SOL* sol = NULL;
953  SCIP_Longint nstallnodes;
954  SCIP_LPSOLSTAT lpstatus;
955  SCIP_Real lowerbound;
956  SCIP_Bool wasfeas = FALSE;
957  SCIP_Bool cutoff;
958  SCIP_Bool lperror;
959  SCIP_Bool solvelp;
960  SCIP_Bool allobj1 = TRUE;
961  SCIP_Bool allobj2 = TRUE;
962  SCIP_Bool backtracked = TRUE;
963  int oldnpscands;
964  int npscands;
965  int nvars;
966  int nprevars;
967 
968  assert(heur != NULL);
969  assert(heurdata != NULL);
970  assert(nvbvars > 0);
971 
972  /* initialize default values */
973  cutoff = FALSE;
974 
975  if( skipobj1 != NULL )
976  *skipobj1 = FALSE;
977  if( skipobj2 != NULL )
978  *skipobj2 = FALSE;
979 
980  /* get variable data of original problem */
981  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
982 
983  SCIPstatistic( nprevars = nvars; )
984 
985  if( nvbvars < nvars * heurdata->minintfixingrate )
986  return SCIP_OKAY;
987 
988  if( *result == SCIP_DIDNOTRUN )
989  *result = SCIP_DIDNOTFIND;
990 
991  lowerbound = SCIPgetLowerbound(scip);
992 
993  oldnpscands = SCIPgetNPseudoBranchCands(scip);
994 
995  /* calculate the maximal number of branching nodes until heuristic is aborted */
996  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
997 
998  /* reward variable bounds heuristic if it succeeded often */
999  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
1000  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
1001  nstallnodes += heurdata->nodesofs;
1002 
1003  /* determine the node limit for the current process */
1004  nstallnodes -= heurdata->usednodes;
1005  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
1006 
1007  SCIPdebugMsg(scip, "apply variable bounds heuristic at node %lld on %d variable bounds, tighten: %d obj: %d\n",
1008  SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nvbvars, tighten, obj);
1009 
1010  /* check whether we have enough nodes left to call subproblem solving */
1011  if( nstallnodes < heurdata->minnodes )
1012  {
1013  SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
1014  return SCIP_OKAY;
1015  }
1016 
1017  if( SCIPisStopped(scip) )
1018  return SCIP_OKAY;
1019 
1020  SCIPstatistic( SCIP_CALL( SCIPcreateClock(scip, &clock) ) );
1021  SCIPstatistic( SCIP_CALL( SCIPstartClock(scip, clock) ) );
1022 
1023  /* check whether the LP should be solved at the current node in the tree to determine whether the heuristic
1024  * is allowed to solve an LP
1025  */
1026  solvelp = SCIPhasCurrentNodeLP(scip);
1027 
1028  if( !SCIPisLPConstructed(scip) && solvelp )
1029  {
1030  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1031 
1032  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1033  if( cutoff )
1034  {
1036  goto TERMINATE;
1037  }
1038 
1039  SCIP_CALL( SCIPflushLP(scip) );
1040  }
1041 
1042  /* start probing */
1043  SCIP_CALL( SCIPstartProbing(scip) );
1044 
1045 #ifdef COLLECTSTATISTICS
1046  SCIPenableVarHistory(scip);
1047 #endif
1048 
1049  /* create temporary solution */
1050  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1051 
1052  /* apply the variable fixings */
1053  SCIP_CALL( applyVboundsFixings(scip, heurdata, vbvars, nvbvars, tighten, obj, &allobj1, &allobj2, &backtracked, &cutoff) );
1054 
1055  if( skipobj1 != NULL )
1056  *skipobj1 = allobj1;
1057 
1058  if( skipobj2 != NULL )
1059  *skipobj2 = allobj2;
1060 
1061  if( cutoff || SCIPisStopped(scip) )
1062  goto TERMINATE;
1063 
1064  /* check that we had enough fixings */
1065  npscands = SCIPgetNPseudoBranchCands(scip);
1066 
1067  SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
1068 
1069  /* check fixing rate */
1070  if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) )
1071  {
1072  if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
1073  {
1074  SCIP_Bool allrowsfulfilled = FALSE;
1075 
1076  SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) );
1077 
1078  if( cutoff || SCIPisStopped(scip) )
1079  {
1080  SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n");
1081  goto TERMINATE;
1082  }
1083 
1084  npscands = SCIPgetNPseudoBranchCands(scip);
1085 
1086  SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
1087  npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate);
1088 
1089  if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) )
1090  {
1091  SCIPdebugMsg(scip, "--> too few fixings\n");
1092 
1093  goto TERMINATE;
1094  }
1095  }
1096  else
1097  {
1098  SCIPdebugMsg(scip, "--> too few fixings\n");
1099 
1100  goto TERMINATE;
1101  }
1102  }
1103 
1104  assert(!cutoff);
1105 
1106  /*************************** Probing LP Solving ***************************/
1107  lpstatus = SCIP_LPSOLSTAT_ERROR;
1108  lperror = FALSE;
1109  /* solve lp only if the problem is still feasible */
1110  if( solvelp )
1111  {
1112  SCIPdebugMsg(scip, "starting solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip));
1113 
1114  /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
1115  * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
1116  * SCIP will stop.
1117  */
1118 #ifdef NDEBUG
1119  {
1120  SCIP_Bool retstat;
1121  retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
1122  if( retstat != SCIP_OKAY )
1123  {
1124  SCIPwarningMessage(scip, "Error while solving LP in vbound heuristic; LP solve terminated with code <%d>\n",
1125  retstat);
1126  }
1127  }
1128 #else
1129  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
1130 #endif
1131  SCIPdebugMsg(scip, "ending solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip));
1132 
1133  lpstatus = SCIPgetLPSolstat(scip);
1134 
1135  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1136  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
1137  }
1138 
1139  /* check if this is a feasible solution */
1140  if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
1141  {
1142  SCIP_Bool stored;
1143  SCIP_Bool success;
1144 
1145  lowerbound = SCIPgetLPObjval(scip);
1146 
1147  /* copy the current LP solution to the working solution */
1148  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
1149 
1150  SCIP_CALL( SCIProundSol(scip, sol, &success) );
1151 
1152  if( success )
1153  {
1154  SCIPdebugMsg(scip, "vbound heuristic found roundable primal solution: obj=%g\n",
1155  SCIPgetSolOrigObj(scip, sol));
1156 
1157  /* check solution for feasibility, and add it to solution store if possible.
1158  * Neither integrality nor feasibility of LP rows have to be checked, because they
1159  * are guaranteed by the heuristic at this stage.
1160  */
1161 #ifdef SCIP_DEBUG
1162  SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
1163 #else
1164  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
1165 #endif
1166 
1167 #ifdef SCIP_DEBUG
1168  SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &wasfeas) );
1169  assert(wasfeas);
1170  SCIPdebugMsg(scip, "found feasible solution by LP rounding: %16.9g\n", SCIPgetSolOrigObj(scip, sol));
1171 #endif
1172 
1173  if( stored )
1174  {
1175  *result = SCIP_FOUNDSOL;
1176  }
1177 
1178  /* we found a solution, so we are done */
1179  goto TERMINATE;
1180  }
1181  }
1182  /*************************** END Probing LP Solving ***************************/
1183 
1184  /*************************** Start Subscip Solving ***************************/
1185  /* if no solution has been found --> fix all other variables by subscip if necessary */
1186  if( !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
1187  {
1188  SCIP* subscip;
1189  SCIP_RETCODE retcode;
1190  SCIP_Bool valid;
1191 
1192  /* check whether there is enough time and memory left */
1193  SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
1194 
1195  if( !valid )
1196  goto TERMINATE;
1197 
1198  /* create subproblem */
1199  SCIP_CALL( SCIPcreate(&subscip) );
1200 
1201  retcode = setupAndSolveSubscip(scip, subscip, heurdata, vars, nvars, sol, nstallnodes, lowerbound,
1202  &nprevars, &wasfeas, result);
1203 
1204  SCIP_CALL( SCIPfree(&subscip) );
1205 
1206  SCIP_CALL( retcode );
1207  }
1208 
1209  /*************************** End Subscip Solving ***************************/
1210 
1211  TERMINATE:
1212 #ifdef SCIP_STATISTIC
1213  SCIP_CALL( SCIPstopClock(scip, clock) );
1214  SCIPstatisticMessage("vbound: tighten=%u obj=%d nvars=%d presolnvars=%d ratio=%.2f infeas=%u found=%d time=%.4f\n",
1215  tighten, obj, nvars, nprevars, (nvars - nprevars) / (SCIP_Real)nvars, cutoff,
1216  wasfeas ? 1 : 0, SCIPclockGetTime(clock) );
1217 #endif
1218 
1219  SCIPstatistic( SCIP_CALL( SCIPfreeClock(scip, &clock) ) );
1220 
1221  /* free solution */
1222  if( sol != NULL )
1223  {
1224  SCIP_CALL( SCIPfreeSol(scip, &sol) );
1225  }
1226 
1227  /* exit probing mode */
1228  if( SCIPinProbing(scip) )
1229  {
1230  SCIP_CALL( SCIPendProbing(scip) );
1231  }
1232 
1233  return SCIP_OKAY;
1234 }
1235 
1236 
1237 /*
1238  * Callback methods of primal heuristic
1239  */
1240 
1241 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1242 static
1243 SCIP_DECL_HEURCOPY(heurCopyVbounds)
1244 { /*lint --e{715}*/
1245  assert(scip != NULL);
1246  assert(heur != NULL);
1247  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1249  /* call inclusion method of heuristic */
1251 
1252  return SCIP_OKAY;
1253 }
1254 
1255 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1256 static
1257 SCIP_DECL_HEURFREE(heurFreeVbounds)
1258 { /*lint --e{715}*/
1259  SCIP_HEURDATA* heurdata;
1260 
1261  /* free heuristic data */
1262  heurdata = SCIPheurGetData(heur);
1263 
1264  SCIPfreeBlockMemory(scip, &heurdata);
1265  SCIPheurSetData(heur, NULL);
1266 
1267  return SCIP_OKAY;
1268 }
1269 
1270 
1271 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1272 static
1273 SCIP_DECL_HEUREXITSOL(heurExitsolVbounds)
1274 { /*lint --e{715}*/
1275  SCIP_HEURDATA* heurdata;
1276  int v;
1277 
1278  heurdata = SCIPheurGetData(heur);
1279  assert(heurdata != NULL);
1280 
1281  /* release all variables */
1282  for( v = 0; v < heurdata->nvbvars; ++v )
1283  {
1284  SCIP_CALL( SCIPreleaseVar(scip, &heurdata->vbvars[v]) );
1285  }
1286 
1287  /* free varbounds array */
1288  SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbbounds, heurdata->nvbvars);
1289  SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbvars, heurdata->nvbvars);
1290 
1291  /* reset heuristic data structure */
1292  heurdataReset(heurdata);
1293 
1294  return SCIP_OKAY;
1295 }
1296 
1297 /** execution method of primal heuristic */
1298 static
1299 SCIP_DECL_HEUREXEC(heurExecVbounds)
1300 { /*lint --e{715}*/
1301  SCIP_HEURDATA* heurdata;
1302  SCIP_Bool skipobj1;
1303  SCIP_Bool skipobj2;
1304 #ifdef NOCONFLICT
1305  SCIP_Bool enabledconflicts;
1306 #endif
1307 
1308  assert( heur != NULL );
1309  assert( scip != NULL );
1310  assert( result != NULL );
1311 
1312  *result = SCIP_DIDNOTRUN;
1313 
1314  if( SCIPgetNPseudoBranchCands(scip) == 0 )
1315  return SCIP_OKAY;
1316 
1317  heurdata = SCIPheurGetData(heur);
1318  assert(heurdata != NULL);
1319 
1320  if( !heurdata->initialized )
1321  {
1322  SCIP_CALL( initializeCandsLists(scip, heurdata) );
1323  }
1324 
1325  if( !heurdata->applicable )
1326  return SCIP_OKAY;
1327 
1328 #ifdef NOCONFLICT
1329  /* disable conflict analysis */
1330  SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
1331 
1332  if( !SCIPisParamFixed(scip, "conflict/enable") )
1333  {
1334  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
1335  }
1336 #endif
1337 
1338  /* try variable bounds */
1339  skipobj1 = FALSE;
1340  skipobj2 = FALSE;
1341  if( (heurdata->feasvariant & VBOUNDVARIANT_NOOBJ) != 0 )
1342  {
1343  SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 0,
1344  &skipobj1, &skipobj2, result) );
1345  }
1346  if( !skipobj1 && (heurdata->feasvariant & VBOUNDVARIANT_BESTBOUND) != 0)
1347  {
1348  SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 1, NULL, NULL, result) );
1349  }
1350  if( !skipobj2 && (heurdata->feasvariant & VBOUNDVARIANT_WORSTBOUND) != 0)
1351  {
1352  SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 2, NULL, NULL, result) );
1353  }
1354 
1355  skipobj1 = FALSE;
1356  skipobj2 = FALSE;
1357  if( (heurdata->tightenvariant & VBOUNDVARIANT_NOOBJ) != 0 )
1358  {
1359  SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 0,
1360  &skipobj1, &skipobj2, result) );
1361  }
1362  if( !skipobj1 && (heurdata->tightenvariant & VBOUNDVARIANT_BESTBOUND) != 0)
1363  {
1364  SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 1, NULL, NULL, result) );
1365  }
1366  if( !skipobj2 && (heurdata->tightenvariant & VBOUNDVARIANT_WORSTBOUND) != 0)
1367  {
1368  SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 2, NULL, NULL, result) );
1369  }
1370 
1371 #ifdef NOCONFLICT
1372  /* reset the conflict analysis */
1373  if( !SCIPisParamFixed(scip, "conflict/enable") )
1374  {
1375  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1376  }
1377 #endif
1378 
1379  return SCIP_OKAY;
1380 }
1381 
1382 /*
1383  * primal heuristic specific interface methods
1384  */
1385 
1386 /** creates the vbounds primal heuristic and includes it in SCIP */
1388  SCIP* scip /**< SCIP data structure */
1389  )
1390 {
1391  SCIP_HEURDATA* heurdata;
1392  SCIP_HEUR* heur;
1393 
1394  /* create vbounds primal heuristic data */
1395  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1396  heurdataReset(heurdata);
1397 
1398  /* include primal heuristic */
1399  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1401  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecVbounds, heurdata) );
1402 
1403  assert(heur != NULL);
1404 
1405  /* set non-NULL pointers to callback methods */
1406  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyVbounds) );
1407  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeVbounds) );
1408  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolVbounds) );
1409 
1410  /* add variable bounds primal heuristic parameters */
1411  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate",
1412  "minimum percentage of integer variables that have to be fixed",
1413  &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1414 
1415  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate",
1416  "minimum percentage of variables that have to be fixed within sub-SCIP (integer and continuous)",
1417  &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1418 
1419  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1420  "maximum number of nodes to regard in the subproblem",
1421  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1422 
1423  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1424  "number of nodes added to the contingent of the total nodes",
1425  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1426 
1427  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1428  "minimum number of nodes required to start the subproblem",
1429  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1430 
1431  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1432  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1433  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1434 
1435  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1436  "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1437  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1438 
1439  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1440  "maximum number of propagation rounds during probing (-1 infinity)",
1441  &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
1442 
1443  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1444  "should all active cuts from cutpool be copied to constraints in subproblem?",
1445  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1446 
1447  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings",
1448  "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1449  &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) );
1450 
1451  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
1452  "maximum number of backtracks during the fixing process",
1453  &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) );
1454 
1455  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/feasvariant",
1456  "which variants of the vbounds heuristic that try to stay feasible should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1457  &heurdata->feasvariant, TRUE, DEFAULT_FEASVARIANT, 0, 7, NULL, NULL) );
1458 
1459  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/tightenvariant",
1460  "which tightening variants of the vbounds heuristic should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1461  &heurdata->tightenvariant, TRUE, DEFAULT_TIGHTENVARIANT, 0, 7, NULL, NULL) );
1462 
1463  return SCIP_OKAY;
1464 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8209
#define HEUR_TIMING
Definition: heur_vbounds.c:58
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
#define DEFAULT_NODESQUOT
Definition: heur_vbounds.c:71
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38570
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5158
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:17490
#define HEUR_USESSUBSCIP
Definition: heur_vbounds.c:59
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3353
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
#define DEFAULT_NODESOFS
Definition: heur_vbounds.c:70
#define getVarIndex(idx)
Definition: heur_vbounds.c:139
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35958
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:42327
SCIP_RETCODE SCIPincludeHeurVbounds(SCIP *scip)
#define DEFAULT_MININTFIXINGRATE
Definition: heur_vbounds.c:62
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35931
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:22622
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:17468
static void heurdataReset(SCIP_HEURDATA *heurdata)
Definition: heur_vbounds.c:151
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1344
internal methods for clocks and timing issues
static long bound
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47082
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12246
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip.c:37359
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17639
#define VBOUNDVARIANT_BESTBOUND
Definition: heur_vbounds.c:48
#define getOtherBoundIndex(idx)
Definition: heur_vbounds.c:142
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18760
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46109
#define isIndexLowerbound(idx)
Definition: heur_vbounds.c:141
static SCIP_RETCODE initializeCandsLists(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_vbounds.c:444
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3389
#define VBOUNDVARIANT_WORSTBOUND
Definition: heur_vbounds.c:49
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39826
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4192
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3884
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:41741
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:205
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_RETCODE applyVboundsFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *allobj1, SCIP_Bool *allobj2, SCIP_Bool *backtracked, SCIP_Bool *infeasible)
Definition: heur_vbounds.c:532
#define SCIPstatisticMessage
Definition: pub_message.h:104
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:17510
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5132
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
#define DEFAULT_MINIMPROVE
Definition: heur_vbounds.c:66
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_vbounds.c:714
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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.c:8084
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36034
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:17480
#define DEFAULT_MAXNODES
Definition: heur_vbounds.c:61
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:46058
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip.c:29243
#define DEFAULT_MAXBACKTRACKS
Definition: heur_vbounds.c:73
#define SCIP_LONGINT_MAX
Definition: def.h:135
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:748
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
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.c:4265
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:45645
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17628
#define HEUR_NAME
Definition: heur_vbounds.c:51
#define DEFAULT_FEASVARIANT
Definition: heur_vbounds.c:84
#define getUbIndex(idx)
Definition: heur_vbounds.c:138
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
#define HEUR_PRIORITY
Definition: heur_vbounds.c:54
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip.c:29220
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7340
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:16109
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:46007
static SCIP_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Longint nstallnodes, SCIP_Real lowerbound, int *nprevars, SCIP_Bool *wasfeas, SCIP_RESULT *result)
Definition: heur_vbounds.c:757
static SCIP_RETCODE topologicalSort(SCIP *scip, int *vbvars, int *nvbvars)
Definition: heur_vbounds.c:395
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4401
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8145
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:36308
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38942
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:36151
#define HEUR_DESC
Definition: heur_vbounds.c:52
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4630
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:928
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip.c:15948
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3065
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
static SCIP_DECL_HEURCOPY(heurCopyVbounds)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35993
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:428
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip.c:4432
#define SCIP_Shortbool
Definition: def.h:69
#define HEUR_FREQ
Definition: heur_vbounds.c:55
#define DEFAULT_MINMIPFIXINGRATE
Definition: heur_vbounds.c:63
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:43271
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:36544
static SCIP_RETCODE dfs(SCIP *scip, int startnode, SCIP_Shortbool *visited, int *dfsstack, int *stacknextedge, int *stacknextcliquevar, int *cliqueexit, int *dfsnodes, int *ndfsnodes)
Definition: heur_vbounds.c:165
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:17532
#define DEFAULT_MINNODES
Definition: heur_vbounds.c:69
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1324
static SCIP_DECL_HEUREXEC(heurExecVbounds)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29202
#define DEFAULT_TIGHTENVARIANT
Definition: heur_vbounds.c:87
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#define DEFAULT_COPYCUTS
Definition: heur_vbounds.c:74
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip.c:40974
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetNImplVars(SCIP *scip)
Definition: scip.c:11941
static SCIP_DECL_HEUREXITSOL(heurExitsolVbounds)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:40018
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11240
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3365
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38529
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25952
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39777
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38988
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip.c:29267
locks primal heuristic
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#define getLbIndex(idx)
Definition: heur_vbounds.c:137
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40694
#define SCIP_MAXTREEDEPTH
Definition: def.h:286
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define getBoundtype(idx)
Definition: heur_vbounds.c:140
#define HEUR_FREQOFS
Definition: heur_vbounds.c:56
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
#define HEUR_MAXDEPTH
Definition: heur_vbounds.c:57
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12856
#define DEFAULT_USELOCKFIXINGS
Definition: heur_vbounds.c:77
int SCIPgetNCliques(SCIP *scip)
Definition: scip.c:24873
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
#define SCIPstatistic(x)
Definition: pub_message.h:101
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18726
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:17522
#define SCIP_Longint
Definition: def.h:134
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16959
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4156
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38807
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8129
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35898
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3343
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:46423
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:43420
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35852
#define SCIP_CALL_ABORT(x)
Definition: def.h:329
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
static SCIP_DECL_HEURFREE(heurFreeVbounds)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
#define VBOUNDVARIANT_NOOBJ
Definition: heur_vbounds.c:47
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16853
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36078
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46092
default SCIP plugins
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.c:4321
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5083
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4746
#define HEUR_DISPCHAR
Definition: heur_vbounds.c:53
static SCIP_RETCODE applyVbounds(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vbvars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *skipobj1, SCIP_Bool *skipobj2, SCIP_RESULT *result)
Definition: heur_vbounds.c:942
#define DEFAULT_MAXPROPROUNDS
Definition: heur_vbounds.c:72
SCIP callable library.
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.c:4239
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:780
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872