73#define PRESOL_NAME "tworowbnd"
74#define PRESOL_DESC "do bound tigthening by using two rows"
75#define PRESOL_PRIORITY -2000
76#define PRESOL_MAXROUNDS 0
77#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE
79#define DEFAULT_ENABLECOPY TRUE
80#define DEFAULT_MAXCONSIDEREDNONZEROS 100
81#define DEFAULT_MAXRETRIEVEFAILS 1000
82#define DEFAULT_MAXCOMBINEFAILS 1000
83#define DEFAULT_MAXHASHFAC 10
84#define DEFAULT_MAXPAIRFAC 1
97 int maxconsiderednonzeros;
123 uint64_t
a = (uint64_t)(
long)rowpair->
row1idx;
124 uint64_t
b = (uint64_t)(
long)rowpair->
row2idx;
125 return (
void*)((
a << 32) |
b);
136 return (
int)(hash >> 1);
151 if( (*pos) >= (*listsize) )
156 (*listsize) = newsize;
159 (*hashlist)[(*pos)] = hash;
160 (*rowidxlist)[(*pos)] = rowidx;
183 while(
i < len && list[
i] == list[
i - 1] )
220#ifdef SCIP_DEBUG_SINGLEROWLP
229 for(
i = 0;
i < len;
i++)
272 mincost =
MIN(mincost,
c[
i] /
a[
i]);
273 maxgain =
MAX(maxgain,
c[
i] /
a[
i]);
300 mincost =
MIN(mincost,
c[
i]/
a[
i]);
312 maxgain =
MAX(maxgain,
c[
i] /
a[
i]);
380#ifdef SCIP_DEBUG_SINGLEROWLP
381 SCIPdebugMsg(
scip,
"After preprocessing: obj = %g, b = %g, nvars = %d, mincost = %g, maxgain = %g\n", (*
obj),
b,
nvars, mincost, maxgain);
404 (*obj) +=
c[
i] *
a[
i];
409 (*obj) += mincost *
b;
441 (*obj) +=
c[
i] *
a[
i];
453 (*obj) += maxgain *
b;
459#ifdef SCIP_DEBUG_SINGLEROWLP
468 (*obj) += mincost *
b;
481#ifdef SCIP_DEBUG_SINGLEROWLP
488#ifdef SCIP_DEBUG_SINGLEROWLP
495 for(
i = 0;
i < k;
i++ )
497 (*obj) +=
c[
i] *
a[
i];
501#ifdef SCIP_DEBUG_SINGLEROWLP
517#ifdef SCIP_DEBUG_SINGLEROWLP
520 (*obj) += mincost *
b;
619 while(
i < row1len && j < row2len )
621 idx1 = row1idxptr[
i];
622 idx2 = row2idxptr[j];
626 coriginal[
nvars] = row1valptr[
i];
627 aoriginal[
nvars] = row2valptr[j];
628 newlbsoriginal[
nvars] = lbs[idx1];
629 newubsoriginal[
nvars] = ubs[idx1];
630 cangetbnd[idx1] =
FALSE;
635 ubs[idx1], row1valptr[
i], row2valptr[j],
nvars);
640 else if( idx1 < idx2 )
647 maxact -= row1valptr[
i] * ubs[idx1];
652 minact -= row1valptr[
i] * lbs[idx1];
659 maxact -= row1valptr[
i] * lbs[idx1];
664 minact -= row1valptr[
i] * ubs[idx1];
666 cangetbnd[idx1] =
TRUE;
668 if( maxinfs > 1 && mininfs > 1 )
675 SCIPdebugMsg(
scip,
"%g <= (%s) <= %g has coefs %g and 0.0, minact = %g, maxact = %g\n",
677 ubs[idx1], row1valptr[
i], minact, maxact);
682 coriginal[
nvars] = 0.0;
683 aoriginal[
nvars] = row2valptr[j];
684 newlbsoriginal[
nvars] = lbs[idx2];
685 newubsoriginal[
nvars] = ubs[idx2];
686 cangetbnd[idx2] =
FALSE;
691 ubs[idx2], row2valptr[j],
nvars);
698 idx1 = row1idxptr[
i];
704 maxact -= row1valptr[
i] * ubs[idx1];
709 minact -= row1valptr[
i] * lbs[idx1];
716 maxact -= row1valptr[
i] * lbs[idx1];
721 minact -= row1valptr[
i] * ubs[idx1];
723 cangetbnd[idx1] =
TRUE;
725 SCIPdebugMsg(
scip,
"%g <= (%s) <= %g has coefs %g and 0.0, minact = %g, maxact = %g\n",
727 ubs[idx1], row1valptr[
i], minact, maxact);
733 idx2 = row2idxptr[j];
734 coriginal[
nvars] = 0.0;
735 aoriginal[
nvars] = row2valptr[j];
736 newlbsoriginal[
nvars] = lbs[idx2];
737 newubsoriginal[
nvars] = ubs[idx2];
742 ubs[idx2], row2valptr[j],
nvars);
755 maxswapsolvable =
FALSE;
756 minswapsolvable =
FALSE;
762 acopy[
i] = aoriginal[
i];
763 ccopy[
i] = -coriginal[
i];
764 newlbscopy[
i] = newlbsoriginal[
i];
765 newubscopy[
i] = newubsoriginal[
i];
768 ccopy, newlbscopy, newubscopy,
nvars, &maxobj, &maxsolvable) );
775 if( mininfs == 0 || (mininfs == 1 && swaprow1) )
780 acopy[
i] = aoriginal[
i];
781 ccopy[
i] = coriginal[
i];
782 newlbscopy[
i] = newlbsoriginal[
i];
783 newubscopy[
i] = newubsoriginal[
i];
786 ccopy, newlbscopy, newubscopy,
nvars, &
minobj, &minsolvable) );
800 acopy[
i] = -aoriginal[
i];
801 ccopy[
i] = -coriginal[
i];
802 newlbscopy[
i] = newlbsoriginal[
i];
803 newubscopy[
i] = newubsoriginal[
i];
806 ccopy, newlbscopy, newubscopy,
nvars, &maxswapobj, &maxswapsolvable) );
813 if( mininfs == 0 || (mininfs == 1 && swaprow1) )
818 acopy[
i] = -aoriginal[
i];
819 ccopy[
i] = coriginal[
i];
820 newlbscopy[
i] = newlbsoriginal[
i];
821 newubscopy[
i] = newubsoriginal[
i];
824 ccopy, newlbscopy, newubscopy,
nvars, &minswapobj, &minswapsolvable) );
832 if( maxinfs <= 1 && (maxsolvable || maxswapsolvable) )
836 if( maxsolvable && maxswapsolvable )
838 else if( maxsolvable )
846 (*infeasible) =
TRUE;
851 else if( maxinfs == 0 )
853 for(
i = 0;
i < row1len;
i++ )
855 idx1 = row1idxptr[
i];
856 if( cangetbnd[idx1] )
863 newbnd =
SCIPceil(
scip, (activity + row1valptr[
i] * ubs[idx1]) / row1valptr[
i]);
865 newbnd = (activity + row1valptr[
i] * ubs[idx1]) / row1valptr[
i];
869#ifdef SCIP_DEBUG_BOUNDS
883 newbnd =
SCIPfloor(
scip, (activity + row1valptr[
i] * lbs[idx1]) / row1valptr[
i]);
885 newbnd = (activity + row1valptr[
i] * lbs[idx1]) / row1valptr[
i];
889#ifdef SCIP_DEBUG_BOUNDS
904 for(
i = 0;
i < row1len;
i++ )
906 idx1 = row1idxptr[
i];
907 if( cangetbnd[idx1] )
916 newbnd = activity / row1valptr[
i];
920#ifdef SCIP_DEBUG_BOUNDS
936 newbnd = activity / row1valptr[
i];
940#ifdef SCIP_DEBUG_BOUNDS
957 if( mininfs <= 1 && (minsolvable || minswapsolvable) )
962 if( minsolvable && minswapsolvable )
964 else if( minsolvable )
972 (*infeasible) =
TRUE;
977 else if( mininfs == 0 )
979 for(
i = 0;
i < row1len;
i++ )
981 idx1 = row1idxptr[
i];
982 if( cangetbnd[idx1] )
989 newbnd =
SCIPceil(
scip, (activity - row1valptr[
i] * ubs[idx1]) / (-row1valptr[
i]));
991 newbnd = (activity - row1valptr[
i] * ubs[idx1]) / (-row1valptr[
i]);
995#ifdef SCIP_DEBUG_BOUNDS
1010 newbnd =
SCIPfloor(
scip, (activity - row1valptr[
i] * lbs[idx1]) / (-row1valptr[
i]));
1012 newbnd = (activity - row1valptr[
i] * lbs[idx1]) / (-row1valptr[
i]);
1016#ifdef SCIP_DEBUG_BOUNDS
1031 for(
i = 0;
i < row1len;
i++ )
1033 idx1 = row1idxptr[
i];
1034 if( cangetbnd[idx1] )
1044 newbnd = activity / (-row1valptr[
i]);
1048#ifdef SCIP_DEBUG_BOUNDS
1064 newbnd = activity / (-row1valptr[
i]);
1068#ifdef SCIP_DEBUG_BOUNDS
1110#ifdef SCIP_DEBUG_2RB
1134 coriginal, ccopy, cangetbnd, lbs, ubs, newlbsoriginal, newlbscopy,
1135 newubsoriginal, newubscopy, success, &infeasible) );
1139 coriginal, ccopy, cangetbnd, lbs, ubs, newlbsoriginal, newlbscopy,
1140 newubsoriginal, newubscopy, success, &infeasible) );
1202 findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end);
1203 findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end);
1206 if( hashlist1[block1start] == hashlist2[block2start] )
1208 for(
i = block1start;
i < block1end;
i++ )
1210 for( j = block2start; j < block2end; j++ )
1212 if( rowidxlist1[
i] != rowidxlist2[j] )
1214 rowpair.
row1idx =
MIN(rowidxlist1[
i], rowidxlist2[j]);
1215 rowpair.
row2idx =
MAX(rowidxlist1[
i], rowidxlist2[j]);
1228 swaprow1, swaprow2, newlbs, newubs, &success) );
1238 if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails )
1243 else if( retrievefails < presoldata->maxretrievefails )
1261 if( block1end < lenhashlist1 && block2end < lenhashlist2 )
1263 findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end);
1264 findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end);
1269 else if( hashlist1[block1start] < hashlist2[block2start] && block1end < lenhashlist1 )
1270 findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end);
1271 else if( hashlist1[block1start] > hashlist2[block2start] && block2end < lenhashlist2 )
1272 findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end);
1300 if( presoldata->enablecopy )
1331 presoldata->nchgbnds = 0;
1332 presoldata->nuselessruns = 0;
1396 if( presoldata->nuselessruns >= 5 )
1403 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
1448 for(
i = 0;
i < nrows;
i++)
1450 if( ((
SCIP_Longint)pospp) + posmm + pospm + posmp > maxhashes )
1457 for( j = 0; j < maxlen; j++)
1459 for( k = j+1; k < maxlen; k++)
1503#ifdef SCIP_DEBUG_HASHING
1505 for(
i = 0;
i < pospp;
i++)
1508 for(
i = 0;
i < posmm;
i++)
1511 for(
i = 0;
i < pospm;
i++)
1514 for(
i = 0;
i < posmp;
i++)
1517 SCIPdebugMsg(
scip,
"hashlist sizes: pp %d, mm %d, pm %d, mp %d \n", pospp, posmm, pospm, posmp);
1524#ifdef SCIP_DEBUG_HASHING
1526 for(
i = 0;
i < pospp;
i++)
1529 for(
i = 0;
i < posmm;
i++)
1532 for(
i = 0;
i < pospm;
i++)
1535 for(
i = 0;
i < posmp;
i++)
1549 newlbs[
i] = oldlbs[
i];
1550 newubs[
i] = oldubs[
i];
1554 if( pospp > 0 && posmm > 0 )
1558 rowidxlistmm, newlbs, newubs) );
1562 if( pospm > 0 && posmp > 0 )
1566 rowidxlistmp, newlbs, newubs) );
1570 oldnchgbds = *nchgbds;
1571 oldnfixedvars = *nfixedvars;
1609 if( bndwastightened )
1626 if( bndwastightened )
1635 if( *nchgbds > oldnchgbds || *nfixedvars > oldnfixedvars )
1638 presoldata->nuselessruns = 0;
1640 else if( infeasible )
1646 presoldata->nuselessruns++;
1687 presolExecTworowbnd,
1698 "presolving/tworowbnd/enablecopy",
1699 "should tworowbnd presolver be copied to sub-SCIPs?",
1702 "presolving/tworowbnd/maxconsiderednonzeros",
1703 "maximal number of considered non-zeros within one row (-1: no limit)",
1706 "presolving/tworowbnd/maxretrievefails",
1707 "maximal number of consecutive useless hashtable retrieves",
1710 "presolving/tworowbnd/maxcombinefails",
1711 "maximal number of consecutive useless row combines",
1714 "presolving/tworowbnd/maxhashfac",
1715 "Maximum number of hashlist entries as multiple of number of rows in the problem (-1: no limit)",
1718 "presolving/tworowbnd/maxpairfac",
1719 "Maximum number of processed row pairs as multiple of the number of rows in the problem (-1: no limit)",
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisStopped(SCIP *scip)
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
#define SCIPhashTwo(a, b)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPincludePresolTworowbnd(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol,)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(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)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
void SCIPselectWeightedReal(SCIP_Real *realarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
assert(minobj< SCIPgetCutoffbound(scip))
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
const char * SCIPmatrixGetColName(SCIP_MATRIX *matrix, int col)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define DEFAULT_MAXCONSIDEREDNONZEROS
#define DEFAULT_MAXHASHFAC
#define DEFAULT_MAXCOMBINEFAILS
#define DEFAULT_MAXRETRIEVEFAILS
#define DEFAULT_MAXPAIRFAC
#define DEFAULT_ENABLECOPY
static SCIP_RETCODE addEntry(SCIP *scip, int *pos, int *listsize, int **hashlist, int **rowidxlist, int hash, int rowidx)
static SCIP_RETCODE transformAndSolve(SCIP *scip, SCIP_MATRIX *matrix, int row1idx, int row2idx, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *aoriginal, SCIP_Real *acopy, SCIP_Real *coriginal, SCIP_Real *ccopy, SCIP_Bool *cangetbnd, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *newlbsoriginal, SCIP_Real *newlbscopy, SCIP_Real *newubsoriginal, SCIP_Real *newubscopy, SCIP_Bool *success, SCIP_Bool *infeasible)
static int hashIndexPair(int idx1, int idx2)
static SCIP_RETCODE solveSingleRowLP(SCIP *scip, SCIP_Real *a, SCIP_Real b, SCIP_Real *c, SCIP_Real *lbs, SCIP_Real *ubs, int len, SCIP_Real *obj, SCIP_Bool *solvable)
static SCIP_RETCODE processHashlists(SCIP *scip, SCIP_PRESOLDATA *presoldata, SCIP_MATRIX *matrix, int *hashlist1, int *hashlist2, int lenhashlist1, int lenhashlist2, int *rowidxlist1, int *rowidxlist2, SCIP_Real *newlbs, SCIP_Real *newubs)
static void * encodeRowPair(ROWPAIR *rowpair)
static void findNextBlock(int *list, int len, int *start, int *end)
static SCIP_RETCODE applyLPboundTightening(SCIP *scip, SCIP_MATRIX *matrix, int row1, int row2, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success)
do bound tightening by using two rows
public methods for matrix
struct SCIP_Matrix SCIP_MATRIX
struct SCIP_HashSet SCIP_HASHSET
#define SCIP_DECL_PRESOLCOPY(x)
struct SCIP_PresolData SCIP_PRESOLDATA
#define SCIP_DECL_PRESOLFREE(x)
struct SCIP_Presol SCIP_PRESOL
#define SCIP_DECL_PRESOLINIT(x)
#define SCIP_DECL_PRESOLEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS