Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for handling independent components

Author
Gerald Gamrath

This constraint handler looks for independent components.

Definition in file cons_components.c.

#include "blockmemshell/memory.h"
#include "scip/cons_components.h"
#include "scip/debug.h"
#include "scip/pub_cons.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sol.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_datastructures.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  Component
 

Macros

#define CONSHDLR_NAME   "components"
 
#define CONSHDLR_DESC   "independent components constraint handler"
 
#define CONSHDLR_ENFOPRIORITY   0
 
#define CONSHDLR_CHECKPRIORITY   -9999999
 
#define CONSHDLR_EAGERFREQ   -1
 
#define CONSHDLR_NEEDSCONS   FALSE
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYPROP   TRUE
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FINAL
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define DEFAULT_MAXDEPTH   -1
 
#define DEFAULT_MAXINTVARS   500
 
#define DEFAULT_MINSIZE   50
 
#define DEFAULT_MINRELSIZE   0.1
 
#define DEFAULT_NODELIMIT   10000LL
 
#define DEFAULT_INTFACTOR   1.0
 
#define DEFAULT_FEASTOLFACTOR   1.0
 
#define consEnfolpComponents   NULL
 
#define consEnfopsComponents   NULL
 
#define consCheckComponents   NULL
 

Typedefs

typedef struct Problem PROBLEM
 
typedef struct Component COMPONENT
 

Functions

static SCIP_DECL_SORTPTRCOMP (componentSort)
 
static int getMinsize (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE initComponent (PROBLEM *problem)
 
static SCIP_RETCODE freeComponent (COMPONENT *component)
 
static SCIP_RETCODE componentSetupWorkingSol (COMPONENT *component, SCIP_HASHMAP *varmap)
 
static SCIP_RETCODE createSubscip (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP **subscip)
 
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)
 
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 solveSubscip (SCIP *scip, SCIP *subscip, SCIP_Longint nodelimit, SCIP_Real gaplimit)
 
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 solveComponent (COMPONENT *component, SCIP_Bool lastcomponent, SCIP_RESULT *result)
 
static SCIP_RETCODE initProblem (SCIP *scip, PROBLEM **problem, SCIP_Real fixedvarsobjsum, int ncomponents)
 
static SCIP_RETCODE freeProblem (PROBLEM **problem)
 
static SCIP_RETCODE createConsComponents (SCIP *scip, SCIP_CONS **cons, const char *name, PROBLEM *problem)
 
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)
 
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 solveProblem (PROBLEM *problem, SCIP_RESULT *result)
 
static SCIP_RETCODE fillDigraph (SCIP *scip, SCIP_DIGRAPH *digraph, SCIP_CONS **conss, int nconss, int *unfixedvarpos, int nunfixedvars, int *firstvaridxpercons, SCIP_Bool *success)
 
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_DECL_CONSHDLRCOPY (conshdlrCopyComponents)
 
static SCIP_DECL_CONSFREE (conshdlrFreeComponents)
 
static SCIP_DECL_CONSPROP (consPropComponents)
 
static SCIP_DECL_CONSPRESOL (consPresolComponents)
 
static SCIP_DECL_CONSDELETE (consDeleteComponents)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxComponents)
 
static SCIP_DECL_CONSLOCK (consLockComponents)
 
static SCIP_DECL_CONSINITSOL (consInitsolComponents)
 
SCIP_RETCODE SCIPincludeConshdlrComponents (SCIP *scip)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "independent components constraint handler"

Definition at line 69 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   0

priority of the constraint handler for constraint enforcing

Definition at line 70 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -9999999

priority of the constraint handler for checking feasibility

Definition at line 71 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   -1

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 72 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   FALSE

should the constraint handler be skipped, if no constraints are available?

Definition at line 75 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 77 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 78 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   TRUE

should propagation method be delayed, if other propagators found reductions?

Definition at line 79 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FINAL

presolving timing of the constraint handler (fast, medium, or exhaustive)

Definition at line 81 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask of the constraint handler

Definition at line 82 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH   -1

maximum depth of a node to run components detection (-1: disable component detection during solving)

