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-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
91 *result = SCIP_DIDNOTFIND;
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
107 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
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
148 assert(SCIPisFeasLE(scip,SCIPvarGetLbLocal(vars[i]),solval) && SCIPisFeasLE(scip,solval,SCIPvarGetUbLocal(vars[i])));
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
176 *result = SCIP_FOUNDSOL;
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
190 *result = SCIP_FOUNDSOL;
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
205 *result = SCIP_FOUNDSOL;
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
220 *result = SCIP_FOUNDSOL;
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:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
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
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeHeurTrivial(SCIP *scip)
Definition: heur_trivial.c:240
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
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:2954
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
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:18144
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
static SCIP_DECL_HEURCOPY(heurCopyTrivial)
Definition: heur_trivial.c:61
#define HEUR_TIMING
Definition: heur_trivial.c:52
#define HEUR_FREQOFS
Definition: heur_trivial.c:50
#define HEUR_DESC
Definition: heur_trivial.c:46
#define HEUR_DISPCHAR
Definition: heur_trivial.c:47
#define HEUR_MAXDEPTH
Definition: heur_trivial.c:51
#define HEUR_PRIORITY
Definition: heur_trivial.c:48
#define HEUR_NAME
Definition: heur_trivial.c:45
#define HEUR_FREQ
Definition: heur_trivial.c:49
static SCIP_DECL_HEUREXEC(heurExecTrivial)
Definition: heur_trivial.c:76
#define HEUR_USESSUBSCIP
Definition: heur_trivial.c:53
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
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97