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_reoptsols.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  reoptsols primal heuristic
28   	 * @author Jakob Witzig
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_reoptsols.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/scip_heur.h"
38   	#include "scip/scip_mem.h"
39   	#include "scip/scip_message.h"
40   	#include "scip/scip_numerics.h"
41   	#include "scip/scip_param.h"
42   	#include "scip/scip_prob.h"
43   	#include "scip/scip_reopt.h"
44   	#include "scip/scip_sol.h"
45   	#include "scip/scip_solve.h"
46   	#include "scip/scip_solvingstats.h"
47   	#include <string.h>
48   	
49   	
50   	#define HEUR_NAME             "reoptsols"
51   	#define HEUR_DESC             "primal heuristic updating solutions found in a previous optimization round"
52   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_PROP
53   	#define HEUR_PRIORITY         40000
54   	#define HEUR_FREQ             0
55   	#define HEUR_FREQOFS          0
56   	#define HEUR_MAXDEPTH         0
57   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFORENODE
58   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
59   	
60   	
61   	/*
62   	 * Data structures
63   	 */
64   	
65   	/* TODO: fill in the necessary primal heuristic data */
66   	
67   	/** primal heuristic data */
68   	struct SCIP_HeurData
69   	{
70   	   int maxsols;                     /**< maximal number of solution to update per run */
71   	   int maxruns;                     /**< check solutions of the last k runs only */
72   	
73   	   /* statistics */
74   	   int ncheckedsols;                /**< number of updated solutions */
75   	   int nimprovingsols;              /**< number of improving solutions */
76   	};
77   	
78   	
79   	/*
80   	 * Local methods
81   	 */
82   	
83   	
84   	/** creates a new solution for the original problem by copying the solution of the subproblem */
85   	static
86   	SCIP_RETCODE createNewSol(
87   	   SCIP*                 scip,               /**< original SCIP data structure */
88   	   SCIP_HEUR*            heur,               /**< the current heuristic */
89   	   SCIP_SOL*             sol,                /**< solution of the subproblem */
90   	   SCIP_Bool*            success             /**< used to store whether new solution was found or not */
91   	   )
92   	{
93   	   SCIP_VAR** vars;                          /* the original problem's variables */
94   	   int        nvars;                         /* the original problem's number of variables */
95   	   SCIP_Real* solvals;                       /* solution values of the subproblem */
96   	   SCIP_SOL*  newsol;                        /* solution to be created for the original problem */
97   	
98   	   assert(scip != NULL);
99   	
100  	   /* get variables' data */
101  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
102  	
103  	   SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) );
104  	
105  	   /* copy the solution */
106  	   SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, solvals) );
107  	
108  	   /* create new solution for the original problem */
109  	   SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
110  	   SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, solvals) );
111  	
112  	   /* try to add new solution to scip and free it immediately */
113  	   SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
114  	
115  	   SCIPfreeBufferArray(scip, &solvals);
116  	
117  	   return SCIP_OKAY;
118  	}
119  	
120  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
121  	static
122  	SCIP_DECL_HEURCOPY(heurCopyReoptsols)
123  	{  /*lint --e{715}*/
124  	   assert(scip != NULL);
125  	   assert(heur != NULL);
126  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
127  	
128  	   /* call inclusion method of primal heuristic */
129  	   SCIP_CALL( SCIPincludeHeurReoptsols(scip) );
130  	
131  	   return SCIP_OKAY;
132  	}
133  	
134  	/* free data of the heuristic */
135  	static
136  	SCIP_DECL_HEURFREE(heurFreeReoptsols)
137  	{
138  	   SCIP_HEURDATA* heurdata;
139  	
140  	   assert(scip != NULL );
141  	   assert(heur != NULL );
142  	
143  	   heurdata = SCIPheurGetData(heur);
144  	   assert(heurdata != NULL );
145  	
146  	   SCIPfreeBlockMemory(scip, &heurdata);
147  	   SCIPheurSetData(heur, NULL);
148  	
149  	   return SCIP_OKAY;
150  	}
151  	
152  	
153  	/* initialize the heuristic */
154  	static SCIP_DECL_HEURINIT(heurInitReoptsols)
155  	{
156  	   SCIP_HEURDATA* heurdata;
157  	
158  	   assert(scip != NULL );
159  	   assert(heur != NULL );
160  	
161  	   heurdata = SCIPheurGetData(heur);
162  	   assert(heurdata != NULL );
163  	
164  	   heurdata->ncheckedsols = 0;
165  	   heurdata->nimprovingsols = 0;
166  	
167  	   return SCIP_OKAY;
168  	}
169  	
170  	/** execution method of primal heuristic */
171  	static
172  	SCIP_DECL_HEUREXEC(heurExecReoptsols)
173  	{/*lint --e{715}*/
174  	   SCIP_HEURDATA* heurdata;
175  	
176  	   SCIP_SOL** sols;
177  	   SCIP_Real objsimsol;
178  	   SCIP_Bool sepabestsol;
179  	   int allocmem;
180  	   int nchecksols;
181  	   int nsolsadded;
182  	#ifdef SCIP_MORE_DEBUG
183  	   int nsolsaddedrun;
184  	#endif
185  	   int run;
186  	   int max_run;
187  	
188  	   assert(heur != NULL);
189  	   assert(scip != NULL);
190  	
191  	   *result = SCIP_DIDNOTRUN;
192  	
193  	   if( !SCIPisReoptEnabled(scip) )
194  	      return SCIP_OKAY;
195  	
196  	   heurdata = SCIPheurGetData(heur);
197  	   assert(heurdata != NULL);
198  	
199  	   max_run = heurdata->maxruns == -1 ? 0 : MAX(0, SCIPgetNReoptRuns(scip)-1-heurdata->maxruns); /*lint !e666*/
200  	   nchecksols = heurdata->maxsols == -1 ? INT_MAX : heurdata->maxsols;
201  	
202  	   SCIP_CALL( SCIPgetRealParam(scip, "reoptimization/objsimsol", &objsimsol) );
203  	   SCIP_CALL( SCIPgetBoolParam(scip, "reoptimization/sepabestsol", &sepabestsol) );
204  	
205  	   /* allocate a buffer array to store the solutions */
206  	   allocmem = 20;
207  	   SCIP_CALL( SCIPallocBufferArray(scip, &sols, allocmem) );
208  	
209  	   nsolsadded = 0;
210  	
211  	   for( run = SCIPgetNReoptRuns(scip); run > max_run && nchecksols > 0; run-- )
212  	   {
213  	      SCIP_Real sim;
214  	      int nsols;
215  	
216  	#ifdef SCIP_MORE_DEBUG
217  	      nsolsaddedrun = 0;
218  	#endif
219  	      nsols = 0;
220  	
221  	      if( objsimsol == -1 )
222  	         sim = 1;
223  	      else
224  	         sim = SCIPgetReoptSimilarity(scip, run, SCIPgetNReoptRuns(scip)-1);
225  	
226  	      if( sim == SCIP_INVALID ) /*lint !e777*/
227  	         return SCIP_INVALIDRESULT;
228  	
229  	      if( sim >= objsimsol )
230  	      {
231  	         int s;
232  	
233  	         /* get solutions of a specific run */
234  	         SCIP_CALL( SCIPgetReoptSolsRun(scip, run, sols, allocmem, &nsols) );
235  	
236  	         /* check memory and reallocate */
237  	         if( nsols >= allocmem )
238  	         {
239  	            allocmem = nsols;
240  	            SCIP_CALL( SCIPreallocBufferArray(scip, &sols, allocmem) );
241  	
242  	            SCIP_CALL( SCIPgetReoptSolsRun(scip, run, sols, allocmem, &nsols) );
243  	         }
244  	         assert(nsols <= allocmem);
245  	
246  	         /* update the solutions
247  	          * stop, if the maximal number of solutions to be checked is reached
248  	          */
249  	         for( s = 0; s < nsols && nchecksols > 0; s++ )
250  	         {
251  	            SCIP_SOL* sol;
252  	            SCIP_Real objsol;
253  	
254  	            sol = sols[s];
255  	
256  	            SCIP_CALL( SCIPrecomputeSolObj(scip, sol) );
257  	            objsol = SCIPgetSolTransObj(scip, sol);
258  	
259  	            /* we do not want to add solutions with objective value +infinity.
260  	             * moreover, the solution should improve the current primal bound
261  	             */
262  	            if( !SCIPisInfinity(scip, objsol) && !SCIPisInfinity(scip, -objsol)
263  	              && SCIPisFeasLT(scip, objsol, SCIPgetCutoffbound(scip)) )
264  	            {
265  	               SCIP_Bool stored;
266  	
267  	               /* create a new solution */
268  	               SCIP_CALL( createNewSol(scip, heur, sol, &stored) );
269  	
270  	               if( stored )
271  	               {
272  	                  nsolsadded++;
273  	#ifdef SCIP_MORE_DEBUG
274  	                  nsolsaddedrun++;
275  	#endif
276  	                  heurdata->nimprovingsols++;
277  	               }
278  	            }
279  	
280  	            nchecksols--;
281  	            heurdata->ncheckedsols++;
282  	         }
283  	      }
284  	#ifdef SCIP_MORE_DEBUG
285  	         printf(">> heuristic <%s> found %d of %d improving solutions from run %d.\n", HEUR_NAME, nsolsaddedrun, nsols, run);
286  	#endif
287  	      }
288  	
289  	   SCIPdebugMsg(scip, ">> heuristic <%s> found %d improving solutions.\n", HEUR_NAME, nsolsadded);
290  	
291  	   if( nsolsadded > 0 )
292  	      *result = SCIP_FOUNDSOL;
293  	   else
294  	      *result = SCIP_DIDNOTFIND;
295  	
296  	   /* reset the marks of the checked solutions */
297  	   SCIPresetReoptSolMarks(scip);
298  	
299  	   /* free the buffer array */
300  	   SCIPfreeBufferArray(scip, &sols);
301  	
302  	   return SCIP_OKAY;
303  	}
304  	
305  	
306  	/*
307  	 * primal heuristic specific interface methods
308  	 */
309  	
310  	/* returns the number of checked solutions */
311  	int SCIPreoptsolsGetNCheckedsols(
312  	   SCIP*                 scip
313  	   )
314  	{
315  	   SCIP_HEUR* heur;
316  	   SCIP_HEURDATA* heurdata;
317  	
318  	   assert(scip != NULL);
319  	
320  	   heur = SCIPfindHeur(scip, HEUR_NAME);
321  	   assert(heur != NULL);
322  	
323  	   heurdata = SCIPheurGetData(heur);
324  	   assert(heurdata != NULL);
325  	
326  	   return heurdata->ncheckedsols;
327  	}
328  	
329  	/* returns the number of found improving solutions */
330  	int SCIPreoptsolsGetNImprovingsols(
331  	   SCIP*                 scip
332  	   )
333  	{
334  	   SCIP_HEUR* heur;
335  	   SCIP_HEURDATA* heurdata;
336  	
337  	   assert(scip != NULL);
338  	
339  	   heur = SCIPfindHeur(scip, HEUR_NAME);
340  	   assert(heur != NULL);
341  	
342  	   heurdata = SCIPheurGetData(heur);
343  	   assert(heurdata != NULL);
344  	
345  	   return heurdata->nimprovingsols;
346  	}
347  	
348  	/** creates the reoptsols primal heuristic and includes it in SCIP */
349  	SCIP_RETCODE SCIPincludeHeurReoptsols(
350  	   SCIP*                 scip                /**< SCIP data structure */
351  	   )
352  	{
353  	   SCIP_HEURDATA* heurdata;
354  	   SCIP_HEUR* heur;
355  	
356  	   /* create reoptsols primal heuristic data */
357  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
358  	
359  	   /* include primal heuristic */
360  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
361  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
362  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecReoptsols, heurdata) );
363  	
364  	   assert(heur != NULL);
365  	
366  	   /* set non fundamental callbacks via setter functions */
367  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyReoptsols) );
368  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeReoptsols) );
369  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitReoptsols) );
370  	
371  	   /* parameters */
372  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxsols", "maximal number solutions which should be checked. (-1: all)",
373  	         &heurdata->maxsols, TRUE, 1000, -1, INT_MAX, NULL, NULL) );
374  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxruns", "check solutions of the last k runs. (-1: all)",
375  	         &heurdata->maxruns, TRUE, -1, -1, INT_MAX, NULL, NULL) );
376  	
377  	   return SCIP_OKAY;
378  	}
379