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-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 */
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* lbsol; /* solution where all variables are set to their lower bounds */
80  SCIP_SOL* ubsol; /* solution where all variables are set to their upper bounds */
81  SCIP_SOL* zerosol; /* solution where all variables are set to zero */
82  SCIP_SOL* locksol; /* solution where all variables are set to the bound with the fewer locks */
83 
84  SCIP_Real large;
85 
86  int nvars;
87  int nbinvars;
88  int i;
89 
90  SCIP_Bool success;
91  SCIP_Bool zerovalid;
92 
93  *result = SCIP_DIDNOTRUN;
94 
95  if( SCIPgetNRuns(scip) > 1 )
96  return SCIP_OKAY;
97 
98  *result = SCIP_DIDNOTFIND;
99  success = FALSE;
100 
101  /* initialize data structure */
102  SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) );
103  SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) );
104  SCIP_CALL( SCIPcreateSol(scip, &zerosol, heur) );
105  SCIP_CALL( SCIPcreateSol(scip, &locksol, heur) );
106 
107  /* determine large value to set variables to */
108  large = SCIPinfinity(scip);
109  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
110  large = 0.1 / SCIPfeastol(scip);
111 
112  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
113 
114  /* if the problem is binary, we do not have to check the zero solution, since it is equal to the lower bound
115  * solution */
116  zerovalid = (nvars != nbinvars);
117  assert(vars != NULL || nvars == 0);
118 
119  for( i = 0; i < nvars; i++ )
120  {
121  SCIP_Real lb;
122  SCIP_Real ub;
123 
124  assert(vars != NULL); /* this assert is needed for flexelint */
125 
126  lb = SCIPvarGetLbLocal(vars[i]);
127  ub = SCIPvarGetUbLocal(vars[i]);
128 
129  /* if problem is obviously infeasible due to empty domain, stop */
130  if( SCIPisGT(scip, lb, ub) )
131  goto TERMINATE;
132 
133  /* set bounds to sufficient large value */
134  if( SCIPisInfinity(scip, -lb) )
135  lb = MIN(-large, ub);
136  if( SCIPisInfinity(scip, ub) )
137  {
138  SCIP_Real tmp;
139 
140  tmp = SCIPvarGetLbLocal(vars[i]);
141  ub = MAX(tmp, large);
142  }
143 
144  SCIP_CALL( SCIPsetSolVal(scip, lbsol, vars[i], lb) );
145  SCIP_CALL( SCIPsetSolVal(scip, ubsol, vars[i], ub) );
146 
147  /* try the zero vector, if it is in the bounds region */
148  if( zerovalid )
149  {
150  if( SCIPisLE(scip, lb, 0.0) && SCIPisLE(scip, 0.0, ub) )
151  {
152  SCIP_CALL( SCIPsetSolVal(scip, zerosol, vars[i], 0.0) );
153  }
154  else
155  zerovalid = FALSE;
156  }
157 
158  /* set variables to the bound with fewer locks, if tie choose an average value */
160  {
161  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], ub) );
162  }
164  {
165  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], lb) );
166  }
167  else
168  {
169  SCIP_Real solval;
170  solval = (lb+ub)/2.0;
171 
172  /* if a tie occurs, roughly every third integer variable will be rounded up */
173  if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS )
174  solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval);
175 
176  assert(SCIPisFeasLE(scip,SCIPvarGetLbLocal(vars[i]),solval) && SCIPisFeasLE(scip,solval,SCIPvarGetUbLocal(vars[i])));
177 
178  SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], solval) );
179  }
180  }
181 
182  /* try lower bound solution */
183  SCIPdebugMsg(scip, "try lower bound solution\n");
184  SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
185 
186  if( success )
187  {
188  SCIPdebugMsg(scip, "found feasible lower bound solution:\n");
189  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, lbsol, NULL, FALSE) ) );
190 
191  *result = SCIP_FOUNDSOL;
192  }
193 
194  /* try upper bound solution */
195  SCIPdebugMsg(scip, "try upper bound solution\n");
196  SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
197 
198  if( success )
199  {
200  SCIPdebugMsg(scip, "found feasible upper bound solution:\n");
201  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, ubsol, NULL, FALSE) ) );
202 
203  *result = SCIP_FOUNDSOL;
204  }
205 
206  /* try zero solution */
207  if( zerovalid )
208  {
209  SCIPdebugMsg(scip, "try zero solution\n");
210  SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
211 
212  if( success )
213  {
214  SCIPdebugMsg(scip, "found feasible zero solution:\n");
215  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, zerosol, NULL, FALSE) ) );
216 
217  *result = SCIP_FOUNDSOL;
218  }
219  }
220 
221  /* try lock solution */
222  SCIPdebugMsg(scip, "try lock solution\n");
223  SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
224 
225  if( success )
226  {
227  SCIPdebugMsg(scip, "found feasible lock solution:\n");
228  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, locksol, NULL, FALSE) ) );
229 
230  *result = SCIP_FOUNDSOL;
231  }
232 
233 TERMINATE:
234  /* free solutions */
235  SCIP_CALL( SCIPfreeSol(scip, &lbsol) );
236  SCIP_CALL( SCIPfreeSol(scip, &ubsol) );
237  SCIP_CALL( SCIPfreeSol(scip, &zerosol) );
238  SCIP_CALL( SCIPfreeSol(scip, &locksol) );
239 
240  return SCIP_OKAY;
241 }
242 
243 
244 /*
245  * primal heuristic specific interface methods
246  */
247 
248 /** creates the trivial primal heuristic and includes it in SCIP */
250  SCIP* scip /**< SCIP data structure */
251  )
252 {
253  SCIP_HEUR* heur;
254 
255  /* include primal heuristic */
256  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
258  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivial, NULL) );
259 
260  assert(heur != NULL);
261 
262  /* set non-NULL pointers to callback methods */
263  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivial) );
264 
265  return SCIP_OKAY;
266 }
SCIP_Real SCIPfeastol(SCIP *scip)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3296
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3354
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17957
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:1866
#define FALSE
Definition: def.h:96
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:95
#define SCIPdebug(x)
Definition: pub_message.h:93
#define HEUR_DISPCHAR
Definition: heur_trivial.c:47
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define HEUR_TIMING
Definition: heur_trivial.c:52
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:117
#define SCIPdebugMsg
Definition: scip_message.h:78
#define HEUR_NAME
Definition: heur_trivial.c:45
public methods for numerical tolerances
public methods for querying solving statistics
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1450
#define HEUR_USESSUBSCIP
Definition: heur_trivial.c:53
#define HEUR_FREQOFS
Definition: heur_trivial.c:50
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:394
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:61
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1221
#define SCIP_Bool
Definition: def.h:93
#define HEUR_FREQ
Definition: heur_trivial.c:49
#define MAX(x, y)
Definition: tclique_def.h:92
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:985
int SCIPgetNRuns(SCIP *scip)
#define HEUR_MAXDEPTH
Definition: heur_trivial.c:51
SCIP_RETCODE SCIPincludeHeurTrivial(SCIP *scip)
Definition: heur_trivial.c:249
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:3098
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:186
public methods for message handling
#define HEUR_DESC
Definition: heur_trivial.c:46
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17407
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:162
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17967
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:76
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:328
#define HEUR_PRIORITY
Definition: heur_trivial.c:48
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1775