Scippy

SCIP

Solving Constraint Integer Programs

heur_oneopt.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_oneopt.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief improvement heuristic that alters single variable values
19  * @author Timo Berthold
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "blockmemshell/memory.h"
25 #include "scip/heur_oneopt.h"
26 #include "scip/pub_heur.h"
27 #include "scip/pub_lp.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_misc_sort.h"
31 #include "scip/pub_sol.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_copy.h"
34 #include "scip/scip_general.h"
35 #include "scip/scip_heur.h"
36 #include "scip/scip_lp.h"
37 #include "scip/scip_mem.h"
38 #include "scip/scip_message.h"
39 #include "scip/scip_numerics.h"
40 #include "scip/scip_param.h"
41 #include "scip/scip_prob.h"
42 #include "scip/scip_sol.h"
43 #include "scip/scip_solve.h"
44 #include "scip/scip_solvingstats.h"
45 #include "scip/scip_tree.h"
46 #include <string.h>
47 
48 /* @note If the heuristic runs in the root node, the timing is changed to (SCIP_HEURTIMING_DURINGLPLOOP |
49  * SCIP_HEURTIMING_BEFORENODE), see SCIP_DECL_HEURINITSOL callback.
50  */
51 
52 #define HEUR_NAME "oneopt"
53 #define HEUR_DESC "1-opt heuristic which tries to improve setting of single integer variables"
54 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE
55 #define HEUR_PRIORITY -20000
56 #define HEUR_FREQ 1
57 #define HEUR_FREQOFS 0
58 #define HEUR_MAXDEPTH -1
59 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_AFTERNODE
60 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
61 
62 #define DEFAULT_WEIGHTEDOBJ TRUE /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */
63 #define DEFAULT_DURINGROOT TRUE /**< should the heuristic be called before and during the root node? */
64 #define DEFAULT_BEFOREPRESOL FALSE /**< should the heuristic be called before presolving */
65 #define DEFAULT_FORCELPCONSTRUCTION FALSE /**< should the construction of the LP be forced even if LP solving is deactivated? */
66 #define DEFAULT_USELOOP TRUE /**< should the heuristic continue to run as long as improvements are found? */
67 /*
68  * Data structures
69  */
70 
71 /** primal heuristic data */
72 struct SCIP_HeurData
73 {
74  int lastsolindex; /**< index of the last solution for which oneopt was performed */
75  SCIP_Bool weightedobj; /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */
76  SCIP_Bool duringroot; /**< should the heuristic be called before and during the root node? */
77  SCIP_Bool forcelpconstruction;/**< should the construction of the LP be forced even if LP solving is deactivated? */
78  SCIP_Bool beforepresol; /**< should the heuristic be called before presolving */
79  SCIP_Bool useloop; /**< should the heuristic continue to run as long as improvements are found? */
80 };
81 
82 
83 /*
84  * Local methods
85  */
86 
87 /** compute value by which the solution of variable @p var can be shifted */
88 static
90  SCIP* scip, /**< SCIP data structure */
91  SCIP_VAR* var, /**< variable that should be shifted */
92  SCIP_Real solval, /**< current solution value */
93  SCIP_Real* activities /**< LP row activities */
94  )
95 {
96  SCIP_Real lb;
97  SCIP_Real ub;
98  SCIP_Real obj;
99  SCIP_Real shiftval;
100 
101  SCIP_COL* col;
102  SCIP_ROW** colrows;
103  SCIP_Real* colvals;
104  SCIP_Bool shiftdown;
105 
106  int ncolrows;
107  int i;
108 
109  /* get variable's solution value, global bounds and objective coefficient */
110  lb = SCIPvarGetLbGlobal(var);
111  ub = SCIPvarGetUbGlobal(var);
112  obj = SCIPvarGetObj(var);
113  shiftdown = TRUE;
114 
115  /* determine shifting direction and maximal possible shifting w.r.t. corresponding bound */
116  if( obj > 0.0 && SCIPisFeasGE(scip, solval - 1.0, lb) )
117  shiftval = SCIPfeasFloor(scip, solval - lb);
118  else if( obj < 0.0 && SCIPisFeasLE(scip, solval + 1.0, ub) )
119  {
120  shiftval = SCIPfeasFloor(scip, ub - solval);
121  shiftdown = FALSE;
122  }
123  else
124  return 0.0;
125 
126  SCIPdebugMsg(scip, "Try to shift %s variable <%s> with\n", shiftdown ? "down" : "up", SCIPvarGetName(var) );
127  SCIPdebugMsg(scip, " lb:<%g> <= val:<%g> <= ub:<%g> and obj:<%g> by at most: <%g>\n", lb, solval, ub, obj, shiftval);
128 
129  /* get data of LP column */
130  col = SCIPvarGetCol(var);
131  colrows = SCIPcolGetRows(col);
132  colvals = SCIPcolGetVals(col);
133  ncolrows = SCIPcolGetNLPNonz(col);
134 
135  assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
136 
137  /* find minimal shift value, st. all rows stay valid */
138  for( i = 0; i < ncolrows && shiftval > 0.0; ++i )
139  {
140  SCIP_ROW* row;
141  int rowpos;
142 
143  row = colrows[i];
144  rowpos = SCIProwGetLPPos(row);
145  assert(-1 <= rowpos && rowpos < SCIPgetNLPRows(scip) );
146 
147  /* only global rows need to be valid */
148  if( rowpos >= 0 && !SCIProwIsLocal(row) )
149  {
150  SCIP_Real shiftvalrow;
151 
152  assert(SCIProwIsInLP(row));
153 
154  if( shiftdown == (colvals[i] > 0) )
155  shiftvalrow = SCIPfeasFloor(scip, (activities[rowpos] - SCIProwGetLhs(row)) / ABS(colvals[i]));
156  else
157  shiftvalrow = SCIPfeasFloor(scip, (SCIProwGetRhs(row) - activities[rowpos]) / ABS(colvals[i]));
158 #ifdef SCIP_DEBUG
159  if( shiftvalrow < shiftval )
160  {
161  SCIPdebugMsg(scip, " -> The shift value had to be reduced to <%g>, because of row <%s>.\n",
162  shiftvalrow, SCIProwGetName(row));
163  SCIPdebugMsg(scip, " lhs:<%g> <= act:<%g> <= rhs:<%g>, colval:<%g>\n",
164  SCIProwGetLhs(row), activities[rowpos], SCIProwGetRhs(row), colvals[i]);
165  }
166 #endif
167  shiftval = MIN(shiftval, shiftvalrow);
168  /* shiftvalrow might be negative, if we detected infeasibility -> make sure that shiftval is >= 0 */
169  shiftval = MAX(shiftval, 0.0);
170  }
171  }
172  if( shiftdown )
173  shiftval *= -1.0;
174 
175  /* we must not shift variables to infinity */
176  if( SCIPisInfinity(scip, solval + shiftval) )
177  shiftval = 0.0;
178 
179  return shiftval;
180 }
181 
182 
183 /** update row activities after a variable's solution value changed */
184 static
186  SCIP* scip, /**< SCIP data structure */
187  SCIP_Real* activities, /**< LP row activities */
188  SCIP_VAR* var, /**< variable that has been changed */
189  SCIP_Real shiftval /**< value that is added to variable */
190  )
191 {
192  SCIP_Real* colvals;
193  SCIP_ROW** colrows;
194  SCIP_COL* col;
195 
196  int ncolrows;
197  int i;
198 
199  assert(activities != NULL);
200 
201  /* get data of column associated to variable */
202  col = SCIPvarGetCol(var);
203  colrows = SCIPcolGetRows(col);
204  colvals = SCIPcolGetVals(col);
205  ncolrows = SCIPcolGetNLPNonz(col);
206  assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
207 
208  /* enumerate all rows with nonzero entry in this column */
209  for( i = 0; i < ncolrows; ++i )
210  {
211  SCIP_ROW* row;
212  int rowpos;
213 
214  row = colrows[i];
215  rowpos = SCIProwGetLPPos(row);
216  assert(-1 <= rowpos && rowpos < SCIPgetNLPRows(scip) );
217 
218  /* update row activity, only regard global rows in the LP */
219  if( rowpos >= 0 && !SCIProwIsLocal(row) )
220  {
221  activities[rowpos] += shiftval * colvals[i];
222 
223  if( SCIPisInfinity(scip, activities[rowpos]) )
224  activities[rowpos] = SCIPinfinity(scip);
225  else if( SCIPisInfinity(scip, -activities[rowpos]) )
226  activities[rowpos] = -SCIPinfinity(scip);
227  }
228  }
229 
230  return SCIP_OKAY;
231 }
232 
233 /** setup and solve oneopt sub-SCIP */
234 static
236  SCIP* scip, /**< SCIP data structure */
237  SCIP* subscip, /**< sub-SCIP data structure */
238  SCIP_HEUR* heur, /**< oneopt heuristic */
239  SCIP_VAR** vars, /**< SCIP variables */
240  SCIP_VAR** subvars, /**< subproblem's variables */
241  SCIP_SOL* bestsol, /**< incumbent solution */
242  SCIP_RESULT* result, /**< pointer to store the result */
243  SCIP_Bool* valid /**< pointer to store the valid value */
244  )
245 {
246  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
247  SCIP_SOL* startsol;
248  int nvars; /* number of original problem's variables */
249  int i;
250 
251  assert(scip != NULL);
252  assert(subscip != NULL);
253  assert(heur != NULL);
254 
255  nvars = SCIPgetNVars(scip);
256 
257  /* create the variable mapping hash map */
258  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
259 
260  /* copy complete SCIP instance */
261  *valid = FALSE;
262  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "oneopt", TRUE, FALSE, FALSE, TRUE, valid) );
263  SCIP_CALL( SCIPtransformProb(subscip) );
264 
265  /* get variable image and create start solution for the subproblem */
266  SCIP_CALL( SCIPcreateOrigSol(subscip, &startsol, NULL) );
267  for( i = 0; i < nvars; i++ )
268  {
269  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
270  if( subvars[i] != NULL )
271  SCIP_CALL( SCIPsetSolVal(subscip, startsol, subvars[i], SCIPgetSolVal(scip, bestsol, vars[i])) );
272  }
273 
274  /* try to add new solution to sub-SCIP and free it immediately */
275  *valid = FALSE;
276  SCIP_CALL( SCIPtrySolFree(subscip, &startsol, FALSE, FALSE, FALSE, FALSE, FALSE, valid) );
277  SCIPhashmapFree(&varmapfw);
278 
279  /* deactivate basically everything except oneopt in the sub-SCIP */
283 
284  /* set limits for the subproblem */
285  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
286  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
287 
288  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
289 
290 #ifdef SCIP_DEBUG
291  /* for debugging, enable full output */
292  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
293  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
294 #else
295  /* disable statistic timing inside sub SCIP and output to console */
296  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
297  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
298 #endif
299 
300  /* if necessary, some of the parameters have to be unfixed first */
301  if( SCIPisParamFixed(subscip, "lp/solvefreq") )
302  {
303  SCIPwarningMessage(scip, "unfixing parameter lp/solvefreq in subscip of oneopt heuristic\n");
304  SCIP_CALL( SCIPunfixParam(subscip, "lp/solvefreq") );
305  }
306  SCIP_CALL( SCIPsetIntParam(subscip, "lp/solvefreq", -1) );
307 
308  if( SCIPisParamFixed(subscip, "heuristics/oneopt/freq") )
309  {
310  SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/freq in subscip of oneopt heuristic\n");
311  SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/freq") );
312  }
313  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) );
314 
315  if( SCIPisParamFixed(subscip, "heuristics/oneopt/forcelpconstruction") )
316  {
317  SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/forcelpconstruction in subscip of oneopt heuristic\n");
318  SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/forcelpconstruction") );
319  }
320  SCIP_CALL( SCIPsetBoolParam(subscip, "heuristics/oneopt/forcelpconstruction", TRUE) );
321 
322  /* avoid recursive call, which would lead to an endless loop */
323  if( SCIPisParamFixed(subscip, "heuristics/oneopt/beforepresol") )
324  {
325  SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/beforepresol in subscip of oneopt heuristic\n");
326  SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/beforepresol") );
327  }
328  SCIP_CALL( SCIPsetBoolParam(subscip, "heuristics/oneopt/beforepresol", FALSE) );
329 
330  /* speed up sub-SCIP by not checking dual LP feasibility */
331  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
332 
333  if( *valid )
334  {
335  /* errors in solving the subproblem should not kill the overall solving process;
336  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
337  */
338  SCIP_CALL_ABORT( SCIPsolve(subscip) );
339 
340 #ifdef SCIP_DEBUG
341  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
342 #endif
343 
344  /* check, whether a solution was found;
345  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
346  */
347  SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, valid, NULL) );
348  if( *valid )
349  *result = SCIP_FOUNDSOL;
350  }
351 
352  return SCIP_OKAY;
353 }
354 
355 /*
356  * Callback methods of primal heuristic
357  */
358 
359 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
360 static
361 SCIP_DECL_HEURCOPY(heurCopyOneopt)
362 { /*lint --e{715}*/
363  assert(scip != NULL);
364  assert(heur != NULL);
365  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
366 
367  /* call inclusion method of primal heuristic */
369 
370  return SCIP_OKAY;
371 }
372 
373 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
374 static
375 SCIP_DECL_HEURFREE(heurFreeOneopt)
376 { /*lint --e{715}*/
377  SCIP_HEURDATA* heurdata;
378 
379  assert(heur != NULL);
380  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
381  assert(scip != NULL);
382 
383  /* free heuristic data */
384  heurdata = SCIPheurGetData(heur);
385  assert(heurdata != NULL);
386  SCIPfreeBlockMemory(scip, &heurdata);
387  SCIPheurSetData(heur, NULL);
388 
389  return SCIP_OKAY;
390 }
391 
392 
393 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
394 static
395 SCIP_DECL_HEURINITSOL(heurInitsolOneopt)
396 {
397  SCIP_HEURDATA* heurdata;
398 
399  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
400 
401  /* create heuristic data */
402  heurdata = SCIPheurGetData(heur);
403  assert(heurdata != NULL);
404 
405  /* if the heuristic is called at the root node, we may want to be called during the cut-and-price loop and even before the first LP solve */
406  if( heurdata->duringroot && SCIPheurGetFreqofs(heur) == 0 )
408 
409  return SCIP_OKAY;
410 }
411 
412 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
413 static
414 SCIP_DECL_HEUREXITSOL(heurExitsolOneopt)
415 {
416  assert(heur != NULL);
417  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
418 
419  /* reset the timing mask to its default value */
421 
422  return SCIP_OKAY;
423 }
424 
425 /** initialization method of primal heuristic (called after problem was transformed) */
426 static
427 SCIP_DECL_HEURINIT(heurInitOneopt)
428 { /*lint --e{715}*/
429  SCIP_HEURDATA* heurdata;
430 
431  assert(heur != NULL);
432  assert(scip != NULL);
433 
434  /* get heuristic data */
435  heurdata = SCIPheurGetData(heur);
436  assert(heurdata != NULL);
437 
438  /* initialize last solution index */
439  heurdata->lastsolindex = -1;
440 
441  return SCIP_OKAY;
442 }
443 
444 /** execution method of primal heuristic */
445 static
446 SCIP_DECL_HEUREXEC(heurExecOneopt)
447 { /*lint --e{715}*/
448  SCIP_HEURDATA* heurdata;
449  SCIP_SOL* bestsol; /* incumbent solution */
450  SCIP_SOL* worksol; /* heuristic's working solution */
451  SCIP_VAR** vars; /* SCIP variables */
452  SCIP_VAR** shiftcands; /* shiftable variables */
453  SCIP_ROW** lprows; /* SCIP LP rows */
454  SCIP_Real* activities; /* row activities for working solution */
455  SCIP_Real* shiftvals;
456  SCIP_Bool shifted;
457 
458  SCIP_RETCODE retcode;
459 
460  SCIP_Real lb;
461  SCIP_Real ub;
462  SCIP_Bool localrows;
463  SCIP_Bool valid;
464  int nchgbound;
465  int nbinvars;
466  int nintvars;
467  int nvars;
468  int nlprows;
469  int i;
470  int nshiftcands;
471  int shiftcandssize;
472  int nsuccessfulshifts;
473  int niterations;
474 
475  assert(heur != NULL);
476  assert(scip != NULL);
477  assert(result != NULL);
478 
479  /* get heuristic's data */
480  heurdata = SCIPheurGetData(heur);
481  assert(heurdata != NULL);
482 
483  *result = SCIP_DELAYED;
484 
485  /* we only want to process each solution once */
486  bestsol = SCIPgetBestSol(scip);
487  if( bestsol == NULL || heurdata->lastsolindex == SCIPsolGetIndex(bestsol) )
488  return SCIP_OKAY;
489 
490  /* reset the timing mask to its default value (at the root node it could be different) */
491  if( SCIPgetNNodes(scip) > 1 )
493 
494  /* get problem variables */
495  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
496  nintvars += nbinvars;
497 
498  /* do not run if there are no discrete variables */
499  if( nintvars == 0 )
500  {
501  *result = SCIP_DIDNOTRUN;
502  return SCIP_OKAY;
503  }
504 
505  if( heurtiming == SCIP_HEURTIMING_BEFOREPRESOL )
506  {
507  SCIP* subscip; /* the subproblem created by oneopt */
508  SCIP_VAR** subvars; /* subproblem's variables */
509 
510  SCIP_Bool success;
511 
512  if( !heurdata->beforepresol )
513  return SCIP_OKAY;
514 
515  /* check whether there is enough time and memory left */
516  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
517 
518  if( !success )
519  return SCIP_OKAY;
520 
521  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
522 
523  /* initialize the subproblem */
524  SCIP_CALL( SCIPcreate(&subscip) );
525 
526  /* setup and solve the subproblem and catch the return code */
527  retcode = setupAndSolveSubscipOneopt(scip, subscip, heur, vars, subvars, bestsol, result, &valid);
528 
529  /* free the subscip in any case */
530  SCIP_CALL( SCIPfree(&subscip) );
531  SCIP_CALL( retcode );
532 
533  SCIPfreeBufferArray(scip, &subvars);
534 
535  return SCIP_OKAY;
536  }
537 
538  /* we can only work on solutions valid in the transformed space */
539  if( SCIPsolIsOriginal(bestsol) )
540  return SCIP_OKAY;
541 
542  if( heurtiming == SCIP_HEURTIMING_BEFORENODE && (SCIPhasCurrentNodeLP(scip) || heurdata->forcelpconstruction) )
543  {
544  SCIP_Bool cutoff;
545 
546  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
547 
548  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
549  if( cutoff )
550  {
552  return SCIP_OKAY;
553  }
554 
556 
557  /* get problem variables again, SCIPconstructLP() might have added new variables */
558  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
559  nintvars += nbinvars;
560  }
561 
562  /* we need an LP */
563  if( SCIPgetNLPRows(scip) == 0 )
564  return SCIP_OKAY;
565 
566  *result = SCIP_DIDNOTFIND;
567 
568  heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
569  SCIP_CALL( SCIPcreateSolCopy(scip, &worksol, bestsol) );
570  SCIPsolSetHeur(worksol,heur);
571 
572  SCIPdebugMsg(scip, "Starting bound adjustment in 1-opt heuristic\n");
573 
574  nchgbound = 0;
575  /* change solution values due to possible global bound changes first */
576  for( i = nvars - 1; i >= 0; --i )
577  {
578  SCIP_VAR* var;
579  SCIP_Real solval;
580 
581  var = vars[i];
582  lb = SCIPvarGetLbGlobal(var);
583  ub = SCIPvarGetUbGlobal(var);
584 
585  solval = SCIPgetSolVal(scip, worksol, var);
586  /* old solution value is smaller than the actual lower bound */
587  if( SCIPisFeasLT(scip, solval, lb) )
588  {
589  /* set the solution value to the global lower bound */
590  SCIP_CALL( SCIPsetSolVal(scip, worksol, var, lb) );
591  ++nchgbound;
592  SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to lb %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, lb);
593  }
594  /* old solution value is greater than the actual upper bound */
595  else if( SCIPisFeasGT(scip, solval, SCIPvarGetUbGlobal(var)) )
596  {
597  /* set the solution value to the global upper bound */
598  SCIP_CALL( SCIPsetSolVal(scip, worksol, var, ub) );
599  ++nchgbound;
600  SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to ub %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, ub);
601  }
602  }
603 
604  SCIPdebugMsg(scip, "number of bound changes (due to global bounds) = %d\n", nchgbound);
605 
606  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
607  SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
608 
609  localrows = FALSE;
610  valid = TRUE;
611 
612  /* initialize LP row activities */
613  for( i = 0; i < nlprows; ++i )
614  {
615  SCIP_ROW* row;
616 
617  row = lprows[i];
618  assert(SCIProwGetLPPos(row) == i);
619 
620  if( !SCIProwIsLocal(row) )
621  {
622  activities[i] = SCIPgetRowSolActivity(scip, row, worksol);
623  SCIPdebugMsg(scip, "Row <%s> has activity %g\n", SCIProwGetName(row), activities[i]);
624  if( SCIPisFeasLT(scip, activities[i], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, activities[i], SCIProwGetRhs(row)) )
625  {
626  valid = FALSE;
628  SCIPdebugMsg(scip, "row <%s> activity %g violates bounds, lhs = %g, rhs = %g\n", SCIProwGetName(row), activities[i], SCIProwGetLhs(row), SCIProwGetRhs(row));
629  break;
630  }
631  }
632  else
633  localrows = TRUE;
634  }
635 
636  if( !valid )
637  {
638  /** @todo try to correct lp rows */
639  SCIPdebugMsg(scip, "Some global bound changes were not valid in lp rows.\n");
640 
641  SCIPfreeBufferArray(scip, &activities);
642  SCIP_CALL( SCIPfreeSol(scip, &worksol) );
643 
644  return SCIP_OKAY;
645  }
646 
647  /* allocate buffer storage for possible shift candidates */
648  shiftcandssize = 8;
649  SCIP_CALL( SCIPallocBufferArray(scip, &shiftcands, shiftcandssize) );
650  SCIP_CALL( SCIPallocBufferArray(scip, &shiftvals, shiftcandssize) );
651  nsuccessfulshifts = 0;
652  niterations = 0;
653  do
654  {
655  /* initialize data */
656  shifted = FALSE;
657  nshiftcands = 0;
658  ++niterations;
659  SCIPdebugMsg(scip, "Starting 1-opt heuristic iteration #%d\n", niterations);
660 
661  /* enumerate all integer variables and find out which of them are shiftable */
662  /* @todo if useloop=TRUE store for each variable which constraint blocked it and only iterate over those variables
663  * in the following rounds for which the constraint slack was increased by previous shifts
664  */
665  for( i = 0; i < nintvars; i++ )
666  {
667  if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN )
668  {
669  SCIP_Real shiftval;
670  SCIP_Real solval;
671 
672  /* find out whether the variable can be shifted */
673  solval = SCIPgetSolVal(scip, worksol, vars[i]);
674  shiftval = calcShiftVal(scip, vars[i], solval, activities);
675 
676  /* insert the variable into the list of shifting candidates */
677  if( !SCIPisFeasZero(scip, shiftval) )
678  {
679  SCIPdebugMsg(scip, " -> Variable <%s> can be shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval);
680 
681  if( nshiftcands == shiftcandssize)
682  {
683  shiftcandssize *= 8;
684  SCIP_CALL( SCIPreallocBufferArray(scip, &shiftcands, shiftcandssize) );
685  SCIP_CALL( SCIPreallocBufferArray(scip, &shiftvals, shiftcandssize) );
686  }
687  shiftcands[nshiftcands] = vars[i];
688  shiftvals[nshiftcands] = shiftval;
689  nshiftcands++;
690  }
691  }
692  }
693 
694  /* if at least one variable can be shifted, shift variables sorted by their objective */
695  if( nshiftcands > 0 )
696  {
697  SCIP_Real shiftval;
698  SCIP_Real solval;
699  SCIP_VAR* var;
700 
701  /* the case that exactly one variable can be shifted is slightly easier */
702  if( nshiftcands == 1 )
703  {
704  var = shiftcands[0];
705  assert(var != NULL);
706  solval = SCIPgetSolVal(scip, worksol, var);
707  shiftval = shiftvals[0];
708  assert(!SCIPisFeasZero(scip,shiftval));
709  SCIPdebugMsg(scip, " Only one shiftcand found, var <%s>, which is now shifted by<%1.1f> \n",
710  SCIPvarGetName(var), shiftval);
711  SCIP_CALL( SCIPsetSolVal(scip, worksol, var, solval+shiftval) );
712  SCIP_CALL( updateRowActivities(scip, activities, var, shiftval) );
713  ++nsuccessfulshifts;
714  }
715  else
716  {
717  SCIP_Real* objcoeffs;
718 
719  SCIP_CALL( SCIPallocBufferArray(scip, &objcoeffs, nshiftcands) );
720 
721  SCIPdebugMsg(scip, " %d shiftcands found \n", nshiftcands);
722 
723  /* sort the variables by their objective, optionally weighted with the shiftval */
724  if( heurdata->weightedobj )
725  {
726  for( i = 0; i < nshiftcands; ++i )
727  objcoeffs[i] = SCIPvarGetObj(shiftcands[i])*shiftvals[i];
728  }
729  else
730  {
731  for( i = 0; i < nshiftcands; ++i )
732  objcoeffs[i] = SCIPvarGetObj(shiftcands[i]);
733  }
734 
735  /* sort arrays with respect to the first one */
736  SCIPsortRealPtr(objcoeffs, (void**)shiftcands, nshiftcands);
737 
738  /* try to shift each variable -> Activities have to be updated */
739  for( i = 0; i < nshiftcands; ++i )
740  {
741  var = shiftcands[i];
742  assert(var != NULL);
743  solval = SCIPgetSolVal(scip, worksol, var);
744  shiftval = calcShiftVal(scip, var, solval, activities);
745  assert(i > 0 || !SCIPisFeasZero(scip, shiftval));
746  assert(SCIPisFeasGE(scip, solval+shiftval, SCIPvarGetLbGlobal(var)) && SCIPisFeasLE(scip, solval+shiftval, SCIPvarGetUbGlobal(var)));
747 
748  /* update data structures for nonzero shift value */
749  if( ! SCIPisFeasZero(scip, shiftval) )
750  {
751  SCIPdebugMsg(scip, " -> Variable <%s> is now shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval);
752  SCIP_CALL( SCIPsetSolVal(scip, worksol, var, solval+shiftval) );
753  SCIP_CALL( updateRowActivities(scip, activities, var, shiftval) );
754  ++nsuccessfulshifts;
755  }
756  }
757 
758  SCIPfreeBufferArray(scip, &objcoeffs);
759  }
760  shifted = TRUE;
761  }
762  }
763  while( heurdata->useloop && shifted );
764 
765  if( nsuccessfulshifts > 0 )
766  {
767  /* if the problem is a pure IP, try to install the solution, if it is a MIP, solve LP again to set the continuous
768  * variables to the best possible value
769  */
770  if( nvars == nintvars || !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
771  {
772  SCIP_Bool success;
773 
774  /* since we ignore local rows, we cannot guarantee their feasibility and have to set the checklprows flag to
775  * TRUE if local rows are present
776  */
777  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, localrows, &success) );
778 
779  if( success )
780  {
781  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
782  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
783  *result = SCIP_FOUNDSOL;
784  }
785  }
786  else
787  {
788  SCIP_Bool lperror;
789 #ifdef NDEBUG
790  SCIP_RETCODE retstat;
791 #endif
792 
793  SCIPdebugMsg(scip, "shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
794 
795  /* start diving to calculate the LP relaxation */
797 
798  /* set the bounds of the variables: fixed for integers, global bounds for continuous */
799  for( i = 0; i < nvars; ++i )
800  {
801  if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN )
802  {
803  SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], SCIPvarGetLbGlobal(vars[i])) );
804  SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], SCIPvarGetUbGlobal(vars[i])) );
805  }
806  }
807  /* apply this after global bounds to not cause an error with intermediate empty domains */
808  for( i = 0; i < nintvars; ++i )
809  {
810  if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN )
811  {
812  SCIP_Real solval;
813  solval = SCIPgetSolVal(scip, worksol, vars[i]);
814  SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], solval) );
815  SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], solval) );
816  }
817  }
818 
819  /* solve LP */
820  SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
821 
822  /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE, say, rather solve the NLP instead of the LP */
823  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
824  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
825  */
826 #ifdef NDEBUG
827  retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
828  if( retstat != SCIP_OKAY )
829  {
830  SCIPwarningMessage(scip, "Error while solving LP in 1-opt heuristic; LP solve terminated with code <%d>\n",retstat);
831  }
832 #else
833  SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
834 #endif
835 
836  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
837  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
838 
839  /* check if this is a feasible solution */
840  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
841  {
842  SCIP_Bool success;
843 
844  /* copy the current LP solution to the working solution */
845  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
846  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
847 
848  /* check solution for feasibility */
849  if( success )
850  {
851  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
852  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
853  *result = SCIP_FOUNDSOL;
854  }
855  }
856 
857  /* terminate the diving */
859  }
860  }
861 
862  /* heuristic should not rerun on this incumbent because the heuristic loop finishes only after no further
863  * improvements of the incumbent solution are possible
864  */
865  if( heurdata->useloop )
866  heurdata->lastsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
867 
868  SCIPfreeBufferArray(scip, &shiftvals);
869  SCIPfreeBufferArray(scip, &shiftcands);
870  SCIPfreeBufferArray(scip, &activities);
871 
872  SCIP_CALL( SCIPfreeSol(scip, &worksol) );
873 
874  SCIPdebugMsg(scip, "Finished 1-opt heuristic\n");
875 
876  return SCIP_OKAY;
877 }
878 
879 /*
880  * primal heuristic specific interface methods
881  */
882 
883 /** creates the oneopt primal heuristic and includes it in SCIP */
885  SCIP* scip /**< SCIP data structure */
886  )
887 {
888  SCIP_HEURDATA* heurdata;
889  SCIP_HEUR* heur;
890 
891  /* create Oneopt primal heuristic data */
892  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
893 
894  /* include primal heuristic */
895  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
897  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecOneopt, heurdata) );
898 
899  assert(heur != NULL);
900 
901  /* set non-NULL pointers to callback methods */
902  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyOneopt) );
903  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeOneopt) );
904  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolOneopt) );
905  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolOneopt) );
906  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitOneopt) );
907 
908  /* add oneopt primal heuristic parameters */
909  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/weightedobj",
910  "should the objective be weighted with the potential shifting value when sorting the shifting candidates?",
911  &heurdata->weightedobj, TRUE, DEFAULT_WEIGHTEDOBJ, NULL, NULL) );
912 
913  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/duringroot",
914  "should the heuristic be called before and during the root node?",
915  &heurdata->duringroot, TRUE, DEFAULT_DURINGROOT, NULL, NULL) );
916 
917  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/forcelpconstruction",
918  "should the construction of the LP be forced even if LP solving is deactivated?",
919  &heurdata->forcelpconstruction, TRUE, DEFAULT_FORCELPCONSTRUCTION, NULL, NULL) );
920 
921  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/beforepresol",
922  "should the heuristic be called before presolving?",
923  &heurdata->beforepresol, TRUE, DEFAULT_BEFOREPRESOL, NULL, NULL) );
924 
925  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/useloop",
926  "should the heuristic continue to run as long as improvements are found?",
927  &heurdata->useloop, TRUE, DEFAULT_USELOOP, NULL, NULL) );
928 
929  return SCIP_OKAY;
930 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define HEUR_DISPCHAR
Definition: heur_oneopt.c:54
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition: type_timing.h:71
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:557
#define DEFAULT_BEFOREPRESOL
Definition: heur_oneopt.c:64
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17250
#define DEFAULT_WEIGHTEDOBJ
Definition: heur_oneopt.c:62
Improvement heuristic that alters single variable values.
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
public methods for SCIP parameter handling
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:596
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
SCIP_EXPORT SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2521
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17010
#define DEFAULT_DURINGROOT
Definition: heur_oneopt.c:63
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
static SCIP_RETCODE setupAndSolveSubscipOneopt(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_SOL *bestsol, SCIP_RESULT *result, SCIP_Bool *valid)
Definition: heur_oneopt.c:235
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:70
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
public solving methods
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2152
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:357
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1396
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
#define DEFAULT_FORCELPCONSTRUCTION
Definition: heur_oneopt.c:65
#define FALSE
Definition: def.h:73
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17000
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17177
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1018
#define HEUR_DESC
Definition: heur_oneopt.c:53
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2359
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:424
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:916
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3200
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2814
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17131
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17350
static SCIP_Real calcShiftVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real *activities)
Definition: heur_oneopt.c:89
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2618
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3125
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
public methods for querying solving statistics
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17372
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
public methods for the branch-and-bound tree
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:610
SCIP_RETCODE SCIPincludeHeurOneopt(SCIP *scip)
Definition: heur_oneopt.c:884
#define HEUR_MAXDEPTH
Definition: heur_oneopt.c:58
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
SCIP_EXPORT void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2649
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:540
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2182
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
static SCIP_DECL_HEURCOPY(heurCopyOneopt)
Definition: heur_oneopt.c:361
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:16989
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1469
static SCIP_RETCODE updateRowActivities(SCIP *scip, SCIP_Real *activities, SCIP_VAR *var, SCIP_Real shiftval)
Definition: heur_oneopt.c:185
public methods for problem copies
SCIP_EXPORT void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
public methods for primal CIP solutions
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
static SCIP_DECL_HEUREXITSOL(heurExitsolOneopt)
Definition: heur_oneopt.c:414
#define SCIP_HEURTIMING_BEFOREPRESOL
Definition: type_timing.h:86
#define DEFAULT_USELOOP
Definition: heur_oneopt.c:66
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
#define HEUR_FREQ
Definition: heur_oneopt.c:56
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:376
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17376
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
#define HEUR_USESSUBSCIP
Definition: heur_oneopt.c:60
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2231
#define SCIP_Bool
Definition: def.h:70
#define HEUR_PRIORITY
Definition: heur_oneopt.c:55
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:115
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
#define HEUR_FREQOFS
Definition: heur_oneopt.c:57
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17141
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2391
public methods for LP management
SCIP_EXPORT int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
static SCIP_DECL_HEUREXEC(heurExecOneopt)
Definition: heur_oneopt.c:446
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:139
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
public methods for the LP relaxation, rows and columns
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
methods for sorting joint arrays of various types
general public methods
static SCIP_DECL_HEURINIT(heurInitOneopt)
Definition: heur_oneopt.c:427
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1535
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for solutions
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
#define HEUR_TIMING
Definition: heur_oneopt.c:59
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
#define SCIP_Real
Definition: def.h:163
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17200
public methods for message handling
#define HEUR_NAME
Definition: heur_oneopt.c:52
static SCIP_DECL_HEURFREE(heurFreeOneopt)
Definition: heur_oneopt.c:375
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
static SCIP_DECL_HEURINITSOL(heurInitsolOneopt)
Definition: heur_oneopt.c:395
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17151
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
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:3231
public methods for global and local (sub)problems
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2084
memory allocation routines