Definition at line 84 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_MAXINTVARS

#define DEFAULT_MAXINTVARS   500

maximum number of integer (or binary) variables to solve a subproblem directly in presolving (-1: no solving)

Definition at line 85 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_MINSIZE

#define DEFAULT_MINSIZE   50

minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound

Definition at line 86 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_MINRELSIZE

#define DEFAULT_MINRELSIZE   0.1

minimum relative size (in terms of variables) to solve a component individually during branch-and-bound

Definition at line 87 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_NODELIMIT

#define DEFAULT_NODELIMIT   10000LL

maximum number of nodes to be solved in subproblems during presolving

Definition at line 88 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_INTFACTOR

#define DEFAULT_INTFACTOR   1.0

the weight of an integer variable compared to binary variables

Definition at line 89 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ DEFAULT_FEASTOLFACTOR

#define DEFAULT_FEASTOLFACTOR   1.0

default value for parameter to increase the feasibility tolerance in all sub-SCIPs

Definition at line 90 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ consEnfolpComponents

#define consEnfolpComponents   NULL

Definition at line 2556 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ consEnfopsComponents

#define consEnfopsComponents   NULL

Definition at line 2557 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ consCheckComponents

#define consCheckComponents   NULL

Definition at line 2558 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

Typedef Documentation

◆ PROBLEM

typedef struct Problem PROBLEM

data related to one problem (see below)

Definition at line 97 of file cons_components.c.

◆ COMPONENT

typedef struct Component COMPONENT

data related to one component

Function Documentation

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( componentSort  )
static

◆ getMinsize()

static int getMinsize ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

returns minimum size of components to be solved individually during the branch-and-bound search

Parameters
scipmain SCIP data structure
conshdlrdataconstraint handler data

Definition at line 212 of file cons_components.c.

References initComponent(), MAX, NULL, and SCIPgetNVars().

Referenced by componentCreateSubscip(), SCIP_DECL_CONSPROP(), SCIP_DECL_SORTPTRCOMP(), and sortComponents().

◆ initComponent()

◆ freeComponent()

◆ componentSetupWorkingSol()

◆ createSubscip()

static SCIP_RETCODE createSubscip ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP **  subscip 
)
static

◆ copyToSubscip()

static SCIP_RETCODE copyToSubscip ( SCIP scip,
SCIP subscip,
const char *  name,
SCIP_VAR **  vars,
SCIP_VAR **  subvars,
SCIP_CONS **  conss,
SCIP_HASHMAP varmap,
SCIP_HASHMAP consmap,
int  nvars,
int  nconss,
SCIP_Bool success 
)
static

copies the given variables and constraints to the given sub-SCIP

Parameters
scipsource SCIP
subsciptarget SCIP
namename for copied problem
varsarray of variables to copy
subvarsarray to fill with copied vars
conssconstraint to copy
varmaphashmap used for the copy process of variables
consmaphashmap used for the copy process of constraints
nvarsnumber of variables to copy
nconssnumber of constraints to copy
successpointer to store whether copying was successful

Definition at line 546 of file cons_components.c.

References componentCreateSubscip(), FALSE, NULL, Component::nvars, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPconsGetHdlr(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcopyProb(), SCIPgetConsCopy(), SCIPgetVarCopy(), SCIPreleaseCons(), and TRUE.

Referenced by componentCreateSubscip(), createSubscip(), and SCIP_DECL_CONSPRESOL().

◆ componentCreateSubscip()

static SCIP_RETCODE componentCreateSubscip ( COMPONENT component,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_HASHMAP varmap,
SCIP_HASHMAP consmap,
SCIP_CONS **  conss,
int  nconss,
SCIP_Bool success 
)
static

create the sub-SCIP for a given component

Parameters
componentcomponent structure
conshdlrdataconstraint handler data
varmapvariable hashmap used to improve performance
consmapconstraint hashmap used to improve performance
conssconstraints contained in this component
nconssnumber of constraints contained in this component
successpointer to store whether the copying process was successful

Definition at line 611 of file cons_components.c.

References CONSHDLR_NAME, copyToSubscip(), createSubscip(), FALSE, getMinsize(), NULL, Component::number, Component::nvars, Component::problem, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPfree(), SCIPsetIntParam(), SCIPsnprintf(), solveSubscip(), Component::subscip, Component::subvars, TRUE, and Component::vars.

Referenced by copyToSubscip(), and createAndSplitProblem().

◆ solveSubscip()

static SCIP_RETCODE solveSubscip ( SCIP scip,
SCIP subscip,
SCIP_Longint  nodelimit,
SCIP_Real  gaplimit 
)
static

◆ solveAndEvalSubscip()

static SCIP_RETCODE solveAndEvalSubscip ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP subscip,
SCIP_VAR **  vars,
SCIP_VAR **  subvars,
SCIP_CONS **  conss,
int  nvars,
int  nconss,
int *  ndeletedconss,
int *  nfixedvars,
int *  ntightenedbounds,
SCIP_RESULT result,
SCIP_Bool solved 
)
static

