Scippy

SCIP

Solving Constraint Integer Programs

heur_completesol.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_completesol.c
17  * @brief COMPLETESOL - primal heuristic trying to complete given partial solutions
18  * @author Jakob Witzig
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "blockmemshell/memory.h"
24 #include "scip/cons_linear.h"
25 #include "scip/heur_completesol.h"
26 #include "scip/pub_event.h"
27 #include "scip/pub_heur.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_sol.h"
31 #include "scip/pub_var.h"
32 #include "scip/scip_branch.h"
33 #include "scip/scip_cons.h"
34 #include "scip/scip_copy.h"
35 #include "scip/scip_event.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_heur.h"
38 #include "scip/scip_mem.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_nlp.h"
41 #include "scip/scip_nodesel.h"
42 #include "scip/scip_numerics.h"
43 #include "scip/scip_param.h"
44 #include "scip/scip_prob.h"
45 #include "scip/scip_probing.h"
46 #include "scip/scip_sol.h"
47 #include "scip/scip_solve.h"
48 #include "scip/scip_solvingstats.h"
49 #include "scip/scip_timing.h"
50 #include "scip/scip_tree.h"
51 #include "scip/scip_var.h"
52 #include <string.h>
53 
54 #define HEUR_NAME "completesol"
55 #define HEUR_DESC "primal heuristic trying to complete given partial solutions"
56 #define HEUR_DISPCHAR 'h'
57 #define HEUR_PRIORITY 0
58 #define HEUR_FREQ 0
59 #define HEUR_FREQOFS 0
60 #define HEUR_MAXDEPTH 0
61 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
62 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
63 
64 /* default values for heuristic plugins */
65 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
66 #define DEFAULT_MAXUNKRATE 0.85 /**< maximum percentage of unknown solution values */
67 #define DEFAULT_ADDALLSOLS FALSE /**< should all subproblem solutions be added to the original SCIP? */
68 #define DEFAULT_MINNODES 50LL /**< minimum number of nodes to regard in the subproblem */
69 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
70 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
71 #define DEFAULT_LPLIMFAC 2.0 /**< factor by which the limit on the number of LP depends on the node limit */
72 #define DEFAULT_OBJWEIGHT 1.0 /**< weight of the original objective function (1: only original objective) */
73 #define DEFAULT_BOUNDWIDENING 0.1 /**< bound widening factor applied to continuous variables
74  * (0: round bounds to next integer, 1: relax to global bounds)
75  */
76 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which the incumbent should be improved at least */
77 #define DEFAULT_MINOBJWEIGHT 1e-3 /**< minimal weight for original objective function (zero could lead to infinite solutions) */
78 #define DEFAULT_IGNORECONT FALSE /**< should solution values for continuous variables be ignored? */
79 #define DEFAULT_BESTSOLS 5 /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */
80 #define DEFAULT_MAXPROPROUNDS 10 /**< maximal number of iterations in propagation (-1: no limit) */
81 #define DEFAULT_MAXLPITER -1LL /**< maximal number of LP iterations (-1: no limit) */
82 #define DEFAULT_MAXCONTVARS -1 /**< maximal number of continuous variables after presolving (-1: no limit) */
83 #define DEFAULT_BEFOREPRESOL TRUE /**< should the heuristic run before presolving? */
84 
85 /* event handler properties */
86 #define EVENTHDLR_NAME "Completesol"
87 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
88 
89 
90 /** primal heuristic data */
91 struct SCIP_HeurData
92 {
93  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
94  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
95  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
96  SCIP_Longint maxlpiter; /**< maximal number of LP iterations (-1: no limit) */
97  SCIP_Real maxunknownrate; /**< maximal rate of changed coefficients in the objective function */
98  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
99  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
100  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
101  SCIP_Real objweight; /**< weight of the original objective function (1: only original obj, 0: try to keep to given solution) */
102  SCIP_Real boundwidening; /**< bound widening factor applied to continuous variables
103  * (0: fix variables to given solution values, 1: relax to global bounds)
104  */
105  SCIP_Real minimprove; /**< factor by which the incumbent should be improved at least */
106  SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
107  SCIP_Bool ignorecont; /**< should solution values for continuous variables be ignored? */
108  SCIP_Bool beforepresol; /**< should the heuristic run before presolving? */
109  int bestsols; /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */
110  int maxcontvars; /**< maximal number of continuous variables after presolving (-1: no limit) */
111  int maxproprounds; /**< maximal number of iterations in propagation (-1: no limit) */
112 };
113 
114 /* ---------------- Callback methods of event handler ---------------- */
115 
116 /* exec the event handler
117  *
118  * we interrupt the solution process
119  */
120 static
121 SCIP_DECL_EVENTEXEC(eventExecCompletesol)
122 {
123  SCIP_HEURDATA* heurdata;
124 
125  assert(eventhdlr != NULL);
126  assert(eventdata != NULL);
127  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
128  assert(event != NULL);
129  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
130 
131  heurdata = (SCIP_HEURDATA*)eventdata;
132  assert(heurdata != NULL);
133 
134  /* interrupt solution process of sub-SCIP */
135  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
136  {
137  SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
139  }
140 
141  return SCIP_OKAY;
142 }
143 
144 /** creates a subproblem by fixing a number of variables */
145 static
147  SCIP* scip, /**< original SCIP data structure */
148  SCIP* subscip, /**< SCIP data structure for the subproblem */
149  SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
150  SCIP_VAR** subvars, /**< the variables of the subproblem */
151  SCIP_SOL* partialsol, /**< partial solution */
152  SCIP_Bool* tightened, /**< array to store for which variables we have found bound tightenings */
153  SCIP_Bool* success /**< pointer to store whether the creation was successful */
154  )
155 {
156  SCIP_VAR** vars;
157  SCIP_CONS* objcons;
158  SCIP_Real epsobj;
159  SCIP_Real cutoff;
160  SCIP_Real upperbound;
161  char consobjname[SCIP_MAXSTRLEN];
162  int nvars;
163  int i;
164 
165  assert(scip != NULL);
166  assert(subscip != NULL);
167  assert(subvars != NULL);
168  assert(heurdata != NULL);
169 
170  *success = TRUE;
171 
172  /* if there is already a solution, add an objective cutoff */
173  if( SCIPgetNSols(scip) > 0 )
174  {
175  assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
176 
177  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
178 
179  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
180  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
181  else
182  {
183  if( SCIPgetUpperbound(scip) >= 0 )
184  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
185  else
186  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
187  }
188  cutoff = MIN(upperbound, cutoff);
189  SCIPdebugMsg(scip, "set cutoff=%g for sub-SCIP\n", cutoff);
190  }
191  else
192  cutoff = SCIPinfinity(scip);
193 
194  /* calculate objective coefficients for all potential epsilons */
195  if( SCIPisEQ(scip, heurdata->objweight, 1.0) )
196  return SCIP_OKAY;
197  else if( !SCIPisInfinity(scip, cutoff) )
198  epsobj = 1.0;
199  else
200  {
201  /* divide by objweight to avoid changing objective coefficient of original problem variables */
202  epsobj = (1.0 - heurdata->objweight)/heurdata->objweight;
203 
204  /* scale with -1 if we have a maximization problem */
206  epsobj *= -1.0;
207  }
208 
209  /* get active variables */
210  vars = SCIPgetVars(scip);
211  nvars = SCIPgetNVars(scip);
212 
213  objcons = NULL;
214 
215  /* add constraints to measure the distance to the given partial solution */
216  for( i = 0; i < nvars; i++ )
217  {
218  SCIP_Real solval;
219  int idx;
220 
221  assert(SCIPvarIsActive(vars[i]));
222 
223  /* add objective function as a constraint, if a primal bound exists */
224  if( SCIPisInfinity(scip, cutoff) )
225  {
226  /* create the constraints */
227  if( objcons == NULL )
228  {
229  SCIP_Real lhs;
230  SCIP_Real rhs;
231 
232  if( SCIPgetObjsense(subscip) == SCIP_OBJSENSE_MINIMIZE )
233  {
234  lhs = -SCIPinfinity(subscip);
235  rhs = cutoff;
236  }
237  else
238  {
239  lhs = cutoff;
240  rhs = SCIPinfinity(subscip);
241  }
242 
243  (void)SCIPsnprintf(consobjname, SCIP_MAXSTRLEN, "obj");
244  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, consobjname, 0, NULL, NULL, lhs, rhs) );
245  }
246 
247  /* add the variable to the constraints */
248  SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(subvars[i])) );
249 
250  /* set objective coefficient to 0.0 */
251  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
252  }
253 
254  solval = SCIPgetSolVal(scip, partialsol, vars[i]);
255 
256  /* skip variables with unknown solution value */
257  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
258  continue;
259 
260  idx = SCIPvarGetProbindex(vars[i]);
261  assert(idx >= 0);
262 
263  /* skip variables where we already found some bound tightenings */
264  if( tightened[idx] == FALSE )
265  {
266  /* special case: vars[i] is binary; we do not add an extra variable, but we mimic the behavior we would get with it.
267  * E.g., if the solval is 0.3, setting the variable to 0 would give a cost of 0.3 * epsobj, setting it to 1 gives
268  * 0.7 * epsobj. Thus, 0.3 * epsobj can be treated as a constant in the objective function and the variable gets
269  * an objective coefficient of 0.4 * epsobj.
270  */
271  if( SCIPvarIsBinary(vars[i]) )
272  {
273  SCIP_Real frac = SCIPfeasFrac(scip, solval);
274  SCIP_Real objcoef;
275 
276  frac = MIN(frac, 1-frac);
277  objcoef = (1 - 2*frac) * epsobj * (int)SCIPgetObjsense(scip);
278 
279  if( solval > 0.5 )
280  {
281  SCIP_CALL( SCIPchgVarObj(scip, vars[i], -objcoef) );
282  }
283  else
284  {
285  SCIP_CALL( SCIPchgVarObj(scip, vars[i], objcoef) );
286  }
287  }
288  else
289  {
290  SCIP_CONS* conspos;
291  SCIP_CONS* consneg;
292  SCIP_VAR* eps;
293  char consnamepos[SCIP_MAXSTRLEN];
294  char consnameneg[SCIP_MAXSTRLEN];
295  char epsname[SCIP_MAXSTRLEN];
296 
297  /* create two new variables */
298  (void)SCIPsnprintf(epsname, SCIP_MAXSTRLEN, "eps_%s", SCIPvarGetName(subvars[i]));
299 
300  SCIP_CALL( SCIPcreateVarBasic(subscip, &eps, epsname, 0.0, SCIPinfinity(scip), epsobj, SCIP_VARTYPE_CONTINUOUS) );
301  SCIP_CALL( SCIPaddVar(subscip, eps) );
302 
303  /* create two constraints */
304  (void)SCIPsnprintf(consnamepos, SCIP_MAXSTRLEN, "cons_%s_pos", SCIPvarGetName(subvars[i]));
305  (void)SCIPsnprintf(consnameneg, SCIP_MAXSTRLEN, "cons_%s_neq", SCIPvarGetName(subvars[i]));
306 
307  /* x_{i} - s_{i} <= e_{i} <==> x_{i} - e_{i} <= s_{i} */
308  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &conspos, consnamepos, 0, NULL, NULL, -SCIPinfinity(scip), solval) );
309  SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, subvars[i], 1.0) );
310  SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, eps, -1.0) );
311  SCIP_CALL( SCIPaddCons(subscip, conspos) );
312  SCIP_CALL( SCIPreleaseCons(subscip, &conspos) );
313 
314  /* s_{i} - x_{i} <= e_{i} <==> e_{i} - x_{i} >= s_{i} */
315  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &consneg, consnameneg, 0, NULL, NULL, solval, SCIPinfinity(scip)) );
316  SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, subvars[i], -1.0) );
317  SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, eps, 1.0) );
318  SCIP_CALL( SCIPaddCons(subscip, consneg) );
319  SCIP_CALL( SCIPreleaseCons(subscip, &consneg) );
320 
321  /* release the variables */
322  SCIP_CALL( SCIPreleaseVar(subscip, &eps) );
323  }
324  }
325  }
326 
327  /* add and release the constraint representing the original objective function */
328  if( objcons != NULL )
329  {
330  SCIP_CALL( SCIPaddCons(subscip, objcons) );
331  SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );
332  }
333 
334  return SCIP_OKAY;
335 }
336 
337 /** creates a new solution for the original problem by copying the solution of the subproblem */
338 static
340  SCIP* scip, /**< original SCIP data structure */
341  SCIP* subscip, /**< SCIP structure of the subproblem */
342  SCIP_VAR** subvars, /**< the variables of the subproblem */
343  SCIP_HEUR* heur, /**< Completesol heuristic structure */
344  SCIP_SOL* subsol, /**< solution of the subproblem or the partial */
345  SCIP_Bool* success /**< used to store whether new solution was found or not */
346  )
347 {
348  SCIP_VAR** vars; /* the original problem's variables */
349  int nvars; /* the original problem's number of variables */
350  SCIP_SOL* newsol; /* solution to be created for the original problem */
351  int v;
352 
353  assert(scip != NULL);
354  assert(subscip != NULL);
355  assert(subvars != NULL);
356  assert(subsol != NULL);
357 
358  /* get variables' data */
359  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
360 
361  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
362  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
363  */
364  assert(nvars <= SCIPgetNOrigVars(subscip));
365 
366  /* create new solution for the original problem */
367  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
368 
369  for( v = 0; v < nvars; v++ )
370  {
371  SCIP_Real solval = SCIPgetSolVal(subscip, subsol, subvars[v]);
372 
373  assert(!SCIPisInfinity(subscip, solval) && !SCIPisInfinity(subscip, -solval));
374  assert(solval != SCIP_UNKNOWN); /*lint !e777*/
375 
376  SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], solval) );
377  }
378 
379  /* try to add new solution to SCIP and free it immediately */
380  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
381 
382  return SCIP_OKAY;
383 }
384 
385 /** perform a probing bound change or fixes the variable */
386 static
388  SCIP* scip, /**< original SCIP data structure */
389  SCIP_VAR* var, /**< problem variable */
390  SCIP_Real newval, /**< new bound */
391  SCIP_BRANCHDIR branchdir, /**< bound change direction */
392  SCIP_Bool* success /**< pointer to store whether the bound could be tightened */
393  )
394 {
395  SCIP_Real ub;
396  SCIP_Real lb;
397 
398  assert(scip != NULL);
399  assert(var != NULL);
400 
401  (*success) = FALSE;
402 
403  ub = SCIPvarGetUbLocal(var);
404  lb = SCIPvarGetLbLocal(var);
405 
406  switch (branchdir) {
408  if( SCIPisLT(scip, newval, ub) && SCIPisGE(scip, newval, lb) )
409  {
410  SCIP_CALL( SCIPchgVarUbProbing(scip, var, newval) );
411  (*success) = TRUE;
412  }
413  break;
415  if( SCIPisLE(scip, newval, ub) && SCIPisGT(scip, newval, lb) )
416  {
417  SCIP_CALL( SCIPchgVarLbProbing(scip, var, newval) );
418  (*success) = TRUE;
419  }
420  break;
422  if( SCIPisLE(scip, newval, ub) && SCIPisGE(scip, newval, lb) )
423  {
424  SCIP_CALL( SCIPfixVarProbing(scip, var, newval) );
425  (*success) = TRUE;
426  }
427  break;
428  default:
429  return SCIP_INVALIDDATA;
430  }/*lint !e788*/
431 
432  return SCIP_OKAY;
433 }
434 
435 /** tries variables bound changes guided by the given solution */
436 static
438  SCIP* scip, /**< original SCIP data structure */
439  SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
440  SCIP_VAR** vars, /**< problem variables */
441  int nvars, /**< number of problem variables */
442  SCIP_SOL* sol, /**< solution to guide the bound changes */
443  SCIP_Bool* tightened, /**< array to store if variable bound could be tightened */
444  SCIP_Bool* success /**< pointer to store the success */
445  )
446 {
447 #ifndef NDEBUG
448  SCIP_Bool incontsection;
449 #endif
450  SCIP_Bool abortearly;
451  SCIP_Bool cutoff;
452  SCIP_Bool probingsuccess;
453  SCIP_Longint ndomreds;
454  SCIP_Longint ndomredssum;
455  int nbndtightenings;
456  int v;
457 
458  assert(scip != NULL);
459  assert(heurdata != NULL);
460  assert(vars != NULL);
461  assert(nvars >= 0);
462  assert(sol != NULL);
463  assert(tightened != NULL);
464 
466 
467  SCIPdebugMsg(scip, "> start probing along the solution values\n");
468 
469  *success = TRUE;
470  abortearly = FALSE;
471  nbndtightenings = 0;
472  ndomredssum = 0;
473 #ifndef NDEBUG
474  incontsection = FALSE;
475 #endif
476 
477  /* there is at least one integral variable; open one probing node for all non-continuous variables */
478  if( nvars - SCIPgetNContVars(scip) > 0 )
479  {
480  SCIP_CALL( SCIPnewProbingNode(scip) );
481  }
482 
483  for( v = 0; v < nvars && !abortearly; v++ )
484  {
485  SCIP_Real solval;
486 
487  assert(SCIPvarIsActive(vars[v]));
488 
489  cutoff = FALSE;
490  ndomreds = 0;
491 
492 #ifndef NDEBUG
493  incontsection |= (!SCIPvarIsIntegral(vars[v])); /*lint !e514*/
494  assert(!incontsection || !SCIPvarIsIntegral(vars[v]));
495 #endif
496 
497  /* return if we have found enough domain reductions tightenings */
498  if( ndomredssum > 0.3*nvars )
499  break;
500 
501  solval = SCIPgetSolVal(scip, sol, vars[v]);
502 
503  /* skip unknown variables */
504  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
505  continue;
506  assert(!SCIPisInfinity(scip, solval) && !SCIPisInfinity(scip, -solval));
507 
508  /* variable is binary or integer */
509  if( SCIPvarIsIntegral(vars[v]) )
510  {
511  /* the solution value is integral, try to fix them */
512  if( SCIPisIntegral(scip, solval) )
513  {
514  SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) );
515  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
516  ++nbndtightenings;
517 
518 #ifdef SCIP_MORE_DEBUG
519  SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g \n", SCIPvarGetName(vars[v]),
520  SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval);
521 #endif
522  }
523  else
524  {
525  SCIP_Real ub = SCIPceil(scip, solval) + 1.0;
526  SCIP_Real lb = SCIPfloor(scip, solval) - 1.0;
527 
528  /* try tightening of upper bound */
529  if( SCIPisLT(scip, ub, SCIPvarGetUbLocal(vars[v])) )
530  {
531  SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
532  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
533  ++nbndtightenings;
534 
535 #ifdef SCIP_MORE_DEBUG
536  SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]),
537  SCIPvarGetUbGlobal(vars[v]), ub);
538 #endif
539  }
540 
541  /* try tightening of lower bound */
542  if( SCIPisGT(scip, lb, SCIPvarGetLbLocal(vars[v])) )
543  {
544  SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
545  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
546  ++nbndtightenings;
547 
548 #ifdef SCIP_MORE_DEBUG
549  SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]),
550  SCIPvarGetLbGlobal(vars[v]), ub);
551 #endif
552  }
553  }
554  }
555  /* variable is continuous */
556  else
557  {
558  /* fix to lb or ub */
559  if( SCIPisEQ(scip, solval, SCIPvarGetLbLocal(vars[v])) || SCIPisEQ(scip, solval, SCIPvarGetUbLocal(vars[v])) )
560  {
561  /* open a new probing node */
562  if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
563  {
564  SCIP_CALL( SCIPnewProbingNode(scip) );
565 
566  SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) );
567 
568  /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
569  * domain propagation
570  */
571  if( probingsuccess )
572  {
573  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
574  }
575 
576  if( cutoff )
577  {
578  ndomreds = 0;
580  }
581  else
582  {
583  assert(SCIPvarGetProbindex(vars[v]) >= 0);
584  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
585  ++nbndtightenings;
586 #ifdef SCIP_MORE_DEBUG
587  SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g (ndomreds=%lld)\n", SCIPvarGetName(vars[v]),
588  SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval, ndomreds);
589 #endif
590  }
591  }
592  else
593  /* abort probing */
594  abortearly = TRUE;
595  }
596  else
597  {
598  SCIP_Real offset;
599  SCIP_Real newub = SCIPvarGetUbGlobal(vars[v]);
600  SCIP_Real newlb = SCIPvarGetLbGlobal(vars[v]);
601 
602  /* both bound are finite */
603  if( !SCIPisInfinity(scip, -newlb) && !SCIPisInfinity(scip, newub) )
604  offset = REALABS(heurdata->boundwidening * (newub-newlb));
605  else
606  {
607  /* if one bound is finite, widen bound w.r.t. solution value and finite bound */
608  if( !SCIPisInfinity(scip, -newlb) )
609  offset = REALABS(heurdata->boundwidening * (solval-newlb));
610  else
611  {
612  assert(!SCIPisInfinity(scip, newub));
613  offset = REALABS(heurdata->boundwidening * (newub-solval));
614  }
615  }
616 
617  /* update bounds */
618  newub = SCIPceil(scip, solval) + offset;
619  newlb = SCIPfloor(scip, solval) - offset;
620 
621  /* try tightening of upper bound */
622  if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(vars[v])) )
623  {
624  /* open a new probing node */
625  if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
626  {
627  SCIP_CALL( SCIPnewProbingNode(scip) );
628  SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
629 
630  /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
631  * domain propagation
632  */
633  if( probingsuccess )
634  {
635  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
636  }
637 
638  if( cutoff )
639  {
640  ndomreds = 0;
641 
642  /* backtrack to last feasible probing node */
644 
645  /* we can tighten the lower bound by newub */
646  SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
647 
648  /* propagate the new bound */
649  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
650 
651  /* there is no feasible solution w.r.t. the current bounds */
652  if( cutoff )
653  {
654  SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n");
655  *success = FALSE;
656  return SCIP_OKAY;
657  }
658 #ifdef SCIP_MORE_DEBUG
659  SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n",
660  SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newub);
661 #endif
662  }
663  else
664  {
665  assert(SCIPvarGetProbindex(vars[v]) >= 0);
666  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
667  ++nbndtightenings;
668 #ifdef SCIP_MORE_DEBUG
669  SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
670  SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newub, ndomreds);
671 #endif
672  }
673  }
674  else
675  /* abort probing */
676  abortearly = TRUE;
677  }
678 
679  /* try tightening of lower bound */
680  if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(vars[v])) )
681  {
682  /* open a new probing node */
683  if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
684  {
685  SCIP_CALL( SCIPnewProbingNode(scip) );
686  SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
687 
688  /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
689  * domain propagation
690  */
691  if( probingsuccess )
692  {
693  SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, &ndomreds) );
694  }
695 
696  if( cutoff )
697  {
698  ndomreds = 0;
699 
700  /* backtrack to last feasible probing node */
702 
703  /* we can tighten the upper bound by newlb */
704  SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
705 
706  /* propagate the new bound */
707  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
708 
709  /* there is no feasible solution w.r.t. the current bounds */
710  if( cutoff )
711  {
712  SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n");
713  *success = FALSE;
714  return SCIP_OKAY;
715  }
716 #ifdef SCIP_MORE_DEBUG
717  SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n",
718  SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newlb);
719 #endif
720  }
721  else
722  {
723  assert(SCIPvarGetProbindex(vars[v]) >= 0);
724  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
725  ++nbndtightenings;
726 #ifdef SCIP_MORE_DEBUG
727  SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
728  SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newlb, ndomreds);
729 #endif
730  }
731  }
732  else
733  /* abort probing */
734  abortearly = TRUE;
735  }
736  }
737  }
738 
739  ndomredssum += ndomreds;
740  }
741 
742  SCIPdebugMsg(scip, "> found %d bound tightenings and %lld induced domain reductions (abort=%u).\n", nbndtightenings,
743  ndomredssum, abortearly);
744 
745  return SCIP_OKAY;
746 }
747 
748 /* setup and solve the sub-SCIP */
749 static
751  SCIP* scip, /**< original SCIP data structure */
752  SCIP* subscip, /**< sub-SCIP data structure */
753  SCIP_HEUR* heur, /**< heuristic data structure */
754  SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
755  SCIP_RESULT* result, /**< result data structure */
756  SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
757  SCIP_SOL* partialsol, /**< partial solution */
758  SCIP_Bool* tightened /**< array to store whether a variable was already tightened */
759  )
760 {
761  SCIP_HASHMAP* varmapf;
762  SCIP_VAR** vars;
763  SCIP_VAR** subvars = NULL;
764  SCIP_EVENTHDLR* eventhdlr;
765  int nvars;
766  int i;
767 
768  SCIP_SOL** subsols;
769  int nsubsols;
770 
771  SCIP_Bool valid;
772  SCIP_Bool success;
773  SCIP_RETCODE retcode;
774 
775  assert(scip != NULL);
776  assert(subscip != NULL);
777  assert(heur != NULL);
778  assert(heurdata != NULL);
779  assert(result != NULL);
780  assert(partialsol != NULL);
781 
782  vars = SCIPgetVars(scip);
783  nvars = SCIPgetNVars(scip);
784 
785  /* create the variable mapping hash map */
786  SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(subscip), nvars) );
787 
788  eventhdlr = NULL;
789  valid = FALSE;
790 
791  /* copy complete SCIP instance */
792  SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapf, NULL, "completesol", NULL, NULL, 0, FALSE, FALSE, TRUE, &valid) );
793  SCIPdebugMsg(scip, "Copying the SCIP instance returned with valid=%d.\n", valid);
794 
795  /* create event handler for LP events */
796  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCompletesol, NULL) );
797  if( eventhdlr == NULL )
798  {
799  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
800  return SCIP_PLUGINNOTFOUND;
801  }
802 
803  /* allocate memory to align the SCIP and the sub-SCIP variables */
804  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
805 
806  /* map all variables */
807  for( i = 0; i < nvars; i++ )
808  {
809  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapf, vars[i]);
810  assert(subvars[i] != NULL);
811  }
812 
813  /* free hash map */
814  SCIPhashmapFree(&varmapf);
815 
816  /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */
817  SCIP_CALL( createSubproblem(scip, subscip, heurdata, subvars, partialsol, tightened, &success) );
818  if( !success )
819  {
820  SCIPdebugMsg(scip, "Error while creating completesol subproblem w.r.t. partial solution <%p>.\n", (void*)partialsol);
821  goto TERMINATE;
822  }
823  SCIPdebugMsg(scip, "Completesol subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
824 
825  /* do not abort subproblem on CTRL-C */
826  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
827 
828 #ifdef SCIP_DEBUG
829  /* for debugging, enable full output */
830  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", SCIP_VERBLEVEL_FULL) );
831  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
832 #else
833  /* disable statistic timing inside sub SCIP and output to console */
834  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int) SCIP_VERBLEVEL_NONE) );
835  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
836 #endif
837 
838  /* set limits for the subproblem */
839  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
840  heurdata->nodelimit = heurdata->maxnodes;
841  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
842  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
843  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsols) );
844 
845  /* limit the number of LP iterations */
846  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", heurdata->maxlpiter) );
847  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiter) );
848 
849  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
850  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
851 
852  /* disable cutting plane separation */
854 
855  /* disable expensive presolving */
857 
858  /* use best estimate node selection */
859  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
860  {
861  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
862  }
863 
864  /* use inference branching */
865  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
866  {
867  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
868  }
869 
870  /* disable conflict analysis */
871  if( !SCIPisParamFixed(subscip, "conflict/enable") )
872  {
873  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
874  }
875 
876  /* speed up sub-SCIP by not checking dual LP feasibility */
877  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
878 
879  SCIP_CALL( SCIPtransformProb(subscip) );
880  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
881 
882  /* solve the subproblem */
883  SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
884 
885  /* errors in solving the subproblem should not kill the overall solving process;
886  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
887  */
888 
889  retcode = SCIPpresolve(subscip);
890 
891  /* errors in presolving the subproblem should not kill the overall solving process;
892  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
893  */
894  if( retcode != SCIP_OKAY )
895  {
896  SCIPwarningMessage(scip, "Error while presolving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
897 
898  SCIPABORT(); /*lint --e{527}*/
899 
900  goto TERMINATE;
901  }
902 
903  if( SCIPgetStage(subscip) == SCIP_STAGE_PRESOLVED )
904  {
905  SCIPdebugMsg(scip, "presolved instance has bin=%d, int=%d, cont=%d variables\n",
906  SCIPgetNBinVars(subscip), SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip));
907 
908  /* check whether the presolved instance is small enough */
909  if( heurdata->maxcontvars >= 0 && SCIPgetNContVars(subscip) > heurdata->maxcontvars )
910  {
911  SCIPdebugMsg(scip, "presolved instance has too many continuous variables (maxcontvars: %d)\n", heurdata->maxcontvars);
912  goto TERMINATE;
913  }
914 
915  /* set node limit of 1 if the presolved problem is an LP, otherwise we would start branching if an LP iteration
916  * limit was set by the user.
917  */
918  if( !SCIPisNLPEnabled(subscip) && SCIPgetNContVars(subscip) == SCIPgetNVars(subscip) )
919  {
920  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
921  }
922 
923  retcode = SCIPsolve(subscip);
924 
925  /* errors in solving the subproblem should not kill the overall solving process;
926  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
927  */
928  if( retcode != SCIP_OKAY )
929  {
930  SCIPwarningMessage(scip, "Error while solving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
931 
932  SCIPABORT(); /*lint --e{527}*/
933 
934  goto TERMINATE;
935  }
936  }
937 
938  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
939 
940  /* print solving statistics of subproblem if we are in SCIP's debug mode */
942 
943  /* check, whether a solution was found;
944  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
945  */
946  nsubsols = SCIPgetNSols(subscip);
947  subsols = SCIPgetSols(subscip);
948  success = FALSE;
949  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); i++ )
950  {
951  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
952  if( success )
953  *result = SCIP_FOUNDSOL;
954  }
955 
956  SCIPstatisticPrintf("%s statistic: fixed %6.3f integer variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT " nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT "\n",
957  HEUR_NAME, 0.0, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip),
958  nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
959 
960  TERMINATE:
961  SCIPfreeBufferArray(scip, &subvars);
962 
963  return SCIP_OKAY;
964 }
965 
966 /** main procedure of the completesol heuristic, creates and solves a sub-SCIP */
967 static
969  SCIP* scip, /**< original SCIP data structure */
970  SCIP_HEUR* heur, /**< heuristic data structure */
971  SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
972  SCIP_RESULT* result, /**< result data structure */
973  SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
974  SCIP_SOL* partialsol /**< partial solution */
975  )
976 {
977  SCIP* subscip;
978  SCIP_VAR** vars;
979  SCIP_Bool* tightened;
980  SCIP_Bool success;
981  SCIP_RETCODE retcode;
982  int nvars;
983 
984  assert(scip != NULL);
985  assert(heur != NULL);
986  assert(heurdata != NULL);
987  assert(result != NULL);
988  assert(partialsol != NULL);
989 
990  *result = SCIP_DIDNOTRUN;
991 
992  SCIPdebugMsg(scip, "+---+ Start Completesol heuristic +---+\n");
993 
994  /* check whether there is enough time and memory left */
995  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
996 
997  if( !success )
998  return SCIP_OKAY;
999 
1000  *result = SCIP_DIDNOTFIND;
1001 
1002  /* get variable data */
1003  vars = SCIPgetVars(scip);
1004  nvars = SCIPgetNVars(scip);
1005 
1006  /* get buffer memory and initialize it to FALSE */
1007  SCIP_CALL( SCIPallocClearBufferArray(scip, &tightened, nvars) );
1008 
1009  SCIP_CALL( SCIPstartProbing(scip) );
1010 
1011  SCIP_CALL( tightenVariables(scip, heurdata, vars, nvars, partialsol, tightened, &success) );
1012 
1013  if( !success )
1014  goto ENDPROBING;
1015 
1016  /* initialize the subproblem */
1017  SCIP_CALL( SCIPcreate(&subscip) );
1018 
1019  retcode = setupAndSolve(scip, subscip, heur, heurdata, result, nstallnodes, partialsol, tightened);
1020 
1021  /* free subproblem */
1022  SCIP_CALL( SCIPfree(&subscip) );
1023 
1024  SCIP_CALL( retcode );
1025 
1026  ENDPROBING:
1027  SCIPfreeBufferArray(scip, &tightened);
1028  SCIP_CALL( SCIPendProbing(scip) );
1029 
1030  return SCIP_OKAY;
1031 }
1032 
1033 
1034 /*
1035  * Callback methods of primal heuristic
1036  */
1037 
1038 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1039 static
1040 SCIP_DECL_HEURCOPY(heurCopyCompletesol)
1041 { /*lint --e{715}*/
1042  assert(scip != NULL);
1043  assert(heur != NULL);
1044  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1045 
1046  /* call inclusion method of primal heuristic */
1048 
1049  return SCIP_OKAY;
1050 }
1051 
1052 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1053 static
1054 SCIP_DECL_HEURFREE(heurFreeCompletesol)
1055 { /*lint --e{715}*/
1056  SCIP_HEURDATA* heurdata;
1057 
1058  assert(heur != NULL);
1059  assert(scip != NULL);
1060 
1061  /* get heuristic data */
1062  heurdata = SCIPheurGetData(heur);
1063  assert(heurdata != NULL);
1064 
1065  /* free heuristic data */
1066  SCIPfreeBlockMemory(scip, &heurdata);
1067  SCIPheurSetData(heur, NULL);
1068 
1069  return SCIP_OKAY;
1070 }
1071 
1072 /** execution method of primal heuristic */
1073 static
1074 SCIP_DECL_HEUREXEC(heurExecCompletesol)
1075 {/*lint --e{715}*/
1076  SCIP_HEURDATA* heurdata;
1077  SCIP_VAR** vars;
1078  SCIP_SOL** partialsols;
1079  SCIP_Longint nstallnodes;
1080  int npartialsols;
1081  int nunknown;
1082  int nfracints;
1083  int nvars;
1084  int s;
1085  int v;
1086 
1087  assert( heur != NULL );
1088  assert( scip != NULL );
1089  assert( result != NULL );
1090 
1091  *result = SCIP_DELAYED;
1092 
1093  /* do not call heuristic of node was already detected to be infeasible */
1094  if( nodeinfeasible )
1095  return SCIP_OKAY;
1096 
1097  /* get heuristic data */
1098  heurdata = SCIPheurGetData(heur);
1099  assert( heurdata != NULL );
1100 
1101  *result = SCIP_DIDNOTRUN;
1102 
1103  if( SCIPisStopped(scip) )
1104  return SCIP_OKAY;
1105 
1106  /* do not run after restart */
1107  if( SCIPgetNRuns(scip) > 1 )
1108  return SCIP_OKAY;
1109 
1110  /* check whether we want to run before presolving */
1111  if( (heurtiming & SCIP_HEURTIMING_BEFOREPRESOL) && !heurdata->beforepresol )
1112  return SCIP_OKAY;
1113 
1114  /* only run before root node */
1115  if( (heurtiming & SCIP_HEURTIMING_BEFORENODE)
1116  && (heurdata->beforepresol || SCIPgetCurrentNode(scip) != SCIPgetRootNode(scip)) )
1117  return SCIP_OKAY;
1118 
1119  /* get variable data and return of no variables are left in the problem */
1120  vars = SCIPgetVars(scip);
1121  nvars = SCIPgetNVars(scip);
1122 
1123  if( nvars == 0 )
1124  return SCIP_OKAY;
1125 
1126  /* calculate the maximal number of branching nodes until heuristic is aborted */
1127  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1128 
1129  /* reward Completesol if it succeeded often */
1130  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
1131  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
1132  nstallnodes += heurdata->nodesofs;
1133 
1134  /* determine the node limit for the current process */
1135  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
1136 
1137  /* check whether we have enough nodes left to call subproblem solving */
1138  if( nstallnodes < heurdata->minnodes )
1139  {
1140  SCIPdebugMsg(scip, "skipping Complete: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n",
1141  nstallnodes, heurdata->minnodes);
1142  return SCIP_OKAY;
1143  }
1144 
1145  /* check the number of variables with unknown value and continuous variables with fractional value */
1146  nfracints = 0;
1147 
1148  /* get all partial sols */
1149  npartialsols = SCIPgetNPartialSols(scip);
1150  partialsols = SCIPgetPartialSols(scip);
1151 
1152  /* loop over all partial solutions */
1153  for( s = 0; s < npartialsols; s++ )
1154  {
1155  SCIP_SOL* sol;
1156  SCIP_Real solval;
1157  SCIP_Real unknownrate;
1158 
1159  sol = partialsols[s];
1160  assert(sol != NULL);
1161  assert(SCIPsolIsPartial(sol));
1162 
1163  nunknown = 0;
1164  /* loop over all variables */
1165  for( v = 0; v < nvars; v++ )
1166  {
1167  assert(SCIPvarIsActive(vars[v]));
1168 
1169  /* skip continuous variables if they should ignored */
1170  if( !SCIPvarIsIntegral(vars[v]) && heurdata->ignorecont )
1171  continue;
1172 
1173  solval = SCIPgetSolVal(scip, sol, vars[v]);
1174 
1175  /* we only want to count variables that are unfixed after the presolving */
1176  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
1177  ++nunknown;
1178  else if( SCIPvarIsIntegral(vars[v]) && !SCIPisIntegral(scip, solval) )
1179  ++nfracints;
1180  }
1181 
1182  if( heurdata->ignorecont )
1183  unknownrate = nunknown/((SCIP_Real)SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip));
1184  else
1185  unknownrate = nunknown/((SCIP_Real)nvars);
1186  SCIPdebugMsg(scip, "%d (rate %.4f) unknown solution values\n", nunknown, unknownrate);
1187 
1188  /* run the heuristic, if not too many unknown variables exist */
1189  if( unknownrate > heurdata->maxunknownrate )
1190  continue;
1191 
1192  /* all variables have a finite/known solution value all integer variables have an integral solution value,
1193  * and there are no continuous variables
1194  * in the sub-SCIP, all variables would be fixed, so create a new solution without solving a sub-SCIP
1195  */
1196  if( nunknown == 0 && nfracints == 0 && SCIPgetNContVars(scip) == 0 && SCIPgetNImplVars(scip) == 0 )
1197  {
1198  SCIP_SOL* newsol;
1199  SCIP_Bool stored;
1200 
1201  assert(vars != NULL);
1202  assert(nvars >= 0);
1203 
1204  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1205 
1206  for( v = 0; v < nvars; v++ )
1207  {
1208  solval = SCIPgetSolVal(scip, sol, vars[v]);
1209  assert(solval != SCIP_UNKNOWN); /*lint !e777*/
1210 
1211  SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], solval) );
1212  }
1213 
1214  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
1215  if( stored )
1216  *result = SCIP_FOUNDSOL;
1217  }
1218  else
1219  {
1220  /* run the heuristic */
1221  SCIP_CALL( applyCompletesol(scip, heur, heurdata, result, nstallnodes, sol) );
1222  }
1223  }
1224 
1225  return SCIP_OKAY;
1226 }
1227 
1228 
1229 /*
1230  * primal heuristic specific interface methods
1231  */
1232 
1233 /** creates the completesol primal heuristic and includes it in SCIP */
1235  SCIP* scip /**< SCIP data structure */
1236  )
1237 {
1238  SCIP_HEURDATA* heurdata;
1239  SCIP_HEUR* heur;
1240 
1241  /* create completesol primal heuristic data */
1242  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1243  assert(heurdata != NULL);
1244 
1245  /* include primal heuristic */
1248  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCompletesol, heurdata) );
1249 
1250  assert(heur != NULL);
1251 
1252  /* set non fundamental callbacks via setter functions */
1253  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCompletesol) );
1254  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCompletesol) );
1255 
1256  /* add completesol primal heuristic parameters */
1257 
1258  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1259  "maximum number of nodes to regard in the subproblem",
1260  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1261 
1262  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1263  "minimum number of nodes required to start the subproblem",
1264  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1265 
1266  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxunknownrate",
1267  "maximal rate of unknown solution values",
1268  &heurdata->maxunknownrate, FALSE, DEFAULT_MAXUNKRATE, 0.0, 1.0, NULL, NULL) );
1269 
1270  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
1271  "should all subproblem solutions be added to the original SCIP?",
1272  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
1273 
1274  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1275  "number of nodes added to the contingent of the total nodes",
1276  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1277 
1278  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1279  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1280  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1281 
1282  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1283  "factor by which the limit on the number of LP depends on the node limit",
1284  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1285 
1286  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/objweight",
1287  "weight of the original objective function (1: only original objective)",
1288  &heurdata->objweight, TRUE, DEFAULT_OBJWEIGHT, DEFAULT_MINOBJWEIGHT, 1.0, NULL, NULL) );
1289 
1290  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/boundwidening",
1291  "bound widening factor applied to continuous variables (0: fix variables to given solution values, 1: relax to global bounds)",
1292  &heurdata->boundwidening, TRUE, DEFAULT_BOUNDWIDENING, 0.0, 1.0, NULL, NULL) );
1293 
1294  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1295  "factor by which the incumbent should be improved at least",
1296  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1297 
1298  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/ignorecont",
1299  "should number of continuous variables be ignored?",
1300  &heurdata->ignorecont, FALSE, DEFAULT_IGNORECONT, NULL, NULL) );
1301 
1302  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solutions",
1303  "heuristic stops, if the given number of improving solutions were found (-1: no limit)",
1304  &heurdata->bestsols, FALSE, DEFAULT_BESTSOLS, -1, INT_MAX, NULL, NULL) );
1305 
1306  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1307  "maximal number of iterations in propagation (-1: no limit)",
1308  &heurdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) );
1309 
1310  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforepresol",
1311  "should the heuristic run before presolving?",
1312  &heurdata->beforepresol, FALSE, DEFAULT_BEFOREPRESOL, NULL, NULL) );
1313 
1314  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiter",
1315  "maximal number of LP iterations (-1: no limit)",
1316  &heurdata->maxlpiter, FALSE, DEFAULT_MAXLPITER, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
1317 
1318  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcontvars",
1319  "maximal number of continuous variables after presolving",
1320  &heurdata->maxcontvars, FALSE, DEFAULT_MAXCONTVARS, -1, INT_MAX, NULL, NULL) );
1321 
1322  return SCIP_OKAY;
1323 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2167
#define EVENTHDLR_DESC
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:84
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
SCIP_Real SCIPsumepsilon(SCIP *scip)
#define DEFAULT_NODESQUOT
static SCIP_RETCODE createSubproblem(SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_SOL *partialsol, SCIP_Bool *tightened, SCIP_Bool *success)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
public methods for SCIP parameter handling
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:408
public methods for node selector plugins
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:155
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
#define DEFAULT_MINOBJWEIGHT
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3399
primal heuristic trying to complete given partial solutions
#define HEUR_MAXDEPTH
#define SCIP_MAXSTRLEN
Definition: def.h:274
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:122
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:70
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:171
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
public solving methods
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
public methods for timing
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:354
#define DEFAULT_MINIMPROVE
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:80
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16918
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3037
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1987
#define DEFAULT_MAXPROPROUNDS
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:359
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
int SCIPgetNPartialSols(SCIP *scip)
Definition: scip_sol.c:3376
static SCIP_DECL_HEURCOPY(heurCopyCompletesol)
#define DEFAULT_ADDALLSOLS
#define DEFAULT_BOUNDWIDENING
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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
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
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:891
#define DEFAULT_BESTSOLS
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_LONGINT_MAX
Definition: def.h:150
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2374
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:2911
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
real eps
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
SCIP_Longint SCIPgetNLPs(SCIP *scip)
#define DEFAULT_MINNODES
#define EVENTHDLR_NAME
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:282
static SCIP_DECL_EVENTEXEC(eventExecCompletesol)
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16929
#define SCIPerrorMessage
Definition: pub_message.h:45
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
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:286
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:276
#define HEUR_USESSUBSCIP
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1942
SCIP_EXPORT SCIP_SOLORIGIN SCIPsolGetOrigin(SCIP_SOL *sol)
Definition: sol.c:2460
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:47
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:99
#define DEFAULT_MAXCONTVARS
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:188
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
static SCIP_RETCODE tightenVariables(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Bool *tightened, SCIP_Bool *success)
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1224
static SCIP_RETCODE setupAndSolve(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_SOL *partialsol, SCIP_Bool *tightened)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:250
#define HEUR_TIMING
#define REALABS(x)
Definition: def.h:188
static SCIP_DECL_HEURFREE(heurFreeCompletesol)
public methods for problem copies
public methods for primal CIP solutions
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:224
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:940
static SCIP_RETCODE applyCompletesol(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_SOL *partialsol)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
#define SCIPstatisticPrintf
Definition: pub_message.h:107
#define SCIP_HEURTIMING_BEFOREPRESOL
Definition: type_timing.h:86
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:215
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2427
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
#define DEFAULT_MAXUNKRATE
#define DEFAULT_IGNORECONT
#define DEFAULT_MAXLPITER
#define HEUR_PRIORITY
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIP_UNKNOWN
Definition: def.h:185
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPincludeHeurCompletesol(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
SCIP_SOL ** SCIPgetPartialSols(SCIP *scip)
Definition: scip_sol.c:3354
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
#define DEFAULT_OBJWEIGHT
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
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_EXPORT SCIP_Bool SCIPsolIsPartial(SCIP_SOL *sol)
Definition: sol.c:2480
#define DEFAULT_NODESOFS
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
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 SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:94
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
#define DEFAULT_BEFOREPRESOL
static SCIP_RETCODE chgProbingBound(SCIP *scip, SCIP_VAR *var, SCIP_Real newval, SCIP_BRANCHDIR branchdir, SCIP_Bool *success)
#define SCIP_REAL_MAX
Definition: def.h:165
public methods for nonlinear relaxations
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
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
#define HEUR_FREQ
#define SCIP_LONGINT_FORMAT
Definition: def.h:156
public methods for branching rule plugins and branching
static SCIP_DECL_HEUREXEC(heurExecCompletesol)
public methods for managing events
general public methods
public methods for solutions
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4451
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:310
#define DEFAULT_LPLIMFAC
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
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_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2533
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:109
#define HEUR_DESC
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
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10263
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 SCIP_Real
Definition: def.h:164
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:335
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
#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
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2765
#define HEUR_NAME
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:314
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1109
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
SCIP_RETCODE SCIPtrySolFree(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:3218
#define SCIPABORT()
Definition: def.h:337
public methods for global and local (sub)problems
#define DEFAULT_MAXNODES
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:496
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:966
#define HEUR_FREQOFS
int SCIPgetNRuns(SCIP *scip)
memory allocation routines