|
|
methods for presolving
- Author
- Michael Winkler
Definition in file presolve.c.
Go to the source code of this file.
|
| 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) |
| |
| 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
|
| 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 40 of file presolve.c.
References MIN, NULL, SCIP_INVALID, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPdebugMessage, SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), and SCIPvarIsBinary().
Referenced by SCIPshrinkDisjunctiveVarSet().
| 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 563 of file presolve.c.
References MIN, NULL, SCIP_BOUNDTYPE_UPPER, SCIP_INVALID, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPdebugMessage, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNImpls(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by SCIPshrinkDisjunctiveVarSet().
| 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
|
| 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 791 of file presolve.c.
References MIN, NULL, SCIP_Bool, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMessage, SCIPvarGetCliques(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by SCIPshrinkDisjunctiveVarSet().
| 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 |
|
) |
| |
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.
- Parameters
-
| scip | SCIP data structure |
| vars | variables array 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 |
| glbinfeas | pointer to store if global infeasibility was detected |
| fullshortening | do we want to try the shortening procedure over the whole set (which might be expensive) |
Definition at line 953 of file presolve.c.
References BMSclearMemoryArray, Scip::branchcand, CLEARRATIO, Scip::cliquetable, collectBinaryCliqueData(), collectNonBinaryImplicationData(), collectNonBinaryVBoundData(), Scip::eventqueue, FALSE, Scip::lp, Scip::mem, SCIP_Tree::npendingbdchgs, NULL, Scip::origprob, SCIP_Mem::probmem, Scip::reopt, SCIP_Tree::root, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcleanupCliques(), SCIPcutoffNode(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetRootNode(), 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().
|
