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