Scippy

SCIP

Solving Constraint Integer Programs

heur_trivial.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_trivial.c
17  * @brief trivial primal heuristic
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/heur_trivial.h"
27 
28 
29 #define HEUR_NAME "trivial"
30 #define HEUR_DESC "start heuristic which tries some trivial solutions"
31 #define HEUR_DISPCHAR 't'
32 #define HEUR_PRIORITY 10000
33 #define HEUR_FREQ 0
34 #define HEUR_FREQOFS 0
35 #define HEUR_MAXDEPTH -1
36 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
37 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
38 
39 /*
40  * Local methods
41  */
42 
43 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
44 static
45 SCIP_DECL_HEURCOPY(heurCopyTrivial)
46 { /*lint --e{715}*/
47  assert(scip != NULL);
48  assert(heur != NULL);
49  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
50 
51  /* call inclusion method of primal heuristic */
53 
54  return SCIP_OKAY;
55 }
56 
57 
58 /** execution method of primal heuristic */
59 static
60 SCIP_DECL_HEUREXEC(heurExecTrivial)
61 { /*lint --e{715}*/
62  SCIP_VAR** vars;
63  SCIP_SOL* lbsol; /* solution where all variables are set to their lower bounds */
64  SCIP_SOL* ubsol; /* solution where all variables are set to their upper bounds */
65  SCIP_SOL* zerosol; /* solution where all variables are set to zero */
66  SCIP_SOL* locksol; /* solution where all variables are set to the bound with the fewer locks */
67 
68  SCIP_Real large;
69 
70  int nvars;
71  int nbinvars;
72  int i;
73 
74  SCIP_Bool success;
75  SCIP_Bool zerovalid;
76 
77  *result = SCIP_DIDNOTRUN;
78 
79  if( SCIPgetNRuns(scip) > 1 )
80  return SCIP_OKAY;
81 
82  *result = SCIP_DIDNOTFIND;
83  success = FALSE;
84 
85  /* initialize data structure */
86  SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) );
87  SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) );
88  SCIP_CALL( SCIPcreateSol(scip, &zerosol, heur) );
89  SCIP_CALL( SCIPcreateSol(scip, &locksol, heur) );
90 
91  /* determine large value to set variables to */
92  large = SCIPinfinity(scip);
93  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
94  large = 0.1 / SCIPfeastol(scip);
95 
96  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
97 
98  /* if the problem is binary, we do not have to check the zero solution, since it is equal to the lower bound
99  * solution */
100  zerovalid = (nvars != nbinvars);
101  assert(vars != NULL || nvars == 0);
102 
103  for( i = 0; i < nvars; i++ )
104  {
105  SCIP_Real lb;
106  SCIP_Real ub;
107 
108  assert(vars != NULL); /* this assert is needed for flexelint */
109 
110  lb = SCIPvarGetLbLocal(vars[i]);
111  ub = SCIPvarGetUbLocal(vars[i]);
112 
113  /* if problem is obviously infeasible due to empty domain, stop */
114  if( SCIPisGT(scip, lb, ub) )
115  goto TERMINATE;
116 
117  /* set bounds to sufficient large value */
118  if( SCIPisInfinity(scip, -lb) )
119  lb = MIN(-large, ub);
120  if( SCIPisInfinity(scip, ub) )
121  {
122  SCIP_Real tmp;
123 
124  tmp = SCIPvarGetLbLocal(vars[i]);
125  ub = MAX(tmp, large);
126  }
127 
128  SCIP_CALL( SCIPsetSolVal(scip, lbsol, vars[i], lb) );
129  SCIP_CALL( SCIPsetSolVal(scip, ubsol, vars[i], ub) );
130 
131  /* try the zero vector, if it is in the bounds region */
132  if( zerovalid )
133  {
134  if( SCIPisLE(scip, lb, 0.0) && SCIPisLE(scip, 0.0, ub) )
135  {
136  SCIP_CALL( SCIPsetSolVal(scip, zerosol, vars[i], 0.0) );
137  }
138  else
139  zerovalid = FALSE;
140  }
141 
142  /* set variables to the bound with fewer locks, if tie choose an average value */
143  if( SCIPvarGetNLocksDown(vars[i]) > SCIPvarGetNLocksUp(vars[i]) )
144  {
145  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], ub) );
146  }
147  else if( SCIPvarGetNLocksDown(vars[i]) < SCIPvarGetNLocksUp(vars[i]) )
148  {
149  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], lb) );
150  }
151  else
152  {
153  SCIP_Real solval;
154  solval = (lb+ub)/2.0;
155 
156  /* if a tie occurs, roughly every third integer variable will be rounded up */
157  if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS )
158  solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval);
159 
160  assert(SCIPisFeasLE(scip,SCIPvarGetLbLocal(vars[i]),solval) && SCIPisFeasLE(scip,solval,SCIPvarGetUbLocal(vars[i])));
161 
162  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], solval) );
163  }
164  }
165 
166  /* try lower bound solution */
167  SCIPdebugMessage("try lower bound solution\n");
168  SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, TRUE, TRUE, &success) );
169 
170  if( success )
171  {
172  SCIPdebugMessage("found feasible lower bound solution:\n");
173  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, lbsol, NULL, FALSE) ) );
174 
175  *result = SCIP_FOUNDSOL;
176  }
177 
178  /* try upper bound solution */
179  SCIPdebugMessage("try upper bound solution\n");
180  SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, TRUE, TRUE, &success) );
181 
182  if( success )
183  {
184  SCIPdebugMessage("found feasible upper bound solution:\n");
185  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, ubsol, NULL, FALSE) ) );
186 
187  *result = SCIP_FOUNDSOL;
188  }
189 
190  /* try zero solution */
191  if( zerovalid )
192  {
193  SCIPdebugMessage("try zero solution\n");
194  SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, TRUE, TRUE, &success) );
195 
196  if( success )
197  {
198  SCIPdebugMessage("found feasible zero solution:\n");
199  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, zerosol, NULL, FALSE) ) );
200 
201  *result = SCIP_FOUNDSOL;
202  }
203  }
204 
205  /* try lock solution */
206  SCIPdebugMessage("try lock solution\n");
207  SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, TRUE, TRUE, &success) );
208 
209  if( success )
210  {
211  SCIPdebugMessage("found feasible lock solution:\n");
212  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, locksol, NULL, FALSE) ) );
213 
214  *result = SCIP_FOUNDSOL;
215  }
216 
217 TERMINATE:
218  /* free solutions */
219  SCIP_CALL( SCIPfreeSol(scip, &lbsol) );
220  SCIP_CALL( SCIPfreeSol(scip, &ubsol) );
221  SCIP_CALL( SCIPfreeSol(scip, &zerosol) );
222  SCIP_CALL( SCIPfreeSol(scip, &locksol) );
223 
224  return SCIP_OKAY;
225 }
226 
227 
228 /*
229  * primal heuristic specific interface methods
230  */
231 
232 /** creates the trivial primal heuristic and includes it in SCIP */
234  SCIP* scip /**< SCIP data structure */
235  )
236 {
237  SCIP_HEUR* heur;
238 
239  /* include primal heuristic */
240  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
242  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivial, NULL) );
243 
244  assert(heur != NULL);
245 
246  /* set non-NULL pointers to callback methods */
247  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivial) );
248 
249  return SCIP_OKAY;
250 }
251