# SCIP

Solving Constraint Integer Programs

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