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