Scippy

SCIP

Solving Constraint Integer Programs

heuristics.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 heuristics.c
26  * @ingroup OTHER_CFILES
27  * @brief methods commonly used by primal heuristics
28  * @author Gregor Hendel
29  */
30 
31 #include "scip/heuristics.h"
32 #include "scip/cons_linear.h"
33 #include "scip/scipdefplugins.h"
34 
35 #include "scip/pub_heur.h"
36 
37 /* the indicator and SOS1 constraint handlers are included for the diving algorithm SCIPperformGenericDivingAlgorithm() */
38 #include "scip/cons_indicator.h"
39 #include "scip/cons_sos1.h"
40 
41 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
42 
43 
44 /** solve probing LP */
45 static
47  SCIP* scip, /**< SCIP data structure */
48  SCIP_DIVESET* diveset, /**< diving settings */
49  SCIP_Longint maxnlpiterations, /**< maximum number of allowed LP iterations */
50  SCIP_DIVECONTEXT divecontext, /**< context for diving statistics */
51  SCIP_Bool* lperror, /**< pointer to store if an internal LP error occurred */
52  SCIP_Bool* cutoff /**< pointer to store whether the LP was infeasible */
53  )
54 {
55  int lpiterationlimit;
56  SCIP_RETCODE retstat;
57  SCIP_Longint nlpiterations;
58 
59  assert(lperror != NULL);
60  assert(cutoff != NULL);
61 
62  nlpiterations = SCIPgetNLPIterations(scip);
63 
64  /* allow at least MINLPITER more iterations so as not to run out of LP iterations during this solve */
65  lpiterationlimit = (int)(maxnlpiterations - SCIPdivesetGetNLPIterations(diveset, divecontext));
66  lpiterationlimit = MAX(lpiterationlimit, MINLPITER);
67 
68  retstat = SCIPsolveProbingLP(scip, lpiterationlimit, lperror, cutoff);
69 
70  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
71  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
72  */
73 #ifdef NDEBUG
74  if( retstat != SCIP_OKAY )
75  {
76  SCIPwarningMessage(scip, "Error while solving LP in %s diving heuristic; LP solve terminated with code <%d>.\n", SCIPdivesetGetName(diveset), retstat);
77  }
78 #else
79  SCIP_CALL( retstat );
80 #endif
81 
82  /* update iteration count */
83  SCIPupdateDivesetLPStats(scip, diveset, SCIPgetNLPIterations(scip) - nlpiterations, divecontext);
84 
85  return SCIP_OKAY;
86 }
87 
88 /** select the next variable and type of diving */
89 static
91  SCIP* scip, /**< SCIP data structure */
92  SCIP_DIVESET* diveset, /**< dive set */
93  SCIP_SOL* worksol, /**< current working solution */
94  SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered? */
95  SCIP_Bool storelpcandscores, /**< should the scores of the LP candidates be updated? */
96  SCIP_VAR** lpcands, /**< LP branching candidates, or NULL if not needed */
97  SCIP_Real * lpcandssol, /**< solution values LP branching candidates, or NULL if not needed */
98  SCIP_Real* lpcandsfrac, /**< fractionalities of LP branching candidates, or NULL if not needed*/
99  SCIP_Real* lpcandsscores, /**< array with LP branching candidate scores, or NULL */
100  SCIP_Bool* lpcandroundup, /**< array to remember whether the preferred branching direction is upwards */
101  int* nviollpcands, /**< pointer to store the number of LP candidates whose solution value already violates local bounds */
102  int nlpcands, /**< number of current LP cands */
103  SCIP_Bool* enfosuccess, /**< pointer to store whether a candidate was sucessfully found */
104  SCIP_Bool* infeasible /**< pointer to store whether the diving can be immediately aborted because it is infeasible */
105  )
106 {
107  assert(scip != NULL);
108  assert(worksol != NULL);
109  assert(!onlylpbranchcands || lpcandsscores != NULL);
110  assert(!onlylpbranchcands || lpcandroundup != NULL);
111  assert(enfosuccess != NULL);
112  assert(infeasible != NULL);
113  assert(nviollpcands != NULL);
114 
115  *nviollpcands = 0;
116  /* we use diving solution enforcement provided by the constraint handlers */
117  if( !onlylpbranchcands )
118  {
119  SCIP_CALL( SCIPgetDiveBoundChanges(scip, diveset, worksol, enfosuccess, infeasible) );
120  }
121  else
122  {
123  int c;
124  int bestcandidx;
125  SCIP_Real bestscore;
126  SCIP_Real score;
127 
128  bestscore = SCIP_REAL_MIN;
129  bestcandidx = -1;
130 
132 
133  /* search for the candidate that maximizes the dive set score function and whose solution value is still feasible */
134  for( c = 0; c < nlpcands; ++c )
135  {
136  assert(SCIPgetSolVal(scip, worksol, lpcands[c]) == lpcandssol[c]); /*lint !e777 doesn't like comparing floats for equality */
137 
138  /* scores are kept in arrays for faster reuse */
139  if( storelpcandscores )
140  {
141  SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_INTEGRALITY, lpcands[c], lpcandssol[c],
142  lpcandsfrac[c], &lpcandsscores[c], &lpcandroundup[c]) );
143  }
144 
145  score = lpcandsscores[c];
146  /* update the best candidate if it has a higher score and a solution value which does not violate one of the local bounds */
147  if( SCIPisLE(scip, SCIPvarGetLbLocal(lpcands[c]), lpcandssol[c]) && SCIPisGE(scip, SCIPvarGetUbLocal(lpcands[c]), lpcandssol[c]) )
148  {
149  if( score > bestscore )
150  {
151  bestcandidx = c;
152  bestscore = score;
153  }
154  }
155  else
156  ++(*nviollpcands);
157  }
158 
159  /* there is no guarantee that a candidate is found since local bounds might render all solution values infeasible */
160  *enfosuccess = (bestcandidx >= 0);
161  if( *enfosuccess )
162  {
163  /* if we want to round up the best candidate, it is added as the preferred bound change */
164  SCIP_CALL( SCIPaddDiveBoundChange(scip, lpcands[bestcandidx], SCIP_BRANCHDIR_UPWARDS,
165  SCIPceil(scip, lpcandssol[bestcandidx]), lpcandroundup[bestcandidx]) );
166  SCIP_CALL( SCIPaddDiveBoundChange(scip, lpcands[bestcandidx], SCIP_BRANCHDIR_DOWNWARDS,
167  SCIPfloor(scip, lpcandssol[bestcandidx]), ! lpcandroundup[bestcandidx]) );
168  }
169  }
170  return SCIP_OKAY;
171 }
172 
173 /** return the LP iteration budget suggestion for this dive set */
174 static
176  SCIP* scip, /**< SCIP data structure */
177  SCIP_DIVESET* diveset, /**< dive set data structure */
178  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
179  )
180 {
181  SCIP_Longint iterlimit;
182  /*todo another factor of 10, REALLY? */
183  iterlimit = (SCIP_Longint)((1.0 + 10*(SCIPdivesetGetNSols(diveset, divecontext)+1.0)/(SCIPdivesetGetNCalls(diveset, divecontext)+1.0)) * SCIPdivesetGetMaxLPIterQuot(diveset) * SCIPgetNNodeLPIterations(scip));
184  iterlimit += SCIPdivesetGetMaxLPIterOffset(diveset);
185  iterlimit -= SCIPdivesetGetNLPIterations(diveset, divecontext);
186 
187  return iterlimit;
188 }
189 
190 /** performs a diving within the limits of the @p diveset parameters
191  *
192  * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
193  * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
194  * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
195  *
196  * Starting from the current LP solution, the algorithm selects candidates which maximize the
197  * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
198  * and propagates the bound change on this candidate.
199  *
200  * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
201  * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
202  * or the last node is proven to be infeasible. It optionally backtracks and tries the
203  * other branching direction.
204  *
205  * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
206  * solved, and the old candidates are replaced by the new LP candidates.
207  *
208  * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
209  *
210  * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
211  * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
212  *
213  * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
214  * call will be executed, see SCIPgetLastDiveNode()
215  *
216  * @todo generalize method to work correctly with pseudo or external branching/diving candidates
217  */
219  SCIP* scip, /**< SCIP data structure */
220  SCIP_DIVESET* diveset, /**< settings for diving */
221  SCIP_SOL* worksol, /**< non-NULL working solution */
222  SCIP_HEUR* heur, /**< the calling primal heuristic */
223  SCIP_RESULT* result, /**< SCIP result pointer */
224  SCIP_Bool nodeinfeasible, /**< is the current node known to be infeasible? */
225  SCIP_Longint iterlim, /**< nonnegative iteration limit for the LP solves, or -1 for dynamic setting */
226  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
227  )
228 {
229  SCIP_CONSHDLR* indconshdlr; /* constraint handler for indicator constraints */
230  SCIP_CONSHDLR* sos1conshdlr; /* constraint handler for SOS1 constraints */
231  SCIP_VAR** lpcands;
232  SCIP_Real* lpcandssol;
233 
234  SCIP_VAR** previouscands;
235  SCIP_Real* lpcandsscores;
236  SCIP_Real* previousvals;
237  SCIP_Real* lpcandsfrac;
238  SCIP_Bool* lpcandroundup;
239  SCIP_Real searchubbound;
240  SCIP_Real searchavgbound;
241  SCIP_Real searchbound;
242  SCIP_Real ubquot;
243  SCIP_Real avgquot;
244  SCIP_Longint maxnlpiterations;
245  SCIP_Longint domreds;
246  int startndivecands;
247  int depth;
248  int maxdepth;
249  int maxdivedepth;
250  int totalnbacktracks;
251  int totalnprobingnodes;
252  int lastlpdepth;
253  int previouscandssize;
254  int lpcandsscoressize;
255  int nviollpcands;
256  SCIP_Longint oldnsolsfound;
257  SCIP_Longint oldnbestsolsfound;
258  SCIP_Longint oldnconflictsfound;
259 
260  SCIP_Bool success;
261  SCIP_Bool leafsol;
262  SCIP_Bool enfosuccess;
263  SCIP_Bool lperror;
264  SCIP_Bool cutoff;
265  SCIP_Bool backtracked;
266  SCIP_Bool backtrack;
267  SCIP_Bool onlylpbranchcands;
268 
269  int nlpcands;
270  int lpsolvefreq;
271 
272  assert(scip != NULL);
273  assert(heur != NULL);
274  assert(result != NULL);
275  assert(worksol != NULL);
276 
277  *result = SCIP_DELAYED;
278 
279  /* do not call heuristic in node that was already detected to be infeasible */
280  if( nodeinfeasible )
281  return SCIP_OKAY;
282 
283  /* only call heuristic, if an optimal LP solution is at hand */
285  return SCIP_OKAY;
286 
287  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
288  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
289  return SCIP_OKAY;
290 
291  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
292  if( !SCIPisLPSolBasic(scip) )
293  return SCIP_OKAY;
294 
295  /* don't dive two times at the same node */
296  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
297  return SCIP_OKAY;
298 
299  *result = SCIP_DIDNOTRUN;
300 
301  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
302  depth = SCIPgetDepth(scip);
303  maxdepth = SCIPgetMaxDepth(scip);
304  maxdepth = MAX(maxdepth, 30);
305  if( depth < SCIPdivesetGetMinRelDepth(diveset) * maxdepth || depth > SCIPdivesetGetMaxRelDepth(diveset) * maxdepth )
306  return SCIP_OKAY;
307 
308  /* calculate the maximal number of LP iterations */
309  if( iterlim < 0 )
310  {
311  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset, divecontext) + getDivesetIterLimit(scip, diveset, divecontext);
312  }
313  else
314  {
315  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset, divecontext) + iterlim;
316  }
317 
318  /* don't try to dive, if we took too many LP iterations during diving */
319  if( SCIPdivesetGetNLPIterations(diveset, divecontext) >= maxnlpiterations )
320  return SCIP_OKAY;
321 
322  /* allow at least a certain number of LP iterations in this dive */
323  if( SCIPdivesetGetNLPIterations(diveset, divecontext) + MINLPITER > maxnlpiterations )
324  maxnlpiterations = SCIPdivesetGetNLPIterations(diveset, divecontext) + MINLPITER;
325 
326  /* these constraint handlers are required for polishing an LP relaxation solution beyond rounding */
327  indconshdlr = SCIPfindConshdlr(scip, "indicator");
328  sos1conshdlr = SCIPfindConshdlr(scip, "SOS1");
329 
330  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
331 
332  onlylpbranchcands = SCIPdivesetUseOnlyLPBranchcands(diveset);
333  /* don't try to dive, if there are no diving candidates */
334  if( onlylpbranchcands && nlpcands == 0 )
335  return SCIP_OKAY;
336 
337  /* calculate the objective search bound */
338  if( SCIPgetNSolsFound(scip) == 0 )
339  {
340  ubquot = SCIPdivesetGetUbQuotNoSol(diveset);
341  avgquot = SCIPdivesetGetAvgQuotNoSol(diveset);
342  }
343  else
344  {
345  ubquot = SCIPdivesetGetUbQuot(diveset);
346  avgquot = SCIPdivesetGetAvgQuot(diveset);
347  }
348 
349  if( ubquot > 0.0 )
350  searchubbound = SCIPgetLowerbound(scip) + ubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
351  else
352  searchubbound = SCIPinfinity(scip);
353 
354  if( avgquot > 0.0 )
355  searchavgbound = SCIPgetLowerbound(scip) + avgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
356  else
357  searchavgbound = SCIPinfinity(scip);
358 
359  searchbound = MIN(searchubbound, searchavgbound);
360 
361  if( SCIPisObjIntegral(scip) )
362  searchbound = SCIPceil(scip, searchbound);
363 
364  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
365  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
366  if ( sos1conshdlr != NULL )
367  maxdivedepth += SCIPgetNSOS1Vars(sos1conshdlr);
368  maxdivedepth = MIN(maxdivedepth, maxdepth);
369  maxdivedepth *= 10;
370 
371  *result = SCIP_DIDNOTFIND;
372 
373  /* start probing mode */
374  SCIP_CALL( SCIPstartProbing(scip) );
375 
376  /* enables collection of variable statistics during probing */
377  SCIPenableVarHistory(scip);
378 
379  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, avgbound=%g, cutoffbound=%g, searchbound=%g\n",
380  SCIPgetNNodes(scip), SCIPheurGetName(heur), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPgetAvgDualbound(scip),
381  SCIPretransformObj(scip, SCIPgetCutoffbound(scip)), SCIPretransformObj(scip, searchbound));
382 
383  /* allocate buffer storage for previous candidates and their branching values for pseudo cost updates */
384  lpsolvefreq = SCIPdivesetGetLPSolveFreq(diveset);
385  previouscandssize = MAX(1, lpsolvefreq);
386  SCIP_CALL( SCIPallocBufferArray(scip, &previouscands, previouscandssize) );
387  SCIP_CALL( SCIPallocBufferArray(scip, &previousvals, previouscandssize) );
388 
389  /* keep some statistics */
390  lperror = FALSE;
391  cutoff = FALSE;
392  lastlpdepth = -1;
393  startndivecands = nlpcands;
394  totalnbacktracks = 0;
395  totalnprobingnodes = 0;
396  oldnsolsfound = SCIPgetNSolsFound(scip);
397  oldnbestsolsfound = SCIPgetNBestSolsFound(scip);
398  oldnconflictsfound = SCIPgetNConflictConssFound(scip);
399 
400  /* link the working solution to the dive set */
401  SCIPdivesetSetWorkSolution(diveset, worksol);
402 
403  if( onlylpbranchcands )
404  {
405  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsscores, nlpcands) );
406  SCIP_CALL( SCIPallocBufferArray(scip, &lpcandroundup, nlpcands) );
407 
408  lpcandsscoressize = nlpcands;
409  }
410  else
411  {
412  lpcandroundup = NULL;
413  lpcandsscores = NULL;
414  lpcandsscoressize = 0;
415  }
416 
417  enfosuccess = TRUE;
418  leafsol = FALSE;
419 
420  /* LP loop; every time a new LP was solved, conditions are checked
421  * dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
422  * - if possible, we dive at least with the depth 10
423  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
424  */
425  while( !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && enfosuccess
426  && (SCIPgetProbingDepth(scip) < 10
427  || nlpcands <= startndivecands - SCIPgetProbingDepth(scip) / 2
428  || (SCIPgetProbingDepth(scip) < maxdivedepth && SCIPdivesetGetNLPIterations(diveset, divecontext) < maxnlpiterations && SCIPgetLPObjval(scip) < searchbound))
429  && !SCIPisStopped(scip) )
430  {
431  SCIP_Real lastlpobjval;
432  int c;
433  SCIP_Bool allroundable;
434  SCIP_Bool infeasible;
435  int prevcandsinsertidx;
436 
437  /* remember the last LP depth */
438  assert(lastlpdepth < SCIPgetProbingDepth(scip));
439  lastlpdepth = SCIPgetProbingDepth(scip);
440  domreds = 0;
441 
442  SCIPdebugMsg(scip, "%s heuristic continues diving at depth %d, %d candidates left\n",
443  SCIPdivesetGetName(diveset), lastlpdepth, nlpcands);
444 
445  /* loop over candidates and determine if they are roundable */
446  allroundable = TRUE;
447  c = 0;
448  while( allroundable && c < nlpcands )
449  {
450  if( SCIPvarMayRoundDown(lpcands[c]) || SCIPvarMayRoundUp(lpcands[c]) )
451  allroundable = TRUE;
452  else
453  allroundable = FALSE;
454  ++c;
455  }
456 
457  /* if all candidates are roundable, try to round the solution */
458  if( allroundable )
459  {
460  success = FALSE;
461 
462  /* working solution must be linked to LP solution */
463  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
464  /* create solution from diving LP and try to round it */
465  SCIP_CALL( SCIProundSol(scip, worksol, &success) );
466 
467  /* adjust SOS1 constraints */
468  if( success && sos1conshdlr != NULL )
469  {
470  SCIP_Bool changed;
471  SCIP_CALL( SCIPmakeSOS1sFeasible(scip, sos1conshdlr, worksol, &changed, &success) );
472  }
473 
474  /* succesfully rounded solutions are tried for primal feasibility */
475  if( success )
476  {
477  SCIP_Bool changed = FALSE;
478  SCIPdebugMsg(scip, "%s found roundable primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
479 
480  /* adjust indicator constraints */
481  if( indconshdlr != NULL )
482  {
483  SCIP_CALL( SCIPmakeIndicatorsFeasible(scip, indconshdlr, worksol, &changed) );
484  }
485 
486  success = FALSE;
487  /* try to add solution to SCIP */
488  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, changed, &success) );
489 
490  /* check, if solution was feasible and good enough */
491  if( success )
492  {
493  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
494  *result = SCIP_FOUNDSOL;
495  leafsol = (nlpcands == 0);
496 
497  /* the rounded solution found above led to a cutoff of the node LP solution */
499  {
500  cutoff = TRUE;
501  break;
502  }
503  }
504  }
505  }
506 
507  /* working solution must be linked to LP solution */
508  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
509  lastlpobjval = SCIPgetLPObjval(scip);
510  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
511 
512  /* we must explicitly store the solution values by unlinking the solution, otherwise,
513  * the working solution may contain wrong entries, if, e.g., a backtrack occurred after an
514  * intermediate LP resolve or the LP was resolved during conflict analysis.
515  */
516  SCIP_CALL( SCIPunlinkSol(scip, worksol) );
517 
518  /* ensure array sizes for the diving on the fractional variables */
519  if( onlylpbranchcands && nlpcands > lpcandsscoressize )
520  {
521  assert(nlpcands > 0);
522  assert(lpcandsscores != NULL);
523  assert(lpcandroundup != NULL);
524 
525  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandsscores, nlpcands) );
526  SCIP_CALL( SCIPreallocBufferArray(scip, &lpcandroundup, nlpcands) );
527 
528  lpcandsscoressize = nlpcands;
529  }
530 
531  enfosuccess = FALSE;
532  /* select the next diving action by selecting appropriate dive bound changes for the preferred and alternative child */
533  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
534  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
535  &enfosuccess, &infeasible) );
536 
537  /* if we did not succeed finding an enforcement, the solution is potentially feasible and we break immediately */
538  if( ! enfosuccess )
539  break;
540 
541  prevcandsinsertidx = -1;
542 
543  /* start propagating candidate variables
544  * - until the desired targetdepth is reached,
545  * - or there is no further candidate variable left because of intermediate bound changes,
546  * - or a cutoff is detected
547  */
548  do
549  {
550  SCIP_VAR* bdchgvar;
551  SCIP_Real bdchgvalue;
552  SCIP_Longint localdomreds;
553  SCIP_BRANCHDIR bdchgdir;
554  int nbdchanges;
555 
556  /* ensure that a new candidate was successfully determined (usually at the end of the previous loop iteration) */
557  assert(enfosuccess);
558  bdchgvar = NULL;
559  bdchgvalue = SCIP_INVALID;
560  bdchgdir = SCIP_BRANCHDIR_AUTO;
561 
562  backtracked = FALSE;
563  do
564  {
565  int d;
566  SCIP_VAR** bdchgvars;
567  SCIP_BRANCHDIR* bdchgdirs;
568  SCIP_Real* bdchgvals;
569 
570  nbdchanges = 0;
571  /* get the bound change information stored in the dive set */
572  SCIPgetDiveBoundChangeData(scip, &bdchgvars, &bdchgdirs, &bdchgvals, &nbdchanges, !backtracked);
573 
574  assert(nbdchanges > 0);
575  assert(bdchgvars != NULL);
576  assert(bdchgdirs != NULL);
577  assert(bdchgvals != NULL);
578 
579  /* return if we reached the depth limit */
580  if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
581  {
582  SCIPdebugMsg(scip, "depth limit reached, we stop diving immediately.\n");
583  goto TERMINATE;
584  }
585 
586  /* dive deeper into the tree */
587  SCIP_CALL( SCIPnewProbingNode(scip) );
588  ++totalnprobingnodes;
589 
590  /* apply all suggested domain changes of the variables */
591  for( d = 0; d < nbdchanges; ++d )
592  {
593  SCIP_Real lblocal;
594  SCIP_Real ublocal;
595  SCIP_Bool infeasbdchange;
596 
597  /* get the next bound change data: variable, direction, and value */
598  bdchgvar = bdchgvars[d];
599  bdchgvalue = bdchgvals[d];
600  bdchgdir = bdchgdirs[d];
601 
602  assert(bdchgvar != NULL);
603  lblocal = SCIPvarGetLbLocal(bdchgvar);
604  ublocal = SCIPvarGetUbLocal(bdchgvar);
605 
606  SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ": var <%s>, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
607  SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset, divecontext), maxnlpiterations,
608  SCIPvarGetName(bdchgvar),
609  lblocal, ublocal,
610  bdchgdir == SCIP_BRANCHDIR_DOWNWARDS ? lblocal : bdchgvalue,
611  bdchgdir == SCIP_BRANCHDIR_UPWARDS ? ublocal : bdchgvalue);
612 
613  infeasbdchange = FALSE;
614  /* tighten the lower and/or upper bound depending on the bound change type */
615  switch( bdchgdir )
616  {
618  /* test if bound change is possible, otherwise propagation might have deduced the same
619  * bound already or numerical troubles might have occurred */
620  if( SCIPisFeasLE(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) )
621  infeasbdchange = TRUE;
622  else
623  {
624  /* round variable up */
625  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
626  }
627  break;
629  /* test if bound change is possible, otherwise propagation might have deduced the same
630  * bound already or numerical troubles might have occurred */
631  if( SCIPisFeasGE(scip, bdchgvalue, ublocal) || SCIPisFeasLT(scip, bdchgvalue, lblocal) )
632  infeasbdchange = TRUE;
633  else
634  {
635  /* round variable down */
636  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
637  }
638  break;
640  /* test if bound change is possible, otherwise propagation might have deduced the same
641  * bound already or numerical troubles might have occurred */
642  if( SCIPisFeasLT(scip, bdchgvalue, lblocal) || SCIPisFeasGT(scip, bdchgvalue, ublocal) ||
643  (SCIPisFeasEQ(scip, lblocal, ublocal) && nbdchanges < 2) )
644  infeasbdchange = TRUE;
645  else
646  {
647  /* fix variable to the bound change value */
648  if( SCIPisFeasLT(scip, lblocal, bdchgvalue) )
649  {
650  SCIP_CALL( SCIPchgVarLbProbing(scip, bdchgvar, bdchgvalue) );
651  }
652  if( SCIPisFeasGT(scip, ublocal, bdchgvalue) )
653  {
654  SCIP_CALL( SCIPchgVarUbProbing(scip, bdchgvar, bdchgvalue) );
655  }
656  }
657  break;
658  case SCIP_BRANCHDIR_AUTO:
659  default:
660  SCIPerrorMessage("Error: Unsupported bound change direction <%d> specified for diving, aborting\n",bdchgdirs[d]);
661  SCIPABORT();
662  return SCIP_INVALIDDATA; /*lint !e527*/
663  }
664  /* if the variable domain has been shrunk in the meantime, numerical troubles may have
665  * occured or variable was fixed by propagation while backtracking => Abort diving!
666  */
667  if( infeasbdchange )
668  {
669  SCIPdebugMsg(scip, "\nSelected variable <%s> domain already [%g,%g] as least as tight as desired bound change, diving aborted \n",
670  SCIPvarGetName(bdchgvar), SCIPvarGetLbLocal(bdchgvar), SCIPvarGetUbLocal(bdchgvar));
671  cutoff = TRUE;
672  break;
673  }
674  }
675  /* break loop immediately if we detected a cutoff */
676  if( cutoff )
677  break;
678 
679  /* apply domain propagation */
680  localdomreds = 0;
681  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &localdomreds) );
682 
683  /* add the number of bound changes we applied by ourselves after propagation, otherwise the counter would have been reset */
684  localdomreds += nbdchanges;
685 
686  SCIPdebugMsg(scip, "domain reductions: %" SCIP_LONGINT_FORMAT " (total: %" SCIP_LONGINT_FORMAT ")\n",
687  localdomreds, domreds + localdomreds);
688 
689  /* resolve the diving LP if the diving resolve frequency is reached or a sufficient number of intermediate bound changes
690  * was reached
691  */
692  if( ! cutoff
693  && ((lpsolvefreq > 0 && ((SCIPgetProbingDepth(scip) - lastlpdepth) % lpsolvefreq) == 0)
694  || (domreds + localdomreds > SCIPdivesetGetLPResolveDomChgQuot(diveset) * SCIPgetNVars(scip))
695  || (onlylpbranchcands && nviollpcands > (int)(SCIPdivesetGetLPResolveDomChgQuot(diveset) * nlpcands))) )
696  {
697  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, divecontext, &lperror, &cutoff) );
698 
699  /* lp errors lead to early termination */
700  if( lperror )
701  {
702  cutoff = TRUE;
703  break;
704  }
705  }
706 
707  /* perform backtracking if a cutoff was detected */
708  if( cutoff && !backtracked && SCIPdivesetUseBacktrack(diveset) )
709  {
710  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
712  ++totalnbacktracks;
713  backtracked = TRUE;
714  backtrack = TRUE;
715  cutoff = FALSE;
716  }
717  else
718  backtrack = FALSE;
719  }
720  while( backtrack );
721 
722  /* we add the domain reductions from the last evaluated node */
723  domreds += localdomreds; /*lint !e771 lint thinks localdomreds has not been initialized */
724 
725  /* store candidate for pseudo cost update and choose next candidate only if no cutoff was detected */
726  if( ! cutoff )
727  {
728  if( nbdchanges == 1 && (bdchgdir == SCIP_BRANCHDIR_UPWARDS || bdchgdir == SCIP_BRANCHDIR_DOWNWARDS) )
729  {
730  ++prevcandsinsertidx;
731  assert(prevcandsinsertidx <= SCIPgetProbingDepth(scip) - lastlpdepth - 1);
732  assert(SCIPgetProbingDepth(scip) > 0);
733  assert(bdchgvar != NULL);
734  assert(bdchgvalue != SCIP_INVALID); /*lint !e777 doesn't like comparing floats for equality */
735 
736  /* extend array in case of a dynamic, domain change based LP resolve strategy */
737  if( prevcandsinsertidx >= previouscandssize )
738  {
739  previouscandssize *= 2;
740  SCIP_CALL( SCIPreallocBufferArray(scip, &previouscands, previouscandssize) );
741  SCIP_CALL( SCIPreallocBufferArray(scip, &previousvals, previouscandssize) );
742  }
743  assert(previouscandssize > prevcandsinsertidx);
744 
745  /* store candidate for pseudo cost update */
746  previouscands[prevcandsinsertidx] = bdchgvar;
747  previousvals[prevcandsinsertidx] = bdchgvalue;
748  }
749 
750  /* choose next candidate variable and resolve the LP if none is found. */
752  {
753  assert(SCIPgetProbingDepth(scip) > lastlpdepth);
754  enfosuccess = FALSE;
755 
756  /* select the next diving action */
757  SCIP_CALL( selectNextDiving(scip, diveset, worksol, onlylpbranchcands, SCIPgetProbingDepth(scip) == lastlpdepth,
758  lpcands, lpcandssol, lpcandsfrac, lpcandsscores, lpcandroundup, &nviollpcands, nlpcands,
759  &enfosuccess, &infeasible) );
760 
761  /* in case of an unsuccesful candidate search, we solve the node LP */
762  if( !enfosuccess )
763  {
764  SCIP_CALL( solveLP(scip, diveset, maxnlpiterations, divecontext, &lperror, &cutoff) );
765 
766  /* check for an LP error and terminate in this case, cutoffs lead to termination anyway */
767  if( lperror )
768  cutoff = TRUE;
769 
770  /* enfosuccess must be set to TRUE for entering the main LP loop again */
771  enfosuccess = TRUE;
772  }
773  }
774  }
775  }
776  while( !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_NOTSOLVED );
777 
778  assert(cutoff || lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_NOTSOLVED);
779 
782 
783  /* check new LP candidates and use the LP Objective gain to update pseudo cost information */
784  if( ! cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
785  {
786  int v;
787  SCIP_Real gain;
788 
789  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
790 
791  SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", SCIPgetLPSolstat(scip), SCIPgetLPObjval(scip), searchbound, nlpcands);
792  /* distribute the gain equally over all variables that we rounded since the last LP */
793  gain = SCIPgetLPObjval(scip) - lastlpobjval;
794  gain = MAX(gain, 0.0);
795  gain /= (1.0 * (SCIPgetProbingDepth(scip) - lastlpdepth));
796 
797  /* loop over previously fixed candidates and share gain improvement */
798  for( v = 0; v <= prevcandsinsertidx; ++v )
799  {
800  SCIP_VAR* cand = previouscands[v];
801  SCIP_Real val = previousvals[v];
802  SCIP_Real solval = SCIPgetSolVal(scip, worksol, cand);
803 
804  /* todo: should the gain be shared with a smaller weight, instead of dividing the gain itself? */
805  /* it may happen that a variable had an integral solution value beforehand, e.g., for indicator variables */
806  if( ! SCIPisZero(scip, val - solval) )
807  {
808  SCIP_CALL( SCIPupdateVarPseudocost(scip, cand, val - solval, gain, 1.0) );
809  }
810  }
811  }
812  else
813  nlpcands = 0;
814  }
815 
816  success = FALSE;
817  /* check if a solution has been found */
818  if( !enfosuccess && !lperror && !cutoff && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
819  {
820  /* create solution from diving LP */
821  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
822  SCIPdebugMsg(scip, "%s found primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
823 
824  /* try to add solution to SCIP */
825  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
826 
827  /* check, if solution was feasible and good enough */
828  if( success )
829  {
830  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
831  *result = SCIP_FOUNDSOL;
832  leafsol = TRUE;
833  }
834  }
835 
836  SCIPupdateDivesetStats(scip, diveset, totalnprobingnodes, totalnbacktracks, SCIPgetNSolsFound(scip) - oldnsolsfound,
837  SCIPgetNBestSolsFound(scip) - oldnbestsolsfound, SCIPgetNConflictConssFound(scip) - oldnconflictsfound, leafsol, divecontext);
838 
839  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") finished %s diveset (%s heur): %d fractionals, dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", objval=%g/%g, lpsolstat=%d, cutoff=%u\n",
840  SCIPgetNNodes(scip), SCIPdivesetGetName(diveset), SCIPheurGetName(heur), nlpcands, SCIPgetProbingDepth(scip), maxdivedepth, SCIPdivesetGetNLPIterations(diveset, divecontext), maxnlpiterations,
841  SCIPretransformObj(scip, SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ? SCIPgetLPObjval(scip) : SCIPinfinity(scip)), SCIPretransformObj(scip, searchbound), SCIPgetLPSolstat(scip), cutoff);
842 
843  TERMINATE:
844  /* end probing mode */
845  SCIP_CALL( SCIPendProbing(scip) );
846 
848 
849  if( onlylpbranchcands )
850  {
851  SCIPfreeBufferArray(scip, &lpcandroundup);
852  SCIPfreeBufferArray(scip, &lpcandsscores);
853  }
854  SCIPfreeBufferArray(scip, &previousvals);
855  SCIPfreeBufferArray(scip, &previouscands);
856 
857  return SCIP_OKAY;
858 }
859 
860 
861 /** creates the rows of the subproblem */
862 static
864  SCIP* scip, /**< original SCIP data structure */
865  SCIP* subscip, /**< SCIP data structure for the subproblem */
866  SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables to the corresponding
867  * target variables */
868  )
869 {
870  SCIP_ROW** rows; /* original scip rows */
871  SCIP_CONS* cons; /* new constraint */
872  SCIP_VAR** consvars; /* new constraint's variables */
873  SCIP_COL** cols; /* original row's columns */
874 
875  SCIP_Real constant; /* constant added to the row */
876  SCIP_Real lhs; /* left hand side of the row */
877  SCIP_Real rhs; /* left right side of the row */
878  SCIP_Real* vals; /* variables' coefficient values of the row */
879 
880  int nrows;
881  int nnonz;
882  int i;
883  int j;
884 
885  /* get the rows and their number */
886  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
887 
888  /* copy all rows to linear constraints */
889  for( i = 0; i < nrows; i++ )
890  {
891  /* ignore rows that are only locally valid */
892  if( SCIProwIsLocal(rows[i]) )
893  continue;
894 
895  /* get the row's data */
896  constant = SCIProwGetConstant(rows[i]);
897  lhs = SCIProwGetLhs(rows[i]) - constant;
898  rhs = SCIProwGetRhs(rows[i]) - constant;
899  vals = SCIProwGetVals(rows[i]);
900  nnonz = SCIProwGetNNonz(rows[i]);
901  cols = SCIProwGetCols(rows[i]);
902 
903  assert(lhs <= rhs);
904 
905  /* allocate memory array to be filled with the corresponding subproblem variables */
906  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
907  for( j = 0; j < nnonz; j++ )
908  consvars[j] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, (SCIPcolGetVar(cols[j])));
909 
910  /* create a new linear constraint and add it to the subproblem */
911  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
912  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
913  SCIP_CALL( SCIPaddCons(subscip, cons) );
914  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
915 
916  /* free temporary memory */
917  SCIPfreeBufferArray(scip, &consvars);
918  }
919 
920  return SCIP_OKAY;
921 }
922 
923 
924 /** get a sub-SCIP copy of the transformed problem */
926  SCIP* sourcescip, /**< source SCIP data structure */
927  SCIP* subscip, /**< sub-SCIP used by the heuristic */
928  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
929  * target variables */
930  const char* suffix, /**< suffix for the problem name */
931  SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
932  SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
933  int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
934  SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
935  SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
936  SCIP_Bool* success, /**< was the copying successful? */
937  SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
938  )
939 {
940  assert(sourcescip != NULL);
941  assert(suffix != NULL);
942  assert(subscip != NULL);
943  assert(varmap != NULL);
944  assert(success != NULL);
945 
946  if( uselprows )
947  {
948  char probname[SCIP_MAXSTRLEN];
949 
950  /* copy all plugins */
952 
953  /* set name to the original problem name and possibly add a suffix */
954  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_%s", SCIPgetProbName(sourcescip), suffix);
955 
956  /* create the subproblem */
957  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
958 
959  /* copy all variables */
960  SCIP_CALL( SCIPcopyVars(sourcescip, subscip, varmap, NULL, fixedvars, fixedvals, nfixedvars, TRUE) );
961 
962  /* copy parameter settings */
963  SCIP_CALL( SCIPcopyParamSettings(sourcescip, subscip) );
964 
965  /* create linear constraints from LP rows of the source problem */
966  SCIP_CALL( createRows(sourcescip, subscip, varmap) );
967  }
968  else
969  {
970  SCIP_CALL( SCIPcopyConsCompression(sourcescip, subscip, varmap, NULL, suffix, fixedvars, fixedvals, nfixedvars,
971  TRUE, FALSE, FALSE, TRUE, valid) );
972 
973  if( copycuts )
974  {
975  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
976  SCIP_CALL( SCIPcopyCuts(sourcescip, subscip, varmap, NULL, TRUE, NULL) );
977  }
978  }
979 
980  *success = TRUE;
981 
982  return SCIP_OKAY;
983 }
984 
985 /** adds a trust region neighborhood constraint to the @p targetscip
986  *
987  * a trust region constraint measures the deviation from the current incumbent solution \f$x^*\f$ by an auxiliary
988  * continuous variable \f$v \geq 0\f$:
989  * \f[
990  * \sum\limits_{j\in B} |x_j^* - x_j| = v
991  * \f]
992  * Only binary variables are taken into account. The deviation is penalized in the objective function using
993  * a positive \p violpenalty.
994  *
995  * @note: the trust region constraint creates an auxiliary variable to penalize the deviation from
996  * the current incumbent solution. This variable can afterwards be accessed using SCIPfindVar() by its name
997  * 'trustregion_violationvar'
998  */
1000  SCIP* sourcescip, /**< the data structure for the main SCIP instance */
1001  SCIP* targetscip, /**< SCIP data structure of the subproblem */
1002  SCIP_VAR** subvars, /**< variables of the subproblem, NULL entries are ignored */
1003  SCIP_Real violpenalty /**< the penalty for violating the trust region */
1004  )
1005 {
1006  SCIP_VAR* violvar;
1007  SCIP_CONS* trustregioncons;
1008  SCIP_VAR** consvars;
1009  SCIP_VAR** vars;
1010  SCIP_SOL* bestsol;
1011 
1012  int nvars;
1013  int nbinvars;
1014  int nconsvars;
1015  int i;
1016  SCIP_Real rhs;
1017  SCIP_Real* consvals;
1018  char name[SCIP_MAXSTRLEN];
1019 
1020  /* get the data of the variables and the best solution */
1021  SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
1022  bestsol = SCIPgetBestSol(sourcescip);
1023  assert(bestsol != NULL);
1024  /* otherwise, this neighborhood would not be active in the first place */
1025  assert(nbinvars > 0);
1026 
1027  /* memory allocation */
1028  SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvars, nbinvars + 1) );
1029  SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars + 1) );
1030  nconsvars = 0;
1031 
1032  /* set initial left and right hand sides of trust region constraint */
1033  rhs = 0.0;
1034 
1035  /* create the distance (to incumbent) function of the binary variables */
1036  for( i = 0; i < nbinvars; i++ )
1037  {
1038  SCIP_Real solval;
1039 
1040  if( subvars[i] == NULL )
1041  continue;
1042 
1043  solval = SCIPgetSolVal(sourcescip, bestsol, vars[i]);
1044  assert( SCIPisFeasIntegral(sourcescip,solval) );
1045 
1046  /* is variable i part of the binary support of bestsol? */
1047  if( SCIPisFeasEQ(sourcescip, solval, 1.0) )
1048  {
1049  consvals[nconsvars] = -1.0;
1050  rhs -= 1.0;
1051  }
1052  else
1053  consvals[nconsvars] = 1.0;
1054  consvars[nconsvars] = subvars[i];
1055  assert(SCIPvarGetType(consvars[nconsvars]) == SCIP_VARTYPE_BINARY);
1056  ++nconsvars;
1057  }
1058 
1059  /* adding the violation variable */
1060  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_trustregionviolvar", SCIPgetProbName(sourcescip));
1061  SCIP_CALL( SCIPcreateVarBasic(targetscip, &violvar, name, 0.0, SCIPinfinity(targetscip), violpenalty, SCIP_VARTYPE_CONTINUOUS) );
1062  SCIP_CALL( SCIPaddVar(targetscip, violvar) );
1063  consvars[nconsvars] = violvar;
1064  consvals[nconsvars] = -1.0;
1065  ++nconsvars;
1066 
1067  /* creates trustregion constraint and adds it to subscip */
1068  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_trustregioncons", SCIPgetProbName(sourcescip));
1069 
1070  SCIP_CALL( SCIPcreateConsLinear(targetscip, &trustregioncons, name, nconsvars, consvars, consvals,
1071  rhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
1072  SCIP_CALL( SCIPaddCons(targetscip, trustregioncons) );
1073  SCIP_CALL( SCIPreleaseCons(targetscip, &trustregioncons) );
1074 
1075  /* releasing the violation variable */
1076  SCIP_CALL( SCIPreleaseVar(targetscip, &violvar) );
1077 
1078  /* free local memory */
1079  SCIPfreeBufferArray(sourcescip, &consvals);
1080  SCIPfreeBufferArray(sourcescip, &consvars);
1081 
1082  return SCIP_OKAY;
1083 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2090
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1026
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define SCIP_MAXSTRLEN
Definition: def.h:302
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmap)
Definition: heuristics.c:863
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:700
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:117
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17216
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:684
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17979
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:661
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:587
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17354
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:483
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:677
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
Definition: cons_sos1.c:10816
constraint handler for indicator constraints
int SCIPgetMaxDepth(SCIP *scip)
void SCIPgetDiveBoundChangeData(SCIP *scip, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1874
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17295
#define FALSE
Definition: def.h:96
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10788
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10714
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:461
methods commonly used by primal heuristics
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
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:194
static SCIP_Longint getDivesetIterLimit(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:175
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:453
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3211
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:2559
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:218
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:741
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:653
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1075
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8780
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
void SCIPclearDiveBoundChanges(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1450
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2778
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
Definition: heuristics.c:999
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:639
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: heuristics.c:46
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17404
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPcopyVars(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global)
Definition: scip_copy.c:1178
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2125
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:692
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17264
#define NULL
Definition: lpi_spx1.cpp:164
static SCIP_RETCODE selectNextDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_Bool onlylpbranchcands, SCIP_Bool storelpcandscores, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Real *lpcandsscores, SCIP_Bool *lpcandroundup, int *nviollpcands, int nlpcands, SCIP_Bool *enfosuccess, SCIP_Bool *infeasible)
Definition: heuristics.c:90
#define SCIP_CALL(x)
Definition: def.h:394
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:819
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17305
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:729
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17241
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2742
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
void SCIPupdateDivesetStats(SCIP *scip, SCIP_DIVESET *diveset, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Longint nconflictsfound, SCIP_Bool leavewassol, SCIP_DIVECONTEXT divecontext)
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
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17251
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:669
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2455
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
#define MAX(x, y)
Definition: tclique_def.h:92
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8741
#define MINLPITER
Definition: heuristics.c:41
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1444
Constraint handler for linear constraints in their most general form, .
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
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
SCIP_Real SCIPgetAvgDualbound(SCIP *scip)
#define SCIP_REAL_MIN
Definition: def.h:188
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:432
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17261
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1570
void SCIPupdateDivesetLPStats(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:72
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2313
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17045
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1676
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1576
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:925
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
#define SCIP_Real
Definition: def.h:186
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:703
constraint handler for SOS type 1 constraints
SCIP_RETCODE SCIPmakeIndicatorsFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed)
#define SCIP_INVALID
Definition: def.h:206
#define SCIP_Longint
Definition: def.h:171
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1190
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17429
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17989
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
public methods for primal heuristics
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:60
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPABORT()
Definition: def.h:366
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
default SCIP plugins
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3455
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3444
int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition: heur.c:708
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:443