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