Scippy

SCIP

Solving Constraint Integer Programs

heur_indicatordiving.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_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"
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
111{
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 */
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};
133typedef struct SCVarData SCVARDATA;
134
135
136/** locally defined heuristic data */
137struct 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 */
161static
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 */
183static
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);
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 */
218static
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
266/** checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint */
267static
269 SCIP* scip, /**< SCIP data structure */
270 SCIP_VAR* cand, /**< candidate variable */
271 SCIP_HASHMAP* map, /**< pointer to hashmap containing varbound conss */
272 SCIP_CONS** cons, /**< pointer to store varbound constraint */
273 SCIP_Bool* isvarbound /**< pointer to store whether candidate variable is indicator variable */
274 )
275{
276 assert(scip != NULL);
277 assert(cand != NULL);
278 assert(map != NULL);
279 assert(cons != NULL);
280 assert(isvarbound != NULL);
281
282 *cons = NULL;
283 *isvarbound = FALSE;
284
286 return;
287
288 *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand);
289 if( *cons != NULL )
290 *isvarbound = TRUE;
291}
292
293/** adds an indicator to the data of a semicontinuous variable */
294static
296 SCIP* scip, /**< SCIP data structure */
297 SCVARDATA* scvdata, /**< semicontinuous variable data */
298 SCIP_VAR* indicator, /**< indicator to be added */
299 SCIP_Real val0, /**< value of the variable when indicator == 0 */
300 SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */
301 SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */
302 )
303{
304 int newsize;
305 int i;
306 SCIP_Bool found;
307 int pos;
308
309 assert(scvdata != NULL);
310 assert(indicator != NULL);
311
312 /* find the position where to insert */
313 if( scvdata->bvars == NULL )
314 {
315 assert(scvdata->nbnds == 0 && scvdata->bndssize == 0);
316 found = FALSE;
317 pos = 0;
318 }
319 else
320 {
321 found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos);
322 }
323
324 if( found )
325 return SCIP_OKAY;
326
327 /* ensure sizes */
328 if( scvdata->nbnds + 1 > scvdata->bndssize )
329 {
330 newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1);
331 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) );
332 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) );
333 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) );
334 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) );
335 scvdata->bndssize = newsize;
336 }
337 assert(scvdata->nbnds + 1 <= scvdata->bndssize);
338 assert(scvdata->bvars != NULL);
339
340 /* move entries if needed */
341 for( i = scvdata->nbnds; i > pos; --i )
342 {
343 /* coverity[var_deref_op] */
344 scvdata->bvars[i] = scvdata->bvars[i-1];
345 scvdata->vals0[i] = scvdata->vals0[i-1];
346 scvdata->lbs1[i] = scvdata->lbs1[i-1];
347 scvdata->ubs1[i] = scvdata->ubs1[i-1];
348 }
349
350 scvdata->bvars[pos] = indicator;
351 scvdata->vals0[pos] = val0;
352 scvdata->lbs1[pos] = lb1;
353 scvdata->ubs1[pos] = ub1;
354 ++scvdata->nbnds;
355
356 return SCIP_OKAY;
357}
358
359/** checks if a variable is semicontinuous and stores it data in the hashmap scvars
360 *
361 * A variable x is semicontinuous if its bounds depend on at least one binary variable called the indicator,
362 * and indicator == 0 => x == x^0 for some real constant x^0.
363 */
364static
366 SCIP* scip, /**< SCIP data structure */
367 SCIP_VAR* var, /**< the variable to check */
368 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
369 SCIP_Real constant, /**< value which should be equal to the constant */
370 SCIP_Bool* result /**< buffer to store whether var is semicontinuous */
371 )
372{
373 SCIP_Real lb0;
374 SCIP_Real ub0;
375 SCIP_Real lb1;
376 SCIP_Real ub1;
377 SCIP_Real glb;
378 SCIP_Real gub;
379 SCIP_Bool exists;
380 int c;
381 int pos;
382 SCIP_VAR** vlbvars;
383 SCIP_VAR** vubvars;
384 SCIP_Real* vlbcoefs;
385 SCIP_Real* vubcoefs;
386 SCIP_Real* vlbconstants;
387 SCIP_Real* vubconstants;
388 int nvlbs;
389 int nvubs;
390 SCVARDATA* scvdata;
391 SCIP_VAR* bvar;
392
393 assert(scip != NULL);
394 assert(var != NULL);
395 assert(scvars != NULL);
396 assert(result != NULL);
397
398 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
399 if( scvdata != NULL )
400 {
401 *result = TRUE;
402 return SCIP_OKAY;
403 }
404
405 vlbvars = SCIPvarGetVlbVars(var);
406 vubvars = SCIPvarGetVubVars(var);
407 vlbcoefs = SCIPvarGetVlbCoefs(var);
408 vubcoefs = SCIPvarGetVubCoefs(var);
409 vlbconstants = SCIPvarGetVlbConstants(var);
410 vubconstants = SCIPvarGetVubConstants(var);
411 nvlbs = SCIPvarGetNVlbs(var);
412 nvubs = SCIPvarGetNVubs(var);
413 glb = SCIPvarGetLbGlobal(var);
414 gub = SCIPvarGetUbGlobal(var);
415
416 pos = -1;
417
418 *result = FALSE;
419
420 /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1.
421 * Then check if there is an upper bound with this vlbvar and save ub0 and ub1.
422 * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0,
423 * save vlbvar and val0 to scvdata.
424 */
425 for( c = 0; c < nvlbs; ++c )
426 {
427 if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY )
428 continue;
429
430 bvar = vlbvars[c];
431
432 lb0 = MAX(vlbconstants[c], glb);
433 lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb);
434
435 /* look for bvar in vubvars */
436 if( vubvars != NULL )
437 exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos);
438 else
439 exists = FALSE;
440
441 if( exists )
442 {
443 /* save the upper bounds */
444 ub0 = MIN(vubconstants[pos], gub);
445 ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub);
446 }
447 else
448 {
449 /* if there is no upper bound with vubvar = bvar, use global var bounds */
450 ub0 = gub;
451 ub1 = gub;
452 }
453
454 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
455 if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
456 {
457 if( scvdata == NULL )
458 {
460 }
461 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
462 }
463 }
464
465 /* look for vubvars that have not been processed yet */
466 assert(vubvars != NULL || nvubs == 0);
467 for( c = 0; c < nvubs; ++c )
468 {
469 /* coverity[var_deref_op] */
470 if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/
471 continue;
472
473 bvar = vubvars[c]; /*lint !e613*/
474
475 /* skip vars that are in vlbvars */
476 if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) )
477 continue;
478
479 lb0 = glb;
480 lb1 = glb;
481 ub0 = MIN(vubconstants[c], gub);
482 ub1 = MIN(vubconstants[c] + vubcoefs[c], gub);
483
484 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
485 if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
486 {
487 if( scvdata == NULL )
488 {
490 }
491
492 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
493 }
494 }
495
496 if( scvdata != NULL )
497 {
498#ifdef SCIP_DEBUG
499 SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub);
500 for( c = 0; c < scvdata->nbnds; ++c )
501 {
502 SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]);
503 }
504#endif
505 SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) );
506 *result = TRUE;
507 }
508
509 return SCIP_OKAY;
510}
511
512/** checks if there are unfixed indicator variables modeling semicont. vars */
513static
515 SCIP* scip, /**< SCIP data structure */
516 SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */
517 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
518 SCIP_Bool* hasunfixedscindconss /**< pointer to store if there are unfixed indicator variables modeling semicont. vars */
519 )
520{
521 SCIP_CONS** indicatorconss;
522 SCIP_VAR** consvars;
523 SCIP_Real* consvals;
524 int nconss;
525 int i;
526
527 *hasunfixedscindconss = FALSE;
528 indicatorconss = SCIPconshdlrGetConss(conshdlr);
529 nconss = SCIPconshdlrGetNConss(conshdlr);
530 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
531 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
532
533 for( i = 0; i < nconss; i++ )
534 {
535 SCIP_VAR *binvar;
536 SCIP_VAR* semicontinuousvar;
537 SCIP_CONS* lincons;
538 SCIP_Real rhs;
539 int nconsvars;
540 SCIP_Bool success;
541 int v;
542
543 binvar = SCIPgetBinaryVarIndicator(indicatorconss[i]);
544
545 /* check if indicator variable is unfixed */
546 if( SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5 )
547 {
548 lincons = SCIPgetLinearConsIndicator(indicatorconss[i]);
549 rhs = SCIPconsGetRhs(scip, lincons, &success);
550 SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) );
551
552 /* check if constraint contains only two variables with finite rhs */
553 /* TODO: allow also indicators for lower bounds */
554 if( nconsvars == 2 && !SCIPisInfinity(scip, rhs) )
555 {
556 SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) );
557 SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) );
558
559 for( v = 0; v < nconsvars ; v++ )
560 {
561 if( consvars[v] == SCIPgetSlackVarIndicator(indicatorconss[i]) ) /* note that we have exact two variables */
562 continue;
563
564 semicontinuousvar = consvars[v];
565 SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, scvars, rhs, &success) );
566
567 /* check if semicontinuous variable */
568 if( success )
569 {
570 *hasunfixedscindconss = TRUE;
571 break;
572 }
573 }
574 if( *hasunfixedscindconss )
575 break;
576 }
577 }
578 }
579 SCIPfreeBufferArray(scip, &consvals);
580 SCIPfreeBufferArray(scip, &consvars);
581 return SCIP_OKAY;
582}
583
584/** creates and initializes hashmaps
585 *
586 * indicatormap: binary var -> indicator constraint
587 * varboundmap: binary var -> varbound constraint
588 *
589 * Currently exactly one constraint is assigned to a binary variable (per hashmap),
590 * but a binary variable can also control more than one constraint.
591 * TODO: Allow more than one corresponding indicator/varbound constraint per binary variable.
592 */
593static
595 SCIP* scip, /**< SCIP data structure */
596 SCIP_CONSHDLR* indicatorconshdlr, /**< indicator constraint handler */
597 SCIP_CONSHDLR* varboundconshdlr, /**< varbound constraint handler */
598 SCIP_Bool usevarbounds, /**< should varbound constraints be considered? */
599 SCIP_HASHMAP** indicatormap, /**< hashmap to store indicator constraints of binary variables */
600 SCIP_HASHMAP** varboundmap /**< hashmap to store varbound constraints of binary variables */
601 )
602{
603 SCIP_CONS** conss;
604 int nconss;
605 int i;
606
607 assert(strcmp(SCIPconshdlrGetName(indicatorconshdlr), "indicator") == 0);
608 assert(strcmp(SCIPconshdlrGetName(varboundconshdlr), "varbound") == 0);
609
610 /* indicator constraints */
611 nconss = SCIPconshdlrGetNConss(indicatorconshdlr);
612 conss = SCIPconshdlrGetConss(indicatorconshdlr);
613 SCIP_CALL( SCIPhashmapCreate(indicatormap, SCIPblkmem(scip), nconss) );
614 for( i = 0; i < nconss; i++ )
615 {
616 if( !SCIPhashmapExists(*indicatormap, SCIPgetBinaryVarIndicator(conss[i])) )
617 {
618 SCIP_CALL( SCIPhashmapInsert(*indicatormap, SCIPgetBinaryVarIndicator(conss[i]), conss[i]) );
619 }
620 }
621
622 /* varbound constraints */
623 if( usevarbounds )
624 {
625 nconss = SCIPconshdlrGetNConss(varboundconshdlr);
626 conss = SCIPconshdlrGetConss(varboundconshdlr);
627 SCIP_CALL( SCIPhashmapCreate(varboundmap, SCIPblkmem(scip), nconss) );
628 for( i = 0; i < nconss; i++ )
629 {
630 if( !SCIPhashmapExists(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i])) )
631 {
632 SCIP_CALL( SCIPhashmapInsert(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i]), conss[i]) );
633 }
634 }
635 }
636 return SCIP_OKAY;
637}
638
639#define MIN_RAND 1e-06
640#define MAX_RAND 1e-05
641
642/** calculate score and preferred rounding direction for the candidate variable */
643static
645 SCIP* scip, /**< SCIP data structure */
646 SCIP_DIVESET* diveset, /**< diving settings */
647 SCIP_VAR* cand, /**< candidate variable */
648 SCIP_Real candsfrac, /**< fractional part of solution value of candidate variable */
649 SCIP_Bool* roundup, /**< pointer to store whether the preferred rounding direction is upwards */
650 SCIP_Real* score /**< pointer for diving score value */
651 )
652{
653 SCIP_RANDNUMGEN* randnumgen;
654 SCIP_Real obj;
655
656 randnumgen = SCIPdivesetGetRandnumgen(diveset);
657 assert(randnumgen != NULL);
658
659 obj = SCIPvarGetObj(cand);
660
661 /* dive towards the pseudosolution, at the same time approximate the contribution to
662 * a potential Farkas-proof (infeasibility proof) by y^TA_i = c_i.
663 */
664 if( SCIPisNegative(scip, obj) )
665 *roundup = TRUE;
666 else if( SCIPisPositive(scip, obj) )
667 *roundup = FALSE;
668 else
669 {
670 if( SCIPisEQ(scip, candsfrac, 0.5) )
671 *roundup = !SCIPrandomGetInt(randnumgen, 0, 1);
672 else
673 *roundup = (candsfrac > 0.5);
674 }
675
676 /* larger score is better */
677 *score = REALABS(obj) + SCIPrandomGetReal(randnumgen, MIN_RAND, MAX_RAND);
678
679 /* prefer decisions on binary variables */
681 *score = -1.0 / *score;
682}
683
684
685/*
686 * Callback methods
687 */
688
689/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
690static
691SCIP_DECL_HEURCOPY(heurCopyIndicatordiving)
692{ /*lint --e{715}*/
693 assert(scip != NULL);
694 assert(heur != NULL);
695 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
696
697 /* call inclusion method of primal heuristic */
699
700 return SCIP_OKAY;
701}
702
703
704/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
705static
706SCIP_DECL_HEURFREE(heurFreeIndicatordiving)
707{ /*lint --e{715}*/
708 SCIP_HEURDATA* heurdata;
709
710 assert(heur != NULL);
711 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
712 assert(scip != NULL);
713
714 /* free heuristic data */
715 heurdata = SCIPheurGetData(heur);
716 assert(heurdata != NULL);
717
718 SCIPfreeBlockMemory(scip, &heurdata);
719 SCIPheurSetData(heur, NULL);
720
721 return SCIP_OKAY;
722}
723
724
725/** initialization method of primal heuristic (called after problem was transformed) */
726static
727SCIP_DECL_HEURINIT(heurInitIndicatordiving)
728{ /*lint --e{715}*/
729 SCIP_HEURDATA* heurdata;
730
731 assert(heur != NULL);
732 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
733 assert(scip != NULL);
734
735 /* get heuristic data */
736 heurdata = SCIPheurGetData(heur);
737 assert(heurdata != NULL);
738
739 /* create working data */
740 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
741 SCIP_CALL( SCIPhashmapCreate( &heurdata->scvars, SCIPblkmem( scip ), SCIPgetNVars(scip) ));
742
743 heurdata->indicatorconshdlr = SCIPfindConshdlr(scip, "indicator");
744 heurdata->varboundconshdlr = SCIPfindConshdlr(scip, "varbound");
745
746 return SCIP_OKAY;
747}
748
749
750/** deinitialization method of primal heuristic (called before transformed problem is freed) */
751static
752SCIP_DECL_HEUREXIT(heurExitIndicatordiving)
753{ /*lint --e{715}*/
754 SCIP_HEURDATA* heurdata;
755
756 assert(heur != NULL);
757 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
758 assert(scip != NULL);
759
760 /* get heuristic data */
761 heurdata = SCIPheurGetData(heur);
762 assert(heurdata != NULL);
763
764 /* free working data */
765 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
766 SCIP_CALL( releaseSCHashmap(scip, heurdata->scvars) );
767
768 return SCIP_OKAY;
769}
770
771
772/** execution method of primal heuristic */
773static
774SCIP_DECL_HEUREXEC(heurExecIndicatordiving)
775{ /*lint --e{715}*/
776 SCIP_HEURDATA* heurdata;
777 SCIP_DIVESET* diveset;
778 SCIP_Bool hasunfixedscindconss; /* are there unfixed indicator variables modeling a semicont. variable? */
779
780 heurdata = SCIPheurGetData(heur);
781 assert(heurdata != NULL);
782
783 assert(SCIPheurGetNDivesets(heur) > 0);
784 assert(SCIPheurGetDivesets(heur) != NULL);
785 diveset = SCIPheurGetDivesets(heur)[0];
786 assert(diveset != NULL);
787
788 assert(result != NULL);
789 *result = SCIP_DIDNOTRUN;
790
791 /* check if there are unfixed indicator variables modeling semicont. vars */
792 SCIP_CALL( hasUnfixedSCIndicator(scip, heurdata->indicatorconshdlr, heurdata->scvars, &hasunfixedscindconss) );
793
794 /* skip heuristic if problem doesn't contain unfixed indicator variables,
795 * or if there are no varbound constraints which should be considered
796 */
797 if( !hasunfixedscindconss && (!heurdata->runwithoutscinds || !heurdata->usevarbounds || SCIPconshdlrGetNConss(heurdata->varboundconshdlr) == 0) )
798 return SCIP_OKAY;
799
800 SCIPdebugMsg(scip, "call heurExecIndicatordiving at depth %d \n", SCIPgetDepth(scip));
801
802 /* create and initialize hashmaps */
803 SCIP_CALL( createMaps(scip, heurdata->indicatorconshdlr, heurdata->varboundconshdlr, heurdata->usevarbounds, &heurdata->indicatormap, &heurdata->varboundmap) );
804
805 /* (re-)set flags */
806 heurdata->gotoindconss = FALSE;
807 heurdata->containsviolindconss = FALSE;
808 heurdata->newnode = TRUE;
809 heurdata->probingdepth = -1;
810
811 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
812
813 /* free hashmaps since constraints can get removed/modified till the next call */
814 if( heurdata->usevarbounds )
815 SCIPhashmapFree(&heurdata->varboundmap);
816 SCIPhashmapFree(&heurdata->indicatormap);
817
818 SCIPdebugMsg(scip, "leave heurExecIndicatordiving\n");
819
820 return SCIP_OKAY;
821}
822
823
824/** calculate score and preferred rounding direction for the candidate variable */
825static
826SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving)
827{ /*lint --e{715}*/
828 SCIP_HEUR* heur;
829 SCIP_HEURDATA* heurdata;
830 SCIP_RANDNUMGEN* randnumgen;
831 SCIP_VAR** consvars;
832 SCIP_CONS* indicatorcons;
833 SCIP_CONS* varboundcons;
834 SCIP_CONS* lincons;
835 SCIP_VAR* nonoptionvar; /* second variable in linear cons which is not the option variable (indicator: slackvar, varbound: binary var) */
836 SCIP_VAR* semicontinuousvar;
837 SCIP_Real lpsolsemicontinuous;
838 SCVARDATA* scdata;
839 SCIP_Real* consvals;
840 SCIP_Real side;
841 int nconsvars;
842 int idxbvars; /* index of bounding variable in hashmap scdata */
843 SCIP_Bool isindicatorvar;
844 SCIP_Bool isvbdvar; /* variable bounding variable in varbound */
845 SCIP_Bool issemicont; /* indicates whether variable has (maybe) required semicont. properties */
846 SCIP_Bool fixconstant; /* should we fix the semicontinuous variable to its constant? */
847 SCIP_Bool success;
848 int v;
849 int b;
850
851 varboundcons = NULL;
852 semicontinuousvar = NULL;
853 scdata = NULL;
854 lpsolsemicontinuous = 0.0;
855 idxbvars = -1;
856 isvbdvar = FALSE;
857 issemicont = TRUE;
858
859 heur = SCIPdivesetGetHeur(diveset);
860 assert(heur != NULL);
861 heurdata = SCIPheurGetData(heur);
862 assert(heurdata != NULL);
863
864 randnumgen = SCIPdivesetGetRandnumgen(diveset);
865 assert(randnumgen != NULL);
866
867 /* check if we are at a new probing node; since diving heuristics backtrack at most one probing node, we are at a new
868 * node iff the probing depth increased */
869 if( heurdata->probingdepth < SCIPgetProbingDepth(scip) )
870 heurdata->newnode = TRUE;
871 else
872 {
873 assert(heurdata->probingdepth == SCIPgetProbingDepth(scip));
874 heurdata->newnode = FALSE;
875 }
876 heurdata->probingdepth = SCIPgetProbingDepth(scip);
877
878 /* skip if current candidate can not be determined by the indicator constraint handler and violated indicator
879 * constraints still exists */
880 if( !(SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5)
881 && heurdata->gotoindconss )
882 {
883 *score = SCIP_REAL_MIN;
884 *roundup = FALSE;
885 return SCIP_OKAY;
886 }
887 else
888 heurdata->gotoindconss = FALSE;
889
890 /* check if candidate variable is indicator variable */
891 checkAndGetIndicator(scip, cand, heurdata->indicatormap, &indicatorcons, &isindicatorvar,
892 &heurdata->containsviolindconss, heurdata->newnode, heurdata->sol, heurdata->indicatorconshdlr);
893
894 /* skip candidate in next calls since we have violated indicator constraints but current candidate is not determined
895 * by the indicator constraint handler */
896 if( heurdata->containsviolindconss &&
897 !((SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5) && isindicatorvar) )
898 {
899 heurdata->gotoindconss = TRUE;
900 *score = SCIP_REAL_MIN;
901 *roundup = FALSE;
902 return SCIP_OKAY;
903 }
904
905 /* check if candidate variable is bounding variable */
906 if( heurdata->usevarbounds && !isindicatorvar )
907 {
908 checkAndGetVarbound(scip, cand, heurdata->varboundmap, &varboundcons, &isvbdvar);
909 }
910
911 /* Return
912 * - if candidate variable is neither a indicator variable nor a variable bounding variable
913 * - or if candidate variable is not an indicator variable but there will be indicator variables as candidates
914 * - or if candidate variable is not an indicator variable and varbound constraints are not considered.
915 */
916 if( !isindicatorvar && (!isvbdvar || heurdata->containsviolindconss || !heurdata->usevarbounds) )
917 {
918 *score = SCIP_REAL_MIN;
919 *roundup = FALSE;
920
921 if( !heurdata->containsviolindconss && !isvbdvar )
922 {
923 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
924 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
925 }
926 return SCIP_OKAY;
927 }
928
929 SCIPdebugMsg(scip, "cand: %s, candsol: %.2f, candobjcoeff: %f\n", SCIPvarGetName(cand), candsol, SCIPvarGetObj(cand));
930
931 if( isindicatorvar ) /* prefer indicator constraint */
932 {
933 SCIP_Real rhs;
934
935 lincons = SCIPgetLinearConsIndicator(indicatorcons);
936 nonoptionvar = SCIPgetSlackVarIndicator(indicatorcons);
937 rhs = SCIPconsGetRhs(scip, lincons, &success);
938 issemicont = SCIPisInfinity(scip, -SCIPconsGetLhs(scip, lincons, &success)); /* TODO: allow also indicators for lower bounds */
939 side = rhs;
940 }
941 else
942 {
943 SCIP_Real rhs;
944 SCIP_Real lhs;
945
946 assert(isvbdvar);
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 SCIPdebugPrintCons(scip, lincons, NULL);
956
957 SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) );
958
959 if( nconsvars != 2 || !issemicont )
960 {
961 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
962 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
963 return SCIP_OKAY;
964 }
965
966 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) );
967 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
968 SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) );
969 SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) );
970
971 issemicont = FALSE;
972 for( v = 0; v < nconsvars ; v++ )
973 {
974 if( consvars[v] == nonoptionvar ) /* note that we have exact two variables */
975 continue;
976
977 semicontinuousvar = consvars[v];
978 lpsolsemicontinuous = SCIPvarGetLPSol( semicontinuousvar );
979 SCIPdebugMsg(scip, "%s lp sol %f %f\n", SCIPvarGetName( semicontinuousvar ), lpsolsemicontinuous,
980 consvals[v] );
981 SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, heurdata->scvars, side, &success) );
982
983 /* only allow semicontinuous variables */
984 if( success )
985 {
986 assert(SCIPhashmapExists(heurdata->scvars, (void*) semicontinuousvar));
987 scdata = (SCVARDATA*) SCIPhashmapGetImage(heurdata->scvars, (void*) semicontinuousvar);
988 assert(scdata != NULL);
989
990 for( b = 0; b < scdata->nbnds; b++ )
991 {
992 if( (scdata->bvars[b] == cand || (SCIPvarIsNegated(cand) && scdata->bvars[0] == SCIPvarGetNegationVar(cand)))
993 && SCIPisEQ(scip, side, scdata->vals0[b]) )
994 {
995 /* TODO: handle also more general variables;
996 * currently we handle only variables with domain vals0 < lb1 <= ub1 */
997 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->vals0[b]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[b]) )
998 {
999 issemicont = TRUE;
1000 idxbvars = b;
1001 break;
1002 }
1003 }
1004 }
1005 }
1006 }
1007
1008 /* only continue if semicontinuous variable */
1009 if( !issemicont )
1010 {
1011 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score);
1012 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */
1013 SCIPfreeBufferArray(scip, &consvals);
1014 SCIPfreeBufferArray(scip, &consvars);
1015 return SCIP_OKAY;
1016 }
1017 assert(idxbvars >= 0);
1018 assert(scdata != NULL);
1019
1020 /* Case: Variable is in range [lb1,ub1] */
1021 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[idxbvars]))
1022 {
1023 *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0);
1024 fixconstant = FALSE;
1025 }
1026 /* Case: Variable is equal to constant */
1027 else if( SCIPisEQ(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) )
1028 {
1029 *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0);
1030 fixconstant = TRUE;
1031 }
1032 /* Case: Variable is between constant and lb1 */
1033 else
1034 {
1035 SCIP_Real shiftedlpsolsemicontinuous = lpsolsemicontinuous;
1036 SCIP_Real shiftedlbs1 = scdata->lbs1[idxbvars];
1037
1038 assert(SCIPisGT(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) && SCIPisLT(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]));
1039
1040 /* handle case if constant of semicont. var is not zero -> shift values */
1041 if( !SCIPisZero(scip, scdata->vals0[idxbvars]) )
1042 {
1043 shiftedlpsolsemicontinuous -= scdata->vals0[idxbvars];
1044 shiftedlbs1 -= scdata->vals0[idxbvars];
1045 }
1046
1047 *score = 100 * (shiftedlbs1 - shiftedlpsolsemicontinuous) / shiftedlbs1;
1048 assert(*score>0);
1049
1050 switch( (INDICATORDIVINGROUNDINGMODE)heurdata->roundingmode )
1051 {
1053 fixconstant = (*score > (1 - heurdata->roundingfrac) * 100);
1054 break;
1056 fixconstant = (*score <= (1 - heurdata->roundingfrac) * 100);
1057 break;
1058 default:
1059 return SCIP_INVALIDDATA;
1060 }
1061
1062 switch( heurdata->semicontscoremode )
1063 {
1064 case 0:
1065 break;
1066 case 1:
1067 if( shiftedlpsolsemicontinuous < shiftedlbs1 * heurdata->roundingfrac )
1068 *score = 100 * (shiftedlpsolsemicontinuous / (heurdata->roundingfrac * shiftedlbs1));
1069 else
1070 *score = 100 * (-shiftedlpsolsemicontinuous / ((1 - heurdata->roundingfrac) * shiftedlbs1) + (1 / (1 - heurdata->roundingfrac)) );
1071 break;
1072 case 2:
1073 *score = 100 - *score;
1074 break;
1075 default:
1076 return SCIP_INVALIDDATA;
1077 }
1078 assert(*score>0);
1079 }
1080
1081 /* Set roundup depending on whether we have an indicator constraint or a varbound constraint:
1082 * - indicator constraint: roundup == fix to constant
1083 * - varbound constraint: roundup == push to range
1084 */
1085 *roundup = isindicatorvar ? fixconstant : !fixconstant; /*lint !e644*/
1086
1087 /* free memory */
1088 SCIPfreeBufferArray(scip, &consvals);
1089 SCIPfreeBufferArray(scip, &consvars);
1090
1091 return SCIP_OKAY;
1092}
1093
1094
1095/** callback to check preconditions for diving, e.g., if an incumbent solution is available */
1096static
1097SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving)
1098{
1099 /* Skip if problem doesn't contain indicator constraints.
1100 * If varbound constraints should be considered, skip only if there are also no varbound constraints.
1101 */
1102 *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "indicator")) == 0;
1103
1104 if( !*available )
1105 {
1106 SCIP_HEUR* heur;
1107 SCIP_HEURDATA* heurdata;
1108
1109 heur = SCIPdivesetGetHeur(diveset);
1110 assert(heur != NULL);
1111 heurdata = SCIPheurGetData(heur);
1112 assert(heurdata != NULL);
1113
1114 if( heurdata->runwithoutscinds && heurdata->usevarbounds )
1115 {
1116 *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "varbound")) == 0;
1117 }
1118 }
1119
1120 return SCIP_OKAY;
1121}
1122
1123/*
1124 * heuristic specific interface methods
1125 */
1126
1127/** creates the indicatordiving heuristic and includes it in SCIP */
1129 SCIP* scip /**< SCIP data structure */
1130 )
1131{
1132 SCIP_HEURDATA* heurdata;
1133 SCIP_HEUR* heur;
1134
1135 /* create indicatordiving primal heuristic data */
1136 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1137
1138 heur = NULL;
1139
1140 /* include primal heuristic */
1143 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIndicatordiving, heurdata) );
1144
1145 assert(heur != NULL);
1146
1147 /* set non fundamental callbacks via setter functions */
1148 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIndicatordiving) );
1149 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIndicatordiving) );
1150 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIndicatordiving) );
1151 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIndicatordiving) );
1152
1153 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
1157 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreIndicatordiving, divesetAvailableIndicatordiving) );
1158
1159 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundingfrac",
1160 "in violation case all fractional below this value are fixed to constant",
1161 &heurdata->roundingfrac, FALSE, DEFAULT_ROUNDINGFRAC, 0.0, 1.0, NULL, NULL) );
1162
1163 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/roundingmode",
1164 "decides which roundingmode is selected (0: conservative, 1: aggressive)",
1165 &heurdata->roundingmode, FALSE, DEFAULT_ROUNDINGMODE, 0, 1, NULL, NULL) );
1166
1167 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/semicontscoremode",
1168 "which values of semi-continuous variables should get a high score? (0: low, 1: middle, 2: high)",
1169 &heurdata->semicontscoremode, FALSE, DEFAULT_SEMICONTSCOREMODE, 0, 2, NULL, NULL) );
1170
1171 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarbounds",
1172 "should varbound constraints be considered?",
1173 &heurdata->usevarbounds, FALSE, DEFAULT_USEVARBOUNDS, NULL, NULL) );
1174
1175 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/runwithoutscinds",
1176 "should heur run if there are no indicator constraints modeling semicont. vars?",
1177 &heurdata->runwithoutscinds, FALSE, DEFAULT_RUNWITHOUTSCINDS, NULL, NULL) );
1178
1179 return SCIP_OKAY;
1180}
SCIP_VAR ** b
Definition: circlepacking.c:65
constraint handler for indicator constraints
Constraint handler for variable bound constraints .
#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_REAL_MIN
Definition: def.h:175
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
SCIP_VAR * SCIPgetSlackVarIndicator(SCIP_CONS *cons)
SCIP_CONS * SCIPgetLinearConsIndicator(SCIP_CONS *cons)
SCIP_Bool SCIPisViolatedIndicator(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPincludeHeurIndicatordiving(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4636
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4670
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool ispublic, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)))
Definition: scip_heur.c:318
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:720
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1661
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1651
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
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_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18292
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18302
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17574
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17904
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18344
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:416
#define DEFAULT_ONLYLPBRANCHCANDS
static SCIP_RETCODE releaseSCHashmap(SCIP *scip, SCIP_HASHMAP *hashmap)
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving)
#define DEFAULT_ROUNDINGMODE
static void checkAndGetIndicator(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isindicator, SCIP_Bool *containsviolindconss, SCIP_Bool newnode, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr)
static SCIP_RETCODE createMaps(SCIP *scip, SCIP_CONSHDLR *indicatorconshdlr, SCIP_CONSHDLR *varboundconshdlr, SCIP_Bool usevarbounds, SCIP_HASHMAP **indicatormap, SCIP_HASHMAP **varboundmap)
#define HEUR_TIMING
#define DEFAULT_USEVARBOUNDS
enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
static SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving)
static SCIP_RETCODE hasUnfixedSCIndicator(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HASHMAP *scvars, SCIP_Bool *hasunfixedscindconss)
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
static void getScoreOfFarkasDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_VAR *cand, SCIP_Real candsfrac, SCIP_Bool *roundup, SCIP_Real *score)
#define DEFAULT_SEMICONTSCOREMODE
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_ROUNDINGFRAC
#define DEFAULT_MAXLPITEROFS
static SCIP_DECL_HEUREXIT(heurExitIndicatordiving)
static SCIP_DECL_HEURINIT(heurInitIndicatordiving)
static SCIP_RETCODE varIsSemicontinuous(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Real constant, SCIP_Bool *result)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define HEUR_NAME
static void checkAndGetVarbound(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isvarbound)
static SCIP_DECL_HEURFREE(heurFreeIndicatordiving)
#define MAX_RAND
static SCIP_RETCODE addSCVarIndicator(SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
static SCIP_Bool isViolatedAndNotFixed(SCIP *scip, SCIP_SOL *sol, SCIP_CONS *cons)
#define DEFAULT_RUNWITHOUTSCINDS
#define DIVESET_ISPUBLIC
#define HEUR_FREQ
#define MIN_RAND
#define DEFAULT_MINRELDEPTH
#define HEUR_USESSUBSCIP
IndicatorDivingRoundingMode
@ ROUNDING_CONSERVATIVE
@ ROUNDING_AGGRESSIVE
static SCIP_DECL_HEURCOPY(heurCopyIndicatordiving)
static SCIP_DECL_HEUREXEC(heurExecIndicatordiving)
LP diving heuristic that fixes indicator variables controlling semicontinuous variables.
methods commonly used by primal heuristics
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:112
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
Definition: misc_linear.c:179
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:48
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for managing constraints
public methods for primal heuristics
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
SCIP_SOL * sol
Definition: struct_heur.h:71
SCIP_Real * vals0
SCIP_VAR ** bvars
SCIP_Real * ubs1
SCIP_Real * lbs1
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_DIVECONTEXT_SINGLE
Definition: type_heur.h:69
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62