|
|
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, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, 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, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds) |
| |
| static void | collectBinaryImplicationData (SCIP_VAR *var, int varidx, int pos, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *issetvar, int nvars, int *foundbin, int *implidx, int *nimplidx) |
| |
| static void | collectBinaryCliqueData (SCIP_VAR *var, int varidx, int pos, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, 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 fullshortening) |
| |
| static void collectNonBinaryVBoundData |
( |
SCIP * |
scip, |
|
|
SCIP_VAR * |
var, |
|
|
int |
varidx, |
|
|
int |
pos, |
|
|
SCIP_Real * |
bounds, |
|
|
SCIP_Bool * |
boundtypes, |
|
|
SCIP_Real * |
newbounds, |
|
|
int * |
counts, |
|
|
int * |
issetvar, |
|
|
int |
nvars, |
|
|
int * |
foundbin, |
|
|
int * |
foundnonbin, |
|
|
int * |
implidx, |
|
|
int * |
nimplidx, |
|
|
SCIP_Real * |
lastbounds |
|
) |
| |
|
static |
collect variable bound information for a avraibel 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 |
| 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) |
| 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, |
|
|
SCIP_Bool |
value, |
|
|
SCIP_Real * |
bounds, |
|
|
SCIP_Bool * |
boundtypes, |
|
|
SCIP_Real * |
newbounds, |
|
|
int * |
counts, |
|
|
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 |
| 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) |
| 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 493 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(), SCIPvarGetNBinImpls(), SCIPvarGetNImpls(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by SCIPshrinkDisjunctiveVarSet().
| static void collectBinaryImplicationData |
( |
SCIP_VAR * |
var, |
|
|
int |
varidx, |
|
|
int |
pos, |
|
|
SCIP_Bool |
value, |
|
|
SCIP_Real * |
bounds, |
|
|
SCIP_Bool * |
boundtypes, |
|
|
SCIP_Real * |
newbounds, |
|
|
int * |
counts, |
|
|
int * |
issetvar, |
|
|
int |
nvars, |
|
|
int * |
foundbin, |
|
|
int * |
implidx, |
|
|
int * |
nimplidx |
|
) |
| |
|
static |
collect binary implication data for variable set reduction and global bound implications; only variable which have the vartype SCIP_VARTYPE_BINARY have binary implications, otherwise the implications are saved as variable bounds
- Parameters
-
| var | set variable |
| varidx | for lower bound set variable index, for upper bound set variable index
|
| pos | variables's position in bdchinfos |
| 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) |
| 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 |
| 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 700 of file presolve.c.
References MIN, NULL, SCIP_BOUNDTYPE_UPPER, SCIP_VARTYPE_BINARY, SCIPdebugMessage, SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNBinImpls(), SCIPvarGetProbindex(), SCIPvarGetType(), and SCIPvarGetUbGlobal().
Referenced by SCIPshrinkDisjunctiveVarSet().
| static void collectBinaryCliqueData |
( |
SCIP_VAR * |
var, |
|
|
int |
varidx, |
|
|
int |
pos, |
|
|
SCIP_Bool |
value, |
|
|
SCIP_Real * |
bounds, |
|
|
SCIP_Bool * |
boundtypes, |
|
|
SCIP_Real * |
newbounds, |
|
|
int * |
counts, |
|
|
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 |
| 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) |
| 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 |
| 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 800 of file presolve.c.
References MIN, NULL, SCIP_Bool, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMessage, SCIPvarGetCliques(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by SCIPshrinkDisjunctiveVarSet().
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().
|
