SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
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"
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"
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) */
96typedef struct Problem PROBLEM;
97
98/** data related to one component */
99typedef 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 */
123
124/** data related to one problem
125 * (corresponding to one node in the branch-and-bound tree and consisting of multiple components)
126 */
127struct 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 */
145struct 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 */
164static
166{
167 SCIP* scip;
170 SCIP_Real gap1;
171 SCIP_Real gap2;
172
173 assert(elem1 != NULL);
174 assert(elem2 != NULL);
175
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 */
210static
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 */
227static
229 PROBLEM* problem /**< subproblem structure */
230 )
231{
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 */
269static
271 COMPONENT* component /**< pointer to component structure */
272 )
273{
274 PROBLEM* problem;
275 SCIP* scip;
276
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 {
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 */
317static
319 COMPONENT* component, /**< component structure */
320 SCIP_HASHMAP* varmap /**< variable hashmap */
321 )
322{
323 SCIP* subscip;
324
326
327 subscip = component->subscip;
328 assert(subscip != NULL);
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;
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
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 {
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 */
373
374 /* variable is globally fixed in sub-SCIP, so it was locally fixed in the main-SCIP */
376 {
378
380 component->fixedvars[idx] = sourcevars[v];
381 component->fixedsubvars[idx] = subvar;
382 ++idx;
383
385 }
386 /* inactive variable */
387 else
388 {
390 }
391 }
392 else
393 {
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
419
420 if( isvalid )
421 {
422 SCIP_Real val;
423 int i;
424
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 */
451static
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 */
469#else
472#endif
473
474 /* the plugins were successfully copied */
475 if( success )
476 {
479#ifdef WITH_DEBUG_SOLUTION
480 SCIP_Bool isvalid = FALSE;
481#endif
482
483 /* copy parameter settings */
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 SCIP_CALL( SCIPresetParam(*subscip, "limits/objectivestop") );
498
499 /* reduce the effort spent for hash tables; however, if the debug solution is enabled and valid in this subtree,
500 * hash tables are needed for installing the debug solution
501 */
502#ifdef WITH_DEBUG_SOLUTION
505#endif
506 {
507 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/usevartable", FALSE) );
508 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/useconstable", FALSE) );
509 }
510
511 /* disable presolving */
513
514 /* disable component presolving and fix the parameter */
515 SCIP_CALL( SCIPsetIntParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds", 0) );
516 SCIP_CALL( SCIPfixParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds") );
517
518 /* find the components constraint handler in the sub-SCIP and inform it about the actual depth in the tree */
521
524 newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth + SCIPgetDepth(scip);
525
526 /* disable output, unless in extended debug mode */
527#ifndef SCIP_MORE_DEBUG
528 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
529#endif
530 }
531 else
532 {
533 SCIP_CALL( SCIPfree(subscip) );
534 *subscip = NULL;
535 }
536
537 return SCIP_OKAY;
538}
539
540/** copies the given variables and constraints to the given sub-SCIP */
541static
543 SCIP* scip, /**< source SCIP */
544 SCIP* subscip, /**< target SCIP */
545 const char* name, /**< name for copied problem */
546 SCIP_VAR** vars, /**< array of variables to copy */
547 SCIP_VAR** subvars, /**< array to fill with copied vars */
548 SCIP_CONS** conss, /**< constraint to copy */
549 SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */
550 SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */
551 int nvars, /**< number of variables to copy */
552 int nconss, /**< number of constraints to copy */
553 SCIP_Bool* success /**< pointer to store whether copying was successful */
554 )
555{
557 int i;
558
559 assert(scip != NULL);
560 assert(subscip != NULL);
561 assert(vars != NULL);
562 assert(subvars != NULL);
563 assert(conss != NULL);
564 assert(varmap != NULL);
565 assert(consmap != NULL);
566 assert(success != NULL);
567
568 *success = TRUE;
569
570 /* create problem in sub-SCIP */
571 SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
572
573 /* copy variables */
574 for( i = 0; i < nvars; ++i )
575 {
576 SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &subvars[i], varmap, consmap, FALSE, success) );
577
578 /* abort if variable was not successfully copied */
579 if( !(*success) )
580 return SCIP_OKAY;
581 }
582
583 /* copy constraints */
584 for( i = 0; i < nconss; ++i )
585 {
586 assert(!SCIPconsIsModifiable(conss[i]));
587
588 /* copy the constraint */
589 SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
593
594 /* abort if constraint was not successfully copied */
595 if( !(*success) )
596 return SCIP_OKAY;
597
598 SCIP_CALL( SCIPaddCons(subscip, newcons) );
599 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
600 }
601
602 return SCIP_OKAY;
603}
604
605/** create the sub-SCIP for a given component */
606static
608 COMPONENT* component, /**< component structure */
609 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
610 SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */
611 SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */
612 SCIP_CONS** conss, /**< constraints contained in this component */
613 int nconss, /**< number of constraints contained in this component */
614 SCIP_Bool* success /**< pointer to store whether the copying process was successful */
615 )
616{
617 char name[SCIP_MAXSTRLEN];
618 PROBLEM* problem;
619 SCIP* scip;
620 int minsize;
621
623 assert(consmap != NULL);
624 assert(conss != NULL);
625 assert(success != NULL);
626 assert(component->nvars > 0);
627
628 problem = component->problem;
629 assert(problem != NULL);
630
631 scip = problem->scip;
632 assert(scip != NULL);
633
634 (*success) = TRUE;
635
636 SCIP_CALL( createSubscip(scip, conshdlrdata, &component->subscip) );
637
638 if( component->subscip != NULL )
639 {
640 /* get minimum size of components to solve individually and set the parameter in the sub-SCIP */
641 minsize = getMinsize(scip, conshdlrdata);
642
643 SCIP_CALL( SCIPsetIntParam(component->subscip, "constraints/" CONSHDLR_NAME "/minsize", minsize) );
644
645 /* get name of the original problem and add "comp_nr" */
646 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, component->number);
647
648 SCIP_CALL( copyToSubscip(scip, component->subscip, name, component->vars, component->subvars,
649 conss, varmap, consmap, component->nvars, nconss, success) );
650
651 if( !(*success) )
652 {
653 SCIP_CALL( SCIPfree(&component->subscip) );
654 component->subscip = NULL;
655 }
656 }
657 else
658 (*success) = FALSE;
659
660 return SCIP_OKAY;
661}
662
663/** solve a given sub-SCIP up to the given limits */
664static
666 SCIP* scip, /**< main SCIP */
667 SCIP* subscip, /**< sub-SCIP to solve */
668 SCIP_Longint nodelimit, /**< node limit */
669 SCIP_Real gaplimit /**< gap limit */
670 )
671{
672 SCIP_Real timelimit;
673 SCIP_Real memorylimit;
674 SCIP_Bool avoidmemout;
675
676 assert(scip != NULL);
677 assert(subscip != NULL);
678
679 /* set time limit */
680 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
681 if( !SCIPisInfinity(scip, timelimit) )
682 {
683 timelimit -= SCIPgetSolvingTime(scip);
684 timelimit += SCIPgetSolvingTime(subscip);
685 }
686
687 /* subtract the memory already used by the main SCIP and the estimated memory usage of external software */
688 /* @todo count memory of other components */
689 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
690 if( !SCIPisInfinity(scip, memorylimit) )
691 {
692 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
693 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
694 }
695
696 /* check if mem limit needs to be avoided */
697 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
698
699 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == TRUE)
700 * to create a copy of SCIP, including external memory usage */
701 if( avoidmemout && memorylimit <= 0.0 )
702 {
703 SCIPdebugMsg(scip, "--> not solved (not enough memory left)\n");
704 return SCIP_OKAY;
705 }
706 else if( timelimit <= 0.0 )
707 {
708 SCIPdebugMsg(scip, "--> not solved (not enough time left)\n");
709 return SCIP_OKAY;
710 }
711
712 /* SCIP copy limits will set wrong time limits since it does not take into account time spent already in the
713 * sub-SCIP; nevertheless, we call it to set the memory limit and unset all other limits, if set in the main SCIP
714 */
715 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
716
717 /* set time and memory limit for the subproblem */
718 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
719
720 /* only set soft time limit if it exists */
721 if( SCIPgetParam(scip, "limits/softtime") != NULL )
722 {
723 SCIP_Real softtimelimit;
724
725 /* set soft time limit, if specified in main SCIP and if it exists */
726 SCIP_CALL( SCIPgetRealParam(scip, "limits/softtime", &softtimelimit) );
727 if( softtimelimit > -0.5 )
728 {
729 softtimelimit -= SCIPgetSolvingTime(scip);
730 softtimelimit += SCIPgetSolvingTime(subscip);
731 softtimelimit = MAX(softtimelimit, 0.0);
732 }
733
734 SCIP_CALL( SCIPsetRealParam(subscip, "limits/softtime", softtimelimit) );
735 }
736
737 /* set gap limit */
738 SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", gaplimit) );
739
740 /* set node limit */
741 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
742
743 /* solve the subproblem */
744 SCIP_CALL( SCIPsolve(subscip) );
745
746#ifdef SCIP_MORE_DEBUG
747 SCIP_CALL( SCIPprintBestSol(subscip, NULL, FALSE) );
749#endif
750
751 return SCIP_OKAY;
752}
753
754/** solve a connected component during presolving and evaluate the result */
755static
757 SCIP* scip, /**< SCIP main data structure */
758 SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
759 SCIP* subscip, /**< sub-SCIP to be solved */
760 SCIP_VAR** vars, /**< array of variables copied to this component */
761 SCIP_VAR** subvars, /**< array of sub-SCIP variables corresponding to the vars array */
762 SCIP_CONS** conss, /**< array of constraints copied to this component */
763 int nvars, /**< number of variables copied to this component */
764 int nconss, /**< number of constraints copied to this component */
765 int* ndeletedconss, /**< pointer to store the number of deleted constraints */
766 int* nfixedvars, /**< pointer to store the number of fixed variables */
767 int* ntightenedbounds, /**< pointer to store the number of bound tightenings */
768 SCIP_RESULT* result, /**< pointer to store the result of the component solving */
769 SCIP_Bool* solved /**< pointer to store if the problem was solved to optimality */
770 )
771{
772 int i;
773
774 assert(scip != NULL);
775 assert(conshdlrdata != NULL);
776 assert(subscip != NULL);
777 assert(vars != NULL);
778 assert(conss != NULL);
780 assert(nfixedvars != NULL);
782 assert(result != NULL);
783
784 *solved = FALSE;
785
786 SCIP_CALL( solveSubscip(scip, subscip, conshdlrdata->nodelimit, 0.0) );
787
788 if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
789 {
790 SCIP_SOL* sol;
791 SCIP_VAR* var;
793 SCIP_Real* fixvals;
794 SCIP_Bool feasible;
795 SCIP_Bool infeasible;
796 SCIP_Bool fixed;
797
798 sol = SCIPgetBestSol(subscip);
799
800#ifdef SCIP_DEBUG
802#else
804#endif
805
806 SCIPdebugMsg(scip, "--> solved to optimality: time = %.2f, solution is%s feasible\n", SCIPgetSolvingTime(subscip), feasible ? "" : " not");
807
809
810 if( feasible )
811 {
812 SCIP_Real glb;
813 SCIP_Real gub;
814
815 /* get values of variables in the optimal solution */
816 for( i = 0; i < nvars; ++i )
817 {
818 var = vars[i];
819 subvar = subvars[i];
820
821 /* get global bounds */
824
825 if( subvar != NULL )
826 {
827 /* get solution value from optimal solution of the sub-SCIP */
828 fixvals[i] = SCIPgetSolVal(subscip, sol, subvar);
829
832
833 /* checking a solution is done with a relative tolerance of feasibility epsilon, if we really want to
834 * change the bounds of the variables by fixing them, the old bounds must not be violated by more than
835 * the absolute epsilon; therefore, we change the fixing values, if needed, and mark that the solution
836 * has to be checked again
837 */
838 if( SCIPisGT(scip, fixvals[i], gub) )
839 {
840 SCIPdebugMsg(scip, "variable <%s> fixval: %f violates global upperbound: %f\n",
842 fixvals[i] = gub;
843 feasible = FALSE;
844 }
845 else if( SCIPisLT(scip, fixvals[i], glb) )
846 {
847 SCIPdebugMsg(scip, "variable <%s> fixval: %f violates global lowerbound: %f\n",
849 fixvals[i] = glb;
850 feasible = FALSE;
851 }
854 }
855 else
856 {
857 /* the variable was not copied, so it was cancelled out of constraints during copying;
858 * thus, the variable is not constrained and we fix it to its best bound
859 */
861 fixvals[i] = glb;
863 fixvals[i] = gub;
864 else
865 {
866 fixvals[i] = 0.0;
867 fixvals[i] = MIN(fixvals[i], gub);
868 fixvals[i] = MAX(fixvals[i], glb);
869 }
870 }
871 }
872
873 /* the solution value of at least one variable is feasible with a relative tolerance of feasibility epsilon,
874 * but infeasible with an absolute tolerance of epsilon; try to set the variables to the bounds and check
875 * solution again in the original space (changing the values might now introduce infeasibilities of constraints)
876 */
877 if( !feasible )
878 {
879 SCIP_Real origobj;
880
881 SCIPdebugMsg(scip, "solution violates bounds by more than epsilon, check the corrected solution...\n");
882
883 origobj = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
884
885 SCIP_CALL( SCIPfreeTransform(subscip) );
886
887 SCIP_CALL( SCIPcreateOrigSol(subscip, &sol, NULL) );
888
889 /* set solution values of variables */
890 for( i = 0; i < nvars; ++i )
891 {
892 if( subvars[i] != NULL )
893 {
894 SCIP_CALL( SCIPsetSolVal(subscip, sol, subvars[i], fixvals[i]) );
895 }
896 }
897
898 /* check the solution; integrality and bounds should be fulfilled and do not have to be checked */
900
901#ifndef NDEBUG
902 /* in debug mode, we additionally check integrality and bounds */
903 if( feasible )
904 {
907 }
908#endif
909
910 SCIPdebugMsg(scip, "--> corrected solution is%s feasible\n", feasible ? "" : " not");
911
912 if( !SCIPisFeasEQ(subscip, SCIPsolGetOrigObj(sol), origobj) )
913 {
914 SCIPdebugMsg(scip, "--> corrected solution has a different objective value (old = %.9g, corrected = %.9g)\n",
915 origobj, SCIPsolGetOrigObj(sol));
916
917 feasible = FALSE;
918 }
919
920 SCIP_CALL( SCIPfreeSol(subscip, &sol) );
921 }
922
923 /* if the solution is feasible, fix variables and delete constraints of the component */
924 if( feasible )
925 {
926 /* fix variables */
927 for( i = 0; i < nvars; ++i )
928 {
933
934 SCIP_CALL( SCIPfixVar(scip, vars[i], fixvals[i], &infeasible, &fixed) );
936 assert(!infeasible);
937 assert(fixed);
938 (*nfixedvars)++;
939 }
940
941 /* delete constraints */
942 for( i = 0; i < nconss; ++i )
943 {
944 SCIP_CALL( SCIPdelCons(scip, conss[i]) );
945 (*ndeletedconss)++;
946 }
947
949 *solved = TRUE;
950 }
951 }
952
954 }
955 else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
956 {
958 }
959 else if( SCIPgetStatus(subscip) == SCIP_STATUS_UNBOUNDED || SCIPgetStatus(subscip) == SCIP_STATUS_INFORUNBD )
960 {
961 /* TODO: store unbounded ray in original SCIP data structure */
963 }
964 else
965 {
966 SCIPdebugMsg(scip, "--> solving interrupted (status = %d, time = %.2f)\n",
967 SCIPgetStatus(subscip), SCIPgetSolvingTime(subscip));
968
969 /* transfer global fixings to the original problem; we can only do this, if we did not find a solution in the
970 * subproblem, because otherwise, the primal bound might lead to dual reductions that cannot be transferred to
971 * the original problem without also transferring the possibly suboptimal solution (which is currently not
972 * possible)
973 */
974 if( SCIPgetNSols(subscip) == 0 )
975 {
976 SCIP_Bool infeasible;
977 SCIP_Bool tightened;
978 int ntightened;
979
980 ntightened = 0;
981
982 for( i = 0; i < nvars; ++i )
983 {
984 if( subvars[i] == NULL )
985 continue;
986
988 &infeasible, &tightened) );
989 assert(!infeasible);
990 if( tightened )
991 ntightened++;
992
994 &infeasible, &tightened) );
995 assert(!infeasible);
996 if( tightened )
997 ntightened++;
998 }
999
1001
1002 *ntightenedbounds += ntightened;
1003
1004 SCIPdebugMsg(scip, "--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened);
1005 }
1006 }
1007
1008 return SCIP_OKAY;
1009}
1010
1011/** (continues) solving a connected component */
1012static
1014 COMPONENT* component, /**< component structure */
1015 SCIP_Bool lastcomponent, /**< is this the last component to be solved? */
1016 SCIP_RESULT* result /**< pointer to store the result of the solving process */
1017 )
1018{
1019 PROBLEM* problem;
1020 SCIP* scip;
1021 SCIP* subscip;
1022 SCIP_SOL* bestsol;
1023 SCIP_Longint nodelimit;
1024 SCIP_Longint lastnnodes;
1025 SCIP_Real gaplimit;
1026 SCIP_STATUS status;
1027
1028 assert(component != NULL);
1029
1030 problem = component->problem;
1031 assert(problem != NULL);
1032
1033 scip = problem->scip;
1034 assert(scip != NULL);
1035
1036 subscip = component->subscip;
1037 assert(subscip != NULL);
1038
1040
1041 SCIPdebugMsg(scip, "solve component <%s> (ncalls = %d, absgap = %.9g)\n",
1042 SCIPgetProbName(subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1043
1044 bestsol = SCIPgetBestSol(scip);
1045
1046 /* update best solution of component */
1047 if( bestsol != NULL && SCIPsolGetIndex(bestsol) != component->lastbestsolindex )
1048 {
1049 SCIP_SOL* compsol = component->workingsol;
1050 SCIP_VAR** vars = component->vars;
1051 SCIP_VAR** subvars = component->subvars;
1052 int nvars = component->nvars;
1053 int v;
1054
1055 component->lastbestsolindex = SCIPsolGetIndex(bestsol);
1056
1057 /* set solution values of component variables */
1058 for( v = 0; v < nvars; ++v )
1059 {
1060 if( subvars[v] != NULL )
1061 {
1062 SCIP_CALL( SCIPsetSolVal(subscip, compsol, subvars[v], SCIPgetSolVal(scip, bestsol, vars[v])) );
1063 }
1064 }
1065#ifndef NDEBUG
1066 for( v = 0; v < component->nfixedvars; ++v )
1067 {
1068 if( component->fixedsubvars[v] != NULL )
1069 assert(SCIPisEQ(scip, SCIPgetSolVal(subscip, compsol, component->fixedsubvars[v]),
1070 SCIPvarGetLbGlobal(component->fixedsubvars[v])));
1071 }
1072#endif
1073
1074 if( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM
1075 || SCIPisLT(subscip, SCIPgetSolOrigObj(subscip, compsol), SCIPgetPrimalbound(subscip)) )
1076 {
1077 SCIP_Bool feasible;
1078
1079 SCIPdebugMsg(scip, "checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n",
1080 SCIPgetProbName(subscip), problem->name,
1081 SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM ? SCIPinfinity(subscip) : SCIPgetPrimalbound(subscip),
1082 SCIPgetSolOrigObj(subscip, compsol));
1083
1085 if( feasible )
1086 {
1087 SCIPdebugMsg(scip,"... feasible, adding solution.\n");
1088
1089 SCIP_CALL( SCIPaddSol(subscip, compsol, &feasible) );
1090 }
1091
1092 /* We cannot take the value of compsol as a cutoff bound if it was not feasible; some of the fixed connecting
1093 * variables are different and might not allow for a better solution in this component, but still for far
1094 * better solutions in other components. Therefore, the only cutoffbound we can apply is the cutoffbound
1095 * of the problem reduced by the dual bounds of the other components
1096 */
1097 if( problem->nlowerboundinf == 0 || (problem->nlowerboundinf == 1
1098 && SCIPisInfinity(scip, -component->lastdualbound)) )
1099 {
1100 SCIP_Real newcutoffbound = SCIPgetSolTransObj(scip, bestsol);
1101
1102 assert(problem->nlowerboundinf > 0 || SCIPisGE(scip, newcutoffbound, problem->lowerbound));
1103
1104 newcutoffbound = newcutoffbound - problem->lowerbound + component->fixedvarsobjsum;
1105
1106 if( problem->nlowerboundinf == 0 )
1107 newcutoffbound += component->lastdualbound;
1108
1109 if( SCIPisSumLT(subscip, newcutoffbound, SCIPgetCutoffbound(subscip)) )
1110 {
1111 SCIPdebugMsg(scip, "update cutoff bound to %.9g\n", newcutoffbound);
1112
1114 }
1115 }
1116 }
1117 }
1118
1119 assert(component->laststatus != SCIP_STATUS_OPTIMAL);
1120
1121 SCIPdebugMsg(scip, "solve sub-SCIP for component <%s> (ncalls = %d, absgap = %.9g)\n",
1122 SCIPgetProbName(component->subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1123
1124 if( component->ncalls == 0 )
1125 {
1126 nodelimit = 1LL;
1127 gaplimit = 0.0;
1128
1129 lastnnodes = 0;
1130 }
1131 else
1132 {
1133 SCIP_Longint mainnodelimit;
1134
1136
1137 SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &mainnodelimit) );
1138
1139 nodelimit = 2 * lastnnodes;
1140 nodelimit = MAX(nodelimit, 10LL);
1141
1142 if( mainnodelimit != -1 )
1143 {
1145 nodelimit = MIN(nodelimit, mainnodelimit - lastnnodes);
1146 }
1147
1148 /* set a gap limit of half the current gap (at most 10%) */
1149 if( SCIPgetGap(component->subscip) < 0.2 )
1150 gaplimit = 0.5 * SCIPgetGap(component->subscip);
1151 else
1152 gaplimit = 0.1;
1153
1154 if( lastcomponent )
1155 gaplimit = 0.0;
1156 }
1157
1158 SCIP_CALL( solveSubscip(scip, subscip, nodelimit, gaplimit) );
1159
1161
1163
1164 status = SCIPgetStatus(subscip);
1165
1166 component->laststatus = status;
1167 ++component->ncalls;
1168
1169 SCIPdebugMsg(scip, "--> (status = %d, nodes = %lld, time = %.2f): gap = %.5g%%, absgap = %.9g\n",
1170 status, SCIPgetNNodes(subscip), SCIPgetSolvingTime(subscip), 100.0*SCIPgetGap(subscip),
1171 SCIPgetPrimalbound(subscip) - SCIPgetDualbound(subscip));
1172
1174
1175 switch( status )
1176 {
1178 component->solved = TRUE;
1179 break;
1181 component->solved = TRUE;
1182
1183 /* the problem is really infeasible */
1184 if( SCIPisInfinity(subscip, SCIPgetPrimalbound(subscip)) )
1185 {
1187 }
1188 /* the cutoff bound was reached; no solution better than the cutoff bound exists */
1189 else
1190 {
1192 component->laststatus = SCIP_STATUS_OPTIMAL;
1193 assert(SCIPisLE(subscip, SCIPgetDualbound(subscip), SCIPgetPrimalbound(subscip)));
1194 }
1195 break;
1198 /* TODO: store unbounded ray in original SCIP data structure */
1200 component->solved = TRUE;
1201 break;
1204 break;
1216 default:
1217 break;
1218 }
1219
1220 /* evaluate call */
1221 if( *result == SCIP_SUCCESS )
1222 {
1223 SCIP_SOL* sol = SCIPgetBestSol(subscip);
1224 SCIP_VAR* var;
1226 SCIP_Real newdualbound;
1227 int v;
1228
1229 /* get dual bound as the minimum of SCIP dual bound and sub-problems dual bound */
1230 newdualbound = SCIPgetDualbound(subscip) - component->fixedvarsobjsum;
1231
1232 /* update dual bound of problem */
1233 if( !SCIPisEQ(scip, component->lastdualbound, newdualbound) )
1234 {
1236
1237 /* first finite dual bound: decrease inf counter and add dual bound to problem dualbound */
1238 if( SCIPisInfinity(scip, -component->lastdualbound) )
1239 {
1240 --problem->nlowerboundinf;
1241 problem->lowerbound += newdualbound;
1242 }
1243 /* increase problem dual bound by dual bound delta */
1244 else
1245 {
1246 problem->lowerbound += (newdualbound - component->lastdualbound);
1247 }
1248
1249 /* update problem dual bound if all problem components have a finite dual bound */
1250 if( problem->nlowerboundinf == 0 )
1251 {
1252 SCIPdebugMsg(scip, "component <%s>: dual bound increased from %.9g to %.9g, new dual bound of problem <%s>: %.9g (gap = %.9g, absgap = %.9g)\n",
1253 SCIPgetProbName(subscip), component->lastdualbound, newdualbound, problem->name,
1254 SCIPretransformObj(scip, problem->lowerbound),
1255 problem->nfeascomps == problem->ncomponents ?
1256 (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1257 MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ), SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1258 : SCIPinfinity(scip),
1259 problem->nfeascomps == problem->ncomponents ?
1260 SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1261 SCIP_CALL( SCIPupdateLocalLowerbound(scip, problem->lowerbound) );
1262 }
1263
1264 /* store dual bound of this call */
1265 component->lastdualbound = newdualbound;
1266 }
1267
1268 /* update primal solution of problem */
1269 if( sol != NULL && component->lastsolindex != SCIPsolGetIndex(sol) )
1270 {
1271 component->lastsolindex = SCIPsolGetIndex(sol);
1272
1273 if( SCIPsolGetHeur(sol) != NULL )
1275 else
1276 SCIPsolSetHeur(problem->bestsol, NULL);
1277
1278 /* increase counter for feasible problems if no solution was known before */
1279 if( SCIPisInfinity(scip, component->lastprimalbound) )
1280 ++(problem->nfeascomps);
1281
1282 /* update working best solution in problem */
1283 for( v = 0; v < component->nvars; ++v )
1284 {
1285 var = component->vars[v];
1286 subvar = component->subvars[v];
1287 assert(var != NULL);
1289
1290 if( subvar == NULL )
1291 continue;
1292
1293 SCIP_CALL( SCIPsetSolVal(scip, problem->bestsol, var, SCIPgetSolVal(subscip, sol, subvar)) );
1294 }
1295
1296 /* if we have a feasible solution for each component, add the working solution to the main problem */
1297 if( problem->nfeascomps == problem->ncomponents )
1298 {
1299 SCIP_Bool feasible;
1300#ifdef SCIP_MORE_DEBUG
1301 SCIP_CALL( SCIPcheckSol(scip, problem->bestsol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
1303#endif
1304 SCIP_CALL( SCIPaddSol(scip, problem->bestsol, &feasible) );
1305
1306 SCIPdebugMsg(scip, "component <%s>: primal bound decreased from %.9g to %.9g, new primal bound of problem <%s>: %.9g (gap = %.9g, absgap = %.9g)\n",
1307 SCIPgetProbName(subscip), component->lastprimalbound, SCIPgetPrimalbound(subscip), problem->name,
1308 SCIPgetSolOrigObj(scip, problem->bestsol),
1309 problem->nfeascomps == problem->ncomponents ?
1310 (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1311 MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ),SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1312 : SCIPinfinity(scip),
1313 problem->nfeascomps == problem->ncomponents ?
1314 SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1315 }
1316
1317 /* store primal bound of this call */
1318 component->lastprimalbound = SCIPgetPrimalbound(subscip) - component->fixedvarsobjsum;
1319 }
1320
1321 /* if the component was solved to optimality, we increase the respective counter and free the subscip */
1322 if( component->laststatus == SCIP_STATUS_OPTIMAL || component->laststatus == SCIP_STATUS_INFEASIBLE ||
1323 component->laststatus == SCIP_STATUS_UNBOUNDED || component->laststatus == SCIP_STATUS_INFORUNBD )
1324 {
1325 ++(problem->nsolvedcomps);
1326 component->solved = TRUE;
1327
1328 /* free working solution and component */
1329 SCIP_CALL( SCIPfreeSol(subscip, &component->workingsol) );
1330
1331 SCIP_CALL( SCIPfree(&subscip) );
1332 component->subscip = NULL;
1333 }
1334 }
1335
1336 return SCIP_OKAY;
1337}
1338
1339/** initialize subproblem structure */
1340static
1342 SCIP* scip, /**< SCIP data structure */
1343 PROBLEM** problem, /**< pointer to subproblem structure */
1344 SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1345 int ncomponents /**< number of independent components */
1346 )
1347{
1348 char name[SCIP_MAXSTRLEN];
1349 SCIP_VAR** vars;
1350 int nvars;
1351 int v;
1352
1353 assert(scip != NULL);
1354 assert(problem != NULL);
1355
1358
1359 SCIP_CALL( SCIPallocBlockMemory(scip, problem) );
1360 assert(*problem != NULL);
1361
1362 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->components, ncomponents) );
1363
1364 /* create a priority queue for the components: we need exactly ncomponents slots in the queue so it should never be
1365 * resized
1366 */
1367 SCIP_CALL( SCIPpqueueCreate(&(*problem)->compqueue, ncomponents, 1.2, componentSort, NULL) );
1368
1369 (*problem)->scip = scip;
1370 (*problem)->lowerbound = fixedvarsobjsum;
1371 (*problem)->fixedvarsobjsum = fixedvarsobjsum;
1372 (*problem)->ncomponents = 0;
1373 (*problem)->componentssize = ncomponents;
1374 (*problem)->nlowerboundinf = ncomponents;
1375 (*problem)->nfeascomps = 0;
1376 (*problem)->nsolvedcomps = 0;
1377
1378 if( SCIPgetDepth(scip) == 0 )
1380 else
1382
1383 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name)+1) );
1384
1385 SCIP_CALL( SCIPcreateSol(scip, &(*problem)->bestsol, NULL) );
1386
1387 for( v = 0; v < nvars; v++ )
1388 {
1390 {
1391 SCIP_CALL( SCIPsetSolVal(scip, (*problem)->bestsol, vars[v],
1393 }
1394 }
1395
1396 SCIPdebugMsg(scip, "initialized problem <%s>\n", (*problem)->name);
1397
1398 return SCIP_OKAY;
1399}
1400
1401/** free subproblem structure */
1402static
1404 PROBLEM** problem /**< pointer to problem to free */
1405 )
1406{
1407 SCIP* scip;
1408 int c;
1409
1410 assert(problem != NULL);
1411 assert(*problem != NULL);
1412
1413 scip = (*problem)->scip;
1414 assert(scip != NULL);
1415
1416 /* free best solution */
1417 if( (*problem)->bestsol != NULL )
1418 {
1419 SCIP_CALL( SCIPfreeSol(scip, &(*problem)->bestsol) );
1420 }
1421
1422 /* free all components */
1423 for( c = (*problem)->ncomponents - 1; c >= 0; --c )
1424 {
1425 SCIP_CALL( freeComponent(&(*problem)->components[c]) );
1426 }
1427 if( (*problem)->components != NULL )
1428 {
1429 SCIPfreeBlockMemoryArray(scip, &(*problem)->components, (*problem)->componentssize);
1430 }
1431
1432 /* free priority queue */
1433 SCIPpqueueFree(&(*problem)->compqueue);
1434
1435 /* free problem name */
1436 SCIPfreeMemoryArray(scip, &(*problem)->name);
1437
1438 /* free PROBLEM struct and set the pointer to NULL */
1439 SCIPfreeBlockMemory(scip, problem);
1440 *problem = NULL;
1441
1442 return SCIP_OKAY;
1443}
1444
1445/** creates and captures a components constraint */
1446static
1448 SCIP* scip, /**< SCIP data structure */
1449 SCIP_CONS** cons, /**< pointer to hold the created constraint */
1450 const char* name, /**< name of constraint */
1451 PROBLEM* problem /**< problem to be stored in the constraint */
1452 )
1453{
1454 SCIP_CONSHDLR* conshdlr;
1455
1456 /* find the components constraint handler */
1457 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1458 if( conshdlr == NULL )
1459 {
1460 SCIPerrorMessage("components constraint handler not found\n");
1461 return SCIP_PLUGINNOTFOUND;
1462 }
1463
1464 /* create constraint */
1465 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, (SCIP_CONSDATA*)problem,
1467 TRUE, FALSE, FALSE, FALSE, TRUE) );
1468
1469 return SCIP_OKAY;
1470}
1471
1472
1473/** sort the components by size and sort vars and conss arrays by component numbers */
1474static
1476 SCIP* scip, /**< SCIP data structure */
1477 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1478 SCIP_DIGRAPH* digraph, /**< directed graph */
1479 SCIP_CONS** conss, /**< constraints */
1480 SCIP_VAR** vars, /**< variables */
1481 int* varcomponent, /**< component numbers for the variables */
1482 int* conscomponent, /**< array to store component numbers for the constraints */
1483 int nconss, /**< number of constraints */
1484 int nvars, /**< number of variables */
1485 int* firstvaridxpercons, /**< array with index of first variable in vars array for each constraint */
1486 int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1487 int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1488 )
1489{
1490 SCIP_Real* compsize;
1491 int* permu;
1492 int ncomponents;
1493 int nbinvars;
1494 int nintvars;
1495 int ndiscvars;
1496 int ncontvars;
1497 int minsize;
1498 int v;
1499 int c;
1500
1501 assert(scip != NULL);
1502 assert(conshdlrdata != NULL);
1503 assert(digraph != NULL);
1504 assert(conss != NULL);
1505 assert(vars != NULL);
1507
1508 /* compute minimum size of components to solve individually */
1509 minsize = getMinsize(scip, conshdlrdata);
1510
1511 ncomponents = SCIPdigraphGetNComponents(digraph);
1512 *ncompsminsize = 0;
1513 *ncompsmaxsize = 0;
1514
1515 /* We want to sort the components in increasing complexity (number of discrete variables,
1516 * integer weighted with factor intfactor, continuous used as tie-breaker).
1517 * Therefore, we now get the variables for each component, count the different variable types
1518 * and compute a size as described above. Then, we rename the components
1519 * such that for i < j, component i has no higher complexity than component j.
1520 */
1521 SCIP_CALL( SCIPallocBufferArray(scip, &compsize, ncomponents) );
1522 SCIP_CALL( SCIPallocBufferArray(scip, &permu, ncomponents) );
1523
1524 /* get number of variables in the components */
1525 for( c = 0; c < ncomponents; ++c )
1526 {
1527 int* cvars;
1528 int ncvars;
1529
1531 permu[c] = c;
1532 nbinvars = 0;
1533 nintvars = 0;
1534
1535 for( v = 0; v < ncvars; ++v )
1536 {
1537 /* check whether variable is of binary or integer type */
1538 if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_BINARY )
1539 nbinvars++;
1540 else if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_INTEGER )
1541 nintvars++;
1542 }
1543 ncontvars = ncvars - nintvars - nbinvars;
1544 ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars);
1545 compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/nvars));
1546
1547 /* component fulfills the maxsize requirement */
1548 if( ndiscvars <= conshdlrdata->maxintvars )
1549 ++(*ncompsmaxsize);
1550
1551 /* component fulfills the minsize requirement */
1552 if( ncvars >= minsize )
1553 ++(*ncompsminsize);
1554 }
1555
1556 /* get permutation of component numbers such that the size of the components is increasing */
1557 SCIPsortRealInt(compsize, permu, ncomponents);
1558
1559 /* now, we need the reverse direction, i.e., for each component number, we store its new number
1560 * such that the components are sorted; for this, we abuse the conscomponent array
1561 */
1562 for( c = 0; c < ncomponents; ++c )
1563 conscomponent[permu[c]] = c;
1564
1565 /* for each variable, replace the old component number by the new one */
1566 for( c = 0; c < nvars; ++c )
1568
1571
1572 /* do the mapping from calculated components per variable to corresponding
1573 * constraints and sort the component-arrays for faster finding the
1574 * actual variables and constraints belonging to one component
1575 */
1576 for( c = 0; c < nconss; c++ )
1578
1580 SCIPsortIntPtr(conscomponent, (void**)conss, nconss);
1581
1582 return SCIP_OKAY;
1583}
1584
1585
1586
1587/** create PROBLEM structure for the current node and split it into components */
1588static
1590 SCIP* scip, /**< SCIP data structure */
1591 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1592 SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1593 SCIP_VAR** sortedvars, /**< array of unfixed variables sorted by components */
1594 SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by components */
1595 int* compstartsvars, /**< start points of components in sortedvars array */
1596 int* compstartsconss, /**< start points of components in sortedconss array */
1597 int ncomponents, /**< number of components */
1598 PROBLEM** problem /**< pointer to store problem structure */
1599 )
1600{
1602 SCIP_HASHMAP* consmap;
1603 SCIP_HASHMAP* varmap;
1606 SCIP_Bool success = TRUE;
1607 int nfixedvars = SCIPgetNVars(scip) - compstartsvars[ncomponents];
1608 int ncompconss;
1609 int comp;
1610
1611 /* init subproblem data structure */
1612 SCIP_CALL( initProblem(scip, problem, fixedvarsobjsum, ncomponents) );
1613 assert((*problem)->components != NULL);
1614
1615 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
1616 SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), compstartsconss[ncomponents]) );
1617
1618 /* loop over all components */
1619 for( comp = 0; comp < ncomponents; comp++ )
1620 {
1621 SCIP_CALL( initComponent(*problem) );
1622 assert((*problem)->ncomponents == comp+1);
1623
1624 component = &(*problem)->components[comp];
1625
1626 /* get component variables and store them in component structure */
1627 compvars = &(sortedvars[compstartsvars[comp]]);
1631 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), component->nvars + nfixedvars) );
1632
1633 /* get component constraints */
1636
1637#ifdef DETAILED_OUTPUT
1638 /* print details about the component including its size */
1639 if( component->nvars > 1 && ncompconss > 1 )
1640 {
1641 int nbinvars = 0;
1642 int nintvars = 0;
1643 int ncontvars = 0;
1644 int i;
1645
1646 for( i = 0; i < component->nvars; ++i )
1647 {
1649 ++nbinvars;
1651 ++nintvars;
1652 else
1653 ++ncontvars;
1654 }
1655 SCIPdebugMsg(scip, "component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n",
1656 comp, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth,
1657 component->nvars, nbinvars, nintvars, ncontvars, ncompconss);
1658 }
1659#endif
1660 assert(ncompconss > 0 || component->nvars == 1);
1661
1662 SCIPdebugMsg(scip, "build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n",
1663 component->number, (*problem)->name, component->nvars, ncompconss);
1664
1665#ifndef NDEBUG
1666 {
1667 int i;
1668 for( i = 0; i < component->nvars; ++i )
1670 }
1671#endif
1672
1673 /* build subscip for component */
1674 SCIP_CALL( componentCreateSubscip(component, conshdlrdata, varmap, consmap, compconss, ncompconss, &success) );
1675
1676 if( success )
1677 {
1679
1680 /* add component to the priority queue of the problem structure */
1681 SCIP_CALL( SCIPpqueueInsert((*problem)->compqueue, component) );
1682 }
1683
1684 SCIPhashmapFree(&varmap);
1685
1686 if( !success )
1687 break;
1688 }
1689
1690 SCIPhashmapFree(&consmap);
1691
1692 if( !success )
1693 {
1694 /* free subproblem data structure since not all component could be copied */
1695 SCIP_CALL( freeProblem(problem) );
1696 }
1697
1698 return SCIP_OKAY;
1699}
1700
1701/** continue solving a problem */
1702static
1704 PROBLEM* problem, /**< problem structure */
1705 SCIP_RESULT* result /**< result pointer for the problem solve */
1706 )
1707{
1710
1711 assert(problem != NULL);
1712
1714
1715 component = (COMPONENT*)SCIPpqueueRemove(problem->compqueue);
1716
1717 /* continue solving the component */
1718 SCIP_CALL( solveComponent(component, SCIPpqueueNElems(problem->compqueue) == 0, &subscipresult) );
1719
1720 /* if infeasibility or unboundedness was detected, return this */
1722 {
1724 }
1725 /* the component was not solved to optimality, so we need to re-insert it in the components queue */
1726 else if( !component->solved )
1727 {
1728 SCIP_CALL( SCIPpqueueInsert(problem->compqueue, component) );
1730 }
1731 /* no unsolved components are left, so this problem has be completely evaluated and the node can be pruned */
1732 else if( SCIPpqueueNElems(problem->compqueue) == 0 )
1734 /* there are some unsolved components left, so we delay this node */
1735 else
1737
1738 return SCIP_OKAY;
1739}
1740
1741/*
1742 * Local methods
1743 */
1744
1745/** loop over constraints, get active variables and fill directed graph */
1746static
1748 SCIP* scip, /**< SCIP data structure */
1749 SCIP_DIGRAPH* digraph, /**< directed graph */
1750 SCIP_CONS** conss, /**< constraints */
1751 int nconss, /**< number of constraints */
1752 int* unfixedvarpos, /**< mapping from variable problem index to unfixed var index */
1753 int nunfixedvars, /**< number of unfixed variables */
1754 int* firstvaridxpercons, /**< array to store for each constraint the index in the local vars array
1755 * of the first variable of the constraint */
1756 SCIP_Bool* success /**< flag indicating successful directed graph filling */
1757 )
1758{
1759 SCIP_VAR** consvars;
1760 int requiredsize;
1761 int nconsvars;
1762 int nvars;
1763 int idx1;
1764 int idx2;
1765 int c;
1766 int v;
1767
1768 assert(scip != NULL);
1769 assert(digraph != NULL);
1770 assert(conss != NULL);
1772 assert(success != NULL);
1773
1774 *success = TRUE;
1775
1776 nconsvars = 0;
1777 requiredsize = 0;
1779
1780 /* allocate buffer for storing active variables per constraint; size = nvars ensures that it will be big enough */
1781 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
1782
1783 for( c = 0; c < nconss; ++c )
1784 {
1785 /* check for reached timelimit */
1786 if( (c % 1000 == 0) && SCIPisStopped(scip) )
1787 {
1788 *success = FALSE;
1789 break;
1790 }
1791
1792 /* get number of variables for this constraint */
1793 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nconsvars, success) );
1794
1795 if( !(*success) )
1796 break;
1797
1798 /* reallocate consvars array, if needed */
1799 if( nconsvars > nvars )
1800 {
1801 nvars = nconsvars;
1803 }
1804
1805#ifndef NDEBUG
1806 /* clearing variables array to check for consistency */
1807 if( nconsvars == nvars )
1808 {
1809 BMSclearMemoryArray(consvars, nconsvars);
1810 }
1811 else
1812 {
1813 assert(nconsvars < nvars);
1814 BMSclearMemoryArray(consvars, nconsvars + 1);
1815 }
1816#endif
1817
1818 /* get variables for this constraint */
1819 SCIP_CALL( SCIPgetConsVars(scip, conss[c], consvars, nvars, success) );
1820
1821 if( !(*success) )
1822 {
1823#ifndef NDEBUG
1824 /* it looks strange if returning the number of variables was successful but not returning the variables */
1825 SCIPwarningMessage(scip, "constraint <%s> returned number of variables but returning variables failed\n", SCIPconsGetName(conss[c]));
1826#endif
1827 break;
1828 }
1829
1830#ifndef NDEBUG
1831 /* check if returned variables are consistent with the number of variables that were returned */
1832 for( v = nconsvars - 1; v >= 0; --v )
1833 assert(consvars[v] != NULL);
1834 if( nconsvars < nvars )
1835 assert(consvars[nconsvars] == NULL);
1836#endif
1837
1838 /* transform given variables to active variables */
1839 SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nconsvars, nvars, &requiredsize) );
1841
1842 firstvaridxpercons[c] = -1;
1843
1844 /* store the index of the first unfixed variable and add edges to the directed graph */
1845 if( nconsvars > 0 )
1846 {
1847 v = 0;
1848 idx1 = -1;
1849
1850 /* go through variables until the first unfixed one is reached (which has unfixedvarpos >= 0) */
1851 while( idx1 == -1 && v < nconsvars )
1852 {
1853 idx1 = SCIPvarGetProbindex(consvars[v]);
1854 assert(idx1 >= 0);
1857 ++v;
1858 }
1859
1860 if( idx1 >= 0 )
1861 {
1862 /* save index of the first variable for later component assignment */
1864
1865 /* create sparse directed graph; sparse means to add only those edges necessary for component calculation,
1866 * i.e., add edges from the first variable to all others
1867 */
1868 for(; v < nconsvars; ++v )
1869 {
1870 idx2 = SCIPvarGetProbindex(consvars[v]);
1871 assert(idx2 >= 0);
1874
1875 /* variable is fixed */
1876 if( idx2 < 0 )
1877 continue;
1878
1879 /* we add only one directed edge, because the other direction is automatically added for component computation */
1881 }
1882 }
1883 }
1884 }
1885
1886 SCIPfreeBufferArray(scip, &consvars);
1887
1888 return SCIP_OKAY;
1889}
1890
1891/** search for components in the problem */
1892static
1894 SCIP* scip, /**< SCIP main data structure */
1895 SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
1896 SCIP_Real* fixedvarsobjsum, /**< objective contribution of all locally fixed variables, or NULL if
1897 * fixed variables should not be disregarded */
1898 SCIP_VAR** sortedvars, /**< array to store variables sorted by components, should have enough size
1899 * for all variables */
1900 SCIP_CONS** sortedconss, /**< array to store (checked) constraints sorted by components, should have
1901 * enough size for all constraints */
1902 int* compstartsvars, /**< start points of components in sortedvars array */
1903 int* compstartsconss, /**< start points of components in sortedconss array */
1904 int* nsortedvars, /**< pointer to store the number of variables belonging to any component */
1905 int* nsortedconss, /**< pointer to store the number of (checked) constraints in components */
1906 int* ncomponents, /**< pointer to store the number of components */
1907 int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1908 int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1909
1910 )
1911{
1913 SCIP_VAR** vars;
1914 SCIP_Bool success;
1915 int ntmpconss;
1916 int nvars;
1917 int c;
1918
1919 assert(scip != NULL);
1920 assert(conshdlrdata != NULL);
1921 assert(sortedvars != NULL);
1925 assert(nsortedvars != NULL);
1927 assert(ncomponents != NULL);
1930
1933
1934 if( fixedvarsobjsum != NULL )
1935 *fixedvarsobjsum = 0.0;
1936
1937 *ncomponents = 0;
1938 *ncompsminsize = 0;
1939 *ncompsmaxsize = 0;
1940
1941 /* collect checked constraints for component detection */
1944 (*nsortedconss) = 0;
1945 for( c = 0; c < ntmpconss; c++ )
1946 {
1947 sortedconss[(*nsortedconss)] = tmpconss[c];
1948 (*nsortedconss)++;
1949 }
1950
1951 if( nvars > 1 && *nsortedconss > 1 )
1952 {
1953 int* unfixedvarpos;
1954 int* firstvaridxpercons;
1955 int* varlocks;
1956 int nunfixedvars = 0;
1957 int v;
1958
1959 /* arrays for storing the first variable in each constraint (for later component assignment), the number of
1960 * variable locks, and the positions in the sortedvars array for all unfixed variables
1961 */
1965
1966 /* count number of varlocks for each variable (up + down locks) and multiply it by 2;
1967 * that value is used as an estimate of the number of arcs incident to the variable's node in the digraph
1968 * to be safe, we double this value
1969 */
1970 for( v = 0; v < nvars; ++v )
1971 {
1972 /* variable is not fixed or we do not want to disregard fixed variables */
1973 if( (fixedvarsobjsum == NULL) || SCIPisLT(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1974 {
1975 assert(nunfixedvars <= v);
1976 sortedvars[nunfixedvars] = vars[v];
1980 ++nunfixedvars;
1981 }
1982 /* variable is fixed; update the objective sum of all fixed variables */
1983 else
1984 {
1985 unfixedvarpos[v] = -1;
1986 (*fixedvarsobjsum) += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
1987 }
1988 }
1989 *nsortedvars = nunfixedvars;
1990
1991 if( nunfixedvars > 0 )
1992 {
1994
1995 /* create and fill directed graph */
1999
2000 if( success )
2001 {
2002 int* varcomponent;
2003 int* conscomponent;
2004
2007
2008 /* compute independent components */
2010
2011 if( *ncomponents > 1 )
2012 {
2013 int nconss = *nsortedconss;
2014 int i;
2015
2016 nvars = *nsortedvars;
2017
2019 "cons components found %d undirected components at node %lld, depth %d (%d)\n",
2020 *ncomponents, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2021
2022 /* sort components by size and sort variables and constraints by component number */
2023 SCIP_CALL( sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars,
2025
2026 /* determine start indices of components in sortedvars and sortedconss array */
2027 i = 0;
2028
2029 while( i < nconss && conscomponent[i] == -1 )
2030 ++i;
2031
2032 for( c = 0; c < *ncomponents + 1; ++c )
2033 {
2034 assert(i == nconss || conscomponent[i] >= c);
2035
2036 compstartsconss[c] = i;
2037
2038 while( i < nconss && conscomponent[i] == c )
2039 ++i;
2040 }
2041
2042 for( c = 0, i = 0; c < *ncomponents + 1; ++c )
2043 {
2044 assert(i == nvars || varcomponent[i] >= c);
2045
2046 compstartsvars[c] = i;
2047
2048 while( i < nvars && varcomponent[i] == c )
2049 ++i;
2050 }
2051
2052#ifndef NDEBUG
2053 for( c = 0; c < *ncomponents; ++c )
2054 {
2055 for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i )
2056 assert(conscomponent[i] == c);
2057 for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i )
2058 assert(varcomponent[i] == c);
2059 }
2060#endif
2061 }
2062
2065 }
2066
2068 }
2069
2073 }
2074
2075 return SCIP_OKAY;
2076}
2077
2078
2079/*
2080 * Callback methods of constraint handler
2081 */
2082
2083/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2084static
2086{ /*lint --e{715}*/
2087 assert(scip != NULL);
2088 assert(conshdlr != NULL);
2090
2091 /* call inclusion method of constraint handler */
2093
2094 *valid = TRUE;
2095
2096 return SCIP_OKAY;
2097}
2098
2099/** destructor of constraint handler to free user data (called when SCIP is exiting) */
2100static
2102{ /*lint --e{715}*/
2103 SCIP_CONSHDLRDATA* conshdlrdata;
2104
2105 /* free constraint handler data */
2106 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2107 assert(conshdlrdata != NULL);
2108
2109 SCIPfreeBlockMemory(scip, &conshdlrdata);
2110 SCIPconshdlrSetData(conshdlr, NULL);
2111
2112 return SCIP_OKAY;
2113}
2114
2115/** domain propagation method of constraint handler */
2116static
2118{ /*lint --e{715}*/
2119 PROBLEM* problem;
2120 SCIP_CONSHDLRDATA* conshdlrdata;
2121 SCIP_Longint nodelimit;
2122
2123 assert(conshdlr != NULL);
2125 assert(result != NULL);
2126 assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2127 assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2128
2129 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2130 assert(conshdlrdata != NULL);
2131
2133
2134 /* do not try to detect independent components if the depth is too high */
2135 if( SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth
2136 && SCIPconshdlrGetNActiveConss(conshdlr) == 0 )
2137 return SCIP_OKAY;
2138
2139 /* don't run in probing or in repropagation */
2141 return SCIP_OKAY;
2142
2143 /* do not run, if not all variables are explicitly known */
2144 if( SCIPgetNActivePricers(scip) > 0 )
2145 return SCIP_OKAY;
2146
2147 /* we do not want to run, if there are no variables left */
2148 if( SCIPgetNVars(scip) == 0 )
2149 return SCIP_OKAY;
2150
2151 /* check for a reached timelimit */
2152 if( SCIPisStopped(scip) )
2153 return SCIP_OKAY;
2154
2155 /* the components constraint handler does kind of dual reductions */
2157 return SCIP_OKAY;
2158
2159 problem = NULL;
2161
2162 /* the current node already has a components constraint storing a problem split into individual components */
2163 if( SCIPconshdlrGetNActiveConss(conshdlr) >= 1 )
2164 {
2165 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 1);
2166
2167 problem = (PROBLEM*)SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]);
2168 }
2169 /* no components constraint at the current node, search for components */
2170 else
2171 {
2172 SCIP_Real fixedvarsobjsum;
2173 SCIP_VAR** sortedvars;
2175 int* compstartsvars;
2176 int* compstartsconss;
2177 int nsortedvars;
2178 int nsortedconss;
2179 int ncomponents;
2180 int ncompsminsize;
2181 int ncompsmaxsize;
2182
2183 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2184
2185 /* allocate memory for sorted components */
2190
2191 /* search for components */
2192 SCIP_CALL( findComponents(scip, conshdlrdata, &fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2193 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2194
2195 if( ncompsminsize > 1 )
2196 {
2197 SCIP_CONS* cons;
2198
2199 SCIPdebugMsg(scip, "found %d components (%d fulfilling the minsize requirement) at node %lld at depth %d (%d)\n",
2201 SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2202
2203 /* if there are components with size smaller than the limit, we merge them with the smallest component */
2204 if( ncomponents > ncompsminsize )
2205 {
2206 int minsize;
2207 int size;
2208 int c;
2209 int m = 0;
2210
2211 /* compute minimum size of components to solve individually */
2212 minsize = getMinsize(scip, conshdlrdata);
2213
2214 for( c = 0; c < ncomponents; ++c )
2215 {
2216 size = compstartsvars[c+1] - compstartsvars[c];
2217
2218 if( size >= minsize )
2219 {
2220 ++m;
2223 }
2224 /* the last component is too small */
2225 else if( c == ncomponents - 1 )
2226 {
2227 assert(m == ncompsminsize);
2230 }
2231 }
2232 assert(m == ncompsminsize);
2233 assert(compstartsvars[m] == nsortedvars);
2235
2236 ncomponents = m;
2237 }
2238
2239 SCIP_CALL( createAndSplitProblem(scip, conshdlrdata, fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2240 compstartsconss, ncomponents, &problem) );
2241
2242 /* if the problem is not NULL, copying worked fine */
2243 if( problem != NULL )
2244 {
2245 SCIP_CALL( createConsComponents(scip, &cons, problem->name, problem) );
2247 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2248 }
2249 }
2250
2254 SCIPfreeBufferArray(scip, &sortedvars);
2255 }
2256
2257 /* (continue to) solve the problem
2258 *
2259 * If the problem was not solved to optimality yet, the result code is set to SCIP_DELAYNODE, so that after the
2260 * propagation is finished, the node is put back into the queue of open nodes and solving the components of the
2261 * problem will be continued when the node is focused and propagated the next time.
2262 * However, if we are at the root node, we continue solving the problem until it is solved or some limit is reached
2263 * since there are no other nodes to process and we want to avoid calling other propagation methods or heuristics
2264 * again and again
2265 */
2266 SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) );
2267 if( nodelimit == -1 )
2268 nodelimit = SCIP_LONGINT_MAX;
2269
2270 do
2271 {
2272 if( problem != NULL )
2273 {
2274 SCIP_CALL( solveProblem(problem, result) );
2275 }
2276 } while( *result == SCIP_DELAYNODE && SCIPgetDepth(scip) == 0 && !SCIPisStopped(scip) && SCIPgetNNodes(scip) < nodelimit);
2277
2278 return SCIP_OKAY;
2279}
2280
2281/** presolving method of constraint handler */
2282static
2284{ /*lint --e{715}*/
2285 SCIP_CONSHDLRDATA* conshdlrdata;
2286 SCIP_VAR** sortedvars;
2288 int* compstartsvars;
2289 int* compstartsconss;
2290 int nsortedvars;
2291 int nsortedconss;
2292 int ncomponents;
2293 int ncompsminsize;
2294 int ncompsmaxsize;
2295 int nvars;
2296
2297 assert(conshdlr != NULL);
2299 assert(result != NULL);
2300 assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2301 assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2302
2303 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2304 assert(conshdlrdata != NULL);
2305
2307
2309 return SCIP_OKAY;
2310
2311 /* do not run, if not all variables are explicitly known */
2312 if( SCIPgetNActivePricers(scip) > 0 )
2313 return SCIP_OKAY;
2314
2316
2317 /* we do not want to run, if there are no variables left */
2318 if( nvars == 0 )
2319 return SCIP_OKAY;
2320
2321 /* only call the components presolving, if presolving would be stopped otherwise */
2323 return SCIP_OKAY;
2324
2325 /* the components constraint handler does kind of dual reductions */
2327 return SCIP_OKAY;
2328
2329 /* check for a reached timelimit */
2330 if( SCIPisStopped(scip) )
2331 return SCIP_OKAY;
2332
2334
2335 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2336
2337 /* allocate memory for sorted components */
2342
2343 /* search for components */
2344 SCIP_CALL( findComponents(scip, conshdlrdata, NULL, sortedvars, sortedconss, compstartsvars,
2345 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2346
2347 if( ncompsmaxsize > 0 )
2348 {
2349 char name[SCIP_MAXSTRLEN];
2350 SCIP* subscip;
2351 SCIP_HASHMAP* consmap;
2352 SCIP_HASHMAP* varmap;
2354 SCIP_VAR** subvars;
2356 SCIP_Bool success;
2357 SCIP_Bool solved;
2358 int nsolved = 0;
2359 int ncompvars;
2360 int ncompconss;
2361 int comp;
2362
2363 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",
2365
2366 /* build subscip */
2367 SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2368
2369 if( subscip == NULL )
2370 goto TERMINATE;
2371
2372 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/usesmalltables", TRUE) );
2373 SCIP_CALL( SCIPsetIntParam(subscip, "constraints/" CONSHDLR_NAME "/propfreq", -1) );
2374
2375 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
2377
2378 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nsortedvars) );
2379
2380 /* loop over all components */
2381 for( comp = 0; comp < ncompsmaxsize && !SCIPisStopped(scip); comp++ )
2382 {
2383#ifdef WITH_DEBUG_SOLUTION
2384 if( SCIPgetStage(subscip) > SCIP_STAGE_INIT )
2385 {
2386 SCIP_CALL( SCIPfree(&subscip) );
2387 SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2388 }
2389#endif
2390 /* get component variables */
2391 compvars = &(sortedvars[compstartsvars[comp]]);
2393
2394 /* get component constraints */
2397
2398 /* if we have an unlocked variable, let duality fixing do the job! */
2399 if( ncompconss == 0 )
2400 {
2401 assert(ncompvars == 1);
2402 continue;
2403 }
2404
2406#ifdef DETAILED_OUTPUT
2407 {
2408 int nbinvars = 0;
2409 int nintvars = 0;
2410 int ncontvars = 0;
2411 int i;
2412
2413 for( i = 0; i < ncompvars; ++i )
2414 {
2416 ++nbinvars;
2418 ++nintvars;
2419 else
2420 ++ncontvars;
2421 }
2422 SCIPdebugMsg(scip, "solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n",
2423 comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss);
2424 }
2425#endif
2426#ifndef NDEBUG
2427 {
2428 int i;
2429 for( i = 0; i < ncompvars; ++i )
2431 }
2432#endif
2433
2434 /* get name of the original problem and add "comp_nr" */
2435 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), comp);
2436
2437 SCIP_CALL( copyToSubscip(scip, subscip, name, compvars, subvars,
2438 compconss, varmap, consmap, ncompvars, ncompconss, &success) );
2439
2440 if( !success )
2441 {
2442 SCIPhashmapFree(&varmap);
2443 continue;
2444 }
2445
2446 /* set up debug solution */
2447#ifdef WITH_DEBUG_SOLUTION
2449 {
2451 SCIP_Real val;
2452 int i;
2453
2455
2456 /* set solution values in the debug solution if it is available */
2457 if( debugsol != NULL )
2458 {
2459 SCIPdebugSolEnable(subscip);
2460
2461 for( i = 0; i < ncompvars; ++i )
2462 {
2463 if( subvars[i] != NULL )
2464 {
2466 SCIP_CALL( SCIPdebugAddSolVal(subscip, subvars[i], val) );
2467 }
2468 }
2469 }
2470 }
2471#endif
2472
2473 /* solve the subproblem and evaluate the result, i.e. apply fixings of variables and remove constraints */
2474 SCIP_CALL( solveAndEvalSubscip(scip, conshdlrdata, subscip, compvars, subvars, compconss,
2475 ncompvars, ncompconss, ndelconss, nfixedvars, nchgbds, result, &solved) );
2476
2477 /* free variable hash map */
2478 SCIPhashmapFree(&varmap);
2479
2480 if( solved )
2481 ++nsolved;
2482
2483 /* if the component is unbounded or infeasible, this holds for the complete problem as well */
2484 if( *result == SCIP_UNBOUNDED || *result == SCIP_CUTOFF )
2485 break;
2486 /* if there is only one component left, let's solve this in the main SCIP */
2487 else if( nsolved == ncomponents - 1 )
2488 break;
2489 }
2490
2491 SCIPfreeBufferArray(scip, &subvars);
2492 SCIPhashmapFree(&consmap);
2493
2494 SCIP_CALL( SCIPfree(&subscip) );
2495 }
2496
2497 TERMINATE:
2501 SCIPfreeBufferArray(scip, &sortedvars);
2502
2503 return SCIP_OKAY;
2504}
2505
2506/** frees specific constraint data */
2507static
2509{ /*lint --e{715}*/
2510 assert(conshdlr != NULL);
2512 assert(consdata != NULL);
2513 assert(*consdata != NULL);
2514
2515 SCIP_CALL( freeProblem((PROBLEM**) consdata) );
2516
2517 return SCIP_OKAY;
2518}
2519
2520/** constraint enforcing method of constraint handler for relaxation solutions */
2521static
2523{ /*lint --e{715}*/
2524 assert(result != NULL);
2525
2526 /* no enforcement is performed, but the callback is needed for all constraint handlers with needscons = FALSE */
2528
2529 return SCIP_OKAY;
2530}
2531
2532/** variable rounding lock method of constraint handler */
2533static
2535{ /*lint --e{715}*/
2536 return SCIP_OKAY;
2537}
2538
2539#ifndef NDEBUG
2540/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
2541static
2543{ /*lint --e{715}*/
2544 assert(nconss == 0);
2545
2546 return SCIP_OKAY;
2547}
2548#endif
2549
2550#define consEnfolpComponents NULL
2551#define consEnfopsComponents NULL
2552#define consCheckComponents NULL
2553
2554/** creates the components constraint handler and includes it in SCIP */
2556 SCIP* scip /**< SCIP data structure */
2557 )
2558{
2559 SCIP_CONSHDLRDATA* conshdlrdata;
2560 SCIP_CONSHDLR* conshdlr;
2561
2562 /* create components constraint data */
2563 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2564 conshdlrdata->subscipdepth = 0;
2565
2566 /* include constraint handler */
2570 conshdlrdata) );
2571 assert(conshdlr != NULL);
2572
2577
2580#ifndef NDEBUG
2582#endif
2585
2587 "constraints/" CONSHDLR_NAME "/maxdepth",
2588 "maximum depth of a node to run components detection (-1: disable component detection during solving)",
2589 &conshdlrdata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2591 "constraints/" CONSHDLR_NAME "/maxintvars",
2592 "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)",
2593 &conshdlrdata->maxintvars, TRUE, DEFAULT_MAXINTVARS, -1, INT_MAX, NULL, NULL) );
2595 "constraints/" CONSHDLR_NAME "/minsize",
2596 "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound",
2597 &conshdlrdata->minsize, TRUE, DEFAULT_MINSIZE, 0, INT_MAX, NULL, NULL) );
2599 "constraints/" CONSHDLR_NAME "/minrelsize",
2600 "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound",
2601 &conshdlrdata->minrelsize, TRUE, DEFAULT_MINRELSIZE, 0.0, 1.0, NULL, NULL) );
2603 "constraints/" CONSHDLR_NAME "/nodelimit",
2604 "maximum number of nodes to be solved in subproblems during presolving",
2605 &conshdlrdata->nodelimit, FALSE, DEFAULT_NODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
2607 "constraints/" CONSHDLR_NAME "/intfactor",
2608 "the weight of an integer variable compared to binary variables",
2609 &conshdlrdata->intfactor, FALSE, DEFAULT_INTFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2611 "constraints/" CONSHDLR_NAME "/feastolfactor",
2612 "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0",
2613 &conshdlrdata->feastolfactor, TRUE, DEFAULT_FEASTOLFACTOR, 0.0, 1000000.0, NULL, NULL) );
2614
2615 return SCIP_OKAY;
2616}
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)
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DESC
#define DEFAULT_MINRELSIZE
static SCIP_RETCODE createConsComponents(SCIP *scip, SCIP_CONS **cons, const char *name, PROBLEM *problem)
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)
static SCIP_RETCODE initComponent(PROBLEM *problem)
static SCIP_RETCODE fillDigraph(SCIP *scip, SCIP_DIGRAPH *digraph, SCIP_CONS **conss, int nconss, int *unfixedvarpos, int nunfixedvars, int *firstvaridxpercons, SCIP_Bool *success)
static int getMinsize(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
#define CONSHDLR_PROP_TIMING
#define DEFAULT_FEASTOLFACTOR
#define consEnfolpComponents
#define CONSHDLR_MAXPREROUNDS
#define consEnfopsComponents
#define DEFAULT_MAXINTVARS
static SCIP_RETCODE componentSetupWorkingSol(COMPONENT *component, SCIP_HASHMAP *varmap)
static SCIP_RETCODE freeProblem(PROBLEM **problem)
#define DEFAULT_MAXDEPTH
static SCIP_RETCODE componentCreateSubscip(COMPONENT *component, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool *success)
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP **subscip)
#define DEFAULT_INTFACTOR
#define DEFAULT_NODELIMIT
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)
#define consCheckComponents
static SCIP_RETCODE solveProblem(PROBLEM *problem, SCIP_RESULT *result)
#define CONSHDLR_PROPFREQ
static SCIP_RETCODE solveSubscip(SCIP *scip, SCIP *subscip, SCIP_Longint nodelimit, SCIP_Real gaplimit)
static SCIP_RETCODE solveComponent(COMPONENT *component, SCIP_Bool lastcomponent, SCIP_RESULT *result)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE freeComponent(COMPONENT *component)
#define CONSHDLR_EAGERFREQ
#define DEFAULT_MINSIZE
#define CONSHDLR_ENFOPRIORITY
struct Problem PROBLEM
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)
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)
static SCIP_RETCODE initProblem(SCIP *scip, PROBLEM **problem, SCIP_Real fixedvarsobjsum, int ncomponents)
#define CONSHDLR_NAME
struct Component COMPONENT
#define CONSHDLR_DELAYPROP
constraint handler for handling independent components
methods for debugging
#define SCIPdebugGetSolVal(scip, var, val)
Definition debug.h:299
#define SCIPdebugSolEnable(scip)
Definition debug.h:301
#define SCIPdebugAddSolVal(scip, var, val)
Definition debug.h:298
#define SCIPdebugSolIsEnabled(scip)
Definition debug.h:303
#define SCIPdebugSolIsValidInSubtree(scip, isvalidinsubtree)
Definition debug.h:300
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_REAL_MAX
Definition def.h:174
#define MIN(x, y)
Definition def.h:243
#define ABS(x)
Definition def.h:235
#define SQR(x)
Definition def.h:214
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define SCIP_LONGINT_MAX
Definition def.h:159
#define SCIP_CALL(x)
Definition def.h:374
SCIP_RETCODE SCIPincludeConshdlrComponents(SCIP *scip)
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
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
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_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:2564
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:3296
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
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition misc.c:8089
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition misc.c:8298
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition misc.c:7662
SCIP_RETCODE SCIPdigraphSetSizes(SCIP_DIGRAPH *digraph, int *sizes)
Definition misc.c:7544
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition misc.c:7568
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition misc.c:8285
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition scip_prob.c:2127
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
int SCIPgetNContVars(SCIP *scip)
Definition scip_prob.c:2172
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition scip_prob.c:3088
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2843
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNOrigVars(SCIP *scip)
Definition scip_prob.c:2432
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
Definition scip_prob.c:3696
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition scip_prob.c:3323
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition scip_param.c:250
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
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition scip_param.c:219
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
SCIP_PARAM * SCIPgetParam(SCIP *scip, const char *name)
Definition scip_param.c:234
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition scip_param.c:545
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_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPresetParam(SCIP *scip, const char *name)
Definition scip_param.c:835
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:953
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition scip_param.c:288
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPfixParam(SCIP *scip, const char *name)
Definition scip_param.c:367
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition scip_param.c:603
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)),)
Definition misc.c:1295
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition misc.c:1322
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition misc.c:1394
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition misc.c:1527
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition misc.c:1493
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition cons.c:4227
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition scip_cons.c:540
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_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:323
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
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
Definition scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4217
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4670
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4593
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition scip_cons.c:2622
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition cons.c:8244
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8234
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8383
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8413
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition scip_cons.c:2578
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8403
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
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8433
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8214
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8463
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8393
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8483
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:258
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition scip_mem.c:126
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:76
#define SCIPfreeMemoryArray(scip, ptr)
Definition scip_mem.h:80
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7490
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition scip_sol.c:3309
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2169
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
Definition sol.c:2741
SCIP_RETCODE SCIPprintBestSol(SCIP *scip, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:2235
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2070
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition sol.c:2804
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition scip_sol.c:421
SCIP_RETCODE SCIPaddSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *stored)
Definition scip_sol.c:2791
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition sol.c:2835
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
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1300
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1347
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1432
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition sol.c:2849
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:222
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
void SCIPaddNNodes(SCIP *scip, SCIP_Longint nnodes)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition scip_tree.c:146
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5205
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17748
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5322
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetIndex(SCIP_VAR *var)
Definition var.c:17758
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
void SCIPvarMarkDeleteGlobalStructures(SCIP_VAR *var)
Definition var.c:17676
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8278
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition scip_var.c:1832
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition scip_var.c:8658
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:8631
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
int c
int maxdepth
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
int nbinvars
int nintvars
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for branch and bound tree
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for data structures
general public methods
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_VAR ** fixedsubvars
PROBLEM * problem
SCIP_Real lastdualbound
SCIP_SOL * workingsol
SCIP_VAR ** subvars
SCIP_STATUS laststatus
SCIP_Real fixedvarsobjsum
SCIP_Real lastprimalbound
SCIP_VAR ** vars
SCIP_VAR ** fixedvars
SCIP_Bool solved
#define SCIP_DECL_CONSDELETE(x)
Definition type_cons.h:229
#define SCIP_DECL_CONSINITSOL(x)
Definition type_cons.h:201
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition type_cons.h:64
#define SCIP_DECL_CONSENFORELAX(x)
Definition type_cons.h:388
#define SCIP_DECL_CONSPROP(x)
Definition type_cons.h:505
#define SCIP_DECL_CONSPRESOL(x)
Definition type_cons.h:560
#define SCIP_DECL_CONSLOCK(x)
Definition type_cons.h:675
struct SCIP_ConsData SCIP_CONSDATA
Definition type_cons.h:65
#define SCIP_DECL_CONSHDLRCOPY(x)
Definition type_cons.h:108
#define SCIP_DECL_CONSFREE(x)
Definition type_cons.h:116
@ SCIP_VERBLEVEL_NORMAL
@ SCIP_VERBLEVEL_FULL
#define SCIP_DECL_SORTPTRCOMP(x)
Definition type_misc.h:188
@ SCIP_PARAMSETTING_OFF
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_FEASIBLE
Definition type_result.h:45
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_UNBOUNDED
Definition type_result.h:47
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_DELAYNODE
Definition type_result.h:59
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_PLUGINNOTFOUND
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_PROBLEM
Definition type_set.h:45
@ SCIP_STAGE_PRESOLVING
Definition type_set.h:49
@ SCIP_STAGE_INIT
Definition type_set.h:44
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_TOTALNODELIMIT
Definition type_stat.h:45
@ SCIP_STATUS_BESTSOLLIMIT
Definition type_stat.h:57
@ SCIP_STATUS_SOLLIMIT
Definition type_stat.h:54
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_UNKNOWN
Definition type_stat.h:42
@ SCIP_STATUS_GAPLIMIT
Definition type_stat.h:53
@ SCIP_STATUS_USERINTERRUPT
Definition type_stat.h:43
@ SCIP_STATUS_TERMINATE
Definition type_stat.h:65
@ SCIP_STATUS_INFORUNBD
Definition type_stat.h:64
@ SCIP_STATUS_STALLNODELIMIT
Definition type_stat.h:48
@ SCIP_STATUS_TIMELIMIT
Definition type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
@ SCIP_STATUS_NODELIMIT
Definition type_stat.h:44
@ SCIP_STATUS_MEMLIMIT
Definition type_stat.h:52
@ SCIP_STATUS_RESTARTLIMIT
Definition type_stat.h:60
enum SCIP_Status SCIP_STATUS
Definition type_stat.h:67
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97