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 
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
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
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
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
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
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
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  SCIP_Real ub = 1.0;
610 
611  /* if the variable in the original problem is fixed, then the corresponding cover variable cannot be 1 in any
612  * optimal solution of the covering problem (see special termIsConstant treatment below)
613  * since some calling code may assume that no fixed variables will appear in the cover (see #1845), but we
614  * might not compute an optimal cover here, we fix these variable to 0 here
615  */
616  if( globalbounds )
617  {
618  if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i])) )
619  ub = 0.0;
620  }
621  else
622  {
623  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
624  ub = 0.0;
625  }
626 
627  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPvarGetName(vars[i]));
628  SCIP_CALL( SCIPcreateVar(coveringscip, &coveringvars[i], name, 0.0, ub, 1.0, SCIP_VARTYPE_BINARY,
629  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
630  assert(coveringvars[i] != NULL);
631  SCIP_CALL( SCIPaddVar(coveringscip, coveringvars[i]) );
632  }
633 
634  /* first, go through some special constraint handlers which we do not want to treat by looking at their nlrow
635  * representation; we store these in a hash map and afterwards process all nlrows which are not found in the hash map
636  */
637  nlrowmap = NULL;
638  if( SCIPisNLPConstructed(scip) )
639  {
640  int nnlprows;
641 
642  nnlprows = SCIPgetNNLPNlRows(scip);
643  if( nnlprows > 0 )
644  {
645  int mapsize;
646 
647  /* calculate size of hash map */
648  conshdlr = SCIPfindConshdlr(scip, "quadratic");
649  mapsize = (conshdlr == NULL) ? 0 : SCIPconshdlrGetNActiveConss(conshdlr);
650  conshdlr = SCIPfindConshdlr(scip, "soc");
651  if( conshdlr != NULL )
652  mapsize += SCIPconshdlrGetNActiveConss(conshdlr);
653  mapsize = MAX(mapsize, nnlprows);
654  assert(mapsize > 0);
655 
656  /* create hash map */
657  SCIP_CALL( SCIPhashmapCreate(&nlrowmap, SCIPblkmem(scip), mapsize) );
658  assert(nlrowmap != NULL);
659  }
660  }
661 
662  /* go through all AND constraints in the original problem */
663  conshdlr = SCIPfindConshdlr(scip, "and");
664  if( conshdlr != NULL )
665  {
666  int c;
667 
668  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
669  {
670  SCIP_CONS* andcons;
671  SCIP_CONS* coveringcons;
672  SCIP_VAR** andvars;
673  SCIP_VAR* andres;
674  SCIP_VAR** coveringconsvars;
675  SCIP_Real* coveringconsvals;
676  SCIP_Bool negated;
677 
678  int ntofix;
679  int v;
680 
681  /* get constraint and variables */
682  andcons = SCIPconshdlrGetConss(conshdlr)[c];
683  assert(andcons != NULL);
684  andvars = SCIPgetVarsAnd(scip, andcons);
685  assert(andvars != NULL);
686 
687  /* "and" constraints are not passed to the NLP, hence nothing to store in the hash map */
688 
689  /* allocate memory for covering constraint */
690  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, SCIPgetNVarsAnd(scip, andcons)+1) );
691  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, SCIPgetNVarsAnd(scip, andcons)+1) );
692 
693  /* collect unfixed variables */
694  BMSclearMemoryArray(consmarker, nvars);
695  ntofix = 0;
696  for( v = SCIPgetNVarsAnd(scip, andcons)-1; v >= 0; v-- )
697  {
698  assert(andvars[v] != NULL);
699  negated = FALSE;
700 
701  /* if variable is fixed to 0, entire constraint can be linearized */
702  if( varIsFixed(scip, andvars[v], 0.0, globalbounds) )
703  {
704  ntofix = 0;
705  break;
706  }
707 
708  /* if variable is fixed, nothing to do */
709  if( termIsConstant(scip, andvars[v], 1.0, globalbounds) )
710  {
711  continue;
712  }
713 
714  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
715  probindex = SCIPvarGetProbindex(andvars[v]);
716  if( probindex == -1 )
717  {
718  SCIP_VAR* repvar;
719 
720  /* get binary representative of variable */
721  SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[v], &repvar, &negated) );
722  assert(repvar != NULL);
723  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
724 
726  {
727  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(andvars[v]));
728  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
729  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
730  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
731  goto TERMINATE;
732  }
733 
734  /* check for negation */
735  if( SCIPvarIsNegated(repvar) )
736  {
737  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
738  negated = TRUE;
739  }
740  else
741  {
742  assert(SCIPvarIsActive(repvar));
743  probindex = SCIPvarGetProbindex(repvar);
744  negated = FALSE;
745  }
746  }
747  assert(probindex >= 0);
748 
749  /* add covering variable for unfixed original variable */
750  if( negated )
751  {
752  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
753  }
754  else
755  coveringconsvars[ntofix] = coveringvars[probindex];
756  coveringconsvals[ntofix] = 1.0;
757  ntofix++;
758  }
759  negated = FALSE;
760 
761  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
762  andres = SCIPgetResultantAnd(scip, andcons);
763  assert(andres != NULL);
764  probindex = SCIPvarGetProbindex(andres);
765 
766  /* if resultant is fixed this constraint can be either linearized or is redundant because all operands can be fixed */
767  if( termIsConstant(scip, andres, 1.0, globalbounds) )
768  {
769  /* free memory for covering constraint */
770  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
771  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
772 
773  continue;
774  }
775 
776  if( probindex == -1 )
777  {
778  SCIP_VAR* repvar;
779 
780  /* get binary representative of variable */
781  SCIP_CALL( SCIPgetBinvarRepresentative(scip, SCIPgetResultantAnd(scip, andcons), &repvar, &negated) );
782  assert(repvar != NULL);
783  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
784 
786  {
787  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(SCIPgetResultantAnd(scip, andcons)));
788  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
789  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
790  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
791  goto TERMINATE;
792  }
793 
794  /* check for negation */
795  if( SCIPvarIsNegated(repvar) )
796  {
797  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
798  negated = TRUE;
799  }
800  else
801  {
802  assert(SCIPvarIsActive(repvar));
803  probindex = SCIPvarGetProbindex(repvar);
804  negated = FALSE;
805  }
806  }
807  else if( SCIPvarGetLbGlobal(andres) > 0.5 || SCIPvarGetUbGlobal(andres) < 0.5 )
808  {
809  /* free memory for covering constraint */
810  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
811  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
812 
813  continue;
814  }
815  assert(probindex >= 0);
816  assert(!termIsConstant(scip, (negated ? SCIPvarGetNegatedVar(vars[probindex]) : vars[probindex]), 1.0, globalbounds));
817 
818  /* if less than two variables are unfixed or the resultant variable is fixed, the entire constraint can be
819  * linearized anyway
820  */
821  if( ntofix >= 2 )
822  {
823  assert(ntofix <= SCIPgetNVarsAnd(scip, andcons));
824 
825  /* add covering variable for unfixed resultant */
826  if( negated )
827  {
828  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
829  }
830  else
831  coveringconsvars[ntofix] = coveringvars[probindex];
832  coveringconsvals[ntofix] = (SCIP_Real)(ntofix - 1);
833  ntofix++;
834 
835  /* create covering constraint */
836  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(andcons));
837  SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals,
838  (SCIP_Real)(ntofix - 2), SCIPinfinity(coveringscip),
839  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
840 
841  if( coveringcons == NULL )
842  {
843  SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
844  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
845  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
846  goto TERMINATE;
847  }
848 
849  /* add and release covering constraint */
850  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
851  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
852 
853  /* update counters */
854  for( v = ntofix-1; v >= 0; v-- )
855  if( SCIPvarIsNegated(coveringconsvars[v]) )
856  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v])));
857  else
858  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v]));
859  }
860 
861  /* free memory for covering constraint */
862  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
863  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
864  }
865  }
866 
867  /* go through all bounddisjunction constraints in the original problem */
868  conshdlr = SCIPfindConshdlr(scip, "bounddisjunction");
869  if( conshdlr != NULL && coverbd )
870  {
871  int c;
872 
873  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
874  {
875  SCIP_CONS* bdcons;
876  SCIP_CONS* coveringcons;
877  SCIP_VAR** bdvars;
878  SCIP_VAR** coveringconsvars;
879  SCIP_Real* coveringconsvals;
880 
881  int nbdvars;
882  int ntofix;
883  int v;
884 
885  /* get constraint and variables */
886  bdcons = SCIPconshdlrGetConss(conshdlr)[c];
887  assert(bdcons != NULL);
888  bdvars = SCIPgetVarsBounddisjunction(scip, bdcons);
889  assert(bdvars != NULL);
890  nbdvars = SCIPgetNVarsBounddisjunction(scip, bdcons);
891 
892  /* bounddisjunction constraints are not passed to the NLP, hence nothing to store in the hash map */
893 
894  /* allocate memory for covering constraint */
895  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, nbdvars) );
896  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, nbdvars) );
897 
898  /* collect unfixed variables */
899  BMSclearMemoryArray(consmarker, nvars);
900  ntofix = 0;
901  for( v = nbdvars-1; v >= 0; v-- )
902  {
903  SCIP_Bool negated;
904 
905  assert(bdvars[v] != NULL);
906  negated = FALSE;
907 
908  /* if variable is fixed, nothing to do */
909  if( varIsFixed(scip, bdvars[v], globalbounds ? SCIPvarGetLbGlobal(bdvars[v]) : SCIPvarGetLbLocal(bdvars[v]),
910  globalbounds) )
911  {
912  continue;
913  }
914 
915  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
916  probindex = SCIPvarGetProbindex(bdvars[v]);
917  if( probindex == -1 )
918  {
919  SCIP_VAR* repvar;
920 
921  /* get binary representative of variable */
922  SCIP_CALL( SCIPgetBinvarRepresentative(scip, bdvars[v], &repvar, &negated) );
923  assert(repvar != NULL);
924  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
925 
927  {
928  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(bdvars[v]));
929  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(bdcons));
930  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
931  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
932  goto TERMINATE;
933  }
934 
935  /* check for negation */
936  if( SCIPvarIsNegated(repvar) )
937  {
938  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
939  negated = TRUE;
940  }
941  else
942  {
943  assert(SCIPvarIsActive(repvar));
944  probindex = SCIPvarGetProbindex(repvar);
945  negated = FALSE;
946  }
947  }
948  assert(probindex >= 0);
949 
950  /* add covering variable for unfixed original variable */
951  if( negated )
952  {
953  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
954  }
955  else
956  coveringconsvars[ntofix] = coveringvars[probindex];
957  coveringconsvals[ntofix] = 1.0;
958  ntofix++;
959  }
960 
961  /* if less than two variables are unfixed, the entire constraint can be linearized anyway */
962  if( ntofix >= 2 )
963  {
964  assert(ntofix <= nbdvars);
965 
966  /* create covering constraint */
967  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(bdcons));
968  SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals,
969  (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip),
970  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
971 
972  if( coveringcons == NULL )
973  {
974  SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
975  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
976  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
977  goto TERMINATE;
978  }
979 
980  /* add and release covering constraint */
981  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
982  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
983 
984  /* update counters */
985  for( v = ntofix-1; v >= 0; v-- )
986  if( SCIPvarIsNegated(coveringconsvars[v]) )
987  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v])));
988  else
989  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v]));
990  }
991 
992  /* free memory for covering constraint */
993  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
994  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
995  }
996  }
997 
998  /* go through all indicator constraints in the original problem; fix the binary variable */
999  conshdlr = SCIPfindConshdlr(scip, "indicator");
1000  if( conshdlr != NULL )
1001  {
1002  int c;
1003 
1004  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
1005  {
1006  SCIP_CONS* indcons;
1007  SCIP_VAR* binvar;
1008  SCIP_VAR* coveringvar;
1009 
1010  /* get constraint and variables */
1011  indcons = SCIPconshdlrGetConss(conshdlr)[c];
1012  assert(indcons != NULL);
1013  binvar = SCIPgetBinaryVarIndicator(indcons);
1014  assert(binvar != NULL);
1015 
1016  /* indicator constraints are not passed to the NLP, hence nothing to store in the hash map */
1017 
1018  /* if variable is fixed, nothing to do */
1019  if( varIsFixed(scip, binvar, globalbounds ? SCIPvarGetLbGlobal(binvar) : SCIPvarGetLbLocal(binvar), globalbounds) )
1020  {
1021  continue;
1022  }
1023 
1024  /* if constraints with inactive variables are present, we have to find the corresponding active variable */
1025  probindex = SCIPvarGetProbindex(binvar);
1026  if( probindex == -1 )
1027  {
1028  SCIP_VAR* repvar;
1029  SCIP_Bool negated;
1030 
1031  /* get binary representative of variable */
1032  negated = FALSE;
1033  SCIP_CALL( SCIPgetBinvarRepresentative(scip, binvar, &repvar, &negated) );
1034  assert(repvar != NULL);
1035  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
1036 
1037  if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
1038  {
1039  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(binvar));
1040  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(indcons));
1041  goto TERMINATE;
1042  }
1043 
1044  /* check for negation */
1045  if( SCIPvarIsNegated(repvar) )
1046  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
1047  else
1048  {
1049  assert(SCIPvarIsActive(repvar));
1050  probindex = SCIPvarGetProbindex(repvar);
1051  }
1052  }
1053  assert(probindex >= 0);
1054 
1055  /* get covering variable for unfixed binary variable in indicator constraint */
1056  coveringvar = coveringvars[probindex];
1057 
1058  /* require covering variable to be fixed such that indicator is linearized */
1059  SCIP_CALL( SCIPchgVarLb(coveringscip, coveringvar, 1.0) );
1060 
1061  /* update counters */
1062  BMSclearMemoryArray(consmarker, nvars);
1063  incCounters(termcounter, conscounter, consmarker, probindex);
1064  }
1065  }
1066 
1067  /* go through all quadratic constraints in the original problem */
1068  conshdlr = SCIPfindConshdlr(scip, "quadratic");
1069  if( conshdlr != NULL )
1070  {
1071  int c;
1072 
1073  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
1074  {
1075  SCIP_CONS* quadcons;
1076  SCIP_NLROW* nlrow;
1077 
1078  /* get constraint */
1079  quadcons = SCIPconshdlrGetConss(conshdlr)[c];
1080  assert(quadcons != NULL);
1081 
1082  /* get nlrow representation and store it in hash map */
1083  SCIP_CALL( SCIPgetNlRowQuadratic(scip, quadcons, &nlrow) );
1084  assert(nlrow != NULL);
1085  if( nlrowmap != NULL )
1086  {
1087  assert(!SCIPhashmapExists(nlrowmap, nlrow));
1088  SCIP_CALL( SCIPhashmapInsert(nlrowmap, nlrow, quadcons) );
1089  }
1090 
1091  /* if we only want to convexify and curvature and bounds prove already convexity, nothing to do */
1092  if( onlyconvexify
1093  && ((SCIPisInfinity(scip, -SCIPgetLhsQuadratic(scip, quadcons)) && SCIPisConvexQuadratic(scip, quadcons))
1094  || (SCIPisInfinity(scip, SCIPgetRhsQuadratic(scip, quadcons)) && SCIPisConcaveQuadratic(scip, quadcons))) )
1095  continue;
1096 
1097  /* process nlrow */
1098  *success = FALSE;
1099  SCIP_CALL( processNlRow(scip, nlrow, exprint, &hessiandata, coveringscip, nvars, coveringvars,
1100  termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1101 
1102  if( *success == FALSE )
1103  goto TERMINATE;
1104  }
1105 
1106  *success = FALSE;
1107  }
1108 
1109  /* go through all "soc" constraints in the original problem */
1110  conshdlr = SCIPfindConshdlr(scip, "soc");
1111  if( conshdlr != NULL && !onlyconvexify )
1112  {
1113  int c;
1114 
1115  for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
1116  {
1117  SCIP_CONS* soccons;
1118  SCIP_CONS* coveringcons;
1119  SCIP_VAR** soclhsvars;
1120  SCIP_VAR* socrhsvar;
1121  SCIP_VAR** coveringconsvars;
1122  SCIP_NLROW* nlrow;
1123 
1124  int ntofix;
1125  int v;
1126 
1127  /* get constraints and variables */
1128  soccons = SCIPconshdlrGetConss(conshdlr)[c];
1129  assert(soccons != NULL);
1130  socrhsvar = SCIPgetRhsVarSOC(scip, soccons);
1131  assert(socrhsvar != NULL);
1132  soclhsvars = SCIPgetLhsVarsSOC(scip, soccons);
1133  assert(soclhsvars != NULL);
1134 
1135  /* get nlrow representation and store it in hash map */
1136  SCIP_CALL( SCIPgetNlRowSOC(scip, soccons, &nlrow) );
1137  assert(nlrow != NULL);
1138  if( nlrowmap != NULL )
1139  {
1140  assert(!SCIPhashmapExists(nlrowmap, nlrow));
1141  SCIP_CALL( SCIPhashmapInsert(nlrowmap, nlrow, soccons) );
1142  }
1143 
1144  /* allocate memory for covering constraint */
1145  SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, SCIPgetNLhsVarsSOC(scip, soccons)+1) );
1146 
1147  /* collect unfixed variables */
1148  BMSclearMemoryArray(consmarker, nvars);
1149  ntofix = 0;
1150 
1151  /* soc constraints should contain only active and multi-aggregated variables; the latter we do not handle */
1152  probindex = SCIPvarGetProbindex(socrhsvar);
1153  if( probindex == -1 )
1154  {
1155  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(soccons));
1156  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1157  goto TERMINATE;
1158  }
1159 
1160  /* add covering variable for unfixed rhs variable */
1161  if( !termIsConstant(scip, socrhsvar, SCIPgetRhsCoefSOC(scip, soccons), globalbounds) )
1162  {
1163  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
1164  ntofix++;
1165  }
1166 
1167  /* go through lhs variables */
1168  for( v = SCIPgetNLhsVarsSOC(scip, soccons)-1; v >= 0; v-- )
1169  {
1170  assert(soclhsvars[v] != NULL);
1171 
1172  /* soc constraints should contain only active and multi-aggregated variables; the latter we do not handle */
1173  probindex = SCIPvarGetProbindex(soclhsvars[v]);
1174  if( probindex == -1 )
1175  {
1176  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(soccons));
1177  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1178  goto TERMINATE;
1179  }
1180 
1181  /* add covering variable for unfixed lhs variable */
1182  if( !termIsConstant(scip, soclhsvars[v], SCIPgetLhsCoefsSOC(scip, soccons)[v], globalbounds) )
1183  {
1184  SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
1185  ntofix++;
1186  }
1187  }
1188 
1189  if( ntofix >= 2 )
1190  {
1191  /* create covering constraint */
1192  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(soccons));
1193  SCIP_CALL( SCIPcreateConsSetpack(coveringscip, &coveringcons, name, ntofix, coveringconsvars,
1194  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1195 
1196  if( coveringcons == NULL )
1197  {
1198  SCIPdebugMsg(scip, "failed to create set packing constraint <%s>\n", name);
1199  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1200  goto TERMINATE;
1201  }
1202 
1203  /* add and release covering constraint */
1204  SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
1205  SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
1206 
1207  /* update counters */
1208  for( v = ntofix-1; v >= 0; v-- )
1209  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegatedVar(coveringconsvars[v])));
1210  }
1211 
1212  /* free memory for covering constraint */
1213  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
1214  }
1215  }
1216 
1217  /* go through all yet unprocessed nlrows */
1218  if( nlrowmap != NULL )
1219  {
1220  SCIP_NLROW** nlrows;
1221  int nnlrows;
1222 
1223  assert(SCIPisNLPConstructed(scip));
1224 
1225  /* get nlrows */
1226  nnlrows = SCIPgetNNLPNlRows(scip);
1227  nlrows = SCIPgetNLPNlRows(scip);
1228 
1229  for( i = nnlrows-1; i >= 0; i-- )
1230  {
1231  assert(nlrows[i] != NULL);
1232 
1233  /* nlrow or corresponding constraint already processed */
1234  if( SCIPhashmapExists(nlrowmap, nlrows[i]) )
1235  continue;
1236 
1237  /* process nlrow */
1238  *success = FALSE;
1239  SCIP_CALL( processNlRow(scip, nlrows[i], exprint, &hessiandata, coveringscip, nvars, coveringvars,
1240  termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1241 
1242  if( *success == FALSE )
1243  goto TERMINATE;
1244  }
1245  }
1246 
1247  /* set objective function of covering problem */
1248  switch( coveringobj )
1249  {
1250  case 'c': /* number of influenced nonlinear constraints */
1251  for( i = nvars-1; i >= 0; i-- )
1252  {
1253  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) conscounter[i]) );
1254  }
1255  break;
1256  case 'd': /* domain size */
1257  for( i = nvars-1; i >= 0; i-- )
1258  {
1259  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i],
1260  (globalbounds ? SCIPvarGetUbGlobal(vars[i]) - SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbLocal(vars[i]) - SCIPvarGetLbLocal(vars[i]))) );
1261  }
1262  break;
1263  case 'l': /* number of locks */
1264  for( i = nvars-1; i >= 0; i-- )
1265  {
1266  nlocksup = SCIPvarGetNLocksUp(vars[i]);
1267  nlocksdown = SCIPvarGetNLocksDown(vars[i]);
1268  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (nlocksup+nlocksdown+1)) );
1269  }
1270  break;
1271  case 'm': /* min(up locks, down locks)+1 */
1272  for( i = nvars-1; i >= 0; i-- )
1273  {
1274  nlocksup = SCIPvarGetNLocksUp(vars[i]);
1275  nlocksdown = SCIPvarGetNLocksDown(vars[i]);
1276  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (MIN(nlocksup, nlocksdown)+1)) );
1277  }
1278  break;
1279  case 't': /* number of influenced nonlinear terms */
1280  for( i = nvars-1; i >= 0; i-- )
1281  {
1282  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) termcounter[i]) );
1283  }
1284  break;
1285  case 'u': /* unit penalties */
1286  for( i = nvars-1; i >= 0; i-- )
1287  {
1288  SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], 1.0) );
1289  }
1290  break;
1291  default:
1292  SCIPerrorMessage("invalid choice <%c> for covering objective\n", coveringobj);
1293  goto TERMINATE;
1294  }
1295 
1296  /* covering problem successfully set up */
1297  *success = TRUE;
1298 
1299  TERMINATE:
1300  /* free nlrow hash map */
1301  if( nlrowmap != NULL )
1302  {
1303  SCIPhashmapFree(&nlrowmap);
1304  }
1305 
1306  /* free hessian data */
1307  if( hessiandata.nvars > 0 )
1308  {
1309  assert(hessiandata.evalsol != NULL);
1310  assert(hessiandata.varvals != NULL);
1311  assert(hessiandata.sparsity != NULL);
1312 
1313  SCIPfreeBufferArray(scip, &hessiandata.sparsity);
1314  SCIPfreeBufferArray(scip, &hessiandata.varvals);
1315 
1316  SCIP_CALL( SCIPfreeSol(scip, &hessiandata.evalsol) );
1317  }
1318  else
1319  {
1320  assert(hessiandata.evalsol == NULL);
1321  assert(hessiandata.varvals == NULL);
1322  assert(hessiandata.sparsity == NULL);
1323  }
1324 
1325  /* free expression interpreter */
1326  SCIP_CALL( SCIPexprintFree(&exprint) );
1327 
1328  SCIPstatistic(
1329  {
1330  int nnonzs;
1331  nnonzs = 0;
1332  for( i = 0; i < nvars; ++i)
1333  nnonzs += termcounter[i];
1334  SCIPstatisticPrintf("UCstats nnz/var: %9.6f\n", nnonzs/(SCIP_Real)nvars);
1335  nnonzs = 0;
1336  for( i = 0; i < nvars; ++i)
1337  if( conscounter[i] > 0 )
1338  nnonzs++;
1339  SCIPstatisticPrintf("UCstats nlvars: %6d\n", nnonzs);
1340  }
1341  );
1342 
1343  /* free counter arrays for weighted objectives */
1344  SCIPfreeBufferArray(scip, &termcounter);
1345  SCIPfreeBufferArray(scip, &conscounter);
1346  SCIPfreeBufferArray(scip, &consmarker);
1347 
1348  return SCIP_OKAY;
1349 }
1350 
1351 
1352 /** adds a constraint to the covering problem to forbid the given cover */
1353 static
1355  SCIP* scip, /**< SCIP data structure of the covering problem */
1356  int nvars, /**< number of variables */
1357  SCIP_VAR** vars, /**< variable array */
1358  int coversize, /**< size of the cover */
1359  int* cover, /**< problem indices of the variables in the cover */
1360  int diversification, /**< how many unfixed variables have to change their value? */
1361  SCIP_Bool* success, /**< pointer to store whether the cutoff constraint was created successfully */
1362  SCIP_Bool* infeas /**< pointer to store whether the cutoff proves (local or global) infeasibility */
1363  )
1364 {
1365  SCIP_CONS* cons;
1366  SCIP_VAR** consvars;
1367 
1368  char name[SCIP_MAXSTRLEN];
1369  int nconsvars;
1370  int i;
1371 
1372  assert(scip != NULL);
1373  assert(vars != NULL);
1374  assert(nvars >= 1);
1375  assert(cover != NULL);
1376  assert(coversize >= 1);
1377  assert(coversize <= nvars);
1378  assert(diversification >= 1);
1379  assert(success != NULL);
1380  assert(infeas != NULL);
1381 
1382  *success = FALSE;
1383  *infeas = FALSE;
1384 
1385  /* allocate memory for constraint variables */
1386  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, coversize) );
1387  nconsvars = 0;
1388  cons = NULL;
1389 
1390  /* create constraint name */
1391  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "forbid_cover_assignment");
1392 
1393  /* if all variables in the cover are binary and we require only one variable to change its value, then we create a
1394  * set covering constraint
1395  */
1396  if( diversification == 1 )
1397  {
1398  /* build up constraint */
1399  for( i = coversize-1; i >= 0; i-- )
1400  {
1401  if( !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1402  {
1403  SCIP_CALL( SCIPgetNegatedVar(scip, vars[cover[i]], &consvars[nconsvars]) );
1404  nconsvars++;
1405  }
1406  }
1407 
1408  /* if all covering variables are fixed to one, the constraint cannot be satisfied */
1409  if( nconsvars == 0 )
1410  {
1411  *infeas = TRUE;
1412  }
1413  else
1414  {
1415  /* create constraint */
1416  SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars,
1417  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1418  }
1419  }
1420  /* if all variables in the cover are binary and we require more variables to change their value, then we create a
1421  * linear constraint
1422  */
1423  else
1424  {
1425  SCIP_Real* consvals;
1426  SCIP_Real rhs;
1427 
1428  /* build up constraint */
1429  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, coversize) );
1430  for( i = coversize-1; i >= 0; i-- )
1431  {
1432  if( !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1433  {
1434  consvars[nconsvars] = vars[cover[i]];
1435  consvals[nconsvars] = 1.0;
1436  nconsvars++;
1437  }
1438  }
1439  rhs = (SCIP_Real) (nconsvars-diversification);
1440 
1441  /* if too many covering variables are fixed to 1, the constraint cannot be satisfied */
1442  if( rhs < 0 )
1443  {
1444  *infeas = TRUE;
1445  }
1446  else
1447  {
1448  /* create constraint */
1449  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name,
1450  nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs,
1451  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1452  }
1453 
1454  /* free memory */
1455  SCIPfreeBufferArray(scip, &consvals);
1456  }
1457 
1458  /* free memory */
1459  SCIPfreeBufferArray(scip, &consvars);
1460 
1461  /* if proven infeasible, we do not even add the constraint; otherwise we add and release the constraint if created
1462  * successfully
1463  */
1464  if( !(*infeas) && cons != NULL )
1465  {
1466  SCIP_CALL( SCIPaddCons(scip, cons) );
1467  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1468  *success = TRUE;
1469  }
1470 
1471  return SCIP_OKAY;
1472 }
1473 
1474 
1475 /** adds a set covering or bound disjunction constraint to the original problem */
1476 static
1478  SCIP* scip, /**< SCIP data structure */
1479  int bdlen, /**< length of bound disjunction */
1480  SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
1481  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
1482  SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
1483  SCIP_Bool local, /**< is constraint valid only locally? */
1484  SCIP_Bool dynamic, /**< is constraint subject to aging? */
1485  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
1486  SCIP_Bool* success /**< pointer to store whether the cutoff constraint was created successfully */
1487  )
1488 {
1489  SCIP_CONS* cons;
1490  SCIP_VAR** consvars;
1491  SCIP_Bool isbinary;
1492  char name[SCIP_MAXSTRLEN];
1493  int i;
1494 
1495  assert(scip != NULL);
1496  assert(bdlen >= 1);
1497  assert(bdvars != NULL);
1498  assert(bdtypes != NULL);
1499  assert(bdbounds != NULL);
1500  assert(success != NULL);
1501 
1502  /* initialize */
1503  *success = FALSE;
1504  cons = NULL;
1505  consvars = NULL;
1506 
1507  /* create constraint name */
1508  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "undercover_cutoff");
1509 
1510  /* check if all variables in the cover are binary */
1511  isbinary = TRUE;
1512  for( i = bdlen-1; i >= 0 && isbinary; i-- )
1513  {
1514  isbinary = SCIPvarIsBinary(bdvars[i]);
1515  }
1516 
1517  /* if all variables in the cover are binary, then we create a logicor constraint */
1518  if( isbinary )
1519  {
1520  /* allocate memory for constraint variables */
1521  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, bdlen) );
1522 
1523  /* build up constraint */
1524  for( i = bdlen-1; i >= 0; i-- )
1525  {
1526  assert(bdtypes[i] == SCIP_BOUNDTYPE_LOWER || SCIPisFeasZero(scip, bdbounds[i]));
1527  assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER || SCIPisFeasEQ(scip, bdbounds[i], 1.0));
1528 
1529  if( bdtypes[i] == SCIP_BOUNDTYPE_LOWER )
1530  {
1531  consvars[i] = bdvars[i];
1532  }
1533  else
1534  {
1535  assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER);
1536  SCIP_CALL( SCIPgetNegatedVar(scip, bdvars[i], &consvars[i]) );
1537  }
1538  }
1539 
1540  /* create conflict constraint */
1541  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, bdlen, consvars,
1542  FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1543  }
1544  /* otherwise we create a bound disjunction constraint as given */
1545  else
1546  {
1547  /* create conflict constraint */
1548  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, bdlen, bdvars, bdtypes, bdbounds,
1549  FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1550  }
1551 
1552  /* add and release constraint if created successfully */
1553  if( cons != NULL )
1554  {
1555  if( local )
1556  {
1557  SCIP_CALL( SCIPaddConsLocal(scip, cons, NULL) );
1558  }
1559  else
1560  {
1561  SCIP_CALL( SCIPaddCons(scip, cons) );
1562  }
1563 
1564  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1565  *success = TRUE;
1566  }
1567 
1568  /* free memory */
1569  SCIPfreeBufferArrayNull(scip, &consvars);
1570 
1571  return SCIP_OKAY;
1572 }
1573 
1574 
1575 /** solve covering problem */
1576 static
1578  SCIP* coveringscip, /**< SCIP data structure for the covering problem */
1579  int ncoveringvars, /**< number of the covering problem's variables */
1580  SCIP_VAR** coveringvars, /**< array of the covering problem's variables */
1581  int* coversize, /**< size of the computed cover */
1582  int* cover, /**< array to store indices of the variables in the computed cover
1583  * (should be ready to hold ncoveringvars entries) */
1584  SCIP_Real timelimit, /**< time limit */
1585  SCIP_Real memorylimit, /**< memory limit */
1586  SCIP_Real objlimit, /**< upper bound on the cover size */
1587  SCIP_Bool* success /**< feasible cover found? */
1588  )
1589 {
1590  SCIP_Real* solvals;
1591  SCIP_Real totalpenalty;
1592  SCIP_RETCODE retcode;
1593  int i;
1594 
1595  assert(coveringscip != NULL);
1596  assert(coveringvars != NULL);
1597  assert(cover != NULL);
1598  assert(coversize != NULL);
1599  assert(timelimit > 0.0);
1600  assert(memorylimit > 0.0);
1601  assert(success != NULL);
1602 
1603  *success = FALSE;
1604 
1605  /* forbid call of heuristics and separators solving sub-CIPs */
1606  SCIP_CALL( SCIPsetSubscipsOff(coveringscip, TRUE) );
1607 
1608  /* set presolving and separation to fast */
1611 
1612  /* use inference branching */
1613  if( SCIPfindBranchrule(coveringscip, "inference") != NULL && !SCIPisParamFixed(coveringscip, "branching/inference/priority") )
1614  {
1615  SCIP_CALL( SCIPsetIntParam(coveringscip, "branching/inference/priority", INT_MAX/4) );
1616  }
1617 
1618  /* only solve root */
1619  SCIP_CALL( SCIPsetLongintParam(coveringscip, "limits/nodes", 1LL) );
1620 
1621  SCIPdebugMsg(coveringscip, "timelimit = %g, memlimit = %g\n", timelimit, memorylimit);
1622 
1623  /* set time, memory, and objective limit */
1624  SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/time", timelimit) );
1625  SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/memory", memorylimit) );
1626  SCIP_CALL( SCIPsetObjlimit(coveringscip, objlimit) );
1627 
1628  /* do not abort on CTRL-C */
1629  SCIP_CALL( SCIPsetBoolParam(coveringscip, "misc/catchctrlc", FALSE) );
1630 
1631  /* disable output to console in optimized mode, enable in SCIP's debug mode */
1632 #ifdef SCIP_DEBUG
1633  SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 5) );
1634  SCIP_CALL( SCIPsetIntParam(coveringscip, "display/freq", 100000) );
1635 #else
1636  SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 0) );
1637 #endif
1638 
1639 
1640  /* solve covering problem */
1641  retcode = SCIPsolve(coveringscip);
1642 
1643  /* errors in solving the covering problem should not kill the overall solving process;
1644  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1645  */
1646  if( retcode != SCIP_OKAY )
1647  {
1648 #ifndef NDEBUG
1649  SCIP_CALL( retcode );
1650 #endif
1651  SCIPwarningMessage(coveringscip, "Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1652  return SCIP_OKAY;
1653  }
1654 
1655  /* check, whether a feasible cover was found */
1656  if( SCIPgetNSols(coveringscip) == 0 )
1657  return SCIP_OKAY;
1658 
1659  /* store solution */
1660  SCIP_CALL( SCIPallocBufferArray(coveringscip, &solvals, ncoveringvars) );
1661  SCIP_CALL( SCIPgetSolVals(coveringscip, SCIPgetBestSol(coveringscip), ncoveringvars, coveringvars, solvals) );
1662 
1663  *coversize = 0;
1664  totalpenalty = 0.0;
1665  for( i = 0; i < ncoveringvars; i++ )
1666  {
1667  if( solvals[i] > 0.5 )
1668  {
1669  cover[*coversize] = i;
1670  (*coversize)++;
1671  }
1672  totalpenalty += SCIPvarGetObj(coveringvars[i]);
1673  }
1674 
1675  /* print solution if we are in SCIP's debug mode */
1676  assert(SCIPgetBestSol(coveringscip) != NULL);
1677  SCIPdebugMsg(coveringscip, "found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n",
1678  *coversize, SCIPgetNOrigVars(coveringscip), SCIPgetSolOrigObj(coveringscip, SCIPgetBestSol(coveringscip))/(totalpenalty+SCIPsumepsilon(coveringscip)));
1679  SCIPdebug( SCIP_CALL( SCIPprintSol(coveringscip, SCIPgetBestSol(coveringscip), NULL, FALSE) ) );
1680  SCIPdebugMsg(coveringscip, "\r \n");
1681 
1682  *success = TRUE;
1683 
1684  /* free array of solution values */
1685  SCIPfreeBufferArray(coveringscip, &solvals);
1686 
1687  return SCIP_OKAY;
1688 }
1689 
1690 
1691 /** computes fixing order and returns whether order has really been changed */
1692 static
1694  SCIP* scip, /**< original SCIP data structure */
1695  SCIP_HEURDATA* heurdata, /**< heuristic data */
1696  int nvars, /**< number of variables in the original problem */
1697  SCIP_VAR** vars, /**< variables in the original problem */
1698  int coversize, /**< size of the cover */
1699  int* cover, /**< problem indices of the variables in the cover */
1700  int lastfailed, /**< position in cover array of the variable the fixing of which yielded
1701  * infeasibility in last dive (or >= coversize, in which case *success
1702  * is always TRUE) */
1703  SCIP_Bool* success /**< has order really been changed? */
1704  )
1705 {
1706  SCIP_Real* scores;
1707  SCIP_Real bestscore;
1708  SCIP_Bool sortdown;
1709  int i;
1710 
1711  assert(scip != NULL);
1712  assert(heurdata != NULL);
1713  assert(nvars >= 1);
1714  assert(vars != NULL);
1715  assert(coversize >= 1);
1716  assert(cover != NULL);
1717  assert(lastfailed >= 0);
1718 
1719  *success = FALSE;
1720 
1721  /* if fixing the first variable had failed, do not try with another order */
1722  if( lastfailed == 0 )
1723  return SCIP_OKAY;
1724 
1725  /* allocate buffer array for score values */
1726  SCIP_CALL( SCIPallocBufferArray(scip, &scores, coversize) );
1727 
1728  /* initialize best score to infinite value */
1729  sortdown = (heurdata->fixingorder == 'c' || heurdata->fixingorder == 'v' );
1730  bestscore = sortdown ? -SCIPinfinity(scip) : +SCIPinfinity(scip);
1731 
1732  /* compute score values */
1733  for( i = coversize-1; i >= 0; i-- )
1734  {
1735  SCIP_VAR* var;
1736 
1737  /* get variable in the cover */
1738  assert(cover[i] >= 0);
1739  assert(cover[i] < nvars);
1740  var = vars[cover[i]];
1741 
1742  if( heurdata->fixingorder == 'C' || heurdata->fixingorder == 'c' )
1743  {
1744  /* add a small pertubation value to the score to reduce performance variability */
1745  scores[i] = heurdata->conflictweight * SCIPgetVarConflictScore(scip, var)
1746  + heurdata->inferenceweight * SCIPgetVarAvgInferenceCutoffScore(scip, var, heurdata->cutoffweight)
1747  + SCIPrandomGetReal(heurdata->randnumgen, 0.0, SCIPepsilon(scip));
1748  }
1749  else if( heurdata->fixingorder == 'V' || heurdata->fixingorder == 'v' )
1750  scores[i] = cover[i];
1751  else
1752  return SCIP_PARAMETERWRONGVAL;
1753 
1754  assert(scores[i] >= 0.0);
1755 
1756  /* update best score */
1757  if( sortdown )
1758  bestscore = MAX(bestscore, scores[i]);
1759  else
1760  bestscore = MIN(bestscore, scores[i]);
1761 
1762  }
1763 
1764  /* put integers to the front */
1765  if( heurdata->fixintfirst )
1766  {
1767  for( i = coversize-1; i >= 0; i-- )
1768  {
1769  if( SCIPvarIsIntegral(vars[cover[i]]) )
1770  {
1771  if( sortdown )
1772  scores[i] += bestscore+1.0;
1773  else
1774  scores[i] = bestscore - 1.0/(scores[i]+1.0);
1775  }
1776  }
1777  }
1778 
1779  /* put last failed variable to the front */
1780  if( lastfailed < coversize )
1781  {
1782  if( sortdown )
1783  scores[lastfailed] += bestscore+2.0;
1784  else
1785  scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0);
1786  i = cover[lastfailed];
1787  }
1788 
1789  /* sort by non-decreasing (negative) score */
1790  if( sortdown )
1791  SCIPsortDownRealInt(scores, cover, coversize);
1792  else
1793  SCIPsortRealInt(scores, cover, coversize);
1794 
1795  assert(lastfailed >= coversize || cover[0] == i);
1796 
1797  /* free buffer memory */
1798  SCIPfreeBufferArray(scip, &scores);
1799 
1800  *success = TRUE;
1801 
1802  return SCIP_OKAY;
1803 }
1804 
1805 
1806 /** gets fixing value */
1807 static
1809  SCIP* scip, /**< original SCIP data structure */
1810  SCIP_HEURDATA* heurdata, /**< heuristic data */
1811  SCIP_VAR* var, /**< variable in the original problem */
1812  SCIP_Real* val, /**< buffer for returning fixing value */
1813  char fixalt, /**< source of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
1814  SCIP_Bool* success, /**< could value be retrieved successfully? */
1815  int bdlen, /**< current length of probing path */
1816  SCIP_VAR** bdvars, /**< array of variables with bound changes along probing path */
1817  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
1818  SCIP_Real* oldbounds /**< array of bounds before fixing */
1819  )
1820 {
1821  assert(scip != NULL);
1822  assert(heurdata != NULL);
1823  assert(var != NULL);
1824  assert(val != NULL);
1825  assert(success != NULL);
1826 
1827  *success = FALSE;
1828 
1829  switch( fixalt )
1830  {
1831  case 'l':
1832  /* get the last LP solution value */
1833  *val = SCIPvarGetLPSol(var);
1834  *success = TRUE;
1835  break;
1836  case 'n':
1837  /* only call this function if NLP relaxation is available */
1838  assert(SCIPisNLPConstructed(scip));
1839 
1840  /* the solution values are already available */
1841  if( heurdata->nlpsolved )
1842  {
1843  assert(!heurdata->nlpfailed);
1844 
1845  /* retrieve NLP solution value */
1846  *val = SCIPvarGetNLPSol(var);
1847  *success = TRUE;
1848  }
1849  /* solve NLP relaxation unless it has not failed too often before */
1850  else if( !heurdata->nlpfailed )
1851  { /*lint --e{850}*/
1852  SCIP_NLPSOLSTAT stat;
1853  int i;
1854 
1855  /* restore bounds at start of probing, since otherwise, if in backtrack mode, NLP solver becomes most likely
1856  * locally infeasible
1857  */
1858  SCIP_CALL( SCIPstartDiveNLP(scip) );
1859 
1860  for( i = bdlen-1; i >= 0; i-- )
1861  {
1862  SCIP_VAR* relaxvar;
1863  SCIP_Real lb;
1864  SCIP_Real ub;
1865 
1866  relaxvar = bdvars[i];
1867 
1868  /* both bounds were tightened */
1869  if( i > 0 && bdvars[i-1] == relaxvar )
1870  {
1871  assert(bdtypes[i] != bdtypes[i-1]);
1872 
1873  lb = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i] : oldbounds[i-1];
1874  ub = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i-1] : oldbounds[i];
1875  i--;
1876  }
1877  /* lower bound was tightened */
1878  else if( bdtypes[i] == SCIP_BOUNDTYPE_UPPER )
1879  {
1880  lb = oldbounds[i];
1881  ub = SCIPvarGetUbLocal(relaxvar);
1882  }
1883  /* upper bound was tightened */
1884  else
1885  {
1886  lb = SCIPvarGetLbLocal(relaxvar);
1887  ub = oldbounds[i];
1888  }
1889 
1890  assert(SCIPisLE(scip, lb, SCIPvarGetLbLocal(relaxvar)));
1891  assert(SCIPisGE(scip, ub, SCIPvarGetUbLocal(relaxvar)));
1892 
1893  /* relax bounds */
1894  SCIP_CALL( SCIPchgVarBoundsDiveNLP(scip, relaxvar, lb, ub) );
1895  }
1896 
1897  /* activate NLP solver output if we are in SCIP's debug mode */
1899 
1900  /* set starting point to lp solution */
1901  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
1902 
1903  /* solve NLP relaxation */
1904  SCIP_CALL( SCIPsolveDiveNLP(scip) );
1905  stat = SCIPgetNLPSolstat(scip);
1906  *success = stat == SCIP_NLPSOLSTAT_GLOBOPT || stat == SCIP_NLPSOLSTAT_LOCOPT || stat == SCIP_NLPSOLSTAT_FEASIBLE;
1907 
1908  SCIPdebugMsg(scip, "solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ? "successful" : "failed", stat);
1909 
1910  if( *success )
1911  {
1912  /* solving succeeded */
1913  heurdata->nnlpfails = 0;
1914  heurdata->nlpsolved = TRUE;
1915 
1916  /* retrieve NLP solution value */
1917  *val = SCIPvarGetNLPSol(var);
1918  }
1919  else
1920  {
1921  /* solving failed */
1922  heurdata->nnlpfails++;
1923  heurdata->nlpfailed = TRUE;
1924  heurdata->nlpsolved = FALSE;
1925 
1926  SCIPdebugMsg(scip, "solving NLP relaxation failed (%d time%s%s)\n",
1927  heurdata->nnlpfails, heurdata->nnlpfails > 1 ? "s" : "", heurdata->nnlpfails >= MAXNLPFAILS ? ", will not be called again" : "");
1928  }
1929  }
1930  break;
1931  case 'i':
1932  /* only call this function if a feasible solution is available */
1933  assert(SCIPgetBestSol(scip) != NULL);
1934 
1935  /* get value in the incumbent solution */
1936  *val = SCIPgetSolVal(scip, SCIPgetBestSol(scip), var);
1937  *success = TRUE;
1938  break;
1939  default:
1940  break;
1941  }
1942 
1943  /* due to propagation (during probing) it might happen that the LP and NLP solution value of var might be outside of
1944  * its bounds
1945  */
1946  *val = MAX(*val, SCIPvarGetLbLocal(var)); /*lint !e666*/
1947  *val = MIN(*val, SCIPvarGetUbLocal(var)); /*lint !e666*/
1948 
1949  return SCIP_OKAY;
1950 }
1951 
1952 
1953 /** calculates up to four alternative values for backtracking, if fixing the variable failed.
1954  * The alternatives are the two bounds of the variable, and the averages of the bounds and the fixing value.
1955  * For infinite bounds, fixval +/- abs(fixval) will be used instead.
1956  */
1957 static
1959  SCIP* scip, /**< original SCIP data structure */
1960  SCIP_VAR* var, /**< variable to calculate alternatives for */
1961  SCIP_Real fixval, /**< reference fixing value */
1962  int* nalternatives, /**< number of fixing values computed */
1963  SCIP_Real* alternatives /**< array to store the alternative fixing values */
1964  )
1965 {
1966  SCIP_Real lb;
1967  SCIP_Real ub;
1968 
1969  /* for binary variables, there is only two possible fixing values */
1970  if( SCIPvarIsBinary(var) )
1971  {
1972  if( SCIPisFeasEQ(scip, fixval, 0.0) || SCIPisFeasEQ(scip, fixval, 1.0) )
1973  {
1974  alternatives[0] = 1.0 - fixval;
1975  *nalternatives = 1;
1976  }
1977  else
1978  {
1979  alternatives[0] = 0.0;
1980  alternatives[1] = 1.0;
1981  *nalternatives = 2;
1982  }
1983  return;
1984  }
1985 
1986  /* get bounds */
1987  lb = SCIPvarGetLbLocal(var);
1988  ub = SCIPvarGetUbLocal(var);
1989 
1990  /* if lower bound is infinite, use x'-|x'|; if x' is zero, use -1.0 instead */
1991  if( SCIPisInfinity(scip, -lb) )
1992  lb = SCIPisFeasZero(scip, fixval) ? -1.0 : fixval - ABS(fixval);
1993 
1994  /* if upper bound is infinite, use x'+|x'|; if x' is zero, use 1.0 instead */
1995  if( SCIPisInfinity(scip, ub) )
1996  ub = SCIPisFeasZero(scip, fixval) ? 1.0 : fixval + ABS(fixval);
1997 
1998  assert(!SCIPisEQ(scip, lb, ub));
1999 
2000  /* collect alternatives */
2001  *nalternatives = 0;
2002 
2003  /* use lower bound if not equal to x' */
2004  if( !SCIPisFeasEQ(scip, lb, fixval) )
2005  {
2006  alternatives[*nalternatives] = lb;
2007  (*nalternatives)++;
2008  }
2009 
2010  /* use upper bound if not equal to x' */
2011  if( !SCIPisFeasEQ(scip, ub, fixval) )
2012  {
2013  alternatives[*nalternatives] = ub;
2014  (*nalternatives)++;
2015  }
2016 
2017  /* use the average of x' and lower bound as alternative value, if this is not equal to any of the other values */
2018  if( !SCIPisFeasEQ(scip, lb, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, lb, fixval-1)) )
2019  {
2020  alternatives[*nalternatives] = (lb+fixval)/2.0;
2021  (*nalternatives)++;
2022  }
2023 
2024  /* use the average of x' and upper bound as alternative value, if this is not equal to any of the other values */
2025  if( !SCIPisFeasEQ(scip, ub, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, ub, fixval+1)) )
2026  {
2027  alternatives[*nalternatives] = (ub+fixval)/2.0;
2028  (*nalternatives)++;
2029  }
2030 
2031  assert(*nalternatives <= 4);
2032 
2033  return;
2034 }
2035 
2036 
2037 /** rounds the given fixing value */
2038 static
2040  SCIP* scip, /**< original SCIP data structure */
2041  SCIP_Real* val, /**< fixing value to be rounded */
2042  SCIP_VAR* var, /**< corresponding variable */
2043  SCIP_Bool locksrounding /**< shall we round according to locks? (otherwise to nearest integer) */
2044  )
2045 {
2046  SCIP_Real x;
2047 
2048  x = *val;
2049 
2050  /* if integral within feasibility tolerance, only shift to nearest integer */
2051  if( SCIPisFeasIntegral(scip, x) )
2052  x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
2053 
2054  /* round in the direction of least locks with fractionality as tie breaker */
2055  else if( locksrounding )
2056  {
2057  if( SCIPvarGetNLocksDown(var) < SCIPvarGetNLocksUp(var) )
2058  x = SCIPfeasFloor(scip, x);
2059  else if( SCIPvarGetNLocksDown(var) > SCIPvarGetNLocksUp(var) )
2060  x = SCIPfeasCeil(scip, x);
2061  else
2062  x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
2063  }
2064  /* round in the direction of least fractionality with locks as tie breaker */
2065  else
2066  {
2067  if( SCIPfeasFrac(scip, x) < 0.5)
2068  x = SCIPfeasFloor(scip, x);
2069  else if( SCIPfeasFrac(scip, x) > 0.5 )
2070  x = SCIPfeasCeil(scip, x);
2071  else
2072  x = SCIPvarGetNLocksDown(var) < SCIPvarGetNLocksUp(var) ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
2073  }
2074 
2075  /* return rounded fixing value */
2076  *val = x;
2077 
2078  return SCIP_OKAY;
2079 }
2080 
2081 
2082 /** copy the solution of the subproblem to newsol */
2083 static
2085  SCIP* scip, /**< original SCIP data structure */
2086  SCIP* subscip, /**< SCIP structure of the subproblem */
2087  SCIP_VAR** subvars, /**< the variables of the subproblem */
2088  SCIP_SOL* subsol, /**< solution of the subproblem */
2089  SCIP_SOL** newsol /**< solution to the original problem */
2090  )
2091 {
2092  SCIP_VAR** vars; /* the original problem's variables */
2093  SCIP_Real* subsolvals; /* solution values of the subproblem */
2094  int nvars;
2095 
2096  assert(scip != NULL);
2097  assert(subscip != NULL);
2098  assert(subvars != NULL);
2099  assert(subsol != NULL);
2100  assert(newsol != NULL);
2101  assert(*newsol != NULL);
2102 
2103  /* get variables' data */
2104  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2105 
2106  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
2107  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
2108  */
2109  assert(nvars <= SCIPgetNOrigVars(subscip));
2110 
2111  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
2112 
2113  /* copy the solution */
2114  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
2115  SCIP_CALL( SCIPsetSolVals(scip, *newsol, nvars, vars, subsolvals) );
2116 
2117  SCIPfreeBufferArray(scip, &subsolvals);
2118 
2119  return SCIP_OKAY;
2120 }
2121 
2122 
2123 /** solve subproblem and pass best feasible solution to original SCIP instance */
2124 static
2126  SCIP* scip, /**< SCIP data structure of the original problem */
2127  SCIP_HEUR* heur, /**< heuristic data structure */
2128  int coversize, /**< size of the cover */
2129  int* cover, /**< problem indices of the variables in the cover */
2130  SCIP_Real* fixedvals, /**< fixing values for the variables in the cover */
2131  SCIP_Real timelimit, /**< time limit */
2132  SCIP_Real memorylimit, /**< memory limit */
2133  SCIP_Longint nodelimit, /**< node limit */
2134  SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
2135  SCIP_Bool* validsolved, /**< was problem constructed from a valid copy and solved (proven optimal or infeasible)? */
2136  SCIP_SOL** sol, /**< best solution found in subproblem (if feasible); *sol must be NULL, solution will be created */
2137  SCIP_Longint* nusednodes /**< number of nodes used for solving the subproblem */
2138  )
2139 {
2140  SCIP_HEURDATA* heurdata;
2141  SCIP* subscip;
2142  SCIP_VAR** subvars;
2143  SCIP_VAR** vars;
2144  SCIP_HASHMAP* varmap;
2145  SCIP_VAR** fixedvars;
2146  int nfixedvars;
2147 
2148  SCIP_RETCODE retcode;
2149 
2150  int nvars;
2151  int i;
2152 
2153  assert(scip != NULL);
2154  assert(heur != NULL);
2155  assert(cover != NULL);
2156  assert(fixedvals != NULL);
2157  assert(coversize >= 1);
2158  assert(timelimit > 0.0);
2159  assert(memorylimit > 0.0);
2160  assert(nodelimit >= 1);
2161  assert(nstallnodes >= 1);
2162  assert(validsolved != NULL);
2163  assert(sol != NULL);
2164  assert(*sol == NULL);
2165  assert(nusednodes != NULL);
2166 
2167  *validsolved = FALSE;
2168  *nusednodes = 0;
2169 
2170  /* get heuristic data */
2171  heurdata = SCIPheurGetData(heur);
2172  assert(heurdata != NULL);
2173 
2174  /* get required data of the original problem */
2175  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2176 
2177  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, coversize) );
2178  nfixedvars = coversize;
2179  /* fix subproblem variables in the cover */
2180  SCIPdebugMsg(scip, "fixing variables\n");
2181  for( i = coversize-1; i >= 0; i-- )
2182  {
2183  assert(cover[i] >= 0);
2184  assert(cover[i] < nvars);
2185 
2186  fixedvars[i] = vars[cover[i]];
2187  }
2188 
2189  /* create subproblem */
2190  SCIP_CALL( SCIPcreate(&subscip) );
2191  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
2192 
2193  /* create the variable mapping hash map */
2194  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
2195 
2196  /* copy original problem to subproblem; do not copy pricers */
2197  SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", fixedvars, fixedvals, nfixedvars,
2198  heurdata->globalbounds, FALSE, TRUE, validsolved) );
2199 
2200  if( heurdata->copycuts )
2201  {
2202  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
2203  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, heurdata->globalbounds, NULL) );
2204  }
2205 
2206  SCIPdebugMsg(scip, "problem copied, copy %svalid\n", *validsolved ? "" : "in");
2207 
2208  /* store subproblem variables */
2209  for( i = nvars-1; i >= 0; i-- )
2210  {
2211  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
2212  assert(subvars[i] != NULL);
2213  }
2214 
2215  /* free variable mapping hash map */
2216  SCIPhashmapFree(&varmap);
2217 
2218  /* set the parameters such that good solutions are found fast */
2219  SCIPdebugMsg(scip, "setting subproblem parameters\n");
2223 
2224  /* deactivate expensive pre-root heuristics, since it may happen that the lp relaxation of the subproblem is already
2225  * infeasible; in this case, we do not want to waste time on heuristics before solving the root lp */
2226  if( !SCIPisParamFixed(subscip, "heuristics/shiftandpropagate/freq") )
2227  {
2228  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shiftandpropagate/freq", -1) );
2229  }
2230 
2231  /* forbid recursive call of undercover heuristic */
2232  if( SCIPisParamFixed(subscip, "heuristics/" HEUR_NAME "/freq") )
2233  {
2234  SCIPwarningMessage(scip, "unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n");
2235  SCIP_CALL( SCIPunfixParam(subscip, "heuristics/" HEUR_NAME "/freq") );
2236  }
2237  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/" HEUR_NAME "/freq", -1) );
2238 
2239  SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
2240 
2241  SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
2242 
2243  /* disable statistic timing inside sub SCIP */
2244  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2245 
2246  /* set time, memory and node limits */
2247  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
2248  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
2249  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
2250  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
2251 
2252  /* do not abort subproblem on CTRL-C */
2253  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2254 
2255  /* disable output to console in optimized mode, enable in SCIP's debug mode */
2256 #ifdef SCIP_DEBUG
2257  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2258  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000) );
2259 #else
2260  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2261 #endif
2262 
2263  /* if there is already a solution, add an objective cutoff; note: this does not affect the validity of the subproblem
2264  * if we find solutions later, thus we do not set *validsolved to FALSE */
2265  if( SCIPgetNSols(scip) > 0 )
2266  {
2267  SCIP_Real cutoff;
2268  SCIP_Real upperbound;
2269 
2270  assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
2271  upperbound = SCIPgetUpperbound(scip);
2272 
2273  if( SCIPisInfinity(scip, -SCIPgetLowerbound(scip)) )
2274  cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound;
2275  else
2276  cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove * SCIPgetLowerbound(scip);
2277 
2278  cutoff = MIN(upperbound, cutoff);
2279  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
2280 
2281  SCIPdebugMsg(scip, "adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove);
2282  }
2283 
2284  /* solve subproblem */
2285  SCIPdebugMsg(scip, "solving subproblem started\n");
2286  retcode = SCIPsolve(subscip);
2287 
2288  /* Errors in solving the subproblem should not kill the overall solving process
2289  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2290  */
2291  if( retcode != SCIP_OKAY )
2292  {
2293 #ifndef NDEBUG
2294  SCIP_CALL( retcode );
2295 #endif
2296  SCIPwarningMessage(scip, "Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
2297  /* free array of subproblem variables, and subproblem */
2298  SCIPfreeBufferArray(scip, &subvars);
2299  SCIPfreeBufferArray(scip, &fixedvars);
2300  SCIP_CALL( SCIPfree(&subscip) );
2301  return SCIP_OKAY;
2302  }
2303 
2304  /* print solving statistics of subproblem if we are in SCIP's debug mode */
2305  SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
2306 
2307  /* store solving status; note: if we proved infeasibility in presence of an objective cutoff beyond the primal bound,
2308  * the subproblem was not a valid copy */
2309  *validsolved = *validsolved && (SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL
2310  || (SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE && (SCIPgetNSols(scip) == 0 || heurdata->minimprove <= 0.0)));
2311  *nusednodes = SCIPgetNNodes(subscip);
2312 
2313  /* if a solution was found for the subproblem, create corresponding solution in the original problem */
2314  if( SCIPgetNSols(subscip) > 0 && (SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE || heurdata->minimprove > 0.0) )
2315  {
2316  SCIP_SOL** subsols;
2317  SCIP_Bool success;
2318  int nsubsols;
2319 
2320  /* create solution */
2321  SCIP_CALL( SCIPcreateSol(scip, sol, heur) );
2322 
2323  /* check, whether a solution was found;
2324  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
2325  nsubsols = SCIPgetNSols(subscip);
2326  subsols = SCIPgetSols(subscip);
2327  assert(subsols != NULL);
2328 
2329  success = FALSE;
2330  for( i = 0; i < nsubsols && !success; i++ )
2331  {
2332  /* transform solution to original problem */
2333  SCIP_CALL( copySol(scip, subscip, subvars, subsols[i], sol) );
2334 
2335  /* try to add new solution to scip */
2336  SCIP_CALL( SCIPtrySol(scip, *sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2337  }
2338 
2339  if( success )
2340  {
2341  assert(i >= 1);
2342  SCIPdebugMsg(scip, "heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i);
2343  }
2344  else
2345  {
2346  /* free solution structure, since we found no feasible solution */
2347  SCIP_CALL( SCIPfreeSol(scip, sol) );
2348  *sol = NULL;
2349  }
2350 
2351  /* if the best subproblem solution was not accepted in the original problem, we do not trust the solving status */
2352  *validsolved = *validsolved && i == 1;
2353  }
2354 
2355  if( *validsolved )
2356  {
2357  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
2358  }
2359 
2360  /* free array of subproblem variables, and subproblem */
2361  SCIPfreeBufferArray(scip, &subvars);
2362  SCIPfreeBufferArray(scip, &fixedvars);
2363  SCIP_CALL( SCIPfree(&subscip) );
2364 
2365  return SCIP_OKAY;
2366 }
2367 
2368 
2369 /** perform fixing of a variable and record bound disjunction information */
2370 static
2372  SCIP* scip, /**< SCIP data structure */
2373  SCIP_VAR* var, /**< variable to fix */
2374  SCIP_Real val, /**< fixing value */
2375  SCIP_Bool* infeas, /**< pointer to store whether the fixing lead to infeasibility */
2376  int* bdlen, /**< current length of bound disjunction */
2377  SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
2378  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
2379  SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
2380  SCIP_Real* oldbounds /**< array of bounds before fixing */
2381  )
2382 {
2383  SCIP_Longint ndomredsfound;
2384  SCIP_Real oldlb;
2385  SCIP_Real oldub;
2386  int oldbdlen;
2387 
2388  assert(scip != NULL);
2389  assert(var != NULL);
2390  assert(val >= SCIPvarGetLbLocal(var));
2391  assert(val <= SCIPvarGetUbLocal(var));
2392  assert(infeas != NULL);
2393  assert(bdlen != NULL);
2394  assert(*bdlen >= 0);
2395  assert(*bdlen < 2*SCIPgetNVars(scip)-1);
2396  assert(bdvars != NULL);
2397  assert(bdtypes != NULL);
2398  assert(bdbounds != NULL);
2399 
2400  assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val));
2401 
2402  /* remember length of probing path */
2403  oldbdlen = *bdlen;
2404 
2405  /* get bounds of the variable to fix */
2406  oldlb = SCIPvarGetLbLocal(var);
2407  oldub = SCIPvarGetUbLocal(var);
2408 
2409  /* decrease upper bound to fixing value */
2410  *infeas = FALSE;
2411  if( SCIPisUbBetter(scip, val, oldlb, oldub) )
2412  {
2413  /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2414  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
2415  {
2416  /* create next probing node */
2417  SCIP_CALL( SCIPnewProbingNode(scip) );
2418  }
2419  SCIP_CALL( SCIPchgVarUbProbing(scip, var, val) );
2420 
2421  SCIPdebugMsg(scip, "tentatively decreasing upper bound of variable <%s> to %g for probing\n",
2422  SCIPvarGetName(var), val);
2423 
2424  /* store bound disjunction information */
2425  bdvars[*bdlen] = var;
2426  bdtypes[*bdlen] = SCIP_BOUNDTYPE_LOWER;
2427  bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)+1.0 : val;
2428  oldbounds[*bdlen] = oldub;
2429  (*bdlen)++;
2430 
2431  /* propagate the bound change; conflict analysis is performed automatically */
2432  SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2433  SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2434 
2435  /* if propagation led to a cutoff, we backtrack immediately */
2436  if( *infeas )
2437  {
2438  *bdlen = oldbdlen;
2439  return SCIP_OKAY;
2440  }
2441 
2442  /* store bound before propagation */
2443  oldbounds[*bdlen] = oldlb;
2444 
2445  /* move fixing value into the new domain, since it may be outside due to numerical issues or previous propagation */
2446  oldlb = SCIPvarGetLbLocal(var);
2447  oldub = SCIPvarGetUbLocal(var);
2448  val = MIN(val, oldub);
2449  val = MAX(val, oldlb);
2450 
2451  assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val));
2452  }
2453 
2454  /* update lower bound to fixing value */
2455  *infeas = FALSE;
2456  if( SCIPisLbBetter(scip, val, oldlb, oldub) )
2457  {
2458  /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2459  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
2460  {
2461  /* create next probing node */
2462  SCIP_CALL( SCIPnewProbingNode(scip) );
2463  }
2464  SCIP_CALL( SCIPchgVarLbProbing(scip, var, val) );
2465 
2466  SCIPdebugMsg(scip, "tentatively increasing lower bound of variable <%s> to %g for probing\n",
2467  SCIPvarGetName(var), val);
2468 
2469  /* store bound disjunction information */
2470  bdvars[*bdlen] = var;
2471  bdtypes[*bdlen] = SCIP_BOUNDTYPE_UPPER;
2472  bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)-1.0 : val;
2473  (*bdlen)++;
2474 
2475  /* propagate the bound change */
2476  SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2477  SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2478 
2479  /* if propagation led to a cutoff, we backtrack immediately */
2480  if( *infeas )
2481  {
2482  *bdlen = oldbdlen;
2483  return SCIP_OKAY;
2484  }
2485  }
2486 
2487  return SCIP_OKAY;
2488 }
2489 
2490 static
2492  SCIP* scip, /**< original SCIP data structure */
2493  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
2494  int* cover, /**< array with indices of the variables in the computed cover */
2495  int coversize, /**< size of the cover */
2496  SCIP_Real* fixingvals, /**< fixing values for the variables in the cover */
2497  int* bdlen, /**< current length of bound disjunction along the probing path */
2498  SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
2499  SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
2500  SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
2501  SCIP_Real* oldbounds, /**< array of bounds before fixing */
2502  int* nfixedints, /**< pointer to store number of fixed integer variables */
2503  int* nfixedconts, /**< pointer to store number of fixed continuous variables */
2504  int* lastfailed, /**< position in cover array of the variable the fixing of which yielded
2505  * infeasibility */
2506  SCIP_Bool* infeas /**< pointer to store whether fix-and-propagate led to an infeasibility */
2507  )
2508 {
2509  SCIP_VAR** vars; /* original problem's variables */
2510 
2511  int i;
2512  SCIP_Bool lpsolved;
2513 
2514  /* start probing in original problem */
2515  lpsolved = SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL;
2516  SCIP_CALL( SCIPstartProbing(scip) );
2517 
2518  /* initialize data */
2519  *nfixedints = 0;
2520  *nfixedconts = 0;
2521  *bdlen = 0;
2522  vars = SCIPgetVars(scip);
2523 
2524  /* round-fix-propagate-analyze-backtrack for each variable in the cover */
2525  for( i = 0; i < coversize && !(*infeas); i++ )
2526  {
2527  SCIP_Real* boundalts;
2528  SCIP_Real* usedvals;
2529  SCIP_Real val;
2530  int nbacktracks;
2531  int nboundalts;
2532  int nfailedvals;
2533  int nusedvals;
2534  int probingdepth;
2535  int idx;
2536 
2537  /* get probindex of next variable in the cover */
2538  idx = cover[i];
2539 
2540  /* nothing to do if the variable was already fixed, e.g., by propagation */
2541  if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[idx]), SCIPvarGetUbLocal(vars[idx])) )
2542  {
2543  fixingvals[i] = SCIPvarGetLbLocal(vars[idx]);
2544  continue;
2545  }
2546 
2547  /* we will store the fixing values already used to avoid try the same value twice */
2548  SCIP_CALL( SCIPallocBufferArray(scip, &usedvals, heurdata->maxbacktracks+1) );
2549  nusedvals = 0;
2550 
2551  /* backtracking loop */
2552  *infeas = TRUE;
2553  nfailedvals = 0;
2554  nboundalts = 0;
2555  boundalts = NULL;
2556  val = 0.0;
2557  for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ )
2558  {
2559  SCIP_Real oldlb;
2560  SCIP_Real oldub;
2561  SCIP_Bool usedbefore;
2562  int j;
2563 
2564  probingdepth = SCIPgetProbingDepth(scip);
2565 
2566  /* get fixing value */
2567  if( nbacktracks < heurdata->nfixingalts )
2568  {
2569  SCIP_Bool success;
2570 
2571  /* if the lp relaxation is not solved, we do not even try to retrieve the lp solution value;
2572  * if the NLP relaxation is not constructed, we do not even try to retrieve the NLP solution value;
2573  * if there is no feasible solution yet, we do not even try to obtain the value in the incumbent */
2574  success = FALSE;
2575  if( (heurdata->fixingalts[nbacktracks] != 'l' || lpsolved)
2576  && (heurdata->fixingalts[nbacktracks] != 'n' || !heurdata->nlpfailed)
2577  && (heurdata->fixingalts[nbacktracks] != 'i' || SCIPgetBestSol(scip) != NULL) )
2578  {
2579  SCIP_CALL( getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) );
2580  }
2581 
2582  if( !success )
2583  {
2584  SCIPdebugMsg(scip, "retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n",
2585  heurdata->fixingalts[nbacktracks], SCIPvarGetName(vars[idx]));
2586  nfailedvals++;
2587  continue;
2588  }
2589 
2590  /* for the first (successfully retrieved) fixing value, compute (at most 4) bound dependent
2591  * alternative fixing values */
2592  if( boundalts == NULL )
2593  {
2594  SCIP_CALL( SCIPallocBufferArray(scip, &boundalts, 4) );
2595  nboundalts = 0;
2596  calculateAlternatives(scip, vars[idx], val, &nboundalts, boundalts);
2597  assert(nboundalts >= 0);
2598  assert(nboundalts <= 4);
2599  }
2600  }
2601  /* get alternative fixing value */
2602  else if( boundalts != NULL && nbacktracks < heurdata->nfixingalts+nboundalts )
2603  {
2604  assert(nbacktracks-heurdata->nfixingalts >= 0);
2605  val = boundalts[nbacktracks-heurdata->nfixingalts];
2606  }
2607  else
2608  break;
2609 
2610  /* round fixing value */
2611  if( SCIPvarIsIntegral(vars[idx]) && !SCIPisIntegral(scip, val) )
2612  {
2613  SCIP_CALL( roundFixingValue(scip, &val, vars[idx], heurdata->locksrounding) );
2614  assert(SCIPisIntegral(scip, val));
2615  }
2616 
2617  /* move value into the domain, since it may be outside due to numerical issues or previous propagation */
2618  oldlb = SCIPvarGetLbLocal(vars[idx]);
2619  oldub = SCIPvarGetUbLocal(vars[idx]);
2620  val = MIN(val, oldub);
2621  val = MAX(val, oldlb);
2622 
2623  assert(!SCIPvarIsIntegral(vars[idx]) || SCIPisFeasIntegral(scip, val));
2624 
2625  /* check if this fixing value was already used */
2626  usedbefore = FALSE;
2627  for( j = nusedvals-1; j >= 0 && !usedbefore; j-- )
2628  usedbefore = SCIPisFeasEQ(scip, val, usedvals[j]);
2629 
2630  if( usedbefore )
2631  {
2632  nfailedvals++;
2633  continue;
2634  }
2635 
2636  /* store fixing value */
2637  assert(nusedvals < heurdata->maxbacktracks);
2638  usedvals[nusedvals] = val;
2639  nusedvals++;
2640 
2641  /* fix-propagate-analyze */
2642  SCIP_CALL( performFixing(scip, vars[idx], val, infeas, bdlen, bdvars, bdtypes, bdbounds, oldbounds) );
2643 
2644  /* if infeasible, backtrack and try alternative fixing value */
2645  if( *infeas )
2646  {
2647  SCIPdebugMsg(scip, " --> cutoff detected - backtracking\n");
2648  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2649  }
2650  }
2651 
2652  /* free array of alternative backtracking values */
2653  if( boundalts != NULL)
2654  SCIPfreeBufferArray(scip, &boundalts);
2655  SCIPfreeBufferArray(scip, &usedvals);
2656 
2657  /* backtracking loop unsuccessful */
2658  if( *infeas )
2659  {
2660  SCIPdebugMsg(scip, "no feasible fixing value found for variable <%s> in fixing order\n",
2661  SCIPvarGetName(vars[idx]));
2662  break;
2663  }
2664  /* fixing successful */
2665  else
2666  {
2667  /* store successful fixing value */
2668  fixingvals[i] = val;
2669 
2670  /* statistics */
2671  if( SCIPvarGetType(vars[idx]) == SCIP_VARTYPE_CONTINUOUS )
2672  (*nfixedconts)++;
2673  else
2674  (*nfixedints)++;
2675  }
2676  }
2677  assert(*infeas || i == coversize);
2678  assert(!(*infeas) || i < coversize);
2679 
2680  /* end of dive */
2681  SCIP_CALL( SCIPendProbing(scip) );
2682 
2683  *lastfailed = i;
2684 
2685  return SCIP_OKAY;
2686 }
2687 
2688 /** main procedure of the undercover heuristic */
2689 static
2691  SCIP* scip, /**< original SCIP data structure */
2692  SCIP_HEUR* heur, /**< heuristic data structure */
2693  SCIP_RESULT* result, /**< result data structure */
2694  SCIP_Real timelimit, /**< time limit */
2695  SCIP_Real memorylimit, /**< memory limit */
2696  SCIP_Longint nstallnodes /**< number of stalling nodes for the subproblem */
2697  )
2698 {
2699  SCIP_HEURDATA* heurdata; /* heuristic data */
2700  SCIP_VAR** vars; /* original problem's variables */
2701  SCIP_CLOCK* clock; /* clock for updating time limit */
2702 
2703  SCIP* coveringscip; /* SCIP data structure for covering problem */
2704  SCIP_VAR** coveringvars; /* covering variables */
2705  SCIP_Real* fixingvals; /* array for storing fixing values used */
2706  int* cover; /* array to store problem indices of variables in the computed cover */
2707 
2708  SCIP_VAR** bdvars; /* array of variables in bound disjunction along the probing path */
2709  SCIP_BOUNDTYPE* bdtypes; /* array of bound types in bound disjunction along the probing path */
2710  SCIP_Real* bdbounds; /* array of bounds in bound disjunction along the probing path */
2711  SCIP_Real* oldbounds; /* array of bounds before fixing along the probing path */
2712 
2713  SCIP_Real maxcoversize;
2714 
2715  int coversize;
2716  int nvars;
2717  int ncovers;
2718  int nunfixeds;
2719  int nnlconss;
2720  int i;
2721 
2722  SCIP_Bool success;
2723  SCIP_Bool reusecover;
2724 
2725  assert(scip != NULL);
2726  assert(heur != NULL);
2727  assert(result != NULL);
2728  assert(*result == SCIP_DIDNOTFIND);
2729 
2730  /* create and start timing */
2731  SCIP_CALL( SCIPcreateClock(scip, &clock) );
2732  SCIP_CALL( SCIPstartClock(scip, clock) );
2733 
2734  /* initialize */
2735  fixingvals = NULL;
2736  cover = NULL;
2737  bdvars = NULL;
2738  bdtypes = NULL;
2739  bdbounds = NULL;
2740  oldbounds = NULL;
2741  coversize = 0;
2742 
2743  /* get heuristic data */
2744  heurdata = SCIPheurGetData(heur);
2745  assert(heurdata != NULL);
2746 
2747  /* NLP relaxation has not been solved yet (only solve once, not again for each cover or dive, because it is expensive) */
2748  heurdata->nlpsolved = FALSE;
2749 
2750  /* if solving the NLP relaxation has failed too often in previous runs, or NLP and NLP solver is not available, we do
2751  * not even try
2752  */
2753  heurdata->nlpfailed = heurdata->nnlpfails >= MAXNLPFAILS || !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0;
2754 
2755  /* get variable data of original problem */
2756  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2757 
2758  /* get number of nonlinear constraints */
2759  nnlconss = 0;
2760  for( i = 0; i < heurdata->nnlconshdlrs; ++i )
2761  nnlconss += SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[i]);
2762  assert(nnlconss >= 0);
2763  assert(nnlconss <= SCIPgetNConss(scip));
2764 
2765  /* run only if problem is sufficiently nonlinear */
2766  if( nnlconss < (SCIP_Real) SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs )
2767  {
2768  SCIPdebugMsg(scip, "too few nonlinear constraints present, not running\n");
2769 
2770  /* free clock */
2771  SCIP_CALL( SCIPfreeClock(scip, &clock) );
2772 
2773  return SCIP_OKAY;
2774  }
2775 
2776  /* calculate upper bound for cover size */
2777  maxcoversize = nvars*heurdata->maxcoversizevars;
2778  if( heurdata->maxcoversizeconss < SCIP_REAL_MAX )
2779  {
2780  SCIP_Real maxcoversizeconss;
2781  maxcoversizeconss = heurdata->maxcoversizeconss * nnlconss / ((SCIP_Real) SCIPgetNConss(scip));
2782  maxcoversize = MIN(maxcoversize, maxcoversizeconss);
2783  }
2784 
2785  /* create covering problem */
2786  success = FALSE;
2787  SCIP_CALL( SCIPcreate(&coveringscip) );
2788  SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) );
2789  SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) );
2790  SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, heurdata->globalbounds, heurdata->onlyconvexify,
2791  heurdata->coverbd, heurdata->coveringobj, &success) );
2792 
2793  if( !success )
2794  {
2795  SCIPdebugMsg(scip, "creating covering problem failed, terminating\n");
2796  goto TERMINATE;
2797  }
2798  else
2799  {
2800  SCIPdebugMsg(scip, "covering problem created successfully\n");
2801  }
2802 
2803  /* count number of unfixed covering variables */
2804  nunfixeds = 0;
2805  for( i = nvars-1; i >= 0; i-- )
2806  {
2807  if( SCIPisFeasEQ(coveringscip, SCIPvarGetLbGlobal(coveringvars[i]), 1.0) )
2808  nunfixeds++;
2809  }
2810 
2811  /* update time limit */
2812  SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2813 
2814  if( timelimit <= MINTIMELEFT )
2815  {
2816  SCIPdebugMsg(scip, "time limit hit, terminating\n");
2817  goto TERMINATE;
2818  }
2819 
2820  /* update memory left */
2821  memorylimit -= SCIPgetMemUsed(coveringscip)/1048576.0;
2822  memorylimit -= SCIPgetMemExternEstim(coveringscip)/1048576.0;
2823 
2824  /* allocate memory for storing bound disjunction information along probing path */
2825  SCIP_CALL( SCIPallocBufferArray(scip, &bdvars, 2*nvars) );
2826  SCIP_CALL( SCIPallocBufferArray(scip, &bdtypes, 2*nvars) );
2827  SCIP_CALL( SCIPallocBufferArray(scip, &bdbounds, 2*nvars) );
2828  SCIP_CALL( SCIPallocBufferArray(scip, &oldbounds, 2*nvars) );
2829 
2830  /* initialize data for recovering loop */
2831  SCIP_CALL( SCIPallocBufferArray(scip, &cover, nvars) );
2832  SCIP_CALL( SCIPallocBufferArray(scip, &fixingvals, nvars) );
2833  ncovers = 0;
2834  success = FALSE;
2835  reusecover = FALSE;
2836 
2837  heurdata->nfixingalts = (int) strlen(heurdata->fixingalts);
2838  assert(heurdata->nfixingalts >= 1);
2839 
2840  /* recovering loop */
2841  while( (ncovers <= heurdata->maxrecovers || reusecover) && !success )
2842  {
2843  int lastfailed;
2844  int ndives;
2845  int nfixedints;
2846  int nfixedconts;
2847  int bdlen; /* current length of bound disjunction along the probing path */
2848 
2849  SCIP_Bool conflictcreated;
2850 
2851  SCIPdebugMsg(scip, "solving covering problem\n\n");
2852  success = FALSE;
2853  bdlen = 0;
2854  conflictcreated = FALSE;
2855 
2856  /* solve covering problem */
2857  if( !reusecover )
2858  {
2859  SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, &coversize, cover,
2860  timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, maxcoversize, &success) );
2861 
2862  SCIPstatistic(
2863  if( ncovers == 0 && success )
2864  SCIPstatisticPrintf("UCstats coversize abs: %6d rel: %9.6f\n", coversize, 100.0*coversize /(SCIP_Real)nvars);
2865  );
2866 
2867  assert(coversize >= 0);
2868  assert(coversize <= nvars);
2869  ncovers++;
2870 
2871  /* free transformed covering problem immediately */
2872  SCIP_CALL( SCIPfreeTransform(coveringscip) );
2873 
2874  /* terminate if no feasible cover was found */
2875  if( !success )
2876  {
2877  SCIPdebugMsg(scip, "no feasible cover found in covering problem %d, terminating\n", ncovers);
2878  goto TERMINATE;
2879  }
2880 
2881  /* terminate, if cover is empty or too large */
2882  if( coversize == 0 || coversize > maxcoversize )
2883  {
2884  SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2885  goto TERMINATE;
2886  }
2887 
2888  /* terminate, if cover too large for the ratio of nonlinear constraints */
2889  if( heurdata->maxcoversizeconss < SCIP_REAL_MAX && coversize > heurdata->maxcoversizeconss * nnlconss / (SCIP_Real) SCIPgetNConss(scip) )
2890  {
2891  SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2892  goto TERMINATE;
2893  }
2894  }
2895 
2896  /* data setup */
2897  ndives = 0;
2898  nfixedints = 0;
2899  nfixedconts = 0;
2900  success = FALSE;
2901  lastfailed = reusecover ? MAX(1, coversize-1) : coversize;
2902 
2903  /* round-fix-propagate-analyze-backtrack-reorder loop */
2904  while( ndives <= heurdata->maxreorders && !success )
2905  {
2906  SCIP_Bool reordered;
2907  SCIP_Bool infeas;
2908 
2909  /* compute fixing order */
2910  SCIP_CALL( computeFixingOrder(scip, heurdata, nvars, vars, coversize, cover, lastfailed, &reordered) );
2911  reordered = reordered || ndives == 0;
2912  SCIPdebugMsg(scip, "%sordering variables in cover %s\n", ndives == 0 ? "" : "re", reordered ? "" : "failed");
2913 
2914  /* stop if order has not changed */
2915  if( !reordered )
2916  break;
2917 
2918  infeas = FALSE;
2919  SCIP_CALL( fixAndPropagate(scip, heurdata, cover, coversize, fixingvals, &bdlen, bdvars, bdtypes, bdbounds, oldbounds,
2920  &nfixedints, &nfixedconts, &lastfailed, &infeas) );
2921  ndives++;
2922  success = !infeas;
2923  }
2924 
2925  /* update time limit */
2926  SCIPdebugMsg(scip, "%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ? "s" : "", ncovers, SCIPgetClockTime(scip, clock));
2927  SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2928 
2929  if( timelimit <= MINTIMELEFT )
2930  {
2931  SCIPdebugMsg(scip, "time limit hit, terminating\n");
2932  goto TERMINATE;
2933  }
2934 
2935  /* no feasible fixing could be found for the current cover */
2936  if( !success )
2937  {
2938  SCIPdebugMsg(scip, "no feasible fixing values found for cover %d\n", ncovers);
2939  }
2940  else
2941  {
2942  SCIP_SOL* sol;
2943  SCIP_Longint nsubnodes;
2944  SCIP_Bool validsolved;
2945 
2946  SCIPdebugMsg(scip, "heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n",
2947  nfixedints+nfixedconts, nfixedints, nfixedconts); /*lint !e771*/
2948 
2949  /* solve sub-CIP and pass feasible solutions to original problem */
2950  success = FALSE;
2951  validsolved = FALSE;
2952  sol = NULL;
2953  nsubnodes = 0;
2954 
2955  SCIP_CALL( solveSubproblem(scip, heur, coversize, cover, fixingvals,
2956  timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) );
2957 
2958  /* update number of sub-CIP nodes used by heuristic so far */
2959  heurdata->nusednodes += nsubnodes;
2960 
2961  /* if the subproblem was constructed from a valid copy and solved, try to forbid the assignment of fixing
2962  * values to variables in the cover
2963  */
2964  if( validsolved )
2965  {
2966  SCIP_Real maxvarsfac;
2967  SCIP_Bool useconf;
2968  int minmaxvars;
2969 
2970  SCIP_CALL( SCIPgetIntParam(scip, "conflict/minmaxvars", &minmaxvars) );
2971  SCIP_CALL( SCIPgetRealParam(scip, "conflict/maxvarsfac", &maxvarsfac) );
2972 
2973  useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars);
2974 
2975  if( useconf )
2976  {
2977  /* even if we had reset the global bounds at start of probing, the constraint might be only locally valid due to local constraints/cuts */
2978  SCIP_CALL( createConflict(scip, bdlen, bdvars, bdtypes, bdbounds, SCIPgetDepth(scip) > 0, TRUE, TRUE, &success) );
2979  conflictcreated = success;
2980  }
2981 
2982  SCIPdebugMsg(scip, "subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n",
2983  sol == NULL ? "infeasible" : "optimal",
2984  success ? "successful" : "failed", useconf ? "" : "skipped due to ", bdlen);
2985  }
2986 
2987  /* heuristic succeeded */
2988  success = (sol != NULL);
2989  if( success )
2990  {
2991  *result = SCIP_FOUNDSOL;
2992  success = TRUE;
2993 
2994  /* update time limit */
2995  SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2996 
2997  /* call NLP local search heuristic unless it has failed too often */
2998  if( heurdata->postnlp && heurdata->npostnlpfails < MAXPOSTNLPFAILS )
2999  {
3000  if( nfixedconts == 0 && validsolved )
3001  {
3002  SCIPdebugMsg(scip, "subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n");
3003  }
3004  else if( timelimit <= MINTIMELEFT )
3005  {
3006  SCIPdebugMsg(scip, "time limit hit, skipping NLP local search\n");
3007  }
3008  else if( heurdata->nlpheur == NULL )
3009  {
3010  SCIPdebugMsg(scip, "NLP heuristic not found, skipping NLP local search\n");
3011  }
3012  else
3013  {
3014  SCIP_RESULT nlpresult;
3015 
3016  SCIP_CALL( SCIPapplyHeurSubNlp(scip, heurdata->nlpheur, &nlpresult, sol, -1LL, timelimit, heurdata->minimprove, NULL, NULL) );
3017  SCIPdebugMsg(scip, "NLP local search %s\n", nlpresult == SCIP_FOUNDSOL ? "successful" : "failed");
3018 
3019  if( nlpresult == SCIP_FOUNDSOL )
3020  heurdata->npostnlpfails = 0;
3021  else
3022  heurdata->npostnlpfails++;
3023  }
3024  }
3025 
3026  /* free solution */
3027  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3028  }
3029  }
3030 
3031  /* heuristic failed but we have another recovering try, hence we forbid the current cover in the covering problem */
3032  if( !success && ncovers <= heurdata->maxrecovers )
3033  {
3034  SCIP_Bool infeas;
3035  int diversification;
3036 
3037  /* compute minimal number of unfixed covering variables (in the cover) which have to change their value */
3038  diversification = (int) SCIPfeasCeil(scip, (heurdata->recoverdiv) * (SCIP_Real) nunfixeds);
3039  diversification = MAX(diversification, 1);
3040 
3041  /* forbid unsuccessful cover globally in covering problem */
3042  SCIP_CALL( forbidCover(coveringscip, nvars, coveringvars, coversize, cover, diversification, &success, &infeas) );
3043 
3044  if( infeas )
3045  {
3046  SCIPdebugMsg(scip, "recovering problem infeasible (diversification=%d), terminating\n", diversification);
3047  goto TERMINATE;
3048  }
3049  else if( !success )
3050  {
3051  SCIPdebugMsg(scip, "failed to forbid current cover in the covering problem, terminating\n");
3052  goto TERMINATE;
3053  }
3054  else
3055  {
3056  SCIPdebugMsg(scip, "added constraint to the covering problem in order to forbid current cover\n");
3057  success = FALSE;
3058  }
3059  }
3060 
3061  /* try to re-use the same cover at most once */
3062  if( heurdata->reusecover && !reusecover && conflictcreated )
3063  reusecover = TRUE;
3064  else
3065  reusecover = FALSE;
3066  }
3067 
3068  TERMINATE:
3069  if( *result != SCIP_FOUNDSOL && *result != SCIP_DELAYED )
3070  {
3071  SCIPdebugMsg(scip, "heuristic terminating unsuccessfully\n");
3072  }
3073 
3074  /* we must remain in NLP diving mode until here to be able to retrieve NLP solution values easily */
3075  /* assert((SCIPisNLPConstructed(scip) == FALSE && heurdata->nlpsolved == FALSE) ||
3076  * (SCIPisNLPConstructed(scip) == TRUE && heurdata->nlpsolved == SCIPnlpIsDiving(SCIPgetNLP(scip))));
3077  */
3078  if( heurdata->nlpsolved )
3079  {
3080  SCIP_CALL( SCIPendDiveNLP(scip) );
3081  }
3082 
3083  /* free arrays for storing the cover */
3084  SCIPfreeBufferArrayNull(scip, &fixingvals);
3085  SCIPfreeBufferArrayNull(scip, &cover);
3086 
3087  /* free arrays for storing bound disjunction information along probing path */
3088  SCIPfreeBufferArrayNull(scip, &oldbounds);
3089  SCIPfreeBufferArrayNull(scip, &bdbounds);
3090  SCIPfreeBufferArrayNull(scip, &bdtypes);
3091  SCIPfreeBufferArrayNull(scip, &bdvars);
3092 
3093  /* free covering problem */
3094  for( i = nvars-1; i >= 0; i-- )
3095  {
3096  SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) );
3097  }
3098  SCIPfreeBufferArray(scip, &coveringvars);
3099  SCIP_CALL( SCIPfree(&coveringscip) );
3100 
3101  /* free clock */
3102  SCIP_CALL( SCIPfreeClock(scip, &clock) );
3103 
3104  return SCIP_OKAY;
3105 }
3106 
3107 
3108 /*
3109  * Callback methods of primal heuristic
3110  */
3111 
3112 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
3113 static
3114 SCIP_DECL_HEURCOPY(heurCopyUndercover)
3115 { /*lint --e{715}*/
3116  assert(scip != NULL);
3117  assert(heur != NULL);
3118  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
3119 
3120  /* call inclusion method of primal heuristic */
3122 
3123  return SCIP_OKAY;
3124 }
3125 
3126 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
3127 static
3128 SCIP_DECL_HEURFREE(heurFreeUndercover)
3129 { /*lint --e{715}*/
3130  SCIP_HEURDATA* heurdata;
3131 
3132  assert(scip != NULL);
3133  assert(heur != NULL);
3134 
3135  /* get heuristic data */
3136  heurdata = SCIPheurGetData(heur);
3137  assert(heurdata != NULL);
3138 
3139  /* free heuristic data */
3140  SCIPfreeBlockMemory(scip, &heurdata);
3141  SCIPheurSetData(heur, NULL);
3142 
3143  return SCIP_OKAY;
3144 }
3145 
3146 /** initialization method of primal heuristic (called after problem was transformed) */
3147 static
3148 SCIP_DECL_HEURINIT(heurInitUndercover)
3149 { /*lint --e{715}*/
3150  SCIP_HEURDATA* heurdata;
3151 
3152  assert(heur != NULL);
3153  assert(scip != NULL);
3154 
3155  /* get heuristic's data */
3156  heurdata = SCIPheurGetData(heur);
3157  assert(heurdata != NULL);
3158 
3159  /* create random number generator */
3160  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
3161  DEFAULT_RANDSEED) );
3162 
3163  return SCIP_OKAY;
3164 }
3165 
3166 /** deinitialization method of primal heuristic */
3167 static
3168 SCIP_DECL_HEUREXIT(heurExitUndercover)
3169 { /*lint --e{715}*/
3170  SCIP_HEURDATA* heurdata;
3171 
3172  assert(heur != NULL);
3173  assert(scip != NULL);
3174 
3175  /* get heuristic's data */
3176  heurdata = SCIPheurGetData(heur);
3177  assert(heurdata != NULL);
3178 
3179  /* free random number generator */
3180  SCIPfreeRandom(scip, &heurdata->randnumgen);
3181 
3182  return SCIP_OKAY;
3183 }
3184 
3185 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
3186 static
3187 SCIP_DECL_HEURINITSOL(heurInitsolUndercover)
3188 { /*lint --e{715}*/
3189  SCIP_HEURDATA* heurdata;
3190  int h;
3191 
3192  assert(heur != NULL);
3193  assert(scip != NULL);
3194 
3195  /* get heuristic's data */
3196  heurdata = SCIPheurGetData(heur);
3197  assert(heurdata != NULL);
3198 
3199  /* initialize counters to zero */
3200  heurdata->nusednodes = 0;
3201  heurdata->npostnlpfails = 0;
3202  heurdata->nnlpfails = 0;
3203 
3204  /* if the heuristic is called at the root node, we may want to be called directly after the initial root LP solve */
3205  if( heurdata->beforecuts && SCIPheurGetFreqofs(heur) == 0 )
3207 
3208  /* find nonlinear constraint handlers */
3209  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->nlconshdlrs, 7) );/*lint !e506*/
3210  h = 0;
3211 
3212  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "and");
3213  if( heurdata->nlconshdlrs[h] != NULL )
3214  h++;
3215 
3216  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "quadratic");
3217  if( heurdata->nlconshdlrs[h] != NULL )
3218  h++;
3219 
3220  if( heurdata->coverbd )
3221  {
3222  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "bounddisjunction");
3223  if( heurdata->nlconshdlrs[h] != NULL )
3224  h++;
3225  }
3226 
3227  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "indicator");
3228  if( heurdata->nlconshdlrs[h] != NULL )
3229  h++;
3230 
3231  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "soc");
3232  if( heurdata->nlconshdlrs[h] != NULL )
3233  h++;
3234 
3235  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "nonlinear");
3236  if( heurdata->nlconshdlrs[h] != NULL )
3237  h++;
3238 
3239  heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "abspower");
3240  if( heurdata->nlconshdlrs[h] != NULL )
3241  h++;
3242 
3243  heurdata->nnlconshdlrs = h;
3244  assert( heurdata->nnlconshdlrs <= 7 );
3245 
3246  /* find NLP local search heuristic */
3247  heurdata->nlpheur = SCIPfindHeur(scip, "subnlp");
3248 
3249  /* add global linear constraints to NLP relaxation */
3250  if( SCIPisNLPConstructed(scip) && heurdata->nlpheur != NULL )
3251  {
3252  SCIP_CALL( SCIPaddLinearConsToNlpHeurSubNlp(scip, heurdata->nlpheur, TRUE, TRUE) );
3253  }
3254 
3255  return SCIP_OKAY;
3256 }
3257 
3258 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
3259 static
3260 SCIP_DECL_HEUREXITSOL(heurExitsolUndercover)
3261 {
3262  SCIP_HEURDATA* heurdata;
3263 
3264  assert(heur != NULL);
3265  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
3266 
3267  /* get heuristic's data */
3268  heurdata = SCIPheurGetData(heur);
3269  assert(heurdata != NULL);
3270 
3271  /* free array of nonlinear constraint handlers */
3272  SCIPfreeBlockMemoryArray(scip, &heurdata->nlconshdlrs, 7);
3273 
3274  /* reset timing, if it was changed temporary (at the root node) */
3276 
3277  return SCIP_OKAY;
3278 }
3279 
3280 /** execution method of primal heuristic */
3281 static
3282 SCIP_DECL_HEUREXEC(heurExecUndercover)
3283 { /*lint --e{715}*/
3284  SCIP_HEURDATA* heurdata; /* heuristic data */
3285  SCIP_Real timelimit; /* time limit for the subproblem */
3286  SCIP_Real memorylimit; /* memory limit for the subproblem */
3287  SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */
3288  SCIP_Bool run;
3289 
3290  int h;
3291 
3292  assert(heur != NULL);
3293  assert(scip != NULL);
3294  assert(result != NULL);
3295 
3296  *result = SCIP_DIDNOTRUN;
3297 
3298  /* do not call heuristic of node was already detected to be infeasible */
3299  if( nodeinfeasible )
3300  return SCIP_OKAY;
3301 
3302  /* get heuristic's data */
3303  heurdata = SCIPheurGetData(heur);
3304  assert(heurdata != NULL);
3305 
3306  /* only call heuristic once at the root */
3307  if( SCIPgetDepth(scip) == 0 && SCIPheurGetNCalls(heur) > 0 )
3308  return SCIP_OKAY;
3309 
3310  /* if we want to use NLP fixing values exclusively and no NLP solver is available, we cannot run */
3311  if( strcmp(heurdata->fixingalts, "n") == 0 && SCIPgetNNlpis(scip) == 0 )
3312  {
3313  SCIPdebugMsg(scip, "skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n");
3314  return SCIP_OKAY;
3315  }
3316 
3317  /* calculate stallnode limit */
3318  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
3319 
3320  /* reward heuristic if it succeeded often */
3321  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0));
3322  nstallnodes -= SUBMIPSETUPCOSTS * SCIPheurGetNCalls(heur); /* account for the setup costs of the sub-CIP */
3323  nstallnodes += heurdata->nodesofs;
3324 
3325  /* determine the node limit for the current process */
3326  nstallnodes -= heurdata->nusednodes;
3327  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
3328  nstallnodes = MAX(nstallnodes, 1);
3329 
3330  /* only call heuristics if we have enough nodes left to call sub-CIP solving */
3331  if( nstallnodes < heurdata->minnodes )
3332  {
3333  SCIPdebugMsg(scip, "skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
3334  return SCIP_OKAY;
3335  }
3336 
3337  /* only call heuristics if we have enough time left */
3338  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
3339  if( !SCIPisInfinity(scip, timelimit) )
3340  timelimit -= SCIPgetSolvingTime(scip);
3341  if( timelimit <= 2*MINTIMELEFT )
3342  {
3343  SCIPdebugMsg(scip, "skipping undercover heuristic: time left=%g\n", timelimit);
3344  return SCIP_OKAY;
3345  }
3346 
3347  /* only call heuristics if we have enough memory left */
3348  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
3349  if( !SCIPisInfinity(scip, memorylimit) )
3350  {
3351  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
3352  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
3353  }
3354 
3355  if( memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
3356  {
3357  SCIPdebugMsg(scip, "skipping undercover heuristic: too little memory\n");
3358  return SCIP_OKAY;
3359  }
3360 
3361  /* only call heuristic if nonlinear constraints are present */
3362  run = FALSE;
3363  for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- )
3364  {
3365  run = (SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[h]) > 0);
3366  }
3367 
3368  /* go through all nlrows and check for general nonlinearities */
3369  if( SCIPisNLPConstructed(scip) )
3370  {
3371  SCIP_NLROW** nlrows;
3372  int nnlrows;
3373  int i;
3374 
3375  /* get nlrows */
3376  nnlrows = SCIPgetNNLPNlRows(scip);
3377  nlrows = SCIPgetNLPNlRows(scip);
3378 
3379  /* check for an nlrow with nontrivial expression tree or quadratic terms; start from 0 since we expect the linear
3380  * nlrows at the end */
3381  for( i = nnlrows-1; i >= 0 && !run; i-- )
3382  {
3383  assert(nlrows[i] != NULL);
3384  run = SCIPnlrowGetExprtree(nlrows[i]) != NULL && SCIPexprtreeGetNVars(SCIPnlrowGetExprtree(nlrows[i])) > 0;
3385  run = run || SCIPnlrowGetNQuadVars(nlrows[i]) > 0;
3386  }
3387  }
3388 
3389  if( !run )
3390  {
3391  SCIPdebugMsg(scip, "skipping undercover heuristic: no nonlinear constraints found\n");
3392  return SCIP_OKAY;
3393  }
3394 
3395  /* only call heuristics if solving has not stopped yet */
3396  if( SCIPisStopped(scip) )
3397  return SCIP_OKAY;
3398 
3399  /* reset timing, if it was changed temporary (at the root node) */
3400  if( heurtiming != HEUR_TIMING )
3402 
3403  /* call heuristic */
3404  *result = SCIP_DIDNOTFIND;
3405  SCIPdebugMsg(scip, "calling undercover heuristic for <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3406 
3407  SCIP_CALL( SCIPapplyUndercover(scip, heur, result, timelimit, memorylimit, nstallnodes) );
3408 
3409  return SCIP_OKAY;
3410 }
3411 
3412 
3413 /*
3414  * primal heuristic specific interface methods
3415  */
3416 
3417 /** creates the undercover primal heuristic and includes it in SCIP */
3419  SCIP* scip /**< SCIP data structure */
3420  )
3421 {
3422  SCIP_HEURDATA* heurdata;
3423  SCIP_HEUR* heur;
3424 
3425  /* create undercover primal heuristic data */
3426  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
3427 
3428  /* always use local bounds */
3429  heurdata->globalbounds = FALSE;
3430 
3431  /* include primal heuristic */
3432  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
3434  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecUndercover, heurdata) );
3435 
3436  assert(heur != NULL);
3437 
3438  /* set non-NULL pointers to callback methods */
3439  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyUndercover) );
3440  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeUndercover) );
3441  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitUndercover) );
3442  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitUndercover) );
3443  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolUndercover) );
3444  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolUndercover) );
3445 
3446  /* add string parameters */
3447  heurdata->fixingalts = NULL;
3448  SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/fixingalts",
3449  "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)",
3450  &heurdata->fixingalts, FALSE, DEFAULT_FIXINGALTS, NULL, NULL) );
3451 
3452  /* add longint parameters */
3453  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
3454  "maximum number of nodes to regard in the subproblem",
3455  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3456 
3457  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
3458  "minimum number of nodes required to start the subproblem",
3459  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3460 
3461  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
3462  "number of nodes added to the contingent of the total nodes",
3463  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3464 
3465  /* add real parameters */
3466  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/conflictweight",
3467  "weight for conflict score in fixing order",
3468  &heurdata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3469 
3470  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/cutoffweight",
3471  "weight for cutoff score in fixing order",
3472  &heurdata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3473 
3474  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/inferenceweight",
3475  "weight for inference score in fixing order",
3476  &heurdata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3477 
3478  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizevars",
3479  "maximum coversize (as fraction of total number of variables)",
3480  &heurdata->maxcoversizevars, TRUE, DEFAULT_MAXCOVERSIZEVARS, 0.0, 1.0, NULL, NULL) );
3481 
3482  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizeconss",
3483  "maximum coversize maximum coversize (as ratio to the percentage of non-affected constraints)",
3484  &heurdata->maxcoversizeconss, TRUE, DEFAULT_MAXCOVERSIZECONSS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3485 
3486  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mincoveredrel",
3487  "minimum percentage of nonlinear constraints in the original problem",
3488  &heurdata->mincoveredrel, TRUE, DEFAULT_MINCOVEREDREL, 0.0, 1.0, NULL, NULL) );
3489 
3490  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
3491  "factor by which the heuristic should at least improve the incumbent",
3492  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, -1.0, 1.0, NULL, NULL) );
3493 
3494  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
3495  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
3496  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
3497 
3498  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/recoverdiv",
3499  "fraction of covering variables in the last cover which need to change their value when recovering",
3500  &heurdata->recoverdiv, TRUE, DEFAULT_RECOVERDIV, 0.0, 1.0, NULL, NULL) );
3501 
3502  /* add int parameters */
3503  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/mincoveredabs",
3504  "minimum number of nonlinear constraints in the original problem",
3505  &heurdata->mincoveredabs, TRUE, DEFAULT_MINCOVEREDABS, 0, INT_MAX, NULL, NULL) );
3506 
3507  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
3508  "maximum number of backtracks in fix-and-propagate",
3509  &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, 0, INT_MAX, NULL, NULL) );
3510 
3511  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxrecovers",
3512  "maximum number of recoverings",
3513  &heurdata->maxrecovers, TRUE, DEFAULT_MAXRECOVERS, 0, INT_MAX, NULL, NULL) );
3514 
3515  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxreorders",
3516  "maximum number of reorderings of the fixing order",
3517  &heurdata->maxreorders, TRUE, DEFAULT_MAXREORDERS, 0, INT_MAX, NULL, NULL) );
3518 
3519  /* add char parameters */
3520  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/coveringobj",
3521  "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)",
3522  &heurdata->coveringobj, TRUE, DEFAULT_COVERINGOBJ, COVERINGOBJS, NULL, NULL) );
3523 
3524  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/fixingorder",
3525  "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index",
3526  &heurdata->fixingorder, TRUE, DEFAULT_FIXINGORDER, FIXINGORDERS, NULL, NULL) );
3527 
3528  /* add bool parameters */
3529  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforecuts",
3530  "should the heuristic be called at root node before cut separation?",
3531  &heurdata->beforecuts, TRUE, DEFAULT_BEFORECUTS, NULL, NULL) );
3532 
3533  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixintfirst",
3534  "should integer variables in the cover be fixed first?",
3535  &heurdata->fixintfirst, TRUE, DEFAULT_FIXINTFIRST, NULL, NULL) );
3536 
3537  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/locksrounding",
3538  "shall LP values for integer vars be rounded according to locks?",
3539  &heurdata->locksrounding, TRUE, DEFAULT_LOCKSROUNDING, NULL, NULL) );
3540 
3541  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyconvexify",
3542  "should we only fix variables in order to obtain a convex problem?",
3543  &heurdata->onlyconvexify, FALSE, DEFAULT_ONLYCONVEXIFY, NULL, NULL) );
3544 
3545  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/postnlp",
3546  "should the NLP heuristic be called to polish a feasible solution?",
3547  &heurdata->postnlp, FALSE, DEFAULT_POSTNLP, NULL, NULL) );
3548 
3549  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverbd",
3550  "should bounddisjunction constraints be covered (or just copied)?",
3551  &heurdata->coverbd, TRUE, DEFAULT_COVERBD, NULL, NULL) );
3552 
3553  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
3554  "should all active cuts from cutpool be copied to constraints in subproblem?",
3555  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
3556 
3557  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reusecover",
3558  "shall the cover be reused if a conflict was added after an infeasible subproblem?",
3559  &heurdata->reusecover, TRUE, DEFAULT_REUSECOVER, NULL, NULL) );
3560 
3561  return SCIP_OKAY;
3562 }
3563 
3564 /** create and solve covering problem */
3565 static
3567  SCIP* scip, /**< SCIP data structure */
3568  SCIP* coveringscip, /**< SCIP instance for covering problem */
3569  int* coversize, /**< buffer for the size of the computed cover */
3570  SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover
3571  * (should be ready to hold SCIPgetNVars(scip) entries) */
3572  SCIP_Real timelimit, /**< time limit */
3573  SCIP_Real memorylimit, /**< memory limit */
3574  SCIP_Real objlimit, /**< objective limit: upper bound on coversize */
3575  SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
3576  SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
3577  SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
3578  char coveringobj, /**< objective function of the covering problem ('b'ranching status,
3579  * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3580  * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3581  SCIP_Bool* success /**< feasible cover found? */
3582  )
3583 {
3584  SCIP_VAR** coveringvars; /* covering variables */
3585  SCIP_VAR** vars; /* original variables */
3586  int* coverinds; /* indices of variables in the cover */
3587  int nvars; /* number of original variables */
3588  int i;
3589 
3590  assert(scip != NULL);
3591  assert(coveringscip != NULL);
3592 
3593  SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) );
3594 
3595  /* allocate memory for variables of the covering problem */
3596  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL ) );
3597  SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) );
3598  SCIP_CALL( SCIPallocBufferArray(scip, &coverinds, nvars) );
3599 
3600  SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, globalbounds, onlyconvexify, coverbd, coveringobj, success) );
3601 
3602  if( *success )
3603  {
3604  /* solve covering problem */
3605  SCIPdebugMsg(scip, "solving covering problem\n\n");
3606 
3607  SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, coversize, coverinds,
3608  timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, objlimit, success) );
3609 
3610  if( *success )
3611  {
3612  assert(*coversize >= 0);
3613  assert(*coversize <= nvars);
3614 
3615  /* return original variables in the cover */
3616  for( i = *coversize-1; i >= 0; i-- )
3617  {
3618  assert(coverinds[i] >= 0);
3619  assert(coverinds[i] < nvars);
3620  cover[i] = vars[coverinds[i]];
3621  }
3622  }
3623  }
3624  else
3625  {
3626  SCIPdebugMsg(scip, "failure: covering problem could not be created\n");
3627  }
3628 
3629  /* free covering problem */
3630  for( i = nvars-1; i >= 0; i-- )
3631  {
3632  SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) );
3633  }
3634  SCIPfreeBufferArray(scip, &coverinds);
3635  SCIPfreeBufferArray(scip, &coveringvars);
3636 
3637  return SCIP_OKAY;
3638 }
3639 
3640 /** computes a minimal set of covering variables */
3642  SCIP* scip, /**< SCIP data structure */
3643  int* coversize, /**< buffer for the size of the computed cover */
3644  SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover
3645  * (should be ready to hold SCIPgetNVars(scip) entries) */
3646  SCIP_Real timelimit, /**< time limit */
3647  SCIP_Real memorylimit, /**< memory limit */
3648  SCIP_Real objlimit, /**< objective limit: upper bound on coversize */
3649  SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
3650  SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
3651  SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
3652  char coveringobj, /**< objective function of the covering problem ('b'ranching status,
3653  * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3654  * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3655  SCIP_Bool* success /**< feasible cover found? */
3656  )
3657 {
3658  SCIP* coveringscip; /* SCIP instance for covering problem */
3659  SCIP_RETCODE retcode;
3660 
3661  assert(scip != NULL);
3662  assert(coversize != NULL);
3663  assert(success != NULL);
3664 
3665  *success = FALSE;
3666 
3667  /* create covering problem */
3668  SCIP_CALL( SCIPcreate(&coveringscip) );
3669 
3670  retcode = computeCoverUndercover(scip, coveringscip, coversize, cover,
3671  timelimit, memorylimit, objlimit,
3672  globalbounds, onlyconvexify, coverbd, coveringobj, success);
3673 
3674  /* free the covering problem scip instance before reacting on potential errors */
3675  SCIP_CALL( SCIPfree(&coveringscip) );
3676 
3677  SCIP_CALL( retcode );
3678 
3679  return SCIP_OKAY;
3680 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8209
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48620
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition: type_timing.h:71
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)
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip.c:31456
SCIP_VAR ** SCIPgetLhsVarsSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5357
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
#define HEUR_TIMING
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5158
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:31227
SCIP_RETCODE SCIPlinkCurrentSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38675
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
#define DEFAULT_FIXINGORDER
static SCIP_Bool termIsConvex(SCIP *scip, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool sign)
methods to interpret (evaluate) an expression tree "fast"
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip.c:19109
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35958
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip.c:27001
#define HEUR_DISPCHAR
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)
static SCIP_RETCODE computeFixingOrder(SCIP *scip, SCIP_HEURDATA *heurdata, int nvars, SCIP_VAR **vars, int coversize, int *cover, int lastfailed, SCIP_Bool *success)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35931
#define DEFAULT_MAXRECOVERS
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:47655
#define DEFAULT_MAXREORDERS
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4489
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1344
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48602
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:9936
#define DEFAULT_MINCOVEREDABS
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8177
#define DEFAULT_COPYCUTS
#define DEFAULT_RECOVERDIV
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12246
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
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:9151
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip.c:31610
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18760
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
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)
static SCIP_RETCODE roundFixingValue(SCIP *scip, SCIP_Real *val, SCIP_VAR *var, SCIP_Bool locksrounding)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
#define DEFAULT_MAXCOVERSIZECONSS
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5106
Undercover primal heuristic for MINLPs.
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39826
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
#define DEFAULT_MINIMPROVE
#define DEFAULT_RANDSEED
#define MAXPOSTNLPFAILS
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:4293
static SCIP_DECL_HEUREXITSOL(heurExitsolUndercover)
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:3884
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5132
SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1304
int SCIPnlrowGetNQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3275
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3383
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
#define DEFAULT_INFERENCEWEIGHT
#define DEFAULT_MINCOVEREDREL
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define DEFAULT_NODESOFS
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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:8084
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:4376
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36034
#define DEFAULT_FIXINTFIRST
#define COVERINGOBJS
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:46058
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
Definition: scip.c:31789
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22010
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47453
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define SCIP_LONGINT_MAX
Definition: def.h:135
#define DEFAULT_BEFORECUTS
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
static SCIP_DECL_HEUREXIT(heurExitUndercover)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:748
static SCIP_DECL_HEURCOPY(heurCopyUndercover)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define DEFAULT_CONFLICTWEIGHT
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17102
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4804
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
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)
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:4265
SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:45645
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:101
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip.c:31434
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:46409
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47429
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47417
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3322
#define HEUR_NAME
#define DEFAULT_MINNODES
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17092
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:47640
#define DEFAULT_ONLYCONVEXIFY
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
#define DEFAULT_MAXNODES
SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Real coef
Definition: type_expr.h:102
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3285
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5121
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8193
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:16109
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
Definition: heur_subnlp.c:2391
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip.c:46007
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip.c:8225
SCIP_RETCODE SCIPsolveDiveNLP(SCIP *scip)
Definition: scip.c:32151
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPgetNlRowSOC(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_soc.c:5320
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4401
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12585
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5146
#define HEUR_USESSUBSCIP
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8145
SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:13210
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:36308
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38942
static SCIP_DECL_HEUREXEC(heurExecUndercover)
#define FIXINGORDERS
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22633
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4630
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:928
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip.c:3065
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
SCIP_RETCODE SCIPchgVarBoundsDiveNLP(SCIP *scip, SCIP_VAR *var, SCIP_Real lb, SCIP_Real ub)
Definition: scip.c:32090
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
SCIPInterval sign(const SCIPInterval &x)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35993
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define DEFAULT_NODESQUOT
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip.c:2428
#define SUBMIPSETUPCOSTS
#define DEFAULT_POSTNLP
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:9602
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip.c:4451
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17650
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip.c:4567
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8612
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:31555
SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3332
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:43271
#define SCIPstatisticPrintf
Definition: pub_message.h:107
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip.c:5061
SCIP_EXPRINTCAPABILITY SCIPexprintGetCapability(void)
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)
#define DEFAULT_CUTOFFWEIGHT
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1324
static SCIP_Bool varIsFixed(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool global)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21847
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
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:9092
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
public data structures and miscellaneous methods
SCIP_RETCODE SCIPincludeHeurUndercover(SCIP *scip)
#define SCIP_EXPRINTCAPABILITY_HESSIAN
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip.c:17246
static SCIP_RETCODE computeCoverUndercover(SCIP *scip, SCIP *coveringscip, 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)
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetNLhsVarsSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5345
static void incCounters(int *termcounter, int *conscounter, SCIP_Bool *consmarker, int idx)
#define DEFAULT_LOCKSROUNDING
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11240
SCIP_VAR * SCIPgetRhsVarSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5405
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46241
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:17663
static void calculateAlternatives(SCIP *scip, SCIP_VAR *var, SCIP_Real fixval, int *nalternatives, SCIP_Real *alternatives)
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define HEUR_FREQ
static SCIP_RETCODE updateTimelimit(SCIP *scip, SCIP_CLOCK *clck, SCIP_Real *timelimit)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38529
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
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:17613
#define DEFAULT_COVERINGOBJ
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39777
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25569
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38988
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)
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:1674
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
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)
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
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:40694
#define SCIP_MAXTREEDEPTH
Definition: def.h:286
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9388
#define HEUR_DESC
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3363
#define SCIP_REAL_MIN
Definition: def.h:151
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)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
#define DEFAULT_MAXBACKTRACKS
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39876
#define DEFAULT_FIXINGALTS
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47106
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:4349
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:46768
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11486
#define MAXNLPFAILS
#define MINTIMELEFT
SCIP_RETCODE SCIPendDiveNLP(SCIP *scip)
Definition: scip.c:32034
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46075
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12856
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27755
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)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8161
SCIP_Real SCIPgetRhsCoefSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5417
static SCIP_Bool termIsConstant(SCIP *scip, SCIP_VAR *var, SCIP_Real coeff, SCIP_Bool global)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:46794
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5097
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1238
SCIP_RETCODE SCIPexprintHessianSparsityDense(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool *sparsity)
#define SCIP_Longint
Definition: def.h:134
static SCIP_RETCODE copySol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *subsol, SCIP_SOL **newsol)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
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)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38807
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
#define HEUR_FREQOFS
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIP_RETCODE SCIPstartDiveNLP(SCIP *scip)
Definition: scip.c:32006
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
Definition: nlp.c:3412
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8129
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35898
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47393
static SCIP_DECL_HEURINIT(heurInitUndercover)
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:46423
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:43420
SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35852
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
static SCIP_RETCODE forbidCover(SCIP *scip, int nvars, SCIP_VAR **vars, int coversize, int *cover, int diversification, SCIP_Bool *success, SCIP_Bool *infeas)
#define DEFAULT_REUSECOVER
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
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)
#define HEUR_PRIORITY
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3373
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
static SCIP_RETCODE SCIPapplyUndercover(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nstallnodes)
static SCIP_DECL_HEURINITSOL(heurInitsolUndercover)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16853
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36078
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip.c:46092
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
default SCIP plugins
#define DEFAULT_MAXCOVERSIZEVARS
SCIP_Real * SCIPgetLhsCoefsSOC(SCIP *scip, SCIP_CONS *cons)
Definition: cons_soc.c:5369
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:4321
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5083
#define DEFAULT_COVERBD
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4746
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:19039
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)
SCIP callable library.
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:4239
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26452
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:780
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16817
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
static SCIP_DECL_HEURFREE(heurFreeUndercover)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:39319