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_sync.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  primal heuristic that adds solutions from synchronization
28   	 * @author Leona Gottwald
29   	 *
30   	 * This heuristic takes solutions during synchronization and then adds them.
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#include <assert.h>
36   	#include <string.h>
37   	
38   	#include "scip/heur_sync.h"
39   	#include "scip/scip.h"
40   	
41   	
42   	#define HEUR_NAME             "sync"
43   	#define HEUR_DESC             "heuristic for synchronizing solution"
44   	#define HEUR_DISPCHAR         'S'
45   	#define HEUR_PRIORITY         -3000000     /* should process after all other heuristics */
46   	#define HEUR_FREQ             -1
47   	#define HEUR_FREQOFS          0
48   	#define HEUR_MAXDEPTH         -1
49   	#define HEUR_TIMING           SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
50   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
51   	
52   	
53   	/*
54   	 * Data structures
55   	 */
56   	
57   	
58   	/** primal heuristic data */
59   	struct SCIP_HeurData
60   	{
61   	   SCIP_SOL**            sols;               /**< storing solutions passed to heuristic sorted by objective value */
62   	   int                   nsols;              /**< number of soluions stored */
63   	   int                   maxnsols;           /**< maximum number of solutions that can be stored */
64   	};
65   	
66   	
67   	/*
68   	 * Callback methods of primal heuristic
69   	 */
70   	
71   	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
72   	static
73   	SCIP_DECL_HEURFREE(heurFreeSync)
74   	{  /*lint --e{715}*/
75   	   SCIP_HEURDATA* heurdata;
76   	
77   	   assert( heur != NULL );
78   	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
79   	   assert( scip != NULL );
80   	
81   	   SCIPdebugMessage("free method of sync primal heuristic.\n");
82   	
83   	   /* get heuristic data */
84   	   heurdata = SCIPheurGetData(heur);
85   	   assert(heurdata != NULL);
86   	   assert(heurdata->nsols == 0);
87   	   SCIPfreeBlockMemoryArray(scip, &heurdata->sols, heurdata->maxnsols);
88   	   SCIPfreeBlockMemory(scip, &heurdata);
89   	
90   	   return SCIP_OKAY;
91   	}
92   	
93   	
94   	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
95   	static
96   	SCIP_DECL_HEUREXITSOL(heurExitSync)
97   	{  /*lint --e{715}*/
98   	   SCIP_HEURDATA* heurdata;
99   	   int            i;
100  	
101  	   assert( heur != NULL );
102  	   assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
103  	   assert( scip != NULL );
104  	
105  	   SCIPdebugMessage("exit method of sync primal heuristic.\n");
106  	
107  	   /* get heuristic data */
108  	   heurdata = SCIPheurGetData(heur);
109  	   assert(heurdata != NULL);
110  	
111  	   /* free solution if one is still present */
112  	   for( i = 0; i < heurdata->nsols; ++i )
113  	   {
114  	      SCIP_CALL( SCIPfreeSol(scip, &heurdata->sols[i]) );
115  	   }
116  	   heurdata->nsols = 0;
117  	   return SCIP_OKAY;
118  	}
119  	
120  	
121  	/** execution method of primal heuristic */
122  	static
123  	SCIP_DECL_HEUREXEC(heurExecSync)
124  	{  /*lint --e{715}*/
125  	   SCIP_HEURDATA* heurdata;
126  	   SCIP_Bool stored;
127  	   int i;
128  	
129  	   assert(heur != NULL);
130  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
131  	   assert(scip != NULL);
132  	   assert(result != NULL);
133  	   assert(SCIPheurGetFreq(heur) == 1);
134  	
135  	   SCIPheurSetFreq(heur, -1);
136  	
137  	   /* get heuristic data */
138  	   heurdata = SCIPheurGetData(heur);
139  	   assert(heurdata != NULL);
140  	   assert(heurdata->nsols > 0);
141  	
142  	   SCIPdebugMessage("exec method of sync primal heuristic.\n");
143  	   *result = SCIP_DIDNOTFIND;
144  	   for( i = 0; i < heurdata->nsols; ++i )
145  	   {
146  	      SCIP_CALL( SCIPtrySolFree(scip, &heurdata->sols[i], FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
147  	      if( stored )
148  	         *result = SCIP_FOUNDSOL;
149  	   }
150  	
151  	   heurdata->nsols = 0;
152  	
153  	   return SCIP_OKAY;
154  	}
155  	
156  	/*
157  	 * primal heuristic specific interface methods
158  	 */
159  	
160  	/** creates the sync primal heuristic and includes it in SCIP */
161  	SCIP_RETCODE SCIPincludeHeurSync(
162  	   SCIP*                 scip                /**< SCIP data structure */
163  	   )
164  	{
165  	   SCIP_HEURDATA* heurdata;
166  	   SCIP_HEUR*     heur;
167  	
168  	   /* create heuristic data */
169  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
170  	   SCIP_CALL( SCIPgetIntParam(scip, "concurrent/sync/maxnsols", &heurdata->maxnsols) );
171  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->sols, heurdata->maxnsols) );
172  	   heurdata->nsols = 0;
173  	
174  	   /* include primal heuristic */
175  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
176  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
177  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSync, heurdata) );
178  	
179  	   assert(heur != NULL);
180  	
181  	   /* set non-NULL pointers to callback methods */
182  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSync) );
183  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSync) );
184  	
185  	   return SCIP_OKAY;
186  	}
187  	
188  	
189  	/** pass solution to sync heuristic */
190  	SCIP_RETCODE SCIPheurSyncPassSol(
191  	   SCIP*                 scip,               /**< SCIP data structure */
192  	   SCIP_HEUR*            heur,               /**< sync heuristic */
193  	   SCIP_SOL*             sol                 /**< solution to be passed */
194  	   )
195  	{
196  	   SCIP_HEURDATA* heurdata;
197  	   SCIP_Real      solobj;
198  	   int            i;
199  	   assert(scip != NULL);
200  	   assert(heur != NULL);
201  	   assert(sol != NULL);
202  	   assert(strcmp(HEUR_NAME, SCIPheurGetName(heur)) == 0);
203  	
204  	   /* get heuristic data */
205  	   heurdata = SCIPheurGetData(heur);
206  	   assert(heurdata != NULL);
207  	
208  	   SCIPsolSetHeur(sol, heur);
209  	   solobj = SCIPgetSolTransObj(scip, sol);
210  	
211  	   /* check if we have an empty space in the solution array or
212  	    * if we need to discard the worst solution
213  	    */
214  	   if( heurdata->nsols < heurdata->maxnsols )
215  	   {
216  	      /* if the maximum number of solutions is not yet reached just
217  	       * insert the solution sorted by its objective value */
218  	      i = heurdata->nsols++;
219  	
220  	      while( i > 0 && solobj > SCIPgetSolTransObj(scip, heurdata->sols[i - 1]) )
221  	      {
222  	         heurdata->sols[i] =  heurdata->sols[i - 1];
223  	         --i;
224  	      }
225  	      heurdata->sols[i] = sol;
226  	   }
227  	   else
228  	   {
229  	      /* already have reached the maximum number of solutions so
230  	       * we need to check if the solution is better than a previous
231  	       * one and free the worst solution to make room for it if that
232  	       * is the case
233  	       */
234  	      i = 0;
235  	      while( i < heurdata->nsols && solobj < SCIPgetSolTransObj(scip, heurdata->sols[i]) )
236  	      {
237  	         if( i > 0 )
238  	         {
239  	            heurdata->sols[i - 1] = heurdata->sols[i];
240  	         }
241  	         else
242  	         {
243  	            SCIP_CALL( SCIPfreeSol(scip, &heurdata->sols[i]) );
244  	         }
245  	
246  	         ++i;
247  	      }
248  	      /* check if solution must be inserted or discarded */
249  	      if( i > 0)
250  	      {
251  	         /* found position to insert the solution sorted by objective value */
252  	         heurdata->sols[i-1] = sol;
253  	      }
254  	      else
255  	      {
256  	         /* solution is not better just discard it */
257  	         SCIP_CALL( SCIPfreeSol(scip, &sol) );
258  	      }
259  	   }
260  	   assert(heurdata->nsols > 0);
261  	   assert(heurdata->nsols <= heurdata->maxnsols);
262  	
263  	   SCIPheurSetFreq(heur, 1);
264  	
265  	   return SCIP_OKAY;
266  	}
267