Scippy

SCIP

Solving Constraint Integer Programs

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