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 devide 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 gloablly 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
498 /* reduce the effort spent for hash tables; however, if the debug solution is enabled and valid in this subtree,
499 * hash tables are needed for installing the debug solution
500 */
501#ifdef WITH_DEBUG_SOLUTION
504#endif
505 {
506 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/usevartable", FALSE) );
507 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/useconstable", FALSE) );
508 }
509
510 /* disable presolving */
512
513 /* disable component presolving and fix the parameter */
514 SCIP_CALL( SCIPsetIntParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds", 0) );
515 SCIP_CALL( SCIPfixParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds") );
516
517 /* find the components constraint handler in the sub-SCIP and inform it about the actual depth in the tree */
520
523 newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth + SCIPgetDepth(scip);
524
525 /* disable output, unless in extended debug mode */
526#ifndef SCIP_MORE_DEBUG
527 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
528#endif
529 }
530 else
531 {
532 SCIP_CALL( SCIPfree(subscip) );
533 *subscip = NULL;
534 }
535
536 return SCIP_OKAY;
537}
538
539/** copies the given variables and constraints to the given sub-SCIP */
540static
542 SCIP* scip, /**< source SCIP */
543 SCIP* subscip, /**< target SCIP */
544 const char* name, /**< name for copied problem */
545 SCIP_VAR** vars, /**< array of variables to copy */
546 SCIP_VAR** subvars, /**< array to fill with copied vars */
547 SCIP_CONS** conss, /**< constraint to copy */
548 SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */
549 SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */
550 int nvars, /**< number of variables to copy */
551 int nconss, /**< number of constraints to copy */
552 SCIP_Bool* success /**< pointer to store whether copying was successful */
553 )
554{
556 int i;
557
558 assert(scip != NULL);
559 assert(subscip != NULL);
560 assert(vars != NULL);
561 assert(subvars != NULL);
562 assert(conss != NULL);
563 assert(varmap != NULL);
564 assert(consmap != NULL);
565 assert(success != NULL);
566
567 *success = TRUE;
568
569 /* create problem in sub-SCIP */
570 SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
571
572 /* copy variables */
573 for( i = 0; i < nvars; ++i )
574 {
575 SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &subvars[i], varmap, consmap, FALSE, success) );
576
577 /* abort if variable was not successfully copied */
578 if( !(*success) )
579 return SCIP_OKAY;
580 }
581
582 /* copy constraints */
583 for( i = 0; i < nconss; ++i )
584 {
585 assert(!SCIPconsIsModifiable(conss[i]));
586
587 /* copy the constraint */
588 SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
592
593 /* abort if constraint was not successfully copied */
594 if( !(*success) )
595 return SCIP_OKAY;
596
597 SCIP_CALL( SCIPaddCons(subscip, newcons) );
598 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
599 }
600
601 return SCIP_OKAY;
602}
603
604/** create the sub-SCIP for a given component */
605static
607 COMPONENT* component, /**< component structure */
608 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
609 SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */
610 SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */
611 SCIP_CONS** conss, /**< constraints contained in this component */
612 int nconss, /**< number of constraints contained in this component */
613 SCIP_Bool* success /**< pointer to store whether the copying process was successful */
614 )
615{
616 char name[SCIP_MAXSTRLEN];
617 PROBLEM* problem;
618 SCIP* scip;
619 int minsize;
620
622 assert(consmap != NULL);
623 assert(conss != NULL);
624 assert(success != NULL);
625 assert(component->nvars > 0);
626
627 problem = component->problem;
628 assert(problem != NULL);
629
630 scip = problem->scip;
631 assert(scip != NULL);
632
633 (*success) = TRUE;
634
635 SCIP_CALL( createSubscip(scip, conshdlrdata, &component->subscip) );
636
637 if( component->subscip != NULL )
638 {
639 /* get minimum size of components to solve individually and set the parameter in the sub-SCIP */
640 minsize = getMinsize(scip, conshdlrdata);
641
642 SCIP_CALL( SCIPsetIntParam(component->subscip, "constraints/" CONSHDLR_NAME "/minsize", minsize) );
643
644 /* get name of the original problem and add "comp_nr" */
645 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, component->number);
646
647 SCIP_CALL( copyToSubscip(scip, component->subscip, name, component->vars, component->subvars,
648 conss, varmap, consmap, component->nvars, nconss, success) );
649
650 if( !(*success) )
651 {
652 SCIP_CALL( SCIPfree(&component->subscip) );
653 component->subscip = NULL;
654 }
655 }
656 else
657 (*success) = FALSE;
658
659 return SCIP_OKAY;
660}
661
662/** solve a given sub-SCIP up to the given limits */
663static
665 SCIP* scip, /**< main SCIP */
666 SCIP* subscip, /**< sub-SCIP to solve */
667 SCIP_Longint nodelimit, /**< node limit */
668 SCIP_Real gaplimit /**< gap limit */
669 )
670{
671 SCIP_Real timelimit;
672 SCIP_Real memorylimit;
673 SCIP_Bool avoidmemout;
674
675 assert(scip != NULL);
676 assert(subscip != NULL);
677
678 /* set time limit */
679 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
680 if( !SCIPisInfinity(scip, timelimit) )
681 {
682 timelimit -= SCIPgetSolvingTime(scip);
683 timelimit += SCIPgetSolvingTime(subscip);
684 }
685
686 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
687 /* @todo count memory of other components */
688 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
689 if( !SCIPisInfinity(scip, memorylimit) )
690 {
691 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
692 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
693 }
694
695 /* check if mem limit needs to be avoided */
696 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
697
698 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == TRUE)
699 * to create a copy of SCIP, including external memory usage */
700 if( avoidmemout && memorylimit <= 0.0 )
701 {
702 SCIPdebugMessage("--> not solved (not enough memory left)\n");
703 return SCIP_OKAY;
704 }
705 else if( timelimit <= 0.0 )
706 {
707 SCIPdebugMessage("--> not solved (not enough time left)\n");
708 return SCIP_OKAY;
709 }
710
711 /* SCIP copy limits will set wrong time limits since it does not take into account time spent already in the
712 * sub-SCIP; nevertheless, we call it to set the memory limit and unset all other limits, if set in the main SCIP
713 */
714 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
715
716 /* set time and memory limit for the subproblem */
717 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
718
719 /* only set soft time limit if it exists */
720 if( SCIPgetParam(scip, "limits/softtime") != NULL )
721 {
722 SCIP_Real softtimelimit;
723
724 /* set soft time limit, if specified in main SCIP and if it exists */
725 SCIP_CALL( SCIPgetRealParam(scip, "limits/softtime", &softtimelimit) );
726 if( softtimelimit > -0.5 )
727 {
728 softtimelimit -= SCIPgetSolvingTime(scip);
729 softtimelimit += SCIPgetSolvingTime(subscip);
730 softtimelimit = MAX(softtimelimit, 0.0);
731 }
732
733 SCIP_CALL( SCIPsetRealParam(subscip, "limits/softtime", softtimelimit) );
734 }
735
736 /* set gap limit */
737 SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", gaplimit) );
738
739 /* set node limit */
740 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
741
742 /* solve the subproblem */
743 SCIP_CALL( SCIPsolve(subscip) );
744
745#ifdef SCIP_MORE_DEBUG
746 SCIP_CALL( SCIPprintBestSol(subscip, NULL, FALSE) );
748#endif
749
750 return SCIP_OKAY;
751}
752
753/** solve a connected component during presolving and evaluate the result */
754static
756 SCIP* scip, /**< SCIP main data structure */
757 SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
758 SCIP* subscip, /**< sub-SCIP to be solved */
759 SCIP_VAR** vars, /**< array of variables copied to this component */
760 SCIP_VAR** subvars, /**< array of sub-SCIP variables corresponding to the vars array */
761 SCIP_CONS** conss, /**< array of constraints copied to this component */
762 int nvars, /**< number of variables copied to this component */
763 int nconss, /**< number of constraints copied to this component */
764 int* ndeletedconss, /**< pointer to store the number of deleted constraints */
765 int* nfixedvars, /**< pointer to store the number of fixed variables */
766 int* ntightenedbounds, /**< pointer to store the number of bound tightenings */
767 SCIP_RESULT* result, /**< pointer to store the result of the component solving */
768 SCIP_Bool* solved /**< pointer to store if the problem was solved to optimality */
769 )
770{
771 int i;
772
773 assert(scip != NULL);
774 assert(conshdlrdata != NULL);
775 assert(subscip != NULL);
776 assert(vars != NULL);
777 assert(conss != NULL);
779 assert(nfixedvars != NULL);
781 assert(result != NULL);
782
783 *solved = FALSE;
784
785 SCIP_CALL( solveSubscip(scip, subscip, conshdlrdata->nodelimit, 0.0) );
786
787 if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
788 {
789 SCIP_SOL* sol;
790 SCIP_VAR* var;
792 SCIP_Real* fixvals;
793 SCIP_Bool feasible;
794 SCIP_Bool infeasible;
795 SCIP_Bool fixed;
796
797 sol = SCIPgetBestSol(subscip);
798
799#ifdef SCIP_DEBUG
801#else
803#endif
804
805 SCIPdebugMessage("--> solved to optimality: time=%.2f, solution is%s feasible\n", SCIPgetSolvingTime(subscip), feasible ? "" : " not");
806
808
809 if( feasible )
810 {
811 SCIP_Real glb;
812 SCIP_Real gub;
813
814 /* get values of variables in the optimal solution */
815 for( i = 0; i < nvars; ++i )
816 {
817 var = vars[i];
818 subvar = subvars[i];
819
820 /* get global bounds */
823
824 if( subvar != NULL )
825 {
826 /* get solution value from optimal solution of the sub-SCIP */
827 fixvals[i] = SCIPgetSolVal(subscip, sol, subvar);
828
831
832 /* checking a solution is done with a relative tolerance of feasibility epsilon, if we really want to
833 * change the bounds of the variables by fixing them, the old bounds must not be violated by more than
834 * the absolute epsilon; therefore, we change the fixing values, if needed, and mark that the solution
835 * has to be checked again
836 */
837 if( SCIPisGT(scip, fixvals[i], gub) )
838 {
839 SCIPdebugMessage("variable <%s> fixval: %f violates global upperbound: %f\n",
841 fixvals[i] = gub;
842 feasible = FALSE;
843 }
844 else if( SCIPisLT(scip, fixvals[i], glb) )
845 {
846 SCIPdebugMessage("variable <%s> fixval: %f violates global lowerbound: %f\n",
848 fixvals[i] = glb;
849 feasible = FALSE;
850 }
853 }
854 else
855 {
856 /* the variable was not copied, so it was cancelled out of constraints during copying;
857 * thus, the variable is not constrained and we fix it to its best bound
858 */
860 fixvals[i] = glb;
862 fixvals[i] = gub;
863 else
864 {
865 fixvals[i] = 0.0;
866 fixvals[i] = MIN(fixvals[i], gub);
867 fixvals[i] = MAX(fixvals[i], glb);
868 }
869 }
870 }
871
872 /* the solution value of at least one variable is feasible with a relative tolerance of feasibility epsilon,
873 * but infeasible with an absolute tolerance of epsilon; try to set the variables to the bounds and check
874 * solution again in the original space (changing the values might now introduce infeasibilities of constraints)
875 */
876 if( !feasible )
877 {
878 SCIP_Real origobj;
879
880 SCIPdebugMessage("solution violates bounds by more than epsilon, check the corrected solution...\n");
881
882 origobj = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
883
884 SCIP_CALL( SCIPfreeTransform(subscip) );
885
886 SCIP_CALL( SCIPcreateOrigSol(subscip, &sol, NULL) );
887
888 /* set solution values of variables */
889 for( i = 0; i < nvars; ++i )
890 {
891 if( subvars[i] != NULL )
892 {
893 SCIP_CALL( SCIPsetSolVal(subscip, sol, subvars[i], fixvals[i]) );
894 }
895 }
896
897 /* check the solution; integrality and bounds should be fulfilled and do not have to be checked */
899
900#ifndef NDEBUG
901 /* in debug mode, we additionally check integrality and bounds */
902 if( feasible )
903 {
906 }
907#endif
908
909 SCIPdebugMessage("--> corrected solution is%s feasible\n", feasible ? "" : " not");
910
911 if( !SCIPisFeasEQ(subscip, SCIPsolGetOrigObj(sol), origobj) )
912 {
913 SCIPdebugMessage("--> corrected solution has a different objective value (old=%16.9g, corrected=%16.9g)\n",
914 origobj, SCIPsolGetOrigObj(sol));
915
916 feasible = FALSE;
917 }
918
919 SCIP_CALL( SCIPfreeSol(subscip, &sol) );
920 }
921
922 /* if the solution is feasible, fix variables and delete constraints of the component */
923 if( feasible )
924 {
925 /* fix variables */
926 for( i = 0; i < nvars; ++i )
927 {
932
933 SCIP_CALL( SCIPfixVar(scip, vars[i], fixvals[i], &infeasible, &fixed) );
935 assert(!infeasible);
936 assert(fixed);
937 (*nfixedvars)++;
938 }
939
940 /* delete constraints */
941 for( i = 0; i < nconss; ++i )
942 {
943 SCIP_CALL( SCIPdelCons(scip, conss[i]) );
944 (*ndeletedconss)++;
945 }
946
948 *solved = TRUE;
949 }
950 }
951
953 }
954 else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
955 {
957 }
958 else if( SCIPgetStatus(subscip) == SCIP_STATUS_UNBOUNDED || SCIPgetStatus(subscip) == SCIP_STATUS_INFORUNBD )
959 {
960 /* TODO: store unbounded ray in original SCIP data structure */
962 }
963 else
964 {
965 SCIPdebugMessage("--> solving interrupted (status=%d, time=%.2f)\n",
966 SCIPgetStatus(subscip), SCIPgetSolvingTime(subscip));
967
968 /* transfer global fixings to the original problem; we can only do this, if we did not find a solution in the
969 * subproblem, because otherwise, the primal bound might lead to dual reductions that cannot be transferred to
970 * the original problem without also transferring the possibly suboptimal solution (which is currently not
971 * possible)
972 */
973 if( SCIPgetNSols(subscip) == 0 )
974 {
975 SCIP_Bool infeasible;
976 SCIP_Bool tightened;
977 int ntightened;
978
979 ntightened = 0;
980
981 for( i = 0; i < nvars; ++i )
982 {
983 if( subvars[i] == NULL )
984 continue;
985
987 &infeasible, &tightened) );
988 assert(!infeasible);
989 if( tightened )
990 ntightened++;
991
993 &infeasible, &tightened) );
994 assert(!infeasible);
995 if( tightened )
996 ntightened++;
997 }
998
1000
1001 *ntightenedbounds += ntightened;
1002
1003 SCIPdebugMessage("--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened);
1004 }
1005 }
1006
1007 return SCIP_OKAY;
1008}
1009
1010/** (continues) solving a connected component */
1011static
1013 COMPONENT* component, /**< component structure */
1014 SCIP_Bool lastcomponent, /**< is this the last component to be solved? */
1015 SCIP_RESULT* result /**< pointer to store the result of the solving process */
1016 )
1017{
1018 PROBLEM* problem;
1019 SCIP* scip;
1020 SCIP* subscip;
1021 SCIP_SOL* bestsol;
1022 SCIP_Longint nodelimit;
1023 SCIP_Longint lastnnodes;
1024 SCIP_Real gaplimit;
1025 SCIP_STATUS status;
1026
1027 assert(component != NULL);
1028
1029 problem = component->problem;
1030 assert(problem != NULL);
1031
1032 scip = problem->scip;
1033 assert(scip != NULL);
1034
1035 subscip = component->subscip;
1036 assert(subscip != NULL);
1037
1039
1040 SCIPdebugMessage("solve component <%s> (ncalls=%d, absgap=%.9g)\n",
1041 SCIPgetProbName(subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1042
1043 bestsol = SCIPgetBestSol(scip);
1044
1045 /* update best solution of component */
1046 if( bestsol != NULL && SCIPsolGetIndex(bestsol) != component->lastbestsolindex )
1047 {
1048 SCIP_SOL* compsol = component->workingsol;
1049 SCIP_VAR** vars = component->vars;
1050 SCIP_VAR** subvars = component->subvars;
1051 int nvars = component->nvars;
1052 int v;
1053
1054 component->lastbestsolindex = SCIPsolGetIndex(bestsol);
1055
1056 /* set solution values of component variables */
1057 for( v = 0; v < nvars; ++v )
1058 {
1059 if( subvars[v] != NULL )
1060 {
1061 SCIP_CALL( SCIPsetSolVal(subscip, compsol, subvars[v], SCIPgetSolVal(scip, bestsol, vars[v])) );
1062 }
1063 }
1064#ifndef NDEBUG
1065 for( v = 0; v < component->nfixedvars; ++v )
1066 {
1067 if( component->fixedsubvars[v] != NULL )
1068 assert(SCIPisEQ(scip, SCIPgetSolVal(subscip, compsol, component->fixedsubvars[v]),
1069 SCIPvarGetLbGlobal(component->fixedsubvars[v])));
1070 }
1071#endif
1072
1073 if( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM
1074 || SCIPisLT(subscip, SCIPgetSolOrigObj(subscip, compsol), SCIPgetPrimalbound(subscip)) )
1075 {
1076 SCIP_Bool feasible;
1077
1078 SCIPdebugMessage("checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n",
1079 SCIPgetProbName(subscip), problem->name,
1080 SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM ? SCIPinfinity(subscip) : SCIPgetPrimalbound(subscip),
1081 SCIPgetSolOrigObj(subscip, compsol));
1082
1084 if( feasible )
1085 {
1086 SCIPdebugMessage("... feasible, adding solution.\n");
1087
1088 SCIP_CALL( SCIPaddSol(subscip, compsol, &feasible) );
1089 }
1090
1091 /* We cannot take the value of compsol as a cutoff bound if it was not feasible; some of the fixed connecting
1092 * variables are different and might not allow for a better solution in this component, but still for far
1093 * better solutions in other components. Therefore, the only cutoffbound we can apply is the cutoffbound
1094 * of the problem reduced by the dual bounds of the other components
1095 */
1096 if( problem->nlowerboundinf == 0 || (problem->nlowerboundinf == 1
1097 && SCIPisInfinity(scip, -component->lastdualbound)) )
1098 {
1099 SCIP_Real newcutoffbound = SCIPgetSolTransObj(scip, bestsol);
1100
1101 assert(problem->nlowerboundinf > 0 || SCIPisGE(scip, newcutoffbound, problem->lowerbound));
1102
1103 newcutoffbound = newcutoffbound - problem->lowerbound + component->fixedvarsobjsum;
1104
1105 if( problem->nlowerboundinf == 0 )
1106 newcutoffbound += component->lastdualbound;
1107
1108 if( SCIPisSumLT(subscip, newcutoffbound, SCIPgetCutoffbound(subscip)) )
1109 {
1110 SCIPdebugMessage("update cutoff bound to %16.9g\n", newcutoffbound);
1111
1113 }
1114 }
1115 }
1116 }
1117
1118 assert(component->laststatus != SCIP_STATUS_OPTIMAL);
1119
1120 SCIPdebugMsg(scip, "solve sub-SCIP for component <%s> (ncalls=%d, absgap=%16.9g)\n",
1121 SCIPgetProbName(component->subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1122
1123 if( component->ncalls == 0 )
1124 {
1125 nodelimit = 1LL;
1126 gaplimit = 0.0;
1127
1128 lastnnodes = 0;
1129 }
1130 else
1131 {
1132 SCIP_Longint mainnodelimit;
1133
1135
1136 SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &mainnodelimit) );
1137
1138 nodelimit = 2 * lastnnodes;
1139 nodelimit = MAX(nodelimit, 10LL);
1140
1141 if( mainnodelimit != -1 )
1142 {
1144 nodelimit = MIN(nodelimit, mainnodelimit - lastnnodes);
1145 }
1146
1147 /* set a gap limit of half the current gap (at most 10%) */
1148 if( SCIPgetGap(component->subscip) < 0.2 )
1149 gaplimit = 0.5 * SCIPgetGap(component->subscip);
1150 else
1151 gaplimit = 0.1;
1152
1153 if( lastcomponent )
1154 gaplimit = 0.0;
1155 }
1156
1157 SCIP_CALL( solveSubscip(scip, subscip, nodelimit, gaplimit) );
1158
1160
1162
1163 status = SCIPgetStatus(subscip);
1164
1165 component->laststatus = status;
1166 ++component->ncalls;
1167
1168 SCIPdebugMsg(scip, "--> (status=%d, nodes=%lld, time=%.2f): gap: %12.5g%% absgap: %16.9g\n",
1169 status, SCIPgetNNodes(subscip), SCIPgetSolvingTime(subscip), 100.0*SCIPgetGap(subscip),
1170 SCIPgetPrimalbound(subscip) - SCIPgetDualbound(subscip));
1171
1173
1174 switch( status )
1175 {
1177 component->solved = TRUE;
1178 break;
1180 component->solved = TRUE;
1181
1182 /* the problem is really infeasible */
1183 if( SCIPisInfinity(subscip, SCIPgetPrimalbound(subscip)) )
1184 {
1186 }
1187 /* the cutoff bound was reached; no solution better than the cutoff bound exists */
1188 else
1189 {
1191 component->laststatus = SCIP_STATUS_OPTIMAL;
1192 assert(SCIPisLE(subscip, SCIPgetDualbound(subscip), SCIPgetPrimalbound(subscip)));
1193 }
1194 break;
1197 /* TODO: store unbounded ray in original SCIP data structure */
1199 component->solved = TRUE;
1200 break;
1203 break;
1215 default:
1216 break;
1217 }
1218
1219 /* evaluate call */
1220 if( *result == SCIP_SUCCESS )
1221 {
1222 SCIP_SOL* sol = SCIPgetBestSol(subscip);
1223 SCIP_VAR* var;
1225 SCIP_Real newdualbound;
1226 int v;
1227
1228 /* get dual bound as the minimum of SCIP dual bound and sub-problems dual bound */
1229 newdualbound = SCIPgetDualbound(subscip) - component->fixedvarsobjsum;
1230
1231 /* update dual bound of problem */
1232 if( !SCIPisEQ(scip, component->lastdualbound, newdualbound) )
1233 {
1235
1236 /* first finite dual bound: decrease inf counter and add dual bound to problem dualbound */
1237 if( SCIPisInfinity(scip, -component->lastdualbound) )
1238 {
1239 --problem->nlowerboundinf;
1240 problem->lowerbound += newdualbound;
1241 }
1242 /* increase problem dual bound by dual bound delta */
1243 else
1244 {
1245 problem->lowerbound += (newdualbound - component->lastdualbound);
1246 }
1247
1248 /* update problem dual bound if all problem components have a finite dual bound */
1249 if( problem->nlowerboundinf == 0 )
1250 {
1251 SCIPdebugMessage("component <%s>: dual bound increased from %16.9g to %16.9g, new dual bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1252 SCIPgetProbName(subscip), component->lastdualbound, newdualbound, problem->name,
1253 SCIPretransformObj(scip, problem->lowerbound),
1254 problem->nfeascomps == problem->ncomponents ?
1255 (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1256 MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ), SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1257 : SCIPinfinity(scip),
1258 problem->nfeascomps == problem->ncomponents ?
1259 SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1260 SCIP_CALL( SCIPupdateLocalLowerbound(scip, problem->lowerbound) );
1261 }
1262
1263 /* store dual bound of this call */
1264 component->lastdualbound = newdualbound;
1265 }
1266
1267 /* update primal solution of problem */
1268 if( sol != NULL && component->lastsolindex != SCIPsolGetIndex(sol) )
1269 {
1270 component->lastsolindex = SCIPsolGetIndex(sol);
1271
1272 if( SCIPsolGetHeur(sol) != NULL )
1274 else
1275 SCIPsolSetHeur(problem->bestsol, NULL);
1276
1277 /* increase counter for feasible problems if no solution was known before */
1278 if( SCIPisInfinity(scip, component->lastprimalbound) )
1279 ++(problem->nfeascomps);
1280
1281 /* update working best solution in problem */
1282 for( v = 0; v < component->nvars; ++v )
1283 {
1284 var = component->vars[v];
1285 subvar = component->subvars[v];
1286 assert(var != NULL);
1288
1289 if( subvar == NULL )
1290 continue;
1291
1292 SCIP_CALL( SCIPsetSolVal(scip, problem->bestsol, var, SCIPgetSolVal(subscip, sol, subvar)) );
1293 }
1294
1295 /* if we have a feasible solution for each component, add the working solution to the main problem */
1296 if( problem->nfeascomps == problem->ncomponents )
1297 {
1298 SCIP_Bool feasible;
1299#ifdef SCIP_MORE_DEBUG
1300 SCIP_CALL( SCIPcheckSol(scip, problem->bestsol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
1302#endif
1303 SCIP_CALL( SCIPaddSol(scip, problem->bestsol, &feasible) );
1304
1305 SCIPdebugMessage("component <%s>: primal bound decreased from %16.9g to %16.9g, new primal bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1306 SCIPgetProbName(subscip), component->lastprimalbound, SCIPgetPrimalbound(subscip), problem->name,
1307 SCIPgetSolOrigObj(scip, problem->bestsol),
1308 problem->nfeascomps == problem->ncomponents ?
1309 (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1310 MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ),SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1311 : SCIPinfinity(scip),
1312 problem->nfeascomps == problem->ncomponents ?
1313 SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1314 }
1315
1316 /* store primal bound of this call */
1317 component->lastprimalbound = SCIPgetPrimalbound(subscip) - component->fixedvarsobjsum;
1318 }
1319
1320 /* if the component was solved to optimality, we increase the respective counter and free the subscip */
1321 if( component->laststatus == SCIP_STATUS_OPTIMAL || component->laststatus == SCIP_STATUS_INFEASIBLE ||
1322 component->laststatus == SCIP_STATUS_UNBOUNDED || component->laststatus == SCIP_STATUS_INFORUNBD )
1323 {
1324 ++(problem->nsolvedcomps);
1325 component->solved = TRUE;
1326
1327 /* free working solution and component */
1328 SCIP_CALL( SCIPfreeSol(subscip, &component->workingsol) );
1329
1330 SCIP_CALL( SCIPfree(&subscip) );
1331 component->subscip = NULL;
1332 }
1333 }
1334
1335 return SCIP_OKAY;
1336}
1337
1338/** initialize subproblem structure */
1339static
1341 SCIP* scip, /**< SCIP data structure */
1342 PROBLEM** problem, /**< pointer to subproblem structure */
1343 SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1344 int ncomponents /**< number of independent components */
1345 )
1346{
1347 char name[SCIP_MAXSTRLEN];
1348 SCIP_VAR** vars;
1349 int nvars;
1350 int v;
1351
1352 assert(scip != NULL);
1353 assert(problem != NULL);
1354
1357
1358 SCIP_CALL( SCIPallocBlockMemory(scip, problem) );
1359 assert(*problem != NULL);
1360
1361 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->components, ncomponents) );
1362
1363 /* create a priority queue for the components: we need exactly ncomponents slots in the queue so it should never be
1364 * resized
1365 */
1366 SCIP_CALL( SCIPpqueueCreate(&(*problem)->compqueue, ncomponents, 1.2, componentSort, NULL) );
1367
1368 (*problem)->scip = scip;
1369 (*problem)->lowerbound = fixedvarsobjsum;
1370 (*problem)->fixedvarsobjsum = fixedvarsobjsum;
1371 (*problem)->ncomponents = 0;
1372 (*problem)->componentssize = ncomponents;
1373 (*problem)->nlowerboundinf = ncomponents;
1374 (*problem)->nfeascomps = 0;
1375 (*problem)->nsolvedcomps = 0;
1376
1377 if( SCIPgetDepth(scip) == 0 )
1379 else
1381
1382 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name)+1) );
1383
1384 SCIP_CALL( SCIPcreateSol(scip, &(*problem)->bestsol, NULL) );
1385
1386 for( v = 0; v < nvars; v++ )
1387 {
1389 {
1390 SCIP_CALL( SCIPsetSolVal(scip, (*problem)->bestsol, vars[v],
1392 }
1393 }
1394
1395 SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name);
1396
1397 return SCIP_OKAY;
1398}
1399
1400/** free subproblem structure */
1401static
1403 PROBLEM** problem /**< pointer to problem to free */
1404 )
1405{
1406 SCIP* scip;
1407 int c;
1408
1409 assert(problem != NULL);
1410 assert(*problem != NULL);
1411
1412 scip = (*problem)->scip;
1413 assert(scip != NULL);
1414
1415 /* free best solution */
1416 if( (*problem)->bestsol != NULL )
1417 {
1418 SCIP_CALL( SCIPfreeSol(scip, &(*problem)->bestsol) );
1419 }
1420
1421 /* free all components */
1422 for( c = (*problem)->ncomponents - 1; c >= 0; --c )
1423 {
1424 SCIP_CALL( freeComponent(&(*problem)->components[c]) );
1425 }
1426 if( (*problem)->components != NULL )
1427 {
1428 SCIPfreeBlockMemoryArray(scip, &(*problem)->components, (*problem)->componentssize);
1429 }
1430
1431 /* free priority queue */
1432 SCIPpqueueFree(&(*problem)->compqueue);
1433
1434 /* free problem name */
1435 SCIPfreeMemoryArray(scip, &(*problem)->name);
1436
1437 /* free PROBLEM struct and set the pointer to NULL */
1438 SCIPfreeBlockMemory(scip, problem);
1439 *problem = NULL;
1440
1441 return SCIP_OKAY;
1442}
1443
1444/** creates and captures a components constraint */
1445static
1447 SCIP* scip, /**< SCIP data structure */
1448 SCIP_CONS** cons, /**< pointer to hold the created constraint */
1449 const char* name, /**< name of constraint */
1450 PROBLEM* problem /**< problem to be stored in the constraint */
1451 )
1452{
1453 SCIP_CONSHDLR* conshdlr;
1454
1455 /* find the samediff constraint handler */
1456 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1457 if( conshdlr == NULL )
1458 {
1459 SCIPerrorMessage("components constraint handler not found\n");
1460 return SCIP_PLUGINNOTFOUND;
1461 }
1462
1463 /* create constraint */
1464 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, (SCIP_CONSDATA*)problem,
1466 TRUE, FALSE, FALSE, FALSE, TRUE) );
1467
1468 return SCIP_OKAY;
1469}
1470
1471
1472/** sort the components by size and sort vars and conss arrays by component numbers */
1473static
1475 SCIP* scip, /**< SCIP data structure */
1476 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1477 SCIP_DIGRAPH* digraph, /**< directed graph */
1478 SCIP_CONS** conss, /**< constraints */
1479 SCIP_VAR** vars, /**< variables */
1480 int* varcomponent, /**< component numbers for the variables */
1481 int* conscomponent, /**< array to store component numbers for the constraints */
1482 int nconss, /**< number of constraints */
1483 int nvars, /**< number of variables */
1484 int* firstvaridxpercons, /**< array with index of first variable in vars array for each constraint */
1485 int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1486 int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1487 )
1488{
1489 SCIP_Real* compsize;
1490 int* permu;
1491 int ncomponents;
1492 int nbinvars;
1493 int nintvars;
1494 int ndiscvars;
1495 int ncontvars;
1496 int minsize;
1497 int v;
1498 int c;
1499
1500 assert(scip != NULL);
1501 assert(conshdlrdata != NULL);
1502 assert(digraph != NULL);
1503 assert(conss != NULL);
1504 assert(vars != NULL);
1506
1507 /* compute minimum size of components to solve individually */
1508 minsize = getMinsize(scip, conshdlrdata);
1509
1510 ncomponents = SCIPdigraphGetNComponents(digraph);
1511 *ncompsminsize = 0;
1512 *ncompsmaxsize = 0;
1513
1514 /* We want to sort the components in increasing complexity (number of discrete variables,
1515 * integer weighted with factor intfactor, continuous used as tie-breaker).
1516 * Therefore, we now get the variables for each component, count the different variable types
1517 * and compute a size as described above. Then, we rename the components
1518 * such that for i < j, component i has no higher complexity than component j.
1519 */
1520 SCIP_CALL( SCIPallocBufferArray(scip, &compsize, ncomponents) );
1521 SCIP_CALL( SCIPallocBufferArray(scip, &permu, ncomponents) );
1522
1523 /* get number of variables in the components */
1524 for( c = 0; c < ncomponents; ++c )
1525 {
1526 int* cvars;
1527 int ncvars;
1528
1530 permu[c] = c;
1531 nbinvars = 0;
1532 nintvars = 0;
1533
1534 for( v = 0; v < ncvars; ++v )
1535 {
1536 /* check whether variable is of binary or integer type */
1537 if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_BINARY )
1538 nbinvars++;
1539 else if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_INTEGER )
1540 nintvars++;
1541 }
1542 ncontvars = ncvars - nintvars - nbinvars;
1543 ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars);
1544 compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/nvars));
1545
1546 /* component fulfills the maxsize requirement */
1547 if( ndiscvars <= conshdlrdata->maxintvars )
1548 ++(*ncompsmaxsize);
1549
1550 /* component fulfills the minsize requirement */
1551 if( ncvars >= minsize )
1552 ++(*ncompsminsize);
1553 }
1554
1555 /* get permutation of component numbers such that the size of the components is increasing */
1556 SCIPsortRealInt(compsize, permu, ncomponents);
1557
1558 /* now, we need the reverse direction, i.e., for each component number, we store its new number
1559 * such that the components are sorted; for this, we abuse the conscomponent array
1560 */
1561 for( c = 0; c < ncomponents; ++c )
1562 conscomponent[permu[c]] = c;
1563
1564 /* for each variable, replace the old component number by the new one */
1565 for( c = 0; c < nvars; ++c )
1567
1570
1571 /* do the mapping from calculated components per variable to corresponding
1572 * constraints and sort the component-arrays for faster finding the
1573 * actual variables and constraints belonging to one component
1574 */
1575 for( c = 0; c < nconss; c++ )
1577
1579 SCIPsortIntPtr(conscomponent, (void**)conss, nconss);
1580
1581 return SCIP_OKAY;
1582}
1583
1584
1585
1586/** create PROBLEM structure for the current node and split it into components */
1587static
1589 SCIP* scip, /**< SCIP data structure */
1590 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1591 SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */
1592 SCIP_VAR** sortedvars, /**< array of unfixed variables sorted by components */
1593 SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by components */
1594 int* compstartsvars, /**< start points of components in sortedvars array */
1595 int* compstartsconss, /**< start points of components in sortedconss array */
1596 int ncomponents, /**< number of components */
1597 PROBLEM** problem /**< pointer to store problem structure */
1598 )
1599{
1601 SCIP_HASHMAP* consmap;
1602 SCIP_HASHMAP* varmap;
1605 SCIP_Bool success = TRUE;
1606 int nfixedvars = SCIPgetNVars(scip) - compstartsvars[ncomponents];
1607 int ncompconss;
1608 int comp;
1609
1610 /* init subproblem data structure */
1611 SCIP_CALL( initProblem(scip, problem, fixedvarsobjsum, ncomponents) );
1612 assert((*problem)->components != NULL);
1613
1614 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
1615 SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), compstartsconss[ncomponents]) );
1616
1617 /* loop over all components */
1618 for( comp = 0; comp < ncomponents; comp++ )
1619 {
1620 SCIP_CALL( initComponent(*problem) );
1621 assert((*problem)->ncomponents == comp+1);
1622
1623 component = &(*problem)->components[comp];
1624
1625 /* get component variables and store them in component structure */
1626 compvars = &(sortedvars[compstartsvars[comp]]);
1630 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), component->nvars + nfixedvars) );
1631
1632 /* get component constraints */
1635
1636#ifdef DETAILED_OUTPUT
1637 /* print details about the component including its size */
1638 if( component->nvars > 1 && ncompconss > 1 )
1639 {
1640 int nbinvars = 0;
1641 int nintvars = 0;
1642 int ncontvars = 0;
1643 int i;
1644
1645 for( i = 0; i < component->nvars; ++i )
1646 {
1648 ++nbinvars;
1650 ++nintvars;
1651 else
1652 ++ncontvars;
1653 }
1654 SCIPdebugMsg(scip, "component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n",
1655 comp, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth,
1656 component->nvars, nbinvars, nintvars, ncontvars, ncompconss);
1657 }
1658#endif
1659 assert(ncompconss > 0 || component->nvars == 1);
1660
1661 SCIPdebugMsg(scip, "build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n",
1662 component->number, (*problem)->name, component->nvars, ncompconss);
1663
1664#ifndef NDEBUG
1665 {
1666 int i;
1667 for( i = 0; i < component->nvars; ++i )
1669 }
1670#endif
1671
1672 /* build subscip for component */
1673 SCIP_CALL( componentCreateSubscip(component, conshdlrdata, varmap, consmap, compconss, ncompconss, &success) );
1674
1675 if( success )
1676 {
1678
1679 /* add component to the priority queue of the problem structure */
1680 SCIP_CALL( SCIPpqueueInsert((*problem)->compqueue, component) );
1681 }
1682
1683 SCIPhashmapFree(&varmap);
1684
1685 if( !success )
1686 break;
1687 }
1688
1689 SCIPhashmapFree(&consmap);
1690
1691 if( !success )
1692 {
1693 /* free subproblem data structure since not all component could be copied */
1694 SCIP_CALL( freeProblem(problem) );
1695 }
1696
1697 return SCIP_OKAY;
1698}
1699
1700/** continue solving a problem */
1701static
1703 PROBLEM* problem, /**< problem structure */
1704 SCIP_RESULT* result /**< result pointer for the problem solve */
1705 )
1706{
1709
1710 assert(problem != NULL);
1711
1713
1714 component = (COMPONENT*)SCIPpqueueRemove(problem->compqueue);
1715
1716 /* continue solving the component */
1717 SCIP_CALL( solveComponent(component, SCIPpqueueNElems(problem->compqueue) == 0, &subscipresult) );
1718
1719 /* if infeasibility or unboundedness was detected, return this */
1721 {
1723 }
1724 /* the component was not solved to optimality, so we need to re-insert it in the components queue */
1725 else if( !component->solved )
1726 {
1727 SCIP_CALL( SCIPpqueueInsert(problem->compqueue, component) );
1729 }
1730 /* no unsolved components are left, so this problem has be completely evaluated and the node can be pruned */
1731 else if( SCIPpqueueNElems(problem->compqueue) == 0 )
1733 /* there are some unsolved components left, so we delay this node */
1734 else
1736
1737 return SCIP_OKAY;
1738}
1739
1740/*
1741 * Local methods
1742 */
1743
1744/** loop over constraints, get active variables and fill directed graph */
1745static
1747 SCIP* scip, /**< SCIP data structure */
1748 SCIP_DIGRAPH* digraph, /**< directed graph */
1749 SCIP_CONS** conss, /**< constraints */
1750 int nconss, /**< number of constraints */
1751 int* unfixedvarpos, /**< mapping from variable problem index to unfixed var index */
1752 int nunfixedvars, /**< number of unfixed variables */
1753 int* firstvaridxpercons, /**< array to store for each constraint the index in the local vars array
1754 * of the first variable of the constraint */
1755 SCIP_Bool* success /**< flag indicating successful directed graph filling */
1756 )
1757{
1758 SCIP_VAR** consvars;
1759 int requiredsize;
1760 int nconsvars;
1761 int nvars;
1762 int idx1;
1763 int idx2;
1764 int c;
1765 int v;
1766
1767 assert(scip != NULL);
1768 assert(digraph != NULL);
1769 assert(conss != NULL);
1771 assert(success != NULL);
1772
1773 *success = TRUE;
1774
1775 nconsvars = 0;
1776 requiredsize = 0;
1778
1779 /* allocate buffer for storing active variables per constraint; size = nvars ensures that it will be big enough */
1780 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
1781
1782 for( c = 0; c < nconss; ++c )
1783 {
1784 /* check for reached timelimit */
1785 if( (c % 1000 == 0) && SCIPisStopped(scip) )
1786 {
1787 *success = FALSE;
1788 break;
1789 }
1790
1791 /* get number of variables for this constraint */
1792 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nconsvars, success) );
1793
1794 if( !(*success) )
1795 break;
1796
1797 /* reallocate consvars array, if needed */
1798 if( nconsvars > nvars )
1799 {
1800 nvars = nconsvars;
1802 }
1803
1804#ifndef NDEBUG
1805 /* clearing variables array to check for consistency */
1806 if( nconsvars == nvars )
1807 {
1808 BMSclearMemoryArray(consvars, nconsvars);
1809 }
1810 else
1811 {
1812 assert(nconsvars < nvars);
1813 BMSclearMemoryArray(consvars, nconsvars + 1);
1814 }
1815#endif
1816
1817 /* get variables for this constraint */
1818 SCIP_CALL( SCIPgetConsVars(scip, conss[c], consvars, nvars, success) );
1819
1820 if( !(*success) )
1821 {
1822#ifndef NDEBUG
1823 /* it looks strange if returning the number of variables was successful but not returning the variables */
1824 SCIPwarningMessage(scip, "constraint <%s> returned number of variables but returning variables failed\n", SCIPconsGetName(conss[c]));
1825#endif
1826 break;
1827 }
1828
1829#ifndef NDEBUG
1830 /* check if returned variables are consistent with the number of variables that were returned */
1831 for( v = nconsvars - 1; v >= 0; --v )
1832 assert(consvars[v] != NULL);
1833 if( nconsvars < nvars )
1834 assert(consvars[nconsvars] == NULL);
1835#endif
1836
1837 /* transform given variables to active variables */
1838 SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nconsvars, nvars, &requiredsize) );
1840
1841 firstvaridxpercons[c] = -1;
1842
1843 /* store the index of the first unfixed variable and add edges to the directed graph */
1844 if( nconsvars > 0 )
1845 {
1846 v = 0;
1847 idx1 = -1;
1848
1849 /* go through variables until the first unfixed one is reached (which has unfixedvarpos >= 0) */
1850 while( idx1 == -1 && v < nconsvars )
1851 {
1852 idx1 = SCIPvarGetProbindex(consvars[v]);
1853 assert(idx1 >= 0);
1856 ++v;
1857 }
1858
1859 if( idx1 >= 0 )
1860 {
1861 /* save index of the first variable for later component assignment */
1863
1864 /* create sparse directed graph; sparse means to add only those edges necessary for component calculation,
1865 * i.e., add edges from the first variable to all others
1866 */
1867 for(; v < nconsvars; ++v )
1868 {
1869 idx2 = SCIPvarGetProbindex(consvars[v]);
1870 assert(idx2 >= 0);
1873
1874 /* variable is fixed */
1875 if( idx2 < 0 )
1876 continue;
1877
1878 /* we add only one directed edge, because the other direction is automatically added for component computation */
1880 }
1881 }
1882 }
1883 }
1884
1885 SCIPfreeBufferArray(scip, &consvars);
1886
1887 return SCIP_OKAY;
1888}
1889
1890/** search for components in the problem */
1891static
1893 SCIP* scip, /**< SCIP main data structure */
1894 SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */
1895 SCIP_Real* fixedvarsobjsum, /**< objective contribution of all locally fixed variables, or NULL if
1896 * fixed variables should not be disregarded */
1897 SCIP_VAR** sortedvars, /**< array to store variables sorted by components, should have enough size
1898 * for all variables */
1899 SCIP_CONS** sortedconss, /**< array to store (checked) constraints sorted by components, should have
1900 * enough size for all constraints */
1901 int* compstartsvars, /**< start points of components in sortedvars array */
1902 int* compstartsconss, /**< start points of components in sortedconss array */
1903 int* nsortedvars, /**< pointer to store the number of variables belonging to any component */
1904 int* nsortedconss, /**< pointer to store the number of (checked) constraints in components */
1905 int* ncomponents, /**< pointer to store the number of components */
1906 int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */
1907 int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */
1908
1909 )
1910{
1912 SCIP_VAR** vars;
1913 SCIP_Bool success;
1914 int ntmpconss;
1915 int nvars;
1916 int c;
1917
1918 assert(scip != NULL);
1919 assert(conshdlrdata != NULL);
1920 assert(sortedvars != NULL);
1924 assert(nsortedvars != NULL);
1926 assert(ncomponents != NULL);
1929
1932
1933 if( fixedvarsobjsum != NULL )
1934 *fixedvarsobjsum = 0.0;
1935
1936 *ncomponents = 0;
1937 *ncompsminsize = 0;
1938 *ncompsmaxsize = 0;
1939
1940 /* collect checked constraints for component detection */
1943 (*nsortedconss) = 0;
1944 for( c = 0; c < ntmpconss; c++ )
1945 {
1946 sortedconss[(*nsortedconss)] = tmpconss[c];
1947 (*nsortedconss)++;
1948 }
1949
1950 if( nvars > 1 && *nsortedconss > 1 )
1951 {
1952 int* unfixedvarpos;
1953 int* firstvaridxpercons;
1954 int* varlocks;
1955 int nunfixedvars = 0;
1956 int v;
1957
1958 /* arrays for storing the first variable in each constraint (for later component assignment), the number of
1959 * variable locks, and the positions in the sortedvars array for all unfixed variables
1960 */
1964
1965 /* count number of varlocks for each variable (up + down locks) and multiply it by 2;
1966 * that value is used as an estimate of the number of arcs incident to the variable's node in the digraph
1967 * to be safe, we double this value
1968 */
1969 for( v = 0; v < nvars; ++v )
1970 {
1971 /* variable is not fixed or we do not want to disregard fixed variables */
1972 if( (fixedvarsobjsum == NULL) || SCIPisLT(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1973 {
1974 assert(nunfixedvars <= v);
1975 sortedvars[nunfixedvars] = vars[v];
1979 ++nunfixedvars;
1980 }
1981 /* variable is fixed; update the objective sum of all fixed variables */
1982 else
1983 {
1984 unfixedvarpos[v] = -1;
1985 (*fixedvarsobjsum) += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
1986 }
1987 }
1988 *nsortedvars = nunfixedvars;
1989
1990 if( nunfixedvars > 0 )
1991 {
1993
1994 /* create and fill directed graph */
1998
1999 if( success )
2000 {
2001 int* varcomponent;
2002 int* conscomponent;
2003
2006
2007 /* compute independent components */
2009
2010 if( *ncomponents > 1 )
2011 {
2012 int nconss = *nsortedconss;
2013 int i;
2014
2015 nvars = *nsortedvars;
2016
2018 "cons components found %d undirected components at node %lld, depth %d (%d)\n",
2019 *ncomponents, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2020
2021 /* sort components by size and sort variables and constraints by component number */
2022 SCIP_CALL( sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars,
2024
2025 /* determine start indices of components in sortedvars and sortedconss array */
2026 i = 0;
2027
2028 while( i < nconss && conscomponent[i] == -1 )
2029 ++i;
2030
2031 for( c = 0; c < *ncomponents + 1; ++c )
2032 {
2033 assert(i == nconss || conscomponent[i] >= c);
2034
2035 compstartsconss[c] = i;
2036
2037 while( i < nconss && conscomponent[i] == c )
2038 ++i;
2039 }
2040
2041 for( c = 0, i = 0; c < *ncomponents + 1; ++c )
2042 {
2043 assert(i == nvars || varcomponent[i] >= c);
2044
2045 compstartsvars[c] = i;
2046
2047 while( i < nvars && varcomponent[i] == c )
2048 ++i;
2049 }
2050
2051#ifndef NDEBUG
2052 for( c = 0; c < *ncomponents; ++c )
2053 {
2054 for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i )
2055 assert(conscomponent[i] == c);
2056 for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i )
2057 assert(varcomponent[i] == c);
2058 }
2059#endif
2060 }
2061
2064 }
2065
2067 }
2068
2072 }
2073
2074 return SCIP_OKAY;
2075}
2076
2077
2078/*
2079 * Callback methods of constraint handler
2080 */
2081
2082/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2083static
2085{ /*lint --e{715}*/
2086 assert(scip != NULL);
2087 assert(conshdlr != NULL);
2089
2090 /* call inclusion method of constraint handler */
2092
2093 *valid = TRUE;
2094
2095 return SCIP_OKAY;
2096}
2097
2098/** destructor of constraint handler to free user data (called when SCIP is exiting) */
2099static
2101{ /*lint --e{715}*/
2102 SCIP_CONSHDLRDATA* conshdlrdata;
2103
2104 /* free constraint handler data */
2105 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2106 assert(conshdlrdata != NULL);
2107
2108 SCIPfreeBlockMemory(scip, &conshdlrdata);
2109 SCIPconshdlrSetData(conshdlr, NULL);
2110
2111 return SCIP_OKAY;
2112}
2113
2114/** domain propagation method of constraint handler */
2115static
2117{ /*lint --e{715}*/
2118 PROBLEM* problem;
2119 SCIP_CONSHDLRDATA* conshdlrdata;
2120 SCIP_Longint nodelimit;
2121
2122 assert(conshdlr != NULL);
2124 assert(result != NULL);
2125 assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2126 assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2127
2128 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2129 assert(conshdlrdata != NULL);
2130
2132
2133 /* do not try to detect independent components if the depth is too high */
2134 if( SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth
2135 && SCIPconshdlrGetNActiveConss(conshdlr) == 0 )
2136 return SCIP_OKAY;
2137
2138 /* don't run in probing or in repropagation */
2140 return SCIP_OKAY;
2141
2142 /* do not run, if not all variables are explicitly known */
2143 if( SCIPgetNActivePricers(scip) > 0 )
2144 return SCIP_OKAY;
2145
2146 /* we do not want to run, if there are no variables left */
2147 if( SCIPgetNVars(scip) == 0 )
2148 return SCIP_OKAY;
2149
2150 /* check for a reached timelimit */
2151 if( SCIPisStopped(scip) )
2152 return SCIP_OKAY;
2153
2154 /* the components constraint handler does kind of dual reductions */
2156 return SCIP_OKAY;
2157
2158 problem = NULL;
2160
2161 /* the current node already has a components constraint storing a problem split into individual components */
2162 if( SCIPconshdlrGetNActiveConss(conshdlr) >= 1 )
2163 {
2164 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 1);
2165
2166 problem = (PROBLEM*)SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]);
2167 }
2168 /* no components constraint at the current node, search for components */
2169 else
2170 {
2171 SCIP_Real fixedvarsobjsum;
2172 SCIP_VAR** sortedvars;
2174 int* compstartsvars;
2175 int* compstartsconss;
2176 int nsortedvars;
2177 int nsortedconss;
2178 int ncomponents;
2179 int ncompsminsize;
2180 int ncompsmaxsize;
2181
2182 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2183
2184 /* allocate memory for sorted components */
2189
2190 /* search for components */
2191 SCIP_CALL( findComponents(scip, conshdlrdata, &fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2192 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2193
2194 if( ncompsminsize > 1 )
2195 {
2196 SCIP_CONS* cons;
2197
2198 SCIPdebugMsg(scip, "found %d components (%d fulfulling the minsize requirement) at node %lld at depth %d (%d)\n",
2200 SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2201
2202 /* if there are components with size smaller than the limit, we merge them with the smallest component */
2203 if( ncomponents > ncompsminsize )
2204 {
2205 int minsize;
2206 int size;
2207 int c;
2208 int m = 0;
2209
2210 /* compute minimum size of components to solve individually */
2211 minsize = getMinsize(scip, conshdlrdata);
2212
2213 for( c = 0; c < ncomponents; ++c )
2214 {
2215 size = compstartsvars[c+1] - compstartsvars[c];
2216
2217 if( size >= minsize )
2218 {
2219 ++m;
2222 }
2223 /* the last component is too small */
2224 else if( c == ncomponents - 1 )
2225 {
2226 assert(m == ncompsminsize);
2229 }
2230 }
2231 assert(m == ncompsminsize);
2232 assert(compstartsvars[m] == nsortedvars);
2234
2235 ncomponents = m;
2236 }
2237
2238 SCIP_CALL( createAndSplitProblem(scip, conshdlrdata, fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2239 compstartsconss, ncomponents, &problem) );
2240
2241 /* if the problem is not NULL, copying worked fine */
2242 if( problem != NULL )
2243 {
2244 SCIP_CALL( createConsComponents(scip, &cons, problem->name, problem) );
2246 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2247 }
2248 }
2249
2253 SCIPfreeBufferArray(scip, &sortedvars);
2254 }
2255
2256 /* (continue to) solve the problem
2257 *
2258 * If the problem was not solved to optimality yet, the result code is set to SCIP_DELAYNODE, so that after the
2259 * propagation is finished, the node is put back into the queue of open nodes and solving the components of the
2260 * problem will be continued when the node is focused and propagated the next time.
2261 * However, if we are at the root node, we continue solving the problem until it is solved or some limit is reached
2262 * since there are no other nodes to process and we want to avoid calling other propagation methods or heuristics
2263 * again and again
2264 */
2265 SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) );
2266 if( nodelimit == -1 )
2267 nodelimit = SCIP_LONGINT_MAX;
2268
2269 do
2270 {
2271 if( problem != NULL )
2272 {
2273 SCIP_CALL( solveProblem(problem, result) );
2274 }
2275 } while( *result == SCIP_DELAYNODE && SCIPgetDepth(scip) == 0 && !SCIPisStopped(scip) && SCIPgetNNodes(scip) < nodelimit);
2276
2277 return SCIP_OKAY;
2278}
2279
2280/** presolving method of constraint handler */
2281static
2283{ /*lint --e{715}*/
2284 SCIP_CONSHDLRDATA* conshdlrdata;
2285 SCIP_VAR** sortedvars;
2287 int* compstartsvars;
2288 int* compstartsconss;
2289 int nsortedvars;
2290 int nsortedconss;
2291 int ncomponents;
2292 int ncompsminsize;
2293 int ncompsmaxsize;
2294 int nvars;
2295
2296 assert(conshdlr != NULL);
2298 assert(result != NULL);
2299 assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2300 assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2301
2302 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2303 assert(conshdlrdata != NULL);
2304
2306
2308 return SCIP_OKAY;
2309
2310 /* do not run, if not all variables are explicitly known */
2311 if( SCIPgetNActivePricers(scip) > 0 )
2312 return SCIP_OKAY;
2313
2315
2316 /* we do not want to run, if there are no variables left */
2317 if( nvars == 0 )
2318 return SCIP_OKAY;
2319
2320 /* only call the components presolving, if presolving would be stopped otherwise */
2322 return SCIP_OKAY;
2323
2324 /* the components constraint handler does kind of dual reductions */
2326 return SCIP_OKAY;
2327
2328 /* check for a reached timelimit */
2329 if( SCIPisStopped(scip) )
2330 return SCIP_OKAY;
2331
2333
2334 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2335
2336 /* allocate memory for sorted components */
2341
2342 /* search for components */
2343 SCIP_CALL( findComponents(scip, conshdlrdata, NULL, sortedvars, sortedconss, compstartsvars,
2344 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2345
2346 if( ncompsmaxsize > 0 )
2347 {
2348 char name[SCIP_MAXSTRLEN];
2349 SCIP* subscip;
2350 SCIP_HASHMAP* consmap;
2351 SCIP_HASHMAP* varmap;
2353 SCIP_VAR** subvars;
2355 SCIP_Bool success;
2356 SCIP_Bool solved;
2357 int nsolved = 0;
2358 int ncompvars;
2359 int ncompconss;
2360 int comp;
2361
2362 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",
2364
2365 /* build subscip */
2366 SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2367
2368 if( subscip == NULL )
2369 goto TERMINATE;
2370
2371 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/usesmalltables", TRUE) );
2372 SCIP_CALL( SCIPsetIntParam(subscip, "constraints/" CONSHDLR_NAME "/propfreq", -1) );
2373
2374 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
2376
2377 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nsortedvars) );
2378
2379 /* loop over all components */
2380 for( comp = 0; comp < ncompsmaxsize && !SCIPisStopped(scip); comp++ )
2381 {
2382#ifdef WITH_DEBUG_SOLUTION
2383 if( SCIPgetStage(subscip) > SCIP_STAGE_INIT )
2384 {
2385 SCIP_CALL( SCIPfree(&subscip) );
2386 SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2387 }
2388#endif
2389 /* get component variables */
2390 compvars = &(sortedvars[compstartsvars[comp]]);
2392
2393 /* get component constraints */
2396
2397 /* if we have an unlocked variable, let duality fixing do the job! */
2398 if( ncompconss == 0 )
2399 {
2400 assert(ncompvars == 1);
2401 continue;
2402 }
2403
2405#ifdef DETAILED_OUTPUT
2406 {
2407 int nbinvars = 0;
2408 int nintvars = 0;
2409 int ncontvars = 0;
2410 int i;
2411
2412 for( i = 0; i < ncompvars; ++i )
2413 {
2415 ++nbinvars;
2417 ++nintvars;
2418 else
2419 ++ncontvars;
2420 }
2421 SCIPdebugMsg(scip, "solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n",
2422 comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss);
2423 }
2424#endif
2425#ifndef NDEBUG
2426 {
2427 int i;
2428 for( i = 0; i < ncompvars; ++i )
2430 }
2431#endif
2432
2433 /* get name of the original problem and add "comp_nr" */
2434 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), comp);
2435
2436 SCIP_CALL( copyToSubscip(scip, subscip, name, compvars, subvars,
2437 compconss, varmap, consmap, ncompvars, ncompconss, &success) );
2438
2439 if( !success )
2440 {
2441 SCIPhashmapFree(&varmap);
2442 continue;
2443 }
2444
2445 /* set up debug solution */
2446#ifdef WITH_DEBUG_SOLUTION
2448 {
2450 SCIP_Real val;
2451 int i;
2452
2454
2455 /* set solution values in the debug solution if it is available */
2456 if( debugsol != NULL )
2457 {
2458 SCIPdebugSolEnable(subscip);
2459
2460 for( i = 0; i < ncompvars; ++i )
2461 {
2462 if( subvars[i] != NULL )
2463 {
2465 SCIP_CALL( SCIPdebugAddSolVal(subscip, subvars[i], val) );
2466 }
2467 }
2468 }
2469 }
2470#endif
2471
2472 /* solve the subproblem and evaluate the result, i.e. apply fixings of variables and remove constraints */
2473 SCIP_CALL( solveAndEvalSubscip(scip, conshdlrdata, subscip, compvars, subvars, compconss,
2474 ncompvars, ncompconss, ndelconss, nfixedvars, nchgbds, result, &solved) );
2475
2476 /* free variable hash map */
2477 SCIPhashmapFree(&varmap);
2478
2479 if( solved )
2480 ++nsolved;
2481
2482 /* if the component is unbounded or infeasible, this holds for the complete problem as well */
2483 if( *result == SCIP_UNBOUNDED || *result == SCIP_CUTOFF )
2484 break;
2485 /* if there is only one component left, let's solve this in the main SCIP */
2486 else if( nsolved == ncomponents - 1 )
2487 break;
2488 }
2489
2490 SCIPfreeBufferArray(scip, &subvars);
2491 SCIPhashmapFree(&consmap);
2492
2493 SCIP_CALL( SCIPfree(&subscip) );
2494 }
2495
2496 TERMINATE:
2500 SCIPfreeBufferArray(scip, &sortedvars);
2501
2502 return SCIP_OKAY;
2503}
2504
2505/** frees specific constraint data */
2506static
2508{ /*lint --e{715}*/
2509 assert(conshdlr != NULL);
2511 assert(consdata != NULL);
2512 assert(*consdata != NULL);
2513
2514 SCIP_CALL( freeProblem((PROBLEM**) consdata) );
2515
2516 return SCIP_OKAY;
2517}
2518
2519/** constraint enforcing method of constraint handler for relaxation solutions */
2520static
2522{ /*lint --e{715}*/
2523 assert(result != NULL );
2524
2525 /* no enforcement is performed, but the callback is needed for all constraint handlers with needscons = FALSE */
2527
2528 return SCIP_OKAY;
2529}
2530
2531/** variable rounding lock method of constraint handler */
2532static
2534{ /*lint --e{715}*/
2535 return SCIP_OKAY;
2536}
2537
2538#ifndef NDEBUG
2539/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
2540static
2542{ /*lint --e{715}*/
2543 assert(nconss == 0);
2544
2545 return SCIP_OKAY;
2546}
2547#endif
2548
2549#define consEnfolpComponents NULL
2550#define consEnfopsComponents NULL
2551#define consCheckComponents NULL
2552
2553/** creates the components constraint handler and includes it in SCIP */
2555 SCIP* scip /**< SCIP data structure */
2556 )
2557{
2558 SCIP_CONSHDLRDATA* conshdlrdata;
2559 SCIP_CONSHDLR* conshdlr;
2560
2561 /* create components propagator data */
2562 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2563 conshdlrdata->subscipdepth = 0;
2564
2565 /* include constraint handler */
2569 conshdlrdata) );
2570 assert(conshdlr != NULL);
2571
2576
2579#ifndef NDEBUG
2581#endif
2584
2586 "constraints/" CONSHDLR_NAME "/maxdepth",
2587 "maximum depth of a node to run components detection (-1: disable component detection during solving)",
2588 &conshdlrdata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2590 "constraints/" CONSHDLR_NAME "/maxintvars",
2591 "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)",
2592 &conshdlrdata->maxintvars, TRUE, DEFAULT_MAXINTVARS, -1, INT_MAX, NULL, NULL) );
2594 "constraints/" CONSHDLR_NAME "/minsize",
2595 "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound",
2596 &conshdlrdata->minsize, TRUE, DEFAULT_MINSIZE, 0, INT_MAX, NULL, NULL) );
2598 "constraints/" CONSHDLR_NAME "/minrelsize",
2599 "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound",
2600 &conshdlrdata->minrelsize, TRUE, DEFAULT_MINRELSIZE, 0.0, 1.0, NULL, NULL) );
2602 "constraints/" CONSHDLR_NAME "/nodelimit",
2603 "maximum number of nodes to be solved in subproblems during presolving",
2604 &conshdlrdata->nodelimit, FALSE, DEFAULT_NODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
2606 "constraints/" CONSHDLR_NAME "/intfactor",
2607 "the weight of an integer variable compared to binary variables",
2608 &conshdlrdata->intfactor, FALSE, DEFAULT_INTFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2610 "constraints/" CONSHDLR_NAME "/feastolfactor",
2611 "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0",
2612 &conshdlrdata->feastolfactor, TRUE, DEFAULT_FEASTOLFACTOR, 0.0, 1000000.0, NULL, NULL) );
2613
2614 return SCIP_OKAY;
2615}
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 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:7444
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
#define SCIPdebugMessage
Definition pub_message.h:96
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