Detailed Description

solve independent components in advance

Author: Dieter Weninger; Gerald Gamrath

This presolver looks for independent components at the end of the presolving. If independent components are found in which a maximum number of discrete variables is not exceeded, the presolver tries to solve them in advance as subproblems. Afterwards, if a subproblem was solved to optimality, the corresponding variables/constraints can be fixed/deleted in the main problem.

Definition in file presol_components.c.

#include <assert.h>
#include "scip/presol_components.h"

Go to the source code of this file.

Macros
#define	PRESOL_NAME "components"

#define	PRESOL_DESC "components presolver"

#define	PRESOL_PRIORITY -9200000

#define	PRESOL_MAXROUNDS -1

#define	PRESOL_DELAY TRUE

#define	DEFAULT_WRITEPROBLEMS FALSE

#define	DEFAULT_MAXINTVARS 500

#define	DEFAULT_NODELIMIT 10000LL

#define	DEFAULT_INTFACTOR 1.0

#define	DEFAULT_RELDECREASE 0.2

#define	DEFAULT_FEASTOLFACTOR 1.0

Functions
static SCIP_RETCODE	copyAndSolveComponent (SCIP scip, SCIP_PRESOLDATA presoldata, SCIP_HASHMAP consmap, int compnr, SCIP_CONS conss, int nconss, SCIP_VAR vars, SCIP_Real fixvals, int nvars, int nbinvars, int nintvars, int nsolvedprobs, int ndeletedvars, int ndeletedconss, SCIP_RESULT result)

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

static SCIP_RETCODE	splitProblem (SCIP scip, SCIP_PRESOLDATA presoldata, SCIP_CONS conss, SCIP_VAR vars, SCIP_Real fixvals, int nconss, int nvars, int components, int ncomponents, int firstvaridxpercons, int nsolvedprobs, int ndeletedvars, int ndeletedconss, SCIP_RESULT *result)

static SCIP_RETCODE	presolComponents (SCIP scip, SCIP_PRESOL presol, int nfixedvars, int ndelconss, SCIP_RESULT *result)

static	SCIP_DECL_PRESOLFREE (presolFreeComponents)

static	SCIP_DECL_PRESOLINIT (presolInitComponents)

static	SCIP_DECL_PRESOLEXEC (presolExecComponents)

SCIP_RETCODE	SCIPincludePresolComponents (SCIP *scip)

Macro Definition Documentation

#define PRESOL_NAME "components"

Definition at line 40 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define PRESOL_DESC "components presolver"

Definition at line 41 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define PRESOL_PRIORITY -9200000

priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators

Definition at line 42 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define PRESOL_MAXROUNDS -1

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

Definition at line 43 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define PRESOL_DELAY TRUE

should presolver be delayed, if other presolvers found reductions?

Definition at line 44 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_WRITEPROBLEMS FALSE

should the single components be written as an .lp-file?

Definition at line 46 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_MAXINTVARS 500

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

Definition at line 47 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_NODELIMIT 10000LL

maximum number of nodes to be solved in subproblems

Definition at line 48 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_INTFACTOR 1.0

the weight of an integer variable compared to binary variables

Definition at line 49 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_RELDECREASE 0.2

percentage by which the number of variables has to be decreased after the last component solving to allow running again (1.0: do not run again)

Definition at line 50 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_FEASTOLFACTOR 1.0

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

Definition at line 52 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

Function Documentation

static SCIP_RETCODE copyAndSolveComponent	(	SCIP *	scip,
		SCIP_PRESOLDATA *	presoldata,
		SCIP_HASHMAP *	consmap,
		int	compnr,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_VAR **	vars,
		SCIP_Real *	fixvals,
		int	nvars,
		int	nbinvars,
		int	nintvars,
		int *	nsolvedprobs,
		int *	ndeletedvars,
		int *	ndeletedconss,
		SCIP_RESULT *	result
	)

static

