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.

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

scip	SCIP data structure
var	set variable
varidx	for lower bound set variable index, for upper bound set variable index number of variables
pos	variables's position in bdchinfos
nredvars	number of reduced variables so far
bounds	array of bounds where one of them must be fullfilled
boundtypes	array of bound types
newbounds	array of implied bounds(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
counts	array 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)
countnonzeros	array to store the indices of non-zero entries in the counts array
ncountnonzeros	pointer to store the number of non-zero entries in the counts array
issetvar	array 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)
nvars	number of problem variables
foundbin	pointer to store the lowest index of a binary implication variable when found
foundnonbin	pointer to store the lowest index of a non-binary implication variable when found
implidx	array to store the variable indices (for upper bound 'nvars' is added to the index) which are implied
nimplidx	pointer to store the number of implied variables
lastbounds	array 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(), SCIPvarIsImpliedIntegral(), 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

scip	SCIP data structure
var	set variable
varidx	for lower bound set variable index, for upper bound set variable index + number of variables
pos	variables's position in bdchinfos
nredvars	number of reduced variables so far
value	value used for clique and implication info
bounds	array of bounds where one of them must be fullfilled
boundtypes	array of bound types
newbounds	array of implied bounds(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
counts	array 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)
countnonzeros	array to store the indices of non-zero entries in the counts array
ncountnonzeros	pointer to store the number of non-zero entries in the counts array
issetvar	array 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)
nvars	number of problem variables
foundbin	pointer to store the lowest index of a binary implication variable when found
foundnonbin	pointer to store the lowest index of a non-binary implication variable when found
implidx	array to store the variable indices (for upper bound 'nvars' is added to the index) which are implied
nimplidx	pointer to store the number of implied variables
lastbounds	array 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(), SCIPvarIsImpliedIntegral(), 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

var	set variable
varidx	for lower bound set variable index, for upper bound set variable index number of variables
pos	variables's position in bdchinfos
nredvars	number of reduced variables so far
value	value used for clique and implication info
bounds	array of bounds where one of them must be fullfilled
boundtypes	array of bound types
newbounds	array of implied bounds(, size is two times number of variables, first half for implied lower bounds, second for implied upper bounds)
counts	array 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)
countnonzeros	array to store the indices of non-zero entries in the counts array
ncountnonzeros	pointer to store the number of non-zero entries in the counts array
issetvar	array 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)
nvars	number of problem variables
foundbin	pointer to store the lowest index of a binary implication variable when found
implidx	array to store the variable indices (for upper bound 'nvars' is added to the index) which are implied
nimplidx	pointer 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CLEARRATIO

Function Documentation

◆ collectNonBinaryVBoundData()

◆ collectNonBinaryImplicationData()

◆ collectBinaryCliqueData()