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