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