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