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