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