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_trivial.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  trivial primal heuristic
28   	 * @author Timo Berthold
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/heur_trivial.h"
34   	#include "scip/pub_heur.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_var.h"
37   	#include "scip/scip_heur.h"
38   	#include "scip/scip_message.h"
39   	#include "scip/scip_numerics.h"
40   	#include "scip/scip_prob.h"
41   	#include "scip/scip_sol.h"
42   	#include "scip/scip_solvingstats.h"
43   	#include <string.h>
44   	
45   	#define HEUR_NAME             "trivial"
46   	#define HEUR_DESC             "start heuristic which tries some trivial solutions"
47   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_TRIVIAL
48   	#define HEUR_PRIORITY         10000
49   	#define HEUR_FREQ             0
50   	#define HEUR_FREQOFS          0
51   	#define HEUR_MAXDEPTH         -1
52   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
53   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
54   	
55   	/*
56   	 * Local methods
57   	 */
58   	
59   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
60   	static
61   	SCIP_DECL_HEURCOPY(heurCopyTrivial)
62   	{  /*lint --e{715}*/
63   	   assert(scip != NULL);
64   	   assert(heur != NULL);
65   	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
66   	
67   	   /* call inclusion method of primal heuristic */
68   	   SCIP_CALL( SCIPincludeHeurTrivial(scip) );
69   	
70   	   return SCIP_OKAY;
71   	}
72   	
73   	
74   	/** execution method of primal heuristic */
75   	static
76   	SCIP_DECL_HEUREXEC(heurExecTrivial)
77   	{  /*lint --e{715}*/
78   	   SCIP_VAR** vars;
79   	   SCIP_SOL* zerosol;                   /* solution where all variables are set next to zero within bounds */
80   	   SCIP_SOL* lbsol;                     /* solution where all variables are set to their lower bounds */
81   	   SCIP_SOL* ubsol;                     /* solution where all variables are set to their upper bounds */
82   	   SCIP_SOL* locksol;                   /* solution where all variables are set to the bound with the fewer locks */
83   	   SCIP_Real large;
84   	   SCIP_Bool difflb;
85   	   SCIP_Bool diffub;
86   	   SCIP_Bool difflock;
87   	   SCIP_Bool success;
88   	   int nvars;
89   	   int i;
90   	
91   	   *result = SCIP_DIDNOTFIND;
92   	
93   	   /* initialize data structure */
94   	   SCIP_CALL( SCIPcreateSol(scip, &zerosol, heur) );
95   	   SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) );
96   	   SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) );
97   	   SCIP_CALL( SCIPcreateSol(scip, &locksol, heur) );
98   	
99   	   /* determine large value to set variables to */
100  	   large = SCIPround(scip, MIN(1.0 / SCIPfeastol(scip), SCIPgetHugeValue(scip)) / 10.0); /*lint !e666 */
101  	
102  	   /* check zero solution once */
103  	   difflb = FALSE;
104  	   diffub = FALSE;
105  	   difflock = FALSE;
106  	
107  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
108  	   assert(vars != NULL || nvars == 0);
109  	
110  	   for( i = 0; i < nvars; ++i )
111  	   {
112  	      SCIP_Real lb;
113  	      SCIP_Real ub;
114  	      SCIP_Real zeroval;
115  	      SCIP_Real solval;
116  	
117  	      assert(vars != NULL); /* this assert is needed for flexelint */
118  	
119  	      lb = SCIPvarGetLbLocal(vars[i]);
120  	      ub = SCIPvarGetUbLocal(vars[i]);
121  	
122  	      /* if problem is obviously infeasible due to empty domain, stop */
123  	      if( SCIPisFeasGT(scip, lb, ub) )
124  	         goto TERMINATE;
125  	
126  	      /* set bounds to sufficient large value */
127  	      if( SCIPisInfinity(scip, -lb) )
128  	         lb = MIN(-large, ub);
129  	      if( SCIPisInfinity(scip, ub) )
130  	         ub = MAX(large, lb);
131  	
132  	      /* set value next to zero within bounds */
133  	      zeroval = MAX(MIN(0.0, ub), lb);
134  	
135  	      /* set value to the bound with fewer locks, if tie choose an average value */
136  	      if( SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) < SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) )
137  	         solval = lb;
138  	      else if( SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) > SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) )
139  	         solval = ub;
140  	      else
141  	      {
142  	         solval = (lb+ub)/2.0;
143  	
144  	         /* if a tie occurs, roughly every third integer variable will be rounded up */
145  	         if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS )
146  	            solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval);
147  	
148  	         assert(SCIPisFeasLE(scip,SCIPvarGetLbLocal(vars[i]),solval) && SCIPisFeasLE(scip,solval,SCIPvarGetUbLocal(vars[i])));
149  	      }
150  	
151  	      if( !SCIPisEQ(scip, lb, zeroval) )
152  	         difflb = TRUE;
153  	
154  	      if( !SCIPisEQ(scip, ub, zeroval) )
155  	         diffub = TRUE;
156  	
157  	      if( !SCIPisEQ(scip, solval, zeroval) )
158  	         difflock = TRUE;
159  	
160  	      /* set variable to values */
161  	      SCIP_CALL( SCIPsetSolVal(scip, zerosol, vars[i], zeroval) );
162  	      SCIP_CALL( SCIPsetSolVal(scip, lbsol, vars[i], lb) );
163  	      SCIP_CALL( SCIPsetSolVal(scip, ubsol, vars[i], ub) );
164  	      SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], solval) );
165  	   }
166  	
167  	   /* try zero solution */
168  	   SCIPdebugMsg(scip, "try zero solution\n");
169  	   SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
170  	
171  	   if( success )
172  	   {
173  	      SCIPdebugMsg(scip, "found feasible zero solution:\n");
174  	      SCIPdebug( SCIP_CALL( SCIPprintSol(scip, zerosol, NULL, FALSE) ) );
175  	
176  	      *result = SCIP_FOUNDSOL;
177  	   }
178  	
179  	   /* try lower bound solution */
180  	   if( difflb )
181  	   {
182  	      SCIPdebugMsg(scip, "try lower bound solution\n");
183  	      SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
184  	
185  	      if( success )
186  	      {
187  	         SCIPdebugMsg(scip, "found feasible lower bound solution:\n");
188  	         SCIPdebug( SCIP_CALL( SCIPprintSol(scip, lbsol, NULL, FALSE) ) );
189  	
190  	         *result = SCIP_FOUNDSOL;
191  	      }
192  	   }
193  	
194  	   /* try upper bound solution */
195  	   if( diffub )
196  	   {
197  	      SCIPdebugMsg(scip, "try upper bound solution\n");
198  	      SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
199  	
200  	      if( success )
201  	      {
202  	         SCIPdebugMsg(scip, "found feasible upper bound solution:\n");
203  	         SCIPdebug( SCIP_CALL( SCIPprintSol(scip, ubsol, NULL, FALSE) ) );
204  	
205  	         *result = SCIP_FOUNDSOL;
206  	      }
207  	   }
208  	
209  	   /* try lock solution */
210  	   if( difflock )
211  	   {
212  	      SCIPdebugMsg(scip, "try lock solution\n");
213  	      SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
214  	
215  	      if( success )
216  	      {
217  	         SCIPdebugMsg(scip, "found feasible lock solution:\n");
218  	         SCIPdebug( SCIP_CALL( SCIPprintSol(scip, locksol, NULL, FALSE) ) );
219  	
220  	         *result = SCIP_FOUNDSOL;
221  	      }
222  	   }
223  	
224  	TERMINATE:
225  	   /* free solutions */
226  	   SCIP_CALL( SCIPfreeSol(scip, &locksol) );
227  	   SCIP_CALL( SCIPfreeSol(scip, &ubsol) );
228  	   SCIP_CALL( SCIPfreeSol(scip, &lbsol) );
229  	   SCIP_CALL( SCIPfreeSol(scip, &zerosol) );
230  	
231  	   return SCIP_OKAY;
232  	}
233  	
234  	
235  	/*
236  	 * primal heuristic specific interface methods
237  	 */
238  	
239  	/** creates the trivial primal heuristic and includes it in SCIP */
240  	SCIP_RETCODE SCIPincludeHeurTrivial(
241  	   SCIP*                 scip                /**< SCIP data structure */
242  	   )
243  	{
244  	   SCIP_HEUR* heur;
245  	
246  	   /* include primal heuristic */
247  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
248  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
249  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivial, NULL) );
250  	
251  	   assert(heur != NULL);
252  	
253  	   /* set non-NULL pointers to callback methods */
254  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivial) );
255  	
256  	   return SCIP_OKAY;
257  	}
258