Scippy

SCIP

Solving Constraint Integer Programs

presol_components.c File Reference

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_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#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 fillDigraph(), and 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_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 44 of file presol_components.c.

Referenced by SCIPincludePresolComponents().

#define DEFAULT_WRITEPROBLEMS   FALSE

should the single components be written as an .cip-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 53 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
scipSCIP data structure
presoldatapresolver data
consmapconstraint hashmap used to improve performance
compnrnumber of the component
conssconstraints contained in this component
nconssnumber of constraints contained in this component
varsvariables contained in this component
fixvalsarray to store the values to fix the variables to
nvarsnumber of variables contained in this component
nbinvarsnumber of binary variables contained in this component
nintvarsnumber of integer variables contained in this component
nsolvedprobspointer to increase, if the subproblem was solved
ndeletedvarspointer to increase by the number of deleted variables
ndeletedconsspointer to increase by the number of deleted constraints
resultpointer to store the result of the presolving call

Definition at line 226 of file presol_components.c.

References FALSE, fillDigraph(), 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(), SCIPwarningMessage(), SCIPwriteOrigProblem(), SCIPwriteParams(), 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
scipSCIP data structure
digraphdirected graph
conssconstraints
nconssnumber of constraints
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 696 of file presol_components.c.

References BMSclearMemoryArray, FALSE, NULL, PRESOL_NAME, SCIP_Bool, SCIP_CALL, SCIP_FILECREATEERROR, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetName(), SCIPdigraphAddArc(), SCIPerrorMessage, SCIPfindPresol(), SCIPfreeBufferArray, SCIPgetActiveVars(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetNVars(), SCIPgetProbName(), SCIPinfoMessage(), SCIPisStopped(), SCIPpresolGetNCalls(), SCIPprintSysError(), SCIPreallocBufferArray, SCIPsnprintf(), SCIPsplitFilename(), SCIPvarGetProbindex(), SCIPwarningMessage(), splitProblem(), and TRUE.

Referenced by copyAndSolveComponent(), and 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
scipSCIP data structure
presoldatapresolver data
conssconstraints
varsvariables
fixvalsarray to store the fixing values
nconssnumber of constraints
nvarsnumber of variables
componentsarray with component number for every variable
ncomponentsnumber of components
firstvaridxperconsarray with index of first variable in vars array for each constraint
nsolvedprobspointer to store the number of solved subproblems
ndeletedvarspointer to store the number of deleted variables
ndeletedconsspointer to store the number of deleted constraints
resultpointer to store the result of the presolving call

Definition at line 960 of file presol_components.c.

References copyAndSolveComponent(), NULL, presolComponents(), SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_UNBOUNDED, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPblkmem(), SCIPfree(), SCIPfreeBufferArray, SCIPgetNConss(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPinfoMessage(), SCIPisStopped(), SCIPprintCons(), SCIPsortIntPtr(), SCIPstatistic, and SCIPvarGetType().

Referenced by fillDigraph(), and presolComponents().

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

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

Definition at line 1341 of file presol_components.c.

References NULL, SCIP_DECL_PRESOLINIT(), SCIP_OKAY, SCIPfreeMemory, SCIPpresolGetData(), and SCIPpresolSetData().

Referenced by presolComponents().

static SCIP_DECL_PRESOLINIT ( presolInitComponents  )
static

initialization method of presolver (called after problem was transformed)

Definition at line 1357 of file presol_components.c.

References FALSE, NULL, SCIP_CALL, SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLEXIT, SCIP_OKAY, SCIPpresolGetData(), SCIPstatistic, and TRUE.

Referenced by SCIP_DECL_PRESOLFREE().

static SCIP_DECL_PRESOLEXEC ( presolExecComponents  )
static

execution method of presolver

Definition at line 1395 of file presol_components.c.

References presolComponents(), SCIP_CALL, SCIP_OKAY, and SCIPincludePresolComponents().

Referenced by SCIP_DECL_PRESOLINIT().