solve a connected component during presolving and evaluate the result

Parameters
scipSCIP main data structure
conshdlrdatathe components constraint handler data
subscipsub-SCIP to be solved
varsarray of variables copied to this component
subvarsarray of sub-SCIP variables corresponding to the vars array
conssarray of constraints copied to this component
nvarsnumber of variables copied to this component
nconssnumber of constraints copied to this component
ndeletedconsspointer to store the number of deleted constraints
nfixedvarspointer to store the number of fixed variables
ntightenedboundspointer to store the number of bound tightenings
resultpointer to store the result of the component solving
solvedpointer to store if the problem was solved to optimality

Definition at line 760 of file cons_components.c.

References FALSE, MAX, MIN, Component::nfixedvars, NULL, Component::nvars, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_OPTIMAL, SCIP_STATUS_UNBOUNDED, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPallocBufferArray, SCIPcheckSol(), SCIPcheckSolOrig(), SCIPcreateOrigSol(), SCIPdebugMsg, SCIPdelCons(), SCIPfixVar(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPsetSolVal(), SCIPsolGetOrigObj(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarMarkDeleteGlobalStructures(), solveComponent(), Component::solved, solveSubscip(), and TRUE.

Referenced by SCIP_DECL_CONSPRESOL(), and solveSubscip().

◆ solveComponent()

static SCIP_RETCODE solveComponent ( COMPONENT component,
SCIP_Bool  lastcomponent,
SCIP_RESULT result 
)
static

(continues) solving a connected component

Parameters
componentcomponent structure
lastcomponentis this the last component to be solved?
resultpointer to store the result of the solving process

Definition at line 1017 of file cons_components.c.

References ABS, FALSE, Component::fixedsubvars, Component::fixedvarsobjsum, initProblem(), Component::lastbestsolindex, Component::lastdualbound, Component::lastprimalbound, Component::lastsolindex, Component::laststatus, MAX, MIN, Component::ncalls, Component::nfixedvars, NULL, Component::nvars, Component::problem, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PROBLEM, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIP_VERBLEVEL_NORMAL, SCIPaddNNodes(), SCIPaddSol(), SCIPcheckSol(), SCIPcheckSolOrig(), SCIPdebugMsg, SCIPfindHeur(), SCIPfree(), SCIPfreeSol(), SCIPgetBestSol(), SCIPgetCutoffbound(), SCIPgetDualbound(), SCIPgetGap(), SCIPgetLongintParam(), SCIPgetNNodes(), SCIPgetPrimalbound(), SCIPgetProbName(), SCIPgetSolOrigObj(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetStatus(), SCIPheurGetName(), SCIPinfinity(), SCIPinterruptSolve(), SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisSumLT(), SCIPprintDisplayLine(), SCIPretransformObj(), SCIPsetSolVal(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPsolSetHeur(), SCIPupdateCutoffbound(), SCIPupdateLocalLowerbound(), SCIPvarGetLbGlobal(), SCIPvarIsActive(), Component::solved, solveSubscip(), Component::subscip, Component::subvars, TRUE, Component::vars, and Component::workingsol.

Referenced by solveAndEvalSubscip(), and solveProblem().

◆ initProblem()

static SCIP_RETCODE initProblem ( SCIP scip,
PROBLEM **  problem,
SCIP_Real  fixedvarsobjsum,
int  ncomponents 
)
static

initialize subproblem structure

Parameters
scipSCIP data structure
problempointer to subproblem structure
fixedvarsobjsumobjective contribution of all locally fixed variables
ncomponentsnumber of independent components

Definition at line 1347 of file cons_components.c.

References Component::fixedvarsobjsum, freeProblem(), NULL, Component::nvars, Component::problem, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateSol(), SCIPdebugMsg, SCIPduplicateMemoryArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPisFeasEQ(), SCIPnodeGetNumber(), SCIPpqueueCreate(), SCIPsetSolVal(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and Component::vars.

Referenced by createAndSplitProblem(), and solveComponent().

◆ freeProblem()

static SCIP_RETCODE freeProblem ( PROBLEM **  problem)
static

◆ createConsComponents()

static SCIP_RETCODE createConsComponents ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
PROBLEM problem 
)
static

creates and captures a components constraint

Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
problemproblem to be stored in the constraint

Definition at line 1453 of file cons_components.c.

References CONSHDLR_NAME, FALSE, NULL, Component::problem, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), sortComponents(), and TRUE.

Referenced by freeProblem(), and SCIP_DECL_CONSPROP().

◆ sortComponents()

static SCIP_RETCODE sortComponents ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_DIGRAPH digraph,
SCIP_CONS **  conss,
SCIP_VAR **  vars,
int *  varcomponent,
int *  conscomponent,
int  nconss,
int  nvars,
int *  firstvaridxpercons,
int *  ncompsminsize,
int *  ncompsmaxsize 
)
static

sort the components by size and sort vars and conss arrays by component numbers

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
digraphdirected graph
conssconstraints
varsvariables
varcomponentcomponent numbers for the variables
conscomponentarray to store component numbers for the constraints
nconssnumber of constraints
nvarsnumber of variables
firstvaridxperconsarray with index of first variable in vars array for each constraint
ncompsminsizepointer to store the number of components not exceeding the minimum size
ncompsmaxsizepointer to store the number of components not exceeding the maximum size

Definition at line 1481 of file cons_components.c.

References createAndSplitProblem(), getMinsize(), NULL, Component::nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPdigraphGetComponent(), SCIPdigraphGetNComponents(), SCIPfreeBufferArray, SCIPsortIntPtr(), SCIPsortRealInt(), and SCIPvarGetType().

Referenced by createConsComponents(), and findComponents().

◆ createAndSplitProblem()

static SCIP_RETCODE createAndSplitProblem ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_Real  fixedvarsobjsum,
SCIP_VAR **  sortedvars,
SCIP_CONS **  sortedconss,
int *  compstartsvars,
int *  compstartsconss,
int  ncomponents,
PROBLEM **  problem 
)
static

create PROBLEM structure for the current node and split it into components

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
fixedvarsobjsumobjective contribution of all locally fixed variables
sortedvarsarray of unfixed variables sorted by components
sortedconssarray of (checked) constraints sorted by components
compstartsvarsstart points of components in sortedvars array
compstartsconssstart points of components in sortedconss array
ncomponentsnumber of components
problempointer to store problem structure

Definition at line 1595 of file cons_components.c.

References componentCreateSubscip(), componentSetupWorkingSol(), Component::fixedvarsobjsum, freeProblem(), initComponent(), initProblem(), Component::nfixedvars, NULL, Component::number, Component::nvars, Component::problem, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPnodeGetNumber(), SCIPpqueueInsert(), SCIPvarGetType(), SCIPvarIsActive(), solveProblem(), Component::subvars, TRUE, and Component::vars.

Referenced by SCIP_DECL_CONSPROP(), and sortComponents().

◆ solveProblem()

static SCIP_RETCODE solveProblem ( PROBLEM problem,
SCIP_RESULT result 
)
static

continue solving a problem

Parameters
problemproblem structure
resultresult pointer for the problem solve

Definition at line 1709 of file cons_components.c.

References fillDigraph(), NULL, Component::problem, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYNODE, SCIP_OKAY, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), solveComponent(), and Component::solved.

