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