copies a connected component consisting of the given constraints and variables into a sub-SCIP and tries to solve the sub-SCIP to optimality

Parameters

scip	SCIP data structure
presoldata	presolver data
consmap	constraint hashmap used to improve performance
compnr	number of the component
conss	constraints contained in this component
nconss	number of constraints contained in this component
vars	variables contained in this component
fixvals	array to store the values to fix the variables to
nvars	number of variables contained in this component
nbinvars	number of binary variables contained in this component
nintvars	number of integer variables contained in this component
nsolvedprobs	pointer to increase, if the subproblem was solved
ndeletedvars	pointer to increase by the number of deleted variables
ndeletedconss	pointer to increase by the number of deleted constraints
result	pointer to store the result of the presolving call

Definition at line 225 of file presol_components.c.

References FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_OPTIMAL, SCIP_STATUS_UNBOUNDED, SCIP_UNBOUNDED, SCIP_VERBLEVEL_FULL, SCIPaddCons(), SCIPblkmem(), SCIPcheckSol(), SCIPcheckSolOrig(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcreate(), SCIPcreateOrigSol(), SCIPcreateProb(), SCIPdebugMessage, SCIPdelCons(), SCIPfixVar(), SCIPfree(), SCIPfreeSol(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetConsCopy(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNIntVars(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPinfoMessage(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisParamFixed(), SCIPisPositive(), SCIPprintStatistics(), SCIPreleaseCons(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsetSolVal(), SCIPsnprintf(), SCIPsolGetOrigObj(), SCIPsolve(), SCIPstatistic, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPverbMessage(), SCIPwriteOrigProblem(), and TRUE.

Referenced by splitProblem().

static SCIP_RETCODE fillDigraph	(	SCIP *	scip,
		SCIP_DIGRAPH *	digraph,
		SCIP_CONS **	conss,
		int	nconss,
		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
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 673 of file presol_components.c.

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

Referenced by presolComponents().

static SCIP_RETCODE splitProblem	(	SCIP *	scip,
		SCIP_PRESOLDATA *	presoldata,
		SCIP_CONS **	conss,
		SCIP_VAR **	vars,
		SCIP_Real *	fixvals,
		int	nconss,
		int	nvars,
		int *	components,
		int	ncomponents,
		int *	firstvaridxpercons,
		int *	nsolvedprobs,
		int *	ndeletedvars,
		int *	ndeletedconss,
		SCIP_RESULT *	result
	)

static

use components to assign variables and constraints to the subscips and try to solve all subscips having not too many integer variables

Parameters

scip	SCIP data structure
presoldata	presolver data
conss	constraints
vars	variables
fixvals	array to store the fixing values
nconss	number of constraints
nvars	number of variables
components	array with component number for every variable
ncomponents	number of components
firstvaridxpercons	array with index of first variable in vars array for each constraint
nsolvedprobs	pointer to store the number of solved subproblems
ndeletedvars	pointer to store the number of deleted variables
ndeletedconss	pointer to store the number of deleted constraints
result	pointer to store the result of the presolving call

Definition at line 937 of file presol_components.c.

References copyAndSolveComponent(), MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_UNBOUNDED, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMessage, SCIPfixVar(), SCIPfree(), SCIPfreeBufferArray, SCIPgetNConss(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPinfoMessage(), SCIPisNegative(), SCIPisPositive(), SCIPisStopped(), SCIPprintCons(), SCIPsortIntPtr(), SCIPstatistic, SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by presolComponents().

static SCIP_RETCODE presolComponents	(	SCIP *	scip,
		SCIP_PRESOL *	presol,
		int *	nfixedvars,
		int *	ndelconss,
		SCIP_RESULT *	result
	)

static

performs presolving by searching for components

Parameters

scip	SCIP main data structure
presol	the presolver itself
nfixedvars	counter to increase by the number of fixed variables
ndelconss	counter to increase by the number of deleted constrains
result	pointer to store the result of the presolving call