Referenced by createAndSplitProblem(), and SCIP_DECL_CONSPROP().

◆ fillDigraph()

static SCIP_RETCODE fillDigraph ( SCIP scip,
SCIP_DIGRAPH digraph,
SCIP_CONS **  conss,
int  nconss,
int *  unfixedvarpos,
int  nunfixedvars,
int *  firstvaridxpercons,
SCIP_Bool success 
)
static

loop over constraints, get active variables and fill directed graph

Parameters
scipSCIP data structure
digraphdirected graph
conssconstraints
nconssnumber of constraints
unfixedvarposmapping from variable problem index to unfixed var index
nunfixedvarsnumber of unfixed variables
firstvaridxperconsarray to store for each constraint the index in the local vars array of the first variable of the constraint
successflag indicating successful directed graph filling

Definition at line 1753 of file cons_components.c.

References BMSclearMemoryArray, FALSE, findComponents(), NULL, Component::nvars, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetName(), SCIPdigraphAddArc(), SCIPfreeBufferArray, SCIPgetActiveVars(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetNVars(), SCIPisStopped(), SCIPreallocBufferArray, SCIPvarGetProbindex(), SCIPwarningMessage(), and TRUE.

Referenced by findComponents(), and solveProblem().

◆ findComponents()

static SCIP_RETCODE findComponents ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_Real fixedvarsobjsum,
SCIP_VAR **  sortedvars,
SCIP_CONS **  sortedconss,
int *  compstartsvars,
int *  compstartsconss,
int *  nsortedvars,
int *  nsortedconss,
int *  ncomponents,
int *  ncompsminsize,
int *  ncompsmaxsize 
)
static

