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