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