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