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