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_simplerounding.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  simple and fast LP rounding heuristic
28   	 * @author Tobias Achterberg
29   	 * @author Marc Pfetsch
30   	 *
31   	 * The heuristic also tries to round relaxation solutions if available.
32   	 */
33   	
34   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35   	
36   	#include "blockmemshell/memory.h"
37   	#include "scip/heur_simplerounding.h"
38   	#include "scip/pub_heur.h"
39   	#include "scip/pub_message.h"
40   	#include "scip/pub_var.h"
41   	#include "scip/scip_branch.h"
42   	#include "scip/scip_heur.h"
43   	#include "scip/scip_lp.h"
44   	#include "scip/scip_mem.h"
45   	#include "scip/scip_message.h"
46   	#include "scip/scip_numerics.h"
47   	#include "scip/scip_param.h"
48   	#include "scip/scip_prob.h"
49   	#include "scip/scip_sol.h"
50   	#include "scip/scip_solvingstats.h"
51   	#include "scip/scip_var.h"
52   	#include <string.h>
53   	
54   	#define HEUR_NAME             "simplerounding"
55   	#define HEUR_DESC             "simple and fast LP rounding heuristic"
56   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_ROUNDING
57   	#define HEUR_PRIORITY         -30
58   	#define HEUR_FREQ             1
59   	#define HEUR_FREQOFS          0
60   	#define HEUR_MAXDEPTH         -1
61   	#define HEUR_TIMING           SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP
62   	#define HEUR_USESSUBSCIP      FALSE          /**< does the heuristic use a secondary SCIP instance? */
63   	
64   	#define DEFAULT_ONCEPERNODE   FALSE          /**< should the heuristic only be called once per node? */
65   	
66   	/* locally defined heuristic data */
67   	struct SCIP_HeurData
68   	{
69   	   SCIP_SOL*             sol;                /**< working solution */
70   	   SCIP_Longint          lastlp;             /**< last LP number where the heuristic was applied */
71   	   int                   nroundablevars;     /**< number of variables that can be rounded (-1 if not yet calculated) */
72   	   SCIP_Bool             oncepernode;        /**< should the heuristic only be called once per node? */
73   	};
74   	
75   	
76   	/*
77   	 * Local methods
78   	 */
79   	
80   	/** perform rounding */
81   	static
82   	SCIP_RETCODE performSimpleRounding(
83   	   SCIP*                 scip,               /**< SCIP main data structure */
84   	   SCIP_SOL*             sol,                /**< solution to round */
85   	   SCIP_VAR**            cands,              /**< candidate variables */
86   	   SCIP_Real*            candssol,           /**< solutions of candidate variables */
87   	   int                   ncands,             /**< number of candidates */
88   	   SCIP_RESULT*          result              /**< pointer to store the result of the heuristic call */
89   	   )
90   	{
91   	   int c;
92   	   int nunroundableimplints = 0;
93   	
94   	   /* round all roundable fractional columns in the corresponding direction as long as no unroundable column was found */
95   	   for (c = 0; c < ncands; ++c)
96   	   {
97   	      SCIP_VAR* var;
98   	      SCIP_Real oldsolval;
99   	      SCIP_Real newsolval;
100  	      SCIP_Bool mayrounddown;
101  	      SCIP_Bool mayroundup;
102  	
103  	      oldsolval = candssol[c];
104  	      assert( ! SCIPisFeasIntegral(scip, oldsolval) );
105  	      var = cands[c];
106  	      assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
107  	      mayrounddown = SCIPvarMayRoundDown(var);
108  	      mayroundup = SCIPvarMayRoundUp(var);
109  	      SCIPdebugMsg(scip, "simple rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n",
110  	         SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup);
111  	
112  	      /* choose rounding direction */
113  	      if ( mayrounddown && mayroundup )
114  	      {
115  	         /* we can round in both directions: round in objective function direction */
116  	         if ( SCIPvarGetObj(var) >= 0.0 )
117  	            newsolval = SCIPfeasFloor(scip, oldsolval);
118  	         else
119  	            newsolval = SCIPfeasCeil(scip, oldsolval);
120  	      }
121  	      else if ( mayrounddown )
122  	         newsolval = SCIPfeasFloor(scip, oldsolval);
123  	      else if ( mayroundup )
124  	         newsolval = SCIPfeasCeil(scip, oldsolval);
125  	      else if( SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT )
126  	      {
127  	         ++nunroundableimplints;
128  	         continue;
129  	      }
130  	      else
131  	         break;
132  	
133  	      /* store new solution value */
134  	      SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) );
135  	   }
136  	
137  	   /* check, if rounding was successful */
138  	   if( c == ncands )
139  	   {
140  	      SCIP_Bool stored;
141  	      SCIP_Bool checklprows;
142  	
143  	      /* unroundable implicit integers are adjusted. LP rows must be checked afterwards */
144  	      if( nunroundableimplints > 0 )
145  	      {
146  	         SCIP_CALL( SCIPadjustImplicitSolVals(scip, sol, TRUE) );
147  	         checklprows = TRUE;
148  	      }
149  	      else
150  	         checklprows = FALSE;
151  	
152  	      if( SCIPallColsInLP(scip) )
153  	      {
154  	         /* check solution for feasibility, and add it to solution store if possible
155  	          * integrality need not be checked, because all fractional
156  	          * variables were already moved in feasible direction to the next integer
157  	          *
158  	          * feasibility of LP rows must be checked again at the presence of
159  	          * unroundable, implicit integer variables with fractional LP solution
160  	          * value
161  	          */
162  	         SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, checklprows, &stored) );
163  	      }
164  	      else
165  	      {
166  	         /* if there are variables which are not present in the LP, e.g., for 
167  	          * column generation, we need to check their bounds
168  	          */
169  	         SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, checklprows, &stored) );
170  	      }
171  	
172  	      if( stored )
173  	      {
174  	#ifdef SCIP_DEBUG
175  	         SCIPdebugMsg(scip, "found feasible rounded solution:\n");
176  	         SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
177  	#endif
178  	         *result = SCIP_FOUNDSOL;
179  	      }
180  	   }
181  	   return SCIP_OKAY;
182  	}
183  	
184  	/** perform LP-rounding */
185  	static
186  	SCIP_RETCODE performLPSimpleRounding(
187  	   SCIP*                 scip,               /**< SCIP main data structure */
188  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
189  	   SCIP_HEURTIMING       heurtiming,         /**< heuristic timing mask */
190  	   SCIP_RESULT*          result              /**< pointer to store the result of the heuristic call */
191  	   )
192  	{
193  	   SCIP_SOL* sol;
194  	   SCIP_VAR** lpcands;
195  	   SCIP_Real* lpcandssol;
196  	   SCIP_Longint nlps;
197  	   int nlpcands;
198  	   int nfracimplvars;
199  	
200  	   /* only call heuristic, if an optimal LP solution is at hand */
201  	   if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
202  	      return SCIP_OKAY;
203  	
204  	   /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
205  	   if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
206  	      return SCIP_OKAY;
207  	
208  	   /* get fractional variables, that should be integral */
209  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, &nfracimplvars) );
210  	
211  	   /* only call heuristic, if LP solution is fractional; except we are called during pricing, in this case we
212  	    * want to detect a (mixed) integer (LP) solution which is primal feasible
213  	    */
214  	   if ( nlpcands == 0  && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP )
215  	      return SCIP_OKAY;
216  	
217  	   /* don't call heuristic, if there are more fractional variables than roundable ones. We do not consider
218  	    * fractional implicit integer variables here, because simple rounding may adjust those separately,
219  	    * even if they aren't roundable
220  	    */
221  	   if ( nlpcands > heurdata->nroundablevars )
222  	      return SCIP_OKAY;
223  	
224  	   /* get the working solution from heuristic's local data */
225  	   sol = heurdata->sol;
226  	   assert( sol != NULL );
227  	
228  	   /* copy the current LP solution to the working solution */
229  	   SCIP_CALL( SCIPlinkLPSol(scip, sol) );
230  	
231  	   /* don't call heuristic, if we have already processed the current LP solution */
232  	   nlps = SCIPgetNLPs(scip);
233  	   if( nlps == heurdata->lastlp )
234  	      return SCIP_OKAY;
235  	   heurdata->lastlp = nlps;
236  	
237  	   /* perform simple rounding */
238  	   SCIPdebugMsg(scip, "executing simple LP-rounding heuristic, fractionals: %d + %d\n", nlpcands, nfracimplvars);
239  	   SCIP_CALL( performSimpleRounding(scip, sol, lpcands, lpcandssol, nlpcands + nfracimplvars, result) );
240  	
241  	   return SCIP_OKAY;
242  	}
243  	
244  	/** perform relaxation solution rounding */
245  	static
246  	SCIP_RETCODE performRelaxSimpleRounding(
247  	   SCIP*                 scip,               /**< SCIP main data structure */
248  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
249  	   SCIP_RESULT*          result              /**< pointer to store the result of the heuristic call */
250  	   )
251  	{
252  	   SCIP_SOL* sol;
253  	   SCIP_VAR** vars;
254  	   SCIP_VAR** relaxcands;
255  	   SCIP_Real* relaxcandssol;
256  	   int nrelaxcands = 0;
257  	   int nbinvars;
258  	   int nintvars;
259  	   int nimplvars;
260  	   int ndiscretevars;
261  	   int v;
262  	
263  	   /* do not call heuristic if no relaxation solution is available */
264  	   if ( ! SCIPisRelaxSolValid(scip) )
265  	      return SCIP_OKAY;
266  	
267  	   /* get variables */
268  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, &nimplvars, NULL) );
269  	   ndiscretevars = nbinvars + nintvars + nimplvars; /* consider binary, integral, and implicit integer variables */
270  	
271  	   /* get storage */
272  	   SCIP_CALL( SCIPallocBufferArray(scip, &relaxcands, ndiscretevars) );
273  	   SCIP_CALL( SCIPallocBufferArray(scip, &relaxcandssol, ndiscretevars) );
274  	
275  	   /* get fractional variables, that should be integral */
276  	   for (v = 0; v < nbinvars + nintvars; ++v)
277  	   {
278  	      SCIP_Real val;
279  	
280  	      val = SCIPgetRelaxSolVal(scip, vars[v]);
281  	      if ( ! SCIPisFeasIntegral(scip, val) )
282  	      {
283  	         relaxcands[nrelaxcands] = vars[v];
284  	         relaxcandssol[nrelaxcands++] = val;
285  	      }
286  	   }
287  	
288  	   /* don't call heuristic, if there are more fractional variables than roundable ones. We explicitly
289  	    * do not consider implicit integer variables with fractional relaxation solution here
290  	    * because they may be feasibly adjusted, although they are not roundable
291  	    */
292  	   if ( nrelaxcands > heurdata->nroundablevars )
293  	   {
294  	      SCIPfreeBufferArray(scip, &relaxcands);
295  	      SCIPfreeBufferArray(scip, &relaxcandssol);
296  	      return SCIP_OKAY;
297  	   }
298  	
299  	   /* collect implicit integer variables with fractional solution value */
300  	   for( v = nbinvars + nintvars; v < ndiscretevars; ++v )
301  	   {
302  	      SCIP_Real val;
303  	
304  	      val = SCIPgetRelaxSolVal(scip, vars[v]);
305  	      if ( ! SCIPisFeasIntegral(scip, val) )
306  	      {
307  	         relaxcands[nrelaxcands] = vars[v];
308  	         relaxcandssol[nrelaxcands++] = val;
309  	      }
310  	   }
311  	   /* get the working solution from heuristic's local data */
312  	   sol = heurdata->sol;
313  	   assert( sol != NULL );
314  	
315  	   /* copy the current relaxation solution to the working solution */
316  	   SCIP_CALL( SCIPlinkRelaxSol(scip, sol) );
317  	
318  	   /* perform simple rounding */
319  	   SCIPdebugMsg(scip, "executing simple rounding heuristic on relaxation solution: %d fractionals\n", nrelaxcands);
320  	   SCIP_CALL( performSimpleRounding(scip, sol, relaxcands, relaxcandssol, nrelaxcands, result) );
321  	
322  	   /* free storage */
323  	   SCIPfreeBufferArray(scip, &relaxcands);
324  	   SCIPfreeBufferArray(scip, &relaxcandssol);
325  	
326  	   return SCIP_OKAY;
327  	}
328  	
329  	
330  	/*
331  	 * Callback methods
332  	 */
333  	
334  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
335  	static
336  	SCIP_DECL_HEURCOPY(heurCopySimplerounding)
337  	{  /*lint --e{715}*/
338  	   assert(scip != NULL);
339  	   assert(heur != NULL);
340  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
341  	
342  	   /* call inclusion method of primal heuristic */
343  	   SCIP_CALL( SCIPincludeHeurSimplerounding(scip) );
344  	
345  	   return SCIP_OKAY;
346  	}
347  	
348  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
349  	static
350  	SCIP_DECL_HEURFREE(heurFreeSimplerounding) /*lint --e{715}*/
351  	{  /*lint --e{715}*/
352  	   SCIP_HEURDATA* heurdata;
353  	
354  	   assert(heur != NULL);
355  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
356  	   assert(scip != NULL);
357  	
358  	   /* free heuristic data */
359  	   heurdata = SCIPheurGetData(heur);
360  	   assert(heurdata != NULL);
361  	   SCIPfreeBlockMemory(scip, &heurdata);
362  	   SCIPheurSetData(heur, NULL);
363  	
364  	   return SCIP_OKAY;
365  	}
366  	
367  	
368  	/** initialization method of primal heuristic (called after problem was transformed) */
369  	static
370  	SCIP_DECL_HEURINIT(heurInitSimplerounding) /*lint --e{715}*/
371  	{  /*lint --e{715}*/
372  	   SCIP_HEURDATA* heurdata;
373  	
374  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
375  	   heurdata = SCIPheurGetData(heur);
376  	   assert(heurdata != NULL);
377  	
378  	   /* create heuristic data */
379  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
380  	   heurdata->lastlp = -1;
381  	   heurdata->nroundablevars = -1;
382  	
383  	   return SCIP_OKAY;
384  	}
385  	
386  	
387  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
388  	static
389  	SCIP_DECL_HEUREXIT(heurExitSimplerounding) /*lint --e{715}*/
390  	{  /*lint --e{715}*/
391  	   SCIP_HEURDATA* heurdata;
392  	
393  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
394  	
395  	   /* free heuristic data */
396  	   heurdata = SCIPheurGetData(heur);
397  	   assert(heurdata != NULL);
398  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
399  	
400  	   return SCIP_OKAY;
401  	}
402  	
403  	
404  	/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
405  	static
406  	SCIP_DECL_HEURINITSOL(heurInitsolSimplerounding)
407  	{
408  	   SCIP_HEURDATA* heurdata;
409  	
410  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
411  	
412  	   heurdata = SCIPheurGetData(heur);
413  	   assert(heurdata != NULL);
414  	   heurdata->lastlp = -1;
415  	
416  	   /* change the heuristic's timingmask, if it should be called only once per node */
417  	   if( heurdata->oncepernode )
418  	      SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_AFTERLPNODE);
419  	
420  	   return SCIP_OKAY;
421  	}
422  	
423  	
424  	/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
425  	static
426  	SCIP_DECL_HEUREXITSOL(heurExitsolSimplerounding)
427  	{
428  	   /* reset the timing mask to its default value */
429  	   SCIPheurSetTimingmask(heur, HEUR_TIMING);
430  	
431  	   return SCIP_OKAY;
432  	}
433  	
434  	
435  	/** execution method of primal heuristic */
436  	static
437  	SCIP_DECL_HEUREXEC(heurExecSimplerounding) /*lint --e{715}*/
438  	{  /*lint --e{715}*/
439  	   SCIP_HEURDATA* heurdata;
440  	
441  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
442  	   assert(result != NULL);
443  	   assert(SCIPhasCurrentNodeLP(scip));
444  	
445  	   *result = SCIP_DIDNOTRUN;
446  	
447  	   /* only call heuristic, if an optimal LP solution is at hand or if relaxation solution is available */
448  	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && ! SCIPisRelaxSolValid(scip) )
449  	      return SCIP_OKAY;
450  	
451  	   /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
452  	   if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
453  	      return SCIP_OKAY;
454  	
455  	   /* get heuristic data */
456  	   heurdata = SCIPheurGetData(heur);
457  	   assert(heurdata != NULL);
458  	
459  	   /* don't call heuristic, if we have already processed the current LP solution but no relaxation solution is available */
460  	   if ( SCIPgetNLPs(scip) == heurdata->lastlp && ! SCIPisRelaxSolValid(scip) )
461  	      return SCIP_OKAY;
462  	
463  	   /* on our first call or after each pricing round, calculate the number of roundable variables */
464  	   if( heurdata->nroundablevars == -1  || heurtiming == SCIP_HEURTIMING_DURINGPRICINGLOOP )
465  	   {
466  	      SCIP_VAR** vars;
467  	      int nbinintvars;
468  	      int nroundablevars;
469  	      int i;
470  	
471  	      vars = SCIPgetVars(scip);
472  	      nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
473  	      nroundablevars = 0;
474  	      for( i = 0; i < nbinintvars; ++i )
475  	      {
476  	         if( SCIPvarMayRoundDown(vars[i]) || SCIPvarMayRoundUp(vars[i]) )
477  	            nroundablevars++;
478  	      }
479  	      heurdata->nroundablevars = nroundablevars;
480  	   }
481  	
482  	   /* don't call heuristic if there are no roundable variables; except we are called during pricing, in this case we
483  	    * want to detect a (mixed) integer (LP) solution which is primal feasible */
484  	   if( heurdata->nroundablevars == 0 && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP )
485  	      return SCIP_OKAY;
486  	
487  	   *result = SCIP_DIDNOTFIND;
488  	
489  	   /* try to round LP solution */
490  	   SCIP_CALL( performLPSimpleRounding(scip, heurdata, heurtiming, result) );
491  	
492  	   /* try to round relaxation solution */
493  	   SCIP_CALL( performRelaxSimpleRounding(scip, heurdata, result) );
494  	
495  	   return SCIP_OKAY;
496  	}
497  	
498  	/*
499  	 * heuristic specific interface methods
500  	 */
501  	
502  	/** creates the simple rounding heuristic and includes it in SCIP */
503  	SCIP_RETCODE SCIPincludeHeurSimplerounding(
504  	   SCIP*                 scip                /**< SCIP data structure */
505  	   )
506  	{
507  	   SCIP_HEURDATA* heurdata;
508  	   SCIP_HEUR* heur;
509  	
510  	   /* create heuristic data */
511  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
512  	
513  	   /* include primal heuristic */
514  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
515  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
516  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSimplerounding, heurdata) );
517  	   assert(heur != NULL);
518  	
519  	   /* set non-NULL pointers to callback methods */
520  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySimplerounding) );
521  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSimplerounding) );
522  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSimplerounding) );
523  	   SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolSimplerounding) );
524  	   SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolSimplerounding) );
525  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSimplerounding) );
526  	
527  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/oncepernode",
528  	         "should the heuristic only be called once per node?",
529  	         &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) );
530  	
531  	   return SCIP_OKAY;
532  	}
533