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-2018 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 visit 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 "scip/heur_trivial.h"
24 #include "scip/pub_heur.h"
25 #include "scip/pub_message.h"
26 #include "scip/pub_var.h"
27 #include "scip/scip_heur.h"
28 #include "scip/scip_message.h"
29 #include "scip/scip_numerics.h"
30 #include "scip/scip_prob.h"
31 #include "scip/scip_sol.h"
32 #include "scip/scip_solvingstats.h"
33 #include <string.h>
34 
35 #define HEUR_NAME "trivial"
36 #define HEUR_DESC "start heuristic which tries some trivial solutions"
37 #define HEUR_DISPCHAR 't'
38 #define HEUR_PRIORITY 10000
39 #define HEUR_FREQ 0
40 #define HEUR_FREQOFS 0
41 #define HEUR_MAXDEPTH -1
42 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
43 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
44 
45 /*
46  * Local methods
47  */
48 
49 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
50 static
51 SCIP_DECL_HEURCOPY(heurCopyTrivial)
52 { /*lint --e{715}*/
53  assert(scip != NULL);
54  assert(heur != NULL);
55  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
56 
57  /* call inclusion method of primal heuristic */
59 
60  return SCIP_OKAY;
61 }
62 
63 
64 /** execution method of primal heuristic */
65 static
66 SCIP_DECL_HEUREXEC(heurExecTrivial)
67 { /*lint --e{715}*/
68  SCIP_VAR** vars;
69  SCIP_SOL* lbsol; /* solution where all variables are set to their lower bounds */
70  SCIP_SOL* ubsol; /* solution where all variables are set to their upper bounds */
71  SCIP_SOL* zerosol; /* solution where all variables are set to zero */
72  SCIP_SOL* locksol; /* solution where all variables are set to the bound with the fewer locks */
73 
74  SCIP_Real large;
75 
76  int nvars;
77  int nbinvars;
78  int i;
79 
80  SCIP_Bool success;
81  SCIP_Bool zerovalid;
82 
83  *result = SCIP_DIDNOTRUN;
84 
85  if( SCIPgetNRuns(scip) > 1 )
86  return SCIP_OKAY;
87 
88  *result = SCIP_DIDNOTFIND;
89  success = FALSE;
90 
91  /* initialize data structure */
92  SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) );
93  SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) );
94  SCIP_CALL( SCIPcreateSol(scip, &zerosol, heur) );
95  SCIP_CALL( SCIPcreateSol(scip, &locksol, heur) );
96 
97  /* determine large value to set variables to */
98  large = SCIPinfinity(scip);
99  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
100  large = 0.1 / SCIPfeastol(scip);
101 
102  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
103 
104  /* if the problem is binary, we do not have to check the zero solution, since it is equal to the lower bound
105  * solution */
106  zerovalid = (nvars != nbinvars);
107  assert(vars != NULL || nvars == 0);
108 
109  for( i = 0; i < nvars; i++ )
110  {
111  SCIP_Real lb;
112  SCIP_Real ub;
113 
114  assert(vars != NULL); /* this assert is needed for flexelint */
115 
116  lb = SCIPvarGetLbLocal(vars[i]);
117  ub = SCIPvarGetUbLocal(vars[i]);
118 
119  /* if problem is obviously infeasible due to empty domain, stop */
120  if( SCIPisGT(scip, lb, ub) )
121  goto TERMINATE;
122 
123  /* set bounds to sufficient large value */
124  if( SCIPisInfinity(scip, -lb) )
125  lb = MIN(-large, ub);
126  if( SCIPisInfinity(scip, ub) )
127  {
128  SCIP_Real tmp;
129 
130  tmp = SCIPvarGetLbLocal(vars[i]);
131  ub = MAX(tmp, large);
132  }
133 
134  SCIP_CALL( SCIPsetSolVal(scip, lbsol, vars[i], lb) );
135  SCIP_CALL( SCIPsetSolVal(scip, ubsol, vars[i], ub) );
136 
137  /* try the zero vector, if it is in the bounds region */
138  if( zerovalid )
139  {
140  if( SCIPisLE(scip, lb, 0.0) && SCIPisLE(scip, 0.0, ub) )
141  {
142  SCIP_CALL( SCIPsetSolVal(scip, zerosol, vars[i], 0.0) );
143  }
144  else
145  zerovalid = FALSE;
146  }
147 
148  /* set variables to the bound with fewer locks, if tie choose an average value */
150  {
151  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], ub) );
152  }
154  {
155  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], lb) );
156  }
157  else
158  {
159  SCIP_Real solval;
160  solval = (lb+ub)/2.0;
161 
162  /* if a tie occurs, roughly every third integer variable will be rounded up */
163  if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS )
164  solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval);
165 
166  assert(SCIPisFeasLE(scip,SCIPvarGetLbLocal(vars[i]),solval) && SCIPisFeasLE(scip,solval,SCIPvarGetUbLocal(vars[i])));
167 
168  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], solval) );
169  }
170  }
171 
172  /* try lower bound solution */
173  SCIPdebugMsg(scip, "try lower bound solution\n");
174  SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
175 
176  if( success )
177  {
178  SCIPdebugMsg(scip, "found feasible lower bound solution:\n");
179  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, lbsol, NULL, FALSE) ) );
180 
181  *result = SCIP_FOUNDSOL;
182  }
183 
184  /* try upper bound solution */
185  SCIPdebugMsg(scip, "try upper bound solution\n");
186  SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
187 
188  if( success )
189  {
190  SCIPdebugMsg(scip, "found feasible upper bound solution:\n");
191  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, ubsol, NULL, FALSE) ) );
192 
193  *result = SCIP_FOUNDSOL;
194  }
195 
196  /* try zero solution */
197  if( zerovalid )
198  {
199  SCIPdebugMsg(scip, "try zero solution\n");
200  SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
201 
202  if( success )
203  {
204  SCIPdebugMsg(scip, "found feasible zero solution:\n");
205  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, zerosol, NULL, FALSE) ) );
206 
207  *result = SCIP_FOUNDSOL;
208  }
209  }
210 
211  /* try lock solution */
212  SCIPdebugMsg(scip, "try lock solution\n");
213  SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, FALSE, TRUE, 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 TERMINATE:
224  /* free solutions */
225  SCIP_CALL( SCIPfreeSol(scip, &lbsol) );
226  SCIP_CALL( SCIPfreeSol(scip, &ubsol) );
227  SCIP_CALL( SCIPfreeSol(scip, &zerosol) );
228  SCIP_CALL( SCIPfreeSol(scip, &locksol) );
229 
230  return SCIP_OKAY;
231 }
232 
233 
234 /*
235  * primal heuristic specific interface methods
236  */
237 
238 /** creates the trivial primal heuristic and includes it in SCIP */
240  SCIP* scip /**< SCIP data structure */
241  )
242 {
243  SCIP_HEUR* heur;
244 
245  /* include primal heuristic */
246  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
248  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivial, NULL) );
249 
250  assert(heur != NULL);
251 
252  /* set non-NULL pointers to callback methods */
253  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivial) );
254 
255  return SCIP_OKAY;
256 }
#define NULL
Definition: def.h:239
SCIP_Real SCIPfeastol(SCIP *scip)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
trivial primal heuristic
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1918
#define FALSE
Definition: def.h:65
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:64
#define SCIPdebug(x)
Definition: pub_message.h:74
#define HEUR_DISPCHAR
Definition: heur_trivial.c:37
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define HEUR_TIMING
Definition: heur_trivial.c:42
public methods for problem variables
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_heur.c:187
#define SCIPdebugMsg
Definition: scip_message.h:88
#define HEUR_NAME
Definition: heur_trivial.c:35
public methods for numerical tolerances
public methods for querying solving statistics
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
#define HEUR_USESSUBSCIP
Definition: heur_trivial.c:43
#define HEUR_FREQOFS
Definition: heur_trivial.c:40
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for primal heuristic plugins and divesets
static SCIP_DECL_HEURCOPY(heurCopyTrivial)
Definition: heur_trivial.c:51
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1270
#define SCIP_Bool
Definition: def.h:62
#define HEUR_FREQ
Definition: heur_trivial.c:39
#define MIN(x, y)
Definition: def.h:209
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:1034
int SCIPgetNRuns(SCIP *scip)
#define HEUR_MAXDEPTH
Definition: heur_trivial.c:41
SCIP_RETCODE SCIPincludeHeurTrivial(SCIP *scip)
Definition: heur_trivial.c:239
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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_sol.c:3197
#define MAX(x, y)
Definition: def.h:208
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
public methods for message output
#define SCIP_Real
Definition: def.h:150
public methods for message handling
#define HEUR_DESC
Definition: heur_trivial.c:36
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
public methods for primal heuristics
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
public methods for global and local (sub)problems
static SCIP_DECL_HEUREXEC(heurExecTrivial)
Definition: heur_trivial.c:66
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377
#define HEUR_PRIORITY
Definition: heur_trivial.c:38
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1824