Scippy

SCIP

Solving Constraint Integer Programs

heur_undercover.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_undercover.c
17  * @brief Undercover primal heuristic for MINLPs
18  * @author Timo Berthold
19  * @author Ambros Gleixner
20  *
21  * The undercover heuristic is designed for mixed-integer nonlinear programs and tries to fix a subset of variables such
22  * as to make each constraint linear or convex. For this purpose it solves a binary program to automatically determine
23  * the minimum number of variable fixings necessary. As fixing values, we use values from the LP relaxation, the NLP
24  * relaxation, or the incumbent solution.
25  *
26  * @todo use the conflict analysis to analyze the infeasibility which arise after the probing of the cover worked and
27  * solve returned infeasible, instead of adding the Nogood/Conflict by hand; that has the advantage that the SCIP
28  * takes care of creating the conflict and might shrink the initial reason
29  *
30  * @todo do not use LP and NLP fixing values in the same run, e.g., fixingalts = "lni", but start a second dive if LP
31  * values fail
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "scip/scip.h"
40 #include "scip/scipdefplugins.h"
41 #include "scip/heur_undercover.h"
42 #include "scip/pub_misc.h"
43 #include "nlpi/exprinterpret.h"
44 
45 #define HEUR_NAME "undercover"
46 #define HEUR_DESC "solves a sub-CIP determined by a set covering approach"
47 #define HEUR_DISPCHAR 'U'
48 #define HEUR_PRIORITY -1110000
49 #define HEUR_FREQ 0
50 #define HEUR_FREQOFS 0
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
53 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
54 
55 /* default values for user parameters, grouped by parameter type */
56 #define DEFAULT_FIXINGALTS "li" /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
57 
58 #define DEFAULT_MAXNODES (SCIP_Longint)500/**< maximum number of nodes to regard in the subproblem */
59 #define DEFAULT_MINNODES (SCIP_Longint)500/**< minimum number of nodes to regard in the subproblem */
60 #define DEFAULT_NODESOFS (SCIP_Longint)500/**< number of nodes added to the contingent of the total nodes */
61 
62 #define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight for conflict score in fixing order */
63 #define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight for cutoff score in fixing order */
64 #define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight for inference score in fixing order */
65 #define DEFAULT_MAXCOVERSIZEVARS 1.0 /**< maximum coversize (as fraction of total number of variables) */
66 #define DEFAULT_MAXCOVERSIZECONSS SCIP_REAL_MAX /**< maximum coversize (as ratio to the percentage of non-affected constraints) */
67 #define DEFAULT_MINCOVEREDREL 0.15 /**< minimum percentage of nonlinear constraints in the original problem */
68 #define DEFAULT_MINCOVEREDABS 5 /**< minimum number of nonlinear constraints in the original problem */
69 #define DEFAULT_MINIMPROVE 0.0 /**< factor by which heuristic should at least improve the incumbent */
70 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
71 #define DEFAULT_RECOVERDIV 0.9 /**< fraction of covering variables in the last cover which need to change their value when recovering */
72 
73 #define DEFAULT_MAXBACKTRACKS 6 /**< maximum number of backtracks */
74 #define DEFAULT_MAXRECOVERS 0 /**< maximum number of recoverings */
75 #define DEFAULT_MAXREORDERS 1 /**< maximum number of reorderings of the fixing order */
76 
77 #define DEFAULT_COVERINGOBJ 'u' /**< objective function of the covering problem */
78 #define DEFAULT_FIXINGORDER 'v' /**< order in which variables should be fixed */
79 
80 #define DEFAULT_BEFORECUTS TRUE /**< should undercover called at root node before cut separation? */
81 #define DEFAULT_FIXINTFIRST FALSE /**< should integer variables in the cover be fixed first? */
82 #define DEFAULT_LOCKSROUNDING TRUE /**< shall LP values for integer vars be rounded according to locks? */
83 #define DEFAULT_ONLYCONVEXIFY FALSE /**< should we only fix/dom.red. variables creating nonconvexity? */
84 #define DEFAULT_POSTNLP TRUE /**< should the NLP heuristic be called to polish a feasible solution? */
85 #define DEFAULT_COVERBD FALSE /**< should bounddisjunction constraints be covered (or just copied)? */
86 #define DEFAULT_REUSECOVER FALSE /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */
87 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied
88  * to constraints of the subscip
89  */
90 #define DEFAULT_RANDSEED 43 /* initial random seed */
91 
92 /* local defines */
93 #define COVERINGOBJS "cdlmtu" /**< list of objective functions of the covering problem */
94 #define FIXINGORDERS "CcVv" /**< list of orders in which variables can be fixed */
95 #define MAXNLPFAILS 1 /**< maximum number of fails after which we give up solving the NLP relaxation */
96 #define MAXPOSTNLPFAILS 1 /**< maximum number of fails after which we give up calling NLP local search */
97 #define MINTIMELEFT 1.0 /**< don't start expensive parts of the heuristics if less than this amount of time left */
98 #define SUBMIPSETUPCOSTS 200 /**< number of nodes equivalent for the costs for setting up the sub-CIP */
99 
100 
101 /*
102  * Data structures
103  */
104 
105 /** primal heuristic data */
106 struct SCIP_HeurData
107 {
108  SCIP_CONSHDLR** nlconshdlrs; /**< array of nonlinear constraint handlers */
109  SCIP_HEUR* nlpheur; /**< pointer to NLP local search heuristics */
110  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
111  char* fixingalts; /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
112  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
113  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
114  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
115  SCIP_Longint nusednodes; /**< nodes already used by heuristic in earlier calls */
116  SCIP_Real conflictweight; /**< weight for conflict score in fixing order */
117  SCIP_Real cutoffweight; /**< weight for cutoff score in fixing order */
118  SCIP_Real inferenceweight; /**< weight for inference score in foxing order */
119  SCIP_Real maxcoversizevars; /**< maximum coversize (as fraction of total number of variables) */
120  SCIP_Real maxcoversizeconss; /**< maximum coversize maximum coversize (as ratio to the percentage of non-affected constraints) */
121  SCIP_Real mincoveredrel; /**< minimum percentage of nonlinear constraints in the original problem */
122  SCIP_Real minimprove; /**< factor by which heuristic should at least improve the incumbent */
123  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
124  SCIP_Real recoverdiv; /**< fraction of covering variables in the last cover which need to change their value when recovering */
125  int mincoveredabs; /**< minimum number of nonlinear constraints in the original problem */
126  int maxbacktracks; /**< maximum number of backtracks */
127  int maxrecovers; /**< maximum number of recoverings */
128  int maxreorders; /**< maximum number of reorderings of the fixing order */
129  int nfixingalts; /**< number of fixing alternatives */
130  int nnlpfails; /**< number of fails when solving the NLP relaxation after last success */
131  int npostnlpfails; /**< number of fails of the NLP local search after last success */
132  int nnlconshdlrs; /**< number of nonlinear constraint handlers */
133  char coveringobj; /**< objective function of the covering problem */
134  char fixingorder; /**< order in which variables should be fixed */
135  SCIP_Bool beforecuts; /**< should undercover be called at root node before cut separation? */
136  SCIP_Bool fixintfirst; /**< should integer variables in the cover be fixed first? */
137  SCIP_Bool globalbounds; /**< should global bounds on variables be used instead of local bounds at focus node? */
138  SCIP_Bool locksrounding; /**< shall LP values for integer vars be rounded according to locks? */
139  SCIP_Bool nlpsolved; /**< has current NLP relaxation already been solved successfully? */
140  SCIP_Bool nlpfailed; /**< has solving the NLP relaxation failed? */
141  SCIP_Bool onlyconvexify; /**< should we only fix/dom.red. variables creating nonconvexity? */
142  SCIP_Bool postnlp; /**< should the NLP heuristic be called to polish a feasible solution? */
143  SCIP_Bool coverbd; /**< should bounddisjunction constraints be covered (or just copied)? */
144  SCIP_Bool reusecover; /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */
145  SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
146  * subproblem? */
147 };
148 
149 /** working memory for retrieving dense sparsity of Hessian matrices */
150 struct HessianData
151 {
152  SCIP_SOL* evalsol;
153  SCIP_Real* varvals;
154  SCIP_Bool* sparsity;
155  int nvars;
156 };
157 
158 /*
159  * Local methods
160  */
161 
162 
163 /** determines, whether a variable is fixed to the given value */
164 static
165 SCIP_Bool varIsFixed(
166  SCIP* scip, /**< SCIP data structure */
167  SCIP_VAR* var, /**< variable to check */
168  SCIP_Real val, /**< value to check */
169  SCIP_Bool global /**< should global bounds be used? */
170  )
171 {
172  SCIP_Bool isfixed;
173 
174  if( global )
175  isfixed = SCIPisFeasEQ(scip, val, SCIPvarGetLbGlobal(var)) && SCIPisFeasEQ(scip, val, SCIPvarGetUbGlobal(var));
176  else
177  isfixed = SCIPisFeasEQ(scip, val, SCIPvarGetLbLocal(var)) && SCIPisFeasEQ(scip, val, SCIPvarGetUbLocal(var));
178 
179  return isfixed;
180 }
181 
182 
183 /** determines, whether a term is already constant, because the variable is fixed or the coefficient is zero */
184 static
185 SCIP_Bool termIsConstant(
186  SCIP* scip, /**< SCIP data structure */
187  SCIP_VAR* var, /**< variable to check */
188  SCIP_Real coeff, /**< coefficient to check */
189  SCIP_Bool global /**< should global bounds be used? */
190  )
191 {
192  /* if the variable has zero coefficient in the original problem, the term is linear */
193  if( SCIPisZero(scip, coeff) )
194  return TRUE;
195 
196  /* if the variable is fixed in the original problem, the term is linear */
197  if( global )
198  return SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
199  else
200  return SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
201 
202 }
203 
204 
205 /** determines, whether a term is convex */
206 static
207 SCIP_Bool termIsConvex(
208  SCIP* scip, /**< SCIP data structure */
209  SCIP_Real lhs, /**< left hand side of the constraint */
210  SCIP_Real rhs, /**< right hand side of the constraint */
211  SCIP_Bool sign /**< signature of the term */
212  )
213 {
214  return sign ? SCIPisInfinity(scip, -lhs) : SCIPisInfinity(scip, rhs);
215 }
216 
217 
218 /** increases counters */
219 static
220 void incCounters(
221  int* termcounter, /**< array to count in how many nonlinear terms a variable appears */
222  int* conscounter, /**< array to count in how many constraints a variable appears */
223  SCIP_Bool* consmarker, /**< was this variable already counted for this constraint? */
224  int idx /**< problem index of the variable */
225  )
226 {
227  termcounter[idx]++;
228  if( !consmarker[idx] )
229  {
230  conscounter[idx]++;
231  consmarker[idx] = TRUE;
232  }
233  return;
234 }
235 
236 
237 /** update time limit */
238 static
239 SCIP_RETCODE updateTimelimit(
240  SCIP* scip, /**< SCIP data structure */
241  SCIP_CLOCK* clck, /**< clock timer */
242  SCIP_Real* timelimit /**< time limit */
243  )
244 {
245  *timelimit -= SCIPgetClockTime(scip, clck);
246  SCIP_CALL( SCIPresetClock(scip, clck) );
247  SCIP_CALL( SCIPstartClock(scip, clck) );
248 
249  return SCIP_OKAY;
250 }
251 
252 
253 /** analyzes a nonlinear row and adds constraints and fixings to the covering problem */
254 static
255 SCIP_RETCODE processNlRow(
256  SCIP* scip, /**< original SCIP data structure */
257  SCIP_NLROW* nlrow, /**< nonlinear row representation of a nonlinear constraint */
258  SCIP_EXPRINT* exprint, /**< expression interpreter for computing sparsity pattern of the Hessian;
259  * if NULL, we will simply fix all variables in the expression tree */
260  struct HessianData* hessiandata, /**< working memory for retrieving dense sparsity of Hessian matrices */
261  SCIP* coveringscip, /**< SCIP data structure for the covering problem */
262  int nvars, /**< number of variables */
263  SCIP_VAR** coveringvars, /**< array to store the covering problem's variables */
264  int* termcounter, /**< counter array for number of nonlinear nonzeros per variable */
265  int* conscounter, /**< counter array for number of nonlinear constraints per variable */
266  SCIP_Bool* consmarker, /**< marker array if constraint has been counted in conscounter */
267  SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
268  SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
269  SCIP_Bool* success /**< pointer to store whether row was processed successfully */
270  )
271 {
272  SCIP_EXPRTREE* exprtree;
273  SCIP_Bool infeas;
274  SCIP_Bool fixed;
275  int t;
276  char name[SCIP_MAXSTRLEN];
277 
278  assert(scip != NULL);
279  assert(nlrow != NULL);
280  assert(exprint == NULL || hessiandata != NULL);
281  assert(coveringscip != NULL);
282  assert(nvars >= 1);
283  assert(coveringvars != NULL);
284  assert(termcounter != NULL);
285  assert(conscounter != NULL);
286  assert(consmarker != NULL);
287  assert(success != NULL);
288 
289  *success = FALSE;
290  BMSclearMemoryArray(consmarker, nvars);
291 
292  /* go through expression tree */
293  exprtree = SCIPnlrowGetExprtree(nlrow);
294  if( exprtree != NULL )
295  {
296  SCIP_VAR** exprtreevars;
297  int nexprtreevars;
298  int probidx1;
299  int probidx2;
300 
301  /* get variables in expression tree */
302  nexprtreevars = SCIPexprtreeGetNVars(exprtree);
303  exprtreevars = SCIPexprtreeGetVars(exprtree);
304 
305  if( exprtreevars != NULL && nexprtreevars > 0 )
306  {
307  SCIP_Bool usehessian;
308  int i;
309 
310  /* is an expression interpreter available which can return the sparsity pattern of the Hessian? */
311  usehessian = exprint != NULL && (SCIPexprintGetCapability() & SCIP_EXPRINTCAPABILITY_HESSIAN);
312  if( usehessian )
313  {
314  int idx1;
315  int idx2;
316 
317  assert(hessiandata != NULL);
318  assert(hessiandata->nvars == 0 || hessiandata->varvals != NULL);
319  assert(hessiandata->nvars == 0 || hessiandata->sparsity != NULL);
320 
321  /* compile expression tree */
322  SCIP_CALL( SCIPexprintCompile(exprint, exprtree) );
323 
324  /* ensure memory */
325  if( hessiandata->nvars < nexprtreevars )
326  {
327  SCIP_CALL( SCIPreallocBufferArray(scip, &hessiandata->varvals, nexprtreevars) );
328  SCIP_CALL( SCIPreallocBufferArray(scip, &hessiandata->sparsity, nexprtreevars*nexprtreevars) );
329  hessiandata->nvars = nexprtreevars;
330  }
331 
332  /* get point at which to evaluate the Hessian sparsity */
333  if( hessiandata->evalsol == NULL )
334  {
335  SCIP_CALL( SCIPcreateSol(scip, &hessiandata->evalsol, NULL) );
336  SCIP_CALL( SCIPlinkCurrentSol(scip, hessiandata->evalsol) );
337  }
338  SCIP_CALL( SCIPgetSolVals(scip, hessiandata->evalsol, nexprtreevars, exprtreevars, hessiandata->varvals) );
339 
340  /* get sparsity of the Hessian at current LP solution */
341  SCIP_CALL( SCIPexprintHessianSparsityDense(exprint, exprtree, hessiandata->varvals, hessiandata->sparsity) );
342 
343  for( idx1 = nexprtreevars-1; idx1 >= 0; idx1-- )
344  {
345  /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */
346  probidx1 = SCIPvarGetProbindex(exprtreevars[idx1]);
347  if( probidx1 == -1 )
348  {
349  SCIPdebugMsg(scip, "strange: inactive variables detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
350  return SCIP_OKAY;
351  }
352 
353  /* nonzero diagonal element of the Hessian: fix */
354  if( hessiandata->sparsity[idx1*nexprtreevars + idx1]
355  && !termIsConstant(scip, exprtreevars[idx1], 1.0, globalbounds) )
356  {
357  SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx1], 1.0, &infeas, &fixed) );
358  assert(!infeas);
359  assert(fixed);
360 
361  /* update counters */
362  incCounters(termcounter, conscounter, consmarker, probidx1);
363 
364  SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx1]));
365 
366  /* if covering variable is fixed, then no need to still check non-diagonal elements */
367  continue;
368  }
369 
370  /* two different variables relate nonlinearly */
371  for( idx2 = nexprtreevars-1; idx2 > idx1; idx2-- )
372  {
373  SCIP_CONS* coveringcons;
374  SCIP_VAR* coveringconsvars[2];
375 
376  /* do not assume symmetry */
377  if( !hessiandata->sparsity[idx1*nexprtreevars + idx2] && !hessiandata->sparsity[idx2*nexprtreevars + idx1] )
378  continue;
379 
380  /* if diagonal has entry already, then covering constraint would always be satisfied, thus no need to add */
381  if( hessiandata->sparsity[idx2*nexprtreevars + idx2] && !termIsConstant(scip, exprtreevars[idx2], 1.0, globalbounds) )
382  continue;
383 
384  /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */
385  probidx2 = SCIPvarGetProbindex(exprtreevars[idx2]);
386  if( probidx2 == -1 )
387  {
388  SCIPdebugMsg(scip, "strange: inactive variables detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
389  return SCIP_OKAY;
390  }
391 
392  /* if the term is linear because one of the variables is fixed, nothing to do */
393  if( termIsConstant(scip, exprtreevars[idx1], 1.0, globalbounds)
394  || termIsConstant(scip, exprtreevars[idx2], 1.0, globalbounds) )
395  continue;
396 
397  /* create covering constraint */
398  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering_%d_%d", SCIPnlrowGetName(nlrow), idx1, idx2);
399  coveringconsvars[0] = coveringvars[probidx1];
400  coveringconsvars[1] = coveringvars[probidx2];
401  SCIP_CALL( SCIPcreateConsSetcover(coveringscip, &coveringcons, name, 2, coveringconsvars,
402  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
403 
404  if( coveringcons == NULL )
405  {
406  SCIPdebugMsg(scip, "failed to create set covering constraint <%s>\n", name);
407  return SCIP_OKAY;
408  }
409 
410  /* add and release covering constraint */
411  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
412  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
413 
414  SCIPdebugMsg(scip, "added covering constraint for vars <%s> and <%s> in covering problem\n", SCIPvarGetName(coveringvars[probidx1]), SCIPvarGetName(coveringvars[probidx2]));
415 
416  /* update counters for both variables */
417  incCounters(termcounter, conscounter, consmarker, probidx1);
418  incCounters(termcounter, conscounter, consmarker, probidx2);
419  }
420  }
421  }
422  /* fix all variables contained in the expression tree */
423  else
424  {
425  for( i = nexprtreevars-1; i >= 0; i-- )
426  {
427  assert(exprtreevars[i] != NULL);
428 
429  /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */
430  probidx1 = SCIPvarGetProbindex(exprtreevars[i]);
431  if( probidx1 == -1 )
432  {
433  SCIPdebugMsg(scip, "strange: inactive variable <%s> detected in nonlinear row <%s>\n",
434  SCIPvarGetName(exprtreevars[i]), SCIPnlrowGetName(nlrow));
435  return SCIP_OKAY;
436  }
437 
438  /* term is constant, nothing to do */
439  if( termIsConstant(scip, exprtreevars[i], 1.0, globalbounds) )
440  continue;
441 
442  /* otherwise fix variable */
443  SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx1], 1.0, &infeas, &fixed) );
444  assert(!infeas);
445  assert(fixed);
446 
447  /* update counters */
448  incCounters(termcounter, conscounter, consmarker, probidx1);
449 
450  SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx1]));
451  }
452  }
453  }
454  }
455 
456  /* go through all quadratic terms */
457  for( t = SCIPnlrowGetNQuadElems(nlrow)-1; t >= 0; t-- )
458  {
459  SCIP_QUADELEM* quadelem;
460  SCIP_VAR* bilinvar1;
461  SCIP_VAR* bilinvar2;
462  int probidx1;
463  int probidx2;
464 
465  /* get quadratic term */
466  quadelem = &SCIPnlrowGetQuadElems(nlrow)[t];
467 
468  /* get involved variables */
469  bilinvar1 = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1];
470  bilinvar2 = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2];
471  assert(bilinvar1 != NULL);
472  assert(bilinvar2 != NULL);
473 
474  /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */
475  probidx1 = SCIPvarGetProbindex(bilinvar1);
476  probidx2 = SCIPvarGetProbindex(bilinvar2);
477  if( probidx1 == -1 || probidx2 == -1 )
478  {
479  SCIPdebugMsg(scip, "inactive variables detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
480  return SCIP_OKAY;
481  }
482 
483  /* we have a square term */
484  if( bilinvar1 == bilinvar2 )
485  {
486  /* term is constant, nothing to do */
487  if( termIsConstant(scip, bilinvar1, quadelem->coef, globalbounds) )
488  continue;
489 
490  /* if we only convexify and term is convex considering the bounds of the nlrow, nothing to do */
491  if( onlyconvexify && termIsConvex(scip, SCIPnlrowGetLhs(nlrow), SCIPnlrowGetRhs(nlrow), quadelem->coef >= 0) )
492  continue;
493 
494  /* otherwise variable has to be in the cover */
495  SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx1], 1.0, &infeas, &fixed) );
496  assert(!infeas);
497  assert(fixed);
498 
499  /* update counters */
500  incCounters(termcounter, conscounter, consmarker, probidx1);
501 
502  SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx1]));
503  }
504  /* we have a bilinear term */
505  else
506  {
507  SCIP_CONS* coveringcons;
508  SCIP_VAR* coveringconsvars[2];
509 
510  /* if the term is linear because one of the variables is fixed or the coefficient is zero, nothing to do */
511  if( termIsConstant(scip, bilinvar1, quadelem->coef, globalbounds)
512  || termIsConstant(scip, bilinvar2, quadelem->coef, globalbounds) )
513  continue;
514 
515  /* create covering constraint */
516  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering%d", SCIPnlrowGetName(nlrow), t);
517  coveringconsvars[0] = coveringvars[probidx1];
518  coveringconsvars[1] = coveringvars[probidx2];
519  SCIP_CALL( SCIPcreateConsSetcover(coveringscip, &coveringcons, name, 2, coveringconsvars,
520  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
521 
522  if( coveringcons == NULL )
523  {
524  SCIPdebugMsg(scip, "failed to create set covering constraint <%s>\n", name);
525  return SCIP_OKAY;
526  }
527 
528  /* add and release covering constraint */
529  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
530  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
531 
532  /* update counters for both variables */
533  incCounters(termcounter, conscounter, consmarker, probidx1);
534  incCounters(termcounter, conscounter, consmarker, probidx2);
535  }
536  }
537 
538  *success = TRUE;
539 
540  return SCIP_OKAY;
541 }
542 
543 
544 /** creates the covering problem to determine a number of variables to be fixed */
545 static
546 SCIP_RETCODE createCoveringProblem(
547  SCIP* scip, /**< original SCIP data structure */
548  SCIP* coveringscip, /**< SCIP data structure for the covering problem */
549  SCIP_VAR** coveringvars, /**< array to store the covering problem's variables */
550  SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
551  SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
552  SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
553  char coveringobj, /**< objective function of the covering problem */
554  SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
555  )
556 {
557  SCIP_VAR** vars;
558  SCIP_CONSHDLR* conshdlr;
559  SCIP_HASHMAP* nlrowmap;
560  SCIP_EXPRINT* exprint;
561  SCIP_Bool* consmarker;
562  int* conscounter;
563  int* termcounter;
564 
565  struct HessianData hessiandata;
566  int nlocksup;
567  int nlocksdown;
568  int nvars;
569  int i;
570  int probindex;
571  char name[SCIP_MAXSTRLEN];
572 
573  assert(scip != NULL);
574  assert(coveringscip != NULL);
575  assert(coveringvars != NULL);
576  assert(success != NULL);
577 
578  *success = FALSE;
579 
580  /* get required data of the original problem */
581  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
582 
583  /* create problem data structure */
584  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPgetProbName(scip));
585  SCIP_CALL( SCIPcreateProb(coveringscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
586 
587  /* allocate and initialize to zero counter arrays for weighted objectives */
588  SCIP_CALL( SCIPallocBufferArray(scip, &consmarker, nvars) );
589  SCIP_CALL( SCIPallocBufferArray(scip, &conscounter, nvars) );
590  SCIP_CALL( SCIPallocBufferArray(scip, &termcounter, nvars) );
591  BMSclearMemoryArray(conscounter, nvars);
592  BMSclearMemoryArray(termcounter, nvars);
593 
594  /* create expression interpreter */
595  SCIP_CALL( SCIPexprintCreate(SCIPblkmem(scip), &exprint) );
596  assert(exprint != NULL);
597 
598  /* initialize empty hessiandata; memory will be allocated in method processNlRow() as required */
599  hessiandata.evalsol = NULL;
600  hessiandata.varvals = NULL;
601  hessiandata.sparsity = NULL;
602  hessiandata.nvars = 0;
603 
604  /* create covering variable for each variable in the original problem (fix it or not?) in the same order as in the
605  * original problem
606  */
607  for( i = 0; i < nvars; i++ )
608  {
609  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPvarGetName(vars[i]));
610  SCIP_CALL( SCIPcreateVar(coveringscip, &coveringvars[i], name, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
611  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
612  assert(coveringvars[i] != NULL);
613  SCIP_CALL( SCIPaddVar(coveringscip, coveringvars[i]) );
614  }
615 
616  /* first, go through some special constraint handlers which we do not want to treat by looking at their nlrow
617  * representation; we store these in a hash map and afterwards process all nlrows which are not found in the hash map
618  */
619  nlrowmap = NULL;
620  if( SCIPisNLPConstructed(scip) )
621  {
622  int nnlprows;
623 
624  nnlprows = SCIPgetNNLPNlRows(scip);
625  if( nnlprows > 0 )
626  {
627  int mapsize;
628 
629  /* calculate size of hash map */
630  conshdlr = SCIPfindConshdlr(scip, "quadratic");
631  mapsize = (conshdlr == NULL) ? 0 : SCIPconshdlrGetNActiveConss(conshdlr);
632  conshdlr = SCIPfindConshdlr(scip, "soc");
633  if( conshdlr != NULL )
634  mapsize += SCIPconshdlrGetNActiveConss(conshdlr);
635  mapsize = MAX(mapsize, nnlprows);
636  assert(mapsize > 0);
637 
638  /* create hash map */
639  SCIP_CALL( SCIPhashmapCreate(&nlrowmap, SCIPblkmem(scip), mapsize) );
640  assert(nlrowmap != NULL);
641  }
642  }
643 
644  /* go through all AND constraints in the original problem */
645  conshdlr = SCIPfindConshdlr(scip, "and");
646  if( conshdlr != NULL )
647  {
648  int c;
649 
650  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
651  {
652  SCIP_CONS* andcons;
653  SCIP_CONS* coveringcons;
654  SCIP_VAR** andvars;
655  SCIP_VAR* andres;
656  SCIP_VAR** coveringconsvars;
657  SCIP_Real* coveringconsvals;
658  SCIP_Bool negated;
659 
660  int ntofix;
661  int v;
662 
663  /* get constraint and variables */
664  andcons = SCIPconshdlrGetConss(conshdlr)[c];
665  assert(andcons != NULL);
666  andvars = SCIPgetVarsAnd(scip, andcons);
667  assert(andvars != NULL);
668 
669  /* "and" constraints are not passed to the NLP, hence nothing to store in the hash map */
670 
671  /* allocate memory for covering constraint */
672  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, SCIPgetNVarsAnd(scip, andcons)+1) );
673  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, SCIPgetNVarsAnd(scip, andcons)+1) );
674 
675  /* collect unfixed variables */
676  BMSclearMemoryArray(consmarker, nvars);
677  ntofix = 0;
678  for( v = SCIPgetNVarsAnd(scip, andcons)-1; v >= 0; v-- )
679  {
680  assert(andvars[v] != NULL);
681  negated = FALSE;
682 
683  /* if variable is fixed to 0, entire constraint can be linearized */
684  if( varIsFixed(scip, andvars[v], 0.0, globalbounds) )
685  {
686  ntofix = 0;
687  break;
688  }
689 
690  /* if variable is fixed, nothing to do */
691  if( termIsConstant(scip, andvars[v], 1.0, globalbounds) )
692  {
693  continue;
694  }
695 
696  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
697  probindex = SCIPvarGetProbindex(andvars[v]);
698  if( probindex == -1 )
699  {
700  SCIP_VAR* repvar;
701 
702  /* get binary representative of variable */
703  SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[v], &repvar, &negated) );
704  assert(repvar != NULL);
705  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
706 
707  if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
708  {
709  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(andvars[v]));
710  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
711  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
712  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
713  goto TERMINATE;
714  }
715 
716  /* check for negation */
717  if( SCIPvarIsNegated(repvar) )
718  {
719  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
720  negated = TRUE;
721  }
722  else
723  {
724  assert(SCIPvarIsActive(repvar));
725  probindex = SCIPvarGetProbindex(repvar);
726  negated = FALSE;
727  }
728  }
729  assert(probindex >= 0);
730 
731  /* add covering variable for unfixed original variable */
732  if( negated )
733  {
734  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
735  }
736  else
737  coveringconsvars[ntofix] = coveringvars[probindex];
738  coveringconsvals[ntofix] = 1.0;
739  ntofix++;
740  }
741  negated = FALSE;
742 
743  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
744  andres = SCIPgetResultantAnd(scip, andcons);
745  assert(andres != NULL);
746  probindex = SCIPvarGetProbindex(andres);
747 
748  /* if resultant is fixed this constraint can be either linearized or is redundant because all operands can be fixed */
749  if( termIsConstant(scip, andres, 1.0, globalbounds) )
750  {
751  /* free memory for covering constraint */
752  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
753  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
754 
755  continue;
756  }
757 
758  if( probindex == -1 )
759  {
760  SCIP_VAR* repvar;
761 
762  /* get binary representative of variable */
763  SCIP_CALL( SCIPgetBinvarRepresentative(scip, SCIPgetResultantAnd(scip, andcons), &repvar, &negated) );
764  assert(repvar != NULL);
765  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
766 
767  if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
768  {
769  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(SCIPgetResultantAnd(scip, andcons)));
770  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
771  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
772  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
773  goto TERMINATE;
774  }
775 
776  /* check for negation */
777  if( SCIPvarIsNegated(repvar) )
778  {
779  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
780  negated = TRUE;
781  }
782  else
783  {
784  assert(SCIPvarIsActive(repvar));
785  probindex = SCIPvarGetProbindex(repvar);
786  negated = FALSE;
787  }
788  }
789  else if( SCIPvarGetLbGlobal(andres) > 0.5 || SCIPvarGetUbGlobal(andres) < 0.5 )
790  {
791  /* free memory for covering constraint */
792  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
793  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
794 
795  continue;
796  }
797  assert(probindex >= 0);
798  assert(!termIsConstant(scip, (negated ? SCIPvarGetNegatedVar(vars[probindex]) : vars[probindex]), 1.0, globalbounds));
799 
800  /* if less than two variables are unfixed or the resultant variable is fixed, the entire constraint can be
801  * linearized anyway
802  */
803  if( ntofix >= 2 )
804  {
805  assert(ntofix <= SCIPgetNVarsAnd(scip, andcons));
806 
807  /* add covering variable for unfixed resultant */
808  if( negated )
809  {
810  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
811  }
812  else
813  coveringconsvars[ntofix] = coveringvars[probindex];
814  coveringconsvals[ntofix] = (SCIP_Real)(ntofix - 1);
815  ntofix++;
816 
817  /* create covering constraint */
818  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(andcons));
819  SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals,
820  (SCIP_Real)(ntofix - 2), SCIPinfinity(coveringscip),
821  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
822 
823  if( coveringcons == NULL )
824  {
825  SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
826  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
827  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
828  goto TERMINATE;
829  }
830 
831  /* add and release covering constraint */
832  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
833  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
834 
835  /* update counters */
836  for( v = ntofix-1; v >= 0; v-- )
837  if( SCIPvarIsNegated(coveringconsvars[v]) )
838  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v])));
839  else
840  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v]));
841  }
842 
843  /* free memory for covering constraint */
844  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
845  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
846  }
847  }
848 
849  /* go through all bounddisjunction constraints in the original problem */
850  conshdlr = SCIPfindConshdlr(scip, "bounddisjunction");
851  if( conshdlr != NULL && coverbd )
852  {
853  int c;
854 
855  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
856  {
857  SCIP_CONS* bdcons;
858  SCIP_CONS* coveringcons;
859  SCIP_VAR** bdvars;
860  SCIP_VAR** coveringconsvars;
861  SCIP_Real* coveringconsvals;
862 
863  int nbdvars;
864  int ntofix;
865  int v;
866 
867  /* get constraint and variables */
868  bdcons = SCIPconshdlrGetConss(conshdlr)[c];
869  assert(bdcons != NULL);
870  bdvars = SCIPgetVarsBounddisjunction(scip, bdcons);
871  assert(bdvars != NULL);
872  nbdvars = SCIPgetNVarsBounddisjunction(scip, bdcons);
873 
874  /* bounddisjunction constraints are not passed to the NLP, hence nothing to store in the hash map */
875 
876  /* allocate memory for covering constraint */
877  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, nbdvars) );
878  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, nbdvars) );
879 
880  /* collect unfixed variables */
881  BMSclearMemoryArray(consmarker, nvars);
882  ntofix = 0;
883  for( v = nbdvars-1; v >= 0; v-- )
884  {
885  SCIP_Bool negated;
886 
887  assert(bdvars[v] != NULL);
888  negated = FALSE;
889 
890  /* if variable is fixed, nothing to do */
891  if( varIsFixed(scip, bdvars[v], globalbounds ? SCIPvarGetLbGlobal(bdvars[v]) : SCIPvarGetLbLocal(bdvars[v]),
892  globalbounds) )
893  {
894  continue;
895  }
896 
897  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
898  probindex = SCIPvarGetProbindex(bdvars[v]);
899  if( probindex == -1 )
900  {
901  SCIP_VAR* repvar;
902 
903  /* get binary representative of variable */
904  SCIP_CALL( SCIPgetBinvarRepresentative(scip, bdvars[v], &repvar, &negated) );
905  assert(repvar != NULL);
906  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
907 
908  if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
909  {
910  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(bdvars[v]));
911  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(bdcons));
912  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
913  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
914  goto TERMINATE;
915  }
916 
917  /* check for negation */
918  if( SCIPvarIsNegated(repvar) )
919  {
920  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
921  negated = TRUE;
922  }
923  else
924  {
925  assert(SCIPvarIsActive(repvar));
926  probindex = SCIPvarGetProbindex(repvar);
927  negated = FALSE;
928  }
929  }
930  assert(probindex >= 0);
931 
932  /* add covering variable for unfixed original variable */
933  if( negated )
934  {
935  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
936  }
937  else
938  coveringconsvars[ntofix] = coveringvars[probindex];
939  coveringconsvals[ntofix] = 1.0;
940  ntofix++;
941  }
942 
943  /* if less than two variables are unfixed, the entire constraint can be linearized anyway */
944  if( ntofix >= 2 )
945  {
946  assert(ntofix <= nbdvars);
947 
948  /* create covering constraint */
949  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(bdcons));
950  SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals,
951  (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip),
952  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
953 
954  if( coveringcons == NULL )
955  {
956  SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
957  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
958  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
959  goto TERMINATE;
960  }
961 
962  /* add and release covering constraint */
963  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
964  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
965 
966  /* update counters */
967  for( v = ntofix-1; v >= 0; v-- )
968  if( SCIPvarIsNegated(coveringconsvars[v]) )
969  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v])));
970  else
971  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v]));
972  }
973 
974  /* free memory for covering constraint */
975  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
976  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
977  }
978  }
979 
980  /* go through all indicator constraints in the original problem; fix the binary variable */
981  conshdlr = SCIPfindConshdlr(scip, "indicator");
982  if( conshdlr != NULL )
983  {
984  int c;
985 
986  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
987  {
988  SCIP_CONS* indcons;
989  SCIP_VAR* binvar;
990  SCIP_VAR* coveringvar;
991 
992  /* get constraint and variables */
993  indcons = SCIPconshdlrGetConss(conshdlr)[c];
994  assert(indcons != NULL);
995  binvar = SCIPgetBinaryVarIndicator(indcons);
996  assert(binvar != NULL);
997 
998  /* indicator constraints are not passed to the NLP, hence nothing to store in the hash map */
999 
1000  /* if variable is fixed, nothing to do */
1001  if( varIsFixed(scip, binvar, globalbounds ? SCIPvarGetLbGlobal(binvar) : SCIPvarGetLbLocal(binvar), globalbounds) )
1002  {
1003  continue;
1004  }
1005 
1006  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
1007  probindex = SCIPvarGetProbindex(binvar);
1008  if( probindex == -1 )
1009  {
1010  SCIP_VAR* repvar;
1011  SCIP_Bool negated;
1012 
1013  /* get binary representative of variable */
1014  negated = FALSE;
1015  SCIP_CALL( SCIPgetBinvarRepresentative(scip, binvar, &repvar, &negated) );
1016  assert(repvar != NULL);
1017  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
1018 
1019  if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
1020  {
1021  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(binvar));
1022  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(indcons));
1023  goto TERMINATE;
1024  }
1025 
1026  /* check for negation */
1027  if( SCIPvarIsNegated(repvar) )
1028  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
1029  else
1030  {
1031  assert(SCIPvarIsActive(repvar));
1032  probindex = SCIPvarGetProbindex(repvar);
1033  }
1034  }
1035  assert(probindex >= 0);
1036 
1037  /* get covering variable for unfixed binary variable in indicator constraint */
1038  coveringvar = coveringvars[probindex];
1039 
1040  /* require covering variable to be fixed such that indicator is linearized */
1041  SCIP_CALL( SCIPchgVarLb(coveringscip, coveringvar, 1.0) );
1042 
1043  /* update counters */
1044  BMSclearMemoryArray(consmarker, nvars);
1045  incCounters(termcounter, conscounter, consmarker, probindex);
1046  }
1047  }
1048 
1049  /* go through all quadratic constraints in the original problem */
1050  conshdlr = SCIPfindConshdlr(scip, "quadratic");
1051  if( conshdlr != NULL )
1052  {
1053  int c;
1054 
1055  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
1056  {
1057  SCIP_CONS* quadcons;
1058  SCIP_NLROW* nlrow;
1059 
1060  /* get constraint */
1061  quadcons = SCIPconshdlrGetConss(conshdlr)[c];
1062  assert(quadcons != NULL);
1063 
1064  /* get nlrow representation and store it in hash map */
1065  SCIP_CALL( SCIPgetNlRowQuadratic(scip, quadcons, &nlrow) );
1066  assert(nlrow != NULL);
1067  if( nlrowmap != NULL )
1068  {
1069  assert(!SCIPhashmapExists(nlrowmap, nlrow));
1070  SCIP_CALL( SCIPhashmapInsert(nlrowmap, nlrow, quadcons) );
1071  }
1072 
1073  /* if we only want to convexify and curvature and bounds prove already convexity, nothing to do */
1074  if( onlyconvexify
1075  && ((SCIPisInfinity(scip, -SCIPgetLhsQuadratic(scip, quadcons)) && SCIPisConvexQuadratic(scip, quadcons))
1076  || (SCIPisInfinity(scip, SCIPgetRhsQuadratic(scip, quadcons)) && SCIPisConcaveQuadratic(scip, quadcons))) )
1077  continue;
1078 
1079  /* process nlrow */
1080  *success = FALSE;
1081  SCIP_CALL( processNlRow(scip, nlrow, exprint, &hessiandata, coveringscip, nvars, coveringvars,
1082  termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1083 
1084  if( *success == FALSE )
1085  goto TERMINATE;
1086  }
1087 
1088  *success = FALSE;
1089  }
1090 
1091  /* go through all "soc" constraints in the original problem */
1092  conshdlr = SCIPfindConshdlr(scip, "soc");
1093  if( conshdlr != NULL && !onlyconvexify )
1094  {
1095  int c;
1096 
1097  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
1098  {
1099  SCIP_CONS* soccons;
1100  SCIP_CONS* coveringcons;
1101  SCIP_VAR** soclhsvars;
1102  SCIP_VAR* socrhsvar;
1103  SCIP_VAR** coveringconsvars;
1104  SCIP_NLROW* nlrow;
1105 
1106  int ntofix;
1107  int v;
1108 
1109  /* get constraints and variables */
1110  soccons = SCIPconshdlrGetConss(conshdlr)[c];
1111  assert(soccons != NULL);
1112  socrhsvar = SCIPgetRhsVarSOC(scip, soccons);
1113  assert(socrhsvar != NULL);
1114  soclhsvars = SCIPgetLhsVarsSOC(scip, soccons);
1115  assert(soclhsvars != NULL);
1116 
1117  /* get nlrow representation and store it in hash map */
1118  SCIP_CALL( SCIPgetNlRowSOC(scip, soccons, &nlrow) );
1119  assert(nlrow != NULL);
1120  if( nlrowmap != NULL )
1121  {
1122  assert(!SCIPhashmapExists(nlrowmap, nlrow));
1123  SCIP_CALL( SCIPhashmapInsert(nlrowmap, nlrow, soccons) );
1124  }
1125 
1126  /* allocate memory for covering constraint */
1127  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, SCIPgetNLhsVarsSOC(scip, soccons)+1) );
1128 
1129  /* collect unfixed variables */
1130  BMSclearMemoryArray(consmarker, nvars);
1131  ntofix = 0;
1132 
1133  /* soc constraints should contain only active and multi-aggregated variables; the latter we do not handle */
1134  probindex = SCIPvarGetProbindex(socrhsvar);
1135  if( probindex == -1 )
1136  {
1137  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(soccons));
1138  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1139  goto TERMINATE;
1140  }
1141 
1142  /* add covering variable for unfixed rhs variable */
1143  if( !termIsConstant(scip, socrhsvar, SCIPgetRhsCoefSOC(scip, soccons), globalbounds) )
1144  {
1145  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
1146  ntofix++;
1147  }
1148 
1149  /* go through lhs variables */
1150  for( v = SCIPgetNLhsVarsSOC(scip, soccons)-1; v >= 0; v-- )
1151  {
1152  assert(soclhsvars[v] != NULL);
1153 
1154  /* soc constraints should contain only active and multi-aggregated variables; the latter we do not handle */
1155  probindex = SCIPvarGetProbindex(soclhsvars[v]);
1156  if( probindex == -1 )
1157  {
1158  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(soccons));
1159  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1160  goto TERMINATE;
1161  }
1162 
1163  /* add covering variable for unfixed lhs variable */
1164  if( !termIsConstant(scip, soclhsvars[v], SCIPgetLhsCoefsSOC(scip, soccons)[v], globalbounds) )
1165  {
1166  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
1167  ntofix++;
1168  }
1169  }
1170 
1171  if( ntofix >= 2 )
1172  {
1173  /* create covering constraint */
1174  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(soccons));
1175  SCIP_CALL( SCIPcreateConsSetpack(coveringscip, &coveringcons, name, ntofix, coveringconsvars,
1176  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1177 
1178  if( coveringcons == NULL )
1179  {
1180  SCIPdebugMsg(scip, "failed to create set packing constraint <%s>\n", name);
1181  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1182  goto TERMINATE;
1183  }
1184 
1185  /* add and release covering constraint */
1186  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
1187  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
1188 
1189  /* update counters */
1190  for( v = ntofix-1; v >= 0; v-- )
1191  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegatedVar(coveringconsvars[v])));
1192  }
1193 
1194  /* free memory for covering constraint */
1195  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1196  }
1197  }
1198 
1199  /* go through all yet unprocessed nlrows */
1200  if( nlrowmap != NULL )
1201  {
1202  SCIP_NLROW** nlrows;
1203  int nnlrows;
1204 
1205  assert(SCIPisNLPConstructed(scip));
1206 
1207  /* get nlrows */
1208  nnlrows = SCIPgetNNLPNlRows(scip);
1209  nlrows = SCIPgetNLPNlRows(scip);
1210 
1211  for( i = nnlrows-1; i >= 0; i-- )
1212  {
1213  assert(nlrows[i] != NULL);
1214 
1215  /* nlrow or corresponding constraint already processed */
1216  if( SCIPhashmapExists(nlrowmap, nlrows[i]) )
1217  continue;
1218 
1219  /* process nlrow */
1220  *success = FALSE;
1221  SCIP_CALL( processNlRow(scip, nlrows[i], exprint, &hessiandata, coveringscip, nvars, coveringvars,
1222  termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1223 
1224  if( *success == FALSE )
1225  goto TERMINATE;
1226  }
1227  }
1228 
1229  /* set objective function of covering problem */
1230  switch( coveringobj )
1231  {
1232  case 'c': /* number of influenced nonlinear constraints */
1233  for( i = nvars-1; i >= 0; i-- )
1234  {
1235  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) conscounter[i]) );
1236  }
1237  break;
1238  case 'd': /* domain size */
1239  for( i = nvars-1; i >= 0; i-- )
1240  {
1241  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i],
1242  (globalbounds ? SCIPvarGetUbGlobal(vars[i]) - SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbLocal(vars[i]) - SCIPvarGetLbLocal(vars[i]))) );
1243  }
1244  break;
1245  case 'l': /* number of locks */
1246  for( i = nvars-1; i >= 0; i-- )
1247  {
1248  nlocksup = SCIPvarGetNLocksUp(vars[i]);
1249  nlocksdown = SCIPvarGetNLocksDown(vars[i]);
1250  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (nlocksup+nlocksdown+1)) );
1251  }
1252  break;
1253  case 'm': /* min(up locks, down locks)+1 */
1254  for( i = nvars-1; i >= 0; i-- )
1255  {
1256  nlocksup = SCIPvarGetNLocksUp(vars[i]);
1257  nlocksdown = SCIPvarGetNLocksDown(vars[i]);
1258  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (MIN(nlocksup, nlocksdown)+1)) );
1259  }
1260  break;
1261  case 't': /* number of influenced nonlinear terms */
1262  for( i = nvars-1; i >= 0; i-- )
1263  {
1264  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) termcounter[i]) );
1265  }
1266  break;
1267  case 'u': /* unit penalties */
1268  for( i = nvars-1; i >= 0; i-- )
1269  {
1270  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], 1.0) );
1271  }
1272  break;
1273  default:
1274  SCIPerrorMessage("invalid choice <%c> for covering objective\n", coveringobj);
1275  goto TERMINATE;
1276  }
1277 
1278  /* covering problem successfully set up */
1279  *success = TRUE;
1280 
1281  TERMINATE:
1282  /* free nlrow hash map */
1283  if( nlrowmap != NULL )
1284  {
1285  SCIPhashmapFree(&nlrowmap);
1286  }
1287 
1288  /* free hessian data */
1289  if( hessiandata.nvars > 0 )
1290  {
1291  assert(hessiandata.evalsol != NULL);
1292  assert(hessiandata.varvals != NULL);
1293  assert(hessiandata.sparsity != NULL);
1294 
1295  SCIPfreeBufferArray(scip, &hessiandata.sparsity);
1296  SCIPfreeBufferArray(scip, &hessiandata.varvals);
1297 
1298  SCIP_CALL( SCIPfreeSol(scip, &hessiandata.evalsol) );
1299  }
1300  else
1301  {
1302  assert(hessiandata.evalsol == NULL);
1303  assert(hessiandata.varvals == NULL);
1304  assert(hessiandata.sparsity == NULL);
1305  }
1306 
1307  /* free expression interpreter */
1308  SCIP_CALL( SCIPexprintFree(&exprint) );
1309 
1310  SCIPstatistic(
1311  {
1312  int nnonzs;
1313  nnonzs = 0;
1314  for( i = 0; i < nvars; ++i)
1315  nnonzs += termcounter[i];
1316  SCIPstatisticPrintf("UCstats nnz/var: %9.6f\n", nnonzs/(SCIP_Real)nvars);
1317  nnonzs = 0;
1318  for( i = 0; i < nvars; ++i)
1319  if( conscounter[i] > 0 )
1320  nnonzs++;
1321  SCIPstatisticPrintf("UCstats nlvars: %6d\n", nnonzs);
1322  }
1323  );
1324 
1325  /* free counter arrays for weighted objectives */
1326  SCIPfreeBufferArray(scip, &termcounter);
1327  SCIPfreeBufferArray(scip, &conscounter);
1328  SCIPfreeBufferArray(scip, &consmarker);
1329 
1330  return SCIP_OKAY;
1331 }
1332 
1333 
1334 /** adds a constraint to the covering problem to forbid the given cover */
1335 static
1336 SCIP_RETCODE forbidCover(
1337  SCIP* scip, /**< SCIP data structure of the covering problem */
1338  int nvars, /**< number of variables */
1339  SCIP_VAR** vars, /**< variable array */
1340  int coversize, /**< size of the cover */
1341  int* cover, /**< problem indices of the variables in the cover */
1342  int diversification, /**< how many unfixed variables have to change their value? */
1343  SCIP_Bool* success, /**< pointer to store whether the cutoff constraint was created successfully */
1344  SCIP_Bool* infeas /**< pointer to store whether the cutoff proves (local or global) infeasibility */
1345  )
1346 {
1347  SCIP_CONS* cons;
1348  SCIP_VAR** consvars;
1349 
1350  char name[SCIP_MAXSTRLEN];
1351  int nconsvars;
1352  int i;
1353 
1354  assert(scip != NULL);
1355  assert(vars != NULL);
1356  assert(nvars >= 1);
1357  assert(cover != NULL);
1358  assert(coversize >= 1);
1359  assert(coversize <= nvars);
1360  assert(diversification >= 1);
1361  assert(success != NULL);
1362  assert(infeas != NULL);
1363 
1364  *success = FALSE;
1365  *infeas = FALSE;
1366 
1367  /* allocate memory for constraint variables */
1368  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, coversize) );
1369  nconsvars = 0;
1370  cons = NULL;
1371 
1372  /* create constraint name */
1373  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "forbid_cover_assignment");
1374 
1375  /* if all variables in the cover are binary and we require only one variable to change its value, then we create a
1376  * set covering constraint
1377  */
1378  if( diversification == 1 )
1379  {
1380  /* build up constraint */
1381  for( i = coversize-1; i >= 0; i-- )
1382  {
1383  if( !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1384  {
1385  SCIP_CALL( SCIPgetNegatedVar(scip, vars[cover[i]], &consvars[nconsvars]) );
1386  nconsvars++;
1387  }
1388  }
1389 
1390  /* if all covering variables are fixed to one, the constraint cannot be satisfied */
1391  if( nconsvars == 0 )
1392  {
1393  *infeas = TRUE;
1394  }
1395  else
1396  {
1397  /* create constraint */
1398  SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars,
1399  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1400  }
1401  }
1402  /* if all variables in the cover are binary and we require more variables to change their value, then we create a
1403  * linear constraint
1404  */
1405  else
1406  {
1407  SCIP_Real* consvals;
1408  SCIP_Real rhs;
1409 
1410  /* build up constraint */
1411  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, coversize) );
1412  for( i = coversize-1; i >= 0; i-- )
1413  {
1414  if( !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1415  {
1416  consvars[nconsvars] = vars[cover[i]];
1417  consvals[nconsvars] = 1.0;
1418  nconsvars++;
1419  }
1420  }
1421  rhs = (SCIP_Real) (nconsvars-diversification);
1422 
1423  /* if too many covering variables are fixed to 1, the constraint cannot be satisfied */
1424  if( rhs < 0 )
1425  {
1426  *infeas = TRUE;
1427  }
1428  else
1429  {
1430  /* create constraint */
1431  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name,
1432  nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs,
1433  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1434  }
1435 
1436  /* free memory */
1437  SCIPfreeBufferArray(scip, &consvals);
1438  }
1439 
1440  /* free memory */
1441  SCIPfreeBufferArray(scip, &consvars);
1442 
1443  /* if proven infeasible, we do not even add the constraint; otherwise we add and release the constraint if created
1444  * successfully
1445  */
1446  if( !(*infeas) && cons != NULL )
1447  {
1448  SCIP_CALL( SCIPaddCons(scip, cons) );
1449  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1450  *success = TRUE;
1451  }
1452 
1453  return SCIP_OKAY;
1454 }
1455 
1456 
1457 /** adds a set covering or bound disjunction constraint to the original problem */
1458 static
1459 SCIP_RETCODE createConflict(
1460  SCIP* scip, /**< SCIP data structure */
1461  int bdlen, /**< length of bound disjunction */
1462  SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
1463  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
1464  SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
1465  SCIP_Bool local, /**< is constraint valid only locally? */
1466  SCIP_Bool dynamic, /**< is constraint subject to aging? */
1467  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
1468  SCIP_Bool* success /**< pointer to store whether the cutoff constraint was created successfully */
1469  )
1470 {
1471  SCIP_CONS* cons;
1472  SCIP_VAR** consvars;
1473  SCIP_Bool isbinary;
1474  char name[SCIP_MAXSTRLEN];
1475  int i;
1476 
1477  assert(scip != NULL);
1478  assert(bdlen >= 1);
1479  assert(bdvars != NULL);
1480  assert(bdtypes != NULL);
1481  assert(bdbounds != NULL);
1482  assert(success != NULL);
1483 
1484  /* initialize */
1485  *success = FALSE;
1486  cons = NULL;
1487  consvars = NULL;
1488 
1489  /* create constraint name */
1490  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "undercover_cutoff");
1491 
1492  /* check if all variables in the cover are binary */
1493  isbinary = TRUE;
1494  for( i = bdlen-1; i >= 0 && isbinary; i-- )
1495  {
1496  isbinary = SCIPvarIsBinary(bdvars[i]);
1497  }
1498 
1499  /* if all variables in the cover are binary, then we create a logicor constraint */
1500  if( isbinary )
1501  {
1502  /* allocate memory for constraint variables */
1503  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, bdlen) );
1504 
1505  /* build up constraint */
1506  for( i = bdlen-1; i >= 0; i-- )
1507  {
1508  assert(bdtypes[i] == SCIP_BOUNDTYPE_LOWER || SCIPisFeasZero(scip, bdbounds[i]));
1509  assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER || SCIPisFeasEQ(scip, bdbounds[i], 1.0));
1510 
1511  if( bdtypes[i] == SCIP_BOUNDTYPE_LOWER )
1512  {
1513  consvars[i] = bdvars[i];
1514  }
1515  else
1516  {
1517  assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER);
1518  SCIP_CALL( SCIPgetNegatedVar(scip, bdvars[i], &consvars[i]) );
1519  }
1520  }
1521 
1522  /* create conflict constraint */
1523  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, bdlen, consvars,
1524  FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1525  }
1526  /* otherwise we create a bound disjunction constraint as given */
1527  else
1528  {
1529  /* create conflict constraint */
1530  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, bdlen, bdvars, bdtypes, bdbounds,
1531  FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1532  }
1533 
1534  /* add and release constraint if created successfully */
1535  if( cons != NULL )
1536  {
1537  if( local )
1538  {
1539  SCIP_CALL( SCIPaddConsLocal(scip, cons, NULL) );
1540  }
1541  else
1542  {
1543  SCIP_CALL( SCIPaddCons(scip, cons) );
1544  }
1545 
1546  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1547  *success = TRUE;
1548  }
1549 
1550  /* free memory */
1551  SCIPfreeBufferArrayNull(scip, &consvars);
1552 
1553  return SCIP_OKAY;
1554 }
1555 
1556 
1557 /** solve covering problem */
1558 static
1559 SCIP_RETCODE solveCoveringProblem(
1560  SCIP* coveringscip, /**< SCIP data structure for the covering problem */
1561  int ncoveringvars, /**< number of the covering problem's variables */
1562  SCIP_VAR** coveringvars, /**< array of the covering problem's variables */
1563  int* coversize, /**< size of the computed cover */
1564  int* cover, /**< array to store indices of the variables in the computed cover
1565  * (should be ready to hold ncoveringvars entries) */
1566  SCIP_Real timelimit, /**< time limit */
1567  SCIP_Real memorylimit, /**< memory limit */
1568  SCIP_Real objlimit, /**< upper bound on the cover size */
1569  SCIP_Bool* success /**< feasible cover found? */
1570  )
1571 {
1572  SCIP_Real* solvals;
1573  SCIP_Real totalpenalty;
1574  SCIP_RETCODE retcode;
1575  int i;
1576 
1577  assert(coveringscip != NULL);
1578  assert(coveringvars != NULL);
1579  assert(cover != NULL);
1580  assert(coversize != NULL);
1581  assert(timelimit > 0.0);
1582  assert(memorylimit > 0.0);
1583  assert(success != NULL);
1584 
1585  *success = FALSE;
1586 
1587  /* forbid call of heuristics and separators solving sub-CIPs */
1588  SCIP_CALL( SCIPsetSubscipsOff(coveringscip, TRUE) );
1589 
1590  /* set presolving and separation to fast */
1591  SCIP_CALL( SCIPsetSeparating(coveringscip, SCIP_PARAMSETTING_FAST, TRUE) );
1592  SCIP_CALL( SCIPsetPresolving(coveringscip, SCIP_PARAMSETTING_FAST, TRUE) );
1593 
1594  /* use inference branching */
1595  if( SCIPfindBranchrule(coveringscip, "inference") != NULL && !SCIPisParamFixed(coveringscip, "branching/inference/priority") )
1596  {
1597  SCIP_CALL( SCIPsetIntParam(coveringscip, "branching/inference/priority", INT_MAX/4) );
1598  }
1599 
1600  /* only solve root */
1601  SCIP_CALL( SCIPsetLongintParam(coveringscip, "limits/nodes", 1LL) );
1602 
1603  SCIPdebugMsg(coveringscip, "timelimit = %g, memlimit = %g\n", timelimit, memorylimit);
1604 
1605  /* set time, memory, and objective limit */
1606  SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/time", timelimit) );
1607  SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/memory", memorylimit) );
1608  SCIP_CALL( SCIPsetObjlimit(coveringscip, objlimit) );
1609 
1610  /* do not abort on CTRL-C */
1611  SCIP_CALL( SCIPsetBoolParam(coveringscip, "misc/catchctrlc", FALSE) );
1612 
1613  /* disable output to console in optimized mode, enable in SCIP's debug mode */
1614 #ifdef SCIP_DEBUG
1615  SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 5) );
1616  SCIP_CALL( SCIPsetIntParam(coveringscip, "display/freq", 100000) );
1617 #else
1618  SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 0) );
1619 #endif
1620 
1621 
1622  /* solve covering problem */
1623  retcode = SCIPsolve(coveringscip);
1624 
1625  /* errors in solving the covering problem should not kill the overall solving process;
1626  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1627  */
1628  if( retcode != SCIP_OKAY )
1629  {
1630 #ifndef NDEBUG
1631  SCIP_CALL( retcode );
1632 #endif
1633  SCIPwarningMessage(coveringscip, "Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1634  return SCIP_OKAY;
1635  }
1636 
1637  /* check, whether a feasible cover was found */
1638  if( SCIPgetNSols(coveringscip) == 0 )
1639  return SCIP_OKAY;
1640 
1641  /* store solution */
1642  SCIP_CALL( SCIPallocBufferArray(coveringscip, &solvals, ncoveringvars) );
1643  SCIP_CALL( SCIPgetSolVals(coveringscip, SCIPgetBestSol(coveringscip), ncoveringvars, coveringvars, solvals) );
1644 
1645  *coversize = 0;
1646  totalpenalty = 0.0;
1647  for( i = 0; i < ncoveringvars; i++ )
1648  {
1649  if( solvals[i] > 0.5 )
1650  {
1651  cover[*coversize] = i;
1652  (*coversize)++;
1653  }
1654  totalpenalty += SCIPvarGetObj(coveringvars[i]);
1655  }
1656 
1657  /* print solution if we are in SCIP's debug mode */
1658  assert(SCIPgetBestSol(coveringscip) != NULL);
1659  SCIPdebugMsg(coveringscip, "found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n",
1660  *coversize, SCIPgetNOrigVars(coveringscip), SCIPgetSolOrigObj(coveringscip, SCIPgetBestSol(coveringscip))/(totalpenalty+SCIPsumepsilon(coveringscip)));
1661  SCIPdebug( SCIP_CALL( SCIPprintSol(coveringscip, SCIPgetBestSol(coveringscip), NULL, FALSE) ) );
1662  SCIPdebugMsg(coveringscip, "\r \n");
1663 
1664  *success = TRUE;
1665 
1666  /* free array of solution values */
1667  SCIPfreeBufferArray(coveringscip, &solvals);
1668 
1669  return SCIP_OKAY;
1670 }
1671 
1672 
1673 /** computes fixing order and returns whether order has really been changed */
1674 static
1675 SCIP_RETCODE computeFixingOrder(
1676  SCIP* scip, /**< original SCIP data structure */
1677  SCIP_HEURDATA* heurdata, /**< heuristic data */
1678  int nvars, /**< number of variables in the original problem */
1679  SCIP_VAR** vars, /**< variables in the original problem */
1680  int coversize, /**< size of the cover */
1681  int* cover, /**< problem indices of the variables in the cover */
1682  int lastfailed, /**< position in cover array of the variable the fixing of which yielded
1683  * infeasibility in last dive (or >= coversize, in which case *success
1684  * is always TRUE) */
1685  SCIP_Bool* success /**< has order really been changed? */
1686  )
1687 {
1688  SCIP_Real* scores;
1689  SCIP_Real bestscore;
1690  SCIP_Bool sortdown;
1691  int i;
1692 
1693  assert(scip != NULL);
1694  assert(heurdata != NULL);
1695  assert(nvars >= 1);
1696  assert(vars != NULL);
1697  assert(coversize >= 1);
1698  assert(cover != NULL);
1699  assert(lastfailed >= 0);
1700 
1701  *success = FALSE;
1702 
1703  /* if fixing the first variable had failed, do not try with another order */
1704  if( lastfailed == 0 )
1705  return SCIP_OKAY;
1706 
1707  /* allocate buffer array for score values */
1708  SCIP_CALL( SCIPallocBufferArray(scip, &scores, coversize) );
1709 
1710  /* initialize best score to infinite value */
1711  sortdown = (heurdata->fixingorder == 'c' || heurdata->fixingorder == 'v' );
1712  bestscore = sortdown ? -SCIPinfinity(scip) : +SCIPinfinity(scip);
1713 
1714  /* compute score values */
1715  for( i = coversize-1; i >= 0; i-- )
1716  {
1717  SCIP_VAR* var;
1718 
1719  /* get variable in the cover */
1720  assert(cover[i] >= 0);
1721  assert(cover[i] < nvars);
1722  var = vars[cover[i]];
1723 
1724  if( heurdata->fixingorder == 'C' || heurdata->fixingorder == 'c' )
1725  {
1726  /* add a small pertubation value to the score to reduce performance variability */
1727  scores[i] = heurdata->conflictweight * SCIPgetVarConflictScore(scip, var)
1728  + heurdata->inferenceweight * SCIPgetVarAvgInferenceCutoffScore(scip, var, heurdata->cutoffweight)
1729  + SCIPrandomGetReal(heurdata->randnumgen, 0.0, SCIPepsilon(scip));
1730  }
1731  else if( heurdata->fixingorder == 'V' || heurdata->fixingorder == 'v' )
1732  scores[i] = cover[i];
1733  else
1734  return SCIP_PARAMETERWRONGVAL;
1735 
1736  assert(scores[i] >= 0.0);
1737 
1738  /* update best score */
1739  if( sortdown )
1740  bestscore = MAX(bestscore, scores[i]);
1741  else
1742  bestscore = MIN(bestscore, scores[i]);
1743 
1744  }
1745 
1746  /* put integers to the front */
1747  if( heurdata->fixintfirst )
1748  {
1749  for( i = coversize-1; i >= 0; i-- )
1750  {
1751  if( SCIPvarIsIntegral(vars[cover[i]]) )
1752  {
1753  if( sortdown )
1754  scores[i] += bestscore+1.0;
1755  else
1756  scores[i] = bestscore - 1.0/(scores[i]+1.0);
1757  }
1758  }
1759  }
1760 
1761  /* put last failed variable to the front */
1762  if( lastfailed < coversize )
1763  {
1764  if( sortdown )
1765  scores[lastfailed] += bestscore+2.0;
1766  else
1767  scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0);
1768  i = cover[lastfailed];
1769  }
1770 
1771  /* sort by non-decreasing (negative) score */
1772  if( sortdown )
1773  SCIPsortDownRealInt(scores, cover, coversize);
1774  else
1775  SCIPsortRealInt(scores, cover, coversize);
1776 
1777  assert(lastfailed >= coversize || cover[0] == i);
1778 
1779  /* free buffer memory */
1780  SCIPfreeBufferArray(scip, &scores);
1781 
1782  *success = TRUE;
1783 
1784  return SCIP_OKAY;
1785 }
1786 
1787 
1788 /** gets fixing value */
1789 static
1790 SCIP_RETCODE getFixingValue(
1791  SCIP* scip, /**< original SCIP data structure */
1792  SCIP_HEURDATA* heurdata, /**< heuristic data */
1793  SCIP_VAR* var, /**< variable in the original problem */
1794  SCIP_Real* val, /**< buffer for returning fixing value */
1795  char fixalt, /**< source of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
1796  SCIP_Bool* success, /**< could value be retrieved successfully? */
1797  int bdlen, /**< current length of probing path */
1798  SCIP_VAR** bdvars, /**< array of variables with bound changes along probing path */
1799  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
1800  SCIP_Real* oldbounds /**< array of bounds before fixing */
1801  )
1802 {
1803  assert(scip != NULL);
1804  assert(heurdata != NULL);
1805  assert(var != NULL);
1806  assert(val != NULL);
1807  assert(success != NULL);
1808 
1809  *success = FALSE;
1810 
1811  switch( fixalt )
1812  {
1813  case 'l':
1814  /* get the last LP solution value */
1815  *val = SCIPvarGetLPSol(var);
1816  *success = TRUE;
1817  break;
1818  case 'n':
1819  /* only call this function if NLP relaxation is available */
1820  assert(SCIPisNLPConstructed(scip));
1821 
1822  /* the solution values are already available */
1823  if( heurdata->nlpsolved )
1824  {
1825  assert(!heurdata->nlpfailed);
1826 
1827  /* retrieve NLP solution value */
1828  *val = SCIPvarGetNLPSol(var);
1829  *success = TRUE;
1830  }
1831  /* solve NLP relaxation unless it has not failed too often before */
1832  else if( !heurdata->nlpfailed )
1833  { /*lint --e{850}*/
1834  SCIP_NLPSOLSTAT stat;
1835  int i;
1836 
1837  /* restore bounds at start of probing, since otherwise, if in backtrack mode, NLP solver becomes most likely
1838  * locally infeasible
1839  */
1840  SCIP_CALL( SCIPstartDiveNLP(scip) );
1841 
1842  for( i = bdlen-1; i >= 0; i-- )
1843  {
1844  SCIP_VAR* relaxvar;
1845  SCIP_Real lb;
1846  SCIP_Real ub;
1847 
1848  relaxvar = bdvars[i];
1849 
1850  /* both bounds were tightened */
1851  if( i > 0 && bdvars[i-1] == relaxvar )
1852  {
1853  assert(bdtypes[i] != bdtypes[i-1]);
1854 
1855  lb = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i] : oldbounds[i-1];
1856  ub = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i-1] : oldbounds[i];
1857  i--;
1858  }
1859  /* lower bound was tightened */
1860  else if( bdtypes[i] == SCIP_BOUNDTYPE_UPPER )
1861  {
1862  lb = oldbounds[i];
1863  ub = SCIPvarGetUbLocal(relaxvar);
1864  }
1865  /* upper bound was tightened */
1866  else
1867  {
1868  lb = SCIPvarGetLbLocal(relaxvar);
1869  ub = oldbounds[i];
1870  }
1871 
1872  assert(SCIPisLE(scip, lb, SCIPvarGetLbLocal(relaxvar)));
1873  assert(SCIPisGE(scip, ub, SCIPvarGetUbLocal(relaxvar)));
1874 
1875  /* relax bounds */
1876  SCIP_CALL( SCIPchgVarBoundsDiveNLP(scip, relaxvar, lb, ub) );
1877  }
1878 
1879  /* activate NLP solver output if we are in SCIP's debug mode */
1880  SCIPdebug( SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_VERBLEVEL, 1) ) );
1881 
1882  /* set starting point to lp solution */
1883  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
1884 
1885  /* solve NLP relaxation */
1886  SCIP_CALL( SCIPsolveDiveNLP(scip) );
1887  stat = SCIPgetNLPSolstat(scip);
1888  *success = stat == SCIP_NLPSOLSTAT_GLOBOPT || stat == SCIP_NLPSOLSTAT_LOCOPT || stat == SCIP_NLPSOLSTAT_FEASIBLE;
1889 
1890  SCIPdebugMsg(scip, "solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ? "successful" : "failed", stat);
1891 
1892  if( *success )
1893  {
1894  /* solving succeeded */
1895  heurdata->nnlpfails = 0;
1896  heurdata->nlpsolved = TRUE;
1897 
1898  /* retrieve NLP solution value */
1899  *val = SCIPvarGetNLPSol(var);
1900  }
1901  else
1902  {
1903  /* solving failed */
1904  heurdata->nnlpfails++;
1905  heurdata->nlpfailed = TRUE;
1906  heurdata->nlpsolved = FALSE;
1907 
1908  SCIPdebugMsg(scip, "solving NLP relaxation failed (%d time%s%s)\n",
1909  heurdata->nnlpfails, heurdata->nnlpfails > 1 ? "s" : "", heurdata->nnlpfails >= MAXNLPFAILS ? ", will not be called again" : "");
1910  }
1911  }
1912  break;
1913  case 'i':
1914  /* only call this function if a feasible solution is available */
1915  assert(SCIPgetBestSol(scip) != NULL);
1916 
1917  /* get value in the incumbent solution */
1918  *val = SCIPgetSolVal(scip, SCIPgetBestSol(scip), var);
1919  *success = TRUE;
1920  break;
1921  default:
1922  break;
1923  }
1924 
1925  return SCIP_OKAY;
1926 }
1927 
1928 
1929 /** calculates up to four alternative values for backtracking, if fixing the variable failed.
1930  * The alternatives are the two bounds of the variable, and the averages of the bounds and the fixing value.
1931  * For infinite bounds, fixval +/- abs(fixval) will be used instead.
1932  */
1933 static
1934 void calculateAlternatives(
1935  SCIP* scip, /**< original SCIP data structure */
1936  SCIP_VAR* var, /**< variable to calculate alternatives for */
1937  SCIP_Real fixval, /**< reference fixing value */
1938  int* nalternatives, /**< number of fixing values computed */
1939  SCIP_Real* alternatives /**< array to store the alternative fixing values */
1940  )
1941 {
1942  SCIP_Real lb;
1943  SCIP_Real ub;
1944 
1945  /* for binary variables, there is only two possible fixing values */
1946  if( SCIPvarIsBinary(var) )
1947  {
1948  if( SCIPisFeasEQ(scip, fixval, 0.0) || SCIPisFeasEQ(scip, fixval, 1.0) )
1949  {
1950  alternatives[0] = 1.0 - fixval;
1951  *nalternatives = 1;
1952  }
1953  else
1954  {
1955  alternatives[0] = 0.0;
1956  alternatives[1] = 1.0;
1957  *nalternatives = 2;
1958  }
1959  return;
1960  }
1961 
1962  /* get bounds */
1963  lb = SCIPvarGetLbLocal(var);
1964  ub = SCIPvarGetUbLocal(var);
1965 
1966  /* if lower bound is infinite, use x'-|x'|; if x' is zero, use -1.0 instead */
1967  if( SCIPisInfinity(scip, -lb) )
1968  lb = SCIPisFeasZero(scip, fixval) ? -1.0 : fixval - ABS(fixval);
1969 
1970  /* if upper bound is infinite, use x'+|x'|; if x' is zero, use 1.0 instead */
1971  if( SCIPisInfinity(scip, ub) )
1972  ub = SCIPisFeasZero(scip, fixval) ? 1.0 : fixval + ABS(fixval);
1973 
1974  assert(!SCIPisEQ(scip, lb, ub));
1975 
1976  /* collect alternatives */
1977  *nalternatives = 0;
1978 
1979  /* use lower bound if not equal to x' */
1980  if( !SCIPisFeasEQ(scip, lb, fixval) )
1981  {
1982  alternatives[*nalternatives] = lb;
1983  (*nalternatives)++;
1984  }
1985 
1986  /* use upper bound if not equal to x' */
1987  if( !SCIPisFeasEQ(scip, ub, fixval) )
1988  {
1989  alternatives[*nalternatives] = ub;
1990  (*nalternatives)++;
1991  }
1992 
1993  /* use the average of x' and lower bound as alternative value, if this is not equal to any of the other values */
1994  if( !SCIPisFeasEQ(scip, lb, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, lb, fixval-1)) )
1995  {
1996  alternatives[*nalternatives] = (lb+fixval)/2.0;
1997  (*nalternatives)++;
1998  }
1999 
2000  /* use the average of x' and upper bound as alternative value, if this is not equal to any of the other values */
2001  if( !SCIPisFeasEQ(scip, ub, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, ub, fixval+1)) )
2002  {
2003  alternatives[*nalternatives] = (ub+fixval)/2.0;
2004  (*nalternatives)++;
2005  }
2006 
2007  assert(*nalternatives <= 4);
2008 
2009  return;
2010 }
2011 
2012 
2013 /** rounds the given fixing value */
2014 static
2015 SCIP_RETCODE roundFixingValue(
2016  SCIP* scip, /**< original SCIP data structure */
2017  SCIP_Real* val, /**< fixing value to be rounded */
2018  SCIP_VAR* var, /**< corresponding variable */
2019  SCIP_Bool locksrounding /**< shall we round according to locks? (otherwise to nearest integer) */
2020  )
2021 {
2022  SCIP_Real x;
2023 
2024  x = *val;
2025 
2026  /* if integral within feasibility tolerance, only shift to nearest integer */
2027  if( SCIPisFeasIntegral(scip, x) )
2028  x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
2029 
2030  /* round in the direction of least locks with fractionality as tie breaker */
2031  else if( locksrounding )
2032  {
2033  if( SCIPvarGetNLocksDown(var) < SCIPvarGetNLocksUp(var) )
2034  x = SCIPfeasFloor(scip, x);
2035  else if( SCIPvarGetNLocksDown(var) > SCIPvarGetNLocksUp(var) )
2036  x = SCIPfeasCeil(scip, x);
2037  else
2038  x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
2039  }
2040  /* round in the direction of least fractionality with locks as tie breaker */
2041  else
2042  {
2043  if( SCIPfeasFrac(scip, x) < 0.5)
2044  x = SCIPfeasFloor(scip, x);
2045  else if( SCIPfeasFrac(scip, x) > 0.5 )
2046  x = SCIPfeasCeil(scip, x);
2047  else
2048  x = SCIPvarGetNLocksDown(var) < SCIPvarGetNLocksUp(var) ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
2049  }
2050 
2051  /* return rounded fixing value */
2052  *val = x;
2053 
2054  return SCIP_OKAY;
2055 }
2056 
2057 
2058 /** copy the solution of the subproblem to newsol */
2059 static
2060 SCIP_RETCODE copySol(
2061  SCIP* scip, /**< original SCIP data structure */
2062  SCIP* subscip, /**< SCIP structure of the subproblem */
2063  SCIP_VAR** subvars, /**< the variables of the subproblem */
2064  SCIP_SOL* subsol, /**< solution of the subproblem */
2065  SCIP_SOL** newsol /**< solution to the original problem */
2066  )
2067 {
2068  SCIP_VAR** vars; /* the original problem's variables */
2069  SCIP_Real* subsolvals; /* solution values of the subproblem */
2070  int nvars;
2071 
2072  assert(scip != NULL);
2073  assert(subscip != NULL);
2074  assert(subvars != NULL);
2075  assert(subsol != NULL);
2076  assert(newsol != NULL);
2077  assert(*newsol != NULL);
2078 
2079  /* get variables' data */
2080  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2081 
2082  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
2083  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
2084  */
2085  assert(nvars <= SCIPgetNOrigVars(subscip));
2086 
2087  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
2088 
2089  /* copy the solution */
2090  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
2091  SCIP_CALL( SCIPsetSolVals(scip, *newsol, nvars, vars, subsolvals) );
2092 
2093  SCIPfreeBufferArray(scip, &subsolvals);
2094 
2095  return SCIP_OKAY;
2096 }
2097 
2098 
2099 /** solve subproblem and pass best feasible solution to original SCIP instance */
2100 static
2101 SCIP_RETCODE solveSubproblem(
2102  SCIP* scip, /**< SCIP data structure of the original problem */
2103  SCIP_HEUR* heur, /**< heuristic data structure */
2104  int coversize, /**< size of the cover */
2105  int* cover, /**< problem indices of the variables in the cover */
2106  SCIP_Real* fixedvals, /**< fixing values for the variables in the cover */
2107  SCIP_Real timelimit, /**< time limit */
2108  SCIP_Real memorylimit, /**< memory limit */
2109  SCIP_Longint nodelimit, /**< node limit */
2110  SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
2111  SCIP_Bool* validsolved, /**< was problem constructed from a valid copy and solved (proven optimal or infeasible)? */
2112  SCIP_SOL** sol, /**< best solution found in subproblem (if feasible); *sol must be NULL, solution will be created */
2113  SCIP_Longint* nusednodes /**< number of nodes used for solving the subproblem */
2114  )
2115 {
2116  SCIP_HEURDATA* heurdata;
2117  SCIP* subscip;
2118  SCIP_VAR** subvars;
2119  SCIP_VAR** vars;
2120  SCIP_HASHMAP* varmap;
2121  SCIP_VAR** fixedvars;
2122  int nfixedvars;
2123 
2124  SCIP_RETCODE retcode;
2125 
2126  int nvars;
2127  int i;
2128 
2129  assert(scip != NULL);
2130  assert(heur != NULL);
2131  assert(cover != NULL);
2132  assert(fixedvals != NULL);
2133  assert(coversize >= 1);
2134  assert(timelimit > 0.0);
2135  assert(memorylimit > 0.0);
2136  assert(nodelimit >= 1);
2137  assert(nstallnodes >= 1);
2138  assert(validsolved != NULL);
2139  assert(sol != NULL);
2140  assert(*sol == NULL);
2141  assert(nusednodes != NULL);
2142 
2143  *validsolved = FALSE;
2144  *nusednodes = 0;
2145 
2146  /* get heuristic data */
2147  heurdata = SCIPheurGetData(heur);
2148  assert(heurdata != NULL);
2149 
2150  /* get required data of the original problem */
2151  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2152 
2153  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, coversize) );
2154  nfixedvars = coversize;
2155  /* fix subproblem variables in the cover */
2156  SCIPdebugMsg(scip, "fixing variables\n");
2157  for( i = coversize-1; i >= 0; i-- )
2158  {
2159  assert(cover[i] >= 0);
2160  assert(cover[i] < nvars);
2161 
2162  fixedvars[i] = vars[cover[i]];
2163  }
2164 
2165  /* create subproblem */
2166  SCIP_CALL( SCIPcreate(&subscip) );
2167  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
2168 
2169  /* create the variable mapping hash map */
2170  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
2171 
2172  /* copy original problem to subproblem; do not copy pricers */
2173  SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", fixedvars, fixedvals, nfixedvars,
2174  heurdata->globalbounds, FALSE, TRUE, validsolved) );
2175 
2176  if( heurdata->copycuts )
2177  {
2178  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
2179  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, heurdata->globalbounds, NULL) );
2180  }
2181 
2182  SCIPdebugMsg(scip, "problem copied, copy %svalid\n", *validsolved ? "" : "in");
2183 
2184  /* store subproblem variables */
2185  for( i = nvars-1; i >= 0; i-- )
2186  {
2187  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
2188  assert(subvars[i] != NULL);
2189  }
2190 
2191  /* free variable mapping hash map */
2192  SCIPhashmapFree(&varmap);
2193 
2194  /* set the parameters such that good solutions are found fast */
2195  SCIPdebugMsg(scip, "setting subproblem parameters\n");
2196  SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
2197  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2198  SCIP_CALL( SCIPsetHeuristics(subscip, SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
2199 
2200  /* deactivate expensive pre-root heuristics, since it may happen that the lp relaxation of the subproblem is already
2201  * infeasible; in this case, we do not want to waste time on heuristics before solving the root lp */
2202  if( !SCIPisParamFixed(subscip, "heuristics/shiftandpropagate/freq") )
2203  {
2204  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shiftandpropagate/freq", -1) );
2205  }
2206 
2207  /* forbid recursive call of undercover heuristic */
2208  if( SCIPisParamFixed(subscip, "heuristics/" HEUR_NAME "/freq") )
2209  {
2210  SCIPwarningMessage(scip, "unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n");
2211  SCIP_CALL( SCIPunfixParam(subscip, "heuristics/" HEUR_NAME "/freq") );
2212  }
2213  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/" HEUR_NAME "/freq", -1) );
2214 
2215  SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
2216 
2217  SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
2218 
2219  /* disable statistic timing inside sub SCIP */
2220  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2221 
2222  /* set time, memory and node limits */
2223  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
2224  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
2225  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
2226  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
2227 
2228  /* do not abort subproblem on CTRL-C */
2229  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2230 
2231  /* disable output to console in optimized mode, enable in SCIP's debug mode */
2232 #ifdef SCIP_DEBUG
2233  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2234  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000) );
2235 #else
2236  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2237 #endif
2238 
2239  /* if there is already a solution, add an objective cutoff; note: this does not affect the validity of the subproblem
2240  * if we find solutions later, thus we do not set *validsolved to FALSE */
2241  if( SCIPgetNSols(scip) > 0 )
2242  {
2243  SCIP_Real cutoff;
2244  SCIP_Real upperbound;
2245 
2246  assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
2247  upperbound = SCIPgetUpperbound(scip);
2248 
2249  if( SCIPisInfinity(scip, -SCIPgetLowerbound(scip)) )
2250  cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound;
2251  else
2252  cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove * SCIPgetLowerbound(scip);
2253 
2254  cutoff = MIN(upperbound, cutoff);
2255  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
2256 
2257  SCIPdebugMsg(scip, "adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove);
2258  }
2259 
2260  /* solve subproblem */
2261  SCIPdebugMsg(scip, "solving subproblem started\n");
2262  retcode = SCIPsolve(subscip);
2263 
2264  /* Errors in solving the subproblem should not kill the overall solving process
2265  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2266  */
2267  if( retcode != SCIP_OKAY )
2268  {
2269 #ifndef NDEBUG
2270  SCIP_CALL( retcode );
2271 #endif
2272  SCIPwarningMessage(scip, "Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
2273  /* free array of subproblem variables, and subproblem */
2274  SCIPfreeBufferArray(scip, &subvars);
2275  SCIPfreeBufferArray(scip, &fixedvars);
2276  SCIP_CALL( SCIPfree(&subscip) );
2277  return SCIP_OKAY;
2278  }
2279 
2280  /* print solving statistics of subproblem if we are in SCIP's debug mode */
2281  SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
2282 
2283  /* store solving status; note: if we proved infeasibility in presence of an objective cutoff beyond the primal bound,
2284  * the subproblem was not a valid copy */
2285  *validsolved = *validsolved && (SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL
2286  || (SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE && (SCIPgetNSols(scip) == 0 || heurdata->minimprove <= 0.0)));
2287  *nusednodes = SCIPgetNNodes(subscip);
2288 
2289  /* if a solution was found for the subproblem, create corresponding solution in the original problem */
2290  if( SCIPgetNSols(subscip) > 0 && (SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE || heurdata->minimprove > 0.0) )
2291  {
2292  SCIP_SOL** subsols;
2293  SCIP_Bool success;
2294  int nsubsols;
2295 
2296  /* create solution */
2297  SCIP_CALL( SCIPcreateSol(scip, sol, heur) );
2298 
2299  /* check, whether a solution was found;
2300  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
2301  nsubsols = SCIPgetNSols(subscip);
2302  subsols = SCIPgetSols(subscip);
2303  assert(subsols != NULL);
2304 
2305  success = FALSE;
2306  for( i = 0; i < nsubsols && !success; i++ )
2307  {
2308  /* transform solution to original problem */
2309  SCIP_CALL( copySol(scip, subscip, subvars, subsols[i], sol) );
2310 
2311  /* try to add new solution to scip */
2312  SCIP_CALL( SCIPtrySol(scip, *sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2313  }
2314 
2315  if( success )
2316  {
2317  assert(i >= 1);
2318  SCIPdebugMsg(scip, "heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i);
2319  }
2320  else
2321  {
2322  /* free solution structure, since we found no feasible solution */
2323  SCIP_CALL( SCIPfreeSol(scip, sol) );
2324  *sol = NULL;
2325  }
2326 
2327  /* if the best subproblem solution was not accepted in the original problem, we do not trust the solving status */
2328  *validsolved = *validsolved && i == 1;
2329  }
2330 
2331  if( *validsolved )
2332  {
2333  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
2334  }
2335 
2336  /* free array of subproblem variables, and subproblem */
2337  SCIPfreeBufferArray(scip, &subvars);
2338  SCIPfreeBufferArray(scip, &fixedvars);
2339  SCIP_CALL( SCIPfree(&subscip) );
2340 
2341  return SCIP_OKAY;
2342 }
2343 
2344 
2345 /** perform fixing of a variable and record bound disjunction information */
2346 static
2347 SCIP_RETCODE performFixing(
2348  SCIP* scip, /**< SCIP data structure */
2349  SCIP_VAR* var, /**< variable to fix */
2350  SCIP_Real val, /**< fixing value */
2351  SCIP_Bool* infeas, /**< pointer to store whether the fixing lead to infeasibility */
2352  int* bdlen, /**< current length of bound disjunction */
2353  SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
2354  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
2355  SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
2356  SCIP_Real* oldbounds /**< array of bounds before fixing */
2357  )
2358 {
2359  SCIP_Longint ndomredsfound;
2360  SCIP_Real oldlb;
2361  SCIP_Real oldub;
2362  int oldbdlen;
2363 
2364  assert(scip != NULL);
2365  assert(var != NULL);
2366  assert(val >= SCIPvarGetLbLocal(var));
2367  assert(val <= SCIPvarGetUbLocal(var));
2368  assert(infeas != NULL);
2369  assert(bdlen != NULL);
2370  assert(*bdlen >= 0);
2371  assert(*bdlen < 2*SCIPgetNVars(scip)-1);
2372  assert(bdvars != NULL);
2373  assert(bdtypes != NULL);
2374  assert(bdbounds != NULL);
2375 
2376  assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val));
2377 
2378  /* remember length of probing path */
2379  oldbdlen = *bdlen;
2380 
2381  /* get bounds of the variable to fix */
2382  oldlb = SCIPvarGetLbLocal(var);
2383  oldub = SCIPvarGetUbLocal(var);
2384 
2385  /* decrease upper bound to fixing value */
2386  *infeas = FALSE;
2387  if( SCIPisUbBetter(scip, val, oldlb, oldub) )
2388  {
2389  /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2390  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
2391  {
2392  /* create next probing node */
2393  SCIP_CALL( SCIPnewProbingNode(scip) );
2394  }
2395  SCIP_CALL( SCIPchgVarUbProbing(scip, var, val) );
2396 
2397  SCIPdebugMsg(scip, "tentatively decreasing upper bound of variable <%s> to %g for probing\n",
2398  SCIPvarGetName(var), val);
2399 
2400  /* store bound disjunction information */
2401  bdvars[*bdlen] = var;
2402  bdtypes[*bdlen] = SCIP_BOUNDTYPE_LOWER;
2403  bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)+1.0 : val;
2404  oldbounds[*bdlen] = oldub;
2405  (*bdlen)++;
2406 
2407  /* propagate the bound change; conflict analysis is performed automatically */
2408  SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2409  SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2410 
2411  /* if propagation led to a cutoff, we backtrack immediately */
2412  if( *infeas )
2413  {
2414  *bdlen = oldbdlen;
2415  return SCIP_OKAY;
2416  }
2417 
2418  /* store bound before propagation */
2419  oldbounds[*bdlen] = oldlb;
2420 
2421  /* move fixing value into the new domain, since it may be outside due to numerical issues or previous propagation */
2422  oldlb = SCIPvarGetLbLocal(var);
2423  oldub = SCIPvarGetUbLocal(var);
2424  val = MIN(val, oldub);
2425  val = MAX(val, oldlb);
2426 
2427  assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val));
2428  }
2429 
2430  /* update lower bound to fixing value */
2431  *infeas = FALSE;
2432  if( SCIPisLbBetter(scip, val, oldlb, oldub) )
2433  {
2434  /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2435  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
2436  {
2437  /* create next probing node */
2438  SCIP_CALL( SCIPnewProbingNode(scip) );
2439  }
2440  SCIP_CALL( SCIPchgVarLbProbing(scip, var, val) );
2441 
2442  SCIPdebugMsg(scip, "tentatively increasing lower bound of variable <%s> to %g for probing\n",
2443  SCIPvarGetName(var), val);
2444 
2445  /* store bound disjunction information */
2446  bdvars[*bdlen] = var;
2447  bdtypes[*bdlen] = SCIP_BOUNDTYPE_UPPER;
2448  bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)-1.0 : val;
2449  (*bdlen)++;
2450 
2451  /* propagate the bound change */
2452  SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2453  SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2454 
2455  /* if propagation led to a cutoff, we backtrack immediately */
2456  if( *infeas )
2457  {
2458  *bdlen = oldbdlen;
2459  return SCIP_OKAY;
2460  }
2461  }
2462 
2463  return SCIP_OKAY;
2464 }
2465 
2466 static
2467 SCIP_RETCODE fixAndPropagate(
2468  SCIP* scip, /**< original SCIP data structure */
2469  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
2470  int* cover, /**< array with indices of the variables in the computed cover */
2471  int coversize, /**< size of the cover */
2472  SCIP_Real* fixingvals, /**< fixing values for the variables in the cover */
2473  int* bdlen, /**< current length of bound disjunction along the probing path */
2474  SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
2475  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
2476  SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
2477  SCIP_Real* oldbounds, /**< array of bounds before fixing */
2478  int* nfixedints, /**< pointer to store number of fixed integer variables */
2479  int* nfixedconts, /**< pointer to store number of fixed continuous variables */
2480  int* lastfailed, /**< position in cover array of the variable the fixing of which yielded
2481  * infeasibility */
2482  SCIP_Bool* infeas /**< pointer to store whether fix-and-propagate led to an infeasibility */
2483  )
2484 {
2485  SCIP_VAR** vars; /* original problem's variables */
2486 
2487  int i;
2488  SCIP_Bool lpsolved;
2489 
2490  /* start probing in original problem */
2491  lpsolved = SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL;
2492  SCIP_CALL( SCIPstartProbing(scip) );
2493 
2494  /* initialize data */
2495  *nfixedints = 0;
2496  *nfixedconts = 0;
2497  *bdlen = 0;
2498  vars = SCIPgetVars(scip);
2499 
2500  /* round-fix-propagate-analyze-backtrack for each variable in the cover */
2501  for( i = 0; i < coversize && !(*infeas); i++ )
2502  {
2503  SCIP_Real* boundalts;
2504  SCIP_Real* usedvals;
2505  SCIP_Real val;
2506  int nbacktracks;
2507  int nboundalts;
2508  int nfailedvals;
2509  int nusedvals;
2510  int probingdepth;
2511  int idx;
2512 
2513  /* get probindex of next variable in the cover */
2514  idx = cover[i];
2515 
2516  /* nothing to do if the variable was already fixed, e.g., by propagation */
2517  if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[idx]), SCIPvarGetUbLocal(vars[idx])) )
2518  {
2519  fixingvals[i] = SCIPvarGetLbLocal(vars[idx]);
2520  continue;
2521  }
2522 
2523  /* we will store the fixing values already used to avoid try the same value twice */
2524  SCIP_CALL( SCIPallocBufferArray(scip, &usedvals, heurdata->maxbacktracks+1) );
2525  nusedvals = 0;
2526 
2527  /* backtracking loop */
2528  *infeas = TRUE;
2529  nfailedvals = 0;
2530  nboundalts = 0;
2531  boundalts = NULL;
2532  val = 0.0;
2533  for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ )
2534  {
2535  SCIP_Real oldlb;
2536  SCIP_Real oldub;
2537  SCIP_Bool usedbefore;
2538  int j;
2539 
2540  probingdepth = SCIPgetProbingDepth(scip);
2541 
2542  /* get fixing value */
2543  if( nbacktracks < heurdata->nfixingalts )
2544  {
2545  SCIP_Bool success;
2546 
2547  /* if the lp relaxation is not solved, we do not even try to retrieve the lp solution value;
2548  * if the NLP relaxation is not constructed, we do not even try to retrieve the NLP solution value;
2549  * if there is no feasible solution yet, we do not even try to obtain the value in the incumbent */
2550  success = FALSE;
2551  if( (heurdata->fixingalts[nbacktracks] != 'l' || lpsolved)
2552  && (heurdata->fixingalts[nbacktracks] != 'n' || !heurdata->nlpfailed)
2553  && (heurdata->fixingalts[nbacktracks] != 'i' || SCIPgetBestSol(scip) != NULL) )
2554  {
2555  SCIP_CALL( getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) );
2556  }
2557 
2558  if( !success )
2559  {
2560  SCIPdebugMsg(scip, "retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n",
2561  heurdata->fixingalts[nbacktracks], SCIPvarGetName(vars[idx]));
2562  nfailedvals++;
2563  continue;
2564  }
2565 
2566  /* for the first (successfully retrieved) fixing value, compute (at most 4) bound dependent
2567  * alternative fixing values */
2568  if( boundalts == NULL )
2569  {
2570  SCIP_CALL( SCIPallocBufferArray(scip, &boundalts, 4) );
2571  nboundalts = 0;
2572  calculateAlternatives(scip, vars[idx], val, &nboundalts, boundalts);
2573  assert(nboundalts >= 0);
2574  assert(nboundalts <= 4);
2575  }
2576  }
2577  /* get alternative fixing value */
2578  else if( boundalts != NULL && nbacktracks < heurdata->nfixingalts+nboundalts )
2579  {
2580  assert(nbacktracks-heurdata->nfixingalts >= 0);
2581  val = boundalts[nbacktracks-heurdata->nfixingalts];
2582  }
2583  else
2584  break;
2585 
2586  /* round fixing value */
2587  if( SCIPvarIsIntegral(vars[idx]) && !SCIPisIntegral(scip, val) )
2588  {
2589  SCIP_CALL( roundFixingValue(scip, &val, vars[idx], heurdata->locksrounding) );
2590  assert(SCIPisIntegral(scip, val));
2591  }
2592 
2593  /* move value into the domain, since it may be outside due to numerical issues or previous propagation */
2594  oldlb = SCIPvarGetLbLocal(vars[idx]);
2595  oldub = SCIPvarGetUbLocal(vars[idx]);
2596  val = MIN(val, oldub);
2597  val = MAX(val, oldlb);
2598 
2599  assert(!SCIPvarIsIntegral(vars[idx]) || SCIPisFeasIntegral(scip, val));
2600 
2601  /* check if this fixing value was already used */
2602  usedbefore = FALSE;
2603  for( j = nusedvals-1; j >= 0 && !usedbefore; j-- )
2604  usedbefore = SCIPisFeasEQ(scip, val, usedvals[j]);
2605 
2606  if( usedbefore )
2607  {
2608  nfailedvals++;
2609  continue;
2610  }
2611 
2612  /* store fixing value */
2613  assert(nusedvals < heurdata->maxbacktracks);
2614  usedvals[nusedvals] = val;
2615  nusedvals++;
2616 
2617  /* fix-propagate-analyze */
2618  SCIP_CALL( performFixing(scip, vars[idx], val, infeas, bdlen, bdvars, bdtypes, bdbounds, oldbounds) );
2619 
2620  /* if infeasible, backtrack and try alternative fixing value */
2621  if( *infeas )
2622  {
2623  SCIPdebugMsg(scip, " --> cutoff detected - backtracking\n");
2624  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2625  }
2626  }
2627 
2628  /* free array of alternative backtracking values */
2629  if( boundalts != NULL)
2630  SCIPfreeBufferArray(scip, &boundalts);
2631  SCIPfreeBufferArray(scip, &usedvals);
2632 
2633  /* backtracking loop unsuccessful */
2634  if( *infeas )
2635  {
2636  SCIPdebugMsg(scip, "no feasible fixing value found for variable <%s> in fixing order\n",
2637  SCIPvarGetName(vars[idx]));
2638  break;
2639  }
2640  /* fixing successful */
2641  else
2642  {
2643  /* store successful fixing value */
2644  fixingvals[i] = val;
2645 
2646  /* statistics */
2647  if( SCIPvarGetType(vars[idx]) == SCIP_VARTYPE_CONTINUOUS )
2648  (*nfixedconts)++;
2649  else
2650  (*nfixedints)++;
2651  }
2652  }
2653  assert(*infeas || i == coversize);
2654  assert(!(*infeas) || i < coversize);
2655 
2656  /* end of dive */
2657  SCIP_CALL( SCIPendProbing(scip) );
2658 
2659  *lastfailed = i;
2660 
2661  return SCIP_OKAY;
2662 }
2663 
2664 /** main procedure of the undercover heuristic */
2665 static
2666 SCIP_RETCODE SCIPapplyUndercover(
2667  SCIP* scip, /**< original SCIP data structure */
2668  SCIP_HEUR* heur, /**< heuristic data structure */
2669  SCIP_RESULT* result, /**< result data structure */
2670  SCIP_Real timelimit, /**< time limit */
2671  SCIP_Real memorylimit, /**< memory limit */
2672  SCIP_Longint nstallnodes /**< number of stalling nodes for the subproblem */
2673  )
2674 {
2675  SCIP_HEURDATA* heurdata; /* heuristic data */
2676  SCIP_VAR** vars; /* original problem's variables */
2677  SCIP_CLOCK* clock; /* clock for updating time limit */
2678 
2679  SCIP* coveringscip; /* SCIP data structure for covering problem */
2680  SCIP_VAR** coveringvars; /* covering variables */
2681  SCIP_Real* fixingvals; /* array for storing fixing values used */
2682  int* cover; /* array to store problem indices of variables in the computed cover */
2683 
2684  SCIP_VAR** bdvars; /* array of variables in bound disjunction along the probing path */
2685  SCIP_BOUNDTYPE* bdtypes; /* array of bound types in bound disjunction along the probing path */
2686  SCIP_Real* bdbounds; /* array of bounds in bound disjunction along the probing path */
2687  SCIP_Real* oldbounds; /* array of bounds before fixing along the probing path */
2688 
2689  SCIP_Real maxcoversize;
2690 
2691  int coversize;
2692  int nvars;
2693  int ncovers;
2694  int nunfixeds;
2695  int nnlconss;
2696  int i;
2697 
2698  SCIP_Bool success;
2699  SCIP_Bool reusecover;
2700 
2701  assert(scip != NULL);
2702  assert(heur != NULL);
2703  assert(result != NULL);
2704  assert(*result == SCIP_DIDNOTFIND);
2705 
2706  /* create and start timing */
2707  SCIP_CALL( SCIPcreateClock(scip, &clock) );
2708  SCIP_CALL( SCIPstartClock(scip, clock) );
2709 
2710  /* initialize */
2711  fixingvals = NULL;
2712  cover = NULL;
2713  bdvars = NULL;
2714  bdtypes = NULL;
2715  bdbounds = NULL;
2716  oldbounds = NULL;
2717  coversize = 0;
2718 
2719  /* get heuristic data */
2720  heurdata = SCIPheurGetData(heur);
2721  assert(heurdata != NULL);
2722 
2723  /* NLP relaxation has not been solved yet (only solve once, not again for each cover or dive, because it is expensive) */
2724  heurdata->nlpsolved = FALSE;
2725 
2726  /* if solving the NLP relaxation has failed too often in previous runs, or NLP and NLP solver is not available, we do
2727  * not even try
2728  */
2729  heurdata->nlpfailed = heurdata->nnlpfails >= MAXNLPFAILS || !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0;
2730 
2731  /* get variable data of original problem */
2732  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2733 
2734  /* get number of nonlinear constraints */
2735  nnlconss = 0;
2736  for( i = 0; i < heurdata->nnlconshdlrs; ++i )
2737  nnlconss += SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[i]);
2738  assert(nnlconss >= 0);
2739  assert(nnlconss <= SCIPgetNConss(scip));
2740 
2741  /* run only if problem is sufficiently nonlinear */
2742  if( nnlconss < (SCIP_Real) SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs )
2743  {
2744  SCIPdebugMsg(scip, "too few nonlinear constraints present, not running\n");
2745 
2746  /* free clock */
2747  SCIP_CALL( SCIPfreeClock(scip, &clock) );
2748 
2749  return SCIP_OKAY;
2750  }
2751 
2752  /* calculate upper bound for cover size */
2753  maxcoversize = nvars*heurdata->maxcoversizevars;
2754  if( heurdata->maxcoversizeconss < SCIP_REAL_MAX )
2755  {
2756  SCIP_Real maxcoversizeconss;
2757  maxcoversizeconss = heurdata->maxcoversizeconss * nnlconss / ((SCIP_Real) SCIPgetNConss(scip));
2758  maxcoversize = MIN(maxcoversize, maxcoversizeconss);
2759  }
2760 
2761  /* create covering problem */
2762  success = FALSE;
2763  SCIP_CALL( SCIPcreate(&coveringscip) );
2764  SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) );
2765  SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) );
2766  SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, heurdata->globalbounds, heurdata->onlyconvexify,
2767  heurdata->coverbd, heurdata->coveringobj, &success) );
2768 
2769  if( !success )
2770  {
2771  SCIPdebugMsg(scip, "creating covering problem failed, terminating\n");
2772  goto TERMINATE;
2773  }
2774  else
2775  {
2776  SCIPdebugMsg(scip, "covering problem created successfully\n");
2777  }
2778 
2779  /* count number of unfixed covering variables */
2780  nunfixeds = 0;
2781  for( i = nvars-1; i >= 0; i-- )
2782  {
2783  if( SCIPisFeasEQ(coveringscip, SCIPvarGetLbGlobal(coveringvars[i]), 1.0) )
2784  nunfixeds++;
2785  }
2786 
2787  /* update time limit */
2788  SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2789 
2790  if( timelimit <= MINTIMELEFT )
2791  {
2792  SCIPdebugMsg(scip, "time limit hit, terminating\n");
2793  goto TERMINATE;
2794  }
2795 
2796  /* update memory left */
2797  memorylimit -= SCIPgetMemUsed(coveringscip)/1048576.0;
2798  memorylimit -= SCIPgetMemExternEstim(coveringscip)/1048576.0;
2799 
2800  /* allocate memory for storing bound disjunction information along probing path */
2801  SCIP_CALL( SCIPallocBufferArray(scip, &bdvars, 2*nvars) );
2802  SCIP_CALL( SCIPallocBufferArray(scip, &bdtypes, 2*nvars) );
2803  SCIP_CALL( SCIPallocBufferArray(scip, &bdbounds, 2*nvars) );
2804  SCIP_CALL( SCIPallocBufferArray(scip, &oldbounds, 2*nvars) );
2805 
2806  /* initialize data for recovering loop */
2807  SCIP_CALL( SCIPallocBufferArray(scip, &cover, nvars) );
2808  SCIP_CALL( SCIPallocBufferArray(scip, &fixingvals, nvars) );
2809  ncovers = 0;
2810  success = FALSE;
2811  reusecover = FALSE;
2812 
2813  heurdata->nfixingalts = (int) strlen(heurdata->fixingalts);
2814  assert(heurdata->nfixingalts >= 1);
2815 
2816  /* recovering loop */
2817  while( (ncovers <= heurdata->maxrecovers || reusecover) && !success )
2818  {
2819  int lastfailed;
2820  int ndives;
2821  int nfixedints;
2822  int nfixedconts;
2823  int bdlen; /* current length of bound disjunction along the probing path */
2824 
2825  SCIP_Bool conflictcreated;
2826 
2827  SCIPdebugMsg(scip, "solving covering problem\n\n");
2828  success = FALSE;
2829  bdlen = 0;
2830  conflictcreated = FALSE;
2831 
2832  /* solve covering problem */
2833  if( !reusecover )
2834  {
2835  SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, &coversize, cover,
2836  timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, maxcoversize, &success) );
2837 
2838  SCIPstatistic(
2839  if( ncovers == 0 && success )
2840  SCIPstatisticPrintf("UCstats coversize abs: %6d rel: %9.6f\n", coversize, 100.0*coversize /(SCIP_Real)nvars);
2841  );
2842 
2843  assert(coversize >= 0);
2844  assert(coversize <= nvars);
2845  ncovers++;
2846 
2847  /* free transformed covering problem immediately */
2848  SCIP_CALL( SCIPfreeTransform(coveringscip) );
2849 
2850  /* terminate if no feasible cover was found */
2851  if( !success )
2852  {
2853  SCIPdebugMsg(scip, "no feasible cover found in covering problem %d, terminating\n", ncovers);
2854  goto TERMINATE;
2855  }
2856 
2857  /* terminate, if cover is empty or too large */
2858  if( coversize == 0 || coversize > maxcoversize )
2859  {
2860  SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2861  goto TERMINATE;
2862  }
2863 
2864  /* terminate, if cover too large for the ratio of nonlinear constraints */
2865  if( heurdata->maxcoversizeconss < SCIP_REAL_MAX && coversize > heurdata->maxcoversizeconss * nnlconss / (SCIP_Real) SCIPgetNConss(scip) )
2866  {
2867  SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2868  goto TERMINATE;
2869  }
2870  }
2871 
2872  /* data setup */
2873  ndives = 0;
2874  nfixedints = 0;
2875  nfixedconts = 0;
2876  success = FALSE;
2877  lastfailed = reusecover ? MAX(1, coversize-1) : coversize;
2878 
2879  /* round-fix-propagate-analyze-backtrack-reorder loop */
2880  while( ndives <= heurdata->maxreorders && !success )
2881  {
2882  SCIP_Bool reordered;
2883  SCIP_Bool infeas;
2884 
2885  /* compute fixing order */
2886  SCIP_CALL( computeFixingOrder(scip, heurdata, nvars, vars, coversize, cover, lastfailed, &reordered) );
2887  reordered = reordered || ndives == 0;
2888  SCIPdebugMsg(scip, "%sordering variables in cover %s\n", ndives == 0 ? "" : "re", reordered ? "" : "failed");
2889 
2890  /* stop if order has not changed */
2891  if( !reordered )
2892  break;
2893 
2894  infeas = FALSE;
2895  SCIP_CALL( fixAndPropagate(scip, heurdata, cover, coversize, fixingvals, &bdlen, bdvars, bdtypes, bdbounds, oldbounds,
2896  &nfixedints, &nfixedconts, &lastfailed, &infeas) );
2897  ndives++;
2898  success = !infeas;
2899  }
2900 
2901  /* update time limit */
2902  SCIPdebugMsg(scip, "%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ? "s" : "", ncovers, SCIPgetClockTime(scip, clock));
2903  SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2904 
2905  if( timelimit <= MINTIMELEFT )
2906  {
2907  SCIPdebugMsg(scip, "time limit hit, terminating\n");
2908  goto TERMINATE;
2909  }
2910 
2911  /* no feasible fixing could be found for the current cover */
2912  if( !success )
2913  {
2914  SCIPdebugMsg(scip, "no feasible fixing values found for cover %d\n", ncovers);
2915  }
2916  else
2917  {
2918  SCIP_SOL* sol;
2919  SCIP_Longint nsubnodes;
2920  SCIP_Bool validsolved;
2921 
2922  SCIPdebugMsg(scip, "heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n",
2923  nfixedints+nfixedconts, nfixedints, nfixedconts); /*lint !e771*/
2924 
2925  /* solve sub-CIP and pass feasible solutions to original problem */
2926  success = FALSE;
2927  validsolved = FALSE;
2928  sol = NULL;
2929  nsubnodes = 0;
2930 
2931  SCIP_CALL( solveSubproblem(scip, heur, coversize, cover, fixingvals,
2932  timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) );
2933 
2934  /* update number of sub-CIP nodes used by heuristic so far */
2935  heurdata->nusednodes += nsubnodes;
2936 
2937  /* if the subproblem was constructed from a valid copy and solved, try to forbid the assignment of fixing
2938  * values to variables in the cover
2939  */
2940  if( validsolved )
2941  {
2942  SCIP_Real maxvarsfac;
2943  SCIP_Bool useconf;
2944  int minmaxvars;
2945 
2946  SCIP_CALL( SCIPgetIntParam(scip, "conflict/minmaxvars", &minmaxvars) );
2947  SCIP_CALL( SCIPgetRealParam(scip, "conflict/maxvarsfac", &maxvarsfac) );
2948 
2949  useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars);
2950 
2951  if( useconf )
2952  {
2953  /* even if we had reset the global bounds at start of probing, the constraint might be only locally valid due to local constraints/cuts */
2954  SCIP_CALL( createConflict(scip, bdlen, bdvars, bdtypes, bdbounds, SCIPgetDepth(scip) > 0, TRUE, TRUE, &success) );
2955  conflictcreated = success;
2956  }
2957 
2958  SCIPdebugMsg(scip, "subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n",
2959  sol == NULL ? "infeasible" : "optimal",
2960  success ? "successful" : "failed", useconf ? "" : "skipped due to ", bdlen);
2961  }
2962 
2963  /* heuristic succeeded */
2964  success = (sol != NULL);
2965  if( success )
2966  {
2967  *result = SCIP_FOUNDSOL;
2968  success = TRUE;
2969 
2970  /* update time limit */
2971  SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2972 
2973  /* call NLP local search heuristic unless it has failed too often */
2974  if( heurdata->postnlp && heurdata->npostnlpfails < MAXPOSTNLPFAILS )
2975  {
2976  if( nfixedconts == 0 && validsolved )
2977  {
2978  SCIPdebugMsg(scip, "subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n");
2979  }
2980  else if( timelimit <= MINTIMELEFT )
2981  {
2982  SCIPdebugMsg(scip, "time limit hit, skipping NLP local search\n");
2983  }
2984  else if( heurdata->nlpheur == NULL )
2985  {
2986  SCIPdebugMsg(scip, "NLP heuristic not found, skipping NLP local search\n");
2987  }
2988  else
2989  {
2990  SCIP_RESULT nlpresult;
2991 
2992  SCIP_CALL( SCIPapplyHeurSubNlp(scip, heurdata->nlpheur, &nlpresult, sol, -1LL, timelimit, heurdata->minimprove, NULL, NULL) );
2993  SCIPdebugMsg(scip, "NLP local search %s\n", nlpresult == SCIP_FOUNDSOL ? "successful" : "failed");
2994 
2995  if( nlpresult == SCIP_FOUNDSOL )
2996  heurdata->npostnlpfails = 0;
2997  else
2998  heurdata->npostnlpfails++;
2999  }
3000  }
3001 
3002  /* free solution */
3003  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3004  }
3005  }
3006 
3007  /* heuristic failed but we have another recovering try, hence we forbid the current cover in the covering problem */
3008  if( !success && ncovers <= heurdata->maxrecovers )
3009  {
3010  SCIP_Bool infeas;
3011  int diversification;
3012 
3013  /* compute minimal number of unfixed covering variables (in the cover) which have to change their value */
3014  diversification = (int) SCIPfeasCeil(scip, (heurdata->recoverdiv) * (SCIP_Real) nunfixeds);
3015  diversification = MAX(diversification, 1);
3016 
3017  /* forbid unsuccessful cover globally in covering problem */
3018  SCIP_CALL( forbidCover(coveringscip, nvars, coveringvars, coversize, cover, diversification, &success, &infeas) );
3019 
3020  if( infeas )
3021  {
3022  SCIPdebugMsg(scip, "recovering problem infeasible (diversification=%d), terminating\n", diversification);
3023  goto TERMINATE;
3024  }
3025  else if( !success )
3026  {
3027  SCIPdebugMsg(scip, "failed to forbid current cover in the covering problem, terminating\n");
3028  goto TERMINATE;
3029  }
3030  else
3031  {
3032  SCIPdebugMsg(scip, "added constraint to the covering problem in order to forbid current cover\n");
3033  success = FALSE;
3034  }
3035  }
3036 
3037  /* try to re-use the same cover at most once */
3038  if( heurdata->reusecover && !reusecover && conflictcreated )
3039  reusecover = TRUE;
3040  else
3041  reusecover = FALSE;
3042  }
3043 
3044  TERMINATE:
3045  if( *result != SCIP_FOUNDSOL && *result != SCIP_DELAYED )
3046  {
3047  SCIPdebugMsg(scip, "heuristic terminating unsuccessfully\n");
3048  }
3049 
3050  /* we must remain in NLP diving mode until here to be able to retrieve NLP solution values easily */
3051  /* assert((SCIPisNLPConstructed(scip) == FALSE && heurdata->nlpsolved == FALSE) ||
3052  * (SCIPisNLPConstructed(scip) == TRUE && heurdata->nlpsolved == SCIPnlpIsDiving(SCIPgetNLP(scip))));
3053  */
3054  if( heurdata->nlpsolved )
3055  {
3056  SCIP_CALL( SCIPendDiveNLP(scip) );
3057  }
3058 
3059  /* free arrays for storing the cover */
3060  SCIPfreeBufferArrayNull(scip, &fixingvals);
3061  SCIPfreeBufferArrayNull(scip, &cover);
3062 
3063  /* free arrays for storing bound disjunction information along probing path */
3064  SCIPfreeBufferArrayNull(scip, &oldbounds);
3065  SCIPfreeBufferArrayNull(scip, &bdbounds);
3066  SCIPfreeBufferArrayNull(scip, &bdtypes);
3067  SCIPfreeBufferArrayNull(scip, &bdvars);
3068 
3069  /* free covering problem */
3070  for( i = nvars-1; i >= 0; i-- )
3071  {
3072  SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) );
3073  }
3074  SCIPfreeBufferArray(scip, &coveringvars);
3075  SCIP_CALL( SCIPfree(&coveringscip) );
3076 
3077  /* free clock */
3078  SCIP_CALL( SCIPfreeClock(scip, &clock) );
3079 
3080  return SCIP_OKAY;
3081 }
3082 
3083 
3084 /*
3085  * Callback methods of primal heuristic
3086  */
3087 
3088 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
3089 static
3090 SCIP_DECL_HEURCOPY(heurCopyUndercover)
3091 { /*lint --e{715}*/
3092  assert(scip != NULL);
3093  assert(heur != NULL);
3094  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
3095 
3096  /* call inclusion method of primal heuristic */
3097  SCIP_CALL( SCIPincludeHeurUndercover(scip) );
3098 
3099  return SCIP_OKAY;
3100 }
3101 
3102 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
3103 static
3104 SCIP_DECL_HEURFREE(heurFreeUndercover)
3105 { /*lint --e{715}*/
3106  SCIP_HEURDATA* heurdata;
3107 
3108  assert(scip != NULL);
3109  assert(heur != NULL);
3110 
3111  /* get heuristic data */
3112  heurdata = SCIPheurGetData(heur);
3113  assert(heurdata != NULL);
3114 
3115  /* free heuristic data */
3116  SCIPfreeBlockMemory(scip, &heurdata);
3117  SCIPheurSetData(heur, NULL);
3118 
3119  return SCIP_OKAY;
3120 }
3121 
3122 /** initialization method of primal heuristic (called after problem was transformed) */
3123 static
3124 SCIP_DECL_HEURINIT(heurInitUndercover)
3125 { /*lint --e{715}*/
3126  SCIP_HEURDATA* heurdata;
3127 
3128  assert(heur != NULL);
3129  assert(scip != NULL);
3130 
3131  /* get heuristic's data */
3132  heurdata = SCIPheurGetData(heur);
3133  assert(heurdata != NULL);
3134 
3135  /* create random number generator */
3136  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip),
3137  SCIPinitializeRandomSeed(scip, DEFAULT_RANDSEED)) );
3138 
3139  return SCIP_OKAY;
3140 }
3141 
3142 /** deinitialization method of primal heuristic */
3143 static
3144 SCIP_DECL_HEUREXIT(heurExitUndercover)
3145 { /*lint --e{715}*/
3146  SCIP_HEURDATA* heurdata;
3147 
3148  assert(heur != NULL);
3149  assert(scip != NULL);
3150 
3151  /* get heuristic's data */
3152  heurdata = SCIPheurGetData(heur);
3153  assert(heurdata != NULL);
3154 
3155  /* free random number generator */
3156  SCIPrandomFree(&heurdata->randnumgen);
3157 
3158  return SCIP_OKAY;
3159 }
3160 
3161 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
3162 static
3163 SCIP_DECL_HEURINITSOL(heurInitsolUndercover)
3164 { /*lint --e{715}*/
3165  SCIP_HEURDATA* heurdata;
3166  int h;
3167 
3168  assert(heur != NULL);
3169  assert(scip != NULL);
3170 
3171  /* get heuristic's data */
3172  heurdata = SCIPheurGetData(heur);
3173  assert(heurdata != NULL);
3174 
3175  /* initialize counters to zero */
3176  heurdata->nusednodes = 0;
3177  heurdata->npostnlpfails = 0;
3178  heurdata->nnlpfails = 0;
3179 
3180  /* if the heuristic is called at the root node, we may want to be called directly after the initial root LP solve */
3181  if( heurdata->beforecuts && SCIPheurGetFreqofs(heur) == 0 )
3182  SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP);
3183 
3184  /* find nonlinear constraint handlers */
3185  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->nlconshdlrs, 7) );/*lint !e506*/
3186  h = 0;
3187 
3188  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "and");
3189  if( heurdata->nlconshdlrs[h] != NULL )
3190  h++;
3191 
3192  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "quadratic");
3193  if( heurdata->nlconshdlrs[h] != NULL )
3194  h++;
3195 
3196  if( heurdata->coverbd )
3197  {
3198  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "bounddisjunction");
3199  if( heurdata->nlconshdlrs[h] != NULL )
3200  h++;
3201  }
3202 
3203  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "indicator");
3204  if( heurdata->nlconshdlrs[h] != NULL )
3205  h++;
3206 
3207  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "soc");
3208  if( heurdata->nlconshdlrs[h] != NULL )
3209  h++;
3210 
3211  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "nonlinear");
3212  if( heurdata->nlconshdlrs[h] != NULL )
3213  h++;
3214 
3215  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "abspower");
3216  if( heurdata->nlconshdlrs[h] != NULL )
3217  h++;
3218 
3219  heurdata->nnlconshdlrs = h;
3220  assert( heurdata->nnlconshdlrs <= 7 );
3221 
3222  /* find NLP local search heuristic */
3223  heurdata->nlpheur = SCIPfindHeur(scip, "subnlp");
3224 
3225  /* add global linear constraints to NLP relaxation */
3226  if( SCIPisNLPConstructed(scip) && heurdata->nlpheur != NULL )
3227  {
3228  SCIP_CALL( SCIPaddLinearConsToNlpHeurSubNlp(scip, heurdata->nlpheur, TRUE, TRUE) );
3229  }
3230 
3231  return SCIP_OKAY;
3232 }
3233 
3234 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
3235 static
3236 SCIP_DECL_HEUREXITSOL(heurExitsolUndercover)
3237 {
3238  SCIP_HEURDATA* heurdata;
3239 
3240  assert(heur != NULL);
3241  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
3242 
3243  /* get heuristic's data */
3244  heurdata = SCIPheurGetData(heur);
3245  assert(heurdata != NULL);
3246 
3247  /* free array of nonlinear constraint handlers */
3248  SCIPfreeBlockMemoryArray(scip, &heurdata->nlconshdlrs, 7);
3249 
3250  /* reset timing, if it was changed temporary (at the root node) */
3251  SCIPheurSetTimingmask(heur, HEUR_TIMING);
3252 
3253  return SCIP_OKAY;
3254 }
3255 
3256 /** execution method of primal heuristic */
3257 static
3258 SCIP_DECL_HEUREXEC(heurExecUndercover)
3259 { /*lint --e{715}*/
3260  SCIP_HEURDATA* heurdata; /* heuristic data */
3261  SCIP_Real timelimit; /* time limit for the subproblem */
3262  SCIP_Real memorylimit; /* memory limit for the subproblem */
3263  SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */
3264  SCIP_Bool run;
3265 
3266  int h;
3267 
3268  assert(heur != NULL);
3269  assert(scip != NULL);
3270  assert(result != NULL);
3271 
3272  *result = SCIP_DIDNOTRUN;
3273 
3274  /* do not call heuristic of node was already detected to be infeasible */
3275  if( nodeinfeasible )
3276  return SCIP_OKAY;
3277 
3278  /* get heuristic's data */
3279  heurdata = SCIPheurGetData(heur);
3280  assert(heurdata != NULL);
3281 
3282  /* only call heuristic once at the root */
3283  if( SCIPgetDepth(scip) == 0 && SCIPheurGetNCalls(heur) > 0 )
3284  return SCIP_OKAY;
3285 
3286  /* if we want to use NLP fixing values exclusively and no NLP solver is available, we cannot run */
3287  if( strcmp(heurdata->fixingalts, "n") == 0 && SCIPgetNNlpis(scip) == 0 )
3288  {
3289  SCIPdebugMsg(scip, "skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n");
3290  return SCIP_OKAY;
3291  }
3292 
3293  /* calculate stallnode limit */
3294  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
3295 
3296  /* reward heuristic if it succeeded often */
3297  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0));
3298  nstallnodes -= SUBMIPSETUPCOSTS * SCIPheurGetNCalls(heur); /* account for the setup costs of the sub-CIP */
3299  nstallnodes += heurdata->nodesofs;
3300 
3301  /* determine the node limit for the current process */
3302  nstallnodes -= heurdata->nusednodes;
3303  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
3304  nstallnodes = MAX(nstallnodes, 1);
3305 
3306  /* only call heuristics if we have enough nodes left to call sub-CIP solving */
3307  if( nstallnodes < heurdata->minnodes )
3308  {
3309  SCIPdebugMsg(scip, "skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
3310  return SCIP_OKAY;
3311  }
3312 
3313  /* only call heuristics if we have enough time left */
3314  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
3315  if( !SCIPisInfinity(scip, timelimit) )
3316  timelimit -= SCIPgetSolvingTime(scip);
3317  if( timelimit <= 2*MINTIMELEFT )
3318  {
3319  SCIPdebugMsg(scip, "skipping undercover heuristic: time left=%g\n", timelimit);
3320  return SCIP_OKAY;
3321  }
3322 
3323  /* only call heuristics if we have enough memory left */
3324  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
3325  if( !SCIPisInfinity(scip, memorylimit) )
3326  {
3327  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
3328  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
3329  }
3330 
3331  if( memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
3332  {
3333  SCIPdebugMsg(scip, "skipping undercover heuristic: too little memory\n");
3334  return SCIP_OKAY;
3335  }
3336 
3337  /* only call heuristic if nonlinear constraints are present */
3338  run = FALSE;
3339  for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- )
3340  {
3341  run = (SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[h]) > 0);
3342  }
3343 
3344  /* go through all nlrows and check for general nonlinearities */
3345  if( SCIPisNLPConstructed(scip) )
3346  {
3347  SCIP_NLROW** nlrows;
3348  int nnlrows;
3349  int i;
3350 
3351  /* get nlrows */
3352  nnlrows = SCIPgetNNLPNlRows(scip);
3353  nlrows = SCIPgetNLPNlRows(scip);
3354 
3355  /* check for an nlrow with nontrivial expression tree or quadratic terms; start from 0 since we expect the linear
3356  * nlrows at the end */
3357  for( i = nnlrows-1; i >= 0 && !run; i-- )
3358  {
3359  assert(nlrows[i] != NULL);
3360  run = SCIPnlrowGetExprtree(nlrows[i]) != NULL && SCIPexprtreeGetNVars(SCIPnlrowGetExprtree(nlrows[i])) > 0;
3361  run = run || SCIPnlrowGetNQuadVars(nlrows[i]) > 0;
3362  }
3363  }
3364 
3365  if( !run )
3366  {
3367  SCIPdebugMsg(scip, "skipping undercover heuristic: no nonlinear constraints found\n");
3368  return SCIP_OKAY;
3369  }
3370 
3371  /* only call heuristics if solving has not stopped yet */
3372  if( SCIPisStopped(scip) )
3373  return SCIP_OKAY;
3374 
3375  /* reset timing, if it was changed temporary (at the root node) */
3376  if( heurtiming != HEUR_TIMING )
3377  SCIPheurSetTimingmask(heur, HEUR_TIMING);
3378 
3379  /* call heuristic */
3380  *result = SCIP_DIDNOTFIND;
3381  SCIPdebugMsg(scip, "calling undercover heuristic for <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3382 
3383  SCIP_CALL( SCIPapplyUndercover(scip, heur, result, timelimit, memorylimit, nstallnodes) );
3384 
3385  return SCIP_OKAY;
3386 }
3387 
3388 
3389 /*
3390  * primal heuristic specific interface methods
3391  */
3392 
3393 /** creates the undercover primal heuristic and includes it in SCIP */
3394 SCIP_RETCODE SCIPincludeHeurUndercover(
3395  SCIP* scip /**< SCIP data structure */
3396  )
3397 {
3398  SCIP_HEURDATA* heurdata;
3399  SCIP_HEUR* heur;
3400 
3401  /* create undercover primal heuristic data */
3402  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
3403 
3404  /* always use local bounds */
3405  heurdata->globalbounds = FALSE;
3406 
3407  /* include primal heuristic */
3408  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
3409  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
3410  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecUndercover, heurdata) );
3411 
3412  assert(heur != NULL);
3413 
3414  /* set non-NULL pointers to callback methods */
3415  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyUndercover) );
3416  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeUndercover) );
3417  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitUndercover) );
3418  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitUndercover) );
3419  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolUndercover) );
3420  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolUndercover) );
3421 
3422  /* add string parameters */
3423  heurdata->fixingalts = NULL;
3424  SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/fixingalts",
3425  "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)",
3426  &heurdata->fixingalts, FALSE, DEFAULT_FIXINGALTS, NULL, NULL) );
3427 
3428  /* add longint parameters */
3429  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
3430  "maximum number of nodes to regard in the subproblem",
3431  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3432 
3433  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
3434  "minimum number of nodes required to start the subproblem",
3435  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3436 
3437  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
3438  "number of nodes added to the contingent of the total nodes",
3439  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3440 
3441  /* add real parameters */
3442  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/conflictweight",
3443  "weight for conflict score in fixing order",
3444  &heurdata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3445 
3446  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/cutoffweight",
3447  "weight for cutoff score in fixing order",
3448  &heurdata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3449 
3450  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/inferenceweight",
3451  "weight for inference score in fixing order",
3452  &heurdata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3453 
3454  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizevars",
3455  "maximum coversize (as fraction of total number of variables)",
3456  &heurdata->maxcoversizevars, TRUE, DEFAULT_MAXCOVERSIZEVARS, 0.0, 1.0, NULL, NULL) );
3457 
3458  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizeconss",
3459  "maximum coversize maximum coversize (as ratio to the percentage of non-affected constraints)",
3460  &heurdata->maxcoversizeconss, TRUE, DEFAULT_MAXCOVERSIZECONSS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3461 
3462  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mincoveredrel",
3463  "minimum percentage of nonlinear constraints in the original problem",
3464  &heurdata->mincoveredrel, TRUE, DEFAULT_MINCOVEREDREL, 0.0, 1.0, NULL, NULL) );
3465 
3466  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
3467  "factor by which the heuristic should at least improve the incumbent",
3468  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, -1.0, 1.0, NULL, NULL) );
3469 
3470  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
3471  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
3472  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
3473 
3474  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/recoverdiv",
3475  "fraction of covering variables in the last cover which need to change their value when recovering",
3476  &heurdata->recoverdiv, TRUE, DEFAULT_RECOVERDIV, 0.0, 1.0, NULL, NULL) );
3477 
3478  /* add int parameters */
3479  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/mincoveredabs",
3480  "minimum number of nonlinear constraints in the original problem",
3481  &heurdata->mincoveredabs, TRUE, DEFAULT_MINCOVEREDABS, 0, INT_MAX, NULL, NULL) );
3482 
3483  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
3484  "maximum number of backtracks in fix-and-propagate",
3485  &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, 0, INT_MAX, NULL, NULL) );
3486 
3487  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxrecovers",
3488  "maximum number of recoverings",
3489  &heurdata->maxrecovers, TRUE, DEFAULT_MAXRECOVERS, 0, INT_MAX, NULL, NULL) );
3490 
3491  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxreorders",
3492  "maximum number of reorderings of the fixing order",
3493  &heurdata->maxreorders, TRUE, DEFAULT_MAXREORDERS, 0, INT_MAX, NULL, NULL) );
3494 
3495  /* add char parameters */
3496  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/coveringobj",
3497  "objective function of the covering problem (influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties)",
3498  &heurdata->coveringobj, TRUE, DEFAULT_COVERINGOBJ, COVERINGOBJS, NULL, NULL) );
3499 
3500  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/fixingorder",
3501  "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index",
3502  &heurdata->fixingorder, TRUE, DEFAULT_FIXINGORDER, FIXINGORDERS, NULL, NULL) );
3503 
3504  /* add bool parameters */
3505  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforecuts",
3506  "should the heuristic be called at root node before cut separation?",
3507  &heurdata->beforecuts, TRUE, DEFAULT_BEFORECUTS, NULL, NULL) );
3508 
3509  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixintfirst",
3510  "should integer variables in the cover be fixed first?",
3511  &heurdata->fixintfirst, TRUE, DEFAULT_FIXINTFIRST, NULL, NULL) );
3512 
3513  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/locksrounding",
3514  "shall LP values for integer vars be rounded according to locks?",
3515  &heurdata->locksrounding, TRUE, DEFAULT_LOCKSROUNDING, NULL, NULL) );
3516 
3517  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyconvexify",
3518  "should we only fix variables in order to obtain a convex problem?",
3519  &heurdata->onlyconvexify, FALSE, DEFAULT_ONLYCONVEXIFY, NULL, NULL) );
3520 
3521  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/postnlp",
3522  "should the NLP heuristic be called to polish a feasible solution?",
3523  &heurdata->postnlp, FALSE, DEFAULT_POSTNLP, NULL, NULL) );
3524 
3525  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverbd",
3526  "should bounddisjunction constraints be covered (or just copied)?",
3527  &heurdata->coverbd, TRUE, DEFAULT_COVERBD, NULL, NULL) );
3528 
3529  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
3530  "should all active cuts from cutpool be copied to constraints in subproblem?",
3531  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
3532 
3533  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reusecover",
3534  "shall the cover be reused if a conflict was added after an infeasible subproblem?",
3535  &heurdata->reusecover, TRUE, DEFAULT_REUSECOVER, NULL, NULL) );
3536 
3537  return SCIP_OKAY;
3538 }
3539 
3540 
3541 /** computes a minimal set of covering variables */
3542 SCIP_RETCODE SCIPcomputeCoverUndercover(
3543  SCIP* scip, /**< SCIP data structure */
3544  int* coversize, /**< buffer for the size of the computed cover */
3545  SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover
3546  * (should be ready to hold SCIPgetNVars(scip) entries) */
3547  SCIP_Real timelimit, /**< time limit */
3548  SCIP_Real memorylimit, /**< memory limit */
3549  SCIP_Real objlimit, /**< objective limit: upper bound on coversize */
3550  SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
3551  SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
3552  SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
3553  char coveringobj, /**< objective function of the covering problem ('b'ranching status,
3554  * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3555  * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3556  SCIP_Bool* success /**< feasible cover found? */
3557  )
3558 {
3559  SCIP* coveringscip; /* SCIP instance for covering problem */
3560  SCIP_VAR** coveringvars; /* covering variables */
3561  SCIP_VAR** vars; /* original variables */
3562  int* coverinds; /* indices of variables in the cover */
3563  int nvars; /* number of original variables */
3564  int i;
3565 
3566  assert(scip != NULL);
3567  assert(coversize != NULL);
3568  assert(success != NULL);
3569 
3570  *success = FALSE;
3571 
3572  /* allocate memory for variables of the covering problem */
3573  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL ) );
3574  SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) );
3575  SCIP_CALL( SCIPallocBufferArray(scip, &coverinds, nvars) );
3576 
3577  /* create covering problem */
3578  SCIP_CALL( SCIPcreate(&coveringscip) );
3579  SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) );
3580  SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, globalbounds, onlyconvexify, coverbd, coveringobj, success) );
3581 
3582  if( *success )
3583  {
3584  /* solve covering problem */
3585  SCIPdebugMsg(scip, "solving covering problem\n\n");
3586 
3587  SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, coversize, coverinds,
3588  timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, objlimit, success) );
3589 
3590  if( *success )
3591  {
3592  assert(*coversize >= 0);
3593  assert(*coversize <= nvars);
3594 
3595  /* return original variables in the cover */
3596  for( i = *coversize-1; i >= 0; i-- )
3597  {
3598  assert(coverinds[i] >= 0);
3599  assert(coverinds[i] < nvars);
3600  cover[i] = vars[coverinds[i]];
3601  }
3602  }
3603  }
3604  else
3605  {
3606  SCIPdebugMsg(scip, "failure: covering problem could not be created\n");
3607  }
3608 
3609  /* free covering problem */
3610  for( i = nvars-1; i >= 0; i-- )
3611  {
3612  SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) );
3613  }
3614  SCIP_CALL( SCIPfree(&coveringscip) );
3615  SCIPfreeBufferArray(scip, &coverinds);
3616  SCIPfreeBufferArray(scip, &coveringvars);
3617 
3618  return SCIP_OKAY;
3619 }
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIPsetHeurExitsol
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8159
SCIPsortRealInt
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_NLPPAR_VERBLEVEL
Definition: type_nlpi.h:46
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21975
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46385
SCIP_HEURTIMING_DURINGLPLOOP
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition: type_timing.h:71
SCIPrandomCreate
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
processNlRow
static SCIP_RETCODE processNlRow(SCIP *scip, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, struct HessianData *hessiandata, SCIP *coveringscip, int nvars, SCIP_VAR **coveringvars, int *termcounter, int *conscounter, SCIP_Bool *consmarker, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool *success)
Definition: heur_undercover.c:257
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIPgetNNLPNlRows
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip.c:31194
SCIPgetLhsVarsSOC
SCIP_VAR ** SCIPgetLhsVarsSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5398
SCIP_FOUNDSOL
Definition: type_result.h:47
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45371
HEUR_TIMING
#define HEUR_TIMING
Definition: heur_undercover.c:52
SCIPsetSeparating
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5130
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21958
SCIP_DELAYED
Definition: type_result.h:34
SCIPisNLPConstructed
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30965
SCIPlinkCurrentSol
SCIP_RETCODE SCIPlinkCurrentSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37952
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
DEFAULT_FIXINGORDER
#define DEFAULT_FIXINGORDER
Definition: heur_undercover.c:78
termIsConvex
static SCIP_Bool termIsConvex(SCIP *scip, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool sign)
Definition: heur_undercover.c:209
exprinterpret.h
methods to interpret (evaluate) an expression tree "fast"
SCIPgetBinvarRepresentative
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip.c:18810
SCIPbacktrackProbing
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35291
SCIPgetVarAvgInferenceCutoffScore
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip.c:26663
HEUR_DISPCHAR
#define HEUR_DISPCHAR
Definition: heur_undercover.c:47
getFixingValue
static SCIP_RETCODE getFixingValue(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real *val, char fixalt, SCIP_Bool *success, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *oldbounds)
Definition: heur_undercover.c:1792
computeFixingOrder
static SCIP_RETCODE computeFixingOrder(SCIP *scip, SCIP_HEURDATA *heurdata, int nvars, SCIP_VAR **vars, int coversize, int *cover, int lastfailed, SCIP_Bool *success)
Definition: heur_undercover.c:1677
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6576
SCIPgetProbingDepth
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35264
DEFAULT_MAXRECOVERS
#define DEFAULT_MAXRECOVERS
Definition: heur_undercover.c:74
SCIPisUbBetter
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:46683
DEFAULT_MAXREORDERS
#define DEFAULT_MAXREORDERS
Definition: heur_undercover.c:75
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4461
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:225
SCIPheurGetNBestSolsFound
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIPcreateProb
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip.c:9813
DEFAULT_MINCOVEREDABS
#define DEFAULT_MINCOVEREDABS
Definition: heur_undercover.c:68
SCIPsetHeurExit
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8127
DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS
Definition: heur_undercover.c:87
DEFAULT_RECOVERDIV
#define DEFAULT_RECOVERDIV
Definition: heur_undercover.c:71
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12120
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
SCIPcreateConsSetcover
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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)
Definition: cons_setppc.c:9093
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
SCIPgetNLPSolstat
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip.c:31348
SCIPgetNVarsBounddisjunction
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3250
SCIP_Var
Definition: struct_var.h:197
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18461
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16735
solveCoveringProblem
static SCIP_RETCODE solveCoveringProblem(SCIP *coveringscip, int ncoveringvars, SCIP_VAR **coveringvars, int *coversize, int *cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool *success)
Definition: heur_undercover.c:1561
roundFixingValue
static SCIP_RETCODE roundFixingValue(SCIP *scip, SCIP_Real *val, SCIP_VAR *var, SCIP_Bool locksrounding)
Definition: heur_undercover.c:2017
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46372
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
DEFAULT_MAXCOVERSIZECONSS
#define DEFAULT_MAXCOVERSIZECONSS
Definition: heur_undercover.c:66
SCIPsetHeuristics
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5078
heur_undercover.h
Undercover primal heuristic for MINLPs.
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
SCIPgetSols
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39108
FALSE
#define FALSE
Definition: def.h:64
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE
Definition: heur_undercover.c:69
DEFAULT_RANDSEED
#define DEFAULT_RANDSEED
Definition: heur_undercover.c:92
MAXPOSTNLPFAILS
#define MAXPOSTNLPFAILS
Definition: heur_undercover.c:98
SCIPaddLongintParam
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
SCIP_DECL_HEUREXITSOL
static SCIP_DECL_HEUREXITSOL(heurExitsolUndercover)
Definition: heur_undercover.c:3238
SCIPcopyConsCompression
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3856
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
TRUE
#define TRUE
Definition: def.h:63
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
SCIPsetPresolving
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5104
SCIP_RandNumGen
Definition: struct_misc.h:239
SCIPexprintCompile
SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
Definition: exprinterpret_cppad.cpp:2198
SCIPfindBranchrule
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9219
SCIPheurGetFreqofs
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1287
SCIPnlrowGetNQuadVars
int SCIPnlrowGetNQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3275
SCIPnlrowGetRhs
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3383
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16862
DEFAULT_INFERENCEWEIGHT
#define DEFAULT_INFERENCEWEIGHT
Definition: heur_undercover.c:64
DEFAULT_MINCOVEREDREL
#define DEFAULT_MINCOVEREDREL
Definition: heur_undercover.c:67
SCIP_HEURDATA
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
DEFAULT_NODESOFS
#define DEFAULT_NODESOFS
Definition: heur_undercover.c:60
SCIP_QuadElement::idx1
int idx1
Definition: type_expr.h:100
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIPincludeHeurBasic
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8034
SCIPaddStringParam
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4348
SCIP_QuadElement
Definition: type_expr.h:98
SCIPchgVarLbProbing
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35367
DEFAULT_FIXINTFIRST
#define DEFAULT_FIXINTFIRST
Definition: heur_undercover.c:81
COVERINGOBJS
#define COVERINGOBJS
Definition: heur_undercover.c:95
SCIPfreeClock
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:45129
SCIPsetNLPIntPar
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
Definition: scip.c:31527
SCIPchgVarLb
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21705
SCIPsortDownRealInt
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPhashmapGetImage
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2902
SCIPfeasFrac
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:46481
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
SCIP_LONGINT_MAX
#define SCIP_LONGINT_MAX
Definition: def.h:131
DEFAULT_BEFORECUTS
#define DEFAULT_BEFORECUTS
Definition: heur_undercover.c:80
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_DECL_HEUREXIT
static SCIP_DECL_HEUREXIT(heurExitUndercover)
Definition: heur_undercover.c:3146
SCIPcreate
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
SCIP_DECL_HEURCOPY
static SCIP_DECL_HEURCOPY(heurCopyUndercover)
Definition: heur_undercover.c:3092
SCIPheurSetData
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
DEFAULT_CONFLICTWEIGHT
#define DEFAULT_CONFLICTWEIGHT
Definition: heur_undercover.c:62
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIPvarGetNegationVar
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:16995
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4776
SCIPwarningMessage
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:451
createConflict
static SCIP_RETCODE createConflict(SCIP *scip, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool *success)
Definition: heur_undercover.c:1461
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
SCIPgetLhsQuadratic
SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:13984
SCIPprintStatistics
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44659
SCIPexprtreeGetVars
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:101
SCIPgetNLPNlRows
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip.c:31172
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:45480
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46457
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46445
SCIPnlrowGetNQuadElems
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3322
HEUR_NAME
#define HEUR_NAME
Definition: heur_undercover.c:45
SCIP_Sol
Definition: struct_sol.h:51
DEFAULT_MINNODES
#define DEFAULT_MINNODES
Definition: heur_undercover.c:59
SCIPvarGetNegatedVar
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:16985
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10759
SCIPhashmapExists
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2996
SCIPisLbBetter
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:46668
DEFAULT_ONLYCONVEXIFY
#define DEFAULT_ONLYCONVEXIFY
Definition: heur_undercover.c:83
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
DEFAULT_MAXNODES
#define DEFAULT_MAXNODES
Definition: heur_undercover.c:58
SCIP_HashMap
Definition: struct_misc.h:121
SCIPrandomFree
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIPisConcaveQuadratic
SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14076
SCIP_QuadElement::coef
SCIP_Real coef
Definition: type_expr.h:102
SCIPnlrowGetQuadVars
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3285
SCIPgetVarsAnd
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5101
SCIPsetHeurInitsol
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8143
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15846
SCIPaddLinearConsToNlpHeurSubNlp
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
Definition: heur_subnlp.c:2389
SCIP_NLPSOLSTAT_FEASIBLE
Definition: type_nlpi.h:63
SCIPheurGetName
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIPcreateClock
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:45078
SCIPfindHeur
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip.c:8175
SCIPsolveDiveNLP
SCIP_RETCODE SCIPsolveDiveNLP(SCIP *scip)
Definition: scip.c:31889
SCIPgetVarsBounddisjunction
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3271
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIP_Cons
Definition: struct_cons.h:37
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIPgetNlRowSOC
SCIP_RETCODE SCIPgetNlRowSOC(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_soc.c:5359
SCIPisParamFixed
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4373
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12459
SCIPgetResultantAnd
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5126
HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP
Definition: heur_undercover.c:53
SCIPsetHeurFree
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
SCIPexprintCreate
SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
Definition: exprinterpret_cppad.cpp:2168
SCIPaddConsLocal
SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:13079
SCIPpropagateProbing
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35650
SCIP_Conshdlr
Definition: struct_cons.h:117
SCIP_NLPSOLSTAT
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38219
SCIP_DECL_HEUREXEC
static SCIP_DECL_HEUREXEC(heurExecUndercover)
Definition: heur_undercover.c:3260
FIXINGORDERS
#define FIXINGORDERS
Definition: heur_undercover.c:96
SCIP_PARAMETERWRONGVAL
Definition: type_retcode.h:48
SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:47
SCIP_STATUS_OPTIMAL
Definition: type_stat.h:52
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22004
SCIPsetBoolParam
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4602
SCIPgetStatus
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:921
SCIPcopyCuts
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3057
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
SCIPchgVarBoundsDiveNLP
SCIP_RETCODE SCIPchgVarBoundsDiveNLP(SCIP *scip, SCIP_VAR *var, SCIP_Real lb, SCIP_Real ub)
Definition: scip.c:31828
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7881
sign
SCIPInterval sign(const SCIPInterval &x)
Definition: intervalarithext.h:383
SCIPendProbing
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35326
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT
Definition: heur_undercover.c:70
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2797
SCIPmergeVariableStatistics
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip.c:2420
SUBMIPSETUPCOSTS
#define SUBMIPSETUPCOSTS
Definition: heur_undercover.c:100
NULL
#define NULL
Definition: lpi_spx1.cpp:137
DEFAULT_POSTNLP
#define DEFAULT_POSTNLP
Definition: heur_undercover.c:84
SCIPgetNNlpis
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:9479
SCIPgetIntParam
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip.c:4423
SCIPvarGetLPSol
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17543
SCIPunfixParam
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip.c:4539
SCIPexprtreeGetNVars
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8559
SCIPsetNLPInitialGuessSol
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:31293
SCIPgetNlRowQuadratic
SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_quadratic.c:13831
SCIP_OKAY
Definition: type_retcode.h:33
SCIPnlrowGetQuadElems
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3332
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:316
SCIPgetLowerbound
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42550
SCIPstatisticPrintf
#define SCIPstatisticPrintf
Definition: pub_message.h:107
SCIPsetEmphasis
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip.c:5033
SCIPexprintGetCapability
SCIP_EXPRINTCAPABILITY SCIPexprintGetCapability(void)
Definition: exprinterpret_cppad.cpp:2158
SCIPcomputeCoverUndercover
SCIP_RETCODE SCIPcomputeCoverUndercover(SCIP *scip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
Definition: heur_undercover.c:3544
DEFAULT_CUTOFFWEIGHT
#define DEFAULT_CUTOFFWEIGHT
Definition: heur_undercover.c:63
SCIPheurGetNCalls
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_Heur
Definition: struct_heur.h:79
varIsFixed
static SCIP_Bool varIsFixed(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool global)
Definition: heur_undercover.c:167
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
SCIPchgVarObj
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21542
SCIPgetRhsQuadratic
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:13996
SCIPcreateConsSetpack
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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)
Definition: cons_setppc.c:9034
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
pub_misc.h
public data structures and miscellaneous methods
SCIPincludeHeurUndercover
SCIP_RETCODE SCIPincludeHeurUndercover(SCIP *scip)
Definition: heur_undercover.c:3396
SCIP_EXPRINTCAPABILITY_HESSIAN
#define SCIP_EXPRINTCAPABILITY_HESSIAN
Definition: type_exprinterpret.h:40
SCIPfreeTransform
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip.c:16947
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
SCIPincludeDefaultPlugins
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition: scipdefplugins.c:27
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
SCIPgetNLhsVarsSOC
int SCIPgetNLhsVarsSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5385
incCounters
static void incCounters(int *termcounter, int *conscounter, SCIP_Bool *consmarker, int idx)
Definition: heur_undercover.c:222
DEFAULT_LOCKSROUNDING
#define DEFAULT_LOCKSROUNDING
Definition: heur_undercover.c:82
SCIPsetObjlimit
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11114
SCIPgetRhsVarSOC
SCIP_VAR * SCIPgetRhsVarSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5450
SCIPgetClockTime
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:45312
SCIPvarGetNLPSol
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:17556
calculateAlternatives
static void calculateAlternatives(SCIP *scip, SCIP_VAR *var, SCIP_Real fixval, int *nalternatives, SCIP_Real *alternatives)
Definition: heur_undercover.c:1936
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
SCIP_PARAMEMPHASIS_FEASIBILITY
Definition: type_paramset.h:65
HEUR_FREQ
#define HEUR_FREQ
Definition: heur_undercover.c:49
updateTimelimit
static SCIP_RETCODE updateTimelimit(SCIP *scip, SCIP_CLOCK *clck, SCIP_Real *timelimit)
Definition: heur_undercover.c:241
SCIPvarGetNLocksUp
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4660
SCIPinitializeRandomSeed
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25561
SCIPfreeSol
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37806
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
SCIPcreateVar
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip.c:17314
DEFAULT_COVERINGOBJ
#define DEFAULT_COVERINGOBJ
Definition: heur_undercover.c:77
SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:45
SCIPgetNSols
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39059
SCIP_QuadElement::idx2
int idx2
Definition: type_expr.h:101
SCIPfixVar
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25235
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38268
performFixing
static SCIP_RETCODE performFixing(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool *infeas, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds)
Definition: heur_undercover.c:2349
SCIPapplyHeurSubNlp
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Longint *iterused, SCIP_SOL *resultsol)
Definition: heur_subnlp.c:1672
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
SCIPcreateConsLogicor
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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)
Definition: cons_logicor.c:5138
SCIPgetBinaryVarIndicator
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
Definition: cons_indicator.c:7762
SCIPtrySol
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39976
SCIP_MAXTREEDEPTH
#define SCIP_MAXTREEDEPTH
Definition: def.h:252
SCIPconshdlrGetNActiveConss
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
SCIPrandomGetReal
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:8745
HEUR_DESC
#define HEUR_DESC
Definition: heur_undercover.c:46
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:146
SCIPnlrowGetExprtree
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3363
SCIP_REAL_MIN
#define SCIP_REAL_MIN
Definition: def.h:147
SCIPcreateConsLinear
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)
Definition: cons_linear.c:17118
SCIPvarGetNLocksDown
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
DEFAULT_MAXBACKTRACKS
#define DEFAULT_MAXBACKTRACKS
Definition: heur_undercover.c:73
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39158
DEFAULT_FIXINGALTS
#define DEFAULT_FIXINGALTS
Definition: heur_undercover.c:56
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46134
SCIP_NLPSOLSTAT_GLOBOPT
Definition: type_nlpi.h:61
SCIPaddCharParam
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
SCIPgetMemUsed
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:45796
SCIPaddVar
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11360
MAXNLPFAILS
#define MAXNLPFAILS
Definition: heur_undercover.c:97
MINTIMELEFT
#define MINTIMELEFT
Definition: heur_undercover.c:99
SCIPendDiveNLP
SCIP_RETCODE SCIPendDiveNLP(SCIP *scip)
Definition: scip.c:31772
SCIPresetClock
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:45146
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:48
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12728
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27417
fixAndPropagate
static SCIP_RETCODE fixAndPropagate(SCIP *scip, SCIP_HEURDATA *heurdata, int *cover, int coversize, SCIP_Real *fixingvals, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds, int *nfixedints, int *nfixedconts, int *lastfailed, SCIP_Bool *infeas)
Definition: heur_undercover.c:2469
SCIPsetHeurInit
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
SCIPgetRhsCoefSOC
SCIP_Real SCIPgetRhsCoefSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5463
termIsConstant
static SCIP_Bool termIsConstant(SCIP *scip, SCIP_VAR *var, SCIP_Real coeff, SCIP_Bool global)
Definition: heur_undercover.c:187
SCIPgetMemExternEstim
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:45822
SCIPgetVars
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11635
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16674
SCIPstatistic
#define SCIPstatistic(x)
Definition: pub_message.h:101
SCIP_Real
#define SCIP_Real
Definition: def.h:145
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
MIN
#define MIN(x, y)
Definition: memory.c:75
SCIPgetNVarsAnd
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5077
SCIP_NlRow
Definition: struct_nlp.h:63
SCIPheurSetTimingmask
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1221
SCIPexprintHessianSparsityDense
SCIP_RETCODE SCIPexprintHessianSparsityDense(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool *sparsity)
Definition: exprinterpret_cppad.cpp:2537
SCIP_Longint
#define SCIP_Longint
Definition: def.h:130
copySol
static SCIP_RETCODE copySol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *subsol, SCIP_SOL **newsol)
Definition: heur_undercover.c:2062
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
SCIPcreateConsBounddisjunction
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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)
Definition: cons_bounddisjunction.c:3167
SCIPsetSolVals
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38084
SCIP_NLPSOLSTAT_LOCOPT
Definition: type_nlpi.h:62
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
HEUR_FREQOFS
#define HEUR_FREQOFS
Definition: heur_undercover.c:50
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
SCIPstartDiveNLP
SCIP_RETCODE SCIPstartDiveNLP(SCIP *scip)
Definition: scip.c:31744
SCIPnlrowGetName
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
Definition: nlp.c:3412
SCIPsetHeurCopy
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
SCIPnewProbingNode
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35231
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46421
SCIP_DECL_HEURINIT
static SCIP_DECL_HEURINIT(heurInitUndercover)
Definition: heur_undercover.c:3126
SCIP_ExprTree
Definition: struct_expr.h:55
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45494
SCIPgetUpperbound
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42699
SCIPexprintFree
SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
Definition: exprinterpret_cppad.cpp:2185
SCIPstartProbing
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35185
SCIPhashmapInsert
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2845
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
forbidCover
static SCIP_RETCODE forbidCover(SCIP *scip, int nvars, SCIP_VAR **vars, int coversize, int *cover, int diversification, SCIP_Bool *success, SCIP_Bool *infeas)
Definition: heur_undercover.c:1338
SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:53
DEFAULT_REUSECOVER
#define DEFAULT_REUSECOVER
Definition: heur_undercover.c:86
SCIPheurGetData
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
solveSubproblem
static SCIP_RETCODE solveSubproblem(SCIP *scip, SCIP_HEUR *heur, int coversize, int *cover, SCIP_Real *fixedvals, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nodelimit, SCIP_Longint nstallnodes, SCIP_Bool *validsolved, SCIP_SOL **sol, SCIP_Longint *nusednodes)
Definition: heur_undercover.c:2103
HEUR_PRIORITY
#define HEUR_PRIORITY
Definition: heur_undercover.c:48
SCIPnlrowGetLhs
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3373
SCIPgetNNodes
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
SCIPapplyUndercover
static SCIP_RETCODE SCIPapplyUndercover(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nstallnodes)
Definition: heur_undercover.c:2668
SCIP_DECL_HEURINITSOL
static SCIP_DECL_HEURINITSOL(heurInitsolUndercover)
Definition: heur_undercover.c:3165
SCIP_VARSTATUS_FIXED
Definition: type_var.h:43
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16746
SCIPchgVarUbProbing
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35411
SCIP_Clock
Definition: struct_clock.h:55
SCIPstartClock
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:45163
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38182
scipdefplugins.h
default SCIP plugins
DEFAULT_MAXCOVERSIZEVARS
#define DEFAULT_MAXCOVERSIZEVARS
Definition: heur_undercover.c:65
SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:53
SCIPgetLhsCoefsSOC
SCIP_Real * SCIPgetLhsCoefsSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5411
SCIPaddRealParam
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
HEUR_MAXDEPTH
#define HEUR_MAXDEPTH
Definition: heur_undercover.c:51
SCIPsetSubscipsOff
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5055
SCIP_ExprInt
Definition: exprinterpret_cppad.cpp:323
DEFAULT_COVERBD
#define DEFAULT_COVERBD
Definition: heur_undercover.c:85
SCIPisConvexQuadratic
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14059
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4718
SCIPgetNegatedVar
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:18740
createCoveringProblem
static SCIP_RETCODE createCoveringProblem(SCIP *scip, SCIP *coveringscip, SCIP_VAR **coveringvars, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
Definition: heur_undercover.c:548
scip.h
SCIP callable library.
SCIP_PARAMSETTING_AGGRESSIVE
Definition: type_paramset.h:52
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
SCIPgetVarConflictScore
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26114
SCIPvarIsActive
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16842
SCIPfree
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIPvarIsNegated
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16710
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178
SCIPreallocBufferArray
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:21995
SCIP_DECL_HEURFREE
static SCIP_DECL_HEURFREE(heurFreeUndercover)
Definition: heur_undercover.c:3106
SCIPprintSol
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38601
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58