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-2017 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  SCIPdebugMsg(scip, "try lower bound solution\n");
168  SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
169 
170  if( success )
171  {
172  SCIPdebugMsg(scip, "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  SCIPdebugMsg(scip, "try upper bound solution\n");
180  SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
181 
182  if( success )
183  {
184  SCIPdebugMsg(scip, "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  SCIPdebugMsg(scip, "try zero solution\n");
194  SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
195 
196  if( success )
197  {
198  SCIPdebugMsg(scip, "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  SCIPdebugMsg(scip, "try lock solution\n");
207  SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
208 
209  if( success )
210  {
211  SCIPdebugMsg(scip, "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 }
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45274
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
trivial primal heuristic
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
#define HEUR_DISPCHAR
Definition: heur_trivial.c:31
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define HEUR_TIMING
Definition: heur_trivial.c:36
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:7999
#define SCIPdebugMsg
Definition: scip.h:451
#define HEUR_NAME
Definition: heur_trivial.c:29
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define HEUR_USESSUBSCIP
Definition: heur_trivial.c:37
#define HEUR_FREQOFS
Definition: heur_trivial.c:34
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
static SCIP_DECL_HEURCOPY(heurCopyTrivial)
Definition: heur_trivial.c:45
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:37867
#define SCIP_Bool
Definition: def.h:61
#define HEUR_FREQ
Definition: heur_trivial.c:33
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:41099
#define HEUR_MAXDEPTH
Definition: heur_trivial.c:35
SCIP_RETCODE SCIPincludeHeurTrivial(SCIP *scip)
Definition: heur_trivial.c:233
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39749
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
#define SCIP_Real
Definition: def.h:135
#define MIN(x, y)
Definition: memory.c:75
#define HEUR_DESC
Definition: heur_trivial.c:30
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:45949
static SCIP_DECL_HEUREXEC(heurExecTrivial)
Definition: heur_trivial.c:60
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005
#define HEUR_PRIORITY
Definition: heur_trivial.c:32
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38421