Scippy

SCIP

Solving Constraint Integer Programs

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