1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_dualval.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief dualval primal heuristic
19 * @author Tobias Buchwald
20 *
21 * This heuristic tries to find solutions by taking the LP or NLP, rounding solution values, fixing the variables to the
22 * rounded values and then changing some of the values.To determine which variable is changed we give each variable a
23 * ranking dependent on its dualvalue. We work with a transformed problem that is always feasible and has objective = 0
24 * iff the original problem is also feasible. Thus we cannot expect to find really good solutions.
25 */
26
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28
29 #include "blockmemshell/memory.h"
30 #include "nlpi/type_expr.h"
31 #include "nlpi/type_nlpi.h"
32 #include "scip/cons_indicator.h"
33 #include "scip/cons_knapsack.h"
34 #include "scip/cons_linear.h"
35 #include "scip/cons_logicor.h"
36 #include "scip/cons_setppc.h"
37 #include "scip/cons_varbound.h"
38 #include "scip/heur_dualval.h"
39 #include "scip/pub_cons.h"
40 #include "scip/pub_event.h"
41 #include "scip/pub_heur.h"
42 #include "scip/pub_message.h"
43 #include "scip/pub_misc.h"
44 #include "scip/pub_misc_sort.h"
45 #include "scip/pub_nlp.h"
46 #include "scip/pub_sol.h"
47 #include "scip/pub_var.h"
48 #include "scip/scip_branch.h"
49 #include "scip/scip_cons.h"
50 #include "scip/scip_copy.h"
51 #include "scip/scip_event.h"
52 #include "scip/scip_general.h"
53 #include "scip/scip_heur.h"
54 #include "scip/scip_lp.h"
55 #include "scip/scip_mem.h"
56 #include "scip/scip_message.h"
57 #include "scip/scip_nlp.h"
58 #include "scip/scip_numerics.h"
59 #include "scip/scip_param.h"
60 #include "scip/scip_prob.h"
61 #include "scip/scip_sol.h"
62 #include "scip/scip_solve.h"
63 #include "scip/scip_solvingstats.h"
64 #include "scip/scip_var.h"
65 #include <string.h>
66
67 #define HEUR_NAME "dualval"
68 #define HEUR_DESC "primal heuristic using dual values"
69 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
70 #define HEUR_PRIORITY 0
71 #define HEUR_FREQ -1
72 #define HEUR_FREQOFS 0
73 #define HEUR_MAXDEPTH -1
74 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
75 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
76
77 #define EVENTHDLR_NAME "lpsol_dualval"
78 #define EVENTHDLR_DESC "event handler for lp solution found"
79
80 /* default values for user parameters */
81 /* boolean parameters */
82 #define DEFAULT_FORCEIMPROVEMENTS FALSE /**< exit if objective doesn't improve */
83 #define DEFAULT_ONLYCHEAPER TRUE /**< add constraint to ensure that discrete vars are improving */
84 #define DEFAULT_ONLYLEAVES FALSE /**< disable the heuristic if it was not called at a leaf of the B&B tree */
85 #define DEFAULT_RELAXINDICATORS FALSE /**< relax the indicator variables by introducing continuous copies */
86 #define DEFAULT_RELAXCONTVARS FALSE /**< enable relaxation of continous variables */
87
88 /* integer parameters */
89 #define DEFAULT_HEURVERBLEVEL 0 /**< verblevel of the heuristic, default is 0 to display nothing */
90 #define DEFAULT_NLPVERBLEVEL 0 /**< verblevel of the nlp solver, can be 0 or 1 */
91 #define DEFAULT_RANKVALUE 10 /**< number of ranks that should be displayed when the heuristic is called */
92 #define DEFAULT_MAXCALLS 25 /**< maximal number of recursive calls of the heuristic (if dynamicdepth is off) */
93 #define DEFAULT_DYNAMICDEPTH 0 /**< says if and how the recursion depth is computed at runtime */
94 #define DEFAULT_MAXEQUALRANKS 50 /**< maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1 */
95
96 /* real value parameters */
97 #define DEFAULT_MINGAP 5.0 /**< minimal gap for which we still run the heuristic, if gap is less we return without doing anything */
98 #define DEFAULT_LAMBDASLACK 1.0 /**< value added to objective of slack variables, must not be zero */
99 #define DEFAULT_LAMBDAOBJ 0.0 /**< scaling factor for the objective function */
100
101
102 /**primal heuristic data */
103 struct SCIP_HeurData
104 {
105 SCIP* subscip; /**< copy of CIP */
106 SCIP_VAR** integervars; /**< array of all binary and integer variables of the original scip */
107 SCIP_HASHMAP* varsciptosubscip; /**< mapping variables in SCIP to sub-SCIP variables */
108 SCIP_HASHMAP* varsubsciptoscip; /**< mapping variables in sub-SCIP to SCIP variables */
109 SCIP_HASHMAP* origsubscipConsMap; /**< maps constraints from the transformed problem to corresponding constraints in subproblem */
110 SCIP_HASHMAP* switchedvars; /**< stores the last value of switched var to avoid cycling */
111 SCIP_HASHMAP* switchedvars2; /**< stores the second last value of switched vars to avoid cycling */
112 SCIP_HASHMAP* relaxcons; /**< maps subscip variables to their relaxation constraints */
113 SCIP_HASHMAP* relaxconsindi; /**< maps indicator variables and their copies to relaxation constraint */
114 SCIP_HASHMAP* slacktoindivarsmap; /**< maps slack variables of indicator constraint to indicator variable */
115 SCIP_HASHMAP* indicators; /**< maps indicator variables to their indicator constraint */
116 SCIP_HASHMAP* conss2nlrow; /**< maps constraint to the corresponding nlrow */
117 SCIP_HASHMAP* dualvalues; /**< maps constraints of the subscip to their dual values */
118 SCIP_HASHMAP* slack2var; /**< maps slack variables to the variable they actually relax */
119 SCIP_HASHMAP* indicopymap; /**< maps indicator variables to their copy variables */
120 SCIP_HASHMAP* indicopymapback; /**< maps copy variables to their indicator variables */
121 SCIP_HASHMAP* slackvarlbMap; /**< mapping used indicators to slack variables lower bound*/
122 SCIP_HASHMAP* slackvarubMap; /**< mapping used indicators to slack variables upper bound*/
123 SCIP_CONS* objbound; /**< contraint for upper bound of the objective function */
124 SCIP_Real prevobjective; /**< stores objective value (of the original) so we know if it improved */
125 SCIP_Real mingap; /**< don't run the heuristic if the gap is less than mingap */
126 SCIP_Real lambdaslack; /**< the value added to the objective function */
127 SCIP_Real lambdaobj; /**< the value the original objective function is scaled with */
128 int integervarssize; /**< size of integervars array */
129 int nintegervars; /**< number of integer variables in the original problem */
130 int heurverblevel; /**< verblevel, range is 0 to 4 */
131 int nlpverblevel; /**< sets verblevel of the included nlp */
132 int rankvalue; /**< print out the 'rankvalue' highest ranks during iterations */
133 int maxcalls; /**< maximum number of allowed iterations */
134 int nonimprovingRounds; /**< nr of rounds, where the algorithm has not improved */
135 int dynamicdepth; /**< how should the number of calls be computed? */
136 int maxequalranks; /**< maximum number of variables that may have maximal (absolute) rank */
137 int nvars; /**< number of active transformed variables in SCIP */
138 int nsubvars; /**< number of original variables in sub-SCIP */
139 int usedcalls; /**< number of currently used iterations */
140 SCIP_Bool isnlp; /**< tells us, whether we have nonlinearities in our program or not */
141 SCIP_Bool forceimprovements; /**< whether we exit on nonimproving objective in the relaxation or not */
142 SCIP_Bool prevInfeasible; /**< will tell us if the previous call led to an infeasible fixing */
143 SCIP_Bool solfound; /**< parameter says, if we already found a solution and have to go back */
144 SCIP_Bool subscipisvalid; /**< whether all constraints have been copied */
145 SCIP_Bool switchdifferent; /**< tells us that we want to go up one level and switch another variable */
146 SCIP_Bool triedsetupsubscip; /**< whether we have tried to setup a sub-SCIP */
147 SCIP_Bool onlycheaper; /**< add constraint to ensure that discrete vars are improving */
148 SCIP_Bool onlyleaves; /**< don't use heuristic if we are not in a leaf of the B&B tree */
149 SCIP_Bool relaxindicators; /**< additionally relax indicator variables */
150 SCIP_Bool relaxcontvars; /**< additionally relax continous variables */
151 };
152
153 /*
154 * event handler method
155 */
156
157 /** initialization method of event handler (called after problem was transformed) */
158 static
SCIP_DECL_EVENTINIT(eventInitLPsol)159 SCIP_DECL_EVENTINIT(eventInitLPsol)
160 { /*lint --e{715}*/
161 assert(scip != NULL);
162 assert(eventhdlr != NULL);
163
164 /* notify SCIP that your event handler wants to react on the event type best solution found */
165 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_FIRSTLPSOLVED | SCIP_EVENTTYPE_LPSOLVED, eventhdlr, NULL, NULL) );
166
167 return SCIP_OKAY;
168 }
169
170 /** deinitialization method of event handler (called before transformed problem is freed) */
171 static
SCIP_DECL_EVENTEXIT(eventExitLPsol)172 SCIP_DECL_EVENTEXIT(eventExitLPsol)
173 { /*lint --e{715}*/
174 assert(scip != NULL);
175 assert(eventhdlr != NULL);
176
177 /* notify SCIP that your event handler wants to drop the event type best solution found */
178 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_FIRSTLPSOLVED | SCIP_EVENTTYPE_LPSOLVED, eventhdlr, NULL, -1) );
179
180 return SCIP_OKAY;
181 }
182
183 /** execution method of event handler */
184 static
SCIP_DECL_EVENTEXEC(eventExecLPsol)185 SCIP_DECL_EVENTEXEC(eventExecLPsol)
186 { /*lint --e{715}*/
187 int i;
188 int nsubconss;
189 SCIP_HEURDATA* heurdata;
190 SCIP_CONS** subconss;
191 SCIP_Real* dualval;
192
193 assert(eventhdlr != NULL);
194 assert(event != NULL);
195 assert(scip != NULL);
196 assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
197
198 heurdata = (SCIP_HEURDATA* )SCIPeventhdlrGetData(eventhdlr);
199 nsubconss = SCIPgetNOrigConss(heurdata->subscip);
200 subconss = SCIPgetOrigConss(heurdata->subscip);
201
202 /* free memory of all entries and clear the hashmap before filling it */
203 for( i = 0; i < nsubconss; i++ )
204 {
205 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
206 if( dualval != NULL )
207 SCIPfreeBlockMemoryArray(heurdata->subscip, &dualval, 1);
208 }
209 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
210
211 /* insert dualvalues from LP into a hashmap */
212 for( i = 0; i < nsubconss; i++ )
213 {
214 SCIP_CONS* transcons = NULL;
215 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, subconss[i], &transcons) );
216
217 if( transcons == NULL )
218 continue;
219
220 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") )
221 continue;
222
223 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
224 *dualval = -SCIPgetDualsolLinear(heurdata->subscip, transcons );
225 SCIP_CALL( SCIPhashmapInsert(heurdata->dualvalues, subconss[i], dualval) );
226 }
227 if( heurdata->heurverblevel > 2 )
228 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "LP solved event!\n");
229
230 return SCIP_OKAY;
231 }
232
233 /** includes event handler for best solution found */
234 static
SCIPincludeEventHdlrLPsol(SCIP * scip,SCIP_HEURDATA * heurdata)235 SCIP_RETCODE SCIPincludeEventHdlrLPsol(
236 SCIP* scip, /**< SCIP data structure */
237 SCIP_HEURDATA* heurdata /**< heuristic data */
238 )
239 {
240 SCIP_EVENTHDLRDATA* eventhdlrdata;
241 SCIP_EVENTHDLR* eventhdlr = NULL;
242
243 eventhdlrdata = (SCIP_EVENTHDLRDATA*)heurdata;
244
245 /* create event handler */
246 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLPsol, eventhdlrdata) );
247 assert(eventhdlr != NULL);
248
249 SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitLPsol) );
250 SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitLPsol) );
251
252 return SCIP_OKAY;
253 }
254
255 /*
256 * Local methods
257 */
258
259 /** releases all variables or constraints from given hash map */
260 static
releaseHashmapEntries(SCIP * scip,SCIP_HASHMAP * hashmap,SCIP_Bool isvarmap)261 SCIP_RETCODE releaseHashmapEntries(
262 SCIP* scip, /**< SCIP data structure */
263 SCIP_HASHMAP* hashmap, /**< hashmap */
264 SCIP_Bool isvarmap /**< are the entries variables or constraints? */
265 )
266 {
267 int nentries;
268 int i;
269
270 assert(scip != NULL);
271 assert(hashmap != NULL);
272
273 nentries = SCIPhashmapGetNEntries(hashmap);
274
275 for( i = 0; i < nentries; ++i )
276 {
277 SCIP_HASHMAPENTRY* entry;
278 entry = SCIPhashmapGetEntry(hashmap, i);
279
280 if( entry != NULL )
281 {
282 if( isvarmap )
283 {
284 SCIP_VAR* var;
285 var = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
286
287 SCIP_CALL( SCIPreleaseVar(scip, &var) );
288 }
289 else
290 {
291 SCIP_CONS* cons;
292 cons = (SCIP_CONS*) SCIPhashmapEntryGetImage(entry);
293
294 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
295 }
296 }
297 }
298
299 return SCIP_OKAY;
300 }
301
302 /** releases all NLP rows from given hash map */
303 static
releaseHashmapNLPRows(SCIP * scip,SCIP_HASHMAP * hashmap)304 SCIP_RETCODE releaseHashmapNLPRows(
305 SCIP* scip, /**< SCIP data structure */
306 SCIP_HASHMAP* hashmap /**< hashmap */
307 )
308 {
309 int nentries;
310 int i;
311
312 assert(scip != NULL);
313 assert(hashmap != NULL);
314
315 nentries = SCIPhashmapGetNEntries(hashmap);
316
317 for( i = 0; i < nentries; ++i )
318 {
319 SCIP_HASHMAPENTRY* entry;
320 entry = SCIPhashmapGetEntry(hashmap, i);
321 if( entry != NULL )
322 {
323 SCIP_NLROW* nlrow;
324 nlrow = (SCIP_NLROW*) SCIPhashmapEntryGetImage(entry);
325
326 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
327 }
328 }
329
330 return SCIP_OKAY;
331 }
332
333
334 /** adds linear constraints from a SCIP instance to its NLP */
335 static
addLinearConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_Bool addcombconss,SCIP_Bool addcontconss,SCIP_HEURDATA * heurdata)336 SCIP_RETCODE addLinearConstraints(
337 SCIP* scip, /**< SCIP data structure */
338 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
339 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
340 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */
341 SCIP_HEURDATA* heurdata /**< heuristic data structure */
342 )
343 {
344 SCIP_CONS** conss;
345 SCIP_VAR** vars;
346 SCIP_NLROW* nlrow;
347 int nconss;
348 int i;
349 int j;
350 int nvars;
351 SCIP_Bool iscombinatorial;
352
353 assert(scip != NULL);
354 assert(conshdlr != NULL);
355
356 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
357 conss = SCIPconshdlrGetConss(conshdlr);
358
359 if( nconss == 0 )
360 return SCIP_OKAY;
361
362 for( i = 0; i < nconss; ++i )
363 {
364 /* skip local and redundant constraints */
365 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
366 continue;
367
368 /* under some circumstances, this method may be called even though the problem has been shown to be
369 * infeasible in presolve already.
370 * this infeasibility may come from a linear constraint with lhs > rhs
371 * the NLP does not allow such constraints, so we skip them here
372 */
373 if( !SCIPisRelLE(scip, SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i])) )
374 continue;
375
376 nvars = SCIPgetNVarsLinear(scip, conss[i]);
377 vars = SCIPgetVarsLinear(scip, conss[i]);
378
379 /* check if constraint should be added, only need this check if we do not wanna any constraint anyway */
380 if( !addcombconss || !addcontconss )
381 {
382 iscombinatorial = TRUE;
383
384 for( j = 0; j < nvars; ++j )
385 {
386 if( SCIPvarGetType(vars[j]) >= SCIP_VARTYPE_CONTINUOUS )
387 {
388 iscombinatorial = FALSE;
389 break;
390 }
391 }
392
393 /* skip constraint, if not of interest */
394 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) )
395 continue;
396 }
397
398 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
399 SCIPgetNVarsLinear(scip, conss[i]), SCIPgetVarsLinear(scip, conss[i]), SCIPgetValsLinear(scip, conss[i]),
400 0, NULL, 0, NULL, NULL,
401 SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i]),
402 SCIP_EXPRCURV_LINEAR) );
403
404 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
405 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
406 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
407 }
408
409 return SCIP_OKAY;
410 }
411
412 /** adds variable bound constraints from a SCIP instance to its NLP */
413 static
addVarboundConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_Bool addcombconss,SCIP_Bool addcontconss,SCIP_HEURDATA * heurdata)414 SCIP_RETCODE addVarboundConstraints(
415 SCIP* scip, /**< SCIP data structure */
416 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
417 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
418 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */
419 SCIP_HEURDATA* heurdata /**< heuristic data structure */
420 )
421 {
422 SCIP_CONS** conss;
423 int nconss;
424 SCIP_NLROW* nlrow;
425 int i;
426 SCIP_VAR* vars[2];
427 SCIP_Real coefs[2];
428 SCIP_Bool iscombinatorial;
429
430 assert(scip != NULL);
431 assert(conshdlr != NULL);
432
433 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
434 conss = SCIPconshdlrGetConss(conshdlr);
435
436 if( nconss == 0 )
437 return SCIP_OKAY;
438
439 for( i = 0; i < nconss; ++i )
440 {
441 /* skip local and redundant constraints */
442 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
443 continue;
444
445 vars[0] = SCIPgetVarVarbound(scip, conss[i]);
446 vars[1] = SCIPgetVbdvarVarbound(scip, conss[i]);
447
448 iscombinatorial = SCIPvarGetType(vars[0]) < SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(vars[1]) < SCIP_VARTYPE_CONTINUOUS;
449
450 /* skip constraint, if not of interest */
451 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) )
452 continue;
453
454 coefs[0] = 1.0;
455 coefs[1] = SCIPgetVbdcoefVarbound(scip, conss[i]);
456
457 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
458 2, vars, coefs,
459 0, NULL, 0, NULL, NULL,
460 SCIPgetLhsVarbound(scip, conss[i]), SCIPgetRhsVarbound(scip, conss[i]),
461 SCIP_EXPRCURV_LINEAR) );
462
463 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
464 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
465 }
466
467 return SCIP_OKAY;
468 }
469
470
471 /** adds logic-or constraints to NLP */
472 static
addLogicOrConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_HEURDATA * heurdata)473 SCIP_RETCODE addLogicOrConstraints(
474 SCIP* scip, /**< SCIP data structure */
475 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
476 SCIP_HEURDATA* heurdata /**< heuristic data structure */
477 )
478 {
479 SCIP_CONS** conss;
480 int nconss;
481 SCIP_NLROW* nlrow;
482 int i;
483 int j;
484 SCIP_Real* coefs;
485 int coefssize;
486 int nvars;
487
488 assert(scip != NULL);
489 assert(conshdlr != NULL);
490
491 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
492 if( !nconss )
493 return SCIP_OKAY;
494
495 conss = SCIPconshdlrGetConss(conshdlr);
496
497 coefs = NULL;
498 coefssize = 0;
499
500 for( i = 0; i < nconss; ++i )
501 {
502 /* skip local and redundant constraints */
503 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
504 continue;
505
506 nvars = SCIPgetNVarsLogicor(scip, conss[i]);
507
508 if( coefssize < nvars )
509 {
510 if( coefs == NULL )
511 {
512 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
513 }
514 else
515 {
516 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
517 }
518 for( j = coefssize; j < nvars; ++j )
519 coefs[j] = 1.0;
520 coefssize = nvars;
521 }
522
523 /* logic or constraints: 1 == sum_j x_j */
524 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
525 nvars, SCIPgetVarsLogicor(scip, conss[i]), coefs,
526 0, NULL, 0, NULL, NULL,
527 1.0, SCIPinfinity(scip),
528 SCIP_EXPRCURV_LINEAR) );
529
530 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
531 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
532 }
533
534 SCIPfreeBufferArrayNull(scip, &coefs);
535
536 return SCIP_OKAY;
537 }
538
539 /** adds setppc constraints to NLP */
540 static
addSetppcConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_HEURDATA * heurdata)541 SCIP_RETCODE addSetppcConstraints(
542 SCIP* scip, /**< SCIP data structure */
543 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
544 SCIP_HEURDATA* heurdata /**< heuristic data structure */
545 )
546 {
547 SCIP_CONS** conss;
548 int nconss;
549 SCIP_NLROW* nlrow;
550 int i;
551 int j;
552 SCIP_Real* coefs;
553 int coefssize;
554 int nvars;
555 SCIP_Real lhs;
556 SCIP_Real rhs;
557
558 assert(scip != NULL);
559 assert(conshdlr != NULL);
560
561 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
562 if( nconss == 0 )
563 return SCIP_OKAY;
564
565 conss = SCIPconshdlrGetConss(conshdlr);
566
567 coefs = NULL;
568 coefssize = 0;
569
570 for( i = 0; i < nconss; ++i )
571 {
572 /* skip local and redundant constraints */
573 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
574 continue;
575
576 nvars = SCIPgetNVarsSetppc(scip, conss[i]);
577
578 if( coefssize < nvars )
579 {
580 if( coefs == NULL )
581 {
582 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
583 }
584 else
585 {
586 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
587 }
588 for( j = coefssize; j < nvars; ++j )
589 coefs[j] = 1.0;
590 coefssize = nvars;
591 }
592
593 /* setppc constraint: 1 ~ sum_j x_j */
594
595 switch( SCIPgetTypeSetppc(scip, conss[i]) )
596 {
597 case SCIP_SETPPCTYPE_PARTITIONING:
598 lhs = 1.0;
599 rhs = 1.0;
600 break;
601
602 case SCIP_SETPPCTYPE_PACKING:
603 lhs = -SCIPinfinity(scip);
604 rhs = 1.0;
605 break;
606
607 case SCIP_SETPPCTYPE_COVERING:
608 lhs = 1.0;
609 rhs = SCIPinfinity(scip);
610 break;
611
612 default:
613 SCIPerrorMessage("unexpected setppc type\n");
614 return SCIP_ERROR;
615 }
616
617 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
618 nvars, SCIPgetVarsSetppc(scip, conss[i]), coefs,
619 0, NULL, 0, NULL, NULL,
620 lhs, rhs,
621 SCIP_EXPRCURV_LINEAR) );
622
623 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
624 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
625 }
626
627 SCIPfreeBufferArrayNull(scip, &coefs);
628
629 return SCIP_OKAY;
630 }
631
632 /** adds knapsack constraints to NLP */
633 static
addKnapsackConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_HEURDATA * heurdata)634 SCIP_RETCODE addKnapsackConstraints(
635 SCIP* scip, /**< SCIP data structure */
636 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
637 SCIP_HEURDATA* heurdata /**< heuristic data structure */
638 )
639 {
640 SCIP_CONS** conss;
641 int nconss;
642 SCIP_NLROW* nlrow;
643 int i;
644 int j;
645 SCIP_Real* coefs;
646 int coefssize;
647 int nvars;
648
649 assert(scip != NULL);
650 assert(conshdlr != NULL);
651
652 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
653 if( nconss == 0 )
654 return SCIP_OKAY;
655
656 conss = SCIPconshdlrGetConss(conshdlr);
657 assert(conss != NULL);
658
659 coefs = NULL;
660 coefssize = 0;
661
662 for( i = 0; i < nconss; ++i )
663 {
664 SCIP_Longint* weights;
665
666 /* skip local and redundant constraints */
667 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
668 continue;
669
670 nvars = SCIPgetNVarsKnapsack(scip, conss[i]);
671
672 if( coefssize < nvars )
673 {
674 if( coefs == NULL )
675 {
676 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
677 }
678 else
679 {
680 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
681 }
682 coefssize = nvars;
683 }
684
685 weights = SCIPgetWeightsKnapsack(scip, conss[i]);
686 for( j = 0; j < nvars; ++j )
687 coefs[j] = (SCIP_Real)weights[j]; /*lint !e613*/
688
689 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
690 nvars, SCIPgetVarsKnapsack(scip, conss[i]), coefs,
691 0, NULL, 0, NULL, NULL,
692 -SCIPinfinity(scip), (SCIP_Real)SCIPgetCapacityKnapsack(scip, conss[i]),
693 SCIP_EXPRCURV_LINEAR) );
694
695 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
696 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
697 }
698
699 SCIPfreeBufferArrayNull(scip, &coefs);
700
701 return SCIP_OKAY;
702 }
703
704
705 /** adds combinatorial and/or continuous variants of linear constraints from a SCIP instance to its NLP */
706 static
addLinearConstraintsToNlp(SCIP * scip,SCIP_Bool addcombconss,SCIP_Bool addcontconss,SCIP_HEURDATA * heurdata)707 SCIP_RETCODE addLinearConstraintsToNlp(
708 SCIP* scip, /**< SCIP data structure */
709 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
710 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */
711 SCIP_HEURDATA* heurdata /**< heuristic data structure */
712 )
713 {
714 SCIP_CONSHDLR* conshdlr;
715
716 /* add linear constraints */
717 conshdlr = SCIPfindConshdlr(scip, "linear");
718 if( conshdlr != NULL )
719 {
720 SCIP_CALL( addLinearConstraints(scip, conshdlr, addcombconss, addcontconss, heurdata) );
721 }
722
723 /* add varbound constraints */
724 conshdlr = SCIPfindConshdlr(scip, "varbound");
725 if( conshdlr != NULL )
726 {
727 SCIP_CALL( addVarboundConstraints(scip, conshdlr, addcombconss, addcontconss, heurdata) );
728 }
729
730 if( addcombconss )
731 {
732 /* add logic-or constraints */
733 conshdlr = SCIPfindConshdlr(scip, "logicor");
734 if( conshdlr != NULL )
735 {
736 SCIP_CALL( addLogicOrConstraints(scip, conshdlr, heurdata) );
737 }
738
739 /* add setppc constraints */
740 conshdlr = SCIPfindConshdlr(scip, "setppc");
741 if( conshdlr != NULL )
742 {
743 SCIP_CALL( addSetppcConstraints(scip, conshdlr, heurdata) );
744 }
745
746 /* add knapsack constraints */
747 conshdlr = SCIPfindConshdlr(scip, "knapsack");
748 if( conshdlr != NULL )
749 {
750 SCIP_CALL( addKnapsackConstraints(scip, conshdlr, heurdata) );
751 }
752 }
753
754 return SCIP_OKAY;
755 }
756
757
758
759 /** creates a SCIP_SOL in our SCIP space out of the SCIP_SOL from a sub-SCIP */
760 static
createSolFromSubScipSol(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL ** sol,SCIP_SOL * subsol)761 SCIP_RETCODE createSolFromSubScipSol(
762 SCIP* scip, /**< SCIP data structure */
763 SCIP_HEUR* heur, /**< heuristic data structure */
764 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, a new solution
765 * is created, otherwise values in the given one are overwritten */
766 SCIP_SOL* subsol /**< solution of sub-SCIP */
767 )
768 {
769 SCIP_HEURDATA* heurdata;
770 SCIP_VAR** vars;
771 SCIP_VAR** subvars;
772 SCIP_VAR* var;
773 SCIP_VAR* subvar;
774 SCIP_Real scalar;
775 SCIP_Real constant;
776 SCIP_Real val;
777 int i;
778 int nvars;
779
780 heurdata = SCIPheurGetData(heur);
781 assert( heurdata != NULL );
782 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nvars, NULL, NULL, NULL, NULL) );
783
784 if( *sol == NULL )
785 {
786 SCIP_CALL( SCIPcreateOrigSol(scip, sol, heur) );
787 }
788
789 vars = SCIPgetOrigVars(scip);
790 nvars = SCIPgetNOrigVars(scip);
791
792 for( i = 0; i < nvars; ++i )
793 {
794 var = vars[i];
795
796 constant = 0;
797 scalar = 1.0;
798 var = SCIPvarGetTransVar(var);
799 val = 0;
800
801 if( REALABS(scalar) > 0 )
802 {
803 SCIP_Real transval = 0.0;
804
805 subvar = (SCIP_VAR*) SCIPhashmapGetImage(heurdata->varsciptosubscip, (void*)var);
806 if( subvar == NULL )
807 {
808 SCIPdebugMsg(scip, "return14 : abort building solution since a variable was not in our list\n");
809
810 SCIP_CALL( SCIPfreeSol(scip, sol) );
811 return SCIP_OKAY;
812 }
813
814 if( SCIPvarIsBinary(subvar) )
815 transval = SCIPvarGetLbGlobal(subvar);
816 else
817 {
818 SCIP_Real tconstant = 0.0;
819 SCIP_Real tscalar = 1.0;
820 SCIP_CALL( SCIPgetProbvarSum(heurdata->subscip, &subvar, &tscalar, &tconstant) );
821
822 transval = 0.0;
823
824 if( REALABS(tscalar) > 0.0 )
825 {
826 assert(subvar != NULL);
827 transval = SCIPgetSolVal(heurdata->subscip, subsol, subvar);
828 }
829
830 /* recompute aggregations */
831 transval = tscalar * transval + tconstant;
832 }
833 val = scalar * transval + constant;
834 }
835 else
836 {
837 /* recompute aggregations */
838 val = scalar * val + constant;
839 }
840
841 assert( val != SCIP_INVALID ); /*lint !e777*/
842 SCIP_CALL( SCIPsetSolVal(scip, *sol, vars[i], val) );
843 }
844
845 return SCIP_OKAY;
846 }
847
848
849
850 /** creates copy of CIP from problem in SCIP */
851 static
createSubSCIP(SCIP * scip,SCIP_HEURDATA * heurdata)852 SCIP_RETCODE createSubSCIP(
853 SCIP* scip, /**< SCIP data structure */
854 SCIP_HEURDATA* heurdata /**< heuristic data structure */
855 )
856 {
857 SCIP_HASHMAP* varsmap;
858 SCIP_HASHMAP* conssmap;
859 SCIP_CONSHDLR* conshdlrindicator;
860 SCIP_CONSHDLR* conshdlrindi;
861 SCIP_CONSHDLR* conshdlrlin;
862 SCIP_CONSHDLR* conshdlrabspow;
863 SCIP_CONSHDLR* conshdlrquad;
864 SCIP_CONSHDLR* conshdlrnonlin;
865 SCIP_CONSHDLR* conshdlrvarbound;
866 SCIP_CONSHDLR* conshdlrknapsack;
867 SCIP_CONSHDLR* conshdlrlogicor;
868 SCIP_CONSHDLR* conshdlrsetppc;
869 SCIP_CONSHDLR* currentconshdlr;
870 SCIP_CONSHDLR* conshdlrsignpower;
871 SCIP_CONS** conss;
872 SCIP_CONS* subcons;
873 SCIP_CONS* transcons;
874 SCIP_CONS* linindicons;
875 SCIP_CONS* indicons;
876 SCIP_CONS* cons = NULL;
877 SCIP_VAR** vars;
878 SCIP_VAR** subvars;
879 SCIP_VAR* var;
880 SCIP_VAR* tmpvar;
881 SCIP_VAR* subvar;
882 SCIP_VAR* slackvarpos;
883 SCIP_VAR* slackvarneg;
884 SCIP_VAR* indislackvarpos;
885 SCIP_VAR* indislackvarneg;
886 SCIP_VAR* indicatorcopy;
887 char probname[SCIP_MAXSTRLEN];
888 char varname[SCIP_MAXSTRLEN];
889 char consname[SCIP_MAXSTRLEN];
890 SCIP_Real varobjective;
891 int nconss;
892 int nconsindicator;
893 int i;
894 int j;
895 int k;
896 int nvars;
897 int ncontvars;
898 SCIP_Bool feasible;
899 SCIP_Bool success;
900
901 assert( heurdata != NULL );
902 assert( heurdata->subscip == NULL );
903
904 heurdata->usedcalls = 0;
905 heurdata->solfound = FALSE;
906 heurdata->nonimprovingRounds = 0;
907
908 /* we can't change the vartype in some constraints, so we have to check that only the right constraints are present*/
909 conshdlrindi = SCIPfindConshdlr(scip, "indicator");
910 conshdlrlin = SCIPfindConshdlr(scip, "linear");
911 conshdlrabspow = SCIPfindConshdlr(scip, "abspower");
912 conshdlrquad = SCIPfindConshdlr(scip, "quadratic");
913 conshdlrnonlin = SCIPfindConshdlr(scip, "nonlinear");
914 conshdlrvarbound = SCIPfindConshdlr(scip, "varbound");
915 conshdlrknapsack = SCIPfindConshdlr(scip, "knapsack");
916 conshdlrlogicor = SCIPfindConshdlr(scip, "logicor");
917 conshdlrsetppc = SCIPfindConshdlr(scip, "setppc");
918 conshdlrsignpower = SCIPfindConshdlr(scip, "signpower");
919
920 nconss = SCIPgetNOrigConss(scip);
921 conss = SCIPgetOrigConss(scip);
922
923 /* for each constraint ask if it has an allowed type */
924 for (i = 0; i < nconss; i++ )
925 {
926 cons = conss[i];
927 currentconshdlr = SCIPconsGetHdlr(cons);
928
929 if( currentconshdlr == conshdlrindi ||
930 currentconshdlr == conshdlrabspow ||
931 currentconshdlr == conshdlrquad ||
932 currentconshdlr == conshdlrnonlin ||
933 currentconshdlr == conshdlrvarbound ||
934 currentconshdlr == conshdlrknapsack ||
935 currentconshdlr == conshdlrlogicor ||
936 currentconshdlr == conshdlrsetppc ||
937 currentconshdlr == conshdlrlin ||
938 currentconshdlr == conshdlrsignpower)
939 {
940 continue;
941 }
942 else
943 {
944 return SCIP_OKAY;
945 }
946 }
947
948 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
949
950 if( heurdata->dynamicdepth == 1 )
951 {
952 heurdata->maxcalls = (int)SCIPfloor(scip, sqrt((double)(nvars - ncontvars)));
953 }
954
955 heurdata->triedsetupsubscip = TRUE;
956
957 /* initializing the subproblem */
958 SCIP_CALL( SCIPcreate(&heurdata->subscip) );
959
960 /* create variable hash mapping scip -> subscip */
961 SCIP_CALL( SCIPhashmapCreate(&varsmap, SCIPblkmem(scip), nvars) );
962
963 SCIP_CALL( SCIPhashmapCreate(&heurdata->switchedvars, SCIPblkmem(scip), heurdata->maxcalls) );
964 SCIP_CALL( SCIPhashmapCreate(&heurdata->switchedvars2, SCIPblkmem(scip), heurdata->maxcalls) );
965
966 /* create sub-SCIP copy of CIP, copy interesting plugins */
967 success = TRUE;
968 SCIP_CALL( SCIPcopyPlugins(scip, heurdata->subscip, TRUE, FALSE, TRUE, FALSE, TRUE,
969 FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, &success) );
970
971 if( success == FALSE )
972 {
973 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some plugins to sub-SCIP, continue anyway\n");
974 }
975
976 /* copy parameter settings */
977 SCIP_CALL( SCIPcopyParamSettings(scip, heurdata->subscip) );
978
979 /* create problem in sub-SCIP */
980
981 /* get name of the original problem and add "dualval" */
982 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_dualval", SCIPgetProbName(scip));
983 SCIP_CALL( SCIPcreateProb(heurdata->subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
984
985 SCIP_CALL( SCIPincludeEventHdlrLPsol(heurdata->subscip, heurdata) );
986
987 /* copy all variables */
988 SCIP_CALL( SCIPcopyVars(scip, heurdata->subscip, varsmap, NULL, NULL, NULL, 0, TRUE) );
989
990 /* copy as many constraints as possible */
991 SCIP_CALL( SCIPhashmapCreate(&conssmap, SCIPblkmem(scip), SCIPgetNConss(scip)) );
992 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) );
993
994 SCIP_CALL( SCIPhashmapCreate(&heurdata->origsubscipConsMap, SCIPblkmem(scip), SCIPgetNConss(scip)) );
995
996 nconss = SCIPgetNOrigConss(scip);
997 conss = SCIPgetOrigConss(scip);
998
999 /* fill constraint mapping from original scip to the subscip */
1000 for( i = 0; i < nconss; ++i )
1001 {
1002 transcons = NULL;
1003 SCIP_CALL( SCIPgetTransformedCons(scip, conss[i], &transcons) );
1004
1005 subcons = (SCIP_CONS*)SCIPhashmapGetImage(conssmap, transcons);
1006 assert( subcons != NULL );
1007
1008 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, subcons) );
1009 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, transcons, subcons) );
1010 }
1011
1012 SCIP_CALL( SCIPhashmapCreate(&heurdata->conss2nlrow, SCIPblkmem(scip), SCIPgetNConss(scip)) );
1013
1014 if( !heurdata->subscipisvalid )
1015 {
1016 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some constraints to sub-SCIP, continue anyway\n");
1017 }
1018
1019 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) );
1020 heurdata->nvars = nvars;
1021
1022 /* create hashmaps from scip transformed vars to subscip original vars, and vice versa
1023 * capture variables in SCIP and sub-SCIP
1024 * catch global bound change events */
1025 SCIP_CALL( SCIPhashmapCreate(&heurdata->varsubsciptoscip, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1026 SCIP_CALL( SCIPhashmapCreate(&heurdata->varsciptosubscip, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1027
1028 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip,
1029 * therefore we iterate over the hashmap */
1030 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i )
1031 {
1032 SCIP_HASHMAPENTRY* entry;
1033 entry = SCIPhashmapGetEntry(varsmap, i);
1034 if( entry != NULL )
1035 {
1036 var = (SCIP_VAR*) SCIPhashmapEntryGetOrigin(entry);
1037 subvar = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
1038
1039 assert( SCIPvarGetProbindex(subvar) >= 0 );
1040 assert( SCIPvarGetProbindex(subvar) <= heurdata->nsubvars );
1041
1042 if( SCIPvarIsActive(var) )
1043 {
1044 assert( SCIPvarGetProbindex(var) <= heurdata->nvars );
1045 /* assert that we have no mapping for this var yet */
1046 assert( SCIPhashmapGetImage(heurdata->varsciptosubscip,var) == NULL );
1047 SCIP_CALL( SCIPhashmapInsert(heurdata->varsciptosubscip, var, subvar) );
1048 }
1049
1050 assert( SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar) == NULL );
1051 SCIP_CALL( SCIPhashmapInsert(heurdata->varsubsciptoscip, subvar, var) );
1052
1053 SCIP_CALL( SCIPcaptureVar(scip, var) );
1054 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, subvar) );
1055
1056 assert( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetLbGlobal(subvar)) );
1057 assert( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetUbGlobal(subvar)) );
1058 }
1059 }
1060
1061 /* we map all slack variables of indicator constraints to their indicator variables */
1062 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1063 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator);
1064
1065 SCIP_CALL( SCIPhashmapCreate(&heurdata->slacktoindivarsmap, SCIPblkmem(scip), nconsindicator) );
1066 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicators, SCIPblkmem(scip), nconsindicator) );
1067 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicopymap, SCIPblkmem(scip), nconsindicator) );
1068 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicopymapback, SCIPblkmem(scip), nconsindicator) );
1069 SCIP_CALL( SCIPhashmapCreate(&heurdata->slackvarlbMap, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1070 SCIP_CALL( SCIPhashmapCreate(&heurdata->slackvarubMap, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1071
1072 for( i = 0; i < nconsindicator; i++ )
1073 {
1074 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1075 SCIP_CONS* currcons;
1076
1077 currcons = indicatorconss[i];
1078 assert(currcons != NULL);
1079
1080 SCIP_CALL( SCIPhashmapInsert(heurdata->slacktoindivarsmap, SCIPgetSlackVarIndicator(currcons),
1081 SCIPgetBinaryVarIndicator(currcons)) );
1082 SCIP_CALL( SCIPhashmapInsert(heurdata->indicators, SCIPgetBinaryVarIndicator(currcons), currcons) );
1083 SCIP_CALL( SCIPcaptureCons(scip, currcons) );
1084 SCIP_CALL( SCIPcaptureVar(scip, SCIPgetBinaryVarIndicator(currcons)) );
1085 }
1086
1087 /* we introduce slackvariables s+ and s- for each constraint to ensure that the problem is feasible
1088 * we want to minimize over the sum of these variables, so set the objective to 1 */
1089 SCIP_CALL( SCIPhashmapCreate(&heurdata->relaxcons, SCIPblkmem(scip), nvars) );
1090 SCIP_CALL( SCIPhashmapCreate(&heurdata->relaxconsindi, SCIPblkmem(scip), nvars) );
1091 SCIP_CALL( SCIPhashmapCreate(&heurdata->slack2var, SCIPblkmem(scip), nvars) );
1092
1093 vars = SCIPgetOrigVars(scip);
1094 nvars = SCIPgetNOrigVars(scip);
1095
1096 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->integervars), nvars) );
1097 BMSclearMemoryArray(heurdata->integervars, nvars);
1098 heurdata->integervarssize = nvars;
1099 j = 0;
1100
1101 /* here we relax the variables (or indicator constraints, since indicator variables cannot be relaxed) */
1102 for( i = 0; i < nvars; ++i )
1103 {
1104 var = SCIPvarGetTransVar(vars[i]);
1105 assert( var != NULL );
1106
1107 if( ! SCIPvarIsActive(var) )
1108 continue;
1109
1110 if( ! SCIPvarIsIntegral(var) )
1111 continue;
1112
1113 heurdata->integervars[j++] = vars[i];
1114
1115 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1116 if( var == NULL )
1117 continue;
1118
1119 /* in this case our variable is an indicator variable */
1120 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) != NULL )
1121 {
1122 /* we have to find all the indicator constraints of this variable */
1123 for( k = 0; k < nconsindicator; k++ )
1124 {
1125 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1126 SCIP_CONS* currcons;
1127 SCIP_VAR* negatedvar;
1128 SCIP_VAR* indicatorbinvar;
1129
1130 currcons = indicatorconss[k];
1131 assert(currcons != NULL);
1132
1133 indicatorbinvar = SCIPgetBinaryVarIndicator(currcons);
1134 assert(indicatorbinvar != NULL);
1135
1136 SCIP_CALL( SCIPgetNegatedVar(scip, (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var), &negatedvar) );
1137
1138 if( indicatorbinvar == SCIPhashmapGetImage(heurdata->varsubsciptoscip, var) || indicatorbinvar == negatedvar )
1139 {
1140 /* case that we have a negated variable */
1141 if( SCIPvarIsNegated(indicatorbinvar) )
1142 {
1143 assert(indicatorbinvar == negatedvar);
1144 varobjective = SCIPvarGetObj(negatedvar);
1145 }
1146 else
1147 {
1148 assert(indicatorbinvar != negatedvar);
1149 varobjective = SCIPvarGetObj(indicatorbinvar);
1150 }
1151
1152 varobjective = heurdata->lambdaobj * REALABS(varobjective);
1153
1154 indicons = currcons;
1155 assert( indicons != NULL );
1156
1157 indicons = (SCIP_CONS*)SCIPhashmapGetImage(conssmap, indicons);
1158
1159 assert( indicons != NULL );
1160 linindicons = SCIPgetLinearConsIndicator(indicons);
1161
1162 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos3", SCIPconsGetName(linindicons));
1163 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1164 heurdata->lambdaslack *100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1165 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) );
1166
1167 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg3", SCIPconsGetName(linindicons));
1168 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1169 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1170 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) );
1171
1172 /* make a copy of the indicator to relax it if this parameter is set true */
1173 if( heurdata->relaxindicators )
1174 {
1175 SCIP_CONS* imagecons;
1176
1177 indicatorbinvar = SCIPgetBinaryVarIndicator(indicons);
1178
1179 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorbinvar, &negatedvar) );
1180
1181 if( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) == NULL &&
1182 SCIPhashmapGetImage(heurdata->indicopymap, negatedvar) == NULL)
1183 {
1184 SCIP_Bool negated = FALSE;
1185
1186 if (SCIPvarIsNegated(indicatorbinvar))
1187 {
1188 indicatorbinvar = negatedvar;
1189 negated = TRUE;
1190 }
1191
1192 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "indicopy_%s", SCIPvarGetName(indicatorbinvar));
1193 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indicatorcopy, varname, SCIPvarGetLbGlobal(indicatorbinvar), SCIPvarGetUbGlobal(indicatorbinvar),
1194 SCIPvarGetObj(indicatorbinvar), SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1195
1196 SCIP_CALL( SCIPaddVar(heurdata->subscip, indicatorcopy) );
1197
1198 SCIP_CALL( SCIPhashmapInsert(heurdata->indicopymap, indicatorbinvar, indicatorcopy) );
1199 SCIP_CALL( SCIPhashmapInsert(heurdata->indicopymapback, indicatorcopy, indicatorbinvar) );
1200 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, indicatorbinvar) );
1201
1202 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos1", SCIPvarGetName(indicatorbinvar));
1203 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indislackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1204 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1205 SCIP_CALL( SCIPaddVar(heurdata->subscip, indislackvarpos) );
1206
1207 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg1", SCIPvarGetName(indicatorbinvar));
1208 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indislackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1209 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1210 SCIP_CALL( SCIPaddVar(heurdata->subscip, indislackvarneg) );
1211
1212 /* create linking constraint */
1213 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "linking_%s", SCIPvarGetName(indicatorbinvar));
1214 cons = NULL;
1215 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1216 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1217 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorbinvar, 1.0) );
1218 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorcopy, -1.0) );
1219 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarpos, 1.0) );
1220 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarneg, -1.0) );
1221
1222 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorbinvar, cons) );
1223 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorcopy, cons) );
1224
1225 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1226 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, cons) );
1227
1228 assert( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) != NULL );
1229
1230 if ( negated )
1231 {
1232 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorcopy, &indicatorcopy) );
1233 }
1234
1235 SCIP_CALL( SCIPchgVarType(heurdata->subscip, indicatorbinvar, SCIP_VARTYPE_CONTINUOUS, &feasible) );
1236
1237 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, indislackvarpos, var) );
1238 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, indislackvarneg, var) );
1239 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1240 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1241 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &indislackvarpos) );
1242 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &indislackvarneg) );
1243 }
1244 else
1245 {
1246 if (!SCIPvarIsNegated(indicatorbinvar))
1247 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar);
1248 else
1249 {
1250 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, negatedvar);
1251 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorcopy, &indicatorcopy) );
1252 }
1253 }
1254
1255 cons = NULL;
1256 SCIP_CALL( SCIPcreateConsIndicatorLinCons(heurdata->subscip, &cons, SCIPconsGetName(indicons), indicatorcopy,
1257 SCIPgetLinearConsIndicator(indicons), SCIPgetSlackVarIndicator(indicons), SCIPconsIsInitial(indicons),
1258 SCIPconsIsSeparated(indicons), SCIPconsIsEnforced(indicons), SCIPconsIsChecked(indicons),
1259 SCIPconsIsPropagated(indicons), SCIPconsIsLocal(indicons), SCIPconsIsDynamic(indicons),
1260 SCIPconsIsRemovable(indicons), SCIPconsIsStickingAtNode(indicons)) );
1261 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1262
1263 /* delete old indicator constraints so we can relax the indicator variables */
1264 imagecons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(currcons));
1265 assert(imagecons != NULL);
1266 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &imagecons) );
1267 SCIP_CALL( SCIPhashmapRemove(heurdata->origsubscipConsMap, currcons) );
1268 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, currcons, cons) );
1269 SCIPconsAddUpgradeLocks(SCIPgetLinearConsIndicator(indicons), -1);
1270 SCIP_CALL( SCIPdelCons(heurdata->subscip, indicons) );
1271 }
1272
1273 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) );
1274 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) );
1275 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1276 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1277
1278 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, linindicons, slackvarpos, 1.0) );
1279 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, linindicons, slackvarneg, -1.0) );
1280 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarpos) );
1281 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarneg) );
1282 }
1283 }
1284 continue;
1285 }
1286
1287 if( heurdata->relaxindicators )
1288 {
1289 /* relax the old indicator variables*/
1290 for( k = 0; k < nvars; k++ )
1291 {
1292 if( SCIPhashmapGetImage(heurdata->indicators, vars[k]) == NULL )
1293 continue;
1294
1295 tmpvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, vars[k]);
1296 SCIP_CALL( SCIPchgVarType(heurdata->subscip, tmpvar, SCIP_VARTYPE_CONTINUOUS, &feasible) );
1297 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, tmpvar, -SCIPinfinity(heurdata->subscip)) );
1298 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, tmpvar, SCIPinfinity(heurdata->subscip)) );
1299 }
1300
1301 /* we map all slack variables of indicator constraints to their indicator variables */
1302 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1303 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator);
1304
1305 /* delete old hashmaps and fill with the new indicators*/
1306 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
1307 SCIP_CALL( releaseHashmapEntries(scip, heurdata->indicators, FALSE) );
1308 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->slacktoindivarsmap) );
1309 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->indicators) );
1310
1311 /* fill hashmaps with new values */
1312 for( k = 0; k < nconsindicator; k++ )
1313 {
1314 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1315 SCIP_CONS* currcons;
1316
1317 currcons = indicatorconss[k];
1318 assert(currcons != NULL);
1319
1320 SCIP_CALL( SCIPcaptureVar(scip, SCIPgetBinaryVarIndicator(currcons)) );
1321 SCIP_CALL( SCIPcaptureCons(scip, currcons) );
1322
1323 SCIP_CALL( SCIPhashmapInsert(heurdata->slacktoindivarsmap, SCIPgetSlackVarIndicator(currcons),
1324 SCIPgetBinaryVarIndicator(currcons)) );
1325 SCIP_CALL( SCIPhashmapInsert(heurdata->indicators, SCIPgetBinaryVarIndicator(currcons), currcons) );
1326 }
1327 }
1328
1329 /* in this case, we have a normal variable */
1330 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_%s", SCIPvarGetName(var));
1331 cons = NULL;
1332 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1333 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1334
1335 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos0", SCIPvarGetName(var));
1336 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1337 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1338 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) );
1339
1340 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg0", SCIPvarGetName(var));
1341 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1342 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1343 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) );
1344
1345 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1346 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, 1.0) );
1347 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, -1.0) );
1348
1349 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1350
1351 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) );
1352 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) );
1353 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1354 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1355 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxcons, var, cons) );
1356 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarpos) );
1357 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarneg) );
1358
1359 /* if the var is no indicator, relax it to a continuous variable */
1360 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) == NULL )
1361 {
1362 SCIP_CALL( SCIPchgVarType(heurdata->subscip, var, SCIP_VARTYPE_CONTINUOUS, &feasible) );
1363 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, var, -SCIPinfinity(heurdata->subscip)) );
1364 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, var, SCIPinfinity(heurdata->subscip)) );
1365 }
1366 }
1367
1368 /* set up relaxation constraints for continuous variables */
1369 if( heurdata->relaxcontvars )
1370 {
1371 for( i = 0; i < nvars; ++i )
1372 {
1373 var = SCIPvarGetTransVar(vars[i]);
1374 assert( var != NULL );
1375
1376 if( ! SCIPvarIsActive(var) )
1377 continue;
1378
1379 if( SCIPvarIsIntegral(var) )
1380 continue;
1381
1382 if( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var)) )
1383 continue;
1384
1385 if( (SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPinfinity(scip))) && (SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), -SCIPinfinity(scip))) )
1386 continue;
1387
1388 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1389 if( var == NULL )
1390 continue;
1391
1392 /* in this case, we have a normal variable */
1393 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_ub_%s", SCIPvarGetName(var));
1394 cons = NULL;
1395 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(heurdata->subscip), SCIPvarGetUbGlobal(var),
1396 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1397
1398 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos2", SCIPvarGetName(var));
1399 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1400 heurdata->lambdaslack, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1401 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) );
1402
1403 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1404 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, -1.0) );
1405
1406 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1407 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1408 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarubMap, var, slackvarpos) );
1409 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) );
1410 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1411
1412 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_lb_%s", SCIPvarGetName(var));
1413 cons = NULL;
1414 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, SCIPvarGetLbGlobal(var), SCIPinfinity(heurdata->subscip),
1415 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1416
1417 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg2", SCIPvarGetName(var));
1418 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1419 heurdata->lambdaslack, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1420 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) );
1421
1422 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1423 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, 1.0) );
1424
1425 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1426 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1427 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarlbMap, var, slackvarneg) );
1428 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) );
1429 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1430
1431 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, var, -SCIPinfinity(heurdata->subscip)) );
1432 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, var, SCIPinfinity(heurdata->subscip)) );
1433 }
1434 }
1435
1436 /* if we have a solution add constraint that the next solution must not be worse than the current one */
1437 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "objbound");
1438 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip),
1439 SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1440 heurdata->objbound = cons;
1441
1442 for( i = 0; i < nvars; ++i )
1443 {
1444 var = SCIPvarGetTransVar(vars[i]);
1445 assert( var != NULL );
1446
1447 if( !SCIPvarIsActive(var) )
1448 continue;
1449
1450 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1451 if( subvar == NULL )
1452 continue;
1453
1454 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, subvar, SCIPvarGetObj(var)) );
1455
1456 SCIP_CALL( SCIPchgVarObj(heurdata->subscip, subvar, heurdata->lambdaobj * SCIPvarGetObj(subvar) ) );
1457 }
1458
1459 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1460 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1461
1462 /* do not need varsmap and conssmap anymore */
1463 SCIPhashmapFree(&conssmap);
1464 SCIPhashmapFree(&varsmap);
1465
1466 /* enable SCIP output if needed */
1467 if( heurdata->heurverblevel > 3 )
1468 {
1469 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 4) );
1470 }
1471 else
1472 {
1473 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) );
1474 }
1475
1476 heurdata->nintegervars = j;
1477
1478 return SCIP_OKAY;
1479 }
1480
1481
1482 /** free sub-SCIP data structure */
1483 static
freeSubSCIP(SCIP * scip,SCIP_HEURDATA * heurdata)1484 SCIP_RETCODE freeSubSCIP(
1485 SCIP* scip, /**< SCIP data structure */
1486 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1487 )
1488 {
1489 assert(scip != NULL);
1490 assert(heurdata != NULL);
1491 assert(heurdata->subscip != NULL);
1492
1493 heurdata->nsubvars = 0;
1494 heurdata->nvars = 0;
1495
1496 /* free sub-SCIP */
1497 SCIP_CALL( SCIPfree(&heurdata->subscip) );
1498
1499 return SCIP_OKAY;
1500 }
1501
1502
1503 /** create a solution from the values of current nonlinear program */
1504 static
createSolFromNLP(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL ** sol)1505 SCIP_RETCODE createSolFromNLP(
1506 SCIP* scip, /**< SCIP data structure */
1507 SCIP_HEUR* heur, /**< heuristic data structure */
1508 SCIP_SOL** sol /**< buffer to store solution value; if pointing to NULL a new solution is
1509 * created, otherwise values in the given one are overwritten */
1510 )
1511 {
1512 SCIP_HEURDATA* heurdata;
1513 SCIP_VAR** subvars;
1514 SCIP_VAR* subvar;
1515 int i;
1516 int nsubvars;
1517
1518 assert(scip != NULL);
1519 assert(heur != NULL);
1520 assert(sol != NULL);
1521
1522 heurdata = SCIPheurGetData(heur);
1523 assert(heurdata != NULL);
1524
1525 if( *sol == NULL )
1526 {
1527 SCIP_CALL( SCIPcreateSol(scip, sol, heur) );
1528 }
1529
1530 /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
1531 * since constraint copying may have required the copy of variables that are fixed in the main SCIP */
1532 assert(heurdata->nsubvars <= SCIPgetNOrigVars(heurdata->subscip));
1533
1534 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) );
1535
1536 /* set solution values */
1537 for( i = 0; i < nsubvars; ++i )
1538 {
1539 subvar = subvars[i];
1540 assert(subvar != NULL);
1541
1542 subvar = SCIPvarGetTransVar(subvar);
1543
1544 if( !SCIPvarIsActive(subvar) )
1545 continue;
1546
1547 assert(SCIPvarGetNLPSol(subvar) != SCIP_INVALID);/*lint !e777*/
1548 SCIP_CALL( SCIPsetSolVal(scip, *sol, subvar, SCIPvarGetNLPSol(subvar)) );
1549 }
1550
1551 return SCIP_OKAY;
1552 }
1553
1554 #define BIG_VALUE 1E+10
1555
1556 /** method to fix the (relaxed) discrete variables */
1557 static
fixDiscreteVars(SCIP * scip,SCIP_HEURDATA * heurdata,SCIP_SOL * refpoint,SCIP_SOL ** transsol)1558 SCIP_RETCODE fixDiscreteVars(
1559 SCIP* scip, /**< SCIP data structure */
1560 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1561 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from;
1562 * if NULL, then LP solution is used */
1563 SCIP_SOL** transsol /**< pointer to new created solution with fixed values as solution value */
1564 )
1565 {
1566 SCIP_Real fixval;
1567 SCIP_VAR* var;
1568 SCIP_VAR* subvar;
1569 SCIP_CONS* rcons;
1570 int i;
1571
1572 SCIP_CALL( SCIPcreateOrigSol(scip, transsol, NULL) );
1573
1574 /* fix discrete variables */
1575 for( i = 0; i < heurdata->nintegervars; i++ )
1576 {
1577 var = heurdata->integervars[i];
1578 assert(var != NULL);
1579
1580 var = SCIPvarGetTransVar(var);
1581 assert(var != NULL);
1582 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1583
1584 if( subvar == NULL )
1585 continue;
1586
1587 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
1588 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, subvar);
1589
1590 /* if we do not really have a startpoint, we set to 0.0 here and project on bounds below */
1591 if( refpoint == NULL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1592 fixval = 0.0;
1593 else
1594 {
1595 /* get value of the variables (NULL as refpoint gives the current LP solution, otherwise the start point) */
1596 fixval = SCIPgetSolVal(scip, refpoint, heurdata->integervars[i]);
1597
1598 /* take care that we do not fix variables to very large values (project on bounds below) */
1599 if( REALABS(fixval) > BIG_VALUE )
1600 fixval = 0.0;
1601 else
1602 {
1603 /* round fractional variables to the nearest integer, use exact integral value, if the variable is only
1604 * integral within numerical tolerances */
1605 fixval = SCIPfloor(scip, fixval + 0.5);
1606 }
1607 }
1608
1609 /* adjust value to the global bounds of the corresponding SCIP variable */
1610 fixval = MAX(fixval, SCIPvarGetLbGlobal(heurdata->integervars[i])); /*lint !e666*/
1611 fixval = MIN(fixval, SCIPvarGetUbGlobal(heurdata->integervars[i])); /*lint !e666*/
1612
1613 SCIP_CALL( SCIPsetSolVal(scip, *transsol, heurdata->integervars[i], fixval) );
1614
1615 /* adjust the relaxation constraints to the new fixval */
1616 rcons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->relaxcons, subvar);
1617
1618 fixval = MAX(fixval, SCIPvarGetLbGlobal(subvar));/*lint !e666*/
1619 fixval = MIN(fixval, SCIPvarGetUbGlobal(subvar));/*lint !e666*/
1620 if( rcons == NULL )
1621 {
1622 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, fixval) );
1623 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, fixval) );
1624 continue;
1625 }
1626
1627 SCIP_CALL( SCIPchgLhsLinear(heurdata->subscip, rcons, fixval) );
1628 SCIP_CALL( SCIPchgRhsLinear(heurdata->subscip, rcons, fixval) );
1629 }
1630
1631 return SCIP_OKAY;
1632 }
1633
1634 /** method to free memory before leaving the heuristic or jumping up in the recursion */
1635 static
freeMemory(SCIP * scip,SCIP_HEURDATA * heurdata,SCIP_SOL * transsol,SCIP_Real * absranks,SCIP_Real * ranks,SCIP_VAR ** sortedvars,SCIP_Bool beforeswitching,SCIP_Bool clearswitchedvars)1636 SCIP_RETCODE freeMemory(
1637 SCIP* scip, /**< scip data structure */
1638 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1639 SCIP_SOL* transsol, /**< sol that has to be freed */
1640 SCIP_Real* absranks, /**< array of absolute rank values */
1641 SCIP_Real* ranks, /**< array of rank values */
1642 SCIP_VAR** sortedvars, /**< array of corresponding variables */
1643 SCIP_Bool beforeswitching, /**< did we call this method before or after switching variables? */
1644 SCIP_Bool clearswitchedvars /**< says if we should clear switchedvars or not */
1645 )
1646 {
1647 SCIP_VAR** subvars;
1648 SCIP_VAR* subvar;
1649 SCIP_VAR* var;
1650 SCIP_Real* val;
1651 int nsubvars;
1652 int nsubbinvars;
1653 int nsubintvars;
1654 int i;
1655
1656 if( clearswitchedvars )
1657 {
1658 /* free memory of the solution values in the hashmaps */
1659 for( i = 0; i < heurdata->nintegervars; i++ )
1660 {
1661 var = heurdata->integervars[i];
1662
1663 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var) != NULL )
1664 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var);
1665
1666 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, var);
1667 if( val != NULL )
1668 {
1669 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1670 }
1671
1672 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, var);
1673 if( val != NULL )
1674 {
1675 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1676 }
1677 }
1678
1679 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars) );
1680 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars2) );
1681 }
1682
1683 SCIPfreeBufferArrayNull( scip, &ranks );
1684 SCIPfreeBufferArrayNull( scip, &absranks );
1685 SCIPfreeBufferArrayNull( scip, &sortedvars );
1686
1687 if( transsol != NULL )
1688 {
1689 SCIP_CALL( SCIPfreeSol(scip, &transsol) );
1690 }
1691
1692 if( beforeswitching )
1693 {
1694 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
1695 }
1696
1697 /* undo fixing of discrete variables in sub-SCIP */
1698 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1699
1700 /* set bounds of discrete variables to original values */
1701 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1702 {
1703 subvar = subvars[i];
1704 assert(SCIPvarGetProbindex(subvar) == i);
1705
1706 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
1707
1708 if (SCIPhashmapGetImage(heurdata->indicopymapback, subvar) != NULL)
1709 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, SCIPhashmapGetImage(heurdata->indicopymapback, subvar));
1710
1711 assert(var != NULL);
1712
1713 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(var)) );
1714 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(var)) );
1715 }
1716
1717 return SCIP_OKAY;
1718 }
1719
1720 /** computes the ranks, saves them into an array and sorts the variables according to absolute ranks */
1721 static
computeRanks(SCIP * scip,SCIP_HEURDATA * heurdata,SCIP_Real * absranks,SCIP_Real * ranks,SCIP_VAR ** sortedvars)1722 SCIP_RETCODE computeRanks(
1723 SCIP* scip, /**< scip data structure */
1724 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1725 SCIP_Real* absranks, /**< array of absolute rank values */
1726 SCIP_Real* ranks, /**< array of rank values */
1727 SCIP_VAR** sortedvars /**< array of corresponding variables */
1728 )
1729 {
1730 SCIP_CONSHDLR* conshdlrindicator;
1731 SCIP_CONS* relaxcons;
1732 SCIP_CONS* indicons;
1733 SCIP_CONS* subcons;
1734 SCIP_CONS* transcons;
1735 SCIP_VAR* var;
1736 SCIP_Real* dualvalue;
1737 int nconsindicator;
1738 int j;
1739 int k;
1740
1741 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1742 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator);
1743
1744 /* Now we compute the rank of each variable */
1745 for( j = 0; j < heurdata->nintegervars; j++ )
1746 {
1747 sortedvars[j] = heurdata->integervars[j];
1748 ranks[j] = 0;
1749 absranks[j] = 0;
1750
1751 if( sortedvars[j] == NULL )
1752 break;
1753
1754 var = SCIPvarGetTransVar(sortedvars[j]);
1755 assert(var != NULL);
1756
1757 /* globally fixed variables get rank 0 */
1758 if (SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)))
1759 {
1760 ranks[j] = 0;
1761 continue;
1762 }
1763 else
1764 {
1765 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1766 assert(var != NULL);
1767 relaxcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxcons, (void*)(var));
1768
1769 /* get ranks */
1770 if( relaxcons != NULL )
1771 {
1772 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, relaxcons, &transcons) );
1773 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)transcons);
1774
1775 if( dualvalue == NULL )
1776 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(relaxcons));
1777
1778 if( dualvalue == NULL )
1779 continue;
1780
1781 assert(dualvalue != NULL);
1782 ranks[j] = (*dualvalue);
1783 }
1784 else /* if we have an indicator variable */
1785 {
1786 assert(ranks[j] == 0.0);
1787
1788 if (SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var)) != NULL)
1789 {
1790 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var));
1791
1792 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1793
1794 if( dualvalue == NULL )
1795 continue;
1796
1797 assert(dualvalue != NULL);
1798
1799 ranks[j] = (*dualvalue);
1800 }
1801
1802 /* compute the rank of the indicators, we take the highest dualvalue of an indicator constraint */
1803 for( k = 0; k < nconsindicator; k++ )
1804 {
1805 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1806 SCIP_CONS* currcons;
1807 SCIP_VAR* indicatorbinvar;
1808
1809 currcons = indicatorconss[k];
1810 assert(currcons != NULL);
1811
1812 indicatorbinvar = SCIPgetBinaryVarIndicator(currcons);
1813 assert(indicatorbinvar != NULL);
1814
1815 if( indicatorbinvar == (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)
1816 || (SCIPvarIsNegated(indicatorbinvar) && indicatorbinvar == SCIPvarGetNegatedVar(var)) )
1817 {
1818 indicons = currcons;
1819 assert(indicons != NULL);
1820
1821 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(indicons));
1822 assert(subcons != NULL);
1823
1824 subcons = SCIPgetLinearConsIndicator(subcons);
1825 assert(subcons != NULL);
1826
1827 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1828
1829 if( dualvalue == NULL )
1830 continue;
1831
1832 assert(dualvalue != NULL);
1833
1834 if( REALABS(ranks[j]) < REALABS(*dualvalue) )
1835 ranks[j] = (*dualvalue);
1836 }
1837 }
1838 }
1839 }
1840
1841 /* take the absolute value of each rank */
1842 absranks[j] = REALABS(ranks[j]);
1843 }
1844
1845 SCIPsortDownRealRealPtr(absranks, ranks, (void**)sortedvars, heurdata->nintegervars);
1846
1847 return SCIP_OKAY;
1848 }
1849
1850 /** compute maximal slack of a variable */
1851 static
maximalslack(SCIP * scip,SCIP_HEURDATA * heurdata)1852 SCIP_Real maximalslack(
1853 SCIP* scip, /**< scip data structure */
1854 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1855 )
1856 {
1857 SCIP_VAR* maxvar;
1858 SCIP_VAR* subvar;
1859 SCIP_SOL* bestsol;
1860 SCIP_Real maxslack;
1861 int i;
1862 int nsubvars;
1863 SCIP_Bool maxslackset;
1864
1865 /* compute maximal slack */
1866 nsubvars = SCIPgetNOrigVars(heurdata->subscip);
1867
1868 /* save information about maximal violation */
1869 maxvar = NULL;
1870 maxslack = -SCIPinfinity(heurdata->subscip);
1871 maxslackset = FALSE;
1872
1873 bestsol = SCIPgetBestSol(heurdata->subscip);
1874
1875 /* search for variable with maximal slack */
1876 for( i = 0; i < nsubvars; i++ )
1877 {
1878 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
1879 if( subvar == NULL)
1880 continue;
1881
1882 /* if variable is slack */
1883 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) != NULL )
1884 {
1885 if( heurdata->isnlp )
1886 {
1887 if( maxslack < SCIPvarGetNLPSol(subvar) )
1888 {
1889 maxslack = SCIPvarGetNLPSol(subvar);
1890 maxvar = subvar;
1891 maxslackset = TRUE;
1892 }
1893 }
1894 else
1895 {
1896 assert(bestsol != NULL);
1897 if( maxslack < SCIPgetSolVal(heurdata->subscip, bestsol, subvar) )
1898 {
1899 maxslack = SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
1900 maxvar = subvar;
1901 maxslackset = TRUE;
1902 }
1903 }
1904 }
1905 }
1906
1907 if( ! maxslackset )
1908 {
1909 maxslack = 0;
1910 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "could not find a variable with maximal slack!\n");
1911 }
1912
1913 assert(maxslack >= 0);
1914
1915 if( heurdata->heurverblevel > 0 && maxslackset )
1916 {
1917 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "maximum slack: %f %s\n", maxslack, SCIPvarGetName(maxvar));
1918 }
1919
1920 return maxslack;
1921 }
1922
1923 /** method called after a solution is found which is feasible in the original problem, stores it and cleans up */
1924 static
storeSolution(SCIP * scip,SCIP_HEUR * heur,SCIP_RESULT * result,SCIP_SOL * transsol,SCIP_SOL * bestsol)1925 SCIP_RETCODE storeSolution(
1926 SCIP* scip, /**< SCIP data structure */
1927 SCIP_HEUR* heur, /**< heuristic data */
1928 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found,
1929 * no solution found, or fixing is infeasible (cutoff) */
1930 SCIP_SOL* transsol, /**< solution to fix variables */
1931 SCIP_SOL* bestsol /**< solution we create a original scip solution from */
1932 )
1933 {
1934 SCIP_HEURDATA* heurdata;
1935 SCIP_SOL* sol = NULL;
1936 SCIP_Bool stored;
1937 SCIP_Real primalobj;
1938
1939 /* get heuristic's data */
1940 heurdata = SCIPheurGetData(heur);
1941 assert(heurdata != NULL);
1942 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, bestsol) );
1943
1944 /* if this happens, there was an ipopt error - stop the heuristic for there is no good starting point */
1945 if( heurdata->isnlp && SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE )
1946 {
1947 *result = SCIP_DIDNOTFIND;
1948 heurdata->solfound = TRUE;
1949
1950 /* here we can be sure that we are in the nlp case */
1951 assert( heurdata->isnlp );
1952 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1953
1954 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
1955
1956 /* don't use the heuristic anymore if IPOPT doesn't give proper solution
1957 * (normally then this happens in most ipopt runs that may follow) */
1958 SCIPheurSetFreq(heur, -1);
1959
1960 SCIPdebugMsg(scip, "return10 : turn off heuristic, ipopt error\n");
1961
1962 if( heurdata->heurverblevel > 1 )
1963 {
1964 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "turn off heuristic due to ipopt error");
1965 }
1966
1967 return SCIP_OKAY;
1968 }
1969
1970 primalobj = SCIPinfinity(scip);
1971
1972 /* if there is a solution, try to add solution to storage and free it */
1973 if( sol != NULL )
1974 {
1975 primalobj = SCIPsolGetOrigObj(sol);
1976
1977 if( heurdata->heurverblevel > 0 )
1978 {
1979 SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, FALSE, TRUE, &stored) );
1980 }
1981 else
1982 {
1983 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
1984 }
1985 }
1986 else
1987 stored = FALSE;
1988
1989 if( stored && heurdata->heurverblevel > 1 )
1990 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "accepted solution\n");
1991
1992 if( heurdata->isnlp )
1993 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1994
1995 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
1996
1997 if( !stored )
1998 {
1999 *result = SCIP_DIDNOTFIND;
2000 heurdata->solfound = TRUE;
2001
2002 if( heurdata->heurverblevel >= 1 )
2003 {
2004 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return9 : found solution that was not stored, objective %f\n", primalobj);/*lint !e644*/
2005 }
2006
2007 return SCIP_OKAY;
2008 }
2009
2010 heurdata->prevInfeasible = FALSE;
2011 heurdata->solfound = TRUE;
2012 *result = SCIP_FOUNDSOL;
2013
2014 if( heurdata->heurverblevel >= 1 )
2015 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return 9 : found and stored new solution, objective %lf\n", primalobj);
2016
2017 return SCIP_OKAY;
2018 }
2019
2020 /** main procedure of the dualval heuristic */
SCIPapplyHeurDualval(SCIP * scip,SCIP_HEUR * heur,SCIP_RESULT * result,SCIP_SOL * refpoint)2021 SCIP_RETCODE SCIPapplyHeurDualval(
2022 SCIP* scip, /**< original SCIP data structure */
2023 SCIP_HEUR* heur, /**< heuristic data structure */
2024 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution
2025 * found, or fixing is infeasible (cutoff) */
2026 SCIP_SOL* refpoint /**< point to take fixation of discrete variables from; if NULL, then LP
2027 * solution is used */
2028 )
2029 {
2030 SCIP_HEURDATA* heurdata;
2031 SCIP_NLROW* nlrow;
2032 SCIP_SOL* transsol;
2033 SCIP_SOL* bestsol;
2034 SCIP_CONS** subconss;
2035 SCIP_CONS* rcons;
2036 SCIP_VAR** subvars;
2037 SCIP_VAR** sortedvars;
2038 SCIP_VAR* var;
2039 SCIP_VAR* subvar;
2040 SCIP_VAR* v;
2041 SCIP_RETCODE retcode;
2042 SCIP_Real* absranks;
2043 SCIP_Real* ranks;
2044 SCIP_Real* startpoint;
2045 SCIP_Real* dualval;
2046 SCIP_Real* lastval;
2047 SCIP_Real* seclastval;
2048 SCIP_Real* newval;
2049 SCIP_Real bound;
2050 SCIP_Real maxslack;
2051 SCIP_Real objvalue;
2052 int i;
2053 int k;
2054 int nsubvars;
2055 int nsubbinvars;
2056 int nsubintvars;
2057 int nsubconss;
2058 int maxequalranks;
2059
2060 assert(scip != NULL);
2061 assert(heur != NULL);
2062
2063 /* dio not run without nlp solver */
2064 if( SCIPgetNNlpis(scip) <= 0 )
2065 return SCIP_OKAY;
2066
2067 /* get heuristic's data */
2068 heurdata = SCIPheurGetData(heur);
2069 assert(heurdata != NULL);
2070
2071 /* don't use the heuristic, if the gap is small so we don't expect to get better solutions than already found */
2072 if( SCIPgetGap(scip) * 100 < heurdata->mingap )
2073 {
2074 SCIPdebugMsg(scip, "return13 : gap is less than mingap\n");
2075 return SCIP_OKAY;
2076 }
2077
2078 /* in the mode 'onlyleaves' don't run the heuristic if we are not in a leaf of the B&B tree */
2079 if( heurdata->onlyleaves && (SCIPgetNLPBranchCands(scip) != 0 || SCIPgetNPseudoBranchCands(scip) != 0) )
2080 return SCIP_OKAY;
2081
2082 /* try to setup subscip if not tried before */
2083 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip )
2084 {
2085 SCIP_CALL( createSubSCIP(scip, heurdata) );
2086 }
2087
2088 /* quit the recursion if we have found a solution */
2089 if( heurdata->solfound )
2090 {
2091 SCIPdebugMsg(scip, "return1 : already found solution \n");
2092 return SCIP_OKAY;
2093 }
2094
2095 *result = SCIP_DIDNOTRUN;
2096
2097 /* not initialized */
2098 if( heurdata->subscip == NULL )
2099 {
2100 SCIPdebugMsg(scip, "return2 : subscip is NULL\n");
2101 return SCIP_OKAY;
2102 }
2103
2104 assert(heurdata->nsubvars > 0);
2105 assert(heurdata->varsubsciptoscip != NULL);
2106
2107 /* fix discrete variables in sub-SCIP */
2108 SCIP_CALL( fixDiscreteVars(scip, heurdata, refpoint, &transsol) );
2109 bound = SCIPgetUpperbound(scip);
2110
2111 if( heurdata->onlycheaper && !SCIPisInfinity(scip, bound) )
2112 {
2113 SCIP_CALL( SCIPchgRhsLinear( heurdata->subscip, heurdata->objbound, bound) );
2114 }
2115
2116 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", 1) );
2117 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "propagating/maxroundsroot", 0) );
2118
2119 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2120 SCIP_CALL( SCIPpresolve(heurdata->subscip) );
2121
2122 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
2123 {
2124 SCIPdebugMsg(scip, "return 4 : subscip is infeasible\n");
2125
2126 *result = SCIP_DIDNOTFIND;
2127 heurdata->prevInfeasible = TRUE;
2128 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2129
2130 return SCIP_OKAY;
2131 }
2132
2133 /* If no NLP was constructed, then there were no nonlinearities after presolve.
2134 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem.
2135 */
2136 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) );
2137 retcode = SCIPsolve(heurdata->subscip);
2138 heurdata->isnlp = TRUE;
2139
2140 bestsol = NULL;
2141
2142 /* we have no dualvalues, so give up */
2143 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_OPTIMAL)
2144 {
2145 *result = SCIP_DIDNOTFIND;
2146 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2147
2148 return SCIP_OKAY;
2149 }
2150
2151 if( ! SCIPisNLPConstructed(heurdata->subscip) && retcode == SCIP_OKAY )
2152 {
2153 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2154 SCIP_CALL( SCIPsolve(heurdata->subscip) );
2155 heurdata->isnlp = FALSE;
2156 bestsol = SCIPgetBestSol(heurdata->subscip);
2157 }
2158
2159 if( heurdata->isnlp )
2160 {
2161 /* add non-combinatorial linear constraints from subscip into subNLP */
2162 SCIP_CALL( addLinearConstraintsToNlp(heurdata->subscip, FALSE, TRUE, heurdata) );
2163
2164 SCIP_CALL( SCIPallocBufferArray(scip, &startpoint, SCIPgetNNLPVars(heurdata->subscip)) );
2165
2166 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */
2167 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i )
2168 {
2169 SCIP_Real scalar = 1.0;
2170 SCIP_Real constant = 0.0;
2171
2172 subvar = SCIPgetNLPVars(heurdata->subscip)[i];
2173
2174 /* gets corresponding original variable */
2175 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) );
2176 if( subvar == NULL )
2177 {
2178 startpoint[i] = constant;
2179 continue;
2180 }
2181
2182 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
2183 if( var == NULL || REALABS( SCIPgetSolVal(scip, refpoint, var) ) > 1.0e+12 )
2184 {
2185 SCIP_Real tmpmax;
2186 tmpmax = MAX( 0.0, SCIPvarGetLbGlobal(subvar) );/*lint !e666*/
2187 startpoint[i] = MIN( tmpmax, SCIPvarGetUbGlobal(subvar) );/*lint !e666*/
2188 }
2189 else
2190 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */
2191 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant;
2192 }
2193
2194 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, startpoint) );
2195
2196 /* don't need startpoint array anymore */
2197 SCIPfreeBufferArray( scip, &startpoint );
2198
2199 SCIP_CALL( SCIPsetNLPIntPar(heurdata->subscip, SCIP_NLPPAR_VERBLEVEL, heurdata->nlpverblevel) );
2200
2201 SCIP_CALL( SCIPsolveNLP(heurdata->subscip) );
2202 assert(SCIPisNLPConstructed(heurdata->subscip));
2203
2204 /* in this case there was an error in ipopt, we try to give another startpoint */
2205 if( SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE )
2206 {
2207 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, NULL) );
2208 SCIP_CALL( SCIPsolveNLP(heurdata->subscip) );
2209 assert(SCIPisNLPConstructed(heurdata->subscip));
2210 }
2211
2212 nsubconss = SCIPgetNOrigConss(heurdata->subscip);
2213 subconss = SCIPgetOrigConss(heurdata->subscip);
2214
2215 /* free memory of all entries and clear the hashmap before filling it */
2216 for( i = 0; i < nsubconss; i++ )
2217 {
2218 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2219 SCIPfreeBlockMemoryArray(heurdata->subscip, &dualval, 1);
2220 }
2221 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2222
2223 /* save the dualvalues from our nlp solution */
2224 for( i = 0; i < nsubconss; i++ )
2225 {
2226 SCIP_CONS* transcons;
2227
2228 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, subconss[i], &transcons) );
2229
2230 if( transcons == NULL )
2231 continue;
2232
2233 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") )
2234 continue;
2235
2236 nlrow = (SCIP_NLROW*)SCIPhashmapGetImage(heurdata->conss2nlrow, transcons);
2237
2238 if (nlrow != NULL)
2239 {
2240 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2241 *dualval = SCIPnlrowGetDualsol(nlrow);
2242 }
2243 else
2244 {
2245 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2246 *dualval = 0;
2247 }
2248
2249 SCIP_CALL( SCIPhashmapInsert(heurdata->dualvalues, subconss[i], dualval) );
2250 }
2251
2252 bestsol = NULL;
2253 SCIP_CALL( createSolFromNLP(heurdata->subscip, heur, &bestsol) );
2254 }
2255
2256 /* if we are infeasible, we can't do anything*/
2257 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
2258 {
2259 SCIPdebugMsg(scip, "return4 : the subscip is infeasible\n");
2260
2261 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2262
2263 return SCIP_OKAY;
2264 }
2265
2266 maxslack = maximalslack(scip, heurdata);
2267 SCIPdebugMsg(scip, "origObj: %f\n", SCIPgetSolOrigObj(heurdata->subscip, bestsol));
2268 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
2269 objvalue = 0.0;
2270 assert(bestsol != NULL);
2271
2272 /* save information about maximal violation */
2273 for( i = 0; i < nsubvars; i++ )
2274 {
2275 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
2276
2277 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) == NULL )
2278 objvalue += SCIPvarGetObj(subvar) * SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
2279 }
2280
2281 /* we stop the heuristic if it does not come "closer" to a feasible solution*/
2282 if( heurdata->forceimprovements )
2283 {
2284 if( SCIPisGE(scip, SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue, heurdata->prevobjective) && maxslack > 0 )
2285 {
2286 heurdata->nonimprovingRounds++;
2287 SCIPdebugMsg(scip, "nonimpr rounds %d prevobj %f \n", heurdata->nonimprovingRounds, heurdata->prevobjective);
2288
2289 /* leave, if we have not improved some iterations*/
2290 if( heurdata->nonimprovingRounds > heurdata->maxcalls/8 )
2291 {
2292 *result = SCIP_DIDNOTFIND;
2293
2294 if( heurdata->isnlp )
2295 {
2296 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2297 }
2298
2299 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2300
2301 heurdata->solfound = TRUE;
2302 heurdata->switchdifferent = TRUE;
2303
2304 SCIPdebugMsg(scip, "return11 : solution did not improve\n");
2305
2306 return SCIP_OKAY;
2307 }
2308 }
2309 }
2310
2311 heurdata->prevobjective = SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue;
2312
2313 /* in this case we found a feasible solution, store it, clean up and stop the heuristic*/
2314 if( SCIPisFeasLE(heurdata->subscip, maxslack, 0.0) )
2315 return storeSolution(scip, heur, result, transsol, bestsol);
2316
2317 SCIP_CALL( SCIPallocBufferArray(scip, &ranks, heurdata->nintegervars) );
2318 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, heurdata->nintegervars) );
2319 SCIP_CALL( SCIPallocBufferArray(scip, &absranks, heurdata->nintegervars) );
2320
2321 /* compute ranks and sort them in non-increasing order */
2322 SCIP_CALL( computeRanks(scip, heurdata, absranks, ranks, sortedvars) );
2323
2324 /* print out the highest ranks */
2325 if( heurdata->heurverblevel > 1 )
2326 {
2327 k = heurdata->rankvalue;
2328
2329 if( heurdata->nintegervars < heurdata->rankvalue )
2330 k = heurdata->nintegervars;
2331
2332 for( i = 0; i < k; i++ )
2333 {
2334 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%i. rank: %f name: %s\n", i, ranks[i], SCIPvarGetName(sortedvars[i]));
2335 }
2336 }
2337
2338 /* free solution */
2339 if( heurdata->isnlp )
2340 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2341
2342 /* we don't allow more than a third of the variables to have the same rank */
2343 maxequalranks = MIN(heurdata->maxequalranks, heurdata->nintegervars/3);
2344
2345 if( heurdata->maxequalranks >= 0 && SCIPisFeasEQ(heurdata->subscip, REALABS(ranks[0]), REALABS(ranks[maxequalranks])) )
2346 {
2347 *result = SCIP_DIDNOTFIND;
2348
2349 SCIPdebugMsg(scip, "return12 : equal maxranks\n");
2350
2351 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, TRUE, TRUE ) );
2352 return SCIP_OKAY;
2353 }
2354
2355 /* now we can start switching the variable values */
2356 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
2357
2358 /* set bounds of fixed discrete variables to original values so we can switch */
2359 for( k = 0; k < heurdata->nintegervars; ++k )
2360 {
2361 var = heurdata->integervars[k];
2362 if( var == NULL )
2363 break;
2364
2365 var = SCIPvarGetTransVar(var);
2366 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
2367
2368 rcons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->relaxcons, subvar);
2369 if( rcons != NULL )
2370 continue;
2371
2372 assert(var != NULL);
2373 assert(subvar != NULL);
2374
2375 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
2376 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, subvar);
2377
2378 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(heurdata->integervars[k])) );
2379 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(heurdata->integervars[k])) );
2380 }
2381
2382 /* switch variable with maximum ranking if possible */
2383 for( i = 0; i < heurdata->nintegervars; i++ )
2384 {
2385 v = sortedvars[i];
2386 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &newval, 1) ); /*lint !e506*/
2387
2388 /* compute the new value of the variable */
2389
2390 /* if we have an indicator constraint, we turn it off */
2391 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v) != NULL )
2392 {
2393 /* get the indicator var of this constraint */
2394 v = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v);
2395
2396 /* set the value to 0 */
2397 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, 0.0) );
2398 if( heurdata->heurverblevel > 1 )
2399 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s%s to 0\n", SCIPvarIsNegated(v) ? "(negated) " : " ", SCIPvarGetName(v));
2400
2401 *newval = 0.0;
2402 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2403 }
2404 else
2405 {
2406 if( ranks[i] > 0 )
2407 {
2408 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 1.0, SCIPgetSolVal(scip, transsol, v)) )
2409 continue;
2410
2411 /* ignore fixed vars in input */
2412 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(v), SCIPvarGetUbGlobal(v)) )
2413 continue;
2414
2415 *newval = SCIPgetSolVal(scip, transsol, v) + 1;
2416 }
2417 else
2418 {
2419 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 0.0, SCIPgetSolVal(scip, transsol, v)) )
2420 continue;
2421
2422 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(v), SCIPvarGetUbGlobal(v)) )
2423 continue;
2424
2425 *newval = SCIPgetSolVal(scip, transsol, v) - 1;
2426 }
2427 }
2428 lastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, v);
2429 seclastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, v);
2430
2431 /* we don't want to set a variable to a value it already had,or set a binary variable more than once */
2432 if( (lastval != NULL && (SCIPvarIsBinary(v) || SCIPisFeasEQ(scip, *lastval, *newval))) || (seclastval != NULL && SCIPisFeasEQ(scip, *seclastval, *newval)) )
2433 {
2434 SCIPfreeBlockMemoryArray(heurdata->subscip, &newval, 1);
2435 continue;
2436 }
2437 else /* update the switchedvars values, switchedvars2 is the second last and switchedvars the last value */
2438 {
2439 if( seclastval != NULL )
2440 SCIPfreeBlockMemoryArray(heurdata->subscip, &seclastval, 1);
2441
2442 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars2, v) );
2443 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars2, v, lastval) );
2444 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars, v) );
2445 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2446
2447 if( heurdata->heurverblevel > 1 )
2448 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s from %f to %f\n", SCIPvarGetName(v), SCIPgetSolVal(scip, transsol, v), *newval);
2449
2450 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, *newval) );
2451 }
2452
2453 /* if we have exceeded our iterations limit give up without any solution */
2454 if( heurdata->usedcalls >= heurdata->maxcalls )
2455 {
2456 SCIPdebugMsg(scip, "return5 : reached iteration limit\n");
2457
2458 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) );
2459 *result = SCIP_DIDNOTFIND;
2460 return SCIP_OKAY;
2461 }
2462
2463 heurdata->usedcalls++;
2464
2465 if( heurdata->heurverblevel > 1 )
2466 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "----- Total Calls: %d\n", heurdata->usedcalls);
2467
2468 /* recursive call of the heuristic */
2469 SCIP_CALL( SCIPapplyHeurDualval(scip, heur, result, transsol) );
2470
2471 /* just to go up in the recursion */
2472 if( *result == SCIP_DIDNOTFIND || heurdata->solfound || heurdata->prevInfeasible )
2473 {
2474 SCIPdebugMsg(scip, "return6 : go up\n");
2475
2476 /* here we only go up one step and try another switch (switch the same variables again is forbidden
2477 * since they are contained in switchedvars) */
2478 if( heurdata->switchdifferent )
2479 {
2480 heurdata->switchdifferent = FALSE;
2481 heurdata->solfound = FALSE;
2482 *result = SCIP_DIDNOTRUN;
2483 heurdata->nonimprovingRounds -= 2;
2484 }
2485
2486 if( heurdata->prevInfeasible )
2487 {
2488 heurdata->prevInfeasible = FALSE;
2489 heurdata->solfound = FALSE;
2490 *result = SCIP_DIDNOTRUN;
2491 heurdata->nonimprovingRounds++;
2492 }
2493
2494 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, FALSE) );
2495 return SCIP_OKAY;
2496 }
2497 }
2498
2499 if( heurdata->subscip == NULL )
2500 {
2501 /* something horrible must have happened that we decided to give up completely on this heuristic */
2502 *result = SCIP_DIDNOTFIND;
2503 SCIPdebugMsg(scip, "return7 : subscip was set NULL\n");
2504
2505 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) );
2506 return SCIP_OKAY;
2507 }
2508 assert(!SCIPisTransformed(heurdata->subscip));
2509
2510 SCIPdebugMsg(scip, "return8 : cannot switch any variable\n");
2511
2512 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) );
2513
2514 *result = SCIP_DIDNOTFIND;
2515 return SCIP_OKAY;
2516 }
2517
2518
2519 /* Callback methods of primal heuristic */
2520
2521 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2522 static
SCIP_DECL_HEURFREE(heurFreeDualval)2523 SCIP_DECL_HEURFREE(heurFreeDualval)
2524 {
2525 SCIP_HEURDATA* heurdata;
2526
2527 assert(scip != NULL);
2528 assert(heur != NULL);
2529
2530 heurdata = SCIPheurGetData(heur);
2531
2532 SCIPfreeBlockMemory(scip, &heurdata);
2533
2534 return SCIP_OKAY;
2535 }
2536
2537
2538 /** initialization method of primal heuristic (called after problem was transformed) */
2539 static
SCIP_DECL_HEURINIT(heurInitDualval)2540 SCIP_DECL_HEURINIT(heurInitDualval)
2541 { /*lint --e{715}*/
2542 SCIP_HEURDATA* heurdata;
2543
2544 assert(scip != NULL);
2545 assert(heur != NULL);
2546
2547 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2548 if( SCIPheurGetFreq(heur) < 0 )
2549 return SCIP_OKAY;
2550
2551 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
2552
2553 heurdata = SCIPheurGetData(heur);
2554 assert(heurdata != NULL);
2555 assert(heurdata->subscip == NULL);
2556 assert(!heurdata->triedsetupsubscip);
2557
2558 /* create sub-SCIP for later use */
2559 SCIP_CALL( createSubSCIP(scip, heurdata) );
2560
2561 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2562 if( heurdata->subscip == NULL )
2563 return SCIP_OKAY;
2564
2565 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2566 if( SCIPheurGetFreqofs(heur) == 0 )
2567 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | HEUR_TIMING);
2568
2569 SCIP_CALL( SCIPhashmapCreate(&heurdata->dualvalues, SCIPblkmem(scip), 512) );
2570
2571 return SCIP_OKAY;
2572 }
2573
2574 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
2575 static
SCIP_DECL_HEUREXIT(heurExitDualval)2576 SCIP_DECL_HEUREXIT(heurExitDualval)
2577 { /*lint --e{715}*/
2578 SCIP_HEURDATA* heurdata;
2579 SCIP_CONS** subconss;
2580 SCIP_Real* dualval;
2581 int i;
2582 int nsubconss;
2583
2584 assert(scip != NULL);
2585 assert(heur != NULL);
2586
2587 heurdata = SCIPheurGetData(heur);
2588 assert(heurdata != NULL);
2589
2590 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->integervars, heurdata->integervarssize);
2591
2592 if( heurdata->subscip != NULL)
2593 {
2594 nsubconss = SCIPgetNOrigConss(heurdata->subscip);
2595 subconss = SCIPgetOrigConss(heurdata->subscip);
2596
2597 /* free memory of all entries and clear the hashmap before filling it */
2598 for( i = 0; i < nsubconss; i++ )
2599 {
2600 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2601 SCIPfreeBlockMemoryArrayNull(heurdata->subscip, &dualval, 1);
2602 }
2603 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2604 SCIPhashmapFree(&heurdata->dualvalues);
2605
2606 if( heurdata->varsciptosubscip != NULL )
2607 {
2608 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->varsciptosubscip, TRUE) );
2609
2610 SCIPhashmapFree(&heurdata->varsciptosubscip);
2611 }
2612 if( heurdata->origsubscipConsMap != NULL )
2613 {
2614 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->origsubscipConsMap, FALSE) );
2615
2616 SCIPhashmapFree(&heurdata->origsubscipConsMap);
2617 }
2618 if( heurdata->relaxcons != NULL )
2619 {
2620 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxcons, FALSE) );
2621
2622 SCIPhashmapFree(&heurdata->relaxcons);
2623 }
2624 if( heurdata->conss2nlrow != NULL )
2625 {
2626 SCIP_CALL( releaseHashmapNLPRows(heurdata->subscip, heurdata->conss2nlrow) );
2627
2628 SCIPhashmapFree(&heurdata->conss2nlrow);
2629 }
2630 if( heurdata->slack2var != NULL )
2631 {
2632 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slack2var, TRUE) );
2633
2634 SCIPhashmapFree(&heurdata->slack2var);
2635 }
2636 if( heurdata->indicopymap != NULL )
2637 {
2638 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymap, TRUE) );
2639
2640 SCIPhashmapFree(&heurdata->indicopymap);
2641 }
2642 if( heurdata->indicopymapback != NULL )
2643 {
2644 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymapback, TRUE) );
2645
2646 SCIPhashmapFree(&heurdata->indicopymapback);
2647 }
2648 if( heurdata->relaxconsindi != NULL )
2649 {
2650 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxconsindi, FALSE) );
2651
2652 SCIPhashmapFree(&heurdata->relaxconsindi);
2653 }
2654 if( heurdata->slackvarlbMap != NULL )
2655 {
2656 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarlbMap, TRUE) );
2657
2658 SCIPhashmapFree(&heurdata->slackvarlbMap);
2659 }
2660 if( heurdata->slackvarubMap != NULL )
2661 {
2662 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarubMap, TRUE) );
2663
2664 SCIPhashmapFree(&heurdata->slackvarubMap);
2665 }
2666
2667 if( heurdata->subscip != NULL )
2668 {
2669 SCIP_CALL( freeSubSCIP(scip, heurdata) );
2670 }
2671 }
2672
2673 if( heurdata->varsubsciptoscip != NULL )
2674 {
2675 SCIP_CALL( releaseHashmapEntries(scip, heurdata->varsubsciptoscip, TRUE) );
2676
2677 SCIPhashmapFree(&heurdata->varsubsciptoscip);
2678 }
2679 if( heurdata->slacktoindivarsmap != NULL )
2680 {
2681 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
2682
2683 SCIPhashmapFree(&heurdata->slacktoindivarsmap);
2684 }
2685 if( heurdata->indicators != NULL )
2686 {
2687 SCIP_CALL( releaseHashmapEntries(scip, heurdata->indicators, FALSE) );
2688
2689 SCIPhashmapFree(&heurdata->indicators);
2690 }
2691 if( heurdata->switchedvars != NULL )
2692 {
2693 SCIPhashmapFree(&heurdata->switchedvars);
2694 }
2695 if( heurdata->switchedvars2 != NULL )
2696 {
2697 SCIPhashmapFree(&heurdata->switchedvars2);
2698 }
2699
2700 /* reset some flags and counters */
2701 heurdata->triedsetupsubscip = FALSE;
2702 heurdata->usedcalls = 0;
2703 heurdata->solfound = FALSE;
2704 heurdata->prevInfeasible = FALSE;
2705
2706 assert(heurdata->subscip == NULL);
2707 assert(heurdata->varsubsciptoscip == NULL);
2708 assert(heurdata->varsciptosubscip == NULL);
2709
2710 return SCIP_OKAY;
2711 }
2712
2713 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2714 static
SCIP_DECL_HEURINITSOL(heurInitsolDualval)2715 SCIP_DECL_HEURINITSOL(heurInitsolDualval)
2716 {
2717 SCIP_HEURDATA* heurdata;
2718
2719 assert(scip != NULL);
2720 assert(heur != NULL);
2721
2722 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2723 if( SCIPheurGetFreq(heur) < 0 )
2724 return SCIP_OKAY;
2725
2726 heurdata = SCIPheurGetData(heur);
2727 assert(heurdata != NULL);
2728
2729 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2730 if( heurdata->subscip == NULL )
2731 return SCIP_OKAY;
2732
2733 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2734 if( SCIPheurGetFreqofs(heur) == 0 )
2735 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | HEUR_TIMING);
2736
2737 return SCIP_OKAY;
2738 }
2739
2740
2741 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2742 static
SCIP_DECL_HEUREXITSOL(heurExitsolDualval)2743 SCIP_DECL_HEUREXITSOL(heurExitsolDualval)
2744 {
2745 assert(scip != NULL);
2746 assert(heur != NULL);
2747
2748 SCIPheurSetTimingmask(heur, HEUR_TIMING);
2749
2750 return SCIP_OKAY;
2751 }
2752
2753
2754 /** execution method of primal heuristic */
2755 static
SCIP_DECL_HEUREXEC(heurExecDualval)2756 SCIP_DECL_HEUREXEC(heurExecDualval)
2757 { /*lint --e{715}*/
2758 SCIP_HEURDATA* heurdata;
2759
2760 assert(scip != NULL);
2761 assert(heur != NULL);
2762 assert(result != NULL);
2763
2764 /* get heuristic's data */
2765 heurdata = SCIPheurGetData(heur);
2766 assert(heurdata != NULL);
2767
2768 /* obviously, we did not do anything yet */
2769 *result = SCIP_DIDNOTRUN;
2770
2771 /* init data */
2772 heurdata->usedcalls = 0;
2773 heurdata->prevInfeasible = FALSE;
2774 heurdata->solfound = FALSE;
2775 heurdata->nonimprovingRounds = 0;
2776 heurdata->prevobjective = INT_MAX;
2777
2778 SCIP_CALL( SCIPapplyHeurDualval(scip, heur, result, NULL) );
2779
2780 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */
2781 if( *result == SCIP_CUTOFF )
2782 *result = SCIP_DIDNOTFIND;
2783
2784 /* reset timing, if it was changed temporary (at the root node) */
2785 if( heurtiming != HEUR_TIMING )
2786 SCIPheurSetTimingmask(heur, HEUR_TIMING);
2787
2788 return SCIP_OKAY;
2789 }
2790
2791
2792 /* primal heuristic specific interface methods */
2793
2794 /** creates the dualval primal heuristic and includes it in SCIP */
SCIPincludeHeurDualval(SCIP * scip)2795 SCIP_RETCODE SCIPincludeHeurDualval(
2796 SCIP* scip /**< SCIP data structure */
2797 )
2798 {
2799 SCIP_HEURDATA* heurdata = NULL;
2800 SCIP_HEUR* heur = NULL;
2801
2802 /* create dualval primal heuristic data */
2803 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2804 BMSclearMemory(heurdata);
2805
2806 /* include primal heuristic */
2807
2808 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2809 * compile independent of new callbacks being added in future SCIP versions */
2810 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2811 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2812 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDualval, heurdata) );
2813
2814 assert(heur != NULL);
2815
2816 /* set non fundamental callbacks via setter functions */
2817 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDualval) );
2818 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitDualval) );
2819 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitDualval) );
2820 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolDualval) );
2821 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolDualval) );
2822
2823 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/forceimprovements",
2824 "exit if objective doesn't improve",
2825 &heurdata->forceimprovements, TRUE, DEFAULT_FORCEIMPROVEMENTS, NULL, NULL) );
2826
2827 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlycheaper",
2828 "add constraint to ensure that discrete vars are improving",
2829 &heurdata->onlycheaper, TRUE, DEFAULT_ONLYCHEAPER, NULL, NULL) );
2830
2831 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyleaves",
2832 "disable the heuristic if it was not called at a leaf of the B&B tree",
2833 &heurdata->onlyleaves, FALSE, DEFAULT_ONLYLEAVES, NULL, NULL) );
2834
2835 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxindicators",
2836 "relax the indicator variables by introducing continuous copies",
2837 &heurdata->relaxindicators, FALSE, DEFAULT_RELAXINDICATORS, NULL, NULL) );
2838
2839 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxcontvars",
2840 "relax the continous variables",
2841 &heurdata->relaxcontvars, FALSE, DEFAULT_RELAXCONTVARS, NULL, NULL) );
2842
2843 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/heurverblevel",
2844 "verblevel of the heuristic, default is 0 to display nothing",
2845 &heurdata->heurverblevel, FALSE, DEFAULT_HEURVERBLEVEL, 0, 4, NULL, NULL) );
2846
2847 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nlpverblevel",
2848 "verblevel of the nlp solver, can be 0 or 1",
2849 &heurdata->nlpverblevel, FALSE, DEFAULT_NLPVERBLEVEL, 0, 1, NULL, NULL) );
2850
2851 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/rankvalue",
2852 "number of ranks that should be displayed when the heuristic is called",
2853 &heurdata->rankvalue, FALSE, DEFAULT_RANKVALUE, 0, INT_MAX, NULL, NULL) );
2854
2855 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcalls",
2856 "maximal number of recursive calls of the heuristic (if dynamicdepth is off)",
2857 &heurdata->maxcalls, FALSE, DEFAULT_MAXCALLS, 0, INT_MAX, NULL, NULL) );
2858
2859 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/dynamicdepth",
2860 "says if and how the recursion depth is computed at runtime",
2861 &heurdata->dynamicdepth, FALSE, DEFAULT_DYNAMICDEPTH, 0, 1, NULL, NULL) );
2862
2863 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxequalranks",
2864 "maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1",
2865 &heurdata->maxequalranks, FALSE, DEFAULT_MAXEQUALRANKS, -1, INT_MAX, NULL, NULL) );
2866
2867 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
2868 "minimal gap for which we still run the heuristic, if gap is less we return without doing anything",
2869 &heurdata->mingap, FALSE, DEFAULT_MINGAP, 0.0, 100.0, NULL, NULL) );
2870
2871 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaslack",
2872 "value added to objective of slack variables, must not be zero",
2873 &heurdata->lambdaslack, FALSE, DEFAULT_LAMBDASLACK, 0.1, SCIPinfinity(scip), NULL, NULL) );
2874
2875 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaobj",
2876 "scaling factor for the objective function",
2877 &heurdata->lambdaobj, FALSE, DEFAULT_LAMBDAOBJ, 0.0, 1.0, NULL, NULL) );
2878
2879 return SCIP_OKAY;
2880 }
2881