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