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