Scippy

SCIP

Solving Constraint Integer Programs

heur_sync.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_sync.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief primal heuristic that adds solutions from synchronization
28 * @author Leona Gottwald
29 *
30 * This heuristic takes solutions during synchronization and then adds them.
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35#include <assert.h>
36#include <string.h>
37
38#include "scip/heur_sync.h"
39#include "scip/scip.h"
40
41
42#define HEUR_NAME "sync"
43#define HEUR_DESC "heuristic for synchronizing solution"
44#define HEUR_DISPCHAR 'S'
45#define HEUR_PRIORITY -3000000 /* should process after all other heuristics */
46#define HEUR_FREQ -1
47#define HEUR_FREQOFS 0
48#define HEUR_MAXDEPTH -1
49#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
50#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
51
52
53/*
54 * Data structures
55 */
56
57
58/** primal heuristic data */
59struct SCIP_HeurData
60{
61 SCIP_SOL** sols; /**< storing solutions passed to heuristic sorted by objective value */
62 int nsols; /**< number of soluions stored */
63 int maxnsols; /**< maximum number of solutions that can be stored */
64};
65
66
67/*
68 * Callback methods of primal heuristic
69 */
70
71/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
72static
73SCIP_DECL_HEURFREE(heurFreeSync)
74{ /*lint --e{715}*/
75 SCIP_HEURDATA* heurdata;
76
77 assert( heur != NULL );
78 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
79 assert( scip != NULL );
80
81 SCIPdebugMessage("free method of sync primal heuristic.\n");
82
83 /* get heuristic data */
84 heurdata = SCIPheurGetData(heur);
85 assert(heurdata != NULL);
86 assert(heurdata->nsols == 0);
87 SCIPfreeBlockMemoryArray(scip, &heurdata->sols, heurdata->maxnsols);
88 SCIPfreeBlockMemory(scip, &heurdata);
89
90 return SCIP_OKAY;
91}
92
93
94/** deinitialization method of primal heuristic (called before transformed problem is freed) */
95static
97{ /*lint --e{715}*/
98 SCIP_HEURDATA* heurdata;
99 int i;
100
101 assert( heur != NULL );
102 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
103 assert( scip != NULL );
104
105 SCIPdebugMessage("exit method of sync primal heuristic.\n");
106
107 /* get heuristic data */
108 heurdata = SCIPheurGetData(heur);
109 assert(heurdata != NULL);
110
111 /* free solution if one is still present */
112 for( i = 0; i < heurdata->nsols; ++i )
113 {
114 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sols[i]) );
115 }
116 heurdata->nsols = 0;
117 return SCIP_OKAY;
118}
119
120
121/** execution method of primal heuristic */
122static
124{ /*lint --e{715}*/
125 SCIP_HEURDATA* heurdata;
126 SCIP_Bool stored;
127 int i;
128
129 assert(heur != NULL);
130 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
131 assert(scip != NULL);
132 assert(result != NULL);
133 assert(SCIPheurGetFreq(heur) == 1);
134
135 SCIPheurSetFreq(heur, -1);
136
137 /* get heuristic data */
138 heurdata = SCIPheurGetData(heur);
139 assert(heurdata != NULL);
140 assert(heurdata->nsols > 0);
141
142 SCIPdebugMessage("exec method of sync primal heuristic.\n");
143 *result = SCIP_DIDNOTFIND;
144 for( i = 0; i < heurdata->nsols; ++i )
145 {
146 SCIP_CALL( SCIPtrySolFree(scip, &heurdata->sols[i], FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
147 if( stored )
148 *result = SCIP_FOUNDSOL;
149 }
150
151 heurdata->nsols = 0;
152
153 return SCIP_OKAY;
154}
155
156/*
157 * primal heuristic specific interface methods
158 */
159
160/** creates the sync primal heuristic and includes it in SCIP */
162 SCIP* scip /**< SCIP data structure */
163 )
164{
165 SCIP_HEURDATA* heurdata;
166 SCIP_HEUR* heur;
167
168 /* create heuristic data */
169 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
170 SCIP_CALL( SCIPgetIntParam(scip, "concurrent/sync/maxnsols", &heurdata->maxnsols) );
171 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->sols, heurdata->maxnsols) );
172 heurdata->nsols = 0;
173
174 /* include primal heuristic */
177 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSync, heurdata) );
178
179 assert(heur != NULL);
180
181 /* set non-NULL pointers to callback methods */
182 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSync) );
183 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSync) );
184
185 return SCIP_OKAY;
186}
187
188
189/** pass solution to sync heuristic */
191 SCIP* scip, /**< SCIP data structure */
192 SCIP_HEUR* heur, /**< sync heuristic */
193 SCIP_SOL* sol /**< solution to be passed */
194 )
195{
196 SCIP_HEURDATA* heurdata;
197 SCIP_Real solobj;
198 int i;
199 assert(scip != NULL);
200 assert(heur != NULL);
201 assert(sol != NULL);
202 assert(strcmp(HEUR_NAME, SCIPheurGetName(heur)) == 0);
203
204 /* get heuristic data */
205 heurdata = SCIPheurGetData(heur);
206 assert(heurdata != NULL);
207
208 SCIPsolSetHeur(sol, heur);
209 solobj = SCIPgetSolTransObj(scip, sol);
210
211 /* check if we have an empty space in the solution array or
212 * if we need to discard the worst solution
213 */
214 if( heurdata->nsols < heurdata->maxnsols )
215 {
216 /* if the maximum number of solutions is not yet reached just
217 * insert the solution sorted by its objective value */
218 i = heurdata->nsols++;
219
220 while( i > 0 && solobj > SCIPgetSolTransObj(scip, heurdata->sols[i - 1]) )
221 {
222 heurdata->sols[i] = heurdata->sols[i - 1];
223 --i;
224 }
225 heurdata->sols[i] = sol;
226 }
227 else
228 {
229 /* already have reached the maximum number of solutions so
230 * we need to check if the solution is better than a previous
231 * one and free the worst solution to make room for it if that
232 * is the case
233 */
234 i = 0;
235 while( i < heurdata->nsols && solobj < SCIPgetSolTransObj(scip, heurdata->sols[i]) )
236 {
237 if( i > 0 )
238 {
239 heurdata->sols[i - 1] = heurdata->sols[i];
240 }
241 else
242 {
243 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sols[i]) );
244 }
245
246 ++i;
247 }
248 /* check if solution must be inserted or discarded */
249 if( i > 0)
250 {
251 /* found position to insert the solution sorted by objective value */
252 heurdata->sols[i-1] = sol;
253 }
254 else
255 {
256 /* solution is not better just discard it */
257 SCIP_CALL( SCIPfreeSol(scip, &sol) );
258 }
259 }
260 assert(heurdata->nsols > 0);
261 assert(heurdata->nsols <= heurdata->maxnsols);
262
263 SCIPheurSetFreq(heur, 1);
264
265 return SCIP_OKAY;
266}
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPheurSyncPassSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_sync.c:190
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPincludeHeurSync(SCIP *scip)
Definition: heur_sync.c:161
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
void SCIPheurSetFreq(SCIP_HEUR *heur, int freq)
Definition: heur.c:1548
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1538
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPtrySolFree(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:3050
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2849
#define HEUR_TIMING
Definition: heur_sync.c:49
#define HEUR_FREQOFS
Definition: heur_sync.c:47
#define HEUR_DESC
Definition: heur_sync.c:43
static SCIP_DECL_HEUREXITSOL(heurExitSync)
Definition: heur_sync.c:96
#define HEUR_DISPCHAR
Definition: heur_sync.c:44
#define HEUR_MAXDEPTH
Definition: heur_sync.c:48
#define HEUR_PRIORITY
Definition: heur_sync.c:45
static SCIP_DECL_HEURFREE(heurFreeSync)
Definition: heur_sync.c:73
#define HEUR_NAME
Definition: heur_sync.c:42
static SCIP_DECL_HEUREXEC(heurExecSync)
Definition: heur_sync.c:123
#define HEUR_FREQ
Definition: heur_sync.c:46
#define HEUR_USESSUBSCIP
Definition: heur_sync.c:50
primal heuristic that adds given solutions
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIP callable library.
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ 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