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-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"
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
62{ /*lint --e{715}*/
63 assert(scip != NULL);
64 assert(heur != NULL);
66
67 /* call inclusion method of primal heuristic */
69
70 return SCIP_OKAY;
71}
72
73
74/** execution method of primal heuristic */
75static
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
94
95 if( SCIPgetNRuns(scip) > 1 )
96 return SCIP_OKAY;
97
99 success = FALSE;
100
101 /* initialize data structure */
102 SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) );
103 SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) );
106
107 /* determine large value to set variables to */
109 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
110 large = 0.1 / SCIPfeastol(scip);
111
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
141 ub = MAX(tmp, large);
142 }
143
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 {
153 }
154 else
156 }
157
158 /* set variables to the bound with fewer locks, if tie choose an average value */
160 {
162 }
164 {
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 */
174 solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval);
175
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");
185
186 if( success )
187 {
188 SCIPdebugMsg(scip, "found feasible lower bound solution:\n");
190
192 }
193
194 /* try upper bound solution */
195 SCIPdebugMsg(scip, "try upper bound solution\n");
197
198 if( success )
199 {
200 SCIPdebugMsg(scip, "found feasible upper bound solution:\n");
202
204 }
205
206 /* try zero solution */
207 if( zerovalid )
208 {
209 SCIPdebugMsg(scip, "try zero solution\n");
211
212 if( success )
213 {
214 SCIPdebugMsg(scip, "found feasible zero solution:\n");
216
218 }
219 }
220
221 /* try lock solution */
222 SCIPdebugMsg(scip, "try lock solution\n");
224
225 if( success )
226 {
227 SCIPdebugMsg(scip, "found feasible lock solution:\n");
229
231 }
232
234 /* free solutions */
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 */
259
260 assert(heur != NULL);
261
262 /* set non-NULL pointers to callback methods */
264
265 return SCIP_OKAY;
266}
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
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:1450
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1775
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_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
int SCIPgetNRuns(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
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
int nbinvars
#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
#define NULL
Definition lpi_spx1.cpp:161
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 MAX(x, y)
Definition tclique_def.h:92
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ 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