Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

methods for presolving

Author
Michael Winkler

Definition in file presolve.c.

#include "blockmemshell/memory.h"
#include "scip/presolve.h"
#include "scip/prob.h"
#include "scip/pub_implics.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_tree.h"
#include "scip/struct_mem.h"
#include "scip/struct_scip.h"
#include "scip/tree.h"

Go to the source code of this file.

Macros

#define CLEARRATIO   0.8
 

Functions

static void collectNonBinaryVBoundData (SCIP *scip, SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds)
 
static void collectNonBinaryImplicationData (SCIP *scip, SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds)
 
static void collectBinaryCliqueData (SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *implidx, int *nimplidx)
 
SCIP_RETCODE SCIPshrinkDisjunctiveVarSet (SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
 

Macro Definition Documentation

◆ CLEARRATIO

#define CLEARRATIO   0.8

Definition at line 972 of file presolve.c.

Referenced by SCIPshrinkDisjunctiveVarSet().

Function Documentation

◆ collectNonBinaryVBoundData()

static void collectNonBinaryVBoundData ( SCIP scip,
SCIP_VAR var,
int  varidx,
int  pos,
int  nredvars,
SCIP_Real bounds,
SCIP_Bool boundtypes,
SCIP_Real newbounds,
int *  counts,
int *  countnonzeros,
int *  ncountnonzeros,
int *  issetvar,
int  nvars,
int *  foundbin,
int *  foundnonbin,
int *  implidx,
int *  nimplidx,
SCIP_Real lastbounds 
)
static

collect variable bound information for a variable set reduction and global implication; only variable which have the vartype != SCIP_VARTYPE_BINARY have variable bounds

Parameters
scipSCIP data structure
varset variable
varidxfor lower bound set variable index, for upper bound set variable index
  • number of variables
posvariables's position in bdchinfos
nredvarsnumber of reduced variables so far
boundsarray of bounds where one of them must be fullfilled
boundtypesarray of bound types
newboundsarray of implied bounds(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
countsarray of number of implication on a bound (, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
countnonzerosarray to store the indices of non-zero entries in the counts array
ncountnonzerospointer to store the number of non-zero entries in the counts array
issetvararray containing for set variables the position in the current set, or 0 if it is not a set variable or -1, if it is a redundant(i.e. implies another set variable) set variables(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
nvarsnumber of problem variables
foundbinpointer to store the lowest index of a binary implication variable when found
foundnonbinpointer to store the lowest index of a non-binary implication variable when found
implidxarray to store the variable indices (for upper bound 'nvars' is added to the index) which are implied
nimplidxpointer to store the number of implied variables
lastboundsarray to remember last implied bounds before taken the current variable into account, first nvars for lower bound, second nvars for upper bound

this array is used when a set variable got redundant, because it implies another set variable, and we need to correct the counts array

Definition at line 57 of file presolve.c.

References MIN, NULL, SCIP_INVALID, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsBinary(), and w.

Referenced by SCIPshrinkDisjunctiveVarSet().

◆ collectNonBinaryImplicationData()

static void collectNonBinaryImplicationData ( SCIP scip,
SCIP_VAR var,
int  varidx,
int  pos,
int  nredvars,
SCIP_Bool  value,
SCIP_Real bounds,
SCIP_Bool boundtypes,
SCIP_Real newbounds,
int *  counts,
int *  countnonzeros,
int *  ncountnonzeros,
int *  issetvar,
int  nvars,
int *  foundbin,
int *  foundnonbin,
int *  implidx,
int *  nimplidx,
SCIP_Real lastbounds 
)
static

collect non-binary implication data for variable set reduction and global bound implications; only variable which have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are saved as variable bounds

Parameters
scipSCIP data structure
varset variable
varidxfor lower bound set variable index, for upper bound set variable index + number of variables
posvariables's position in bdchinfos
nredvarsnumber of reduced variables so far
valuevalue used for clique and implication info
boundsarray of bounds where one of them must be fullfilled
boundtypesarray of bound types
newboundsarray of implied bounds(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
countsarray of number of implication on a bound (, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
countnonzerosarray to store the indices of non-zero entries in the counts array
ncountnonzerospointer to store the number of non-zero entries in the counts array
issetvararray containing for set variables the position in the current set, or 0 if it is not a set variable or -1, if it is a redundant(i.e. implies another set variable) set variables(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
nvarsnumber of problem variables
foundbinpointer to store the lowest index of a binary implication variable when found
foundnonbinpointer to store the lowest index of a non-binary implication variable when found
implidxarray to store the variable indices (for upper bound 'nvars' is added to the index) which are implied
nimplidxpointer to store the number of implied variables
lastboundsarray to remember last implied bounds before taken the current variable into account, first nvars for lower bound, second nvars for upper bound

this array is used when a set variable got redundant, because it implies another set variable, and we need to correct the counts array

Definition at line 595 of file presolve.c.

References MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_INVALID, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGE(), SCIPisLE(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNImpls(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and w.

Referenced by SCIPshrinkDisjunctiveVarSet().

◆ collectBinaryCliqueData()

static void collectBinaryCliqueData ( SCIP_VAR var,
int  varidx,
int  pos,
int  nredvars,
SCIP_Bool  value,
SCIP_Real bounds,
SCIP_Bool boundtypes,
SCIP_Real newbounds,
int *  counts,
int *  countnonzeros,
int *  ncountnonzeros,
int *  issetvar,
int  nvars,
int *  foundbin,
int *  implidx,
int *  nimplidx 
)
static

collect clique data on binary variables for variable set reduction and global bound implications

Parameters
varset variable
varidxfor lower bound set variable index, for upper bound set variable index
  • number of variables
posvariables's position in bdchinfos
nredvarsnumber of reduced variables so far
valuevalue used for clique and implication info
boundsarray of bounds where one of them must be fullfilled
boundtypesarray of bound types
newboundsarray of implied bounds(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
countsarray of number of implication on a bound (, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
countnonzerosarray to store the indices of non-zero entries in the counts array
ncountnonzerospointer to store the number of non-zero entries in the counts array
issetvararray containing for set variables the position in the current set, or 0 if it is not a set variable, or -1, if it is a redundant (i.e. implies another set variable) set variable (the size of the array is two times the number of variables, first half for implied lower bounds, second for implied upper bounds)
nvarsnumber of problem variables
foundbinpointer to store the lowest index of a binary implication variable when found
implidxarray to store the variable indices (for upper bound 'nvars' is added to the index) which are implied
nimplidxpointer to store the number of implied variables

Definition at line 833 of file presolve.c.

References MIN, NULL, SCIP_Bool, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMessage, SCIPvarGetCliques(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and w.

Referenced by SCIPshrinkDisjunctiveVarSet().