Scippy

SCIP

Solving Constraint Integer Programs

cons_components.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_components.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for handling independent components
19  * @author Gerald Gamrath
20  *
21  * This constraint handler looks for independent components.
22  */
23 /*#define DETAILED_OUTPUT*/
24 /*#define SCIP_DEBUG*/
25 /*#define SCIP_MORE_DEBUG*/
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include "blockmemshell/memory.h"
29 #include "scip/cons_components.h"
30 #include "scip/debug.h"
31 #include "scip/pub_cons.h"
32 #include "scip/pub_heur.h"
33 #include "scip/pub_message.h"
34 #include "scip/pub_misc.h"
35 #include "scip/pub_misc_sort.h"
36 #include "scip/pub_sol.h"
37 #include "scip/pub_tree.h"
38 #include "scip/pub_var.h"
39 #include "scip/scip_cons.h"
40 #include "scip/scip_copy.h"
42 #include "scip/scip_general.h"
43 #include "scip/scip_heur.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_message.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_pricer.h"
49 #include "scip/scip_prob.h"
50 #include "scip/scip_probing.h"
51 #include "scip/scip_sol.h"
52 #include "scip/scip_solve.h"
53 #include "scip/scip_solvingstats.h"
54 #include "scip/scip_timing.h"
55 #include "scip/scip_tree.h"
56 #include "scip/scip_var.h"
57 #include <string.h>
58 
59 #define CONSHDLR_NAME "components"
60 #define CONSHDLR_DESC "independent components constraint handler"
61 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
62 #define CONSHDLR_CHECKPRIORITY -9999999 /**< priority of the constraint handler for checking feasibility */
63 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
64  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
65 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
66 
67 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
68 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
69 #define CONSHDLR_DELAYPROP TRUE /**< should propagation method be delayed, if other propagators found reductions? */
70 
71 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FINAL /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
72 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/
73 
74 #define DEFAULT_MAXDEPTH -1 /**< maximum depth of a node to run components detection (-1: disable component detection during solving) */
75 #define DEFAULT_MAXINTVARS 500 /**< maximum number of integer (or binary) variables to solve a subproblem directly in presolving (-1: no solving) */
76 #define DEFAULT_MINSIZE 50 /**< minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound */
77 #define DEFAULT_MINRELSIZE 0.1 /**< minimum relative size (in terms of variables) to solve a component individually during branch-and-bound */
78 #define DEFAULT_NODELIMIT 10000LL /**< maximum number of nodes to be solved in subproblems during presolving */
79 #define DEFAULT_INTFACTOR 1.0 /**< the weight of an integer variable compared to binary variables */
80 #define DEFAULT_FEASTOLFACTOR 1.0 /**< default value for parameter to increase the feasibility tolerance in all sub-SCIPs */
81 
82 /*
83  * Data structures
84  */
85 
86 /** data related to one problem (see below) */
87 typedef struct Problem PROBLEM;
88 
89 /** data related to one component */
90 typedef struct Component
91 {
92  PROBLEM* problem; /**< the problem this component belongs to */
93  SCIP* subscip; /**< sub-SCIP representing the component */
94  SCIP_SOL* workingsol; /**< working solution for transferring solutions into the sub-SCIP */
95  SCIP_VAR** vars; /**< variables belonging to this component (in complete problem) */
96  SCIP_VAR** subvars; /**< variables belonging to this component (in subscip) */
97  SCIP_VAR** fixedvars; /**< variables in the original SCIP which were copied while copying the component's
98  * constraints, but do not count to the subvars, because they were locally fixed */
99  SCIP_VAR** fixedsubvars; /**< variables in the sub-SCIP which were copied while copying the component's
100  * constraints, but do not count to the subvars, because they were locally fixed */
101  SCIP_Real fixedvarsobjsum; /**< objective contribution of all locally fixed variables */
102  SCIP_Real lastdualbound; /**< dual bound after last optimization call for this component */
103  SCIP_Real lastprimalbound; /**< primal bound after last optimization call for this component */
104  SCIP_STATUS laststatus; /**< solution status of last optimization call for the sub-SCIP of this component */
105  SCIP_Bool solved; /**< was this component solved already? */
106  int ncalls; /**< number of optimization calls for this component */
107  int lastsolindex; /**< index of best solution after last optimization call for this component */
108  int lastbestsolindex; /**< index of last best solution transferred to this component from the main problem */
109  int nvars; /**< number of variables belonging to this component */
110  int nfixedvars; /**< number of fixed variables copied during constraint copying */
111  int fixedvarssize; /**< size of fixedvars and fixedsubvars arrays */
112  int number; /**< component number */
114 
115 /** data related to one problem
116  * (corresponding to one node in the branch-and-bound tree and consisting of multiple components)
117  */
118 struct Problem
119 {
120  SCIP* scip; /**< the SCIP instance this problem belongs to */
121  COMPONENT* components; /**< independent components into which the problem can be divided */
122  SCIP_PQUEUE* compqueue; /**< priority queue for components */
123  SCIP_SOL* bestsol; /**< best solution found so far for the problem */
124  char* name; /**< name of the problem */
125  SCIP_Real fixedvarsobjsum; /**< objective contribution of all locally fixed variables */
126  SCIP_Real lowerbound; /**< lower bound of the problem */
127  int ncomponents; /**< number of independent components into which the problem can be divided */
128  int componentssize; /**< size of components array */
129  int nfeascomps; /**< number of components for which a feasible solution was found */
130  int nsolvedcomps; /**< number of components solved to optimality */
131  int nlowerboundinf; /**< number of components with lower bound equal to -infinity */
132 };
133 
134 
135 /** constraint handler data */
136 struct SCIP_ConshdlrData
137 {
138  SCIP_Longint nodelimit; /**< maximum number of nodes to be solved in subproblems */
139  SCIP_Real intfactor; /**< the weight of an integer variable compared to binary variables */
140  SCIP_Real feastolfactor; /**< parameter to increase the feasibility tolerance in all sub-SCIPs */
141  int maxintvars; /**< maximum number of integer (or binary) variables to solve a subproblem
142  * directly (-1: no solving) */
143  int maxdepth; /**< maximum depth of a node to run components detection (-1: disable
144  * component detection during solving) */
145  int minsize; /**< minimum absolute size (in terms of variables) to solve a component
146  * individually during branch-and-bound */
147  SCIP_Real minrelsize; /**< minimum relative size (in terms of variables) to solve a component
148  * individually during branch-and-bound */
149  int subscipdepth; /**< depth offset of the current (sub-)problem compared to the original
150  * problem */
151 };
152 
153 
154 /** comparison method for sorting components */
155 static
156 SCIP_DECL_SORTPTRCOMP(componentSort)
157 {
158  SCIP* scip;
159  COMPONENT* comp1;
160  COMPONENT* comp2;
161  SCIP_Real gap1;
162  SCIP_Real gap2;
163 
164  assert(elem1 != NULL);
165  assert(elem2 != NULL);
166 
167  comp1 = (COMPONENT*)elem1;
168  comp2 = (COMPONENT*)elem2;
169 
170  if( comp1->ncalls == 0 )
171  if( comp2->ncalls == 0 )
172  return comp1->number - comp2->number;
173  else
174  return -1;
175  else if( comp2->ncalls == 0 )
176  return 1;
177 
178  /* the main sorting criterion is the absolute gap; however, we devide it by the number of solving calls for this
179  * component to diversify the search if one component does not improve
180  * @todo investigate other sorting criteria
181  */
182  gap1 = SQR(comp1->lastprimalbound - comp1->lastdualbound) / comp1->ncalls;
183  gap2 = SQR(comp2->lastprimalbound - comp2->lastdualbound) / comp2->ncalls;
184 
185  assert(comp1->problem != NULL);
186  assert(comp1->problem == comp2->problem);
187  assert(comp1->problem->scip == comp2->problem->scip);
188 
189  scip = comp1->problem->scip;
190  assert(scip != NULL);
191 
192  if( SCIPisFeasGT(scip, gap1, gap2) )
193  return -1;
194  else if( SCIPisFeasLT(scip, gap1, gap2) )
195  return +1;
196  else
197  return comp1->number - comp2->number;
198 }
199 
200 /** returns minimum size of components to be solved individually during the branch-and-bound search */
201 static
202 int getMinsize(
203  SCIP* scip, /**< main SCIP data structure */
204  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
205  )
206 {
207  int minsize;
208 
209  assert(conshdlrdata != NULL);
210 
211  minsize = (int)(conshdlrdata->minrelsize * SCIPgetNVars(scip));
212  minsize = MAX(minsize, conshdlrdata->minsize);
213 
214  return minsize;
215 }
216 
217 /** initialize component structure */
218 static
220  PROBLEM* problem /**< subproblem structure */
221  )
222 {
223  COMPONENT* component;
224  SCIP* scip;
225 
226  assert(problem != NULL);
227  assert(problem->ncomponents < problem->componentssize);
228 
229  scip = problem->scip;
230  assert(scip != NULL);
231 
232  component = &problem->components[problem->ncomponents];
233 
234  component->problem = problem;
235  component->subscip = NULL;
236  component->workingsol = NULL;
237  component->vars = NULL;
238  component->subvars = NULL;
239  component->fixedvars = NULL;
240  component->fixedsubvars = NULL;
241  component->fixedvarsobjsum = 0.0;
242  component->lastdualbound = -SCIPinfinity(scip);
243  component->lastprimalbound = SCIPinfinity(scip);
244  component->laststatus = SCIP_STATUS_UNKNOWN;
245  component->solved = FALSE;
246  component->ncalls = 0;
247  component->lastsolindex = -1;
248  component->lastbestsolindex = -1;
249  component->nvars = 0;
250  component->nfixedvars = 0;
251  component->fixedvarssize = 0;
252  component->number = problem->ncomponents;
253 
254  ++problem->ncomponents;
255 
256  return SCIP_OKAY;
257 }
258 
259 /** free component structure */
260 static
262  COMPONENT* component /**< pointer to component structure */
263  )
264 {
265  PROBLEM* problem;
266  SCIP* scip;
267 
268  assert(component != NULL);
269 
270  problem = component->problem;
271  assert(problem != NULL);
272 
273  scip = problem->scip;
274  assert(scip != NULL);
275 
276  SCIPdebugMsg(scip, "freeing component %d of problem <%s>\n", component->number, component->problem->name);
277 
278  assert((component->vars != NULL) == (component->subvars != NULL));
279  if( component->vars != NULL )
280  {
281  SCIPfreeBlockMemoryArray(scip, &component->vars, component->nvars);
282  SCIPfreeBlockMemoryArray(scip, &component->subvars, component->nvars);
283  }
284 
285  assert((component->fixedvars != NULL) == (component->fixedsubvars != NULL));
286  if( component->fixedvars != NULL )
287  {
288  SCIPfreeBlockMemoryArray(scip, &component->fixedsubvars, component->fixedvarssize);
289  SCIPfreeBlockMemoryArray(scip, &component->fixedvars, component->fixedvarssize);
290  }
291 
292  /* free sub-SCIP belonging to this component and the working solution */
293  if( component->subscip != NULL )
294  {
295  if( component->workingsol != NULL )
296  {
297  SCIP_CALL( SCIPfreeSol(component->subscip, &component->workingsol) );
298  }
299 
300  SCIP_CALL( SCIPfree(&component->subscip) );
301  }
302 
303  return SCIP_OKAY;
304 }
305 
306 
307 /** create the working solution for a given component, store fixed variables and the corresponding objective offset */
308 static
310  COMPONENT* component, /**< component structure */
311  SCIP_HASHMAP* varmap /**< variable hashmap */
312  )
313 {
314  SCIP* subscip;
315 
316  assert(component != NULL);
317 
318  subscip = component->subscip;
319  assert(subscip != NULL);
320  assert(SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM);
321 
322  /* the solution should live in the primal, not the origprimal, of the sub-SCIP, so we need to transform it first */
323  SCIP_CALL( SCIPtransformProb(subscip) );
324  SCIP_CALL( SCIPcreateOrigSol(subscip, &(component->workingsol), NULL) );
325 
326  /* the number of variables was increased by copying the constraints */
327  if( SCIPgetNOrigVars(subscip) > component->nvars )
328  {
329  PROBLEM* problem;
330  SCIP* scip;
331  SCIP_VAR** sourcevars;
332  SCIP_VAR* subvar;
333  int nsourcevars;
334  int nnewvars;
335  int idx = 0;
336  int nvars;
337  int v;
338 
339  problem = component->problem;
340  assert(problem != NULL);
341 
342  scip = problem->scip;
343  assert(scip != NULL);
344 
345  sourcevars = SCIPgetVars(scip);
346  nsourcevars = SCIPgetNVars(scip);
347  nnewvars = SCIPgetNOrigVars(subscip);
348  nvars = component->nvars;
349 
350  component->fixedvarssize = nnewvars - nvars;
351  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->fixedvars, component->fixedvarssize) );
352  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->fixedsubvars, component->fixedvarssize) );
353 
354  for( v = 0; v < nsourcevars; ++v )
355  {
356  subvar = (SCIP_VAR*)SCIPhashmapGetImage(varmap, sourcevars[v]);
357  if( subvar != NULL && SCIPvarGetIndex(subvar) >= nvars )
358  {
359  /* the variable is either locally fixed or could be an inactive variable present in a constraint
360  * for which an aggregation constraint linking it to the active variable was created in the subscip
361  */
362  assert(SCIPisZero(subscip, SCIPvarGetObj(subvar)) ||
363  SCIPisEQ(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)));
364 
365  /* variable is gloablly fixed in sub-SCIP, so it was locally fixed in the main-SCIP */
366  if( SCIPisEQ(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)) )
367  {
368  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(sourcevars[v]), SCIPvarGetUbLocal(sourcevars[v])));
369 
370  component->fixedvarsobjsum += SCIPvarGetLbGlobal(subvar) * SCIPvarGetObj(subvar);
371  component->fixedvars[idx] = sourcevars[v];
372  component->fixedsubvars[idx] = subvar;
373  ++idx;
374 
375  SCIP_CALL( SCIPsetSolVal(subscip, component->workingsol, subvar, SCIPvarGetLbGlobal(subvar)) );
376  }
377  /* inactive variable */
378  else
379  {
380  assert(SCIPisZero(subscip, SCIPvarGetObj(subvar)));
381  }
382  }
383  else
384  {
385  assert(subvar == NULL || SCIPisLT(scip, SCIPvarGetLbGlobal(sourcevars[v]), SCIPvarGetUbGlobal(sourcevars[v])));
386  assert(subvar == NULL || SCIPisLT(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)));
387  }
388  }
389  component->nfixedvars = idx;
390  assert(component->nfixedvars <= component->fixedvarssize);
391  SCIPdebugMsg(scip, "%d locally fixed variables have been copied, objective contribution: %g\n",
392  component->nfixedvars, component->fixedvarsobjsum);
393  }
394 
395  /* set up debug solution */
396 #ifdef WITH_DEBUG_SOLUTION
397  if( SCIPdebugSolIsEnabled(component->problem->scip) )
398  {
399  PROBLEM* problem;
400  SCIP* scip;
401  SCIP_Bool isvalid = FALSE;
402 
403  problem = component->problem;
404  assert(problem != NULL);
405 
406  scip = problem->scip;
407  assert(scip != NULL);
408 
409  SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) );
410 
411  if( isvalid )
412  {
413  SCIP_Real val;
414  int i;
415 
416  SCIPdebugSolEnable(component->subscip);
417 
418  for( i = 0; i < component->nvars; ++i )
419  {
420  if( component->subvars[i] != NULL )
421  {
422  SCIP_CALL( SCIPdebugGetSolVal(scip, component->vars[i], &val) );
423  SCIP_CALL( SCIPdebugAddSolVal(component->subscip, component->subvars[i], val) );
424  }
425  }
426  for( i = 0; i < component->nfixedvars; ++i )
427  {
428  if( component->fixedsubvars[i] != NULL )
429  {
430  SCIP_CALL( SCIPdebugGetSolVal(scip, component->fixedvars[i], &val) );
431  SCIP_CALL( SCIPdebugAddSolVal(component->subscip, component->fixedsubvars[i], val) );
432  }
433  }
434  }
435  }
436 #endif
437 
438  return SCIP_OKAY;
439 }
440 
441 /** create a sub-SCIP for the given variables and constraints */
442 static
444  SCIP* scip, /**< main SCIP data structure */
445  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
446  SCIP** subscip /**< pointer to store created sub-SCIP */
447  )
448 {
449  SCIP_Bool success;
450 
451  assert(conshdlrdata != NULL);
452 
453  /* create a new SCIP instance */
454  SCIP_CALL( SCIPcreate(subscip) );
455 
456  /* copy plugins, we omit pricers (because we do not run if there are active pricers) and dialogs */
457 #ifdef SCIP_MORE_DEBUG /* we print statistics later, so we need to copy statistics tables */
458  SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE,
459  TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, &success) );
460 #else
461  SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE,
462  TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
463 #endif
464 
465  /* the plugins were successfully copied */
466  if( success )
467  {
468  SCIP_CONSHDLR* newconshdlr;
469  SCIP_CONSHDLRDATA* newconshdlrdata;
470 #ifdef WITH_DEBUG_SOLUTION
471  SCIP_Bool isvalid = FALSE;
472 #endif
473 
474  /* copy parameter settings */
475  SCIP_CALL( SCIPcopyParamSettings(scip, *subscip) );
476 
477  /* some general settings should not be fixed */
478  assert(!SCIPisParamFixed(*subscip, "limits/solutions"));
479  assert(!SCIPisParamFixed(*subscip, "limits/bestsol"));
480  assert(!SCIPisParamFixed(*subscip, "misc/usevartable"));
481  assert(!SCIPisParamFixed(*subscip, "misc/useconstable"));
482  assert(!SCIPisParamFixed(*subscip, "numerics/feastol"));
483  assert(!SCIPisParamFixed(*subscip, "misc/usesmalltables"));
484 
485  /* disable solution limits */
486  SCIP_CALL( SCIPsetIntParam(*subscip, "limits/solutions", -1) );
487  SCIP_CALL( SCIPsetIntParam(*subscip, "limits/bestsol", -1) );
488 
489  /* reduce the effort spent for hash tables; however, if the debug solution is enabled and valid in this subtree,
490  * hash tables are needed for installing the debug solution
491  */
492 #ifdef WITH_DEBUG_SOLUTION
493  SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) );
494  if( !isvalid && SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
495 #endif
496  {
497  SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/usevartable", FALSE) );
498  SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/useconstable", FALSE) );
499  }
500 
501  /* disable presolving */
503 
504  /* disable component presolving and fix the parameter */
505  SCIP_CALL( SCIPsetIntParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds", 0) );
506  SCIP_CALL( SCIPfixParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds") );
507 
508  /* find the components constraint handler in the sub-SCIP and inform it about the actual depth in the tree */
509  newconshdlr = SCIPfindConshdlr(*subscip, CONSHDLR_NAME);
510  assert(newconshdlr != NULL);
511 
512  newconshdlrdata = SCIPconshdlrGetData(newconshdlr);
513  assert(newconshdlrdata != NULL);
514  newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth + SCIPgetDepth(scip);
515 
516  /* disable output, unless in extended debug mode */
517 #ifndef SCIP_MORE_DEBUG
518  SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
519 #endif
520  }
521  else
522  {
523  SCIP_CALL( SCIPfree(subscip) );
524  *subscip = NULL;
525  }
526 
527  return SCIP_OKAY;
528 }
529 
530 /** copies the given variables and constraints to the given sub-SCIP */
531 static
533  SCIP* scip, /**< source SCIP */
534  SCIP* subscip, /**< target SCIP */
535  const char* name, /**< name for copied problem */
536  SCIP_VAR** vars, /**< array of variables to copy */
537  SCIP_VAR** subvars, /**< array to fill with copied vars */
538  SCIP_CONS** conss, /**< constraint to copy */
539  SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */
540  SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */
541  int nvars, /**< number of variables to copy */
542  int nconss, /**< number of constraints to copy */
543  SCIP_Bool* success /**< pointer to store whether copying was successful */
544  )
545 {
546  SCIP_CONS* newcons;
547  int i;
548 
549  assert(scip != NULL);
550  assert(subscip != NULL);
551  assert(vars != NULL);
552  assert(subvars != NULL);
553  assert(conss != NULL);
554  assert(varmap != NULL);
555  assert(consmap != NULL);
556  assert(success != NULL);
557 
558  *success = TRUE;
559 
560  /* create problem in sub-SCIP */
561  SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
562 
563  /* copy variables */
564  for( i = 0; i < nvars; ++i )
565  {
566  SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &subvars[i], varmap, consmap, FALSE, success) );
567 
568  /* abort if variable was not successfully copied */
569  if( !(*success) )
570  return SCIP_OKAY;
571  }
572 
573  /* copy constraints */
574  for( i = 0; i < nconss; ++i )
575  {
576  assert(!SCIPconsIsModifiable(conss[i]));
577 
578  /* copy the constraint */
579  SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
580  SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]),
581  SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE,
582  SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) );
583 
584  /* abort if constraint was not successfully copied */
585  if( !(*success) )
586  return SCIP_OKAY;
587 
588  SCIP_CALL( SCIPaddCons(subscip, newcons) );
589  SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
590  }
591 
592  return SCIP_OKAY;
593 }
594 
595 /** create the sub-SCIP for a given component */
596 static
598  COMPONENT* component, /**< component structure */
599  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
600  SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */
601  SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */
602  SCIP_CONS** conss, /**< constraints contained in this component */
603  int nconss, /**< number of constraints contained in this component */
604  SCIP_Bool* success /**< pointer to store whether the copying process was successful */
605  )
606 {
607  char name[SCIP_MAXSTRLEN];
608  PROBLEM* problem;
609  SCIP* scip;
610  int minsize;
611 
612  assert(component != NULL);
613  assert(consmap != NULL);
614  assert(conss != NULL);
615  assert(success != NULL);
616  assert(component->nvars > 0);
617 
618  problem = component->problem;
619  assert(problem != NULL);
620 
621  scip = problem->scip;
622  assert(scip != NULL);
623 
624  (*success) = TRUE;
625 
626  SCIP_CALL( createSubscip(scip, conshdlrdata, &component->subscip) );
627 
628  if( component->subscip != NULL )
629  {
630  /* get minimum size of components to solve individually and set the parameter in the sub-SCIP */
631  minsize = getMinsize(scip, conshdlrdata);
632 
633  SCIP_CALL( SCIPsetIntParam(component->subscip, "constraints/" CONSHDLR_NAME "/minsize", minsize) );
634 
635  /* get name of the original problem and add "comp_nr" */
636  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, component->number);
637 
638  SCIP_CALL( copyToSubscip(scip, component->subscip, name, component->vars, component->subvars,
639  conss, varmap, consmap, component->nvars, nconss, success) );
640 
641  if( !(*success) )
642  {
643  SCIP_CALL( SCIPfree(&component->subscip) );
644  component->subscip = NULL;
645  }
646  }
647  else
648  (*success) = FALSE;
649 
650  return SCIP_OKAY;
651 }
652 
653 /** solve a given sub-SCIP up to the given limits */
654 static
656  SCIP* scip, /**< main SCIP */
657  SCIP* subscip, /**< sub-SCIP to solve */
658  SCIP_Longint nodelimit, /**< node limit */
659  SCIP_Real gaplimit /**< gap limit */
660  )
661 {
662  SCIP_Real timelimit;
663  SCIP_Real memorylimit;
664  SCIP_Bool avoidmemout;
665 
666  assert(scip != NULL);
667  assert(subscip != NULL);
668 
669  /* set time limit */
670  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
671  if( !SCIPisInfinity(scip, timelimit) )
672  {
673  timelimit -= SCIPgetSolvingTime(scip);
674  timelimit += SCIPgetSolvingTime(subscip);
675  }
676 
677  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
678  /* @todo count memory of other components */
679  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
680  if( !SCIPisInfinity(scip, memorylimit) )
681  {
682  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
683  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
684  }
685 
686  /* check if mem limit needs to be avoided */
687  SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
688 
689  /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == TRUE)
690  * to create a copy of SCIP, including external memory usage */
691  if( avoidmemout && memorylimit <= 0.0 )
692  {
693  SCIPdebugMessage("--> not solved (not enough memory left)\n");
694  return SCIP_OKAY;
695  }
696  else if( timelimit <= 0.0 )
697  {
698  SCIPdebugMessage("--> not solved (not enough time left)\n");
699  return SCIP_OKAY;
700  }
701 
702  /* SCIP copy limits will set wrong time limits since it does not take into account time spent already in the
703  * sub-SCIP; nevertheless, we call it to set the memory limit and unset all other limits, if set in the main SCIP
704  */
705  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
706 
707  /* set time and memory limit for the subproblem */
708  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
709 
710  /* only set soft time limit if it exists */
711  if( SCIPgetParam(scip, "limits/softtime") != NULL )
712  {
713  SCIP_Real softtimelimit;
714 
715  /* set soft time limit, if specified in main SCIP and if it exists */
716  SCIP_CALL( SCIPgetRealParam(scip, "limits/softtime", &softtimelimit) );
717  if( softtimelimit > -0.5 )
718  {
719  softtimelimit -= SCIPgetSolvingTime(scip);
720  softtimelimit += SCIPgetSolvingTime(subscip);
721  softtimelimit = MAX(softtimelimit, 0.0);
722  }
723 
724  SCIP_CALL( SCIPsetRealParam(subscip, "limits/softtime", softtimelimit) );
725  }
726 
727  /* set gap limit */
728  SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", gaplimit) );
729 
730  /* set node limit */
731  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
732 
733  /* solve the subproblem */
734  SCIP_CALL( SCIPsolve(subscip) );
735 
736 #ifdef SCIP_MORE_DEBUG
737  SCIP_CALL( SCIPprintBestSol(subscip, NULL, FALSE) );
738  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
739 #endif
740 
741  return SCIP_OKAY;
742 }
743 
744 /** solve a connected component during presolving and evaluate the result */
745 static
747  SCIP* scip, /**< SCIP main data structure */
748  SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
749  SCIP* subscip, /**< sub-SCIP to be solved */
750  SCIP_VAR** vars, /**< array of variables copied to this component */
751  SCIP_VAR** subvars, /**< array of sub-SCIP variables corresponding to the vars array */
752  SCIP_CONS** conss, /**< array of constraints copied to this component */
753  int nvars, /**< number of variables copied to this component */
754  int nconss, /**< number of constraints copied to this component */
755  int* ndeletedconss, /**< pointer to store the number of deleted constraints */
756  int* nfixedvars, /**< pointer to store the number of fixed variables */
757  int* ntightenedbounds, /**< pointer to store the number of bound tightenings */
758  SCIP_RESULT* result, /**< pointer to store the result of the component solving */
759  SCIP_Bool* solved /**< pointer to store if the problem was solved to optimality */
760  )
761 {
762  int i;
763 
764  assert(scip != NULL);
765  assert(conshdlrdata != NULL);
766  assert(subscip != NULL);
767  assert(vars != NULL);
768  assert(conss != NULL);
769  assert(ndeletedconss != NULL);
770  assert(nfixedvars != NULL);
771  assert(ntightenedbounds != NULL);
772  assert(result != NULL);
773 
774  *solved = FALSE;
775 
776  SCIP_CALL( solveSubscip(scip, subscip, conshdlrdata->nodelimit, 0.0) );
777 
778  if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
779  {
780  SCIP_SOL* sol;
781  SCIP_VAR* var;
782  SCIP_VAR* subvar;
783  SCIP_Real* fixvals;
784  SCIP_Bool feasible;
785  SCIP_Bool infeasible;
786  SCIP_Bool fixed;
787 
788  sol = SCIPgetBestSol(subscip);
789 
790 #ifdef SCIP_DEBUG
791  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
792 #else
793  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, FALSE, FALSE) );
794 #endif
795 
796  SCIPdebugMessage("--> solved to optimality: time=%.2f, solution is%s feasible\n", SCIPgetSolvingTime(subscip), feasible ? "" : " not");
797 
798  SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nvars) );
799 
800  if( feasible )
801  {
802  SCIP_Real glb;
803  SCIP_Real gub;
804 
805  /* get values of variables in the optimal solution */
806  for( i = 0; i < nvars; ++i )
807  {
808  var = vars[i];
809  subvar = subvars[i];
810 
811  /* get global bounds */
812  glb = SCIPvarGetLbGlobal(var);
813  gub = SCIPvarGetUbGlobal(var);
814 
815  if( subvar != NULL )
816  {
817  /* get solution value from optimal solution of the sub-SCIP */
818  fixvals[i] = SCIPgetSolVal(subscip, sol, subvar);
819 
820  assert(SCIPisFeasLE(scip, fixvals[i], SCIPvarGetUbLocal(var)));
821  assert(SCIPisFeasGE(scip, fixvals[i], SCIPvarGetLbLocal(var)));
822 
823  /* checking a solution is done with a relative tolerance of feasibility epsilon, if we really want to
824  * change the bounds of the variables by fixing them, the old bounds must not be violated by more than
825  * the absolute epsilon; therefore, we change the fixing values, if needed, and mark that the solution
826  * has to be checked again
827  */
828  if( SCIPisGT(scip, fixvals[i], gub) )
829  {
830  SCIPdebugMessage("variable <%s> fixval: %f violates global upperbound: %f\n",
831  SCIPvarGetName(var), fixvals[i], gub);
832  fixvals[i] = gub;
833  feasible = FALSE;
834  }
835  else if( SCIPisLT(scip, fixvals[i], glb) )
836  {
837  SCIPdebugMessage("variable <%s> fixval: %f violates global lowerbound: %f\n",
838  SCIPvarGetName(var), fixvals[i], glb);
839  fixvals[i] = glb;
840  feasible = FALSE;
841  }
842  assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(var)));
843  assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(var)));
844  }
845  else
846  {
847  /* the variable was not copied, so it was cancelled out of constraints during copying;
848  * thus, the variable is not constrained and we fix it to its best bound
849  */
850  if( SCIPisPositive(scip, SCIPvarGetObj(var)) )
851  fixvals[i] = glb;
852  else if( SCIPisNegative(scip, SCIPvarGetObj(var)) )
853  fixvals[i] = gub;
854  else
855  {
856  fixvals[i] = 0.0;
857  fixvals[i] = MIN(fixvals[i], gub);
858  fixvals[i] = MAX(fixvals[i], glb);
859  }
860  }
861  }
862 
863  /* the solution value of at least one variable is feasible with a relative tolerance of feasibility epsilon,
864  * but infeasible with an absolute tolerance of epsilon; try to set the variables to the bounds and check
865  * solution again in the original space (changing the values might now introduce infeasibilities of constraints)
866  */
867  if( !feasible )
868  {
869  SCIP_Real origobj;
870 
871  SCIPdebugMessage("solution violates bounds by more than epsilon, check the corrected solution...\n");
872 
873  origobj = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
874 
875  SCIP_CALL( SCIPfreeTransform(subscip) );
876 
877  SCIP_CALL( SCIPcreateOrigSol(subscip, &sol, NULL) );
878 
879  /* set solution values of variables */
880  for( i = 0; i < nvars; ++i )
881  {
882  if( subvars[i] != NULL )
883  {
884  SCIP_CALL( SCIPsetSolVal(subscip, sol, subvars[i], fixvals[i]) );
885  }
886  }
887 
888  /* check the solution; integrality and bounds should be fulfilled and do not have to be checked */
889  SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &feasible) );
890 
891 #ifndef NDEBUG
892  /* in debug mode, we additionally check integrality and bounds */
893  if( feasible )
894  {
895  SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, TRUE, TRUE, FALSE, &feasible) );
896  assert(feasible);
897  }
898 #endif
899 
900  SCIPdebugMessage("--> corrected solution is%s feasible\n", feasible ? "" : " not");
901 
902  if( !SCIPisFeasEQ(subscip, SCIPsolGetOrigObj(sol), origobj) )
903  {
904  SCIPdebugMessage("--> corrected solution has a different objective value (old=%16.9g, corrected=%16.9g)\n",
905  origobj, SCIPsolGetOrigObj(sol));
906 
907  feasible = FALSE;
908  }
909 
910  SCIP_CALL( SCIPfreeSol(subscip, &sol) );
911  }
912 
913  /* if the solution is feasible, fix variables and delete constraints of the component */
914  if( feasible )
915  {
916  /* fix variables */
917  for( i = 0; i < nvars; ++i )
918  {
919  assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(vars[i])));
920  assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(vars[i])));
921  assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbGlobal(vars[i])));
922  assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbGlobal(vars[i])));
923 
924  SCIP_CALL( SCIPfixVar(scip, vars[i], fixvals[i], &infeasible, &fixed) );
926  assert(!infeasible);
927  assert(fixed);
928  (*nfixedvars)++;
929  }
930 
931  /* delete constraints */
932  for( i = 0; i < nconss; ++i )
933  {
934  SCIP_CALL( SCIPdelCons(scip, conss[i]) );
935  (*ndeletedconss)++;
936  }
937 
938  *result = SCIP_SUCCESS;
939  *solved = TRUE;
940  }
941  }
942 
943  SCIPfreeBufferArray(scip, &fixvals);
944  }
945  else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
946  {
947  *result = SCIP_CUTOFF;
948  }
949  else if( SCIPgetStatus(subscip) == SCIP_STATUS_UNBOUNDED || SCIPgetStatus(subscip) == SCIP_STATUS_INFORUNBD )
950  {
951  /* TODO: store unbounded ray in original SCIP data structure */
952  *result = SCIP_UNBOUNDED;
953  }
954  else
955  {
956  SCIPdebugMessage("--> solving interrupted (status=%d, time=%.2f)\n",
957  SCIPgetStatus(subscip), SCIPgetSolvingTime(subscip));
958 
959  /* transfer global fixings to the original problem; we can only do this, if we did not find a solution in the
960  * subproblem, because otherwise, the primal bound might lead to dual reductions that cannot be transferred to
961  * the original problem without also transferring the possibly suboptimal solution (which is currently not
962  * possible)
963  */
964  if( SCIPgetNSols(subscip) == 0 )
965  {
966  SCIP_Bool infeasible;
967  SCIP_Bool tightened;
968  int ntightened;
969 
970  ntightened = 0;
971 
972  for( i = 0; i < nvars; ++i )
973  {
974  if( subvars[i] == NULL )
975  continue;
976 
977  SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE,
978  &infeasible, &tightened) );
979  assert(!infeasible);
980  if( tightened )
981  ntightened++;
982 
983  SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE,
984  &infeasible, &tightened) );
985  assert(!infeasible);
986  if( tightened )
987  ntightened++;
988  }
989 
990  *result = SCIP_SUCCESS;
991 
992  *ntightenedbounds += ntightened;
993 
994  SCIPdebugMessage("--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened);
995  }
996  }
997 
998  return SCIP_OKAY;
999 }
1000 
1001 /** (continues) solving a connected component */
1002 static
1004  COMPONENT* component, /**< component structure */
1005  SCIP_Bool lastcomponent, /**< is this the last component to be solved? */
1006  SCIP_RESULT* result /**< pointer to store the result of the solving process */
1007  )
1008 {
1009  PROBLEM* problem;
1010  SCIP* scip;
1011  SCIP* subscip;
1012  SCIP_SOL* bestsol;
1013  SCIP_Longint nodelimit;
1014  SCIP_Longint lastnnodes;
1015  SCIP_Real gaplimit;
1016  SCIP_STATUS status;
1017 
1018  assert(component != NULL);
1019 
1020  problem = component->problem;
1021  assert(problem != NULL);
1022 
1023  scip = problem->scip;
1024  assert(scip != NULL);
1025 
1026  subscip = component->subscip;
1027  assert(subscip != NULL);
1028 
1029  *result = SCIP_DIDNOTRUN;
1030 
1031  SCIPdebugMessage("solve component <%s> (ncalls=%d, absgap=%.9g)\n",
1032  SCIPgetProbName(subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1033 
1034  bestsol = SCIPgetBestSol(scip);
1035 
1036  /* update best solution of component */
1037  if( bestsol != NULL && SCIPsolGetIndex(bestsol) != component->lastbestsolindex )
1038  {
1039  SCIP_SOL* compsol = component->workingsol;
1040  SCIP_VAR** vars = component->vars;
1041  SCIP_VAR** subvars = component->subvars;
1042  int nvars = component->nvars;
1043  int v;
1044 
1045  component->lastbestsolindex = SCIPsolGetIndex(bestsol);
1046 
1047  /* set solution values of component variables */
1048  for( v = 0; v < nvars; ++v )
1049  {
1050  if( subvars[v] != NULL )
1051  {
1052  SCIP_CALL( SCIPsetSolVal(subscip, compsol, subvars[v], SCIPgetSolVal(scip, bestsol, vars[v])) );
1053  }
1054  }
1055 #ifndef NDEBUG
1056  for( v = 0; v < component->nfixedvars; ++v )
1057  {
1058  if( component->fixedsubvars[v] != NULL )
1059  assert(SCIPisEQ(scip, SCIPgetSolVal(subscip, compsol, component->fixedsubvars[v]),
1060  SCIPvarGetLbGlobal(component->fixedsubvars[v])));
1061  }
1062 #endif
1063 
1064  if( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM
1065  || SCIPisLT(subscip, SCIPgetSolOrigObj(subscip, compsol), SCIPgetPrimalbound(subscip)) )
1066  {
1067  SCIP_Bool feasible;
1068 
1069  SCIPdebugMessage("checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n",
1070  SCIPgetProbName(subscip), problem->name,
1071  SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM ? SCIPinfinity(subscip) : SCIPgetPrimalbound(subscip),
1072  SCIPgetSolOrigObj(subscip, compsol));
1073 
1074  SCIP_CALL( SCIPcheckSolOrig(subscip, compsol, &feasible, FALSE, FALSE) );
1075  if( feasible )
1076  {
1077  SCIPdebugMessage("... feasible, adding solution.\n");
1078 
1079  SCIP_CALL( SCIPaddSol(subscip, compsol, &feasible) );
1080  }
1081 
1082  /* We cannot take the value of compsol as a cutoff bound if it was not feasible; some of the fixed connecting
1083  * variables are different and might not allow for a better solution in this component, but still for far
1084  * better solutions in other components. Therefore, the only cutoffbound we can apply is the cutoffbound
1085  * of the problem reduced by the dual bounds of the other components
1086  */
1087  if( problem->nlowerboundinf == 0 || (problem->nlowerboundinf == 1
1088  && SCIPisInfinity(scip, -component->lastdualbound)) )
1089  {
1090  SCIP_Real newcutoffbound = SCIPgetSolTransObj(scip, bestsol);
1091 
1092  assert(problem->nlowerboundinf > 0 || SCIPisGE(scip, newcutoffbound, problem->lowerbound));
1093 
1094  newcutoffbound = newcutoffbound - problem->lowerbound + component->fixedvarsobjsum;
1095 
1096  if( problem->nlowerboundinf == 0 )
1097  newcutoffbound += component->lastdualbound;
1098 
1099  if( SCIPisSumLT(subscip, newcutoffbound, SCIPgetCutoffbound(subscip)) )
1100  {
1101  SCIPdebugMessage("update cutoff bound to %16.9g\n", newcutoffbound);
1102 
1103  SCIP_CALL( SCIPupdateCutoffbound(subscip, newcutoffbound) );
1104  }
1105  }
1106  }
1107  }
1108 
1109  assert(component->laststatus != SCIP_STATUS_OPTIMAL);
1110 
1111  SCIPdebugMsg(scip, "solve sub-SCIP for component <%s> (ncalls=%d, absgap=%16.9g)\n",
1112  SCIPgetProbName(component->subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1113 
1114  if( component->ncalls == 0 )
1115  {
1116  nodelimit = 1LL;
1117  gaplimit = 0.0;
1118 
1119  lastnnodes = 0;
1120  }
1121  else
1122  {
1123  SCIP_Longint mainnodelimit;
1124 
1125  lastnnodes = SCIPgetNNodes(component->subscip);
1126 
1127  SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &mainnodelimit) );
1128 
1129  nodelimit = 2 * lastnnodes;
1130  nodelimit = MAX(nodelimit, 10LL);
1131 
1132  if( mainnodelimit != -1 )
1133  {
1134  assert(mainnodelimit >= lastnnodes);
1135  nodelimit = MIN(nodelimit, mainnodelimit - lastnnodes);
1136  }
1137 
1138  /* set a gap limit of half the current gap (at most 10%) */
1139  if( SCIPgetGap(component->subscip) < 0.2 )
1140  gaplimit = 0.5 * SCIPgetGap(component->subscip);
1141  else
1142  gaplimit = 0.1;
1143 
1144  if( lastcomponent )
1145  gaplimit = 0.0;
1146  }
1147 
1148  SCIP_CALL( solveSubscip(scip, subscip, nodelimit, gaplimit) );
1149 
1150  SCIPaddNNodes(scip, SCIPgetNNodes(subscip) - lastnnodes);
1151 
1153 
1154  status = SCIPgetStatus(subscip);
1155 
1156  component->laststatus = status;
1157  ++component->ncalls;
1158 
1159  SCIPdebugMsg(scip, "--> (status=%d, nodes=%lld, time=%.2f): gap: %12.5g%% absgap: %16.9g\n",
1160  status, SCIPgetNNodes(subscip), SCIPgetSolvingTime(subscip), 100.0*SCIPgetGap(subscip),
1161  SCIPgetPrimalbound(subscip) - SCIPgetDualbound(subscip));
1162 
1163  *result = SCIP_SUCCESS;
1164 
1165  switch( status )
1166  {
1167  case SCIP_STATUS_OPTIMAL:
1168  component->solved = TRUE;
1169  break;
1171  component->solved = TRUE;
1172 
1173  /* the problem is really infeasible */
1174  if( SCIPisInfinity(subscip, SCIPgetPrimalbound(subscip)) )
1175  {
1176  *result = SCIP_CUTOFF;
1177  }
1178  /* the cutoff bound was reached; no solution better than the cutoff bound exists */
1179  else
1180  {
1181  *result = SCIP_SUCCESS;
1182  component->laststatus = SCIP_STATUS_OPTIMAL;
1183  assert(SCIPisLE(subscip, SCIPgetDualbound(subscip), SCIPgetPrimalbound(subscip)));
1184  }
1185  break;
1186  case SCIP_STATUS_UNBOUNDED:
1187  case SCIP_STATUS_INFORUNBD:
1188  /* TODO: store unbounded ray in original SCIP data structure */
1189  *result = SCIP_UNBOUNDED;
1190  component->solved = TRUE;
1191  break;
1193  SCIP_CALL( SCIPinterruptSolve(scip) );
1194  break;
1195  case SCIP_STATUS_TERMINATE:
1196  case SCIP_STATUS_UNKNOWN:
1197  case SCIP_STATUS_NODELIMIT:
1200  case SCIP_STATUS_TIMELIMIT:
1201  case SCIP_STATUS_MEMLIMIT:
1202  case SCIP_STATUS_GAPLIMIT:
1203  case SCIP_STATUS_SOLLIMIT:
1206  default:
1207  break;
1208  }
1209 
1210  /* evaluate call */
1211  if( *result == SCIP_SUCCESS )
1212  {
1213  SCIP_SOL* sol = SCIPgetBestSol(subscip);
1214  SCIP_VAR* var;
1215  SCIP_VAR* subvar;
1216  SCIP_Real newdualbound;
1217  int v;
1218 
1219  /* get dual bound as the minimum of SCIP dual bound and sub-problems dual bound */
1220  newdualbound = SCIPgetDualbound(subscip) - component->fixedvarsobjsum;
1221 
1222  /* update dual bound of problem */
1223  if( !SCIPisEQ(scip, component->lastdualbound, newdualbound) )
1224  {
1225  assert(!SCIPisInfinity(scip, -newdualbound));
1226 
1227  /* first finite dual bound: decrease inf counter and add dual bound to problem dualbound */
1228  if( SCIPisInfinity(scip, -component->lastdualbound) )
1229  {
1230  --problem->nlowerboundinf;
1231  problem->lowerbound += newdualbound;
1232  }
1233  /* increase problem dual bound by dual bound delta */
1234  else
1235  {
1236  problem->lowerbound += (newdualbound - component->lastdualbound);
1237  }
1238 
1239  /* update problem dual bound if all problem components have a finite dual bound */
1240  if( problem->nlowerboundinf == 0 )
1241  {
1242  SCIPdebugMessage("component <%s>: dual bound increased from %16.9g to %16.9g, new dual bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1243  SCIPgetProbName(subscip), component->lastdualbound, newdualbound, problem->name,
1244  SCIPretransformObj(scip, problem->lowerbound),
1245  problem->nfeascomps == problem->ncomponents ?
1246  (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1247  MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ), SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1248  : SCIPinfinity(scip),
1249  problem->nfeascomps == problem->ncomponents ?
1250  SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1251  SCIP_CALL( SCIPupdateLocalLowerbound(scip, problem->lowerbound) );
1252  }
1253 
1254  /* store dual bound of this call */
1255  component->lastdualbound = newdualbound;
1256  }
1257 
1258  /* update primal solution of problem */
1259  if( sol != NULL && component->lastsolindex != SCIPsolGetIndex(sol) )
1260  {
1261  component->lastsolindex = SCIPsolGetIndex(sol);
1262 
1263  if( SCIPsolGetHeur(sol) != NULL )
1265  else
1266  SCIPsolSetHeur(problem->bestsol, NULL);
1267 
1268  /* increase counter for feasible problems if no solution was known before */
1269  if( SCIPisInfinity(scip, component->lastprimalbound) )
1270  ++(problem->nfeascomps);
1271 
1272  /* update working best solution in problem */
1273  for( v = 0; v < component->nvars; ++v )
1274  {
1275  var = component->vars[v];
1276  subvar = component->subvars[v];
1277  assert(var != NULL);
1278  assert(SCIPvarIsActive(var));
1279 
1280  if( subvar == NULL )
1281  continue;
1282 
1283  SCIP_CALL( SCIPsetSolVal(scip, problem->bestsol, var, SCIPgetSolVal(subscip, sol, subvar)) );
1284  }
1285 
1286  /* if we have a feasible solution for each component, add the working solution to the main problem */
1287  if( problem->nfeascomps == problem->ncomponents )
1288  {
1289  SCIP_Bool feasible;
1290 #ifdef SCIP_MORE_DEBUG
1291  SCIP_CALL( SCIPcheckSol(scip, problem->bestsol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
1292  assert(feasible);
1293 #endif
1294  SCIP_CALL( SCIPaddSol(scip, problem->bestsol, &feasible) );
1295 
1296  SCIPdebugMessage("component <%s>: primal bound decreased from %16.9g to %16.9g, new primal bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1297  SCIPgetProbName(subscip), component->lastprimalbound, SCIPgetPrimalbound(subscip), problem->name,
1298  SCIPgetSolOrigObj(scip, problem->bestsol),
1299  problem->nfeascomps == problem->ncomponents ?
1300  (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1301  MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ),SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1302  : SCIPinfinity(scip),
1303  problem->nfeascomps == problem->ncomponents ?
1304  SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1305  }
1306 
1307  /* store primal bound of this call */
1308  component->lastprimalbound = SCIPgetPrimalbound(subscip) - component->fixedvarsobjsum;
1309  }
1310 
1311  /* if the component was solved to optimality, we increase the respective counter and free the subscip */
1312  if( component->laststatus == SCIP_STATUS_OPTIMAL || component->laststatus == SCIP_STATUS_INFEASIBLE ||
1313  component->laststatus == SCIP_STATUS_UNBOUNDED || component->laststatus == SCIP_STATUS_INFORUNBD )
1314  {
1315  ++(problem->nsolvedcomps);
1316  component->solved = TRUE;
1317 
1318  /* free working solution and component */
1319  SCIP_CALL( SCIPfreeSol(subscip, &component->workingsol) );
1320 
1321  SCIP_CALL( SCIPfree(&subscip) );
1322  component->subscip = NULL;
1323  }
1324  }
1325 
1326  return SCIP_OKAY;
1327 }
1328 
1329 /** initialize subproblem structure */
1330 static
1332  SCIP* scip, /**< SCIP data structure */
1333  PROBLEM** problem, /**< pointer to subproblem structure */
1334  SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1335  int ncomponents /**< number of independent components */
1336  )
1337 {
1338  char name[SCIP_MAXSTRLEN];
1339  SCIP_VAR** vars;
1340  int nvars;
1341  int v;
1342 
1343  assert(scip != NULL);
1344  assert(problem != NULL);
1345 
1346  vars = SCIPgetVars(scip);
1347  nvars = SCIPgetNVars(scip);
1348 
1350  assert(*problem != NULL);
1351 
1352  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->components, ncomponents) );
1353 
1354  /* create a priority queue for the components: we need exactly ncomponents slots in the queue so it should never be
1355  * resized
1356  */
1357  SCIP_CALL( SCIPpqueueCreate(&(*problem)->compqueue, ncomponents, 1.2, componentSort, NULL) );
1358 
1359  (*problem)->scip = scip;
1360  (*problem)->lowerbound = fixedvarsobjsum;
1361  (*problem)->fixedvarsobjsum = fixedvarsobjsum;
1362  (*problem)->ncomponents = 0;
1363  (*problem)->componentssize = ncomponents;
1364  (*problem)->nlowerboundinf = ncomponents;
1365  (*problem)->nfeascomps = 0;
1366  (*problem)->nsolvedcomps = 0;
1367 
1368  if( SCIPgetDepth(scip) == 0 )
1369  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
1370  else
1371  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_node_%" SCIP_LONGINT_FORMAT, SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
1372 
1373  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name)+1) );
1374 
1375  SCIP_CALL( SCIPcreateSol(scip, &(*problem)->bestsol, NULL) );
1376 
1377  for( v = 0; v < nvars; v++ )
1378  {
1379  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1380  {
1381  SCIP_CALL( SCIPsetSolVal(scip, (*problem)->bestsol, vars[v],
1382  (SCIPvarGetUbLocal(vars[v]) + SCIPvarGetLbLocal(vars[v]))/2) );
1383  }
1384  }
1385 
1386  SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name);
1387 
1388  return SCIP_OKAY;
1389 }
1390 
1391 /** free subproblem structure */
1392 static
1394  PROBLEM** problem /**< pointer to problem to free */
1395  )
1396 {
1397  SCIP* scip;
1398  int c;
1399 
1400  assert(problem != NULL);
1401  assert(*problem != NULL);
1402 
1403  scip = (*problem)->scip;
1404  assert(scip != NULL);
1405 
1406  /* free best solution */
1407  if( (*problem)->bestsol != NULL )
1408  {
1409  SCIP_CALL( SCIPfreeSol(scip, &(*problem)->bestsol) );
1410  }
1411 
1412  /* free all components */
1413  for( c = (*problem)->ncomponents - 1; c >= 0; --c )
1414  {
1415  SCIP_CALL( freeComponent(&(*problem)->components[c]) );
1416  }
1417  if( (*problem)->components != NULL )
1418  {
1419  SCIPfreeBlockMemoryArray(scip, &(*problem)->components, (*problem)->componentssize);
1420  }
1421 
1422  /* free priority queue */
1423  SCIPpqueueFree(&(*problem)->compqueue);
1424 
1425  /* free problem name */
1426  SCIPfreeMemoryArray(scip, &(*problem)->name);
1427 
1428  /* free PROBLEM struct and set the pointer to NULL */
1430  *problem = NULL;
1431 
1432  return SCIP_OKAY;
1433 }
1434 
1435 /** creates and captures a components constraint */
1436 static
1438  SCIP* scip, /**< SCIP data structure */
1439  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1440  const char* name, /**< name of constraint */
1441  PROBLEM* problem /**< problem to be stored in the constraint */
1442  )
1443 {
1444  SCIP_CONSHDLR* conshdlr;
1445 
1446  /* find the samediff constraint handler */
1447  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1448  if( conshdlr == NULL )
1449  {
1450  SCIPerrorMessage("components constraint handler not found\n");
1451  return SCIP_PLUGINNOTFOUND;
1452  }
1453 
1454  /* create constraint */
1455  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, (SCIP_CONSDATA*)problem,
1456  FALSE, FALSE, FALSE, FALSE, TRUE,
1457  TRUE, FALSE, FALSE, FALSE, TRUE) );
1458 
1459  return SCIP_OKAY;
1460 }
1461 
1462 
1463 /** sort the components by size and sort vars and conss arrays by component numbers */
1464 static
1466  SCIP* scip, /**< SCIP data structure */
1467  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1468  SCIP_DIGRAPH* digraph, /**< directed graph */
1469  SCIP_CONS** conss, /**< constraints */
1470  SCIP_VAR** vars, /**< variables */
1471  int* varcomponent, /**< component numbers for the variables */
1472  int* conscomponent, /**< array to store component numbers for the constraints */
1473  int nconss, /**< number of constraints */
1474  int nvars, /**< number of variables */
1475  int* firstvaridxpercons, /**< array with index of first variable in vars array for each constraint */
1476  int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1477  int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1478  )
1479 {
1480  SCIP_Real* compsize;
1481  int* permu;
1482  int ncomponents;
1483  int nbinvars;
1484  int nintvars;
1485  int ndiscvars;
1486  int ncontvars;
1487  int minsize;
1488  int v;
1489  int c;
1490 
1491  assert(scip != NULL);
1492  assert(conshdlrdata != NULL);
1493  assert(digraph != NULL);
1494  assert(conss != NULL);
1495  assert(vars != NULL);
1496  assert(firstvaridxpercons != NULL);
1497 
1498  /* compute minimum size of components to solve individually */
1499  minsize = getMinsize(scip, conshdlrdata);
1500 
1501  ncomponents = SCIPdigraphGetNComponents(digraph);
1502  *ncompsminsize = 0;
1503  *ncompsmaxsize = 0;
1504 
1505  /* We want to sort the components in increasing complexity (number of discrete variables,
1506  * integer weighted with factor intfactor, continuous used as tie-breaker).
1507  * Therefore, we now get the variables for each component, count the different variable types
1508  * and compute a size as described above. Then, we rename the components
1509  * such that for i < j, component i has no higher complexity than component j.
1510  */
1511  SCIP_CALL( SCIPallocBufferArray(scip, &compsize, ncomponents) );
1512  SCIP_CALL( SCIPallocBufferArray(scip, &permu, ncomponents) );
1513 
1514  /* get number of variables in the components */
1515  for( c = 0; c < ncomponents; ++c )
1516  {
1517  int* cvars;
1518  int ncvars;
1519 
1520  SCIPdigraphGetComponent(digraph, c, &cvars, &ncvars);
1521  permu[c] = c;
1522  nbinvars = 0;
1523  nintvars = 0;
1524 
1525  for( v = 0; v < ncvars; ++v )
1526  {
1527  /* check whether variable is of binary or integer type */
1528  if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_BINARY )
1529  nbinvars++;
1530  else if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_INTEGER )
1531  nintvars++;
1532  }
1533  ncontvars = ncvars - nintvars - nbinvars;
1534  ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars);
1535  compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/nvars));
1536 
1537  /* component fulfills the maxsize requirement */
1538  if( ndiscvars <= conshdlrdata->maxintvars )
1539  ++(*ncompsmaxsize);
1540 
1541  /* component fulfills the minsize requirement */
1542  if( ncvars >= minsize )
1543  ++(*ncompsminsize);
1544  }
1545 
1546  /* get permutation of component numbers such that the size of the components is increasing */
1547  SCIPsortRealInt(compsize, permu, ncomponents);
1548 
1549  /* now, we need the reverse direction, i.e., for each component number, we store its new number
1550  * such that the components are sorted; for this, we abuse the conscomponent array
1551  */
1552  for( c = 0; c < ncomponents; ++c )
1553  conscomponent[permu[c]] = c;
1554 
1555  /* for each variable, replace the old component number by the new one */
1556  for( c = 0; c < nvars; ++c )
1557  varcomponent[c] = conscomponent[varcomponent[c]];
1558 
1559  SCIPfreeBufferArray(scip, &permu);
1560  SCIPfreeBufferArray(scip, &compsize);
1561 
1562  /* do the mapping from calculated components per variable to corresponding
1563  * constraints and sort the component-arrays for faster finding the
1564  * actual variables and constraints belonging to one component
1565  */
1566  for( c = 0; c < nconss; c++ )
1567  conscomponent[c] = (firstvaridxpercons[c] == -1 ? -1 : varcomponent[firstvaridxpercons[c]]);
1568 
1569  SCIPsortIntPtr(varcomponent, (void**)vars, nvars);
1570  SCIPsortIntPtr(conscomponent, (void**)conss, nconss);
1571 
1572  return SCIP_OKAY;
1573 }
1574 
1575 
1576 
1577 /** create PROBLEM structure for the current node and split it into components */
1578 static
1580  SCIP* scip, /**< SCIP data structure */
1581  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1582  SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1583  SCIP_VAR** sortedvars, /**< array of unfixed variables sorted by components */
1584  SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by components */
1585  int* compstartsvars, /**< start points of components in sortedvars array */
1586  int* compstartsconss, /**< start points of components in sortedconss array */
1587  int ncomponents, /**< number of components */
1588  PROBLEM** problem /**< pointer to store problem structure */
1589  )
1590 {
1591  COMPONENT* component;
1592  SCIP_HASHMAP* consmap;
1593  SCIP_HASHMAP* varmap;
1594  SCIP_VAR** compvars;
1595  SCIP_CONS** compconss;
1596  SCIP_Bool success = TRUE;
1597  int nfixedvars = SCIPgetNVars(scip) - compstartsvars[ncomponents];
1598  int ncompconss;
1599  int comp;
1600 
1601  /* init subproblem data structure */
1602  SCIP_CALL( initProblem(scip, problem, fixedvarsobjsum, ncomponents) );
1603  assert((*problem)->components != NULL);
1604 
1605  /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
1606  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), compstartsconss[ncomponents]) );
1607 
1608  /* loop over all components */
1609  for( comp = 0; comp < ncomponents; comp++ )
1610  {
1612  assert((*problem)->ncomponents == comp+1);
1613 
1614  component = &(*problem)->components[comp];
1615 
1616  /* get component variables and store them in component structure */
1617  compvars = &(sortedvars[compstartsvars[comp]]);
1618  component->nvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
1619  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &component->vars, compvars, component->nvars) );
1620  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->subvars, component->nvars) );
1621  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), component->nvars + nfixedvars) );
1622 
1623  /* get component constraints */
1624  compconss = &(sortedconss[compstartsconss[comp]]);
1625  ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
1626 
1627 #ifdef DETAILED_OUTPUT
1628  /* print details about the component including its size */
1629  if( component->nvars > 1 && ncompconss > 1 )
1630  {
1631  int nbinvars = 0;
1632  int nintvars = 0;
1633  int ncontvars = 0;
1634  int i;
1635 
1636  for( i = 0; i < component->nvars; ++i )
1637  {
1638  if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY )
1639  ++nbinvars;
1640  else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER )
1641  ++nintvars;
1642  else
1643  ++ncontvars;
1644  }
1645  SCIPdebugMsg(scip, "component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n",
1646  comp, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth,
1647  component->nvars, nbinvars, nintvars, ncontvars, ncompconss);
1648  }
1649 #endif
1650  assert(ncompconss > 0 || component->nvars == 1);
1651 
1652  SCIPdebugMsg(scip, "build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n",
1653  component->number, (*problem)->name, component->nvars, ncompconss);
1654 
1655 #ifndef NDEBUG
1656  {
1657  int i;
1658  for( i = 0; i < component->nvars; ++i )
1659  assert(SCIPvarIsActive(component->vars[i]));
1660  }
1661 #endif
1662 
1663  /* build subscip for component */
1664  SCIP_CALL( componentCreateSubscip(component, conshdlrdata, varmap, consmap, compconss, ncompconss, &success) );
1665 
1666  if( success )
1667  {
1668  SCIP_CALL( componentSetupWorkingSol(component, varmap) );
1669 
1670  /* add component to the priority queue of the problem structure */
1671  SCIP_CALL( SCIPpqueueInsert((*problem)->compqueue, component) );
1672  }
1673 
1674  SCIPhashmapFree(&varmap);
1675 
1676  if( !success )
1677  break;
1678  }
1679 
1680  SCIPhashmapFree(&consmap);
1681 
1682  if( !success )
1683  {
1684  /* free subproblem data structure since not all component could be copied */
1686  }
1687 
1688  return SCIP_OKAY;
1689 }
1690 
1691 /** continue solving a problem */
1692 static
1694  PROBLEM* problem, /**< problem structure */
1695  SCIP_RESULT* result /**< result pointer for the problem solve */
1696  )
1697 {
1698  COMPONENT* component;
1699  SCIP_RESULT subscipresult;
1700 
1701  assert(problem != NULL);
1702 
1703  *result = SCIP_SUCCESS;
1704 
1705  component = (COMPONENT*)SCIPpqueueRemove(problem->compqueue);
1706 
1707  /* continue solving the component */
1708  SCIP_CALL( solveComponent(component, SCIPpqueueNElems(problem->compqueue) == 0, &subscipresult) );
1709 
1710  /* if infeasibility or unboundedness was detected, return this */
1711  if( subscipresult == SCIP_CUTOFF || subscipresult == SCIP_UNBOUNDED )
1712  {
1713  *result = subscipresult;
1714  }
1715  /* the component was not solved to optimality, so we need to re-insert it in the components queue */
1716  else if( !component->solved )
1717  {
1718  SCIP_CALL( SCIPpqueueInsert(problem->compqueue, component) );
1719  *result = SCIP_DELAYNODE;
1720  }
1721  /* no unsolved components are left, so this problem has be completely evaluated and the node can be pruned */
1722  else if( SCIPpqueueNElems(problem->compqueue) == 0 )
1723  *result = SCIP_CUTOFF;
1724  /* there are some unsolved components left, so we delay this node */
1725  else
1726  *result = SCIP_DELAYNODE;
1727 
1728  return SCIP_OKAY;
1729 }
1730 
1731 /*
1732  * Local methods
1733  */
1734 
1735 /** loop over constraints, get active variables and fill directed graph */
1736 static
1738  SCIP* scip, /**< SCIP data structure */
1739  SCIP_DIGRAPH* digraph, /**< directed graph */
1740  SCIP_CONS** conss, /**< constraints */
1741  int nconss, /**< number of constraints */
1742  int* unfixedvarpos, /**< mapping from variable problem index to unfixed var index */
1743  int nunfixedvars, /**< number of unfixed variables */
1744  int* firstvaridxpercons, /**< array to store for each constraint the index in the local vars array
1745  * of the first variable of the constraint */
1746  SCIP_Bool* success /**< flag indicating successful directed graph filling */
1747  )
1748 {
1749  SCIP_VAR** consvars;
1750  int requiredsize;
1751  int nconsvars;
1752  int nvars;
1753  int idx1;
1754  int idx2;
1755  int c;
1756  int v;
1757 
1758  assert(scip != NULL);
1759  assert(digraph != NULL);
1760  assert(conss != NULL);
1761  assert(firstvaridxpercons != NULL);
1762  assert(success != NULL);
1763 
1764  *success = TRUE;
1765 
1766  nconsvars = 0;
1767  requiredsize = 0;
1768  nvars = SCIPgetNVars(scip);
1769 
1770  /* allocate buffer for storing active variables per constraint; size = nvars ensures that it will be big enough */
1771  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
1772 
1773  for( c = 0; c < nconss; ++c )
1774  {
1775  /* check for reached timelimit */
1776  if( (c % 1000 == 0) && SCIPisStopped(scip) )
1777  {
1778  *success = FALSE;
1779  break;
1780  }
1781 
1782  /* get number of variables for this constraint */
1783  SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nconsvars, success) );
1784 
1785  if( !(*success) )
1786  break;
1787 
1788  /* reallocate consvars array, if needed */
1789  if( nconsvars > nvars )
1790  {
1791  nvars = nconsvars;
1792  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, nvars) );
1793  }
1794 
1795 #ifndef NDEBUG
1796  /* clearing variables array to check for consistency */
1797  if( nconsvars == nvars )
1798  {
1799  BMSclearMemoryArray(consvars, nconsvars);
1800  }
1801  else
1802  {
1803  assert(nconsvars < nvars);
1804  BMSclearMemoryArray(consvars, nconsvars + 1);
1805  }
1806 #endif
1807 
1808  /* get variables for this constraint */
1809  SCIP_CALL( SCIPgetConsVars(scip, conss[c], consvars, nvars, success) );
1810 
1811  if( !(*success) )
1812  {
1813 #ifndef NDEBUG
1814  /* it looks strange if returning the number of variables was successful but not returning the variables */
1815  SCIPwarningMessage(scip, "constraint <%s> returned number of variables but returning variables failed\n", SCIPconsGetName(conss[c]));
1816 #endif
1817  break;
1818  }
1819 
1820 #ifndef NDEBUG
1821  /* check if returned variables are consistent with the number of variables that were returned */
1822  for( v = nconsvars - 1; v >= 0; --v )
1823  assert(consvars[v] != NULL);
1824  if( nconsvars < nvars )
1825  assert(consvars[nconsvars] == NULL);
1826 #endif
1827 
1828  /* transform given variables to active variables */
1829  SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nconsvars, nvars, &requiredsize) );
1830  assert(requiredsize <= nvars);
1831 
1832  firstvaridxpercons[c] = -1;
1833 
1834  /* store the index of the first unfixed variable and add edges to the directed graph */
1835  if( nconsvars > 0 )
1836  {
1837  v = 0;
1838  idx1 = -1;
1839 
1840  /* go through variables until the first unfixed one is reached (which has unfixedvarpos >= 0) */
1841  while( idx1 == -1 && v < nconsvars )
1842  {
1843  idx1 = SCIPvarGetProbindex(consvars[v]);
1844  assert(idx1 >= 0);
1845  idx1 = unfixedvarpos[idx1];
1846  assert(idx1 < nunfixedvars);
1847  ++v;
1848  }
1849 
1850  if( idx1 >= 0 )
1851  {
1852  /* save index of the first variable for later component assignment */
1853  firstvaridxpercons[c] = idx1;
1854 
1855  /* create sparse directed graph; sparse means to add only those edges necessary for component calculation,
1856  * i.e., add edges from the first variable to all others
1857  */
1858  for(; v < nconsvars; ++v )
1859  {
1860  idx2 = SCIPvarGetProbindex(consvars[v]);
1861  assert(idx2 >= 0);
1862  idx2 = unfixedvarpos[idx2];
1863  assert(idx2 < nunfixedvars);
1864 
1865  /* variable is fixed */
1866  if( idx2 < 0 )
1867  continue;
1868 
1869  /* we add only one directed edge, because the other direction is automatically added for component computation */
1870  SCIP_CALL( SCIPdigraphAddArc(digraph, idx1, idx2, NULL) );
1871  }
1872  }
1873  }
1874  }
1875 
1876  SCIPfreeBufferArray(scip, &consvars);
1877 
1878  return SCIP_OKAY;
1879 }
1880 
1881 /** search for components in the problem */
1882 static
1884  SCIP* scip, /**< SCIP main data structure */
1885  SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
1886  SCIP_Real* fixedvarsobjsum, /**< objective contribution of all locally fixed variables, or NULL if
1887  * fixed variables should not be disregarded */
1888  SCIP_VAR** sortedvars, /**< array to store variables sorted by components, should have enough size
1889  * for all variables */
1890  SCIP_CONS** sortedconss, /**< array to store (checked) constraints sorted by components, should have
1891  * enough size for all constraints */
1892  int* compstartsvars, /**< start points of components in sortedvars array */
1893  int* compstartsconss, /**< start points of components in sortedconss array */
1894  int* nsortedvars, /**< pointer to store the number of variables belonging to any component */
1895  int* nsortedconss, /**< pointer to store the number of (checked) constraints in components */
1896  int* ncomponents, /**< pointer to store the number of components */
1897  int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1898  int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1899 
1900  )
1901 {
1902  SCIP_CONS** tmpconss;
1903  SCIP_VAR** vars;
1904  SCIP_Bool success;
1905  int ntmpconss;
1906  int nvars;
1907  int c;
1908 
1909  assert(scip != NULL);
1910  assert(conshdlrdata != NULL);
1911  assert(sortedvars != NULL);
1912  assert(sortedconss != NULL);
1913  assert(compstartsvars != NULL);
1914  assert(compstartsconss != NULL);
1915  assert(nsortedvars != NULL);
1916  assert(nsortedconss != NULL);
1917  assert(ncomponents != NULL);
1918  assert(ncompsminsize != NULL);
1919  assert(ncompsmaxsize != NULL);
1920 
1921  vars = SCIPgetVars(scip);
1922  nvars = SCIPgetNVars(scip);
1923 
1924  if( fixedvarsobjsum != NULL )
1925  *fixedvarsobjsum = 0.0;
1926 
1927  *ncomponents = 0;
1928  *ncompsminsize = 0;
1929  *ncompsmaxsize = 0;
1930 
1931  /* collect checked constraints for component detection */
1932  ntmpconss = SCIPgetNConss(scip);
1933  tmpconss = SCIPgetConss(scip);
1934  (*nsortedconss) = 0;
1935  for( c = 0; c < ntmpconss; c++ )
1936  {
1937  sortedconss[(*nsortedconss)] = tmpconss[c];
1938  (*nsortedconss)++;
1939  }
1940 
1941  if( nvars > 1 && *nsortedconss > 1 )
1942  {
1943  int* unfixedvarpos;
1944  int* firstvaridxpercons;
1945  int* varlocks;
1946  int nunfixedvars = 0;
1947  int v;
1948 
1949  /* arrays for storing the first variable in each constraint (for later component assignment), the number of
1950  * variable locks, and the positions in the sortedvars array for all unfixed variables
1951  */
1952  SCIP_CALL( SCIPallocBufferArray(scip, &firstvaridxpercons, *nsortedconss) );
1953  SCIP_CALL( SCIPallocBufferArray(scip, &varlocks, nvars) );
1954  SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvarpos, nvars) );
1955 
1956  /* count number of varlocks for each variable (up + down locks) and multiply it by 2;
1957  * that value is used as an estimate of the number of arcs incident to the variable's node in the digraph
1958  * to be safe, we double this value
1959  */
1960  for( v = 0; v < nvars; ++v )
1961  {
1962  /* variable is not fixed or we do not want to disregard fixed variables */
1963  if( (fixedvarsobjsum == NULL) || SCIPisLT(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1964  {
1965  assert(nunfixedvars <= v);
1966  sortedvars[nunfixedvars] = vars[v];
1967  varlocks[nunfixedvars] = 4 * (SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL)
1969  unfixedvarpos[v] = nunfixedvars;
1970  ++nunfixedvars;
1971  }
1972  /* variable is fixed; update the objective sum of all fixed variables */
1973  else
1974  {
1975  unfixedvarpos[v] = -1;
1976  (*fixedvarsobjsum) += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
1977  }
1978  }
1979  *nsortedvars = nunfixedvars;
1980 
1981  if( nunfixedvars > 0 )
1982  {
1983  SCIP_DIGRAPH* digraph;
1984 
1985  /* create and fill directed graph */
1986  SCIP_CALL( SCIPcreateDigraph(scip, &digraph, nunfixedvars) );
1987  SCIP_CALL( SCIPdigraphSetSizes(digraph, varlocks) );
1988  SCIP_CALL( fillDigraph(scip, digraph, sortedconss, *nsortedconss, unfixedvarpos, nunfixedvars, firstvaridxpercons, &success) );
1989 
1990  if( success )
1991  {
1992  int* varcomponent;
1993  int* conscomponent;
1994 
1995  SCIP_CALL( SCIPallocBufferArray(scip, &varcomponent, nunfixedvars) );
1996  SCIP_CALL( SCIPallocBufferArray(scip, &conscomponent, MAX(nunfixedvars,*nsortedconss)) );
1997 
1998  /* compute independent components */
1999  SCIP_CALL( SCIPdigraphComputeUndirectedComponents(digraph, 1, varcomponent, ncomponents) );
2000 
2001  if( *ncomponents > 1 )
2002  {
2003  int nconss = *nsortedconss;
2004  int i;
2005 
2006  nvars = *nsortedvars;
2007 
2009  "cons components found %d undirected components at node %lld, depth %d (%d)\n",
2010  *ncomponents, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2011 
2012  /* sort components by size and sort variables and constraints by component number */
2013  SCIP_CALL( sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars,
2014  firstvaridxpercons, ncompsminsize, ncompsmaxsize) );
2015 
2016  /* determine start indices of components in sortedvars and sortedconss array */
2017  i = 0;
2018 
2019  while( i < nconss && conscomponent[i] == -1 )
2020  ++i;
2021 
2022  for( c = 0; c < *ncomponents + 1; ++c )
2023  {
2024  assert(i == nconss || conscomponent[i] >= c);
2025 
2026  compstartsconss[c] = i;
2027 
2028  while( i < nconss && conscomponent[i] == c )
2029  ++i;
2030  }
2031 
2032  for( c = 0, i = 0; c < *ncomponents + 1; ++c )
2033  {
2034  assert(i == nvars || varcomponent[i] >= c);
2035 
2036  compstartsvars[c] = i;
2037 
2038  while( i < nvars && varcomponent[i] == c )
2039  ++i;
2040  }
2041 
2042 #ifndef NDEBUG
2043  for( c = 0; c < *ncomponents; ++c )
2044  {
2045  for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i )
2046  assert(conscomponent[i] == c);
2047  for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i )
2048  assert(varcomponent[i] == c);
2049  }
2050 #endif
2051  }
2052 
2053  SCIPfreeBufferArray(scip, &conscomponent);
2054  SCIPfreeBufferArray(scip, &varcomponent);
2055  }
2056 
2057  SCIPdigraphFree(&digraph);
2058  }
2059 
2060  SCIPfreeBufferArray(scip, &unfixedvarpos);
2061  SCIPfreeBufferArray(scip, &varlocks);
2062  SCIPfreeBufferArray(scip, &firstvaridxpercons);
2063  }
2064 
2065  return SCIP_OKAY;
2066 }
2067 
2068 
2069 /*
2070  * Callback methods of constraint handler
2071  */
2072 
2073 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2074 static
2075 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents)
2076 { /*lint --e{715}*/
2077  assert(scip != NULL);
2078  assert(conshdlr != NULL);
2079  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2080 
2081  /* call inclusion method of constraint handler */
2083 
2084  *valid = TRUE;
2085 
2086  return SCIP_OKAY;
2087 }
2088 
2089 /** destructor of constraint handler to free user data (called when SCIP is exiting) */
2090 static
2091 SCIP_DECL_CONSFREE(conshdlrFreeComponents)
2092 { /*lint --e{715}*/
2093  SCIP_CONSHDLRDATA* conshdlrdata;
2094 
2095  /* free constraint handler data */
2096  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2097  assert(conshdlrdata != NULL);
2098 
2099  SCIPfreeBlockMemory(scip, &conshdlrdata);
2100  SCIPconshdlrSetData(conshdlr, NULL);
2101 
2102  return SCIP_OKAY;
2103 }
2104 
2105 /** domain propagation method of constraint handler */
2106 static
2107 SCIP_DECL_CONSPROP(consPropComponents)
2108 { /*lint --e{715}*/
2109  PROBLEM* problem;
2110  SCIP_CONSHDLRDATA* conshdlrdata;
2111  SCIP_Longint nodelimit;
2112 
2113  assert(conshdlr != NULL);
2114  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2115  assert(result != NULL);
2116  assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2117  assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2118 
2119  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2120  assert(conshdlrdata != NULL);
2121 
2122  *result = SCIP_DIDNOTRUN;
2123 
2124  /* do not try to detect independent components if the depth is too high */
2125  if( SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth
2126  && SCIPconshdlrGetNActiveConss(conshdlr) == 0 )
2127  return SCIP_OKAY;
2128 
2129  /* don't run in probing or in repropagation */
2130  if( SCIPinProbing(scip) || SCIPinRepropagation(scip) )
2131  return SCIP_OKAY;
2132 
2133  /* do not run, if not all variables are explicitly known */
2134  if( SCIPgetNActivePricers(scip) > 0 )
2135  return SCIP_OKAY;
2136 
2137  /* we do not want to run, if there are no variables left */
2138  if( SCIPgetNVars(scip) == 0 )
2139  return SCIP_OKAY;
2140 
2141  /* check for a reached timelimit */
2142  if( SCIPisStopped(scip) )
2143  return SCIP_OKAY;
2144 
2145  /* the components constraint handler does kind of dual reductions */
2146  if( !SCIPallowStrongDualReds(scip) || !SCIPallowWeakDualReds(scip) )
2147  return SCIP_OKAY;
2148 
2149  problem = NULL;
2150  *result = SCIP_DIDNOTFIND;
2151 
2152  /* the current node already has a components constraint storing a problem split into individual components */
2153  if( SCIPconshdlrGetNActiveConss(conshdlr) >= 1 )
2154  {
2155  assert(SCIPconshdlrGetNActiveConss(conshdlr) == 1);
2156 
2157  problem = (PROBLEM*)SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]);
2158  }
2159  /* no components constraint at the current node, search for components */
2160  else
2161  {
2163  SCIP_VAR** sortedvars;
2164  SCIP_CONS** sortedconss;
2165  int* compstartsvars;
2166  int* compstartsconss;
2167  int nsortedvars;
2168  int nsortedconss;
2169  int ncomponents;
2170  int ncompsminsize;
2171  int ncompsmaxsize;
2172 
2173  assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2174 
2175  /* allocate memory for sorted components */
2176  SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) );
2177  SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) );
2178  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) );
2179  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) );
2180 
2181  /* search for components */
2182  SCIP_CALL( findComponents(scip, conshdlrdata, &fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2183  compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2184 
2185  if( ncompsminsize > 1 )
2186  {
2187  SCIP_CONS* cons;
2188 
2189  SCIPdebugMsg(scip, "found %d components (%d fulfulling the minsize requirement) at node %lld at depth %d (%d)\n",
2190  ncomponents, ncompsminsize, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip),
2191  SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2192 
2193  /* if there are components with size smaller than the limit, we merge them with the smallest component */
2194  if( ncomponents > ncompsminsize )
2195  {
2196  int minsize;
2197  int size;
2198  int c;
2199  int m = 0;
2200 
2201  /* compute minimum size of components to solve individually */
2202  minsize = getMinsize(scip, conshdlrdata);
2203 
2204  for( c = 0; c < ncomponents; ++c )
2205  {
2206  size = compstartsvars[c+1] - compstartsvars[c];
2207 
2208  if( size >= minsize )
2209  {
2210  ++m;
2211  compstartsvars[m] = compstartsvars[c+1];
2212  compstartsconss[m] = compstartsconss[c+1];
2213  }
2214  /* the last component is too small */
2215  else if( c == ncomponents - 1 )
2216  {
2217  assert(m == ncompsminsize);
2218  compstartsvars[m] = compstartsvars[c+1];
2219  compstartsconss[m] = compstartsconss[c+1];
2220  }
2221  }
2222  assert(m == ncompsminsize);
2223  assert(compstartsvars[m] == nsortedvars);
2224  assert(compstartsconss[m] == nsortedconss);
2225 
2226  ncomponents = m;
2227  }
2228 
2229  SCIP_CALL( createAndSplitProblem(scip, conshdlrdata, fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2230  compstartsconss, ncomponents, &problem) );
2231 
2232  /* if the problem is not NULL, copying worked fine */
2233  if( problem != NULL )
2234  {
2235  SCIP_CALL( createConsComponents(scip, &cons, problem->name, problem) );
2236  SCIP_CALL( SCIPaddConsNode(scip, SCIPgetCurrentNode(scip), cons, NULL) );
2237  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2238  }
2239  }
2240 
2241  SCIPfreeBufferArray(scip, &compstartsconss);
2242  SCIPfreeBufferArray(scip, &compstartsvars);
2243  SCIPfreeBufferArray(scip, &sortedconss);
2244  SCIPfreeBufferArray(scip, &sortedvars);
2245  }
2246 
2247  /* (continue to) solve the problem
2248  *
2249  * If the problem was not solved to optimality yet, the result code is set to SCIP_DELAYNODE, so that after the
2250  * propagation is finished, the node is put back into the queue of open nodes and solving the components of the
2251  * problem will be continued when the node is focused and propagated the next time.
2252  * However, if we are at the root node, we continue solving the problem until it is solved or some limit is reached
2253  * since there are no other nodes to process and we want to avoid calling other propagation methods or heuristics
2254  * again and again
2255  */
2256  SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) );
2257  if( nodelimit == -1 )
2258  nodelimit = SCIP_LONGINT_MAX;
2259 
2260  do
2261  {
2262  if( problem != NULL )
2263  {
2264  SCIP_CALL( solveProblem(problem, result) );
2265  }
2266  } while( *result == SCIP_DELAYNODE && SCIPgetDepth(scip) == 0 && !SCIPisStopped(scip) && SCIPgetNNodes(scip) < nodelimit);
2267 
2268  return SCIP_OKAY;
2269 }
2270 
2271 /** presolving method of constraint handler */
2272 static
2273 SCIP_DECL_CONSPRESOL(consPresolComponents)
2274 { /*lint --e{715}*/
2275  SCIP_CONSHDLRDATA* conshdlrdata;
2276  SCIP_VAR** sortedvars;
2277  SCIP_CONS** sortedconss;
2278  int* compstartsvars;
2279  int* compstartsconss;
2280  int nsortedvars;
2281  int nsortedconss;
2282  int ncomponents;
2283  int ncompsminsize;
2284  int ncompsmaxsize;
2285  int nvars;
2286 
2287  assert(conshdlr != NULL);
2288  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2289  assert(result != NULL);
2290  assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2291  assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2292 
2293  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2294  assert(conshdlrdata != NULL);
2295 
2296  *result = SCIP_DIDNOTRUN;
2297 
2298  if( SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING || SCIPinProbing(scip) )
2299  return SCIP_OKAY;
2300 
2301  /* do not run, if not all variables are explicitly known */
2302  if( SCIPgetNActivePricers(scip) > 0 )
2303  return SCIP_OKAY;
2304 
2305  nvars = SCIPgetNVars(scip);
2306 
2307  /* we do not want to run, if there are no variables left */
2308  if( nvars == 0 )
2309  return SCIP_OKAY;
2310 
2311  /* only call the components presolving, if presolving would be stopped otherwise */
2312  if( !SCIPisPresolveFinished(scip) )
2313  return SCIP_OKAY;
2314 
2315  /* the components constraint handler does kind of dual reductions */
2316  if( !SCIPallowStrongDualReds(scip) || !SCIPallowWeakDualReds(scip) )
2317  return SCIP_OKAY;
2318 
2319  /* check for a reached timelimit */
2320  if( SCIPisStopped(scip) )
2321  return SCIP_OKAY;
2322 
2323  *result = SCIP_DIDNOTFIND;
2324 
2325  assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2326 
2327  /* allocate memory for sorted components */
2328  SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) );
2329  SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) );
2330  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) );
2331  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) );
2332 
2333  /* search for components */
2334  SCIP_CALL( findComponents(scip, conshdlrdata, NULL, sortedvars, sortedconss, compstartsvars,
2335  compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2336 
2337  if( ncompsmaxsize > 0 )
2338  {
2339  char name[SCIP_MAXSTRLEN];
2340  SCIP* subscip;
2341  SCIP_HASHMAP* consmap;
2342  SCIP_HASHMAP* varmap;
2343  SCIP_VAR** compvars;
2344  SCIP_VAR** subvars;
2345  SCIP_CONS** compconss;
2346  SCIP_Bool success;
2347  SCIP_Bool solved;
2348  int nsolved = 0;
2349  int ncompvars;
2350  int ncompconss;
2351  int comp;
2352 
2353  SCIPdebugMsg(scip, "found %d components (%d with small size) during presolving; overall problem size: %d vars (%d int, %d bin, %d cont), %d conss\n",
2354  ncomponents, ncompsmaxsize, SCIPgetNVars(scip), SCIPgetNBinVars(scip), SCIPgetNIntVars(scip), SCIPgetNContVars(scip) + SCIPgetNImplVars(scip), SCIPgetNConss(scip));
2355 
2356  /* build subscip */
2357  SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2358 
2359  if( subscip == NULL )
2360  goto TERMINATE;
2361 
2362  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/usesmalltables", TRUE) );
2363  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/" CONSHDLR_NAME "/propfreq", -1) );
2364 
2365  /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
2366  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), nsortedconss) );
2367 
2368  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nsortedvars) );
2369 
2370  /* loop over all components */
2371  for( comp = 0; comp < ncompsmaxsize && !SCIPisStopped(scip); comp++ )
2372  {
2373 #ifdef WITH_DEBUG_SOLUTION
2374  if( SCIPgetStage(subscip) > SCIP_STAGE_INIT )
2375  {
2376  SCIP_CALL( SCIPfree(&subscip) );
2377  SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2378  }
2379 #endif
2380  /* get component variables */
2381  compvars = &(sortedvars[compstartsvars[comp]]);
2382  ncompvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
2383 
2384  /* get component constraints */
2385  compconss = &(sortedconss[compstartsconss[comp]]);
2386  ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
2387 
2388  /* if we have an unlocked variable, let duality fixing do the job! */
2389  if( ncompconss == 0 )
2390  {
2391  assert(ncompvars == 1);
2392  continue;
2393  }
2394 
2395  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), ncompvars) );
2396 #ifdef DETAILED_OUTPUT
2397  {
2398  int nbinvars = 0;
2399  int nintvars = 0;
2400  int ncontvars = 0;
2401  int i;
2402 
2403  for( i = 0; i < ncompvars; ++i )
2404  {
2405  if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY )
2406  ++nbinvars;
2407  else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER )
2408  ++nintvars;
2409  else
2410  ++ncontvars;
2411  }
2412  SCIPdebugMsg(scip, "solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n",
2413  comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss);
2414  }
2415 #endif
2416 #ifndef NDEBUG
2417  {
2418  int i;
2419  for( i = 0; i < ncompvars; ++i )
2420  assert(SCIPvarIsActive(compvars[i]));
2421  }
2422 #endif
2423 
2424  /* get name of the original problem and add "comp_nr" */
2425  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), comp);
2426 
2427  SCIP_CALL( copyToSubscip(scip, subscip, name, compvars, subvars,
2428  compconss, varmap, consmap, ncompvars, ncompconss, &success) );
2429 
2430  if( !success )
2431  {
2432  SCIPhashmapFree(&varmap);
2433  continue;
2434  }
2435 
2436  /* set up debug solution */
2437 #ifdef WITH_DEBUG_SOLUTION
2438  if( SCIPdebugSolIsEnabled(scip) )
2439  {
2440  SCIP_SOL* debugsol;
2441  SCIP_Real val;
2442  int i;
2443 
2444  SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
2445 
2446  /* set solution values in the debug solution if it is available */
2447  if( debugsol != NULL )
2448  {
2449  SCIPdebugSolEnable(subscip);
2450 
2451  for( i = 0; i < ncompvars; ++i )
2452  {
2453  if( subvars[i] != NULL )
2454  {
2455  SCIP_CALL( SCIPdebugGetSolVal(scip, compvars[i], &val) );
2456  SCIP_CALL( SCIPdebugAddSolVal(subscip, subvars[i], val) );
2457  }
2458  }
2459  }
2460  }
2461 #endif
2462 
2463  /* solve the subproblem and evaluate the result, i.e. apply fixings of variables and remove constraints */
2464  SCIP_CALL( solveAndEvalSubscip(scip, conshdlrdata, subscip, compvars, subvars, compconss,
2465  ncompvars, ncompconss, ndelconss, nfixedvars, nchgbds, result, &solved) );
2466 
2467  /* free variable hash map */
2468  SCIPhashmapFree(&varmap);
2469 
2470  if( solved )
2471  ++nsolved;
2472 
2473  /* if the component is unbounded or infeasible, this holds for the complete problem as well */
2474  if( *result == SCIP_UNBOUNDED || *result == SCIP_CUTOFF )
2475  break;
2476  /* if there is only one component left, let's solve this in the main SCIP */
2477  else if( nsolved == ncomponents - 1 )
2478  break;
2479  }
2480 
2481  SCIPfreeBufferArray(scip, &subvars);
2482  SCIPhashmapFree(&consmap);
2483 
2484  SCIP_CALL( SCIPfree(&subscip) );
2485  }
2486 
2487  TERMINATE:
2488  SCIPfreeBufferArray(scip, &compstartsconss);
2489  SCIPfreeBufferArray(scip, &compstartsvars);
2490  SCIPfreeBufferArray(scip, &sortedconss);
2491  SCIPfreeBufferArray(scip, &sortedvars);
2492 
2493  return SCIP_OKAY;
2494 }
2495 
2496 /** frees specific constraint data */
2497 static
2498 SCIP_DECL_CONSDELETE(consDeleteComponents)
2499 { /*lint --e{715}*/
2500  assert(conshdlr != NULL);
2501  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2502  assert(consdata != NULL);
2503  assert(*consdata != NULL);
2504 
2505  SCIP_CALL( freeProblem((PROBLEM**) consdata) );
2506 
2507  return SCIP_OKAY;
2508 }
2509 
2510 /** constraint enforcing method of constraint handler for relaxation solutions */
2511 static
2512 SCIP_DECL_CONSENFORELAX(consEnforelaxComponents)
2513 { /*lint --e{715}*/
2514  assert(result != NULL );
2515 
2516  /* no enforcement is performed, but the callback is needed for all constraint handlers with needscons = FALSE */
2517  *result = SCIP_FEASIBLE;
2518 
2519  return SCIP_OKAY;
2520 }
2521 
2522 /** variable rounding lock method of constraint handler */
2523 static
2524 SCIP_DECL_CONSLOCK(consLockComponents)
2525 { /*lint --e{715}*/
2526  return SCIP_OKAY;
2527 }
2528 
2529 #ifndef NDEBUG
2530 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
2531 static
2532 SCIP_DECL_CONSINITSOL(consInitsolComponents)
2533 { /*lint --e{715}*/
2534  assert(nconss == 0);
2535 
2536  return SCIP_OKAY;
2537 }
2538 #endif
2539 
2540 #define consEnfolpComponents NULL
2541 #define consEnfopsComponents NULL
2542 #define consCheckComponents NULL
2544 /** creates the components constraint handler and includes it in SCIP */
2546  SCIP* scip /**< SCIP data structure */
2547  )
2548 {
2549  SCIP_CONSHDLRDATA* conshdlrdata;
2550  SCIP_CONSHDLR* conshdlr;
2551 
2552  /* create components propagator data */
2553  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2554  conshdlrdata->subscipdepth = 0;
2555 
2556  /* include constraint handler */
2560  conshdlrdata) );
2561  assert(conshdlr != NULL);
2562 
2563  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropComponents,
2565  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolComponents,
2567 
2568  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, conshdlrFreeComponents) );
2569  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxComponents) );
2570 #ifndef NDEBUG
2571  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolComponents) );
2572 #endif
2573  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyComponents, NULL) );
2574  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteComponents) );
2575 
2576  SCIP_CALL( SCIPaddIntParam(scip,
2577  "constraints/" CONSHDLR_NAME "/maxdepth",
2578  "maximum depth of a node to run components detection (-1: disable component detection during solving)",
2579  &conshdlrdata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2580  SCIP_CALL( SCIPaddIntParam(scip,
2581  "constraints/" CONSHDLR_NAME "/maxintvars",
2582  "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)",
2583  &conshdlrdata->maxintvars, TRUE, DEFAULT_MAXINTVARS, -1, INT_MAX, NULL, NULL) );
2584  SCIP_CALL( SCIPaddIntParam(scip,
2585  "constraints/" CONSHDLR_NAME "/minsize",
2586  "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound",
2587  &conshdlrdata->minsize, TRUE, DEFAULT_MINSIZE, 0, INT_MAX, NULL, NULL) );
2589  "constraints/" CONSHDLR_NAME "/minrelsize",
2590  "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound",
2591  &conshdlrdata->minrelsize, TRUE, DEFAULT_MINRELSIZE, 0.0, 1.0, NULL, NULL) );
2593  "constraints/" CONSHDLR_NAME "/nodelimit",
2594  "maximum number of nodes to be solved in subproblems during presolving",
2595  &conshdlrdata->nodelimit, FALSE, DEFAULT_NODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
2597  "constraints/" CONSHDLR_NAME "/intfactor",
2598  "the weight of an integer variable compared to binary variables",
2599  &conshdlrdata->intfactor, FALSE, DEFAULT_INTFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2601  "constraints/" CONSHDLR_NAME "/feastolfactor",
2602  "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0",
2603  &conshdlrdata->feastolfactor, TRUE, DEFAULT_FEASTOLFACTOR, 0.0, 1000000.0, NULL, NULL) );
2604 
2605  return SCIP_OKAY;
2606 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPprintBestSol(SCIP *scip, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:2370
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2080
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4205
#define CONSHDLR_ENFOPRIORITY
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1468
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:137
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
#define DEFAULT_MAXINTVARS
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
public methods for branch and bound tree
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:67
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE freeProblem(PROBLEM **problem)
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
static SCIP_DECL_CONSENFORELAX(consEnforelaxComponents)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
#define SCIP_MAXSTRLEN
Definition: def.h:293
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:7991
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2841
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
static SCIP_DECL_CONSDELETE(consDeleteComponents)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public solving methods
public methods for timing
#define DEFAULT_INTFACTOR
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
static SCIP_RETCODE solveSubscip(SCIP *scip, SCIP *subscip, SCIP_Longint nodelimit, SCIP_Real gaplimit)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:339
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
static int getMinsize(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPdigraphSetSizes(SCIP_DIGRAPH *digraph, int *sizes)
Definition: misc.c:7446
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
SCIP_RETCODE SCIPincludeConshdlrComponents(SCIP *scip)
public methods for problem variables
PROBLEM * problem
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8186
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1263
#define SCIPdebugMessage
Definition: pub_message.h:87
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8199
SCIP_Real lastprimalbound
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3086
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_MAXDEPTH
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
constraint handler for handling independent components
static SCIP_RETCODE freeComponent(COMPONENT *component)
public methods for SCIP variables
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
SCIP_RETCODE SCIPcopyPlugins(SCIP *sourcescip, SCIP *targetscip, SCIP_Bool copyreaders, SCIP_Bool copypricers, SCIP_Bool copyconshdlrs, SCIP_Bool copyconflicthdlrs, SCIP_Bool copypresolvers, SCIP_Bool copyrelaxators, SCIP_Bool copyseparators, SCIP_Bool copycutselectors, SCIP_Bool copypropagators, SCIP_Bool copyheuristics, SCIP_Bool copyeventhdlrs, SCIP_Bool copynodeselectors, SCIP_Bool copybranchrules, SCIP_Bool copydisplays, SCIP_Bool copydialogs, SCIP_Bool copytables, SCIP_Bool copyexprhdlrs, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:266
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:2550
static SCIP_RETCODE solveAndEvalSubscip(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_CONS **conss, int nvars, int nconss, int *ndeletedconss, int *nfixedvars, int *ntightenedbounds, SCIP_RESULT *result, SCIP_Bool *solved)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2170
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, 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: scip_cons.c:934
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:556
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
Definition: sol.c:2541
#define consEnfopsComponents
public methods for numerical tolerances
public methods for querying solving statistics
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
public methods for the branch-and-bound tree
static SCIP_DECL_CONSLOCK(consLockComponents)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7432
SCIP_Bool solved
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_NAME
static SCIP_RETCODE copyToSubscip(SCIP *scip, SCIP *subscip, const char *name, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_CONS **conss, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int nvars, int nconss, SCIP_Bool *success)
public methods for managing constraints
SCIP_VAR ** subvars
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
Definition: scip_general.c:603
SCIP_Real lastdualbound
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
#define CONSHDLR_PRESOLTIMING
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2558
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3497
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
#define CONSHDLR_MAXPREROUNDS
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_STATUS laststatus
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2604
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1482
SCIP_PARAM * SCIPgetParam(SCIP *scip, const char *name)
Definition: scip_param.c:225
public methods for problem copies
public methods for primal CIP solutions
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE componentSetupWorkingSol(COMPONENT *component, SCIP_HASHMAP *varmap)
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct Component COMPONENT
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_SORTPTRCOMP(componentSort)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7564
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:281
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip_param.c:279
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1434
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2514
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, 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_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1577
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3321
static SCIP_DECL_CONSPRESOL(consPresolComponents)
SCIP_VAR ** vars
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
public data structures and miscellaneous methods
static SCIP_RETCODE solveComponent(COMPONENT *component, SCIP_Bool lastcomponent, SCIP_RESULT *result)
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3432
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3440
static SCIP_RETCODE findComponents(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Real *fixedvarsobjsum, SCIP_VAR **sortedvars, SCIP_CONS **sortedconss, int *compstartsvars, int *compstartsconss, int *nsortedvars, int *nsortedconss, int *ncomponents, int *ncompsminsize, int *ncompsmaxsize)
#define SCIP_Bool
Definition: def.h:84
static SCIP_RETCODE createConsComponents(SCIP *scip, SCIP_CONS **cons, const char *name, PROBLEM *problem)
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2125
#define DEFAULT_MINSIZE
char * name
Definition: struct_cons.h:40
static SCIP_RETCODE fillDigraph(SCIP *scip, SCIP_DIGRAPH *digraph, SCIP_CONS **conss, int nconss, int *unfixedvarpos, int nunfixedvars, int *firstvaridxpercons, SCIP_Bool *success)
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
#define DEFAULT_FEASTOLFACTOR
#define consCheckComponents
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_Real SCIPgetGap(SCIP *scip)
static SCIP_RETCODE initComponent(PROBLEM *problem)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2649
struct Problem PROBLEM
#define SCIPdebugSolIsValidInSubtree(scip, isvalidinsubtree)
Definition: debug.h:282
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
methods for debugging
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
#define CONSHDLR_PROPFREQ
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
static SCIP_DECL_CONSPROP(consPropComponents)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8653
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
SCIP_RETCODE SCIPfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:358
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2035
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4624
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for variable pricer plugins
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
#define SCIP_REAL_MAX
Definition: def.h:178
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
Definition: scip_prob.c:3694
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
SCIP_RETCODE SCIPaddSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *stored)
Definition: scip_sol.c:2925
methods for sorting joint arrays of various types
SCIP_RETCODE SCIPcopyProb(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, const char *name)
Definition: scip_copy.c:518
general public methods
SCIP_VAR ** fixedvars
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:91
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
static SCIP_RETCODE componentCreateSubscip(COMPONENT *component, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool *success)
static SCIP_RETCODE sortComponents(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *digraph, SCIP_CONS **conss, SCIP_VAR **vars, int *varcomponent, int *conscomponent, int nconss, int nvars, int *firstvaridxpercons, int *ncompsminsize, int *ncompsmaxsize)
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_SOL * workingsol
SCIP_Real fixedvarsobjsum
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
public methods for message output
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1567
static SCIP_DECL_CONSINITSOL(consInitsolComponents)
#define DEFAULT_MINRELSIZE
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:117
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
static SCIP_RETCODE createAndSplitProblem(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Real fixedvarsobjsum, SCIP_VAR **sortedvars, SCIP_CONS **sortedconss, int *compstartsvars, int *compstartsconss, int ncomponents, PROBLEM **problem)
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
static SCIP_RETCODE solveProblem(PROBLEM *problem, SCIP_RESULT *result)
SCIP * subscip
public methods for message handling
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
#define DEFAULT_NODELIMIT
public methods for data structures
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
#define SCIP_Longint
Definition: def.h:162
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:280
#define CONSHDLR_DESC
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:358
#define SCIPdebugSolIsEnabled(scip)
Definition: debug.h:285
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int lastbestsolindex
static SCIP_RETCODE initProblem(SCIP *scip, PROBLEM **problem, SCIP_Real fixedvarsobjsum, int ncomponents)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
SCIP_VAR ** fixedsubvars
static SCIP_DECL_CONSFREE(conshdlrFreeComponents)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3516
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for primal heuristics
#define CONSHDLR_PROP_TIMING
SCIPallocBlockMemory(scip, subsol))
void SCIPaddNNodes(SCIP *scip, SCIP_Longint nnodes)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7470
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPdebugSolEnable(scip)
Definition: debug.h:283
public methods for global and local (sub)problems
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition: scip_var.c:1827
#define consEnfolpComponents
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP **subscip)
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8626
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
void SCIPvarMarkDeleteGlobalStructures(SCIP_VAR *var)
Definition: var.c:17508
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
memory allocation routines