Scippy

SCIP

Solving Constraint Integer Programs

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