search for components in the problem

Parameters
scipSCIP main data structure
conshdlrdatathe components constraint handler data
fixedvarsobjsumobjective contribution of all locally fixed variables, or NULL if fixed variables should not be disregarded
sortedvarsarray to store variables sorted by components, should have enough size for all variables
sortedconssarray to store (checked) constraints sorted by components, should have enough size for all constraints
compstartsvarsstart points of components in sortedvars array
compstartsconssstart points of components in sortedconss array
nsortedvarspointer to store the number of variables belonging to any component
nsortedconsspointer to store the number of (checked) constraints in components
ncomponentspointer to store the number of components
ncompsminsizepointer to store the number of components not exceeding the minimum size
ncompsmaxsizepointer to store the number of components not exceeding the maximum size

Definition at line 1899 of file cons_components.c.

References fillDigraph(), Component::fixedvarsobjsum, MAX, NULL, Component::nvars, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPallocBufferArray, SCIPcreateDigraph(), SCIPdigraphComputeUndirectedComponents(), SCIPdigraphFree(), SCIPdigraphSetSizes(), SCIPfreeBufferArray, SCIPgetConss(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetVars(), SCIPisLT(), SCIPnodeGetNumber(), SCIPvarGetLbLocal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetUbLocal(), SCIPverbMessage(), sortComponents(), and Component::vars.

Referenced by fillDigraph(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyComponents  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 2091 of file cons_components.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrComponents(), and TRUE.

Referenced by findComponents().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( conshdlrFreeComponents  )
static

destructor of constraint handler to free user data (called when SCIP is exiting)

Definition at line 2107 of file cons_components.c.

References NULL, SCIP_DECL_CONSPROP(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrSetData(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteComponents  )
static

frees specific constraint data

Definition at line 2514 of file cons_components.c.

References CONSHDLR_NAME, freeProblem(), NULL, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_OKAY, and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxComponents  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 2528 of file cons_components.c.

References NULL, SCIP_DECL_CONSLOCK(), SCIP_FEASIBLE, and SCIP_OKAY.

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockComponents  )
static

variable rounding lock method of constraint handler

Definition at line 2540 of file cons_components.c.

References SCIP_DECL_CONSINITSOL(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolComponents  )
static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 2548 of file cons_components.c.

References SCIP_OKAY.

Referenced by SCIP_DECL_CONSLOCK().