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_fixandinfer.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  fix-and-infer primal heuristic
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/heur_fixandinfer.h"
34   	#include "scip/pub_heur.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_var.h"
37   	#include "scip/scip_branch.h"
38   	#include "scip/scip_general.h"
39   	#include "scip/scip_heur.h"
40   	#include "scip/scip_mem.h"
41   	#include "scip/scip_message.h"
42   	#include "scip/scip_numerics.h"
43   	#include "scip/scip_param.h"
44   	#include "scip/scip_prob.h"
45   	#include "scip/scip_probing.h"
46   	#include "scip/scip_sol.h"
47   	#include "scip/scip_tree.h"
48   	#include "scip/scip_var.h"
49   	#include <string.h>
50   	
51   	#define HEUR_NAME             "fixandinfer"
52   	#define HEUR_DESC             "iteratively fixes variables and propagates inferences"
53   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_PROP
54   	#define HEUR_PRIORITY         -500000
55   	#define HEUR_FREQ             -1        /* at the moment, the heuristic seems to be useless */
56   	#define HEUR_FREQOFS          0
57   	#define HEUR_MAXDEPTH         -1
58   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE
59   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
60   	
61   	#define MAXDIVEDEPTH          100
62   	
63   	
64   	/*
65   	 * Default parameter settings
66   	 */
67   	
68   	#define DEFAULT_PROPROUNDS           0  /**< maximal number of propagation rounds in probing subproblems */
69   	#define DEFAULT_MINFIXINGS         100  /**< minimal number of fixings to apply before dive may be aborted */
70   	
71   	
72   	/*
73   	 * Data structures
74   	 */
75   	
76   	/** primal heuristic data */
77   	struct SCIP_HeurData
78   	{
79   	   int                   proprounds;         /**< maximal number of propagation rounds in probing subproblems */
80   	   int                   minfixings;         /**< minimal number of fixings to apply before dive may be aborted */
81   	};
82   	
83   	
84   	/*
85   	 * Local methods
86   	 */
87   	
88   	/** selects a variable and fixes it to its current pseudo solution value */
89   	static
90   	SCIP_RETCODE fixVariable(
91   	   SCIP*                 scip,               /**< SCIP data structure */
92   	   SCIP_VAR**            pseudocands,        /**< array of unfixed variables */
93   	   int                   npseudocands,       /**< number of unfixed variables */
94   	   SCIP_Real             large               /**< large value to be used instead of infinity */
95   	   )
96   	{
97   	   SCIP_VAR* var;
98   	   SCIP_Real bestscore;
99   	   SCIP_Real score;
100  	   SCIP_Real solval;
101  	   int bestcand;
102  	   int ncands;
103  	   int c;
104  	
105  	   assert(pseudocands != NULL);
106  	   assert(npseudocands > 0);
107  	
108  	   /* if existing, choose one of the highest priority binary variables; if no high priority binary variables
109  	    * exist, choose a variable among all unfixed integral variables
110  	    */
111  	   ncands = SCIPgetNPrioPseudoBranchBins(scip);
112  	   if( ncands == 0 )
113  	      ncands = npseudocands;
114  	
115  	   /* select variable to tighten the domain for */
116  	   bestscore = -SCIPinfinity(scip);
117  	   bestcand = -1;
118  	   for( c = 0; c < ncands; ++c )
119  	   {
120  	      score = SCIPgetVarAvgInferenceScore(scip, pseudocands[c]);
121  	      if( score > bestscore )
122  	      {
123  	         bestscore = score;
124  	         bestcand = c;
125  	      }
126  	   }
127  	   assert(bestcand != -1);
128  	
129  	   /* fix variable to its current pseudo solution value */
130  	   var = pseudocands[bestcand];
131  	   solval = SCIPgetVarSol(scip, var);
132  	
133  	   /* adapt solution value if it is infinite */
134  	   if( SCIPisInfinity(scip, solval) )
135  	   {
136  	      SCIP_Real lb;
137  	      assert(SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
138  	      lb = SCIPvarGetLbLocal(var);
139  	
140  	      /* adapt fixing value by changing it to a large value */
141  	      if( SCIPisInfinity(scip, -lb) )
142  	         solval = SCIPceil(scip, large);
143  	      else if( !SCIPisInfinity(scip, SCIPceil(scip, lb+large)) )
144  	         solval = SCIPceil(scip, lb+large);
145  	   }
146  	   else if( SCIPisInfinity(scip, -solval) )
147  	   {
148  	      SCIP_Real ub;
149  	      assert(SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
150  	      ub = SCIPvarGetUbLocal(var);
151  	
152  	      /* adapt fixing value by changing it to a large negative value */
153  	      if( SCIPisInfinity(scip, ub) )
154  	         solval = SCIPfloor(scip, -large);
155  	      else if( !SCIPisInfinity(scip, -SCIPfloor(scip, ub-large)) )
156  	         solval = SCIPfloor(scip, ub-large);
157  	   }
158  	
159  	   assert(SCIPisFeasIntegral(scip, solval)); /* in probing, we always have the pseudo solution */
160  	   SCIPdebugMsg(scip, " -> fixed variable <%s>[%g,%g] = %g (%d candidates left)\n",
161  	      SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), solval, npseudocands - 1);
162  	   SCIP_CALL( SCIPfixVarProbing(scip, var, solval) );
163  	
164  	   return SCIP_OKAY;
165  	}
166  	
167  	
168  	/*
169  	 * Callback methods of primal heuristic
170  	 */
171  	
172  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
173  	static
174  	SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
175  	{  /*lint --e{715}*/
176  	   assert(scip != NULL);
177  	   assert(heur != NULL);
178  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
179  	
180  	   /* call inclusion method of primal heuristic */
181  	   SCIP_CALL( SCIPincludeHeurFixandinfer(scip) );
182  	
183  	   return SCIP_OKAY;
184  	}
185  	
186  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
187  	static
188  	SCIP_DECL_HEURFREE(heurFreeFixandinfer) /*lint --e{715}*/
189  	{  /*lint --e{715}*/
190  	   SCIP_HEURDATA* heurdata;
191  	
192  	   /* free heuristic data */
193  	   heurdata = SCIPheurGetData(heur);
194  	   assert(heurdata != NULL);
195  	   SCIPfreeBlockMemory(scip, &heurdata);
196  	   SCIPheurSetData(heur, NULL);
197  	
198  	   return SCIP_OKAY;
199  	}
200  	
201  	
202  	/** execution method of primal heuristic */
203  	static
204  	SCIP_DECL_HEUREXEC(heurExecFixandinfer)
205  	{  /*lint --e{715}*/
206  	   SCIP_HEURDATA* heurdata;
207  	   SCIP_VAR** cands;
208  	   int ncands;
209  	   int startncands;
210  	   int divedepth;
211  	   SCIP_Bool cutoff;
212  	   SCIP_Real large;
213  	
214  	   *result = SCIP_DIDNOTRUN;
215  	
216  	   /* do not call heuristic of node was already detected to be infeasible */
217  	   if( nodeinfeasible )
218  	      return SCIP_OKAY;
219  	
220  	   /* we cannot run on problems with continuous variables */
221  	   if( SCIPgetNContVars(scip) > 0 )
222  	      return SCIP_OKAY;
223  	
224  	   /* get unfixed variables */
225  	   SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
226  	   if( ncands == 0 )
227  	      return SCIP_OKAY;
228  	
229  	   /* get heuristic data */
230  	   heurdata = SCIPheurGetData(heur);
231  	   assert(heurdata != NULL);
232  	
233  	   /* fix variables and propagate inferences as long as the problem is still feasible and there are
234  	    * unfixed integral variables
235  	    */
236  	   cutoff = FALSE;
237  	   divedepth = 0;
238  	   startncands = ncands;
239  	
240  	   /* start probing */
241  	   SCIP_CALL( SCIPstartProbing(scip) );
242  	
243  	   if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
244  	   {
245  	      SCIP_CALL( SCIPendProbing(scip) );
246  	      return SCIP_OKAY;
247  	   }
248  	
249  	   SCIPdebugMsg(scip, "starting fix-and-infer heuristic with %d unfixed integral variables\n", ncands);
250  	
251  	   *result = SCIP_DIDNOTFIND;
252  	
253  	   /* create next probing node */
254  	   SCIP_CALL( SCIPnewProbingNode(scip) );
255  	
256  	   /* determine large value to set variables to */
257  	   large = SCIPinfinity(scip);
258  	   if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
259  	      large = 0.1 / SCIPfeastol(scip);
260  	
261  	   while( !cutoff && ncands > 0
262  	      && (divedepth < heurdata->minfixings || (startncands - ncands) * 2 * MAXDIVEDEPTH >= startncands * divedepth)
263  	      && !SCIPisStopped(scip) )
264  	   {
265  	      divedepth++;
266  	
267  	      /* fix next variable */
268  	      SCIP_CALL( fixVariable(scip, cands, ncands, large) );
269  	
270  	      /* propagate the fixing */
271  	      SCIP_CALL( SCIPpropagateProbing(scip, heurdata->proprounds, &cutoff, NULL) );
272  	
273  	      /* get remaining unfixed variables */
274  	      if( !cutoff )
275  	      {
276  	         SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
277  	      }
278  	   }
279  	
280  	   /* check, if we are still feasible */
281  	   if( cutoff )
282  	   {
283  	      SCIPdebugMsg(scip, "propagation detected a cutoff\n");
284  	   }
285  	   else if( ncands == 0 )
286  	   {
287  	      SCIP_Bool success;
288  	
289  	      success = FALSE;
290  	
291  	      /* try to add solution to SCIP */
292  	      SCIP_CALL( SCIPtryCurrentSol(scip, heur, FALSE, FALSE, FALSE, TRUE, &success) );
293  	
294  	      if( success )
295  	      {
296  	         SCIPdebugMsg(scip, "found primal feasible solution\n");
297  	         *result = SCIP_FOUNDSOL;
298  	      }
299  	      else
300  	      {
301  	         SCIPdebugMsg(scip, "primal solution was rejected\n");
302  	      }
303  	   }
304  	   else
305  	   {
306  	      SCIPdebugMsg(scip, "probing was aborted (probing depth: %d, fixed: %d/%d)", divedepth, startncands - ncands, startncands);
307  	   }
308  	
309  	   /* end probing */
310  	   SCIP_CALL( SCIPendProbing(scip) );
311  	
312  	   return SCIP_OKAY;
313  	}
314  	
315  	
316  	/*
317  	 * primal heuristic specific interface methods
318  	 */
319  	
320  	/** creates the fix-and-infer primal heuristic and includes it in SCIP */
321  	SCIP_RETCODE SCIPincludeHeurFixandinfer(
322  	   SCIP*                 scip                /**< SCIP data structure */
323  	   )
324  	{
325  	   SCIP_HEURDATA* heurdata;
326  	   SCIP_HEUR* heur;
327  	
328  	    /* create Fixandinfer primal heuristic data */
329  	    SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
330  	
331  	    /* include primal heuristic */
332  	    SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
333  	          HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
334  	          HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFixandinfer, heurdata) );
335  	
336  	    assert(heur != NULL);
337  	
338  	    /* set non-NULL pointers to callback methods */
339  	    SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFixandinfer) );
340  	    SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFixandinfer) );
341  	
342  	   /* fixandinfer heuristic parameters */
343  	   SCIP_CALL( SCIPaddIntParam(scip,
344  	         "heuristics/fixandinfer/proprounds",
345  	         "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
346  	         &heurdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
347  	   SCIP_CALL( SCIPaddIntParam(scip,
348  	         "heuristics/fixandinfer/minfixings",
349  	         "minimal number of fixings to apply before dive may be aborted",
350  	         &heurdata->minfixings, TRUE, DEFAULT_MINFIXINGS, 0, INT_MAX, NULL, NULL) );
351  	
352  	   return SCIP_OKAY;
353  	}
354