SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2024 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"
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) */
60static
61SCIP_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 */
75static
76SCIP_DECL_HEUREXEC(heurExecTrivial)
77{ /*lint --e{715}*/
78 SCIP_VAR** vars;
79 SCIP_SOL* zerosol; /* solution where all variables are set next to zero within bounds */
80 SCIP_SOL* lbsol; /* solution where all variables are set to their lower bounds */
81 SCIP_SOL* ubsol; /* solution where all variables are set to their upper bounds */
82 SCIP_SOL* locksol; /* solution where all variables are set to the bound with the fewer locks */
83 SCIP_Real large;
84 SCIP_Bool difflb;
85 SCIP_Bool diffub;
86 SCIP_Bool difflock;
87 SCIP_Bool success;
88 int nvars;
89 int i;
90
92
93 /* initialize data structure */
94 SCIP_CALL( SCIPcreateSol(scip, &zerosol, heur) );
95 SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) );
96 SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) );
97 SCIP_CALL( SCIPcreateSol(scip, &locksol, heur) );
98
99 /* determine large value to set variables to */
100 large = SCIPround(scip, MIN(1.0 / SCIPfeastol(scip), SCIPgetHugeValue(scip)) / 10.0); /*lint !e666 */
101
102 /* check zero solution once */
103 difflb = FALSE;
104 diffub = FALSE;
105 difflock = FALSE;
106
108 assert(vars != NULL || nvars == 0);
109
110 for( i = 0; i < nvars; ++i )
111 {
112 SCIP_Real lb;
113 SCIP_Real ub;
114 SCIP_Real zeroval;
115 SCIP_Real solval;
116
117 assert(vars != NULL); /* this assert is needed for flexelint */
118
119 lb = SCIPvarGetLbLocal(vars[i]);
120 ub = SCIPvarGetUbLocal(vars[i]);
121
122 /* if problem is obviously infeasible due to empty domain, stop */
123 if( SCIPisFeasGT(scip, lb, ub) )
124 goto TERMINATE;
125
126 /* set bounds to sufficient large value */
127 if( SCIPisInfinity(scip, -lb) )
128 lb = MIN(-large, ub);
129 if( SCIPisInfinity(scip, ub) )
130 ub = MAX(large, lb);
131
132 /* set value next to zero within bounds */
133 zeroval = MAX(MIN(0.0, ub), lb);
134
135 /* set value to the bound with fewer locks, if tie choose an average value */
137 solval = lb;
139 solval = ub;
140 else
141 {
142 solval = (lb+ub)/2.0;
143
144 /* if a tie occurs, roughly every third integer variable will be rounded up */
146 solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval);
147
149 }
150
151 if( !SCIPisEQ(scip, lb, zeroval) )
152 difflb = TRUE;
153
154 if( !SCIPisEQ(scip, ub, zeroval) )
155 diffub = TRUE;
156
157 if( !SCIPisEQ(scip, solval, zeroval) )
158 difflock = TRUE;
159
160 /* set variable to values */
161 SCIP_CALL( SCIPsetSolVal(scip, zerosol, vars[i], zeroval) );
162 SCIP_CALL( SCIPsetSolVal(scip, lbsol, vars[i], lb) );
163 SCIP_CALL( SCIPsetSolVal(scip, ubsol, vars[i], ub) );
164 SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], solval) );
165 }
166
167 /* try zero solution */
168 SCIPdebugMsg(scip, "try zero solution\n");
169 SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
170
171 if( success )
172 {
173 SCIPdebugMsg(scip, "found feasible zero solution:\n");
174 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, zerosol, NULL, FALSE) ) );
175
177 }
178
179 /* try lower bound solution */
180 if( difflb )
181 {
182 SCIPdebugMsg(scip, "try lower bound solution\n");
183 SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
184
185 if( success )
186 {
187 SCIPdebugMsg(scip, "found feasible lower bound solution:\n");
189
191 }
192 }
193
194 /* try upper bound solution */
195 if( diffub )
196 {
197 SCIPdebugMsg(scip, "try upper bound solution\n");
198 SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
199
200 if( success )
201 {
202 SCIPdebugMsg(scip, "found feasible upper bound solution:\n");
204
206 }
207 }
208
209 /* try lock solution */
210 if( difflock )
211 {
212 SCIPdebugMsg(scip, "try lock solution\n");
213 SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, FALSE, FALSE, 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
221 }
222 }
223
224TERMINATE:
225 /* free solutions */
226 SCIP_CALL( SCIPfreeSol(scip, &locksol) );
227 SCIP_CALL( SCIPfreeSol(scip, &ubsol) );
228 SCIP_CALL( SCIPfreeSol(scip, &lbsol) );
229 SCIP_CALL( SCIPfreeSol(scip, &zerosol) );
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 */
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}
#define NULL
Definition def.h:266
#define MIN(x, y)
Definition def.h:242
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:238
#define SCIP_CALL(x)
Definition def.h:373
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
#define SCIPdebugMsg
SCIP_RETCODE SCIPincludeHeurTrivial(SCIP *scip)
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
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1627
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:2950
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1073
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18143
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17583
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18133
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
static SCIP_VAR ** vars
#define HEUR_TIMING
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
trivial primal heuristic
public methods for primal heuristics
public methods for message output
#define SCIPdebug(x)
Definition pub_message.h:93
public methods for problem variables
public methods for primal heuristic plugins and divesets
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97