cons_components.c File Reference

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)
Interface methods
SCIP_RETCODE	SCIPincludeConshdlrComponents (SCIP *scip)

Macro Definition Documentation

CONSHDLR_NAME

#define CONSHDLR_NAME   "components"

Definition at line 59 of file cons_components.c.

Referenced by componentCreateSubscip(), createConsComponents(), createSubscip(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPROP(), and SCIPincludeConshdlrComponents().

CONSHDLR_DESC

#define CONSHDLR_DESC   "independent components constraint handler"

Definition at line 60 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 61 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 62 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 63 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 66 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 68 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 69 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 70 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 72 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 73 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 75 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 76 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 77 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 78 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 79 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 80 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 81 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

consEnfolpComponents

#define consEnfolpComponents   NULL

Definition at line 2525 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

consEnfopsComponents

#define consEnfopsComponents   NULL

Definition at line 2526 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

consCheckComponents

#define consCheckComponents   NULL

Definition at line 2527 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 88 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

comparison method for sorting components

Definition at line 157 of file cons_components.c.

References getMinsize(), Component::lastdualbound, Component::lastprimalbound, Component::ncalls, NULL, Component::number, Component::problem, SCIP_Real, SCIPisFeasGT(), and SCIPisFeasLT().

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

scip	main SCIP data structure
conshdlrdata	constraint handler data

Definition at line 203 of file cons_components.c.

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

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

initComponent()

static SCIP_RETCODE initComponent ( PROBLEM *  problem )

static

initialize component structure

Parameters

problem

subproblem structure

Definition at line 220 of file cons_components.c.

References FALSE, Component::fixedsubvars, Component::fixedvars, Component::fixedvarsobjsum, Component::fixedvarssize, freeComponent(), Component::lastbestsolindex, Component::lastdualbound, Component::lastprimalbound, Component::lastsolindex, Component::laststatus, Component::ncalls, Component::nfixedvars, NULL, Component::number, Component::nvars, Component::problem, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPinfinity(), Component::solved, Component::subscip, Component::subvars, Component::vars, and Component::workingsol.

Referenced by createAndSplitProblem(), and getMinsize().

freeComponent()

static SCIP_RETCODE freeComponent ( COMPONENT *  component )

static

free component structure

Parameters

component

pointer to component structure

Definition at line 262 of file cons_components.c.

References componentSetupWorkingSol(), Component::fixedsubvars, Component::fixedvars, Component::fixedvarssize, NULL, Component::number, Component::nvars, Component::problem, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPfreeSol(), Component::subscip, Component::subvars, Component::vars, and Component::workingsol.

Referenced by freeProblem(), and initComponent().

componentSetupWorkingSol()

static SCIP_RETCODE componentSetupWorkingSol ( COMPONENT *  component, SCIP_HASHMAP *  varmap  )

static

create the working solution for a given component, store fixed variables and the corresponding objective offset

Parameters

component	component structure
varmap	variable hashmap

Definition at line 310 of file cons_components.c.

References createSubscip(), FALSE, Component::fixedsubvars, Component::fixedvars, Component::fixedvarsobjsum, Component::fixedvarssize, Component::nfixedvars, NULL, Component::nvars, Component::problem, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PROBLEM, SCIPallocBlockMemoryArray, SCIPcreateOrigSol(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPdebugSolEnable, SCIPdebugSolIsEnabled, SCIPdebugSolIsValidInSubtree, SCIPgetNOrigVars(), SCIPgetNVars(), SCIPgetStage(), SCIPgetVars(), SCIPhashmapGetImage(), SCIPisEQ(), SCIPisLT(), SCIPisZero(), SCIPsetSolVal(), SCIPtransformProb(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), Component::subscip, Component::subvars, Component::vars, and Component::workingsol.

Referenced by createAndSplitProblem(), and freeComponent().

createSubscip()

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

static

create a sub-SCIP for the given variables and constraints

Parameters

scip	main SCIP data structure
conshdlrdata	constraint handler data
subscip	pointer to store created sub-SCIP

Definition at line 444 of file cons_components.c.

References CONSHDLR_NAME, copyToSubscip(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_OFF, SCIP_STAGE_PRESOLVING, SCIPconshdlrGetData(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcreate(), SCIPdebugSolIsValidInSubtree, SCIPfindConshdlr(), SCIPfixParam(), SCIPfree(), SCIPgetDepth(), SCIPgetStage(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), and TRUE.

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

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

scip	source SCIP
subscip	target SCIP
name	name for copied problem
vars	array of variables to copy
subvars	array to fill with copied vars
conss	constraint to copy
varmap	hashmap used for the copy process of variables
consmap	hashmap used for the copy process of constraints
nvars	number of variables to copy
nconss	number of constraints to copy
success	pointer to store whether copying was successful

Definition at line 533 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

component	component structure
conshdlrdata	constraint handler data
varmap	variable hashmap used to improve performance
consmap	constraint hashmap used to improve performance
conss	constraints contained in this component
nconss	number of constraints contained in this component
success	pointer to store whether the copying process was successful

Definition at line 598 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

solve a given sub-SCIP up to the given limits

Parameters

scip	main SCIP
subscip	sub-SCIP to solve
nodelimit	node limit
gaplimit	gap limit

Definition at line 656 of file cons_components.c.

References FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcopyLimits(), SCIPdebugMessage, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPprintBestSol(), SCIPprintStatistics(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), and solveAndEvalSubscip().

Referenced by componentCreateSubscip(), solveAndEvalSubscip(), and solveComponent().

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

scip	SCIP main data structure
conshdlrdata	the components constraint handler data
subscip	sub-SCIP to be solved
vars	array of variables copied to this component
subvars	array of sub-SCIP variables corresponding to the vars array
conss	array of constraints copied to this component
nvars	number of variables copied to this component
nconss	number of constraints copied to this component
ndeletedconss	pointer to store the number of deleted constraints
nfixedvars	pointer to store the number of fixed variables
ntightenedbounds	pointer to store the number of bound tightenings
result	pointer to store the result of the component solving
solved	pointer to store if the problem was solved to optimality

Definition at line 731 of file cons_components.c.

References FALSE, MAX, 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(), SCIPdebugMessage, 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

component	component structure
lastcomponent	is this the last component to be solved?
result	pointer to store the result of the solving process

Definition at line 988 of file cons_components.c.

References FALSE, Component::fixedsubvars, Component::fixedvarsobjsum, initProblem(), Component::lastbestsolindex, Component::lastdualbound, Component::lastprimalbound, Component::lastsolindex, Component::laststatus, MAX, 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_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, 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(), SCIPdebugMessage, 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

scip	SCIP data structure
problem	pointer to subproblem structure
fixedvarsobjsum	objective contribution of all locally fixed variables
ncomponents	number of independent components

Definition at line 1316 of file cons_components.c.

References Component::fixedvarsobjsum, freeProblem(), NULL, Component::nvars, Component::problem, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateSol(), SCIPdebugMessage, 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

free subproblem structure

Parameters

problem

pointer to problem to free

Definition at line 1378 of file cons_components.c.

References createConsComponents(), freeComponent(), NULL, Component::problem, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArray, SCIPfreeSol(), and SCIPpqueueFree().

Referenced by createAndSplitProblem(), initProblem(), and SCIP_DECL_CONSDELETE().

createConsComponents()

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

static

creates and captures a components constraint

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
problem	problem to be stored in the constraint

Definition at line 1422 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

scip	SCIP data structure
conshdlrdata	constraint handler data
digraph	directed graph
conss	constraints
vars	variables
varcomponent	component numbers for the variables
conscomponent	array to store component numbers for the constraints
nconss	number of constraints
nvars	number of variables
firstvaridxpercons	array with index of first variable in vars array for each constraint
ncompsminsize	pointer to store the number of components not exceeding the minimum size
ncompsmaxsize	pointer to store the number of components not exceeding the maximum size

Definition at line 1450 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

scip	SCIP data structure
conshdlrdata	constraint handler data
fixedvarsobjsum	objective contribution of all locally fixed variables
sortedvars	array of unfixed variables sorted by components
sortedconss	array of (checked) constraints sorted by components
compstartsvars	start points of components in sortedvars array
compstartsconss	start points of components in sortedconss array
ncomponents	number of components
problem	pointer to store problem structure

Definition at line 1564 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

problem	problem structure
result	result pointer for the problem solve

Definition at line 1678 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

scip	SCIP data structure
digraph	directed graph
conss	constraints
nconss	number of constraints
unfixedvarpos	mapping from variable problem index to unfixed var index
nunfixedvars	number of unfixed variables
firstvaridxpercons	array to store for each constraint the index in the local vars array of the first variable of the constraint
success	flag indicating successful directed graph filling

Definition at line 1722 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

scip	SCIP main data structure
conshdlrdata	the components constraint handler data
fixedvarsobjsum	objective contribution of all locally fixed variables, or NULL if fixed variables should not be disregarded
sortedvars	array to store variables sorted by components, should have enough size for all variables
sortedconss	array to store (checked) constraints sorted by components, should have enough size for all constraints
compstartsvars	start points of components in sortedvars array
compstartsconss	start points of components in sortedconss array
nsortedvars	pointer to store the number of variables belonging to any component
nsortedconss	pointer to store the number of (checked) constraints in components
ncomponents	pointer to store the number of components
ncompsminsize	pointer to store the number of components not exceeding the minimum size
ncompsmaxsize	pointer to store the number of components not exceeding the maximum size

Definition at line 1868 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 2060 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 2076 of file cons_components.c.

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

Referenced by SCIP_DECL_CONSHDLRCOPY().

SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropComponents  )

static

domain propagation method of constraint handler

Definition at line 2092 of file cons_components.c.

References CONSHDLR_NAME, createAndSplitProblem(), createConsComponents(), findComponents(), Component::fixedvarsobjsum, getMinsize(), SCIP_Cons::name, NULL, Component::problem, SCIP_CALL, SCIP_DECL_CONSPRESOL(), SCIP_DELAYNODE, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPallowStrongDualReds(), SCIPallowWeakDualReds(), SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetData(), SCIPconshdlrGetNActiveConss(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLongintParam(), SCIPgetNActivePricers(), SCIPgetNConss(), SCIPgetNNodes(), SCIPgetNVars(), SCIPinProbing(), SCIPinRepropagation(), SCIPisStopped(), SCIPnodeGetNumber(), SCIPreleaseCons(), and solveProblem().

Referenced by SCIP_DECL_CONSFREE().

SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolComponents  )

static

presolving method of constraint handler

Definition at line 2258 of file cons_components.c.

References CONSHDLR_NAME, copyToSubscip(), createSubscip(), findComponents(), Component::nfixedvars, NULL, Component::nvars, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSDELETE(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INIT, SCIP_STAGE_PRESOLVING, SCIP_UNBOUNDED, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPallowStrongDualReds(), SCIPallowWeakDualReds(), SCIPblkmem(), SCIPconshdlrGetData(), SCIPconshdlrGetNActiveConss(), SCIPconshdlrGetName(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPdebugSolEnable, SCIPdebugSolIsEnabled, SCIPfree(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetStage(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPinProbing(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsnprintf(), SCIPvarGetType(), SCIPvarIsActive(), solveAndEvalSubscip(), Component::solved, Component::subscip, Component::subvars, and TRUE.

Referenced by SCIP_DECL_CONSPROP().

SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteComponents  )

static

frees specific constraint data

Definition at line 2483 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 2497 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 2509 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 2517 of file cons_components.c.

References SCIP_OKAY.

Referenced by SCIP_DECL_CONSLOCK().