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_bound.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  heuristic which fixes all integer variables to a bound (lower/upper) and solves the remaining LP
28   	 * @author Gerald Gamrath
29   	 *
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "scip/heur_bound.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/pub_tree.h"
38   	#include "scip/pub_var.h"
39   	#include "scip/scip_branch.h"
40   	#include "scip/scip_general.h"
41   	#include "scip/scip_heur.h"
42   	#include "scip/scip_lp.h"
43   	#include "scip/scip_mem.h"
44   	#include "scip/scip_message.h"
45   	#include "scip/scip_numerics.h"
46   	#include "scip/scip_param.h"
47   	#include "scip/scip_prob.h"
48   	#include "scip/scip_probing.h"
49   	#include "scip/scip_sol.h"
50   	#include "scip/scip_solvingstats.h"
51   	#include "scip/scip_timing.h"
52   	#include "scip/scip_tree.h"
53   	#include <string.h>
54   	
55   	#ifdef SCIP_STATISTIC
56   	#include "scip/clock.h"
57   	#endif
58   	
59   	#define HEUR_NAME             "bound"
60   	#define HEUR_DESC             "heuristic which fixes all integer variables to a bound and solves the remaining LP"
61   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_PROP
62   	#define HEUR_PRIORITY         -1107000
63   	#define HEUR_FREQ             -1
64   	#define HEUR_FREQOFS          0
65   	#define HEUR_MAXDEPTH         -1
66   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFORENODE
67   	#define HEUR_USESSUBSCIP      FALSE     /**< does the heuristic use a secondary SCIP instance? */
68   	
69   	#define DEFAULT_ONLYWITHOUTSOL   TRUE   /**< Should heuristic only be executed if no primal solution was found, yet? */
70   	#define DEFAULT_MAXPROPROUNDS    0      /* maximum number of propagation rounds during probing */
71   	#define DEFAULT_BOUND           'l'     /**< to which bound should integer variables be fixed? */
72   	
73   	
74   	/*
75   	 * Data structures
76   	 */
77   	
78   	/** primal heuristic data */
79   	struct SCIP_HeurData
80   	{
81   	   SCIP_Bool             onlywithoutsol;     /**< Should heuristic only be executed if no primal solution was found, yet? */
82   	   int                   maxproprounds;      /**< maximum number of propagation rounds during probing */
83   	   char                  bound;              /**< to which bound should integer variables be fixed? */
84   	};
85   	
86   	/*
87   	 * Local methods
88   	 */
89   	
90   	/** main procedure of the bound heuristic */
91   	static
92   	SCIP_RETCODE applyBoundHeur(
93   	   SCIP*                 scip,               /**< original SCIP data structure */
94   	   SCIP_HEUR*            heur,               /**< heuristic */
95   	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
96   	   SCIP_Bool             lower,              /**< should integer variables be fixed to their lower bound? */
97   	   SCIP_RESULT*          result              /**< pointer to store the result */
98   	   )
99   	{
100  	   SCIP_VAR** vars;
101  	   SCIP_VAR* var;
102  	   SCIP_Bool infeasible = FALSE;
103  	   int maxproprounds;
104  	   int nbinvars;
105  	   int nintvars;
106  	   int nvars;
107  	   int v;
108  	
109  	   /* get variable data of original problem */
110  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
111  	
112  	   maxproprounds = heurdata->maxproprounds;
113  	   if( maxproprounds == -2 )
114  	      maxproprounds = 0;
115  	
116  	   /* only look at binary and integer variables */
117  	   nvars = nbinvars + nintvars;
118  	
119  	   /* stop if we would have infinite fixings */
120  	   if( lower )
121  	   {
122  	      for( v = 0; v < nvars; ++v )
123  	      {
124  	         if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(vars[v])) )
125  	            return SCIP_OKAY;
126  	      }
127  	   }
128  	   else
129  	   {
130  	      for( v = 0; v < nvars; ++v )
131  	      {
132  	         if( SCIPisInfinity(scip, SCIPvarGetUbLocal(vars[v])) )
133  	            return SCIP_OKAY;
134  	      }
135  	   }
136  	
137  	   /* start probing */
138  	   SCIP_CALL( SCIPstartProbing(scip) );
139  	
140  	   for( v = 0; v < nvars; ++v )
141  	   {
142  	      var = vars[v];
143  	
144  	      assert(SCIPvarGetType(var) < SCIP_VARTYPE_IMPLINT);
145  	
146  	      /* skip variables which are already fixed */
147  	      if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) )
148  	         continue;
149  	
150  	      /* fix variable to lower bound */
151  	      if( lower )
152  	      {
153  	         SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) );
154  	         SCIPdebugMsg(scip, "fixing %d: variable <%s> to lower bound <%g> (%d pseudo cands)\n",
155  	            v, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPgetNPseudoBranchCands(scip));
156  	      }
157  	      /* fix variable to upper bound */
158  	      else
159  	      {
160  	         SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
161  	         SCIPdebugMsg(scip, "fixing %d: variable <%s> to upper bound <%g> (%d pseudo cands)\n",
162  	            v, SCIPvarGetName(var), SCIPvarGetUbLocal(var), SCIPgetNPseudoBranchCands(scip));
163  	      }
164  	
165  	      /* propagate fixings */
166  	      if( heurdata->maxproprounds != 0 )
167  	      {
168  	         SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) );
169  	      }
170  	
171  	      /* try to repair probing */
172  	      if( infeasible )
173  	      {
174  	#if 0
175  	         SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) );
176  	
177  	         /* fix the last variable, which was fixed the reverse bound */
178  	         SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
179  	
180  	         /* propagate fixings */
181  	         SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) );
182  	
183  	         SCIPdebugMsg(scip, "backtracking ended with %sfeasible problem\n", (infeasible ? "in" : ""));
184  	
185  	         if( infeasible )
186  	#endif
187  	            break;
188  	      }
189  	   }
190  	
191  	   SCIPdebugMsg(scip, "probing ended with %sfeasible problem\n", infeasible ? "in" : "");
192  	
193  	   /*************************** Probing LP Solving ***************************/
194  	
195  	   /* solve lp only if the problem is still feasible */
196  	   if( !infeasible )
197  	   {
198  	      char strbuf[SCIP_MAXSTRLEN];
199  	      SCIP_LPSOLSTAT lpstatus;
200  	      SCIP_Bool lperror;
201  	      int ncols;
202  	
203  	      /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
204  	       * which the user sees no output; more detailed probing stats only in debug mode */
205  	      ncols = SCIPgetNLPCols(scip);
206  	      if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
207  	      {
208  	         int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
209  	
210  	         if( nunfixedcols > 0.5 * ncols )
211  	         {
212  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
213  	               "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
214  	               100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
215  	         }
216  	      }
217  	      SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
218  	         SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN));
219  	
220  	      /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
221  	       * heuristic.  hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
222  	       * SCIP will stop.
223  	       */
224  	      SCIPdebugMsg(scip, "starting solving bound-heur LP at time %g, LP iterations: %" SCIP_LONGINT_FORMAT "\n",
225  	         SCIPgetSolvingTime(scip), SCIPgetNLPIterations(scip));
226  	#ifdef NDEBUG
227  	      {
228  	         SCIP_Bool retstat;
229  	         retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
230  	         if( retstat != SCIP_OKAY )
231  	         {
232  	            SCIPwarningMessage(scip, "Error while solving LP in bound heuristic; LP solve terminated with code <%d>\n",
233  	               retstat);
234  	         }
235  	      }
236  	#else
237  	      SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
238  	#endif
239  	      SCIPdebugMsg(scip, "ending solving bound-heur LP at time %g\n", SCIPgetSolvingTime(scip));
240  	
241  	      lpstatus = SCIPgetLPSolstat(scip);
242  	
243  	      SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
244  	      SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
245  	
246  	      /* check if this is a feasible solution */
247  	      if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
248  	      {
249  	         SCIP_SOL* newsol;
250  	         SCIP_Bool stored;
251  	         SCIP_Bool success;
252  	
253  	         /* create temporary solution */
254  	         SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
255  	
256  	         /* copy the current LP solution to the working solution */
257  	         SCIP_CALL( SCIPlinkLPSol(scip, newsol) );
258  	
259  	         SCIP_CALL( SCIProundSol(scip, newsol, &success) );
260  	
261  	         if( success )
262  	         {
263  	            SCIPdebugMsg(scip, "bound heuristic found roundable primal solution: obj=%g\n",
264  	               SCIPgetSolOrigObj(scip, newsol));
265  	
266  	            /* check solution for feasibility, and add it to solution store if possible.
267  	             * Neither integrality nor feasibility of LP rows have to be checked, because they
268  	             * are guaranteed by the heuristic at this stage.
269  	             */
270  	#ifdef SCIP_DEBUG
271  	            SCIP_CALL( SCIPtrySol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
272  	#else
273  	            SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
274  	#endif
275  	
276  	            if( stored )
277  	            {
278  	               SCIPdebugMsg(scip, "found feasible solution:\n");
279  	               *result = SCIP_FOUNDSOL;
280  	            }
281  	         }
282  	
283  	         /* free solution */
284  	         SCIP_CALL( SCIPfreeSol(scip, &newsol) );
285  	      }
286  	   }
287  	
288  	   /* exit probing mode */
289  	   SCIP_CALL( SCIPendProbing(scip) );
290  	
291  	   return SCIP_OKAY;
292  	}
293  	
294  	
295  	/*
296  	 * Callback methods of primal heuristic
297  	 */
298  	
299  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
300  	static
301  	SCIP_DECL_HEURCOPY(heurCopyBound)
302  	{  /*lint --e{715}*/
303  	   assert(scip != NULL);
304  	   assert(heur != NULL);
305  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
306  	
307  	   /* call inclusion method of heuristic */
308  	   SCIP_CALL( SCIPincludeHeurBound(scip) );
309  	
310  	   return SCIP_OKAY;
311  	}
312  	
313  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
314  	static
315  	SCIP_DECL_HEURFREE(heurFreeBound)
316  	{  /*lint --e{715}*/
317  	   SCIP_HEURDATA* heurdata;
318  	
319  	   /* free heuristic data */
320  	   heurdata = SCIPheurGetData(heur);
321  	
322  	   SCIPfreeBlockMemory(scip, &heurdata);
323  	   SCIPheurSetData(heur, NULL);
324  	
325  	   return SCIP_OKAY;
326  	}
327  	
328  	/** execution method of primal heuristic */
329  	static
330  	SCIP_DECL_HEUREXEC(heurExecBound)
331  	{  /*lint --e{715}*/
332  	   SCIP_HEURDATA* heurdata;
333  	
334  	   assert(heur != NULL);
335  	   assert(scip != NULL);
336  	   assert(result != NULL);
337  	
338  	   *result = SCIP_DIDNOTRUN;
339  	
340  	   if( SCIPgetNPseudoBranchCands(scip) == 0 )
341  	      return SCIP_OKAY;
342  	
343  	   if( !SCIPhasCurrentNodeLP(scip) )
344  	      return SCIP_OKAY;
345  	
346  	   heurdata = SCIPheurGetData(heur);
347  	   assert(heurdata != NULL);
348  	
349  	   *result = SCIP_DIDNOTFIND;
350  	
351  	   if( SCIPisStopped(scip) )
352  	      return SCIP_OKAY;
353  	
354  	   /* stop execution method if there is already a primal feasible solution at hand */
355  	   if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
356  	      return SCIP_OKAY;
357  	
358  	   SCIPdebugMsg(scip, "apply bound heuristic at node %lld\n",
359  	      SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
360  	
361  	   if( !SCIPisLPConstructed(scip) )
362  	   {
363  	      SCIP_Bool cutoff;
364  	
365  	      SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
366  	
367  	      /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
368  	      if( cutoff )
369  	      {
370  	         SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
371  	         return SCIP_OKAY;
372  	      }
373  	
374  	      SCIP_CALL( SCIPflushLP(scip) );
375  	   }
376  	
377  	   if( heurdata->bound == 'l' || heurdata->bound == 'b' )
378  	   {
379  	      SCIP_CALL(applyBoundHeur(scip, heur, heurdata, TRUE, result) );
380  	   }
381  	   if( heurdata->bound == 'u' || heurdata->bound == 'b' )
382  	   {
383  	      SCIP_CALL(applyBoundHeur(scip, heur, heurdata, FALSE, result) );
384  	   }
385  	
386  	   return SCIP_OKAY;
387  	}
388  	
389  	/*
390  	 * primal heuristic specific interface methods
391  	 */
392  	
393  	/** creates the bound primal heuristic and includes it in SCIP */
394  	SCIP_RETCODE SCIPincludeHeurBound(
395  	   SCIP*                 scip                /**< SCIP data structure */
396  	   )
397  	{
398  	   SCIP_HEURDATA* heurdata;
399  	   SCIP_HEUR* heur;
400  	
401  	   /* create bound primal heuristic data */
402  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
403  	
404  	   /* include primal heuristic */
405  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
406  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
407  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecBound, heurdata) );
408  	
409  	   assert(heur != NULL);
410  	
411  	   /* set non-NULL pointers to callback methods */
412  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyBound) );
413  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeBound) );
414  	
415  	   /* add bound heuristic parameters */
416  	
417  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
418  	         "Should heuristic only be executed if no primal solution was found, yet?",
419  	         &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
420  	
421  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
422  	         "maximum number of propagation rounds during probing (-1 infinity, -2 parameter settings)",
423  	         &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
424  	
425  	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/bound",
426  	         "to which bound should integer variables be fixed? ('l'ower, 'u'pper, or 'b'oth)",
427  	         &heurdata->bound, FALSE, DEFAULT_BOUND, "lub", NULL, NULL) );
428  	
429  	   return SCIP_OKAY;
430  	}
431