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_trysol.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  primal heuristic that tries a given solution
28   	 * @author Marc Pfetsch
29   	 *
30   	 * This heuristic takes a solution from somewhere else via the function SCIPheurPassSolTrySol(). It
31   	 * then tries to commit this solution. It is mainly used by cons_indicator, which tries to correct a
32   	 * given solution, but cannot directly submit this solution, because it is a constraint handler and
33   	 * not a heuristic.
34   	 */
35   	
36   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37   	
38   	#include "scip/heur_trysol.h"
39   	#include "scip/pub_heur.h"
40   	#include "scip/pub_message.h"
41   	#include "scip/pub_sol.h"
42   	#include "scip/scip_heur.h"
43   	#include "scip/scip_mem.h"
44   	#include "scip/scip_message.h"
45   	#include "scip/scip_numerics.h"
46   	#include "scip/scip_prob.h"
47   	#include "scip/scip_sol.h"
48   	#include <string.h>
49   	
50   	#define HEUR_NAME             "trysol"
51   	#define HEUR_DESC             "try solution heuristic"
52   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_TRIVIAL
53   	#define HEUR_PRIORITY         -3000010     /* should process after all other heuristics */
54   	#define HEUR_FREQ             1
55   	#define HEUR_FREQOFS          0
56   	#define HEUR_MAXDEPTH         -1
57   	#define HEUR_TIMING           SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFOREPRESOL | 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   	
66   	/** primal heuristic data */
67   	struct SCIP_HeurData
68   	{
69   	   SCIP_SOL*             trysol;             /**< storing solution passed to heuristic which has to tried (NULL if none) */
70   	   SCIP_SOL*             addsol;             /**< storing solution passed to heuristic which can be added without checking (NULL if none) */
71   	   SCIP_Bool             rec;                /**< whether we are within our own call */
72   	};
73   	
74   	
75   	/*
76   	 * Callback methods of primal heuristic
77   	 */
78   	
79   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
80   	static
81   	SCIP_DECL_HEURCOPY(heurCopyTrySol)
82   	{  /*lint --e{715}*/
83   	   assert(scip != NULL);
84   	   assert(heur != NULL);
85   	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
86   	
87   	   /* call inclusion method of primal heuristic */
88   	   SCIP_CALL( SCIPincludeHeurTrySol(scip) );
89   	
90   	   return SCIP_OKAY;
91   	}
92   	
93   	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
94   	static
95   	SCIP_DECL_HEURFREE(heurFreeTrySol)
96   	{  /*lint --e{715}*/
97   	   SCIP_HEURDATA* heurdata;
98   	
99   	   assert( heur != NULL );
100  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
101  	   assert( scip != NULL );
102  	
103  	   SCIPdebugMsg(scip, "free method of trysol primal heuristic.\n");
104  	
105  	   /* get heuristic data */
106  	   heurdata = SCIPheurGetData(heur);
107  	   assert(heurdata != NULL);
108  	
109  	   SCIPfreeBlockMemory(scip, &heurdata);
110  	
111  	   return SCIP_OKAY;
112  	}
113  	
114  	
115  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
116  	static
117  	SCIP_DECL_HEUREXITSOL(heurExitTrySol)
118  	{  /*lint --e{715}*/
119  	   SCIP_HEURDATA* heurdata;
120  	
121  	   assert( heur != NULL );
122  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
123  	   assert( scip != NULL );
124  	
125  	   SCIPdebugMsg(scip, "exit method of trysol primal heuristic.\n");
126  	
127  	   /* get heuristic data */
128  	   heurdata = SCIPheurGetData(heur);
129  	   assert(heurdata != NULL);
130  	
131  	   /* free solution if one is still present */
132  	   if( heurdata->trysol != NULL )
133  	      SCIP_CALL( SCIPfreeSol(scip, &heurdata->trysol) );
134  	   assert( heurdata->trysol == NULL );
135  	
136  	   /* free solution if one is still present */
137  	   if( heurdata->addsol != NULL )
138  	      SCIP_CALL( SCIPfreeSol(scip, &heurdata->addsol) );
139  	   assert( heurdata->trysol == NULL );
140  	
141  	   return SCIP_OKAY;
142  	}
143  	
144  	
145  	/** execution method of primal heuristic */
146  	static
147  	SCIP_DECL_HEUREXEC(heurExecTrySol)
148  	{  /*lint --e{715}*/
149  	   SCIP_HEURDATA* heurdata;
150  	   SCIP_Bool stored;
151  	#ifdef SCIP_DEBUG
152  	   SCIP_Real obj;
153  	#endif
154  	
155  	   assert( heur != NULL );
156  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
157  	   assert( scip != NULL );
158  	   assert( result != NULL );
159  	
160  	   *result = SCIP_DIDNOTRUN;
161  	
162  	   /* get heuristic data */
163  	   heurdata = SCIPheurGetData(heur);
164  	   assert(heurdata != NULL);
165  	
166  	   /* only run if solution present */
167  	   if( heurdata->addsol == NULL && heurdata->trysol == NULL )
168  	      return SCIP_OKAY;
169  	
170  	   SCIPdebugMsg(scip, "exec method of trysol primal heuristic.\n");
171  	   *result = SCIP_DIDNOTFIND;
172  	   heurdata->rec = TRUE;
173  	
174  	   if( heurdata->trysol != NULL )
175  	   {
176  	      /* try solution and free it - check everything, because we are not sure */
177  	#ifdef SCIP_DEBUG
178  	      obj = SCIPgetSolOrigObj(scip, heurdata->trysol);
179  	#endif
180  	
181  	      SCIP_CALL( SCIPtrySolFree(scip, &heurdata->trysol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
182  	
183  	      if( stored )
184  	      {
185  	#ifdef SCIP_DEBUG
186  	         SCIPdebugMsg(scip, "Found feasible solution of value %g.\n", obj);
187  	#endif
188  	         *result = SCIP_FOUNDSOL;
189  	      }
190  	   }
191  	
192  	   if( heurdata->addsol != NULL )
193  	   {
194  	#ifdef SCIP_DEBUG
195  	      obj = SCIPgetSolOrigObj(scip, heurdata->addsol);
196  	#endif
197  	
198  	      SCIP_CALL( SCIPaddSolFree(scip, &heurdata->addsol, &stored) );
199  	
200  	      if( stored )
201  	      {
202  	#ifdef SCIP_DEBUG
203  	         SCIPdebugMsg(scip, "Found feasible solution of value %g.\n", obj);
204  	#endif
205  	         *result = SCIP_FOUNDSOL;
206  	      }
207  	   }
208  	
209  	   assert( heurdata->trysol == NULL );
210  	   assert( heurdata->addsol == NULL );
211  	
212  	   heurdata->rec = FALSE;
213  	
214  	   return SCIP_OKAY;
215  	}
216  	
217  	/*
218  	 * primal heuristic specific interface methods
219  	 */
220  	
221  	/** creates the trysol primal heuristic and includes it in SCIP */
222  	SCIP_RETCODE SCIPincludeHeurTrySol(
223  	   SCIP*                 scip                /**< SCIP data structure */
224  	   )
225  	{
226  	   SCIP_HEURDATA* heurdata;
227  	   SCIP_HEUR* heur;
228  	
229  	   /* create heuristic data */
230  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
231  	   heurdata->trysol = NULL;
232  	   heurdata->addsol = NULL;
233  	   heurdata->rec = FALSE;
234  	
235  	   /* include primal heuristic */
236  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
237  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
238  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrySol, heurdata) );
239  	
240  	   assert(heur != NULL);
241  	
242  	   /* set non-NULL pointers to callback methods */
243  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrySol) );
244  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeTrySol) );
245  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitTrySol) );
246  	
247  	   return SCIP_OKAY;
248  	}
249  	
250  	
251  	/** pass solution to trysol heuristic */
252  	SCIP_RETCODE SCIPheurPassSolTrySol(
253  	   SCIP*                 scip,               /**< SCIP data structure */
254  	   SCIP_HEUR*            heur,               /**< trysol heuristic */
255  	   SCIP_SOL*             sol                 /**< solution to be passed */
256  	   )
257  	{
258  	   SCIP_HEURDATA* heurdata;
259  	
260  	   assert( scip != NULL );
261  	   assert( heur != NULL );
262  	   assert( sol != NULL );
263  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
264  	
265  	   /* get heuristic data */
266  	   heurdata = SCIPheurGetData(heur);
267  	   assert(heurdata != NULL);
268  	
269  	   /* only store solution if we are not within our own SCIPtrySol() call */
270  	   if( ! heurdata->rec )
271  	   {
272  	      if( heurdata->trysol == NULL || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE &&
273  	            SCIPisGT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->trysol))) ||
274  	         SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->trysol)) )
275  	      {
276  	         if( heurdata->trysol != NULL )
277  	         {
278  	            /* free previous solution */
279  	            SCIP_CALL( SCIPfreeSol(scip, &heurdata->trysol) );
280  	         }
281  	
282  	         SCIPdebugMsg(scip, "Received solution of value %g.\n", SCIPgetSolOrigObj(scip, sol));
283  	         SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->trysol, sol) );
284  	         SCIP_CALL( SCIPunlinkSol(scip, heurdata->trysol) );
285  	         SCIPsolSetHeur(heurdata->trysol, heur);
286  	      }
287  	   }
288  	
289  	   return SCIP_OKAY;
290  	}
291  	
292  	/** pass solution to trysol heuristic which just gets added (without checking feasibility */
293  	SCIP_RETCODE SCIPheurPassSolAddSol(
294  	   SCIP*                 scip,               /**< SCIP data structure */
295  	   SCIP_HEUR*            heur,               /**< trysol heuristic */
296  	   SCIP_SOL*             sol                 /**< solution to be passed */
297  	   )
298  	{
299  	   SCIP_HEURDATA* heurdata;
300  	
301  	   assert( scip != NULL );
302  	   assert( heur != NULL );
303  	   assert( sol != NULL );
304  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
305  	
306  	   /* get heuristic data */
307  	   heurdata = SCIPheurGetData(heur);
308  	   assert(heurdata != NULL);
309  	
310  	   /* only store solution if we are not within our own SCIPtrySol() call */
311  	   if( ! heurdata->rec )
312  	   {
313  	      if( heurdata->addsol == NULL || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE &&
314  	            SCIPisGT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->addsol))) ||
315  	         SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->addsol)) )
316  	      {
317  	         if( heurdata->addsol != NULL )
318  	         {
319  	            /* free previous solution */
320  	            SCIP_CALL( SCIPfreeSol(scip, &heurdata->addsol) );
321  	         }
322  	
323  	         SCIPdebugMsg(scip, "Received solution of value %g.\n", SCIPgetSolOrigObj(scip, sol));
324  	         SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->addsol, sol) );
325  	         SCIP_CALL( SCIPunlinkSol(scip, heurdata->addsol) );
326  	         SCIPsolSetHeur(heurdata->addsol, heur);
327  	      }
328  	   }
329  	
330  	   return SCIP_OKAY;
331  	}
332