66 SCIP_Bool* boundtypes,
102 SCIP_Real* implcoefs;
103 SCIP_Real* implconsts;
126 if( !boundtypes[pos] )
131 if( counts[
varidx] == pos - nredvars )
138 countnonzeros[*ncountnonzeros] =
varidx;
140 newbounds[
varidx] = bounds[pos];
143 else if( newbounds[
varidx] > bounds[pos] )
145 lastbounds[*nimplidx] = newbounds[
varidx];
146 newbounds[
varidx] = bounds[pos];
153 *foundnonbin =
MIN(*foundnonbin,
varidx);
155 implidx[*nimplidx] =
varidx;
164 for(
w = nimpls - 1;
w >= 0; --
w )
175 if( implcoefs[
w] < 0.0 )
180 if( counts[idx] == pos - nredvars )
196 if( issetvar[idx] > 0 )
198 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g\n",
206 *foundbin =
MIN(*foundbin, idx);
208 if( counts[idx] == 1 )
211 countnonzeros[*ncountnonzeros] = idx;
215 implidx[*nimplidx] = idx;
228 newub = (bounds[pos] - implconsts[
w]) / implcoefs[
w];
233 if( issetvar[idx] > 0 && newub <= bounds[issetvar[idx] - 1] )
235 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
244 if( counts[idx] == 1 )
247 countnonzeros[*ncountnonzeros] = idx;
249 newbounds[idx] = newub;
252 else if( newbounds[idx] < newub )
254 lastbounds[*nimplidx] = newbounds[idx];
255 newbounds[idx] = newub;
260 *foundnonbin =
MIN(*foundnonbin, idx);
262 implidx[*nimplidx] = idx;
272 if( counts[idx] == pos - nredvars )
288 if( issetvar[idx] > 0 )
290 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g\n",
298 *foundbin =
MIN(*foundbin, idx);
300 if( counts[idx] == 1 )
303 countnonzeros[*ncountnonzeros] = idx;
307 implidx[*nimplidx] = idx;
320 newlb = (bounds[pos] - implconsts[
w]) / implcoefs[
w];
325 if( issetvar[idx] > 0 && newlb >= bounds[issetvar[idx] - 1] )
327 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
336 if( counts[idx] == 1 )
339 countnonzeros[*ncountnonzeros] = idx;
342 newbounds[idx] = newlb;
344 else if( newbounds[idx] > newlb )
346 lastbounds[*nimplidx] = newbounds[idx];
347 newbounds[idx] = newlb;
352 *foundnonbin =
MIN(*foundnonbin, idx);
354 implidx[*nimplidx] = idx;
368 if( counts[
varidx] == pos - nredvars )
375 countnonzeros[*ncountnonzeros] =
varidx;
377 newbounds[
varidx] = bounds[pos];
380 else if( newbounds[
varidx] < bounds[pos] )
382 lastbounds[*nimplidx] = newbounds[
varidx];
383 newbounds[
varidx] = bounds[pos];
390 *foundnonbin =
MIN(*foundnonbin,
varidx);
392 implidx[*nimplidx] =
varidx;
401 for(
w = nimpls - 1;
w >= 0; --
w )
412 if( implcoefs[
w] < 0.0 )
414 assert(counts[idx] <= pos - nredvars + 1);
417 if( counts[idx] == pos - nredvars )
430 if( issetvar[idx] > 0 )
432 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g\n",
440 *foundbin =
MIN(*foundbin, idx);
442 if( counts[idx] == 1 )
445 countnonzeros[*ncountnonzeros] = idx;
449 implidx[*nimplidx] = idx;
462 newlb = (bounds[pos] - implconsts[
w]) / implcoefs[
w];
464 if( issetvar[idx] > 0 && newlb >= bounds[issetvar[idx] - 1] )
466 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
475 if( counts[idx] == 1 )
478 countnonzeros[*ncountnonzeros] = idx;
481 newbounds[idx] = newlb;
483 else if( newbounds[idx] > newlb )
485 lastbounds[*nimplidx] = newbounds[idx];
486 newbounds[idx] = newlb;
491 *foundnonbin =
MIN(*foundnonbin, idx);
493 implidx[*nimplidx] = idx;
503 assert(counts[idx] <= pos - nredvars + 1);
505 if( counts[idx] == pos - nredvars )
518 if( issetvar[idx] > 0 )
520 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g\n",
528 *foundbin =
MIN(*foundbin, idx);
530 if( counts[idx] == 1 )
533 countnonzeros[*ncountnonzeros] = idx;
537 implidx[*nimplidx] = idx;
550 newub = (bounds[pos] - implconsts[
w]) / implcoefs[
w];
552 if( issetvar[idx] > 0 && newub <= bounds[issetvar[idx] - 1] )
554 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
563 if( counts[idx] == 1 )
566 countnonzeros[*ncountnonzeros] = idx;
569 newbounds[idx] = newub;
571 else if( newbounds[idx] < newub )
573 lastbounds[*nimplidx] = newbounds[idx];
574 newbounds[idx] = newub;
579 *foundnonbin =
MIN(*foundnonbin, idx);
581 implidx[*nimplidx] = idx;
605 SCIP_Bool* boundtypes,
606 SCIP_Real* newbounds,
631 SCIP_Real* lastbounds
657 if( issetvar[
varidx] > 0 )
660 SCIP_Real* implbounds;
691 assert(counts[idx] <= pos - nredvars + 1);
696 if( issetvar[idx] > 0 && bounds[issetvar[idx] - 1] >= implbounds[
w] )
698 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
700 "<=", implbounds[
w], bounds[issetvar[idx] - 1]);
710 if( counts[idx] == pos - nredvars && !redundant )
723 *foundbin =
MIN(*foundbin, idx);
725 if( counts[idx] == 1 )
728 countnonzeros[*ncountnonzeros] = idx;
734 *foundnonbin =
MIN(*foundnonbin, idx);
736 if( counts[idx] == 1 )
739 countnonzeros[*ncountnonzeros] = idx;
741 newbounds[idx] = implbounds[
w];
744 else if( newbounds[idx] < implbounds[
w] )
746 lastbounds[*nimplidx] = newbounds[idx];
747 newbounds[idx] = implbounds[
w];
753 implidx[*nimplidx] = idx;
761 assert(counts[idx] <= pos - nredvars + 1);
766 if( issetvar[idx] > 0 && bounds[issetvar[idx] - 1] <= implbounds[
w] )
768 SCIPdebugMsg(
scip,
"set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
770 ">=", implbounds[
w], bounds[issetvar[idx] - 1]);
780 if( counts[idx] == pos - nredvars && !redundant )
793 *foundbin =
MIN(*foundbin, idx);
795 if( counts[idx] == 1 )
798 countnonzeros[*ncountnonzeros] = idx;
804 *foundnonbin =
MIN(*foundnonbin, idx);
806 if( counts[idx] == 1 )
809 countnonzeros[*ncountnonzeros] = idx;
811 newbounds[idx] = implbounds[
w];
814 else if( newbounds[idx] > implbounds[
w] )
816 lastbounds[*nimplidx] = newbounds[idx];
817 newbounds[idx] = implbounds[
w];
823 implidx[*nimplidx] = idx;
842 SCIP_Bool* boundtypes,
843 SCIP_Real* newbounds,
868 SCIP_Bool* clqvalues;
891 if( issetvar[
varidx] > 0 )
894 if( counts[
varidx] == pos - nredvars )
902 countnonzeros[*ncountnonzeros] =
varidx;
906 implidx[*nimplidx] =
varidx;
931 assert(counts[idx] <= pos - nredvars + 1);
936 if( issetvar[idx] > 0 )
938 SCIPdebugMessage(
"set variable <%s> %s %g implies other set variable <%s> %s %g\n",
940 clqvalues[
w] ?
"<=" :
">=", clqvalues[
w] ? 0.0 : 1.0);
947 if( counts[idx] == pos - nredvars )
950 *foundbin =
MIN(*foundbin, idx);
952 if( counts[idx] == 1 )
955 countnonzeros[*ncountnonzeros] = idx;
959 implidx[*nimplidx] = idx;
972#define CLEARRATIO 0.8
1000 SCIP_Bool* boundtypes,
1002 SCIP_Bool* redundants,
1007 SCIP_Bool* setredundant,
1009 SCIP_Bool* glbinfeas,
1010 SCIP_Bool fullshortening
1013 SCIP_Real* newbounds;
1016 SCIP_Real* lastbounds;
1038 SCIP_Bool usebin =
TRUE;
1039 SCIP_Bool usenonbin =
TRUE;
1040 SCIP_Bool globalred =
TRUE;
1041 SCIP_Bool reducedset;
1043 SCIP_Bool implbinvarsexist;
1044 int start = INT_MAX;
1051 int maxcountnonzeros;
1082 maxcountnonzeros = (int)(2*nprobvars*
CLEARRATIO);
1085 for( v = 0; v <
nvars; ++v )
1106 SCIP_Bool infeasible;
1113 for( v = 0; v <
nvars; ++v )
1118 foundnonbin = INT_MAX;
1122 value = (!boundtypes[v]);
1135 collectBinaryCliqueData(
var,
varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts, countnonzeros,
1136 &ncountnonzeros, issetvar, nprobvars, &foundbin, implidx, &nimplidx);
1148 collectNonBinaryImplicationData(
scip,
var,
varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts,
1149 countnonzeros, &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1158 collectNonBinaryVBoundData(
scip,
var,
varidx, v, *nredvars, bounds, boundtypes, newbounds, counts, countnonzeros,
1159 &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1163 if( issetvar[
varidx] < 0 )
1176 for(
w = nimplidx - 1;
w >= 0; --
w )
1178 assert(implidx[
w] < 2 * nprobvars);
1179 assert(counts[implidx[
w]] == v - (*nredvars) + 1);
1181 --counts[implidx[
w]];
1183 if( implidx[
w] == countnonzeros[ncountnonzeros-1] && counts[implidx[
w]] == 0 )
1186 probidx = implidx[
w] < nprobvars ? implidx[
w] : implidx[
w] - nprobvars;
1189 newbounds[implidx[
w]] = lastbounds[
w];
1199 if( !fullshortening )
1202 if( foundbin < INT_MAX && !reducedset )
1205 if( foundnonbin < INT_MAX && !reducedset )
1210 globalred = globalred && (foundbin < INT_MAX || foundnonbin < INT_MAX);
1216 if( foundbin < INT_MAX && foundbin >= nprobvars )
1217 foundbin -= nprobvars;
1220 if( foundnonbin < INT_MAX && foundnonbin >= nprobvars )
1221 foundnonbin -= nprobvars;
1223 if( start > foundbin )
1226 if( start > foundnonbin )
1227 start = foundnonbin;
1233 if( !usebin && !usenonbin )
1244 for( v =
nvars - 1; v >= 0; --v )
1255 if( issetvar[
varidx] < 0 )
1259 redundants[v] =
TRUE;
1265 assert((*nredvars) == nreds);
1279 assert(start < nprobvars);
1282 for( v = start; v < nprobvars; ++v )
1284 probvar = probvars[v];
1290 if( counts[v] + (*nredvars) ==
nvars )
1307 if( issetvar[v] > 0 )
1308 *setredundant =
TRUE;
1333 if( issetvar[v] > 0 && newbounds[v] >= bounds[issetvar[v] - 1] )
1334 *setredundant =
TRUE;
1338 else if( counts[nprobvars + v] + (*nredvars) ==
nvars )
1355 if( issetvar[nprobvars + v] > 0 )
1356 *setredundant =
TRUE;
1361 int idx = nprobvars + v;
1383 if( issetvar[idx] > 0 && newbounds[idx] <= bounds[issetvar[idx] - 1] )
1384 *setredundant =
TRUE;
1392 for( v = 0; v <
nvars; ++v )
1403 if( ncountnonzeros >= maxcountnonzeros )
1409 while( --ncountnonzeros >= 0 )
1410 counts[countnonzeros[ncountnonzeros]] = 0;
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
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)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNVlbs(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
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 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 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)
methods commonly used for presolving
const char * SCIPprobGetName(SCIP_PROB *prob)
int SCIPprobGetNImplBinVars(SCIP_PROB *prob)
int SCIPprobGetNVars(SCIP_PROB *prob)
SCIP_VAR ** SCIPprobGetVars(SCIP_PROB *prob)
internal methods for storing and manipulating the main problem
public methods for implications, variable bounds, and cliques
public methods for message output
public methods for problem variables
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for the branch-and-bound tree
datastructures for block memory pools and memory buffers
SCIP main data structure.
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
internal methods for branch and bound tree
enum SCIP_BoundType SCIP_BOUNDTYPE
enum SCIP_Retcode SCIP_RETCODE