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