presolve.h File Reference

Detailed Description

internal methods for presolving

Author

Michael Winkler

Definition in file presolve.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
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 fullshortening)

Function Documentation

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	fullshortening
	)

try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one must be fulfilled

e.g. a set of logicor or bounddisjunctive constraint variables would be such a set

consider the following set:

x1 >= 1, x2 >= 3, x3 >= 1, x4 <= 0

by (global) implication data (cliques, implications, and variable bounds) we have also the following implications given:

x1 >= 1 => x3 >= 1 x2 >= 2 => x3 >= 1 x4 <= 0 => x1 >= 1

Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we can reduce the set by x4. Also, the both other implications and x3 >= 1 (in the given variable set) all imply exactly x3 >= 1, so we tighten the global lower bound of x3 to 1 and the set of variables gets redundant.

try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one must be fulfilled

e.g. a set of logicor or bounddisjunctive constraint variables would be such a set

consider the following set:

x1 >= 1, x2 >= 3, x3 >= 1, x4 <= 0

by (global) implication data (cliques, implications, and variable bounds) we have also the following implications given:

x1 >= 1 => x3 >= 1 x2 >= 2 => x3 >= 1 x4 <= 0 => x1 >= 1

Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we can reduce the set by x4. Also, the both other implications and x3 >= 1 (in the given variable set) all implie exactly x3 >= 1, so we tighten the global lower bound of x3 to 1 and the set of variables gets redundant.

Parameters

scip	SCIP data structure
vars	array of active! variables for which at least one must be fulfilled in the following bounds and boundtypes
bounds	bounds array for which at least one must be fulfilled
boundtypes	boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE == SCIP_BOUNDTYPE_LOWER) for which at least one must be fulfilled
redundants	array which be filled and then indicate if a variable in the set is redundant
nvars	number of variables
nredvars	pointer to store how many variables can be removed
nglobalred	pointer to store number of global reductions on variable bounds found through this set of variables
setredundant	pointer to store if we found a global reduction on a variable which was part of the given set of variables, this makes this disjunction redundant
fullshortening	do we want to try the shortening procedure over the whole set (which might be expensive)

Definition at line 941 of file presolve.c.

References BMSallocClearMemoryArray, BMSclearMemoryArray, BMSfreeMemoryArray, Scip::branchcand, collectBinaryCliqueData(), collectBinaryImplicationData(), collectNonBinaryImplicationData(), collectNonBinaryVBoundData(), Scip::eventqueue, FALSE, Scip::lp, Scip::mem, SCIP_Tree::npendingbdchgs, NULL, Scip::origprob, SCIP_Mem::probmem, SCIP_Tree::root, SCIP_ALLOC, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGT(), SCIPisLT(), SCIPnodeAddBoundchg(), SCIPprobGetName(), SCIPprobGetNImplBinVars(), SCIPprobGetNVars(), SCIPprobGetVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), Scip::set, Scip::stat, Scip::transprob, Scip::tree, and TRUE.

Referenced by detectImpliedBounds(), and shortenConss().