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 WITH_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 #ifdef SCIP_MORE_DEBUG /* we print statistics later, so we need to copy statistics tables */
425  SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE,
426  TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, &success) );
427 #else
428  SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE,
429  TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, &success) );
430 #endif
431 
432  /* the plugins were successfully copied */
433  if( success )
434  {
435  SCIP_CONSHDLR* newconshdlr;
436  SCIP_CONSHDLRDATA* newconshdlrdata;
437 #ifdef WITH_DEBUG_SOLUTION
438  SCIP_Bool isvalid = FALSE;
439 #endif
440 
441  /* copy parameter settings */
442  SCIP_CALL( SCIPcopyParamSettings(scip, *subscip) );
443 
444  /* some general settings should not be fixed */
445  assert(!SCIPisParamFixed(*subscip, "limits/solutions"));
446  assert(!SCIPisParamFixed(*subscip, "limits/bestsol"));
447  assert(!SCIPisParamFixed(*subscip, "misc/usevartable"));
448  assert(!SCIPisParamFixed(*subscip, "misc/useconstable"));
449  assert(!SCIPisParamFixed(*subscip, "numerics/feastol"));
450  assert(!SCIPisParamFixed(*subscip, "misc/usesmalltables"));
451 
452  /* disable solution limits */
453  SCIP_CALL( SCIPsetIntParam(*subscip, "limits/solutions", -1) );
454  SCIP_CALL( SCIPsetIntParam(*subscip, "limits/bestsol", -1) );
455 
456  /* reduce the effort spent for hash tables; however, if the debug solution is enabled and valid in this subtree,
457  * hash tables are needed for installing the debug solution
458  */
459 #ifdef WITH_DEBUG_SOLUTION
460  SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) );
461  if( !isvalid && SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
462 #endif
463  {
464  SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/usevartable", FALSE) );
465  SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/useconstable", FALSE) );
466  }
467 
468  /* disable presolving */
470 
471  /* disable component presolving and fix the parameter */
472  SCIP_CALL( SCIPsetIntParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds", 0) );
473  SCIP_CALL( SCIPfixParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds") );
474 
475  /* find the components constraint handler in the sub-SCIP and inform it about the actual depth in the tree */
476  newconshdlr = SCIPfindConshdlr(*subscip, CONSHDLR_NAME);
477  assert(newconshdlr != NULL);
478 
479  newconshdlrdata = SCIPconshdlrGetData(newconshdlr);
480  assert(newconshdlrdata != NULL);
481  newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth + SCIPgetDepth(scip);
482 
483  /* disable output, unless in extended debug mode */
484 #ifndef SCIP_MORE_DEBUG
485  SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
486 #endif
487  }
488  else
489  {
490  SCIP_CALL( SCIPfree(subscip) );
491  *subscip = NULL;
492  }
493 
494  return SCIP_OKAY;
495 }
496 
497 /** copies the given variables and constraints to the given sub-SCIP */
498 static
500  SCIP* scip, /**< source SCIP */
501  SCIP* subscip, /**< target SCIP */
502  const char* name, /**< name for copied problem */
503  SCIP_VAR** vars, /**< array of variables to copy */
504  SCIP_VAR** subvars, /**< array to fill with copied vars */
505  SCIP_CONS** conss, /**< constraint to copy */
506  SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */
507  SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */
508  int nvars, /**< number of variables to copy */
509  int nconss, /**< number of constraints to copy */
510  SCIP_Bool* success /**< pointer to store whether copying was successful */
511  )
512 {
513  SCIP_CONS* newcons;
514  int i;
515 
516  assert(scip != NULL);
517  assert(subscip != NULL);
518  assert(vars != NULL);
519  assert(subvars != NULL);
520  assert(conss != NULL);
521  assert(varmap != NULL);
522  assert(consmap != NULL);
523  assert(success != NULL);
524 
525  *success = TRUE;
526 
527  /* create problem in sub-SCIP */
528  SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
529 
530  /* copy variables */
531  for( i = 0; i < nvars; ++i )
532  {
533  SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &subvars[i], varmap, consmap, FALSE, success) );
534 
535  /* abort if variable was not successfully copied */
536  if( !(*success) )
537  return SCIP_OKAY;
538  }
539  assert(nvars == SCIPgetNOrigVars(subscip));
540 
541  /* copy constraints */
542  for( i = 0; i < nconss; ++i )
543  {
544  assert(!SCIPconsIsModifiable(conss[i]));
545 
546  /* copy the constraint */
547  SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
548  SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]),
549  SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE,
550  SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) );
551 
552  /* abort if constraint was not successfully copied */
553  if( !(*success) )
554  return SCIP_OKAY;
555 
556  SCIP_CALL( SCIPaddCons(subscip, newcons) );
557  SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
558  }
559 
560  return SCIP_OKAY;
561 }
562 
563 /** create the sub-SCIP for a given component */
564 static
566  COMPONENT* component, /**< component structure */
567  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
568  SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */
569  SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */
570  SCIP_CONS** conss, /**< constraints contained in this component */
571  int nconss, /**< number of constraints contained in this component */
572  SCIP_Bool* success /**< pointer to store whether the copying process was successful */
573  )
574 {
575  char name[SCIP_MAXSTRLEN];
576  PROBLEM* problem;
577  SCIP* scip;
578  int minsize;
579 
580  assert(component != NULL);
581  assert(consmap != NULL);
582  assert(conss != NULL);
583  assert(success != NULL);
584  assert(component->nvars > 0);
585 
586  problem = component->problem;
587  assert(problem != NULL);
588 
589  scip = problem->scip;
590  assert(scip != NULL);
591 
592  (*success) = TRUE;
593 
594  SCIP_CALL( createSubscip(scip, conshdlrdata, &component->subscip) );
595 
596  if( component->subscip != NULL )
597  {
598  /* get minimum size of components to solve individually and set the parameter in the sub-SCIP */
599  minsize = getMinsize(scip, conshdlrdata);
600 
601  SCIP_CALL( SCIPsetIntParam(component->subscip, "constraints/" CONSHDLR_NAME "/minsize", minsize) );
602 
603  /* get name of the original problem and add "comp_nr" */
604  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, component->number);
605 
606  SCIP_CALL( copyToSubscip(scip, component->subscip, name, component->vars, component->subvars,
607  conss, varmap, consmap, component->nvars, nconss, success) );
608 
609  if( !(*success) )
610  {
611  SCIP_CALL( SCIPfree(&component->subscip) );
612  component->subscip = NULL;
613  }
614  }
615  else
616  (*success) = FALSE;
617 
618  return SCIP_OKAY;
619 }
620 
621 /** solve a given sub-SCIP up to the given limits */
622 static
624  SCIP* scip, /**< main SCIP */
625  SCIP* subscip, /**< sub-SCIP to solve */
626  SCIP_Longint nodelimit, /**< node limit */
627  SCIP_Real gaplimit /**< gap limit */
628  )
629 {
630  SCIP_Real timelimit;
631  SCIP_Real softtimelimit;
632  SCIP_Real memorylimit;
633 
634  assert(scip != NULL);
635  assert(subscip != NULL);
636 
637  /* set time limit */
638  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
639  if( !SCIPisInfinity(scip, timelimit) )
640  {
641  timelimit -= SCIPgetSolvingTime(scip);
642  timelimit += SCIPgetSolvingTime(subscip);
643  }
644 
645  /* set soft time limit, if specified in main SCIP */
646  SCIP_CALL( SCIPgetRealParam(scip, "limits/softtime", &softtimelimit) );
647  if( softtimelimit > -0.5 )
648  {
649  softtimelimit -= SCIPgetSolvingTime(scip);
650  softtimelimit += SCIPgetSolvingTime(subscip);
651  softtimelimit = MAX(softtimelimit, 0.0);
652  }
653 
654  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
655  /* @todo count memory of other components */
656  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
657  if( !SCIPisInfinity(scip, memorylimit) )
658  {
659  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
660  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
661  }
662 
663  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
664  if( timelimit <= 0.0 || memorylimit <= 0.0)
665  {
666  SCIPdebugMessage("--> not solved (not enough memory or time left)\n");
667  return SCIP_OKAY;
668  }
669 
670  /* SCIP copy limits will set wrong time limits since it does not take into account time spent already in the
671  * sub-SCIP; nevertheless, we call it to set the memory limit and unset all other limits, if set in the main SCIP
672  */
673  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
674 
675  /* set time and memory limit for the subproblem */
676  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
677  SCIP_CALL( SCIPsetRealParam(subscip, "limits/softtime", softtimelimit) );
678 
679  /* set gap limit */
680  SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", gaplimit) );
681 
682  /* set node limit */
683  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
684 
685  /* solve the subproblem */
686  SCIP_CALL( SCIPsolve(subscip) );
687 
688 #ifdef SCIP_MORE_DEBUG
689  SCIP_CALL( SCIPprintBestSol(subscip, NULL, FALSE) );
690  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
691 #endif
692 
693  return SCIP_OKAY;
694 }
695 
696 /** solve a connected component during presolving and evaluate the result */
697 static
699  SCIP* scip, /**< SCIP main data structure */
700  SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
701  SCIP* subscip, /**< sub-SCIP to be solved */
702  SCIP_VAR** vars, /**< array of variables copied to this component */
703  SCIP_VAR** subvars, /**< array of sub-SCIP variables corresponding to the vars array */
704  SCIP_CONS** conss, /**< array of constraints copied to this component */
705  int nvars, /**< number of variables copied to this component */
706  int nconss, /**< number of constraints copied to this component */
707  int* ndeletedconss, /**< pointer to store the number of deleted constraints */
708  int* nfixedvars, /**< pointer to store the number of fixed variables */
709  int* ntightenedbounds, /**< pointer to store the number of bound tightenings */
710  SCIP_RESULT* result, /**< pointer to store the result of the component solving */
711  SCIP_Bool* solved /**< pointer to store if the problem was solved to optimality */
712  )
713 {
714  int i;
715 
716  assert(scip != NULL);
717  assert(conshdlrdata != NULL);
718  assert(subscip != NULL);
719  assert(vars != NULL);
720  assert(conss != NULL);
721  assert(ndeletedconss != NULL);
722  assert(nfixedvars != NULL);
723  assert(ntightenedbounds != NULL);
724  assert(result != NULL);
725 
726  *solved = FALSE;
727 
728  SCIP_CALL( solveSubscip(scip, subscip, conshdlrdata->nodelimit, 0.0) );
729 
730  if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
731  {
732  SCIP_SOL* sol;
733  SCIP_VAR* var;
734  SCIP_VAR* subvar;
735  SCIP_Real* fixvals;
736  SCIP_Bool feasible;
737  SCIP_Bool infeasible;
738  SCIP_Bool fixed;
739 
740  sol = SCIPgetBestSol(subscip);
741 
742 #ifdef SCIP_DEBUG
743  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
744 #else
745  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, FALSE, FALSE) );
746 #endif
747 
748  SCIPdebugMessage("--> solved to optimality: time=%.2f, solution is%s feasible\n", SCIPgetSolvingTime(subscip), feasible ? "" : " not");
749 
750  SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nvars) );
751 
752  if( feasible )
753  {
754  SCIP_Real glb;
755  SCIP_Real gub;
756 
757  /* get values of variables in the optimal solution */
758  for( i = 0; i < nvars; ++i )
759  {
760  var = vars[i];
761  subvar = subvars[i];
762 
763  /* get global bounds */
764  glb = SCIPvarGetLbGlobal(var);
765  gub = SCIPvarGetUbGlobal(var);
766 
767  if( subvar != NULL )
768  {
769  /* get solution value from optimal solution of the sub-SCIP */
770  fixvals[i] = SCIPgetSolVal(subscip, sol, subvar);
771 
772  assert(SCIPisFeasLE(scip, fixvals[i], SCIPvarGetUbLocal(var)));
773  assert(SCIPisFeasGE(scip, fixvals[i], SCIPvarGetLbLocal(var)));
774 
775  /* checking a solution is done with a relative tolerance of feasibility epsilon, if we really want to
776  * change the bounds of the variables by fixing them, the old bounds must not be violated by more than
777  * the absolute epsilon; therefore, we change the fixing values, if needed, and mark that the solution
778  * has to be checked again
779  */
780  if( SCIPisGT(scip, fixvals[i], gub) )
781  {
782  SCIPdebugMessage("variable <%s> fixval: %f violates global upperbound: %f\n",
783  SCIPvarGetName(var), fixvals[i], gub);
784  fixvals[i] = gub;
785  feasible = FALSE;
786  }
787  else if( SCIPisLT(scip, fixvals[i], glb) )
788  {
789  SCIPdebugMessage("variable <%s> fixval: %f violates global lowerbound: %f\n",
790  SCIPvarGetName(var), fixvals[i], glb);
791  fixvals[i] = glb;
792  feasible = FALSE;
793  }
794  assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(var)));
795  assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(var)));
796  }
797  else
798  {
799  /* the variable was not copied, so it was cancelled out of constraints during copying;
800  * thus, the variable is not constrained and we fix it to its best bound
801  */
802  if( SCIPisPositive(scip, SCIPvarGetObj(var)) )
803  fixvals[i] = glb;
804  else if( SCIPisNegative(scip, SCIPvarGetObj(var)) )
805  fixvals[i] = gub;
806  else
807  {
808  fixvals[i] = 0.0;
809  fixvals[i] = MIN(fixvals[i], gub);
810  fixvals[i] = MAX(fixvals[i], glb);
811  }
812  }
813  }
814 
815  /* the solution value of at least one variable is feasible with a relative tolerance of feasibility epsilon,
816  * but infeasible with an absolute tolerance of epsilon; try to set the variables to the bounds and check
817  * solution again in the original space (changing the values might now introduce infeasibilities of constraints)
818  */
819  if( !feasible )
820  {
821  SCIP_Real origobj;
822 
823  SCIPdebugMessage("solution violates bounds by more than epsilon, check the corrected solution...\n");
824 
825  origobj = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
826 
827  SCIP_CALL( SCIPfreeTransform(subscip) );
828 
829  SCIP_CALL( SCIPcreateOrigSol(subscip, &sol, NULL) );
830 
831  /* set solution values of variables */
832  for( i = 0; i < nvars; ++i )
833  {
834  SCIP_CALL( SCIPsetSolVal(subscip, sol, subvars[i], fixvals[i]) );
835  }
836 
837  /* check the solution; integrality and bounds should be fulfilled and do not have to be checked */
838  SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &feasible) );
839 
840 #ifndef NDEBUG
841  /* in debug mode, we additionally check integrality and bounds */
842  if( feasible )
843  {
844  SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, TRUE, TRUE, FALSE, &feasible) );
845  assert(feasible);
846  }
847 #endif
848 
849  SCIPdebugMessage("--> corrected solution is%s feasible\n", feasible ? "" : " not");
850 
851  if( !SCIPisFeasEQ(subscip, SCIPsolGetOrigObj(sol), origobj) )
852  {
853  SCIPdebugMessage("--> corrected solution has a different objective value (old=%16.9g, corrected=%16.9g)\n",
854  origobj, SCIPsolGetOrigObj(sol));
855 
856  feasible = FALSE;
857  }
858 
859  SCIP_CALL( SCIPfreeSol(subscip, &sol) );
860  }
861 
862  /* if the solution is feasible, fix variables and delete constraints of the component */
863  if( feasible )
864  {
865  /* fix variables */
866  for( i = 0; i < nvars; ++i )
867  {
868  assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(vars[i])));
869  assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(vars[i])));
870  assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbGlobal(vars[i])));
871  assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbGlobal(vars[i])));
872 
873  SCIP_CALL( SCIPfixVar(scip, vars[i], fixvals[i], &infeasible, &fixed) );
875  assert(!infeasible);
876  assert(fixed);
877  (*nfixedvars)++;
878  }
879 
880  /* delete constraints */
881  for( i = 0; i < nconss; ++i )
882  {
883  SCIP_CALL( SCIPdelCons(scip, conss[i]) );
884  (*ndeletedconss)++;
885  }
886 
887  *result = SCIP_SUCCESS;
888  *solved = TRUE;
889  }
890  }
891 
892  SCIPfreeBufferArray(scip, &fixvals);
893  }
894  else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
895  {
896  *result = SCIP_CUTOFF;
897  }
898  else if( SCIPgetStatus(subscip) == SCIP_STATUS_UNBOUNDED || SCIPgetStatus(subscip) == SCIP_STATUS_INFORUNBD )
899  {
900  /* TODO: store unbounded ray in original SCIP data structure */
901  *result = SCIP_UNBOUNDED;
902  }
903  else
904  {
905  SCIPdebugMessage("--> solving interrupted (status=%d, time=%.2f)\n",
906  SCIPgetStatus(subscip), SCIPgetSolvingTime(subscip));
907 
908  /* transfer global fixings to the original problem; we can only do this, if we did not find a solution in the
909  * subproblem, because otherwise, the primal bound might lead to dual reductions that cannot be transferred to
910  * the original problem without also transferring the possibly suboptimal solution (which is currently not
911  * possible)
912  */
913  if( SCIPgetNSols(subscip) == 0 )
914  {
915  SCIP_Bool infeasible;
916  SCIP_Bool tightened;
917  int ntightened;
918 
919  ntightened = 0;
920 
921  for( i = 0; i < nvars; ++i )
922  {
923  assert(subvars[i] != NULL);
924 
925  SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE,
926  &infeasible, &tightened) );
927  assert(!infeasible);
928  if( tightened )
929  ntightened++;
930 
931  SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE,
932  &infeasible, &tightened) );
933  assert(!infeasible);
934  if( tightened )
935  ntightened++;
936  }
937 
938  *result = SCIP_SUCCESS;
939 
940  *ntightenedbounds += ntightened;
941 
942  SCIPdebugMessage("--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened);
943  }
944  }
945 
946  return SCIP_OKAY;
947 }
948 
949 /** (continues) solving a connected component */
950 static
952  COMPONENT* component, /**< component structure */
953  SCIP_Bool lastcomponent, /**< is this the last component to be solved? */
954  SCIP_RESULT* result /**< pointer to store the result of the solving process */
955  )
956 {
957  PROBLEM* problem;
958  SCIP* scip;
959  SCIP* subscip;
960  SCIP_SOL* bestsol;
961  SCIP_Longint nodelimit;
962  SCIP_Longint lastnnodes;
963  SCIP_Real gaplimit;
964  SCIP_STATUS status;
965 
966  assert(component != NULL);
967 
968  problem = component->problem;
969  assert(problem != NULL);
970 
971  scip = problem->scip;
972  assert(scip != NULL);
973 
974  subscip = component->subscip;
975  assert(subscip != NULL);
976 
977  *result = SCIP_DIDNOTRUN;
978 
979  SCIPdebugMessage("solve component <%s> (ncalls=%d, absgap=%.9g)\n",
980  SCIPgetProbName(subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
981 
982  bestsol = SCIPgetBestSol(scip);
983 
984  /* update best solution of component */
985  if( bestsol != NULL && SCIPsolGetIndex(bestsol) != component->lastbestsolindex )
986  {
987  SCIP_SOL* compsol = component->workingsol;
988  SCIP_VAR** vars = component->vars;
989  SCIP_VAR** subvars = component->subvars;
990  int nvars = component->nvars;
991  int v;
992 
993  component->lastbestsolindex = SCIPsolGetIndex(bestsol);
994 
995  /* set solution values of component variables */
996  for( v = 0; v < nvars; ++v )
997  {
998  SCIP_CALL( SCIPsetSolVal(subscip, compsol, subvars[v], SCIPgetSolVal(scip, bestsol, vars[v])) );
999  }
1000 #ifndef NDEBUG
1001  for( v = 0; v < component->nfixedvars; ++v )
1002  {
1003  assert(SCIPisEQ(scip, SCIPgetSolVal(subscip, compsol, component->fixedsubvars[v]),
1004  SCIPvarGetLbGlobal(component->fixedsubvars[v])));
1005  }
1006 #endif
1007 
1008  if( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM
1009  || SCIPisLT(subscip, SCIPgetSolOrigObj(subscip, compsol), SCIPgetPrimalbound(subscip)) )
1010  {
1011  SCIP_Bool feasible;
1012 
1013  SCIPdebugMessage("checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n",
1014  SCIPgetProbName(subscip), problem->name,
1015  SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM ? SCIPinfinity(subscip) : SCIPgetPrimalbound(subscip),
1016  SCIPgetSolOrigObj(subscip, compsol));
1017 
1018  SCIP_CALL( SCIPcheckSolOrig(subscip, compsol, &feasible, FALSE, FALSE) );
1019  if( feasible )
1020  {
1021  SCIPdebugMessage("... feasible, adding solution.\n");
1022 
1023  SCIP_CALL( SCIPaddSol(subscip, compsol, &feasible) );
1024  }
1025 
1026  /* We cannot take the value of compsol as a cutoff bound if it was not feasible; some of the fixed connecting
1027  * variables are different and might not allow for a better solution in this component, but still for far
1028  * better solutions in other components. Therefore, the only cutoffbound we can apply is the cutoffbound
1029  * of the problem reduced by the dual bounds of the other components
1030  */
1031  if( problem->nlowerboundinf == 0 || (problem->nlowerboundinf == 1
1032  && SCIPisInfinity(scip, -component->lastdualbound)) )
1033  {
1034  SCIP_Real newcutoffbound = SCIPgetSolTransObj(scip, bestsol);
1035 
1036  assert(problem->nlowerboundinf > 0 || SCIPisGE(scip, newcutoffbound, problem->lowerbound));
1037 
1038  newcutoffbound = newcutoffbound - problem->lowerbound + component->fixedvarsobjsum;
1039 
1040  if( problem->nlowerboundinf == 0 )
1041  newcutoffbound += component->lastdualbound;
1042 
1043  if( SCIPisSumLT(subscip, newcutoffbound, SCIPgetCutoffbound(subscip)) )
1044  {
1045  SCIPdebugMessage("update cutoff bound to %16.9g\n", newcutoffbound);
1046 
1047  SCIP_CALL( SCIPupdateCutoffbound(subscip, newcutoffbound) );
1048  }
1049  }
1050  }
1051  }
1052 
1053  assert(component->laststatus != SCIP_STATUS_OPTIMAL);
1054 
1055  SCIPdebugMsg(scip, "solve sub-SCIP for component <%s> (ncalls=%d, absgap=%16.9g)\n",
1056  SCIPgetProbName(component->subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1057 
1058  if( component->ncalls == 0 )
1059  {
1060  nodelimit = 1LL;
1061  gaplimit = 0.0;
1062 
1063  lastnnodes = 0;
1064  }
1065  else
1066  {
1067  SCIP_Longint mainnodelimit;
1068 
1069  lastnnodes = SCIPgetNNodes(component->subscip);
1070 
1071  SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &mainnodelimit) );
1072 
1073  nodelimit = 2 * lastnnodes;
1074  nodelimit = MAX(nodelimit, 10LL);
1075 
1076  if( mainnodelimit != -1 )
1077  {
1078  assert(mainnodelimit >= lastnnodes);
1079  nodelimit = MIN(nodelimit, mainnodelimit - lastnnodes);
1080  }
1081 
1082  /* set a gap limit of half the current gap (at most 10%) */
1083  if( SCIPgetGap(component->subscip) < 0.2 )
1084  gaplimit = 0.5 * SCIPgetGap(component->subscip);
1085  else
1086  gaplimit = 0.1;
1087 
1088  if( lastcomponent )
1089  gaplimit = 0.0;
1090  }
1091 
1092  SCIP_CALL( solveSubscip(scip, subscip, nodelimit, gaplimit) );
1093 
1094  SCIPaddNNodes(scip, SCIPgetNNodes(subscip) - lastnnodes);
1095 
1097 
1098  status = SCIPgetStatus(subscip);
1099 
1100  component->laststatus = status;
1101  ++component->ncalls;
1102 
1103  SCIPdebugMsg(scip, "--> (status=%d, nodes=%lld, time=%.2f): gap: %12.5g%% absgap: %16.9g\n",
1104  status, SCIPgetNNodes(subscip), SCIPgetSolvingTime(subscip), 100.0*SCIPgetGap(subscip),
1105  SCIPgetPrimalbound(subscip) - SCIPgetDualbound(subscip));
1106 
1107  *result = SCIP_SUCCESS;
1108 
1109  switch( status )
1110  {
1111  case SCIP_STATUS_OPTIMAL:
1112  component->solved = TRUE;
1113  break;
1115  component->solved = TRUE;
1116 
1117  /* the problem is really infeasible */
1118  if( SCIPisInfinity(subscip, SCIPgetPrimalbound(subscip)) )
1119  {
1120  *result = SCIP_CUTOFF;
1121  }
1122  /* the cutoff bound was reached; no solution better than the cutoff bound exists */
1123  else
1124  {
1125  *result = SCIP_SUCCESS;
1126  component->laststatus = SCIP_STATUS_OPTIMAL;
1127  assert(SCIPisLE(subscip, SCIPgetDualbound(subscip), SCIPgetPrimalbound(subscip)));
1128  }
1129  break;
1130  case SCIP_STATUS_UNBOUNDED:
1131  case SCIP_STATUS_INFORUNBD:
1132  /* TODO: store unbounded ray in original SCIP data structure */
1133  *result = SCIP_UNBOUNDED;
1134  component->solved = TRUE;
1135  break;
1137  SCIP_CALL( SCIPinterruptSolve(scip) );
1138  break;
1139  case SCIP_STATUS_UNKNOWN:
1140  case SCIP_STATUS_NODELIMIT:
1143  case SCIP_STATUS_TIMELIMIT:
1144  case SCIP_STATUS_MEMLIMIT:
1145  case SCIP_STATUS_GAPLIMIT:
1146  case SCIP_STATUS_SOLLIMIT:
1149  default:
1150  break;
1151  }
1152 
1153  /* evaluate call */
1154  if( *result == SCIP_SUCCESS )
1155  {
1156  SCIP_SOL* sol = SCIPgetBestSol(subscip);
1157  SCIP_VAR* var;
1158  SCIP_VAR* subvar;
1159  SCIP_Real newdualbound;
1160  int v;
1161 
1162  /* get dual bound as the minimum of SCIP dual bound and sub-problems dual bound */
1163  newdualbound = SCIPgetDualbound(subscip) - component->fixedvarsobjsum;
1164 
1165  /* update dual bound of problem */
1166  if( !SCIPisEQ(scip, component->lastdualbound, newdualbound) )
1167  {
1168  assert(!SCIPisInfinity(scip, -newdualbound));
1169 
1170  /* first finite dual bound: decrease inf counter and add dual bound to problem dualbound */
1171  if( SCIPisInfinity(scip, -component->lastdualbound) )
1172  {
1173  --problem->nlowerboundinf;
1174  problem->lowerbound += newdualbound;
1175  }
1176  /* increase problem dual bound by dual bound delta */
1177  else
1178  {
1179  problem->lowerbound += (newdualbound - component->lastdualbound);
1180  }
1181 
1182  /* update problem dual bound if all problem components have a finite dual bound */
1183  if( problem->nlowerboundinf == 0 )
1184  {
1185  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",
1186  SCIPgetProbName(subscip), component->lastdualbound, newdualbound, problem->name,
1187  SCIPretransformObj(scip, problem->lowerbound),
1188  problem->nfeascomps == problem->ncomponents ?
1189  (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1190  MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ), SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1191  : SCIPinfinity(scip),
1192  problem->nfeascomps == problem->ncomponents ?
1193  SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1194  SCIP_CALL( SCIPupdateLocalLowerbound(scip, problem->lowerbound) );
1195  }
1196 
1197  /* store dual bound of this call */
1198  component->lastdualbound = newdualbound;
1199  }
1200 
1201  /* update primal solution of problem */
1202  if( sol != NULL && component->lastsolindex != SCIPsolGetIndex(sol) )
1203  {
1204  component->lastsolindex = SCIPsolGetIndex(sol);
1205 
1206  if( SCIPsolGetHeur(sol) != NULL )
1208  else
1209  SCIPsolSetHeur(problem->bestsol, NULL);
1210 
1211  /* increase counter for feasible problems if no solution was known before */
1212  if( SCIPisInfinity(scip, component->lastprimalbound) )
1213  ++(problem->nfeascomps);
1214 
1215  /* update working best solution in problem */
1216  for( v = 0; v < component->nvars; ++v )
1217  {
1218  var = component->vars[v];
1219  subvar = component->subvars[v];
1220  assert(var != NULL);
1221  assert(subvar != NULL);
1222  assert(SCIPvarIsActive(var));
1223 
1224  SCIP_CALL( SCIPsetSolVal(scip, problem->bestsol, var, SCIPgetSolVal(subscip, sol, subvar)) );
1225  }
1226 
1227  /* if we have a feasible solution for each component, add the working solution to the main problem */
1228  if( problem->nfeascomps == problem->ncomponents )
1229  {
1230  SCIP_Bool feasible;
1231 #ifdef SCIP_MORE_DEBUG
1232  SCIP_CALL( SCIPcheckSol(scip, problem->bestsol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
1233  assert(feasible);
1234 #endif
1235  SCIP_CALL( SCIPaddSol(scip, problem->bestsol, &feasible) );
1236 
1237  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",
1238  SCIPgetProbName(subscip), component->lastprimalbound, SCIPgetPrimalbound(subscip), problem->name,
1239  SCIPgetSolOrigObj(scip, problem->bestsol),
1240  problem->nfeascomps == problem->ncomponents ?
1241  (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1242  MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ),SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1243  : SCIPinfinity(scip),
1244  problem->nfeascomps == problem->ncomponents ?
1245  SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1246  }
1247 
1248  /* store primal bound of this call */
1249  component->lastprimalbound = SCIPgetPrimalbound(subscip) - component->fixedvarsobjsum;
1250  }
1251 
1252  /* if the component was solved to optimality, we increase the respective counter and free the subscip */
1253  if( component->laststatus == SCIP_STATUS_OPTIMAL || component->laststatus == SCIP_STATUS_INFEASIBLE ||
1254  component->laststatus == SCIP_STATUS_UNBOUNDED || component->laststatus == SCIP_STATUS_INFORUNBD )
1255  {
1256  ++(problem->nsolvedcomps);
1257  component->solved = TRUE;
1258 
1259  /* free working solution and component */
1260  SCIP_CALL( SCIPfreeSol(subscip, &component->workingsol) );
1261 
1262  SCIP_CALL( SCIPfree(&subscip) );
1263  component->subscip = NULL;
1264  }
1265  }
1266 
1267  return SCIP_OKAY;
1268 }
1269 
1270 /** initialize subproblem structure */
1271 static
1273  SCIP* scip, /**< SCIP data structure */
1274  PROBLEM** problem, /**< pointer to subproblem structure */
1275  SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1276  int ncomponents /**< number of independent components */
1277  )
1278 {
1279  char name[SCIP_MAXSTRLEN];
1280  SCIP_VAR** vars;
1281  int nvars;
1282  int v;
1283 
1284  assert(scip != NULL);
1285  assert(problem != NULL);
1286 
1287  vars = SCIPgetVars(scip);
1288  nvars = SCIPgetNVars(scip);
1289 
1291  assert(*problem != NULL);
1292 
1293  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->components, ncomponents) );
1294 
1295  /* create a priority queue for the components: we need exactly ncomponents slots in the queue so it should never be
1296  * resized
1297  */
1298  SCIP_CALL( SCIPpqueueCreate(&(*problem)->compqueue, ncomponents, 1.2, componentSort) );
1299 
1300  (*problem)->scip = scip;
1301  (*problem)->lowerbound = fixedvarsobjsum;
1302  (*problem)->fixedvarsobjsum = fixedvarsobjsum;
1303  (*problem)->ncomponents = 0;
1304  (*problem)->componentssize = ncomponents;
1305  (*problem)->nlowerboundinf = ncomponents;
1306  (*problem)->nfeascomps = 0;
1307  (*problem)->nsolvedcomps = 0;
1308 
1309  if( SCIPgetDepth(scip) == 0 )
1310  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
1311  else
1312  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_node_%d", SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
1313 
1314  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name)+1) );
1315 
1316  SCIP_CALL( SCIPcreateSol(scip, &(*problem)->bestsol, NULL) );
1317 
1318  for( v = 0; v < nvars; v++ )
1319  {
1320  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1321  {
1322  SCIP_CALL( SCIPsetSolVal(scip, (*problem)->bestsol, vars[v],
1323  (SCIPvarGetUbLocal(vars[v]) + SCIPvarGetLbLocal(vars[v]))/2) );
1324  }
1325  }
1326 
1327  SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name);
1328 
1329  return SCIP_OKAY;
1330 }
1331 
1332 /** free subproblem structure */
1333 static
1335  PROBLEM** problem /**< pointer to problem to free */
1336  )
1337 {
1338  SCIP* scip;
1339  int c;
1340 
1341  assert(problem != NULL);
1342  assert(*problem != NULL);
1343 
1344  scip = (*problem)->scip;
1345  assert(scip != NULL);
1346 
1347  /* free best solution */
1348  if( (*problem)->bestsol != NULL )
1349  {
1350  SCIP_CALL( SCIPfreeSol(scip, &(*problem)->bestsol) );
1351  }
1352 
1353  /* free all components */
1354  for( c = (*problem)->ncomponents - 1; c >= 0; --c )
1355  {
1356  SCIP_CALL( freeComponent(&(*problem)->components[c]) );
1357  }
1358  if( (*problem)->components != NULL )
1359  {
1360  SCIPfreeBlockMemoryArray(scip, &(*problem)->components, (*problem)->componentssize);
1361  }
1362 
1363  /* free priority queue */
1364  SCIPpqueueFree(&(*problem)->compqueue);
1365 
1366  /* free problem name */
1367  SCIPfreeMemoryArray(scip, &(*problem)->name);
1368 
1369  /* free PROBLEM struct and set the pointer to NULL */
1371  *problem = NULL;
1372 
1373  return SCIP_OKAY;
1374 }
1375 
1376 /** creates and captures a components constraint */
1377 static
1379  SCIP* scip, /**< SCIP data structure */
1380  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1381  const char* name, /**< name of constraint */
1382  PROBLEM* problem /**< problem to be stored in the constraint */
1383  )
1384 {
1385  SCIP_CONSHDLR* conshdlr;
1386 
1387  /* find the samediff constraint handler */
1388  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1389  if( conshdlr == NULL )
1390  {
1391  SCIPerrorMessage("components constraint handler not found\n");
1392  return SCIP_PLUGINNOTFOUND;
1393  }
1394 
1395  /* create constraint */
1396  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, (SCIP_CONSDATA*)problem,
1397  FALSE, FALSE, FALSE, FALSE, TRUE,
1398  TRUE, FALSE, FALSE, FALSE, TRUE) );
1399 
1400  return SCIP_OKAY;
1401 }
1402 
1403 
1404 /** sort the components by size and sort vars and conss arrays by component numbers */
1405 static
1407  SCIP* scip, /**< SCIP data structure */
1408  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1409  SCIP_DIGRAPH* digraph, /**< directed graph */
1410  SCIP_CONS** conss, /**< constraints */
1411  SCIP_VAR** vars, /**< variables */
1412  int* varcomponent, /**< component numbers for the variables */
1413  int* conscomponent, /**< array to store component numbers for the constraints */
1414  int nconss, /**< number of constraints */
1415  int nvars, /**< number of variables */
1416  int* firstvaridxpercons, /**< array with index of first variable in vars array for each constraint */
1417  int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1418  int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1419  )
1420 {
1421  SCIP_Real* compsize;
1422  int* permu;
1423  int ncomponents;
1424  int nbinvars;
1425  int nintvars;
1426  int ndiscvars;
1427  int ncontvars;
1428  int minsize;
1429  int v;
1430  int c;
1431 
1432  assert(scip != NULL);
1433  assert(conshdlrdata != NULL);
1434  assert(digraph != NULL);
1435  assert(conss != NULL);
1436  assert(vars != NULL);
1437  assert(firstvaridxpercons != NULL);
1438 
1439  /* compute minimum size of components to solve individually */
1440  minsize = getMinsize(scip, conshdlrdata);
1441 
1442  ncomponents = SCIPdigraphGetNComponents(digraph);
1443  *ncompsminsize = 0;
1444  *ncompsmaxsize = 0;
1445 
1446  /* We want to sort the components in increasing complexity (number of discrete variables,
1447  * integer weighted with factor intfactor, continuous used as tie-breaker).
1448  * Therefore, we now get the variables for each component, count the different variable types
1449  * and compute a size as described above. Then, we rename the components
1450  * such that for i < j, component i has no higher complexity than component j.
1451  */
1452  SCIP_CALL( SCIPallocBufferArray(scip, &compsize, ncomponents) );
1453  SCIP_CALL( SCIPallocBufferArray(scip, &permu, ncomponents) );
1454 
1455  /* get number of variables in the components */
1456  for( c = 0; c < ncomponents; ++c )
1457  {
1458  int* cvars;
1459  int ncvars;
1460 
1461  SCIPdigraphGetComponent(digraph, c, &cvars, &ncvars);
1462  permu[c] = c;
1463  nbinvars = 0;
1464  nintvars = 0;
1465 
1466  for( v = 0; v < ncvars; ++v )
1467  {
1468  /* check whether variable is of binary or integer type */
1469  if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_BINARY )
1470  nbinvars++;
1471  else if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_INTEGER )
1472  nintvars++;
1473  }
1474  ncontvars = ncvars - nintvars - nbinvars;
1475  ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars);
1476  compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/nvars));
1477 
1478  /* component fulfills the maxsize requirement */
1479  if( ndiscvars <= conshdlrdata->maxintvars )
1480  ++(*ncompsmaxsize);
1481 
1482  /* component fulfills the minsize requirement */
1483  if( ncvars >= minsize )
1484  ++(*ncompsminsize);
1485  }
1486 
1487  /* get permutation of component numbers such that the size of the components is increasing */
1488  SCIPsortRealInt(compsize, permu, ncomponents);
1489 
1490  /* now, we need the reverse direction, i.e., for each component number, we store its new number
1491  * such that the components are sorted; for this, we abuse the conscomponent array
1492  */
1493  for( c = 0; c < ncomponents; ++c )
1494  conscomponent[permu[c]] = c;
1495 
1496  /* for each variable, replace the old component number by the new one */
1497  for( c = 0; c < nvars; ++c )
1498  varcomponent[c] = conscomponent[varcomponent[c]];
1499 
1500  SCIPfreeBufferArray(scip, &permu);
1501  SCIPfreeBufferArray(scip, &compsize);
1502 
1503  /* do the mapping from calculated components per variable to corresponding
1504  * constraints and sort the component-arrays for faster finding the
1505  * actual variables and constraints belonging to one component
1506  */
1507  for( c = 0; c < nconss; c++ )
1508  conscomponent[c] = (firstvaridxpercons[c] == -1 ? -1 : varcomponent[firstvaridxpercons[c]]);
1509 
1510  SCIPsortIntPtr(varcomponent, (void**)vars, nvars);
1511  SCIPsortIntPtr(conscomponent, (void**)conss, nconss);
1512 
1513  return SCIP_OKAY;
1514 }
1515 
1516 
1517 
1518 /** create PROBLEM structure for the current node and split it into components */
1519 static
1521  SCIP* scip, /**< SCIP data structure */
1522  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1523  SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1524  SCIP_VAR** sortedvars, /**< array of unfixed variables sorted by components */
1525  SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by components */
1526  int* compstartsvars, /**< start points of components in sortedvars array */
1527  int* compstartsconss, /**< start points of components in sortedconss array */
1528  int ncomponents, /**< number of components */
1529  PROBLEM** problem /**< pointer to store problem structure */
1530  )
1531 {
1532  COMPONENT* component;
1533  SCIP_HASHMAP* consmap;
1534  SCIP_HASHMAP* varmap;
1535  SCIP_VAR** compvars;
1536  SCIP_CONS** compconss;
1537  SCIP_Bool success = TRUE;
1538  int nfixedvars = SCIPgetNVars(scip) - compstartsvars[ncomponents];
1539  int ncompconss;
1540  int comp;
1541 
1542  /* init subproblem data structure */
1543  SCIP_CALL( initProblem(scip, problem, fixedvarsobjsum, ncomponents) );
1544  assert((*problem)->components != NULL);
1545 
1546  /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
1547  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), compstartsconss[ncomponents]) );
1548 
1549  /* loop over all components */
1550  for( comp = 0; comp < ncomponents; comp++ )
1551  {
1553  assert((*problem)->ncomponents == comp+1);
1554 
1555  component = &(*problem)->components[comp];
1556 
1557  /* get component variables and store them in component structure */
1558  compvars = &(sortedvars[compstartsvars[comp]]);
1559  component->nvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
1560  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &component->vars, compvars, component->nvars) );
1561  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->subvars, component->nvars) );
1562  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), component->nvars + nfixedvars) );
1563 
1564  /* get component constraints */
1565  compconss = &(sortedconss[compstartsconss[comp]]);
1566  ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
1567 
1568 #ifdef DETAILED_OUTPUT
1569  /* print details about the component including its size */
1570  if( component->nvars > 1 && ncompconss > 1 )
1571  {
1572  int nbinvars = 0;
1573  int nintvars = 0;
1574  int ncontvars = 0;
1575  int i;
1576 
1577  for( i = 0; i < component->nvars; ++i )
1578  {
1579  if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY )
1580  ++nbinvars;
1581  else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER )
1582  ++nintvars;
1583  else
1584  ++ncontvars;
1585  }
1586  SCIPdebugMsg(scip, "component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n",
1587  comp, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth,
1588  component->nvars, nbinvars, nintvars, ncontvars, ncompconss);
1589  }
1590 #endif
1591  assert(ncompconss > 0 || component->nvars == 1);
1592 
1593  SCIPdebugMsg(scip, "build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n",
1594  component->number, (*problem)->name, component->nvars, ncompconss);
1595 
1596 #ifndef NDEBUG
1597  {
1598  int i;
1599  for( i = 0; i < component->nvars; ++i )
1600  assert(SCIPvarIsActive(component->vars[i]));
1601  }
1602 #endif
1603 
1604  /* build subscip for component */
1605  SCIP_CALL( componentCreateSubscip(component, conshdlrdata, varmap, consmap, compconss, ncompconss, &success) );
1606 
1607  if( success )
1608  {
1609  SCIP_CALL( componentSetupWorkingSol(component, varmap) );
1610 
1611  /* add component to the priority queue of the problem structure */
1612  SCIP_CALL( SCIPpqueueInsert((*problem)->compqueue, component) );
1613  }
1614 
1615  SCIPhashmapFree(&varmap);
1616 
1617  if( !success )
1618  break;
1619  }
1620 
1621  SCIPhashmapFree(&consmap);
1622 
1623  if( !success )
1624  {
1625  /* free subproblem data structure since not all component could be copied */
1627  }
1628 
1629  return SCIP_OKAY;
1630 }
1631 
1632 /** continue solving a problem */
1633 static
1635  PROBLEM* problem, /**< problem structure */
1636  SCIP_RESULT* result /**< result pointer for the problem solve */
1637  )
1638 {
1639  COMPONENT* component;
1640  SCIP_RESULT subscipresult;
1641 
1642  assert(problem != NULL);
1643 
1644  *result = SCIP_SUCCESS;
1645 
1646  component = (COMPONENT*)SCIPpqueueRemove(problem->compqueue);
1647 
1648  /* continue solving the component */
1649  SCIP_CALL( solveComponent(component, SCIPpqueueNElems(problem->compqueue) == 0, &subscipresult) );
1650 
1651  /* if infeasibility or unboundedness was detected, return this */
1652  if( subscipresult == SCIP_CUTOFF || subscipresult == SCIP_UNBOUNDED )
1653  {
1654  *result = subscipresult;
1655  }
1656  /* the component was not solved to optimality, so we need to re-insert it in the components queue */
1657  else if( !component->solved )
1658  {
1659  SCIP_CALL( SCIPpqueueInsert(problem->compqueue, component) );
1660  *result = SCIP_DELAYNODE;
1661  }
1662  /* no unsolved components are left, so this problem has be completely evaluated and the node can be pruned */
1663  else if( SCIPpqueueNElems(problem->compqueue) == 0 )
1664  *result = SCIP_CUTOFF;
1665  /* there are some unsolved components left, so we delay this node */
1666  else
1667  *result = SCIP_DELAYNODE;
1668 
1669  return SCIP_OKAY;
1670 }
1671 
1672 /*
1673  * Local methods
1674  */
1675 
1676 /** loop over constraints, get active variables and fill directed graph */
1677 static
1679  SCIP* scip, /**< SCIP data structure */
1680  SCIP_DIGRAPH* digraph, /**< directed graph */
1681  SCIP_CONS** conss, /**< constraints */
1682  int nconss, /**< number of constraints */
1683  int* unfixedvarpos, /**< mapping from variable problem index to unfixed var index */
1684  int nunfixedvars, /**< number of unfixed variables */
1685  int* firstvaridxpercons, /**< array to store for each constraint the index in the local vars array
1686  * of the first variable of the constraint */
1687  SCIP_Bool* success /**< flag indicating successful directed graph filling */
1688  )
1689 {
1690  SCIP_VAR** consvars;
1691  int requiredsize;
1692  int nconsvars;
1693  int nvars;
1694  int idx1;
1695  int idx2;
1696  int c;
1697  int v;
1698 
1699  assert(scip != NULL);
1700  assert(digraph != NULL);
1701  assert(conss != NULL);
1702  assert(firstvaridxpercons != NULL);
1703  assert(success != NULL);
1704 
1705  *success = TRUE;
1706 
1707  nconsvars = 0;
1708  requiredsize = 0;
1709  nvars = SCIPgetNVars(scip);
1710 
1711  /* allocate buffer for storing active variables per constraint; size = nvars ensures that it will be big enough */
1712  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
1713 
1714  for( c = 0; c < nconss; ++c )
1715  {
1716  /* check for reached timelimit */
1717  if( (c % 1000 == 0) && SCIPisStopped(scip) )
1718  {
1719  *success = FALSE;
1720  break;
1721  }
1722 
1723  /* get number of variables for this constraint */
1724  SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nconsvars, success) );
1725 
1726  if( !(*success) )
1727  break;
1728 
1729  /* reallocate consvars array, if needed */
1730  if( nconsvars > nvars )
1731  {
1732  nvars = nconsvars;
1733  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, nvars) );
1734  }
1735 
1736 #ifndef NDEBUG
1737  /* clearing variables array to check for consistency */
1738  if( nconsvars == nvars )
1739  {
1740  BMSclearMemoryArray(consvars, nconsvars);
1741  }
1742  else
1743  {
1744  assert(nconsvars < nvars);
1745  BMSclearMemoryArray(consvars, nconsvars + 1);
1746  }
1747 #endif
1748 
1749  /* get variables for this constraint */
1750  SCIP_CALL( SCIPgetConsVars(scip, conss[c], consvars, nvars, success) );
1751 
1752  if( !(*success) )
1753  {
1754 #ifndef NDEBUG
1755  /* it looks strange if returning the number of variables was successful but not returning the variables */
1756  SCIPwarningMessage(scip, "constraint <%s> returned number of variables but returning variables failed\n", SCIPconsGetName(conss[c]));
1757 #endif
1758  break;
1759  }
1760 
1761 #ifndef NDEBUG
1762  /* check if returned variables are consistent with the number of variables that were returned */
1763  for( v = nconsvars - 1; v >= 0; --v )
1764  assert(consvars[v] != NULL);
1765  if( nconsvars < nvars )
1766  assert(consvars[nconsvars] == NULL);
1767 #endif
1768 
1769  /* transform given variables to active variables */
1770  SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nconsvars, nvars, &requiredsize) );
1771  assert(requiredsize <= nvars);
1772 
1773  firstvaridxpercons[c] = -1;
1774 
1775  /* store the index of the first unfixed variable and add edges to the directed graph */
1776  if( nconsvars > 0 )
1777  {
1778  v = 0;
1779  idx1 = -1;
1780 
1781  /* go through variables until the first unfixed one is reached (which has unfixedvarpos >= 0) */
1782  while( idx1 == -1 && v < nconsvars )
1783  {
1784  idx1 = SCIPvarGetProbindex(consvars[v]);
1785  assert(idx1 >= 0);
1786  idx1 = unfixedvarpos[idx1];
1787  assert(idx1 < nunfixedvars);
1788  ++v;
1789  }
1790 
1791  if( idx1 >= 0 )
1792  {
1793  /* save index of the first variable for later component assignment */
1794  firstvaridxpercons[c] = idx1;
1795 
1796  /* create sparse directed graph; sparse means to add only those edges necessary for component calculation,
1797  * i.e., add edges from the first variable to all others
1798  */
1799  for(; v < nconsvars; ++v )
1800  {
1801  idx2 = SCIPvarGetProbindex(consvars[v]);
1802  assert(idx2 >= 0);
1803  idx2 = unfixedvarpos[idx2];
1804  assert(idx2 < nunfixedvars);
1805 
1806  /* variable is fixed */
1807  if( idx2 < 0 )
1808  continue;
1809 
1810  /* we add only one directed edge, because the other direction is automatically added for component computation */
1811  SCIP_CALL( SCIPdigraphAddArc(digraph, idx1, idx2, NULL) );
1812  }
1813  }
1814  }
1815  }
1816 
1817  SCIPfreeBufferArray(scip, &consvars);
1818 
1819  return SCIP_OKAY;
1820 }
1821 
1822 /** search for components in the problem */
1823 static
1825  SCIP* scip, /**< SCIP main data structure */
1826  SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
1827  SCIP_Real* fixedvarsobjsum, /**< objective contribution of all locally fixed variables, or NULL if
1828  * fixed variables should not be disregarded */
1829  SCIP_VAR** sortedvars, /**< array to store variables sorted by components, should have enough size
1830  * for all variables */
1831  SCIP_CONS** sortedconss, /**< array to store (checked) constraints sorted by components, should have
1832  * enough size for all constraints */
1833  int* compstartsvars, /**< start points of components in sortedvars array */
1834  int* compstartsconss, /**< start points of components in sortedconss array */
1835  int* nsortedvars, /**< pointer to store the number of variables belonging to any component */
1836  int* nsortedconss, /**< pointer to store the number of (checked) constraints in components */
1837  int* ncomponents, /**< pointer to store the number of components */
1838  int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1839  int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1840 
1841  )
1842 {
1843  SCIP_CONS** tmpconss;
1844  SCIP_VAR** vars;
1845  SCIP_Bool success;
1846  int ntmpconss;
1847  int nvars;
1848  int c;
1849 
1850  assert(scip != NULL);
1851  assert(conshdlrdata != NULL);
1852  assert(sortedvars != NULL);
1853  assert(sortedconss != NULL);
1854  assert(compstartsvars != NULL);
1855  assert(compstartsconss != NULL);
1856  assert(nsortedvars != NULL);
1857  assert(nsortedconss != NULL);
1858  assert(ncomponents != NULL);
1859  assert(ncompsminsize != NULL);
1860  assert(ncompsmaxsize != NULL);
1861 
1862  vars = SCIPgetVars(scip);
1863  nvars = SCIPgetNVars(scip);
1864 
1865  if( fixedvarsobjsum != NULL )
1866  *fixedvarsobjsum = 0.0;
1867 
1868  *ncomponents = 0;
1869  *ncompsminsize = 0;
1870  *ncompsmaxsize = 0;
1871 
1872  /* collect checked constraints for component detection */
1873  ntmpconss = SCIPgetNConss(scip);
1874  tmpconss = SCIPgetConss(scip);
1875  (*nsortedconss) = 0;
1876  for( c = 0; c < ntmpconss; c++ )
1877  {
1878  sortedconss[(*nsortedconss)] = tmpconss[c];
1879  (*nsortedconss)++;
1880  }
1881 
1882  if( nvars > 1 && *nsortedconss > 1 )
1883  {
1884  int* unfixedvarpos;
1885  int* firstvaridxpercons;
1886  int* varlocks;
1887  int nunfixedvars = 0;
1888  int v;
1889 
1890  /* arrays for storing the first variable in each constraint (for later component assignment), the number of
1891  * variable locks, and the positions in the sortedvars array for all unfixed variables
1892  */
1893  SCIP_CALL( SCIPallocBufferArray(scip, &firstvaridxpercons, *nsortedconss) );
1894  SCIP_CALL( SCIPallocBufferArray(scip, &varlocks, nvars) );
1895  SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvarpos, nvars) );
1896 
1897  /* count number of varlocks for each variable (up + down locks) and multiply it by 2;
1898  * that value is used as an estimate of the number of arcs incident to the variable's node in the digraph
1899  * to be safe, we double this value
1900  */
1901  for( v = 0; v < nvars; ++v )
1902  {
1903  /* variable is not fixed or we do not want to disregard fixed variables */
1904  if( (fixedvarsobjsum == NULL) || SCIPisLT(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1905  {
1906  assert(nunfixedvars <= v);
1907  sortedvars[nunfixedvars] = vars[v];
1908  varlocks[nunfixedvars] = 4 * (SCIPvarGetNLocksDown(vars[v]) + SCIPvarGetNLocksUp(vars[v]));
1909  unfixedvarpos[v] = nunfixedvars;
1910  ++nunfixedvars;
1911  }
1912  /* variable is fixed; update the objective sum of all fixed variables */
1913  else
1914  {
1915  unfixedvarpos[v] = -1;
1916  (*fixedvarsobjsum) += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
1917  }
1918  }
1919  *nsortedvars = nunfixedvars;
1920 
1921  if( nunfixedvars > 0 )
1922  {
1923  SCIP_DIGRAPH* digraph;
1924 
1925  /* create and fill directed graph */
1926  SCIP_CALL( SCIPcreateDigraph(scip, &digraph, nunfixedvars) );
1927  SCIP_CALL( SCIPdigraphSetSizes(digraph, varlocks) );
1928  SCIP_CALL( fillDigraph(scip, digraph, sortedconss, *nsortedconss, unfixedvarpos, nunfixedvars, firstvaridxpercons, &success) );
1929 
1930  if( success )
1931  {
1932  int* varcomponent;
1933  int* conscomponent;
1934 
1935  SCIP_CALL( SCIPallocBufferArray(scip, &varcomponent, nunfixedvars) );
1936  SCIP_CALL( SCIPallocBufferArray(scip, &conscomponent, MAX(nunfixedvars,*nsortedconss)) );
1937 
1938  /* compute independent components */
1939  SCIP_CALL( SCIPdigraphComputeUndirectedComponents(digraph, 1, varcomponent, ncomponents) );
1940 
1941  if( *ncomponents > 1 )
1942  {
1943  int nconss = *nsortedconss;
1944  int i;
1945 
1946  nvars = *nsortedvars;
1947 
1949  "cons components found %d undirected components at node %lld, depth %d (%d)\n",
1950  *ncomponents, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
1951 
1952  /* sort components by size and sort variables and constraints by component number */
1953  SCIP_CALL( sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars,
1954  firstvaridxpercons, ncompsminsize, ncompsmaxsize) );
1955 
1956  /* determine start indices of components in sortedvars and sortedconss array */
1957  i = 0;
1958 
1959  while( i < nconss && conscomponent[i] == -1 )
1960  ++i;
1961 
1962  for( c = 0; c < *ncomponents + 1; ++c )
1963  {
1964  assert(i == nconss || conscomponent[i] >= c);
1965 
1966  compstartsconss[c] = i;
1967 
1968  while( i < nconss && conscomponent[i] == c )
1969  ++i;
1970  }
1971 
1972  for( c = 0, i = 0; c < *ncomponents + 1; ++c )
1973  {
1974  assert(i == nvars || varcomponent[i] >= c);
1975 
1976  compstartsvars[c] = i;
1977 
1978  while( i < nvars && varcomponent[i] == c )
1979  ++i;
1980  }
1981 
1982 #ifndef NDEBUG
1983  for( c = 0; c < *ncomponents; ++c )
1984  {
1985  for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i )
1986  assert(conscomponent[i] == c);
1987  for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i )
1988  assert(varcomponent[i] == c);
1989  }
1990 #endif
1991  }
1992 
1993  SCIPfreeBufferArray(scip, &conscomponent);
1994  SCIPfreeBufferArray(scip, &varcomponent);
1995  }
1996 
1997  SCIPdigraphFree(&digraph);
1998  }
1999 
2000  SCIPfreeBufferArray(scip, &unfixedvarpos);
2001  SCIPfreeBufferArray(scip, &varlocks);
2002  SCIPfreeBufferArray(scip, &firstvaridxpercons);
2003  }
2004 
2005  return SCIP_OKAY;
2006 }
2007 
2008 
2009 /*
2010  * Callback methods of constraint handler
2011  */
2012 
2013 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2014 static
2015 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents)
2016 { /*lint --e{715}*/
2017  assert(scip != NULL);
2018  assert(conshdlr != NULL);
2019  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2020 
2021  /* call inclusion method of constraint handler */
2023 
2024  *valid = TRUE;
2025 
2026  return SCIP_OKAY;
2027 }
2028 
2029 /** destructor of constraint handler to free user data (called when SCIP is exiting) */
2030 static
2031 SCIP_DECL_CONSFREE(conshdlrFreeComponents)
2032 { /*lint --e{715}*/
2033  SCIP_CONSHDLRDATA* conshdlrdata;
2034 
2035  /* free constraint handler data */
2036  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2037  assert(conshdlrdata != NULL);
2038 
2039  SCIPfreeBlockMemory(scip, &conshdlrdata);
2040  SCIPconshdlrSetData(conshdlr, NULL);
2041 
2042  return SCIP_OKAY;
2043 }
2044 
2045 /** domain propagation method of constraint handler */
2046 static
2047 SCIP_DECL_CONSPROP(consPropComponents)
2048 { /*lint --e{715}*/
2049  PROBLEM* problem;
2050  SCIP_CONSHDLRDATA* conshdlrdata;
2051  SCIP_Longint nodelimit;
2052 
2053  assert(conshdlr != NULL);
2054  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2055  assert(result != NULL);
2056  assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2057  assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2058 
2059  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2060  assert(conshdlrdata != NULL);
2061 
2062  *result = SCIP_DIDNOTRUN;
2063 
2064  /* do not try to detect independent components if the depth is too high */
2065  if( SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth
2066  && SCIPconshdlrGetNActiveConss(conshdlr) == 0 )
2067  return SCIP_OKAY;
2068 
2069  /* don't run in probing or in repropagation */
2070  if( SCIPinProbing(scip) || SCIPinRepropagation(scip) )
2071  return SCIP_OKAY;
2072 
2073  /* do not run, if not all variables are explicitly known */
2074  if( SCIPgetNActivePricers(scip) > 0 )
2075  return SCIP_OKAY;
2076 
2077  /* we do not want to run, if there are no variables left */
2078  if( SCIPgetNVars(scip) == 0 )
2079  return SCIP_OKAY;
2080 
2081  /* check for a reached timelimit */
2082  if( SCIPisStopped(scip) )
2083  return SCIP_OKAY;
2084 
2085  /* the components constraint handler does kind of dual reductions */
2086  if( !SCIPallowDualReds(scip) || !SCIPallowObjProp(scip) )
2087  return SCIP_OKAY;
2088 
2089  problem = NULL;
2090  *result = SCIP_DIDNOTFIND;
2091 
2092  /* the current node already has a components constraint storing a problem split into individual components */
2093  if( SCIPconshdlrGetNActiveConss(conshdlr) >= 1 )
2094  {
2095  assert(SCIPconshdlrGetNActiveConss(conshdlr) == 1);
2096 
2097  problem = (PROBLEM*)SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]);
2098  }
2099  /* no components constraint at the current node, search for components */
2100  else
2101  {
2103  SCIP_VAR** sortedvars;
2104  SCIP_CONS** sortedconss;
2105  int* compstartsvars;
2106  int* compstartsconss;
2107  int nsortedvars;
2108  int nsortedconss;
2109  int ncomponents;
2110  int ncompsminsize;
2111  int ncompsmaxsize;
2112 
2113  assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2114 
2115  /* allocate memory for sorted components */
2116  SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) );
2117  SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) );
2118  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) );
2119  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) );
2120 
2121  /* search for components */
2122  SCIP_CALL( findComponents(scip, conshdlrdata, &fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2123  compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2124 
2125  if( ncompsminsize > 1 )
2126  {
2127  SCIP_CONS* cons;
2128 
2129  SCIPdebugMsg(scip, "found %d components (%d fulfulling the minsize requirement) at node %lld at depth %d (%d)\n",
2130  ncomponents, ncompsminsize, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip),
2131  SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2132 
2133  /* if there are components with size smaller than the limit, we merge them with the smallest component */
2134  if( ncomponents > ncompsminsize )
2135  {
2136  int minsize;
2137  int size;
2138  int c;
2139  int m = 0;
2140 
2141  /* compute minimum size of components to solve individually */
2142  minsize = getMinsize(scip, conshdlrdata);
2143 
2144  for( c = 0; c < ncomponents; ++c )
2145  {
2146  size = compstartsvars[c+1] - compstartsvars[c];
2147 
2148  if( size >= minsize )
2149  {
2150  ++m;
2151  compstartsvars[m] = compstartsvars[c+1];
2152  compstartsconss[m] = compstartsconss[c+1];
2153  }
2154  /* the last component is too small */
2155  else if( c == ncomponents - 1 )
2156  {
2157  assert(m == ncompsminsize);
2158  compstartsvars[m] = compstartsvars[c+1];
2159  compstartsconss[m] = compstartsconss[c+1];
2160  }
2161  }
2162  assert(m == ncompsminsize);
2163  assert(compstartsvars[m] == nsortedvars);
2164  assert(compstartsconss[m] == nsortedconss);
2165 
2166  ncomponents = m;
2167  }
2168 
2169  SCIP_CALL( createAndSplitProblem(scip, conshdlrdata, fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2170  compstartsconss, ncomponents, &problem) );
2171 
2172  /* if the problem is not NULL, copying worked fine */
2173  if( problem != NULL )
2174  {
2175  SCIP_CALL( createConsComponents(scip, &cons, problem->name, problem) );
2176  SCIP_CALL( SCIPaddConsNode(scip, SCIPgetCurrentNode(scip), cons, NULL) );
2177  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2178  }
2179  }
2180 
2181  SCIPfreeBufferArray(scip, &compstartsconss);
2182  SCIPfreeBufferArray(scip, &compstartsvars);
2183  SCIPfreeBufferArray(scip, &sortedconss);
2184  SCIPfreeBufferArray(scip, &sortedvars);
2185  }
2186 
2187  /* (continue to) solve the problem
2188  *
2189  * If the problem was not solved to optimality yet, the result code is set to SCIP_DELAYNODE, so that after the
2190  * propagation is finished, the node is put back into the queue of open nodes and solving the components of the
2191  * problem will be continued when the node is focused and propagated the next time.
2192  * However, if we are at the root node, we continue solving the problem until it is solved or some limit is reached
2193  * since there are no other nodes to process and we want to avoid calling other propagation methods or heuristics
2194  * again and again
2195  */
2196  SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) );
2197  if( nodelimit == -1 )
2198  nodelimit = SCIP_LONGINT_MAX;
2199 
2200  do
2201  {
2202  if( problem != NULL )
2203  {
2204  SCIP_CALL( solveProblem(problem, result) );
2205  }
2206  } while( *result == SCIP_DELAYNODE && SCIPgetDepth(scip) == 0 && !SCIPisStopped(scip) && SCIPgetNNodes(scip) < nodelimit);
2207 
2208  return SCIP_OKAY;
2209 }
2210 
2211 /** presolving method of constraint handler */
2212 static
2213 SCIP_DECL_CONSPRESOL(consPresolComponents)
2214 { /*lint --e{715}*/
2215  SCIP_CONSHDLRDATA* conshdlrdata;
2216  SCIP_VAR** sortedvars;
2217  SCIP_CONS** sortedconss;
2218  int* compstartsvars;
2219  int* compstartsconss;
2220  int nsortedvars;
2221  int nsortedconss;
2222  int ncomponents;
2223  int ncompsminsize;
2224  int ncompsmaxsize;
2225  int nvars;
2226 
2227  assert(conshdlr != NULL);
2228  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2229  assert(result != NULL);
2230  assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2231  assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2232 
2233  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2234  assert(conshdlrdata != NULL);
2235 
2236  *result = SCIP_DIDNOTRUN;
2237 
2238  if( SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING || SCIPinProbing(scip) )
2239  return SCIP_OKAY;
2240 
2241  /* do not run, if not all variables are explicitly known */
2242  if( SCIPgetNActivePricers(scip) > 0 )
2243  return SCIP_OKAY;
2244 
2245  nvars = SCIPgetNVars(scip);
2246 
2247  /* we do not want to run, if there are no variables left */
2248  if( nvars == 0 )
2249  return SCIP_OKAY;
2250 
2251  /* only call the components presolving, if presolving would be stopped otherwise */
2252  if( !SCIPisPresolveFinished(scip) )
2253  return SCIP_OKAY;
2254 
2255  /* the components constraint handler does kind of dual reductions */
2256  if( !SCIPallowDualReds(scip) || !SCIPallowObjProp(scip) )
2257  return SCIP_OKAY;
2258 
2259  /* check for a reached timelimit */
2260  if( SCIPisStopped(scip) )
2261  return SCIP_OKAY;
2262 
2263  *result = SCIP_DIDNOTFIND;
2264 
2265  assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2266 
2267  /* allocate memory for sorted components */
2268  SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) );
2269  SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) );
2270  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) );
2271  SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) );
2272 
2273  /* search for components */
2274  SCIP_CALL( findComponents(scip, conshdlrdata, NULL, sortedvars, sortedconss, compstartsvars,
2275  compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2276 
2277  if( ncompsmaxsize > 0 )
2278  {
2279  char name[SCIP_MAXSTRLEN];
2280  SCIP* subscip;
2281  SCIP_HASHMAP* consmap;
2282  SCIP_HASHMAP* varmap;
2283  SCIP_VAR** compvars;
2284  SCIP_VAR** subvars;
2285  SCIP_CONS** compconss;
2286  SCIP_Bool success;
2287  SCIP_Bool solved;
2288  int nsolved = 0;
2289  int ncompvars;
2290  int ncompconss;
2291  int comp;
2292 
2293  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",
2294  ncomponents, ncompsmaxsize, SCIPgetNVars(scip), SCIPgetNBinVars(scip), SCIPgetNIntVars(scip), SCIPgetNContVars(scip) + SCIPgetNImplVars(scip), SCIPgetNConss(scip));
2295 
2296  /* build subscip */
2297  SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2298 
2299  if( subscip == NULL )
2300  goto TERMINATE;
2301 
2302  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/usesmalltables", TRUE) );
2303  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/" CONSHDLR_NAME "/propfreq", -1) );
2304 
2305  /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
2306  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), nsortedconss) );
2307 
2308  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nsortedvars) );
2309 
2310  /* loop over all components */
2311  for( comp = 0; comp < ncompsmaxsize && !SCIPisStopped(scip); comp++ )
2312  {
2313 #ifdef WITH_DEBUG_SOLUTION
2314  if( SCIPgetStage(subscip) > SCIP_STAGE_INIT )
2315  {
2316  SCIP_CALL( SCIPfree(&subscip) );
2317  SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2318  }
2319 #endif
2320  /* get component variables */
2321  compvars = &(sortedvars[compstartsvars[comp]]);
2322  ncompvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
2323 
2324  /* get component constraints */
2325  compconss = &(sortedconss[compstartsconss[comp]]);
2326  ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
2327 
2328  /* if we have an unlocked variable, let duality fixing do the job! */
2329  if( ncompconss == 0 )
2330  {
2331  assert(ncompvars == 1);
2332  continue;
2333  }
2334 
2335  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), ncompvars) );
2336 #ifdef DETAILED_OUTPUT
2337  {
2338  int nbinvars = 0;
2339  int nintvars = 0;
2340  int ncontvars = 0;
2341  int i;
2342 
2343  for( i = 0; i < ncompvars; ++i )
2344  {
2345  if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY )
2346  ++nbinvars;
2347  else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER )
2348  ++nintvars;
2349  else
2350  ++ncontvars;
2351  }
2352  SCIPdebugMsg(scip, "solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n",
2353  comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss);
2354  }
2355 #endif
2356 #ifndef NDEBUG
2357  {
2358  int i;
2359  for( i = 0; i < ncompvars; ++i )
2360  assert(SCIPvarIsActive(compvars[i]));
2361  }
2362 #endif
2363 
2364  /* get name of the original problem and add "comp_nr" */
2365  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), comp);
2366 
2367  SCIP_CALL( copyToSubscip(scip, subscip, name, compvars, subvars,
2368  compconss, varmap, consmap, ncompvars, ncompconss, &success) );
2369 
2370  if( !success )
2371  {
2372  SCIPhashmapFree(&varmap);
2373  continue;
2374  }
2375 
2376  /* set up debug solution */
2377 #ifdef WITH_DEBUG_SOLUTION
2378  {
2379  SCIP_SOL* debugsol;
2380  SCIP_Real val;
2381  int i;
2382 
2383  SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
2384 
2385  /* set solution values in the debug solution if it is available */
2386  if( debugsol != NULL )
2387  {
2388  SCIPdebugSolEnable(subscip);
2389 
2390  for( i = 0; i < ncompvars; ++i )
2391  {
2392  SCIP_CALL( SCIPdebugGetSolVal(scip, compvars[i], &val) );
2393  SCIP_CALL( SCIPdebugAddSolVal(subscip, subvars[i], val) );
2394  }
2395  }
2396  }
2397 #endif
2398 
2399  /* solve the subproblem and evaluate the result, i.e. apply fixings of variables and remove constraints */
2400  SCIP_CALL( solveAndEvalSubscip(scip, conshdlrdata, subscip, compvars, subvars, compconss,
2401  ncompvars, ncompconss, ndelconss, nfixedvars, nchgbds, result, &solved) );
2402 
2403  /* free variable hash map */
2404  SCIPhashmapFree(&varmap);
2405 
2406  if( solved )
2407  ++nsolved;
2408 
2409  /* if the component is unbounded or infeasible, this holds for the complete problem as well */
2410  if( *result == SCIP_UNBOUNDED || *result == SCIP_CUTOFF )
2411  break;
2412  /* if there is only one component left, let's solve this in the main SCIP */
2413  else if( nsolved == ncomponents - 1 )
2414  break;
2415  }
2416 
2417  SCIPfreeBufferArray(scip, &subvars);
2418  SCIPhashmapFree(&consmap);
2419 
2420  SCIP_CALL( SCIPfree(&subscip) );
2421  }
2422 
2423  TERMINATE:
2424  SCIPfreeBufferArray(scip, &compstartsconss);
2425  SCIPfreeBufferArray(scip, &compstartsvars);
2426  SCIPfreeBufferArray(scip, &sortedconss);
2427  SCIPfreeBufferArray(scip, &sortedvars);
2428 
2429  return SCIP_OKAY;
2430 }
2431 
2432 /** frees specific constraint data */
2433 static
2434 SCIP_DECL_CONSDELETE(consDeleteComponents)
2435 { /*lint --e{715}*/
2436  PROBLEM* problem;
2437 
2438  assert(conshdlr != NULL);
2439  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2440  assert(consdata != NULL);
2441  assert(*consdata != NULL);
2442 
2443  problem = (PROBLEM*)(*consdata);
2444 
2445  SCIP_CALL( freeProblem(&problem) );
2446 
2447  *consdata = NULL;
2448 
2449  return SCIP_OKAY;
2450 }
2451 
2452 /** constraint enforcing method of constraint handler for relaxation solutions */
2453 static
2454 SCIP_DECL_CONSENFORELAX(consEnforelaxComponents)
2455 { /*lint --e{715}*/
2456  assert(result != NULL );
2457 
2458  /* no enforcement is performed, but the callback is needed for all constraint handlers with needscons = FALSE */
2459  *result = SCIP_FEASIBLE;
2460 
2461  return SCIP_OKAY;
2462 }
2463 
2464 /** variable rounding lock method of constraint handler */
2465 static
2466 SCIP_DECL_CONSLOCK(consLockComponents)
2467 { /*lint --e{715}*/
2468  return SCIP_OKAY;
2469 }
2470 
2471 #ifndef NDEBUG
2472 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
2473 static
2474 SCIP_DECL_CONSINITSOL(consInitsolComponents)
2475 { /*lint --e{715}*/
2476  assert(nconss == 0);
2477 
2478  return SCIP_OKAY;
2479 }
2480 #endif
2481 
2482 #define consEnfolpComponents NULL
2483 #define consEnfopsComponents NULL
2484 #define consCheckComponents NULL
2486 /**@} */
2487 
2488 /**@name Interface methods
2489  *
2490  * @{
2491  */
2492 
2493 /** creates the components constraint handler and includes it in SCIP */
2495  SCIP* scip /**< SCIP data structure */
2496  )
2497 {
2498  SCIP_CONSHDLRDATA* conshdlrdata;
2499  SCIP_CONSHDLR* conshdlr;
2500 
2501  /* create components propagator data */
2502  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2503  conshdlrdata->subscipdepth = 0;
2504 
2505  /* include constraint handler */
2509  conshdlrdata) );
2510  assert(conshdlr != NULL);
2511 
2512  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropComponents,
2514  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolComponents,
2516 
2517  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, conshdlrFreeComponents) );
2518  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxComponents) );
2519 #ifndef NDEBUG
2520  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolComponents) );
2521 #endif
2522  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyComponents, NULL) );
2523  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteComponents) );
2524 
2525  SCIP_CALL( SCIPaddIntParam(scip,
2526  "constraints/" CONSHDLR_NAME "/maxdepth",
2527  "maximum depth of a node to run components detection (-1: disable component detection during solving)",
2528  &conshdlrdata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2529  SCIP_CALL( SCIPaddIntParam(scip,
2530  "constraints/" CONSHDLR_NAME "/maxintvars",
2531  "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)",
2532  &conshdlrdata->maxintvars, TRUE, DEFAULT_MAXINTVARS, -1, INT_MAX, NULL, NULL) );
2533  SCIP_CALL( SCIPaddIntParam(scip,
2534  "constraints/" CONSHDLR_NAME "/minsize",
2535  "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound",
2536  &conshdlrdata->minsize, TRUE, DEFAULT_MINSIZE, 0, INT_MAX, NULL, NULL) );
2538  "constraints/" CONSHDLR_NAME "/minrelsize",
2539  "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound",
2540  &conshdlrdata->minrelsize, TRUE, DEFAULT_MINRELSIZE, 0.0, 1.0, NULL, NULL) );
2542  "constraints/" CONSHDLR_NAME "/nodelimit",
2543  "maximum number of nodes to be solved in subproblems during presolving",
2544  &conshdlrdata->nodelimit, FALSE, DEFAULT_NODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
2546  "constraints/" CONSHDLR_NAME "/intfactor",
2547  "the weight of an integer variable compared to binary variables",
2548  &conshdlrdata->intfactor, FALSE, DEFAULT_INTFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2550  "constraints/" CONSHDLR_NAME "/feastolfactor",
2551  "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0",
2552  &conshdlrdata->feastolfactor, TRUE, DEFAULT_FEASTOLFACTOR, 0.0, 1000000.0, NULL, NULL) );
2553 
2554 
2555  return SCIP_OKAY;
2556 }
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:39942
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
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:6291
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip.c:41453
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
#define DEFAULT_MAXINTVARS
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22517
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8245
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47305
static SCIP_RETCODE freeProblem(PROBLEM **problem)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
Definition: scip.c:43396
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
static SCIP_DECL_CONSENFORELAX(consEnforelaxComponents)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4489
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
Definition: scip.c:43475
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:6036
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:7417
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12657
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47082
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12246
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
static SCIP_DECL_CONSDELETE(consDeleteComponents)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
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 copytables, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:1568
#define DEFAULT_INTFACTOR
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
Definition: scip.c:45875
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:2793
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:4293
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4192
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:5894
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5718
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
static int getMinsize(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47094
#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:7040
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5132
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
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:22633
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:7612
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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:7625
SCIP_Real lastprimalbound
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip.c:12902
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define DEFAULT_MAXDEPTH
#define SCIP_LONGINT_MAX
Definition: def.h:135
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:748
constraint handler for handling independent components
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
static SCIP_RETCODE freeComponent(COMPONENT *component)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4804
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8255
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
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:4265
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:3501
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:45645
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11986
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:27578
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip.c:48562
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:38109
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
Definition: sol.c:2485
#define consEnfopsComponents
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
static SCIP_DECL_CONSLOCK(consLockComponents)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7340
SCIP_Bool solved
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip.c:6157
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
#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:1054
SCIP_Real lastdualbound
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:16109
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:6060
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip.c:8225
#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:4401
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip.c:29170
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12585
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents)
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:43250
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4630
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:928
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip.c:41031
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8205
#define CONSHDLR_MAXPREROUNDS
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_STATUS laststatus
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:6085
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4133
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2548
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:39035
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE componentSetupWorkingSol(COMPONENT *component, SCIP_HASHMAP *varmap)
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47331
struct Component COMPONENT
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
static SCIP_DECL_SORTPTRCOMP(componentSort)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7154
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:262
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip.c:4470
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:29126
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:2533
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:13140
static SCIP_DECL_CONSPRESOL(consPresolComponents)
SCIP_VAR ** vars
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38765
static SCIP_RETCODE solveComponent(COMPONENT *component, SCIP_Bool lastcomponent, SCIP_RESULT *result)
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip.c:17246
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:40974
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:11941
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip.h:22565
#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:43039
SCIP_Real SCIPgetGap(SCIP *scip)
Definition: scip.c:43530
static SCIP_RETCODE initComponent(PROBLEM *problem)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2589
struct Problem PROBLEM
#define SCIPdebugSolIsValidInSubtree(scip, isvalidinsubtree)
Definition: debug.h:263
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:8006
methods for debugging
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
#define CONSHDLR_PROPFREQ
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38529
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8185
static SCIP_DECL_CONSPROP(consPropComponents)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8155
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39777
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip.h:22569
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25569
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38988
SCIP_RETCODE SCIPfixParam(SCIP *scip, const char *name)
Definition: scip.c:4549
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
Definition: scip.c:13513
SCIP_RETCODE SCIPaddSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *stored)
Definition: scip.c:40494
SCIP_RETCODE SCIPcopyProb(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, const char *name)
Definition: scip.c:1739
SCIP_VAR ** fixedvars
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39876
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:46768
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:1920
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8016
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:12856
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:27755
SCIP_SOL * workingsol
SCIP_Real fixedvarsobjsum
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25879
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:6253
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:39120
static SCIP_DECL_CONSINITSOL(consInitsolComponents)
#define DEFAULT_MINRELSIZE
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:46794
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
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:149
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8235
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
static SCIP_RETCODE solveProblem(PROBLEM *problem, SCIP_RESULT *result)
SCIP * subscip
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8175
#define DEFAULT_NODELIMIT
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8165
#define SCIP_Longint
Definition: def.h:134
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16959
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:261
#define CONSHDLR_DESC
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13929
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
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:17342
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:17318
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47204
#define CONSHDLR_PROP_TIMING
void SCIPaddNNodes(SCIP *scip, SCIP_Longint nnodes)
Definition: scip.c:42098
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7064
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
#define SCIPdebugSolEnable(scip)
Definition: debug.h:264
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition: scip.c:19341
#define consEnfolpComponents
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP **subscip)
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2579
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:4321
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4746
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip.c:25889
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:780
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
void SCIPvarMarkDeleteGlobalStructures(SCIP_VAR *var)
Definition: var.c:16919
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5994