1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright 2002-2022 Zuse Institute Berlin */
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_indicatordiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that fixes indicator variables controlling semicontinuous variables
28 * @author Katrin Halbig
29 * @author Alexander Hoen
30 *
31 * A diving heuristic iteratively rounds some fractional variables or variables determined by constraint handlers,
32 * and resolves the LP relaxation. Thereby simulating a depth-first-search in the tree.
33 *
34 * Indicatordiving focuses on indicator variables, which control semicontinuous variables.
35 * If the semicontinuous variable is unbounded, the indicator constraint is not part of the LP and,
36 * therefore, the indicator variable is not set to an useful value in the LP solution.
37 *
38 * For these indicator variables the score depends on the LP value and the bounds of the corresponding semicontinuous variable.
39 * If parameter usevarbounds=TRUE, also varbound constraints modeling semicontinuous variables are considered.
40 * For all other variables the Farkas score (scaled) is returned.
41 */
42
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44
45 #include <assert.h>
46
47 #include "scip/cons_indicator.h"
48 #include "scip/cons_varbound.h"
49 #include "scip/heur_indicatordiving.h"
50 #include "scip/heuristics.h"
51 #include "scip/pub_cons.h"
52 #include "scip/pub_heur.h"
53 #include "scip/pub_message.h"
54 #include "scip/pub_misc.h"
55 #include "scip/pub_var.h"
56 #include "scip/scip_cons.h"
57 #include "scip/scip_heur.h"
58 #include "scip/scip_mem.h"
59 #include "scip/scip_numerics.h"
60 #include "scip/scip_param.h"
61 #include "scip/scip_probing.h"
62 #include "scip/scip_sol.h"
63 #include "scip/scip_tree.h"
64 #include "scip/scip_prob.h"
65 #include "scip/scip_message.h"
66
67 #define HEUR_NAME "indicatordiving"
68 #define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables"
69 #define HEUR_DISPCHAR 'I'
70 #define HEUR_PRIORITY -150000
71 #define HEUR_FREQ 0
72 #define HEUR_FREQOFS 0
73 #define HEUR_MAXDEPTH -1
74 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
75 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
76 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
77 #define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
78
79
80 /*
81 * Default parameter settings
82 */
83
84 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
85 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
86 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
87 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
88 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
89 * where diving is performed (0.0: no limit) */
90 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
91 * where diving is performed (0.0: no limit) */
92 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
93 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
94 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
95 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
96 #define DEFAULT_LPSOLVEFREQ 30 /**< LP solve frequency for diving heuristics */
97 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
98 * more general constraint handler diving variable selection? */
99 #define DEFAULT_RANDSEED 11 /**< initial seed for random number generation */
100
101 /*
102 * Heuristic specific parameters
103 */
104 #define DEFAULT_ROUNDINGFRAC 0.5 /**< default setting for parameter roundingfrac */
105 #define DEFAULT_ROUNDINGMODE 0 /**< default setting for parameter roundingmode */
106 #define DEFAULT_SEMICONTSCOREMODE 0 /**< default setting for parameter semicontscoremode */
107 #define DEFAULT_USEVARBOUNDS TRUE /**< default setting for parameter usevarbounds */
108 #define DEFAULT_RUNWITHOUTSCINDS FALSE /**< default setting for parameter runwithoutscinds */
109
110 enum IndicatorDivingRoundingMode
111 {
112 ROUNDING_CONSERVATIVE = 0,
113 ROUNDING_AGGRESSIVE = 1
114 };
115 typedef enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE;
116
117 /** data structure to store information of a semicontinuous variable
118 *
119 * For a variable x (not stored in the struct), this stores the data of nbnds implications
120 * bvars[i] = 0 -> x = vals[i]
121 * bvars[i] = 1 -> lbs[i] <= x <= ubs[i]
122 * where bvars[i] are binary variables.
123 */
124 struct SCVarData
125 {
126 SCIP_Real* vals0; /**< values of the variable when the corresponding bvars[i] = 0 */
127 SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */
128 SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */
129 SCIP_VAR** bvars; /**< the binary variables on which the variable domain depends */
130 int nbnds; /**< number of suitable on/off bounds the var has */
131 int bndssize; /**< size of the arrays */
132 };
133 typedef struct SCVarData SCVARDATA;
134
135
136 /** locally defined heuristic data */
137 struct SCIP_HeurData
138 {
139 SCIP_SOL* sol; /**< working solution */
140 SCIP_CONSHDLR* indicatorconshdlr; /**< indicator constraint handler */
141 SCIP_CONSHDLR* varboundconshdlr; /**< varbound constraint handler */
142 SCIP_HASHMAP* scvars; /**< hashmap to store semicontinuous variables */
143 SCIP_HASHMAP* indicatormap; /**< hashmap to store indicator constraints of binary variables */
144 SCIP_HASHMAP* varboundmap; /**< hashmap to store varbound constraints of binary variables */
145 SCIP_Real roundingfrac; /**< in violation case all fractional below this value are fixed to constant */
146 int roundingmode; /**< decides which roundingmode is selected (0: conservative (default), 1: aggressive) */
147 int semicontscoremode; /**< which values of semi-continuous variables should get a high score? (0: low (default), 1: middle, 2: high) */
148 SCIP_Bool usevarbounds; /**< should varbound constraints be considered? */
149 SCIP_Bool runwithoutscinds; /**< should heur run if there are no indicator constraints modeling semicont. vars? */
150 SCIP_Bool gotoindconss; /**< can we skip the candidate var until indicator conss handler determines the candidate var? */
151 SCIP_Bool containsviolindconss;/**< contains current solution violated indicator constraints? (only unbounded) */
152 SCIP_Bool newnode; /**< are we at a new probing node? */
153 int probingdepth; /**< current probing depth */
154 };
155
156 /*
157 * Local methods
158 */
159
160 /** checks if constraint is violated but not fixed, i.e., it will be a diving candidate variable */
161 static
162 SCIP_Bool isViolatedAndNotFixed(
163 SCIP* scip, /**< SCIP data structure */
164 SCIP_SOL* sol, /**< pointer to solution */
165 SCIP_CONS* cons /**< pointer to indicator constraint */
166 )
167 {
168 SCIP_VAR* binvar;
169 SCIP_Real solval;
170
171 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "indicator") == 0);
172
173 if( !SCIPisViolatedIndicator(scip, cons, sol) )
174 return FALSE;
175
176 binvar = SCIPgetBinaryVarIndicator(cons);
177 solval = SCIPgetSolVal(scip, sol, binvar);
178
179 return (SCIPisFeasIntegral(scip, solval) && SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5);
180 }
181
182 /** releases all data from given hashmap filled with SCVarData and the hashmap itself */
183 static
184 SCIP_RETCODE releaseSCHashmap(
185 SCIP* scip, /**< SCIP data structure */
186 SCIP_HASHMAP* hashmap /**< hashmap to be freed */
187 )
188 {
189 SCIP_HASHMAPENTRY* entry;
190 SCVARDATA* data;
191 int c;
192
193 if( hashmap != NULL )
194 {
195 for( c = 0; c < SCIPhashmapGetNEntries( hashmap ); c++ )
196 {
197 entry = SCIPhashmapGetEntry( hashmap, c);
198 if( entry != NULL )
199 {
200 data = (SCVARDATA*) SCIPhashmapEntryGetImage(entry);
201 SCIPfreeBlockMemoryArray(scip, &data->ubs1, data->bndssize);
202 SCIPfreeBlockMemoryArray(scip, &data->lbs1, data->bndssize);
203 SCIPfreeBlockMemoryArray(scip, &data->vals0, data->bndssize);
204 SCIPfreeBlockMemoryArray(scip, &data->bvars, data->bndssize);
205 SCIPfreeBlockMemory(scip, &data);
206 }
207 }
208 SCIPhashmapFree(&hashmap);
209 assert(hashmap == NULL);
210 }
211
212 return SCIP_OKAY;
213 }
214
215 /** checks if variable is indicator variable and stores corresponding indicator constraint; additionally, if we are at a
216 * new probing node, it checks whether there are violated but not fixed indicator constraints
217 */
218 static
219 SCIP_RETCODE checkAndGetIndicator(
220 SCIP* scip, /**< SCIP data structure */
221 SCIP_VAR* cand, /**< candidate variable */
222 SCIP_HASHMAP* map, /**< pointer to hashmap containing indicator conss */
223 SCIP_CONS** cons, /**< pointer to store indicator constraint */
224 SCIP_Bool* isindicator, /**< pointer to store whether candidate variable is indicator variable */
225 SCIP_Bool* containsviolindconss,/**< pointer to store whether there are violated and not fixed (unbounded) indicator constraints */
226 SCIP_Bool newnode, /**< are we at a new probing node? */
227 SCIP_SOL* sol, /**< pointer to solution */
228 SCIP_CONSHDLR* conshdlr /**< constraint handler */
229 )
230 {
231 assert(scip != NULL);
232 assert(cand != NULL);
233 assert(map != NULL);
234 assert(cons != NULL);
235 assert(isindicator != NULL);
236 assert(sol != NULL);
237
238 *cons = NULL;
239 *isindicator = FALSE;
240
241 *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand);
242 if( *cons != NULL )
243 *isindicator = TRUE;
244
245 /* since we are at a new probing node, check if there are violated and not fixed indicator constraints */
246 if( newnode )
247 {
248 SCIP_CONS** indicatorconss;
249 int nconss;
250 int c;
251
252 indicatorconss = SCIPconshdlrGetConss(conshdlr);
253 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
254 *containsviolindconss = FALSE;
255
256 for( c = 0; c < nconss; c++ )
257 {
258 *containsviolindconss = *containsviolindconss || isViolatedAndNotFixed(scip, sol, indicatorconss[c]);
259
260 if( *containsviolindconss )
261 break;
262 }
263 }
264
265 return SCIP_OKAY;
266 }
267
268 /** checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint */
269 static
270 SCIP_RETCODE checkAndGetVarbound(
271 SCIP* scip, /**< SCIP data structure */
272 SCIP_VAR* cand, /**< candidate variable */
273 SCIP_HASHMAP* map, /**< pointer to hashmap containing varbound conss */
274 SCIP_CONS** cons, /**< pointer to store varbound constraint */
275 SCIP_Bool* isvarbound /**< pointer to store whether candidate variable is indicator variable */
276 )
277 {
278 assert(scip != NULL);
279 assert(cand != NULL);
280 assert(map != NULL);
281 assert(cons != NULL);
282 assert(isvarbound != NULL);
283
284 *cons = NULL;
285 *isvarbound = FALSE;
286
287 if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
288 return SCIP_OKAY;
289
290 *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand);
291 if( *cons != NULL )
292 *isvarbound = TRUE;
293
294 return SCIP_OKAY;
295 }
296
297 /** adds an indicator to the data of a semicontinuous variable */
298 static
299 SCIP_RETCODE addSCVarIndicator(
300 SCIP* scip, /**< SCIP data structure */
301 SCVARDATA* scvdata, /**< semicontinuous variable data */
302 SCIP_VAR* indicator, /**< indicator to be added */
303 SCIP_Real val0, /**< value of the variable when indicator == 0 */
304 SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */
305 SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */
306 )
307 {
308 int newsize;
309 int i;
310 SCIP_Bool found;
311 int pos;
312
313 assert(scvdata != NULL);
314 assert(indicator != NULL);
315
316 /* find the position where to insert */
317 if( scvdata->bvars == NULL )
318 {
319 assert(scvdata->nbnds == 0 && scvdata->bndssize == 0);
320 found = FALSE;
321 pos = 0;
322 }
323 else
324 {
325 found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos);
326 }
327
328 if( found )
329 return SCIP_OKAY;
330
331 /* ensure sizes */
332 if( scvdata->nbnds + 1 > scvdata->bndssize )
333 {
334 newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1);
335 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) );
336 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) );
337 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) );
338 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) );
339 scvdata->bndssize = newsize;
340 }
341 assert(scvdata->nbnds + 1 <= scvdata->bndssize);
342 assert(scvdata->bvars != NULL);
343
344 /* move entries if needed */
345 for( i = scvdata->nbnds; i > pos; --i )
346 {
347 scvdata->bvars[i] = scvdata->bvars[i-1];
348 scvdata->vals0[i] = scvdata->vals0[i-1];
349 scvdata->lbs1[i] = scvdata->lbs1[i-1];
350 scvdata->ubs1[i] = scvdata->ubs1[i-1];
351 }
352
353 scvdata->bvars[pos] = indicator;
354 scvdata->vals0[pos] = val0;
355 scvdata->lbs1[pos] = lb1;
356 scvdata->ubs1[pos] = ub1;
357 ++scvdata->nbnds;
358
359 return SCIP_OKAY;
360 }
361
362 /** checks if a variable is semicontinuous and stores it data in the hashmap scvars
363 *
364 * A variable x is semicontinuous if its bounds depend on at least one binary variable called the indicator,
365 * and indicator == 0 => x == x^0 for some real constant x^0.
366 */
367 static
368 SCIP_RETCODE varIsSemicontinuous(
369 SCIP* scip, /**< SCIP data structure */
370 SCIP_VAR* var, /**< the variable to check */
371 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
372 SCIP_Real constant, /**< value which should be equal to the constant */
373 SCIP_Bool* result /**< buffer to store whether var is semicontinuous */
374 )
375 {
376 SCIP_Real lb0;
377 SCIP_Real ub0;
378 SCIP_Real lb1;
379 SCIP_Real ub1;
380 SCIP_Real glb;
381 SCIP_Real gub;
382 SCIP_Bool exists;
383 int c;
384 int pos;
385 SCIP_VAR** vlbvars;
386 SCIP_VAR** vubvars;
387 SCIP_Real* vlbcoefs;
388 SCIP_Real* vubcoefs;
389 SCIP_Real* vlbconstants;
390 SCIP_Real* vubconstants;
391 int nvlbs;
392 int nvubs;
393 SCVARDATA* scvdata;
394 SCIP_VAR* bvar;
395
396 assert(scip != NULL);
397 assert(var != NULL);
398 assert(scvars != NULL);
399 assert(result != NULL);
400
401 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
(1) Event cond_false: |
Condition "scvdata != NULL", taking false branch. |
402 if( scvdata != NULL )
403 {
404 *result = TRUE;
405 return SCIP_OKAY;
(2) Event if_end: |
End of if statement. |
406 }
407
(3) Event cond_true: |
Condition "var->vlbs != NULL", taking true branch. |
408 vlbvars = SCIPvarGetVlbVars(var);
(4) Event cond_true: |
Condition "var->vubs != NULL", taking true branch. |
409 vubvars = SCIPvarGetVubVars(var);
(5) Event cond_true: |
Condition "var->vlbs != NULL", taking true branch. |
410 vlbcoefs = SCIPvarGetVlbCoefs(var);
(6) Event cond_true: |
Condition "var->vubs != NULL", taking true branch. |
411 vubcoefs = SCIPvarGetVubCoefs(var);
(7) Event cond_true: |
Condition "var->vlbs != NULL", taking true branch. |
412 vlbconstants = SCIPvarGetVlbConstants(var);
(8) Event cond_true: |
Condition "var->vubs != NULL", taking true branch. |
413 vubconstants = SCIPvarGetVubConstants(var);
(9) Event cond_true: |
Condition "var->vlbs != NULL", taking true branch. |
414 nvlbs = SCIPvarGetNVlbs(var);
(10) Event cond_true: |
Condition "var->vubs != NULL", taking true branch. |
415 nvubs = SCIPvarGetNVubs(var);
416 glb = SCIPvarGetLbGlobal(var);
417 gub = SCIPvarGetUbGlobal(var);
418
419 pos = -1;
420
421 *result = FALSE;
422
423 /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1.
424 * Then check if there is an upper bound with this vlbvar and save ub0 and ub1.
425 * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0,
426 * save vlbvar and val0 to scvdata.
427 */
(11) Event cond_true: |
Condition "c < nvlbs", taking true branch. |
(15) Event cond_true: |
Condition "c < nvlbs", taking true branch. |
(19) Event cond_true: |
Condition "c < nvlbs", taking true branch. |
(38) Event loop_begin: |
Jumped back to beginning of loop. |
(39) Event cond_false: |
Condition "c < nvlbs", taking false branch. |
428 for( c = 0; c < nvlbs; ++c )
429 {
(12) Event cond_true: |
Condition "(SCIP_VARTYPE)vlbvars[c]->vartype != SCIP_VARTYPE_BINARY", taking true branch. |
(16) Event cond_true: |
Condition "(SCIP_VARTYPE)vlbvars[c]->vartype != SCIP_VARTYPE_BINARY", taking true branch. |
(20) Event cond_false: |
Condition "(SCIP_VARTYPE)vlbvars[c]->vartype != SCIP_VARTYPE_BINARY", taking false branch. |
430 if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY )
(13) Event continue: |
Continuing loop. |
(17) Event continue: |
Continuing loop. |
(21) Event if_end: |
End of if statement. |
431 continue;
432
433 bvar = vlbvars[c];
434
(22) Event cond_true: |
Condition "vlbconstants[c] >= glb", taking true branch. |
435 lb0 = MAX(vlbconstants[c], glb);
(23) Event cond_true: |
Condition "vlbconstants[c] + vlbcoefs[c] >= glb", taking true branch. |
436 lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb);
437
438 /* look for bvar in vubvars */
(24) Event cond_false: |
Condition "vubvars != NULL", taking false branch. |
(26) Event var_compare_op: |
Comparing "vubvars" to null implies that "vubvars" might be null. |
Also see events: |
[var_deref_op] |
439 if( vubvars != NULL )
440 exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos);
441 else
(25) Event else_branch: |
Reached else branch. |
442 exists = FALSE;
443
(27) Event cond_false: |
Condition "exists", taking false branch. |
444 if( exists )
445 {
446 /* save the upper bounds */
447 ub0 = MIN(vubconstants[pos], gub);
448 ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub);
449 }
450 else
(28) Event else_branch: |
Reached else branch. |
451 {
452 /* if there is no upper bound with vubvar = bvar, use global var bounds */
453 ub0 = gub;
454 ub1 = gub;
455 }
456
457 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
(29) Event cond_true: |
Condition "fabs(lb0 - constant) <= scip->set->num_epsilon", taking true branch. |
(30) Event cond_true: |
Condition "!(fabs(lb0 - lb1) <= scip->set->num_epsilon)", taking true branch. |
458 if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
459 {
(31) Event cond_true: |
Condition "scvdata == NULL", taking true branch. |
460 if( scvdata == NULL )
461 {
(32) Event cond_false: |
Condition "(scvdata = BMSallocClearBlockMemory_call(SCIPblkmem(scip), 40UL /* sizeof (*scvdata) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scip-soplex-9.0.0_rc1/scip/src/scip/heur_indicatordiving.c", 462)) == NULL", taking false branch. |
(33) Event cond_false: |
Condition "(_restat_ = (((scvdata = BMSallocClearBlockMemory_call(SCIPblkmem(scip), 40UL /* sizeof (*scvdata) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scip-soplex-9.0.0_rc1/scip/src/scip/heur_indicatordiving.c", 462)) == NULL) ? SCIP_NOMEMORY : SCIP_OKAY)) != SCIP_OKAY", taking false branch. |
(34) Event if_end: |
End of if statement. |
462 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
463 }
(35) Event cond_false: |
Condition "(_restat_ = addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1)) != SCIP_OKAY", taking false branch. |
(36) Event if_end: |
End of if statement. |
464 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
465 }
(14) Event loop: |
Looping back. |
(18) Event loop: |
Looping back. |
(37) Event loop: |
Jumping back to the beginning of the loop. |
(40) Event loop_end: |
Reached end of loop. |
466 }
467
468 /* look for vubvars that have not been processed yet */
469 assert(vubvars != NULL || nvubs == 0);
(41) Event cond_true: |
Condition "c < nvubs", taking true branch. |
470 for( c = 0; c < nvubs; ++c )
471 {
(42) Event var_deref_op: |
Dereferencing null pointer "vubvars". |
Also see events: |
[var_compare_op] |
472 if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/
473 continue;
474
475 bvar = vubvars[c]; /*lint !e613*/
476
477 /* skip vars that are in vlbvars */
478 if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) )
479 continue;
480
481 lb0 = glb;
482 lb1 = glb;
483 ub0 = MIN(vubconstants[c], gub);
484 ub1 = MIN(vubconstants[c] + vubcoefs[c], gub);
485
486 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
487 if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
488 {
489 if( scvdata == NULL )
490 {
491 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
492 }
493
494 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
495 }
496 }
497
498 if( scvdata != NULL )
499 {
500 #ifdef SCIP_DEBUG
501 SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub);
502 for( c = 0; c < scvdata->nbnds; ++c )
503 {
504 SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]);
505 }
506 #endif
507 SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) );
508 *result = TRUE;
509 }
510
511 return SCIP_OKAY;
512 }
513
514 /** checks if there are unfixed indicator variables modeling semicont. vars */
515 static
516 SCIP_RETCODE hasUnfixedSCIndicator(
517 SCIP* scip, /**< SCIP data structure */
518 SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */
519 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
520 SCIP_Bool* hasunfixedscindconss /**< pointer to store if there are unfixed indicator variables modeling semicont. vars */
521 )
522 {
523 SCIP_CONS** indicatorconss;
524 SCIP_VAR** consvars;
525 SCIP_Real* consvals;
526 int nconss;
527 int i;
528
529 *hasunfixedscindconss = FALSE;
530 indicatorconss = SCIPconshdlrGetConss(conshdlr);
531 nconss = SCIPconshdlrGetNConss(conshdlr);
532 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
533 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
534
535 for( i = 0; i < nconss; i++ )
536 {
537 SCIP_VAR *binvar;
538 SCIP_VAR* semicontinuousvar;
539 SCIP_CONS* lincons;
540 SCIP_Real rhs;
541 int nconsvars;
542 SCIP_Bool success;
543 int v;
544
545 binvar = SCIPgetBinaryVarIndicator(indicatorconss[i]);
546
547 /* check if indicator variable is unfixed */
548 if( SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5 )
549 {
550 lincons = SCIPgetLinearConsIndicator(indicatorconss[i]);
551 rhs = SCIPconsGetRhs(scip, lincons, &success);
552 SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) );
553
554 /* check if constraint contains only two variables with finite rhs */
555 /* TODO: allow also indicators for lower bounds */
556 if( nconsvars == 2 && !SCIPisInfinity(scip, rhs) )
557 {
558 SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) );
559 SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) );
560
561 for( v = 0; v < nconsvars ; v++ )
562 {
563 if( consvars[v] == SCIPgetSlackVarIndicator(indicatorconss[i]) ) /* note that we have exact two variables */
564 continue;
565
566 semicontinuousvar = consvars[v];
567 SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, scvars, rhs, &success) );
568
569 /* check if semicontinuous variable */
570 if( success )
571 {
572 *hasunfixedscindconss = TRUE;
573 break;
574 }
575 }
576 if( *hasunfixedscindconss )
577 break;
578 }
579 }
580 }
581 SCIPfreeBufferArray(scip, &consvals);
582 SCIPfreeBufferArray(scip, &consvars);
583 return SCIP_OKAY;
584 }
585
586 /** creates and initializes hashmaps
587 *
588 * indicatormap: binary var -> indicator constraint
589 * varboundmap: binary var -> varbound constraint
590 *
591 * Currently exactly one constraint is assigned to a binary variable (per hashmap),
592 * but a binary variable can also control more than one constraint.
593 * TODO: Allow more than one corresponding indicator/varbound constraint per binary variable.
594 */
595 static
596 SCIP_RETCODE createMaps(
597 SCIP* scip, /**< SCIP data structure */
598 SCIP_CONSHDLR* indicatorconshdlr, /**< indicator constraint handler */
599 SCIP_CONSHDLR* varboundconshdlr, /**< varbound constraint handler */
600 SCIP_Bool usevarbounds, /**< should varbound constraints be considered? */
601 SCIP_HASHMAP** indicatormap, /**< hashmap to store indicator constraints of binary variables */
602 SCIP_HASHMAP** varboundmap /**< hashmap to store varbound constraints of binary variables */
603 )
604 {
605 SCIP_CONS** conss;
606 int nconss;
607 int i;
608
609 assert(strcmp(SCIPconshdlrGetName(indicatorconshdlr), "indicator") == 0);
610 assert(strcmp(SCIPconshdlrGetName(varboundconshdlr), "varbound") == 0);
611
612 /* indicator constraints */
613 nconss = SCIPconshdlrGetNConss(indicatorconshdlr);
614 conss = SCIPconshdlrGetConss(indicatorconshdlr);
615 SCIP_CALL( SCIPhashmapCreate(indicatormap, SCIPblkmem(scip), nconss) );
616 for( i = 0; i < nconss; i++ )
617 {
618 if( !SCIPhashmapExists(*indicatormap, SCIPgetBinaryVarIndicator(conss[i])) )
619 {
620 SCIP_CALL( SCIPhashmapInsert(*indicatormap, SCIPgetBinaryVarIndicator(conss[i]), conss[i]) );
621 }
622 }
623
624 /* varbound constraints */
625 if( usevarbounds )
626 {
627 nconss = SCIPconshdlrGetNConss(varboundconshdlr);
628 conss = SCIPconshdlrGetConss(varboundconshdlr);
629 SCIP_CALL( SCIPhashmapCreate(varboundmap, SCIPblkmem(scip), nconss) );
630 for( i = 0; i < nconss; i++ )
631 {
632 if( !SCIPhashmapExists(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i])) )
633 {
634 SCIP_CALL( SCIPhashmapInsert(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i]), conss[i]) );
635 }
636 }
637 }
638 return SCIP_OKAY;
639 }
640
641 #define MIN_RAND 1e-06
642 #define MAX_RAND 1e-05
643
644 /** calculate score and preferred rounding direction for the candidate variable */
645 static
646 void getScoreOfFarkasDiving(
647 SCIP* scip, /**< SCIP data structure */
648 SCIP_DIVESET* diveset, /**< diving settings */
649 SCIP_VAR* cand, /**< candidate variable */
650 SCIP_Real candsfrac, /**< fractional part of solution value of candidate variable */
651 SCIP_Bool* roundup, /**< pointer to store whether the preferred rounding direction is upwards */
652 SCIP_Real* score /**< pointer for diving score value */
653 )
654 {
655 SCIP_RANDNUMGEN* randnumgen;
656 SCIP_Real obj;
657
658 randnumgen = SCIPdivesetGetRandnumgen(diveset);
659 assert(randnumgen != NULL);
660
661 obj = SCIPvarGetObj(cand);
662
663 /* dive towards the pseudosolution, at the same time approximate the contribution to
664 * a potential Farkas-proof (infeasibility proof) by y^TA_i = c_i.
665 */
666 if( SCIPisNegative(scip, obj) )
667 *roundup = TRUE;
668 else if( SCIPisPositive(scip, obj) )
669 *roundup = FALSE;
670 else
671 {
672 if( SCIPisEQ(scip, candsfrac, 0.5) )
673 *roundup = !SCIPrandomGetInt(randnumgen, 0, 1);
674 else
675 *roundup = (candsfrac > 0.5);
676 }
677
678 /* larger score is better */
679 *score = REALABS(obj) + SCIPrandomGetReal(randnumgen, MIN_RAND, MAX_RAND);
680
681 /* prefer decisions on binary variables */
682 if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
683 *score = -1.0 / *score;
684 }
685
686
687 /*
688 * Callback methods
689 */
690
691 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
692 static
693 SCIP_DECL_HEURCOPY(heurCopyIndicatordiving)
694 { /*lint --e{715}*/
695 assert(scip != NULL);
696 assert(heur != NULL);
697 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
698
699 /* call inclusion method of primal heuristic */
700 SCIP_CALL( SCIPincludeHeurIndicatordiving(scip) );
701
702 return SCIP_OKAY;
703 }
704
705
706 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
707 static
708 SCIP_DECL_HEURFREE(heurFreeIndicatordiving)
709 { /*lint --e{715}*/
710 SCIP_HEURDATA* heurdata;
711
712 assert(heur != NULL);
713 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
714 assert(scip != NULL);
715
716 /* free heuristic data */
717 heurdata = SCIPheurGetData(heur);
718 assert(heurdata != NULL);
719
720 SCIPfreeBlockMemory(scip, &heurdata);
721 SCIPheurSetData(heur, NULL);
722
723 return SCIP_OKAY;
724 }
725
726
727 /** initialization method of primal heuristic (called after problem was transformed) */
728 static
729 SCIP_DECL_HEURINIT(heurInitIndicatordiving)
730 { /*lint --e{715}*/
731 SCIP_HEURDATA* heurdata;
732
733 assert(heur != NULL);
734 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
735 assert(scip != NULL);
736
737 /* get heuristic data */
738 heurdata = SCIPheurGetData(heur);
739 assert(heurdata != NULL);
740
741 /* create working data */
742 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
743 SCIP_CALL( SCIPhashmapCreate( &heurdata->scvars, SCIPblkmem( scip ), SCIPgetNVars(scip) ));
744
745 heurdata->indicatorconshdlr = SCIPfindConshdlr(scip, "indicator");
746 heurdata->varboundconshdlr = SCIPfindConshdlr(scip, "varbound");
747
748 return SCIP_OKAY;
749 }
750
751
752 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
753 static
754 SCIP_DECL_HEUREXIT(heurExitIndicatordiving)
755 { /*lint --e{715}*/
756 SCIP_HEURDATA* heurdata;
757
758 assert(heur != NULL);
759 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
760 assert(scip != NULL);
761
762 /* get heuristic data */
763 heurdata = SCIPheurGetData(heur);
764 assert(heurdata != NULL);
765
766 /* free working data */
767 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
768 SCIP_CALL( releaseSCHashmap(scip, heurdata->scvars) );
769
770 return SCIP_OKAY;
771 }
772
773
774 /** execution method of primal heuristic */
775 static
776 SCIP_DECL_HEUREXEC(heurExecIndicatordiving)
777 { /*lint --e{715}*/
778 SCIP_HEURDATA* heurdata;
779 SCIP_DIVESET* diveset;
780 SCIP_Bool hasunfixedscindconss; /* are there unfixed indicator variables modeling a semicont. variable? */
781
782 heurdata = SCIPheurGetData(heur);
783 assert(heurdata != NULL);
784
785 assert(SCIPheurGetNDivesets(heur) > 0);
786 assert(SCIPheurGetDivesets(heur) != NULL);
787 diveset = SCIPheurGetDivesets(heur)[0];
788 assert(diveset != NULL);
789
790 assert(result != NULL);
791 *result = SCIP_DIDNOTRUN;
792
793 /* check if there are unfixed indicator variables modeling semicont. vars */
794 SCIP_CALL( hasUnfixedSCIndicator(scip, heurdata->indicatorconshdlr, heurdata->scvars, &hasunfixedscindconss) );
795
796 /* skip heuristic if problem doesn't contain unfixed indicator variables,
797 * or if there are no varbound constraints which should be considered
798 */
799 if( !hasunfixedscindconss && (!heurdata->runwithoutscinds || !heurdata->usevarbounds || SCIPconshdlrGetNConss(heurdata->varboundconshdlr) == 0) )
800 return SCIP_OKAY;
801
802 SCIPdebugMsg(scip, "call heurExecIndicatordiving at depth %d \n", SCIPgetDepth(scip));
803
804 /* create and initialize hashmaps */
805 SCIP_CALL( createMaps(scip, heurdata->indicatorconshdlr, heurdata->varboundconshdlr, heurdata->usevarbounds, &heurdata->indicatormap, &heurdata->varboundmap) );
806
807 /* (re-)set flags */
808 heurdata->gotoindconss = FALSE;
809 heurdata->containsviolindconss = FALSE;
810 heurdata->newnode = TRUE;
811 heurdata->probingdepth = -1;
812
813 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
814
815 /* free hashmaps since constraints can get removed/modified till the next call */
816 if( heurdata->usevarbounds )
817 SCIPhashmapFree(&heurdata->varboundmap);
818 SCIPhashmapFree(&heurdata->indicatormap);
819
820 SCIPdebugMsg(scip, "leave heurExecIndicatordiving\n");
821
822 return SCIP_OKAY;
823 }
824
825
826 /** calculate score and preferred rounding direction for the candidate variable */
827 static
828 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving)
829 { /*lint --e{715}*/
830 SCIP_HEUR* heur;
831 SCIP_HEURDATA* heurdata;
832 SCIP_RANDNUMGEN* randnumgen;
833 SCIP_VAR** consvars;
834 SCIP_CONS* indicatorcons;
835 SCIP_CONS* varboundcons;
836 SCIP_CONS* lincons;
837 SCIP_VAR* nonoptionvar; /* second variable in linear cons which is not the option variable (indicator: slackvar, varbound: binary var) */
838 SCIP_VAR* semicontinuousvar;
839 SCIP_Real lpsolsemicontinuous;
840 SCVARDATA* scdata;
841 SCIP_Real* consvals;
842 SCIP_Real side;
843 int nconsvars;
844 int idxbvars; /* index of bounding variable in hashmap scdata */
845 SCIP_Bool isindicatorvar;
846 SCIP_Bool isvbdvar; /* variable bounding variable in varbound */
847 SCIP_Bool issemicont; /* indicates whether variable has (maybe) required semicont. properties */
848 SCIP_Bool fixconstant; /* should we fix the semicontinuous variable to its constant? */
849 SCIP_Bool success;
850 int v;
851 int b;
852
853 varboundcons = NULL;
854 semicontinuousvar = NULL;
855 scdata = NULL;
856 lpsolsemicontinuous = 0.0;
857 idxbvars = -1;
858 isvbdvar = FALSE;
859 issemicont = TRUE;
860
861 heur = SCIPdivesetGetHeur(diveset);
862 assert(heur != NULL);
863 heurdata = SCIPheurGetData(heur);
864 assert(heurdata != NULL);
865
866 randnumgen = SCIPdivesetGetRandnumgen(diveset);
867 assert(randnumgen != NULL);
868
869 /* check if we are at a new probing node; since diving heuristics backtrack at most one probing node, we are at a new
870 * node iff the probing depth increased */
871 if( heurdata->probingdepth < SCIPgetProbingDepth(scip) )
872 heurdata->newnode = TRUE;
873 else
874 {
875 assert(heurdata->probingdepth == SCIPgetProbingDepth(scip));
876 heurdata->newnode = FALSE;
877 }
878 heurdata->probingdepth = SCIPgetProbingDepth(scip);
879
880 /* skip if current candidate can not be determined by the indicator constraint handler and violated indicator
881 * constraints still exists */
882 if( !(SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5)
883 && heurdata->gotoindconss )
884 {
885 *score = SCIP_REAL_MIN;
886 *roundup = FALSE;
887 return SCIP_OKAY;
888 }
889 else
890 heurdata->gotoindconss = FALSE;
891
892 /* check if candidate variable is indicator variable */
893 SCIP_CALL( checkAndGetIndicator(scip, cand, heurdata->indicatormap, &indicatorcons, &isindicatorvar,
894 &heurdata->containsviolindconss, heurdata->newnode, heurdata->sol, heurdata->indicatorconshdlr) );
895
896 /* skip candidate in next calls since we have violated indicator constraints but current candidate is not determined
897 * by the indicator constraint handler */
898 if( heurdata->containsviolindconss &&
899 !((SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5) && isindicatorvar) )
900 {
901 heurdata->gotoindconss = TRUE;
902 *score = SCIP_REAL_MIN;
903 *roundup = FALSE;
904 return SCIP_OKAY;
905 }
906
907 /* check if candidate variable is bounding variable */
908 if( heurdata->usevarbounds && !isindicatorvar )
909 {
910 SCIP_CALL( checkAndGetVarbound(scip, cand, heurdata->varboundmap, &varboundcons, &isvbdvar) );
911 }
912
913 /* Return
914 * - if candidate variable is neither a indicator variable nor a variable bounding variable
915 * - or if candidate variable is not an indicator variable but there will be indicator variables as candidates
916 * - or if candidate variable is not an indicator variable and varbound constraints are not considered.
917 */
918 if( !isindicatorvar && (!isvbdvar || heurdata->containsviolindconss || !heurdata->usevarbounds) )
919 {
920 *score = SCIP_REAL_MIN;
921 *roundup = FALSE;
922
923 if( !heurdata->containsviolindconss && !isvbdvar )
924 {
925 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
926 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
927 }
928 return SCIP_OKAY;
929 }
930
931 SCIPdebugMsg(scip, "cand: %s, candsol: %.2f, candobjcoeff: %f\n", SCIPvarGetName(cand), candsol, SCIPvarGetObj(cand));
932
933 if( isindicatorvar ) /* prefer indicator constraint */
934 {
935 SCIP_Real rhs;
936
937 lincons = SCIPgetLinearConsIndicator(indicatorcons);
938 nonoptionvar = SCIPgetSlackVarIndicator(indicatorcons);
939 rhs = SCIPconsGetRhs(scip, lincons, &success);
940 issemicont = SCIPisInfinity(scip, -SCIPconsGetLhs(scip, lincons, &success)); /* TODO: allow also indicators for lower bounds */
941 side = rhs;
942 }
943 else if( isvbdvar )
944 {
945 SCIP_Real rhs;
946 SCIP_Real lhs;
947
948 lincons = varboundcons;
949 nonoptionvar = SCIPgetVbdvarVarbound(scip, varboundcons);
950 rhs = SCIPconsGetRhs(scip, lincons, &success);
951 lhs = SCIPconsGetLhs(scip, lincons, &success);
952 side = SCIPisInfinity(scip, rhs) ? lhs : rhs;
953 assert(!SCIPisInfinity(scip, side));
954 }
955 else
956 {
957 assert(FALSE);
958 }
959 SCIPdebugPrintCons(scip, lincons, NULL);
960
961 SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) );
962
963 if( nconsvars != 2 || !issemicont )
964 {
965 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
966 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
967 return SCIP_OKAY;
968 }
969
970 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) );
971 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
972 SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) );
973 SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) );
974
975 issemicont = FALSE;
976 for( v = 0; v < nconsvars ; v++ )
977 {
978 if( consvars[v] == nonoptionvar ) /* note that we have exact two variables */
979 continue;
980
981 semicontinuousvar = consvars[v];
982 lpsolsemicontinuous = SCIPvarGetLPSol( semicontinuousvar );
983 SCIPdebugMsg(scip, "%s lp sol %f %f\n", SCIPvarGetName( semicontinuousvar ), lpsolsemicontinuous,
984 consvals[v] );
985 SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, heurdata->scvars, side, &success) );
986
987 /* only allow semicontinuous variables */
988 if( success )
989 {
990 assert(SCIPhashmapExists(heurdata->scvars, (void*) semicontinuousvar));
991 scdata = (SCVARDATA*) SCIPhashmapGetImage(heurdata->scvars, (void*) semicontinuousvar);
992 assert(scdata != NULL);
993
994 for( b = 0; b < scdata->nbnds; b++ )
995 {
996 if( (scdata->bvars[b] == cand || (SCIPvarIsNegated(cand) && scdata->bvars[0] == SCIPvarGetNegationVar(cand)))
997 && SCIPisEQ(scip, side, scdata->vals0[b]) )
998 {
999
1000 /* TODO: handle also more general variables;
1001 * currently we handle only variables with domain vals0 < lb1 <= ub1 */
1002 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->vals0[b]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[b]) )
1003 {
1004 issemicont = TRUE;
1005 idxbvars = b;
1006 break;
1007 }
1008 }
1009 }
1010 }
1011 }
1012
1013 /* only continue if semicontinuous variable */
1014 if( !issemicont )
1015 {
1016 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
1017 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
1018 SCIPfreeBufferArray(scip, &consvals);
1019 SCIPfreeBufferArray(scip, &consvars);
1020 return SCIP_OKAY;
1021 }
1022 assert(idxbvars >= 0);
1023 assert(scdata != NULL);
1024
1025 /* Case: Variable is in range [lb1,ub1] */
1026 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[idxbvars]))
1027 {
1028 *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0);
1029 fixconstant = FALSE;
1030 }
1031 /* Case: Variable is equal to constant */
1032 else if( SCIPisEQ(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) )
1033 {
1034 *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0);
1035 fixconstant = TRUE;
1036 }
1037 /* Case: Variable is between constant and lb1 */
1038 else if( SCIPisGT(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) && SCIPisLT(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) )
1039 {
1040 SCIP_Real shiftedlpsolsemicontinuous = lpsolsemicontinuous;
1041 SCIP_Real shiftedlbs1 = scdata->lbs1[idxbvars];
1042
1043 /* handle case if constant of semicont. var is not zero -> shift values */
1044 if( !SCIPisZero(scip, scdata->vals0[idxbvars]) )
1045 {
1046 shiftedlpsolsemicontinuous -= scdata->vals0[idxbvars];
1047 shiftedlbs1 -= scdata->vals0[idxbvars];
1048 }
1049
1050 *score = 100 * (shiftedlbs1 - shiftedlpsolsemicontinuous) / shiftedlbs1;
1051 assert(*score>0);
1052
1053 switch( (INDICATORDIVINGROUNDINGMODE)heurdata->roundingmode )
1054 {
1055 case ROUNDING_CONSERVATIVE:
1056 fixconstant = (*score > (1 - heurdata->roundingfrac) * 100);
1057 break;
1058 case ROUNDING_AGGRESSIVE:
1059 fixconstant = (*score <= (1 - heurdata->roundingfrac) * 100);
1060 break;
1061 }
1062
1063 switch( heurdata->semicontscoremode )
1064 {
1065 case 0:
1066 break;
1067 case 1:
1068 if( shiftedlpsolsemicontinuous < shiftedlbs1 * heurdata->roundingfrac )
1069 *score = 100 * (shiftedlpsolsemicontinuous / (heurdata->roundingfrac * shiftedlbs1));
1070 else
1071 *score = 100 * (-shiftedlpsolsemicontinuous / ((1 - heurdata->roundingfrac) * shiftedlbs1) + (1 / (1 - heurdata->roundingfrac)) );
1072 break;
1073 case 2:
1074 *score = 100 - *score;
1075 break;
1076 default:
1077 return SCIP_INVALIDDATA;
1078 }
1079 assert(*score>0);
1080 }
1081 else
1082 {
1083 assert(FALSE);
1084 }
1085
1086 /* Set roundup depending on whether we have an indicator constraint or a varbound constraint:
1087 * - indicator constraint: roundup == fix to constant
1088 * - varbound constraint: roundup == push to range
1089 */
1090 *roundup = isindicatorvar ? fixconstant : !fixconstant; /*lint !e644*/
1091
1092 /* free memory */
1093 SCIPfreeBufferArray(scip, &consvals);
1094 SCIPfreeBufferArray(scip, &consvars);
1095
1096 return SCIP_OKAY;
1097 }
1098
1099
1100 /** callback to check preconditions for diving, e.g., if an incumbent solution is available */
1101 static
1102 SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving)
1103 {
1104 /* Skip if problem doesn't contain indicator constraints.
1105 * If varbound constraints should be considered, skip only if there are also no varbound constraints.
1106 */
1107 *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "indicator")) == 0;
1108
1109 if( !*available )
1110 {
1111 SCIP_HEUR* heur;
1112 SCIP_HEURDATA* heurdata;
1113
1114 heur = SCIPdivesetGetHeur(diveset);
1115 assert(heur != NULL);
1116 heurdata = SCIPheurGetData(heur);
1117 assert(heurdata != NULL);
1118
1119 if( heurdata->runwithoutscinds && heurdata->usevarbounds )
1120 {
1121 *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "varbound")) == 0;
1122 }
1123 }
1124
1125 return SCIP_OKAY;
1126 }
1127
1128 /*
1129 * heuristic specific interface methods
1130 */
1131
1132 /** creates the indicatordiving heuristic and includes it in SCIP */
1133 SCIP_RETCODE SCIPincludeHeurIndicatordiving(
1134 SCIP* scip /**< SCIP data structure */
1135 )
1136 {
1137 SCIP_HEURDATA* heurdata;
1138 SCIP_HEUR* heur;
1139
1140 /* create indicatordiving primal heuristic data */
1141 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1142
1143 heur = NULL;
1144
1145 /* include primal heuristic */
1146 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1147 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1148 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIndicatordiving, heurdata) );
1149
1150 assert(heur != NULL);
1151
1152 /* set non fundamental callbacks via setter functions */
1153 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIndicatordiving) );
1154 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIndicatordiving) );
1155 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIndicatordiving) );
1156 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIndicatordiving) );
1157
1158 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
1159 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
1160 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
1161 DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
1162 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreIndicatordiving, divesetAvailableIndicatordiving) );
1163
1164 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundingfrac",
1165 "in violation case all fractional below this value are fixed to constant",
1166 &heurdata->roundingfrac, FALSE, DEFAULT_ROUNDINGFRAC, 0.0, 1.0, NULL, NULL) );
1167
1168 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/roundingmode",
1169 "decides which roundingmode is selected (0: conservative, 1: aggressive)",
1170 &heurdata->roundingmode, FALSE, DEFAULT_ROUNDINGMODE, 0, 1, NULL, NULL) );
1171
1172 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/semicontscoremode",
1173 "which values of semi-continuous variables should get a high score? (0: low, 1: middle, 2: high)",
1174 &heurdata->semicontscoremode, FALSE, DEFAULT_SEMICONTSCOREMODE, 0, 2, NULL, NULL) );
1175
1176 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarbounds",
1177 "should varbound constraints be considered?",
1178 &heurdata->usevarbounds, FALSE, DEFAULT_USEVARBOUNDS, NULL, NULL) );
1179
1180 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/runwithoutscinds",
1181 "should heur run if there are no indicator constraints modeling semicont. vars?",
1182 &heurdata->runwithoutscinds, FALSE, DEFAULT_RUNWITHOUTSCINDS, NULL, NULL) );
1183
1184 return SCIP_OKAY;
1185 }
1186