Detailed Description

constraint handler for handling independent components

Author: Gerald Gamrath

This constraint handler looks for independent components.

#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

#define CONSHDLR_NAME "components"

Definition at line 68 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 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 2550 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ consEnfopsComponents

#define consEnfopsComponents NULL

Definition at line 2551 of file cons_components.c.

Referenced by SCIPincludeConshdlrComponents().

◆ consCheckComponents

#define consCheckComponents NULL

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

comparison method for sorting components

Definition at line 166 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 212 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 229 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 271 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 319 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 453 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 542 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 607 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 665 of file cons_components.c.

References FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcopyLimits(), SCIPdebugMessage, SCIPgetBoolParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetParam(), 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 756 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 1013 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 1341 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 1403 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 1447 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 1475 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 1589 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 1703 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 1747 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 1893 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 2085 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 2101 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 2117 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 2283 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 2508 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 2522 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 2534 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 2542 of file cons_components.c.

References SCIP_OKAY.

Referenced by SCIP_DECL_CONSLOCK().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_PRESOLTIMING

◆ CONSHDLR_PROP_TIMING

◆ DEFAULT_MAXDEPTH

◆ DEFAULT_MAXINTVARS

◆ DEFAULT_MINSIZE

◆ DEFAULT_MINRELSIZE

◆ DEFAULT_NODELIMIT

◆ DEFAULT_INTFACTOR

◆ DEFAULT_FEASTOLFACTOR

◆ consEnfolpComponents

◆ consEnfopsComponents

◆ consCheckComponents

Typedef Documentation

◆ PROBLEM

◆ COMPONENT

Function Documentation

◆ SCIP_DECL_SORTPTRCOMP()

◆ getMinsize()

◆ initComponent()

◆ freeComponent()

◆ componentSetupWorkingSol()

◆ createSubscip()

◆ copyToSubscip()

◆ componentCreateSubscip()

◆ solveSubscip()

◆ solveAndEvalSubscip()

◆ solveComponent()

◆ initProblem()

◆ freeProblem()

◆ createConsComponents()

◆ sortComponents()

◆ createAndSplitProblem()

◆ solveProblem()

◆ fillDigraph()

◆ findComponents()

◆ SCIP_DECL_CONSHDLRCOPY()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSENFORELAX()

◆ SCIP_DECL_CONSLOCK()

◆ SCIP_DECL_CONSINITSOL()