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
98   	SCIP_Real calcShiftVal(
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
212  	SCIP_RETCODE updateRowActivities(
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
261  	SCIP_RETCODE setupAndSolveSubscipOneopt(
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 */
305  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
306  	   SCIP_CALL( SCIPsetHeuristics(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
307  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
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 */
393  	   SCIP_CALL( SCIPincludeHeurOneopt(scip) );
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 )
432  	      SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFORENODE);
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 */
445  	   SCIPheurSetTimingmask(heur, HEUR_TIMING);
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 )
515  	      SCIPheurSetTimingmask(heur, HEUR_TIMING);
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  	      {
574  	         SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
575  	         return SCIP_OKAY;
576  	      }
577  	
578  	      SCIP_CALL( SCIPflushLP(scip) );
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;
649  	            SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
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 */
816  	         SCIP_CALL( SCIPstartDive(scip) );
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 */
878  	         SCIP_CALL( SCIPendDive(scip) );
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 */
904  	SCIP_RETCODE SCIPincludeHeurOneopt(
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,
916  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
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  	}
951