61 #define SEPA_NAME "zerohalf" 62 #define SEPA_DESC "{0,1/2}-cuts separator" 63 #define SEPA_PRIORITY -6000 65 #define SEPA_MAXBOUNDDIST 0.0 66 #define SEPA_USESSUBSCIP TRUE 67 #define SEPA_DELAY FALSE 69 #define DEFAULT_MAXROUNDS 5 70 #define DEFAULT_MAXROUNDSROOT 10 71 #define DEFAULT_MAXSEPACUTS 50 72 #define DEFAULT_MAXSEPACUTSROOT 500 73 #define DEFAULT_DYNAMICCUTS TRUE 74 #define DEFAULT_DECOMPOSEPROBLEM FALSE 75 #define DEFAULT_MAXDEPTH -1 76 #define DEFAULT_MINVIOLATION 0.30 77 #define DEFAULT_FORCECUTSTOLP FALSE 78 #define DEFAULT_FORCECUTSTOSEPASTORE FALSE 80 #define DEFAULT_MAXCUTS 100 82 #define DEFAULT_MAXCUTSROOT 1000 84 #define DEFAULT_SUBSCIPOBJECTIVE 'v' 85 #define DEFAULT_RELAXCONTVARS FALSE 86 #define DEFAULT_SCALEFRACCOEFFS TRUE 87 #define DEFAULT_SUBSCIPSETTINGS "-" 88 #define DEFAULT_SUBSCIPSOLLIMIT -1 89 #define DEFAULT_SUBSCIPUSEALLSOLS TRUE 91 #define DEFAULT_PPDELTA 0.500 92 #define DEFAULT_SUBSCIPOBJPEN 0.001 94 #define DEFAULT_PPMETHODS "CXGXIM" 95 #define DEFAULT_SEPAMETHODS "2g" 96 #define DEFAULT_MAXNCALLS -1LL 97 #define DEFAULT_IGNOREPREVIOUSZHCUTS FALSE 98 #define DEFAULT_ONLYORIGROWS FALSE 99 #define DEFAULT_USEZHCUTPOOL TRUE 100 #define DEFAULT_DELAYEDCUTS TRUE 101 #define DEFAULT_MAXTESTDELTA 10 102 #define DEFAULT_TRYNEGSCALING TRUE 105 #define ORTHOFUNC 'e' 109 #define NNONZOFFSET 500 110 #define BOUNDSWITCH 0.50 112 #define ALLOWLOCAL TRUE 113 #define FIXINTEGRALRHS TRUE 114 #define BOUNDSFORTRANS NULL 115 #define BOUNDTYPESFORTRANS NULL 116 #define MAXWEIGHTRANGE 10000.00 122 #define MAXSCALE 1000.0 125 #define USEVARBOUNDS TRUE 180 #define ISEVEN(scip, value) (SCIPisEQ((scip) , SCIPfloor(scip , (value) / 2) , (value) / 2)) 181 #define ISODD(scip, value) (!(ISEVEN((scip), (value)))) 182 #define XOR(bool1, bool2) ((bool1) ^ (bool2)) 183 #define DIV(value1, powerof2value) (((unsigned int)(value1)) / ((unsigned int)(powerof2value))) 184 #define MOD(value1, powerof2value) (((unsigned int)(value1)) % ((unsigned int)(powerof2value))) 186 #ifndef BMSmoveMemoryArray 188 #define BMSmoveMemoryArray(ptr, source, num) \ 190 size_t size__ = (num) * sizeof(*(ptr)); \ 193 assert((void*)(ptr) != NULL); \ 194 assert((void*)(source) != NULL); \ 195 memmove((void*)(ptr), (void*)(source), size__); \ 200 #ifdef ZEROHALF__PRINT_STATISTICS 202 #define ZEROHALFstatistics(x) x 203 #define ZEROHALFstatisticsMessage printf("#### ") ; printf 204 #define ZEROHALFcreateNewTimer(timervar) SCIP_CALL(SCIPcreateClock(scip, &timervar)) 205 #define ZEROHALFcreateTimer(timervar) SCIP_CALL(SCIPcreateClock(scip, &timervar)) 206 #define ZEROHALFfreeTimer(timervar) SCIP_CALL(SCIPfreeClock(scip, &timervar)) 207 #define ZEROHALFresetTimer(timervar) SCIP_CALL(SCIPresetClock(scip, timervar)) 208 #define ZEROHALFstartTimer(timervar) SCIP_CALL(SCIPstartClock(scip, timervar)) 209 #define ZEROHALFstopTimer(timervar) SCIP_CALL(SCIPstopClock(scip, timervar)) 210 #define ZEROHALFevalTimer(timervar) (SCIPgetClockTime(scip, timervar)) 215 #define ZEROHALFstatistics(x) 216 #define ZEROHALFstatisticsMessage while( FALSE ) printf 217 #define ZEROHALFcreateNewTimer(timervar) 218 #define ZEROHALFcreateTimer(timervar) 219 #define ZEROHALFfreeTimer(timervar) 220 #define ZEROHALFresetTimer(timervar) 221 #define ZEROHALFstartTimer(timervar) 222 #define ZEROHALFstopTimer(timervar) 223 #define ZEROHALFevalTimer(timervar) (0.0) 234 #define IRRELEVANT -1 237 #define ZERO_ROW -100 238 #define IDENT_TO_ROW_WITH_SMALLER_SLACK -101 239 #define SLACK_GREATER_THAN_MAXSLACK -102 240 #define DEFINES_VIOLATED_ZEROHALF_CUT -103 242 #define ROW_IN_SUBPROB_WITHOUT_ODD_RHS -104 244 #define NONEXISTENT_ROW -105 245 #define NO_RELEVANT_COLUMNS -106 246 #define SLACK_GREATER_THAN_MSL_MINUS_SODD -107 248 #define LARGE_COL_EXISTS -108 253 #define ZERO_COLUMN -200 254 #define IDENT_TO_ANOTHER_COLUMN -201 255 #define ZERO_LP_SOL -202 256 #define LP_SOL_EQUALS_EVEN_LB -203 257 #define LP_SOL_EQUALS_ODD_LB -204 258 #define LP_SOL_EQUALS_EVEN_UB -205 259 #define LP_SOL_EQUALS_ODD_UB -206 260 #define SINGLETON_COLUMN -207 261 #define CONTINUOUS_VARIABLE -208 262 #define SMALL_FRACSOL_HEUR -209 263 #define ALL_MATRIX_ROWS_DELETED -210 265 #define COLUMN_IN_SUBPROB_WITHOUT_ODD_RHS -211 274 #define BITARRAYBASETYPE unsigned int 275 #define BITARRAYBITMASKTYPE BITARRAYBASETYPE 284 #define BITARRAY BITARRAYBASETYPE* 287 #define BITMASK(pos) ((unsigned int)(1 << (pos))) 290 #define BITSET(var, pos) (var) |= BITMASK(pos) 293 #define BITISSET(var, pos) (var & BITMASK(pos)) 296 #define BITARRAYBITSET(barray, pos) BITSET(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \ 297 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 300 #define BITARRAYBITISSET(barray, pos) BITISSET(barray[DIV(pos,Zerohalf_bitarraybasetypesize_nbits)], \ 301 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 304 #define BITARRAYCLEAR(barray, barraysize) BMSclearMemoryArray(barray,barraysize) 307 #define GETREQUIREDBITARRAYSIZE(nvalstostore) \ 308 ((((unsigned int)(nvalstostore)) % (Zerohalf_bitarraybasetypesize_nbits) == 0) \ 309 ? (((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) \ 310 : ((((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) + 1)) 313 #define GETBITARRAYINDEX(pos) DIV((pos),Zerohalf_bitarraybasetypesize_nbits) 316 #define GETBITARRAYMASK(pos) BITMASK(MOD((pos),Zerohalf_bitarraybasetypesize_nbits)) 319 #define BITARRAYSFOREACH(barray1, barray2, size, op) \ 322 for( idx__ = 0 ; idx__ < (size) ; ++idx__) \ 324 barray2[idx__] op barray1[idx__]; \ 329 #define BITARRAYSXOR(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,^=) 332 #define BITARRAYSAREEQUAL(barray1, barray2, size) \ 333 (memcmp((void*)(barray1), (void*)(barray2), (size_t)((size) * (Zerohalf_bitarraybasetypesize))) == 0) 337 #define BITCLEAR(var, pos) (var) &= ~BITMASK(pos) 340 #define BITFLIP(var, pos) (var) ^= BITMASK(pos) 343 #define BITARRAYBITCLEAR(barray, pos) BITCLEAR(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \ 344 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 347 #define BITARRAYBITFLIP(barray, pos) BITFLIP(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \ 348 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 351 #define BITARRAYSAND(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,&=) 354 #define BITARRAYSOR(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,|=) 357 #define BITARRAYSNOT(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,= ~) 395 char* subscipsettings;
396 char subscipobjective;
421 int* nzerohalfcutsalgo;
426 struct Zerohalf_SubLPData
437 typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA;
441 struct Zerohalf_LPData
451 ZEROHALF_SUBLPDATA** subproblems;
458 int* subproblemsindexofrow;
460 int* rrowsindexofleftrow;
461 int* rrowsindexofrightrow;
464 int* subproblemsindexofcol;
466 int* rcolsindexofcol;
503 struct Zerohalf_AuxIPData
523 typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA;
527 struct Zerohalf_Mod2Data
529 ZEROHALF_SUBLPDATA* relatedsubproblem;
539 int rowsbitarraysize;
540 int rowaggregationsbitarraysize;
557 struct Zerohalf_CutData
559 ZEROHALF_SUBLPDATA* relatedsubproblem;
588 struct Zerohalf_AuxGraph_Node;
591 struct Zerohalf_AuxGraph_Node
603 struct Zerohalf_AuxGraph
609 typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH;
621 ZEROHALF_SUBLPDATA** subproblem
624 assert(scip !=
NULL);
625 assert(subproblem !=
NULL);
629 (*subproblem)->rrowsrhs =
NULL;
630 (*subproblem)->rrowsslack =
NULL;
631 (*subproblem)->nrrows = 0;
633 (*subproblem)->rcols =
NULL;
634 (*subproblem)->rcolslbslack =
NULL;
635 (*subproblem)->rcolsubslack =
NULL;
636 (*subproblem)->nrcols = 0;
646 ZEROHALF_SUBLPDATA** subproblem
649 assert(scip !=
NULL);
650 assert(subproblem !=
NULL);
651 assert(*subproblem !=
NULL);
653 if( (*subproblem)->rrows !=
NULL )
657 if( (*subproblem)->rrowsrhs !=
NULL )
661 if( (*subproblem)->rrowsslack !=
NULL )
665 if( (*subproblem)->rcols !=
NULL )
669 if( (*subproblem)->rcolslbslack !=
NULL )
673 if( (*subproblem)->rcolsubslack !=
NULL )
678 (*subproblem) =
NULL;
689 assert(scip !=
NULL);
690 assert(lpdata !=
NULL);
694 (*lpdata)->rows =
NULL;
695 (*lpdata)->cols =
NULL;
697 (*lpdata)->subproblems =
NULL;
698 (*lpdata)->nsubproblems = 0;
700 (*lpdata)->intscalarsleftrow =
NULL;
701 (*lpdata)->intscalarsrightrow =
NULL;
703 (*lpdata)->subproblemsindexofrow =
NULL;
704 (*lpdata)->rrowsindexofleftrow =
NULL;
705 (*lpdata)->rrowsindexofrightrow =
NULL;
707 (*lpdata)->subproblemsindexofcol =
NULL;
708 (*lpdata)->rcolsindexofcol =
NULL;
710 (*lpdata)->bestlbidxofcol =
NULL;
711 (*lpdata)->bestubidxofcol =
NULL;
726 assert(scip !=
NULL);
727 assert(lpdata !=
NULL);
731 assert(((*lpdata)->nsubproblems == 0 && (*lpdata)->subproblems ==
NULL)
732 || ((*lpdata)->nsubproblems > 0 && (*lpdata)->subproblems !=
NULL));
734 if( (*lpdata)->subproblems !=
NULL )
736 for( sp = 0 ; sp < (*lpdata)->nsubproblems ; ++sp )
737 if( (*lpdata)->subproblems[sp] !=
NULL )
742 if( (*lpdata)->intscalarsleftrow !=
NULL )
746 if( (*lpdata)->intscalarsrightrow !=
NULL )
750 if( (*lpdata)->subproblemsindexofrow !=
NULL )
754 if( (*lpdata)->rrowsindexofleftrow !=
NULL )
758 if( (*lpdata)->rrowsindexofrightrow !=
NULL )
762 if( (*lpdata)->subproblemsindexofcol !=
NULL )
766 if( (*lpdata)->rcolsindexofcol !=
NULL )
770 if( (*lpdata)->bestlbidxofcol !=
NULL )
774 if( (*lpdata)->bestubidxofcol !=
NULL )
792 assert(scip !=
NULL);
793 assert(mod2data !=
NULL);
797 (*mod2data)->relatedsubproblem =
NULL;
799 (*mod2data)->rows =
NULL;
800 (*mod2data)->rowaggregations =
NULL;
801 (*mod2data)->rhs =
NULL;
803 (*mod2data)->slacks =
NULL;
804 (*mod2data)->fracsol =
NULL;
806 (*mod2data)->rowstatistics =
NULL;
807 (*mod2data)->colstatistics =
NULL;
809 (*mod2data)->rowsind =
NULL;
810 (*mod2data)->colsind =
NULL;
825 assert(scip !=
NULL);
826 assert(mod2data !=
NULL);
829 if( (*mod2data)->rows !=
NULL )
831 for( i = 0 ; i < (*mod2data)->nrows ; ++i)
832 if( (*mod2data)->rows[i] !=
NULL )
839 if( (*mod2data)->rowaggregations !=
NULL )
841 for( i = 0 ; i < (*mod2data)->nrows ; ++i)
842 if( (*mod2data)->rowaggregations[i] !=
NULL )
849 if( (*mod2data)->rhs !=
NULL )
853 if( (*mod2data)->slacks !=
NULL )
857 if( (*mod2data)->fracsol !=
NULL )
861 if( (*mod2data)->rowstatistics !=
NULL )
865 if( (*mod2data)->colstatistics !=
NULL )
869 if( (*mod2data)->rowsind !=
NULL )
873 if( (*mod2data)->colsind !=
NULL )
888 ZEROHALF_AUXIPDATA** auxipdata
891 assert(scip !=
NULL);
892 assert(auxipdata !=
NULL);
896 (*auxipdata)->subscip =
NULL;
898 (*auxipdata)->v =
NULL;
899 (*auxipdata)->y =
NULL;
900 (*auxipdata)->r =
NULL;
901 (*auxipdata)->q =
NULL;
903 (*auxipdata)->feasipcons =
NULL;
904 (*auxipdata)->oddrhscons =
NULL;
905 (*auxipdata)->columnsumcons =
NULL;
915 ZEROHALF_AUXIPDATA** auxipdata
918 assert(scip !=
NULL);
919 assert(auxipdata !=
NULL);
920 assert(*auxipdata !=
NULL);
922 if( (*auxipdata)->subscip !=
NULL )
927 if( (*auxipdata)->v !=
NULL )
931 if( (*auxipdata)->y !=
NULL )
935 if( (*auxipdata)->r !=
NULL )
939 if( (*auxipdata)->columnsumcons !=
NULL )
955 ZEROHALF_SUBLPDATA* relatedsubproblem,
962 assert(scip !=
NULL);
963 assert(cutdata !=
NULL);
964 assert(nrrowsincut >= 0);
965 assert(nrowsincut >= 0);
969 (*cutdata)->relatedsubproblem = relatedsubproblem;
970 (*cutdata)->relatedmod2data = relatedmod2data;
972 (*cutdata)->cut =
NULL;
974 (*cutdata)->success =
FALSE;
975 (*cutdata)->isfeasviolated =
FALSE;
976 (*cutdata)->islocal =
TRUE;
978 (*cutdata)->activity = 0.0;
979 (*cutdata)->rhs = 0.0;
980 (*cutdata)->norm = 0.0;
981 (*cutdata)->efficacy = 0.0;
982 (*cutdata)->violation = 0.0;
983 (*cutdata)->cutrank = 0;
984 (*cutdata)->nnonz = 0;
986 (*cutdata)->nrrowsincut = nrrowsincut;
987 (*cutdata)->nrowsincut = nrowsincut;
988 (*cutdata)->separatedby = separatedby;
989 (*cutdata)->addedtolp =
FALSE;
1002 assert(scip !=
NULL);
1003 assert(cutdata !=
NULL);
1004 assert(*cutdata !=
NULL);
1024 assert(scip !=
NULL);
1025 assert(node !=
NULL);
1029 (*node)->neighbors =
NULL;
1030 (*node)->edgeweights =
NULL;
1031 (*node)->relatedrows =
NULL;
1032 (*node)->nneighbors = 0;
1034 (*node)->distance = -1.0;
1035 (*node)->previous =
NULL;
1048 assert(scip !=
NULL);
1049 assert(node !=
NULL);
1051 if( (*node)->neighbors !=
NULL )
1055 if( (*node)->edgeweights !=
NULL )
1059 if( (*node)->relatedrows !=
NULL )
1074 ZEROHALF_AUXGRAPH** auxgraph
1077 assert(scip !=
NULL);
1078 assert(auxgraph !=
NULL);
1082 (*auxgraph)->nodes =
NULL;
1083 (*auxgraph)->nodecopies =
NULL;
1085 (*auxgraph)->nnodes = 0;
1095 ZEROHALF_AUXGRAPH** auxgraph
1100 assert(scip !=
NULL);
1101 assert(auxgraph !=
NULL);
1103 if( (*auxgraph)->nodes !=
NULL )
1105 assert((*auxgraph)->nnodes > 0);
1106 for( n = 0; n < (*auxgraph)->nnodes ; ++n )
1107 if( (*auxgraph)->nodes[n] !=
NULL )
1114 if( (*auxgraph)->nodecopies !=
NULL )
1116 assert((*auxgraph)->nnodes > 0);
1117 for( n = 0; n < (*auxgraph)->nnodes ; ++n )
1118 if( (*auxgraph)->nodecopies[n] !=
NULL )
1139 char* getconstantname(
1156 #ifdef WITHDECOMPOSE 1157 case ROW_IN_SUBPROB_WITHOUT_ODD_RHS:
1190 #ifdef WITHDECOMPOSE 1191 case COLUMN_IN_SUBPROB_WITHOUT_ODD_RHS:
1204 #ifdef ZEROHALF__PRINT_STATISTICS 1215 int nirrelevantrows;
1218 int nirrelevantcols;
1221 int nnonexistingrows;
1223 assert(lpdata !=
NULL);
1226 nirrelevantrows = 0;
1227 nnonexistingrows = 0;
1229 nirrelevantcols = 0;
1232 for( i = 0 ; i < lpdata->nrows ; ++i)
1234 if( lpdata->rrowsindexofleftrow[i] >= 0 )
1237 if( lpdata->rrowsindexofleftrow[i] < -199 )
1244 if( lpdata->rrowsindexofrightrow[i] >= 0 )
1247 if( lpdata->rrowsindexofrightrow[i] < -199 )
1256 for( i = 0 ; i < lpdata->ncols ; ++i)
1258 if( lpdata->rcolsindexofcol[i] >= 0 )
1261 if( lpdata->rcolsindexofcol[i] == -1 )
1264 if( lpdata->rcolsindexofcol[i] > -200 || lpdata->rcolsindexofcol[i] < -299 )
1270 nrows = nrelevantrows + nirrelevantrows - nnonexistingrows;
1271 ncols = nrelevantcols + nirrelevantcols;
1273 ZEROHALFstatisticsMessage(
"\n");
1274 ZEROHALFstatisticsMessage(
" | ----- lp data ----- | --- (reductions) -- | --- problem data -- | -lpdata- | -(red.)- | -probd.- | --------\n");
1275 ZEROHALFstatisticsMessage(
" | nrows | ncols | ndelrows | ndelcols | nrrows | nrcols | nvarbnds | ndlvbnds | nvarbnds | \n");
1276 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d |\n",
1277 "READING LPDATA", nrows, ncols, nirrelevantrows - nnonexistingrows, nirrelevantcols, nrelevantrows, nrelevantcols,
1278 lpdata->nvarbounds, lpdata->ndelvarbounds, lpdata->nvarbounds - lpdata->ndelvarbounds);
1288 void debugPrintSubLpData(
1291 ZEROHALF_SUBLPDATA* sublpdata
1297 assert(scip !=
NULL);
1298 assert(lpdata !=
NULL);
1299 assert(sublpdata !=
NULL);
1305 for( i = 0 ; i < sublpdata->nrrows ; ++i)
1308 i, sublpdata->rrows[i], sublpdata->rrowsrhs[i], sublpdata->rrowsslack[i],
1312 for( j = 0 ; j < sublpdata->nrcols ; ++j)
1315 i, sublpdata->rcols[i], sublpdata->rcolslbslack[i], sublpdata->rcolsubslack[i]);
1324 void debugPrintMod2Data(
1335 assert(scip !=
NULL);
1336 assert(lpdata !=
NULL);
1337 assert(mod2data !=
NULL);
1342 SCIPdebugMessage(
" nrows = %d, nvarbounds = %d, nrcols = %d, nrowsind = %d, ncolsind = %d\n",
1343 mod2data->nrows, mod2data->nvarbounds, mod2data->relatedsubproblem->nrcols,
1344 mod2data->nrowsind, mod2data->ncolsind);
1345 SCIPdebugMessage(
" rowsbitarraysize = %d, rowaggregationsbitarraysize = %d\n",
1346 mod2data->rowsbitarraysize, mod2data->rowaggregationsbitarraysize);
1350 for( j = 0 ; j < mod2data->relatedsubproblem->nrcols ; ++j )
1352 for( k = 0 ; k < mod2data->ncolsind ; ++k )
1353 if( mod2data->colsind[k] == j )
1355 SCIPdebugMessage(
" rcols[%6d]: fracsol: %6g colsind: %6d name: %s\n", j, mod2data->fracsol[j],
1356 k < mod2data->ncolsind ? k : -1,
1360 SCIPdebugMessage(
"\n (A mod 2, b mod 2, [#nonz] (slacks), R, name(rrows), left(-)/right(+):\n");
1361 if( mod2data->nrowsind == 0 )
1365 for( i = 0 ; i < mod2data->nrowsind ; ++i )
1369 for( j = 0 ; j < mod2data->ncolsind; ++j )
1370 if(
BITARRAYBITISSET(mod2data->rows[mod2data->rowsind[i]], mod2data->colsind[j]) )
1379 if( mod2data->rhs[mod2data->rowsind[i]] )
1390 if( printaggregations )
1392 for( j = 0 ; j < mod2data->relatedsubproblem->nrrows; ++j )
1403 if( mod2data->rowsind[i] < mod2data->nrows - mod2data->nvarbounds )
1406 if( lpdata->rrowsindexofleftrow[mod2data->relatedsubproblem->rrows[mod2data->rowsind[i]]] == mod2data->rowsind[i] )
1437 assert(scip !=
NULL);
1438 assert(lpdata !=
NULL);
1441 for( i = 0 ; i < lpdata->nrows ; ++i)
1444 (lpdata->subproblemsindexofrow[i] ==
IRRELEVANT)
1445 || (lpdata->rrowsindexofleftrow[i] < 0) ?
"IRRELEVANT" :
"RELEVANT",
1446 lpdata->subproblemsindexofrow[i], lpdata->rrowsindexofleftrow[i],
1447 lpdata->rrowsindexofleftrow[i] < 0 ? getconstantname(temp, lpdata->rrowsindexofleftrow[i]) :
"");
1449 (lpdata->subproblemsindexofrow[i] ==
IRRELEVANT)
1450 || (lpdata->rrowsindexofrightrow[i] < 0) ?
"IRRELEVANT" :
"RELEVANT",
1451 lpdata->subproblemsindexofrow[i], lpdata->rrowsindexofrightrow[i],
1452 lpdata->rrowsindexofrightrow[i] < 0 ? getconstantname(temp, lpdata->rrowsindexofrightrow[i]) :
"");
1457 for( j = 0 ; j < lpdata->ncols ; ++j)
1460 (lpdata->subproblemsindexofcol[j] ==
IRRELEVANT)
1461 || (lpdata->rcolsindexofcol[j] < 0) ?
"IRRELEVANT" :
"RELEVANT",
1462 lpdata->subproblemsindexofcol[j], lpdata->rcolsindexofcol[j],
1463 lpdata->rcolsindexofcol[j] < 0 ? getconstantname(temp, lpdata->rcolsindexofcol[j]) :
"");
1487 if( scores[ind1] < scores[ind2] )
1489 else if( scores[ind1] > scores[ind2] )
1504 if( scores[ind1] < scores[ind2] )
1506 else if( scores[ind1] > scores[ind2] )
1532 ZEROHALF_SUBLPDATA* problem;
1534 #ifdef ZEROHALF__PRINT_STATISTICS 1539 assert(scip !=
NULL);
1540 assert(lpdata !=
NULL);
1541 assert(lpdata->cols !=
NULL);
1542 assert(lpdata->ncols > 0);
1543 assert(lpdata->nrows > 0);
1544 assert(lpdata->subproblems ==
NULL);
1545 assert(lpdata->nsubproblems == 0);
1546 assert(lpdata->subproblemsindexofrow ==
NULL);
1547 assert(lpdata->rrowsindexofleftrow ==
NULL);
1548 assert(lpdata->rrowsindexofrightrow ==
NULL);
1549 assert(lpdata->subproblemsindexofcol ==
NULL);
1550 assert(lpdata->rcolsindexofcol ==
NULL);
1551 assert(lpdata->bestlbidxofcol ==
NULL);
1552 assert(lpdata->bestubidxofcol ==
NULL);
1572 lpdata->nsubproblems = 1;
1573 lpdata->subproblems[0] = problem;
1574 lpdata->nvarbounds = 0;
1575 lpdata->ndelvarbounds = 0;
1578 for( j = 0 ; j < lpdata->ncols ; ++j)
1581 lpdata->bestlbidxofcol[j] = -2;
1582 lpdata->bestubidxofcol[j] = -2;
1584 col = lpdata->cols[j];
1598 lbslack = primsol - lb;
1599 ubslack = ub - primsol;
1608 #ifdef ZEROHALF__PRINT_STATISTICS 1614 lpdata->nvarbounds += tempnvarbnds;
1628 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1635 #ifdef ZEROHALF__PRINT_STATISTICS 1636 lpdata->ndelvarbounds += tempnvarbnds;
1638 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1639 if(
ISODD(scip, lb) )
1648 #ifdef ZEROHALF__PRINT_STATISTICS 1649 lpdata->ndelvarbounds += tempnvarbnds;
1651 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1652 if(
ISODD(scip, ub) )
1660 problem->rcols[problem->nrcols] = j;
1661 problem->rcolslbslack[problem->nrcols] = lbslack;
1662 problem->rcolsubslack[problem->nrcols] = ubslack;
1663 lpdata->subproblemsindexofcol[j] = 0;
1664 lpdata->rcolsindexofcol[j] = problem->nrcols;
1671 #ifdef ZEROHALF__PRINT_STATISTICS 1672 lpdata->ndelvarbounds += tempnvarbnds;
1674 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1681 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1714 assert(lpdata !=
NULL);
1715 assert(bestlbsol !=
NULL);
1716 assert(bestlbtype !=
NULL);
1717 assert(bestzvlb !=
NULL);
1718 assert(bestbvlb !=
NULL);
1719 assert(bestdvlb !=
NULL);
1725 *bestlbtype = lpdata->bestlbidxofcol[collppos];
1730 if( *bestlbtype == -1 )
1740 assert(zvlb !=
NULL || nvlb == 0);
1741 assert(bvlb !=
NULL || nvlb == 0);
1742 assert(dvlb !=
NULL || nvlb == 0);
1745 if( *bestlbtype == -2 )
1751 for( j = 0; j < nvlb; j++ )
1753 assert(zvlb !=
NULL);
1754 assert(bvlb !=
NULL);
1755 assert(dvlb !=
NULL);
1765 if( vlbsol > *bestlbsol )
1767 *bestlbsol = vlbsol;
1775 if( *bestlbtype == -2 )
1779 lpdata->bestlbidxofcol[collppos] = *bestlbtype;
1781 assert(lpdata->bestlbidxofcol[collppos] > -2);
1783 if( *bestlbtype >= 0 )
1786 assert(*bestlbtype < nvlb);
1787 assert(zvlb !=
NULL);
1788 assert(bvlb !=
NULL);
1789 assert(dvlb !=
NULL);
1790 *bestzvlb = zvlb[*bestlbtype];
1791 *bestbvlb = bvlb[*bestlbtype];
1792 *bestdvlb = dvlb[*bestlbtype];
1821 assert(lpdata !=
NULL);
1822 assert(bestubsol !=
NULL);
1823 assert(bestubtype !=
NULL);
1824 assert(bestzvub !=
NULL);
1825 assert(bestbvub !=
NULL);
1826 assert(bestdvub !=
NULL);
1831 *bestubtype = lpdata->bestubidxofcol[collppos];
1836 if( *bestubtype == -1 )
1846 assert(zvub !=
NULL || nvub == 0);
1847 assert(bvub !=
NULL || nvub == 0);
1848 assert(dvub !=
NULL || nvub == 0);
1851 if( *bestubtype == -2 )
1856 for( j = 0; j < nvub; j++ )
1858 assert(zvub !=
NULL);
1859 assert(bvub !=
NULL);
1860 assert(dvub !=
NULL);
1870 if( vubsol < *bestubsol )
1872 *bestubsol = vubsol;
1879 if( *bestubtype == -2 )
1883 lpdata->bestubidxofcol[collppos] = *bestubtype;
1885 assert(lpdata->bestubidxofcol[collppos] > -2);
1887 if( *bestubtype >= 0 )
1890 assert(*bestubtype < nvub);
1891 assert(zvub !=
NULL);
1892 assert(bvub !=
NULL);
1893 assert(dvub !=
NULL);
1894 *bestzvub = zvub[*bestubtype];
1895 *bestbvub = bvub[*bestubtype];
1896 *bestdvub = dvub[*bestubtype];
1931 int nnonzcurrentrow;
1942 ZEROHALF_SUBLPDATA* problem;
1947 assert(scip !=
NULL);
1948 assert(sepadata !=
NULL);
1949 assert(lpdata !=
NULL);
1950 assert(lpdata->rows !=
NULL);
1951 assert(lpdata->nrows > 0);
1952 assert(lpdata->subproblemsindexofcol !=
NULL);
1953 assert(lpdata->rcolsindexofcol !=
NULL);
1954 assert(lpdata->subproblems !=
NULL);
1955 assert(lpdata->nsubproblems > 0);
1957 assert(lpdata->subproblemsindexofrow ==
NULL);
1958 assert(lpdata->rrowsindexofleftrow ==
NULL);
1959 assert(lpdata->rrowsindexofrightrow ==
NULL);
1962 problem = lpdata->subproblems[k];
1965 assert(k <= lpdata->nsubproblems);
1966 assert(problem !=
NULL);
1967 assert(problem->rcols !=
NULL);
1968 assert(problem->nrcols > 0);
1969 assert(problem->rcolslbslack !=
NULL);
1970 assert(problem->rcolsubslack !=
NULL);
1972 assert(problem->rrows ==
NULL);
1973 assert(problem->rrowsrhs ==
NULL);
1974 assert(problem->rrowsslack ==
NULL);
1995 maxslack = sepadata->maxslack;
1996 problem->nrrows = 0;
1997 for( r = 0 ; r < lpdata->nrows ; ++r)
1999 row = lpdata->rows[r];
2001 if( sepadata->ignoreprevzhcuts )
2006 if( strlen(rowname) > 8 )
2007 if(rowname[0] ==
'z' 2008 && rowname[1] ==
'e' 2009 && rowname[2] ==
'r' 2010 && rowname[3] ==
'o' 2011 && rowname[4] ==
'h' 2012 && rowname[5] ==
'a' 2013 && rowname[6] ==
'l' 2014 && rowname[7] ==
'f' )
2016 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2024 if( sepadata->onlyorigrows )
2031 assert(sepadata->origrows !=
NULL);
2032 assert(sepadata->norigrows > 0);
2036 right = sepadata->norigrows - 1;
2038 while( left <= right && center > -1 )
2040 center = left + ((right - left) / 2);
2041 if( sepadata->origrows[center] == rowindex )
2043 if( sepadata->origrows[center] > rowindex )
2050 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2067 for( c = 0; c < nnonzcurrentrow; ++c)
2070 assert(0 <= collppos && collppos < lpdata->ncols);
2093 &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2094 assert( bestbndtype > -2 && lpdata->bestlbidxofcol[collppos] == bestbndtype);
2096 if( bestbndtype > -1 )
2101 assert(0 <= zlppos && zlppos < lpdata->ncols);
2103 if( valscurrentrow[c] > 0 )
2104 densecoeffscurrentrightrow[zlppos] += valscurrentrow[c] * bestbvbnd;
2106 densecoeffscurrentleftrow[zlppos] -= valscurrentrow[c] * bestbvbnd;
2110 &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2111 assert(bestbndtype > -2 && lpdata->bestubidxofcol[collppos] == bestbndtype);
2113 if( bestbndtype > -1 )
2118 assert(0 <= zlppos && zlppos < lpdata->ncols);
2120 if( valscurrentrow[c] > 0 )
2121 densecoeffscurrentleftrow[zlppos] -= valscurrentrow[c] * bestbvbnd;
2123 densecoeffscurrentrightrow[zlppos] += valscurrentrow[c] * bestbvbnd;
2128 densecoeffscurrentleftrow[collppos] -= valscurrentrow[c];
2129 densecoeffscurrentrightrow[collppos] += valscurrentrow[c];
2136 intscalarleftrow = 1.0;
2137 intscalarrightrow = 1.0;
2159 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2164 lpdata->intscalarsleftrow[r] = intscalarleftrow;
2165 lpdata->intscalarsrightrow[r] = intscalarrightrow;
2179 lhs = (lhs - cst) * intscalarleftrow;
2180 rhs = (rhs - cst) * intscalarrightrow;
2185 lhsslack = lhsslack * intscalarleftrow;
2186 rhsslack = rhsslack * intscalarrightrow;
2189 if( (!lhsisinfinity &&
SCIPisLE(scip, lhsslack, maxslack))
2190 || (!rhsisinfinity &&
SCIPisLE(scip, rhsslack, maxslack)) )
2196 lhsiseven =
ISEVEN(scip, lhs);
2197 rhsiseven =
ISEVEN(scip, rhs);
2199 rowisrelevant =
FALSE;
2200 for( c = 0 ; c < nnonzcurrentrow ; ++c )
2210 lhsiseven = !lhsiseven;
2211 rhsiseven = !rhsiseven;
2217 if( !rhsisinfinity )
2219 if( valscurrentrow[c] * intscalarrightrow > 0 )
2221 findClosestLb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2222 assert(bestbndtype > -2 && lpdata->bestlbidxofcol[collppos] == bestbndtype);
2226 assert(valscurrentrow[c] * intscalarrightrow < 0);
2227 findClosestUb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2228 assert(bestbndtype > -2 && lpdata->bestubidxofcol[collppos] == bestbndtype);
2230 assert(bestbndtype == -1 || bestzvbnd !=
NULL);
2233 rhsisinfinity =
TRUE;
2237 if ( bestbndtype == -1 )
2238 rhs -= intscalarrightrow *
REALABS(valscurrentrow[c]) * bestbndsol;
2240 rhs -= intscalarrightrow *
REALABS(valscurrentrow[c]) * bestdvbnd;
2241 rhsslack += intscalarrightrow *
REALABS(valscurrentrow[c])
2243 assert(
SCIPisGE(scip, rhsslack, 0.0));
2248 if( !lhsisinfinity )
2250 if( valscurrentrow[c] * intscalarleftrow < 0 )
2252 findClosestLb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2253 assert(bestbndtype > -2 && lpdata->bestlbidxofcol[collppos] == bestbndtype);
2257 assert(valscurrentrow[c] * intscalarleftrow > 0);
2258 findClosestUb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2259 assert(bestbndtype > -2 && lpdata->bestubidxofcol[collppos] == bestbndtype);
2261 assert(bestbndtype == -1 || bestzvbnd !=
NULL);
2264 lhsisinfinity =
TRUE;
2268 if( bestbndtype == -1 )
2269 lhs -= intscalarleftrow *
REALABS(valscurrentrow[c]) * bestbndsol;
2271 lhs -= intscalarleftrow *
REALABS(valscurrentrow[c]) * bestdvbnd;
2272 lhsslack += intscalarleftrow *
REALABS(valscurrentrow[c])
2274 assert(
SCIPisGE(scip, lhsslack, 0.0));
2280 if( lhsisinfinity && rhsisinfinity )
2282 rowisrelevant =
FALSE;
2286 rowisrelevant =
TRUE;
2290 if( lpdata->subproblemsindexofcol[collppos] == k )
2291 rowisrelevant =
TRUE;
2294 if( c == nnonzcurrentrow - 1 && (!lhsiseven || !rhsiseven) )
2295 rowisrelevant =
TRUE;
2298 assert(
SCIPisGE(scip, lhsslack, 0.0));
2299 assert(
SCIPisGE(scip, rhsslack, 0.0));
2306 problem->rrows[problem->nrrows] = r;
2308 lhsslackislessequalmaxslack =
SCIPisLE(scip, lhsslack, maxslack);
2309 rhsslackislessequalmaxslack =
SCIPisLE(scip, rhsslack, maxslack);
2315 if( !lhsisinfinity && lhsslackislessequalmaxslack )
2318 lpdata->subproblemsindexofrow[r] = k;
2319 lpdata->rrowsindexofleftrow[r] = problem->nrrows;
2321 problem->rrows[problem->nrrows] = r;
2325 problem->rrowsrhs[problem->nrrows] = lhs;
2326 problem->rrowsslack[problem->nrrows] = lhsslack;
2336 if( !rhsisinfinity && rhsslackislessequalmaxslack )
2339 lpdata->subproblemsindexofrow[r] = k;
2340 lpdata->rrowsindexofrightrow[r] = problem->nrrows;
2342 problem->rrows[problem->nrrows] = r;
2343 problem->rrowsrhs[problem->nrrows] = rhs;
2344 problem->rrowsslack[problem->nrrows] = rhsslack;
2352 if( lpdata->rrowsindexofleftrow[r] > -1 || lpdata->rrowsindexofrightrow[r] > -1 )
2358 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2365 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2390 assert(mod2data !=
NULL);
2392 if( mod2data->nrowsind == 0 )
2395 if( mod2data->ncolsind <= 2 )
2398 for( r = 0; r < mod2data->nrowsind ; ++r )
2401 for( c = 0; c < mod2data->ncolsind ; ++c )
2403 if(
BITARRAYBITISSET(mod2data->rows[mod2data->rowsind[r]], mod2data->colsind[c]) )
2417 #ifdef ZEROHALF__PRINT_STATISTICS 2420 SCIP_Bool hasMatrixMax2EntriesPerColumn(
2428 assert(mod2data !=
NULL);
2430 if( mod2data->ncolsind == 0 )
2433 if( mod2data->nrowsind <= 2 )
2436 for( c = 0; c < mod2data->ncolsind ; ++c )
2439 for( r = 0; r < mod2data->nrowsind ; ++r )
2441 if(
BITARRAYBITISSET(mod2data->rows[mod2data->rowsind[r]], mod2data->colsind[c]) )
2462 int subproblemindex,
2466 ZEROHALF_SUBLPDATA* problem;
2473 int* varboundstoadd;
2474 int nnonzcurrentrow;
2479 #ifdef ZEROHALF__PRINT_STATISTICS 2480 int nirrelevantvarbounds;
2488 assert(scip !=
NULL);
2489 assert(sepadata !=
NULL);
2490 assert(lpdata !=
NULL);
2491 assert(lpdata->rows !=
NULL);
2492 assert(lpdata->nrows > 0);
2493 assert(lpdata->cols !=
NULL);
2494 assert(lpdata->ncols > 0);
2495 assert(lpdata->subproblems !=
NULL);
2496 assert(lpdata->nsubproblems > 0);
2497 assert(lpdata->subproblemsindexofrow !=
NULL);
2498 assert(lpdata->rrowsindexofleftrow !=
NULL);
2499 assert(lpdata->rrowsindexofrightrow !=
NULL);
2500 assert(lpdata->subproblemsindexofcol !=
NULL);
2501 assert(lpdata->rcolsindexofcol !=
NULL);
2502 assert(0 <= subproblemindex);
2503 assert(subproblemindex <= lpdata->nsubproblems);
2504 problem = lpdata->subproblems[subproblemindex];
2505 assert(problem !=
NULL);
2506 assert(problem->rrows !=
NULL);
2507 assert(problem->nrrows > 0);
2508 assert(problem->rrowsrhs !=
NULL);
2509 assert(problem->rrowsslack !=
NULL);
2510 assert(problem->rcols !=
NULL);
2511 assert(problem->nrcols > 0);
2512 assert(problem->rcolslbslack !=
NULL);
2513 assert(problem->rcolsubslack !=
NULL);
2514 assert(mod2data !=
NULL);
2519 maxslack = sepadata->maxslack;
2521 #ifdef ZEROHALF__PRINT_STATISTICS 2522 nirrelevantvarbounds = 0;
2524 mod2data->nvarbounds = 0;
2525 for( c = 0 ; c < problem->nrcols ; c++ )
2530 lbslackisok =
SCIPisLE(scip, problem->rcolslbslack[c], maxslack);
2531 ubslackisok =
SCIPisLE(scip, problem->rcolsubslack[c], maxslack);
2533 if( lbslackisok && ubslackisok )
2543 varboundstoadd[mod2data->nvarbounds] = (-1) * (c + 1);
2544 mod2data->nvarbounds++;
2545 varboundstoadd[mod2data->nvarbounds] = c + 1;
2546 mod2data->nvarbounds++;
2550 if(
SCIPisLE(scip, problem->rcolslbslack[c], problem->rcolsubslack[c]) )
2551 varboundstoadd[mod2data->nvarbounds] = (-1) * (c + 1);
2553 varboundstoadd[mod2data->nvarbounds] = c + 1;
2554 mod2data->nvarbounds++;
2555 #ifdef ZEROHALF__PRINT_STATISTICS 2556 nirrelevantvarbounds++;
2564 varboundstoadd[mod2data->nvarbounds] = (-1) * (c + 1);
2565 mod2data->nvarbounds++;
2567 #ifdef ZEROHALF__PRINT_STATISTICS 2569 nirrelevantvarbounds++;
2573 varboundstoadd[mod2data->nvarbounds] = c + 1;
2574 mod2data->nvarbounds++;
2576 #ifdef ZEROHALF__PRINT_STATISTICS 2578 nirrelevantvarbounds++;
2582 mod2data->nrows = problem->nrrows + mod2data->nvarbounds;
2597 mod2data->relatedsubproblem = problem;
2601 for( c = 0 ; c < problem->nrcols ; ++c)
2603 for( c = 0 ; c < problem->nrcols ; c++)
2604 mod2data->colsind[c] = c;
2605 mod2data->nrowsind = 0;
2606 mod2data->ncolsind = problem->nrcols;
2609 tempcurrentrow =
NULL;
2612 for( i = 0 ; i < problem->nrrows ; ++i )
2614 row = lpdata->rows[problem->rrows[i]];
2618 assert(nnonzcurrentrow > 0);
2619 tempcurrentrow =
NULL;
2624 if( lpdata->rrowsindexofleftrow[problem->rrows[i]] == i )
2628 assert(lpdata->rrowsindexofrightrow[problem->rrows[i]] == i);
2631 intscalar = isrhsrow ? lpdata->intscalarsrightrow[problem->rrows[i]]
2632 : lpdata->intscalarsleftrow[problem->rrows[i]];
2638 for( j = 0 ; j < nnonzcurrentrow; ++j )
2650 if( nonzvalscurrentrow[j] * intscalar > 0.0 )
2651 ispositivecoeff =
TRUE;
2653 ispositivecoeff =
FALSE;
2656 if( isrhsrow == ispositivecoeff )
2657 findClosestLb(scip, lpdata, colscurrentrow[j], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2659 findClosestUb(scip, lpdata, colscurrentrow[j], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2662 assert(bestbndtype > -2);
2664 assert(bestbndtype == -1);
2667 if( bestbndtype == -1 )
2676 densecoeffscurrentrow[
SCIPcolGetLPPos(colscurrentrow[j])] += (nonzvalscurrentrow[j] * intscalar);
2680 for( j = 0 ; j < lpdata->ncols; ++j )
2684 if(
SCIPisZero(scip, densecoeffscurrentrow[j]) )
2687 if( intscalar == 1.0 && !
SCIPisIntegral(scip, densecoeffscurrentrow[j]) )
2693 assert(sepadata->scalefraccoeffs);
2698 densecoeffscurrentrow[j] =
SCIPfloor(scip, densecoeffscurrentrow[j]);
2700 densecoeffscurrentrow[j] =
SCIPceil(scip, densecoeffscurrentrow[j]);
2702 if(
ISODD(scip, densecoeffscurrentrow[j]) )
2704 rcolsindex = lpdata->rcolsindexofcol[j];
2705 fliplhsrhs =
XOR((
int) fliplhsrhs,
2707 if( rcolsindex >= 0 )
2709 if( tempcurrentrow ==
NULL )
2714 assert(rcolsindex < problem->nrcols);
2724 if( tempcurrentrow !=
NULL )
2727 tempcurrentrow =
NULL;
2733 if(
XOR((
int)
ISODD(scip, problem->rrowsrhs[i]), (
int) fliplhsrhs) )
2736 tempmod2rhs =
FALSE;
2738 if( tempcurrentrow ==
NULL && tempmod2rhs )
2743 assert(tempcurrentrow !=
NULL || !tempmod2rhs);
2746 if( tempcurrentrow !=
NULL )
2748 mod2data->rows[i] = tempcurrentrow;
2749 mod2data->rhs[i] = tempmod2rhs;
2751 assert(mod2data->rowaggregationsbitarraysize > 0);
2753 mod2data->rowaggregationsbitarraysize) );
2754 BITARRAYCLEAR(mod2data->rowaggregations[i], mod2data->rowaggregationsbitarraysize);
2757 mod2data->rowsind[mod2data->nrowsind] = i;
2758 mod2data->nrowsind++;
2760 tempcurrentrow =
NULL;
2765 lpdata->subproblemsindexofrow[problem->rrows[i]] =
IRRELEVANT;
2766 if( lpdata->rrowsindexofleftrow[problem->rrows[i]] >= 0 )
2767 lpdata->rrowsindexofleftrow[problem->rrows[i]] =
ZERO_ROW;
2768 if( lpdata->rrowsindexofrightrow[problem->rrows[i]] >= 0 )
2769 lpdata->rrowsindexofrightrow[problem->rrows[i]] =
ZERO_ROW;
2775 i = problem->nrrows;
2776 for( j = 0 ; j < mod2data->nvarbounds ; ++j)
2780 if( varboundstoadd[j] < 0 )
2781 c = (-1) * varboundstoadd[j] - 1;
2783 c = varboundstoadd[j] - 1;
2785 assert(mod2data->rowsbitarraysize > 0);
2787 BITARRAYCLEAR(mod2data->rows[i], mod2data->rowsbitarraysize);
2792 mod2data->rowaggregationsbitarraysize));
2793 BITARRAYCLEAR(mod2data->rowaggregations[i], mod2data->rowaggregationsbitarraysize);
2795 if( varboundstoadd[j] < 0 )
2798 mod2data->rhs[i] =
ISODD(scip, bound);
2799 mod2data->slacks[i] = problem->rcolslbslack[c];
2804 mod2data->rhs[i] =
ISODD(scip, bound);
2805 mod2data->slacks[i] = problem->rcolsubslack[c];
2808 mod2data->slacks[i] = 0.0;
2810 mod2data->rowsind[mod2data->nrowsind] = i;
2811 mod2data->nrowsind++;
2819 #ifdef ZEROHALF__PRINT_STATISTICS 2820 ZEROHALFstatisticsMessage(
"\n");
2821 ZEROHALFstatisticsMessage(
" | ------------------------------- subproblem ------------------------------- | ------------------------------\n");
2822 ZEROHALFstatisticsMessage(
" | nrrows | nrcols | nvarbnds | ndlvbnds | max2/row | max2/col | A^T ept | \n");
2823 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8s | %8s | %8s |\n",
2824 "SUBPROBLEMDATA", problem->nrrows, problem->nrcols, mod2data->nvarbounds, nirrelevantvarbounds,
2862 assert(nvars == 0 || cutcoefs !=
NULL);
2863 assert(nvars == 0 || varsolvals !=
NULL);
2864 assert(cutvars !=
NULL);
2865 assert(cutvals !=
NULL);
2866 assert(cutlen !=
NULL);
2867 assert(cutact !=
NULL);
2868 assert(cutnorm !=
NULL);
2877 for( v = 0; v < nvars; ++v)
2882 act += val * varsolvals[v];
2883 cutsqrnorm += SQR(val);
2884 cutvars[len] = vars[v];
2889 norm = SQRT(cutsqrnorm);
2892 for( v = 0; v < nvars; ++v)
2897 act += val * varsolvals[v];
2899 norm =
MAX(norm, absval);
2900 cutvars[len] = vars[v];
2907 for( v = 0; v < nvars; ++v)
2912 act += val * varsolvals[v];
2914 cutvars[len] = vars[v];
2921 for( v = 0; v < nvars; ++v)
2926 act += val * varsolvals[v];
2928 cutvars[len] = vars[v];
2958 assert(scip !=
NULL);
2960 assert(cutdata !=
NULL);
2961 assert(result !=
NULL);
2964 if( !cutdata->isfeasviolated || !cutdata->success )
2975 if( !sepadata->forcecutstolp && !sepadata->forcecutstosepastore
2982 if( !sepadata->usezhcutpool )
2991 if( !cutdata->islocal )
2997 cutdata->addedtolp =
TRUE;
3022 assert(mod2data !=
NULL);
3023 assert(mod2data->relatedsubproblem !=
NULL);
3024 assert(mod2data->nrowsind > 0);
3026 assert(r < mod2data->nrowsind);
3028 mod2data->rowstatistics[mod2data->rowsind[r]] = flag;
3045 assert(mod2data !=
NULL);
3046 assert(mod2data->relatedsubproblem !=
NULL);
3047 assert(mod2data->ncolsind > 0);
3049 assert(c < mod2data->ncolsind);
3053 mod2data->colstatistics[mod2data->colsind[c]] = flag;
3058 for( i = 0 ; i < mod2data->nrowsind ; ++i)
3059 mod2data->rows[mod2data->rowsind[i]][rowsbind] &= rowsbmask;
3081 ZEROHALF_SUBLPDATA* problem;
3086 assert(scip !=
NULL);
3087 assert(lpdata !=
NULL);
3088 assert(lpdata->nrows > 0);
3089 assert(mod2data !=
NULL);
3090 assert(mod2data->relatedsubproblem !=
NULL);
3091 assert(mod2data->nrowsind > 0);
3092 assert(rrowsincut !=
NULL);
3093 assert(weights !=
NULL);
3094 assert(*weights ==
NULL);
3095 assert(nrowsincut !=
NULL);
3103 problem = mod2data->relatedsubproblem;
3108 for( i = 0 ; i < problem->nrrows ; ++i)
3110 lppos = problem->rrows[i];
3111 assert(0 <= lppos && lppos <= lpdata->nrows);
3114 assert(lpdata->rrowsindexofleftrow[lppos] == i || lpdata->rrowsindexofrightrow[lppos] == i);
3117 lpdata->rrowsindexofleftrow[lppos] == i ?
"-" :
"+",
3118 lpdata->intscalarsleftrow[lppos], lpdata->intscalarsrightrow[lppos],
3121 if( lpdata->rrowsindexofleftrow[lppos] == i )
3122 (*weights)[lppos] = lpdata->intscalarsleftrow[lppos] * (-0.5);
3124 (*weights)[lppos] = lpdata->intscalarsrightrow[lppos] * 0.5;
3132 if( nnonz >= 5 * sepadata->maxnnonz )
3162 assert(scip !=
NULL);
3163 assert(lpdata !=
NULL);
3164 assert(lpdata->nvars > 0);
3165 assert(weights !=
NULL);
3166 assert(varsolvals !=
NULL);
3167 assert(cutdata !=
NULL);
3168 assert(cutdata->relatedsubproblem !=
NULL);
3169 assert(cutoff !=
NULL);
3180 cutdata->success =
FALSE;
3181 if( sepadata->maxtestdelta == 0 )
3186 weights, -1.0,
NULL, -1, -1,
NULL, 1.0,
NULL,
NULL, cutcoefs, &(cutdata->rhs), &(cutdata->activity),
3187 &(cutdata->success), &(cutdata->islocal), &(cutdata->cutrank)) );
3189 if( sepadata->trynegscaling )
3193 weights, -1.0,
NULL, -1, -1,
NULL, -1.0,
NULL,
NULL, cutcoefs, &(cutdata->rhs), &(cutdata->activity),
3194 &(cutdata->success), &(cutdata->islocal), &(cutdata->cutrank)) );
3205 if( *varsolvals ==
NULL )
3218 for(i = lpdata->nvars - 1; i >= 0; --i )
3223 assert(*varsolvals !=
NULL);
3227 -1.0,
NULL, -1, -1,
BOUNDSWITCH,
USEVBDS,
ALLOWLOCAL,
FIXINTEGRALRHS, sepadata->maxnnonz,
MAXWEIGHTRANGE,
3228 MINFRAC,
MAXFRAC, sepadata->trynegscaling,
TRUE,
"zerohalf", cutoff, &ncuts, &bestdelta, &bestdeltavalid) );
3232 if( !(*cutoff) && bestdeltavalid )
3236 weights, -1.0,
NULL, -1, -1,
NULL, bestdelta,
NULL,
NULL, cutcoefs, &(cutdata->rhs), &(cutdata->activity),
3237 &(cutdata->success), &(cutdata->islocal), &(cutdata->cutrank)) );
3242 cutdata->violation = cutdata->activity - cutdata->rhs;
3245 if( !(*cutoff) && cutdata->success )
3247 cutdata->isfeasviolated =
SCIPisFeasGT(scip, cutdata->activity, cutdata->rhs);
3249 cutdata->isfeasviolated ?
"" :
"not ", cutdata->activity, cutdata->rhs, cutdata->violation);
3251 if( cutdata->isfeasviolated )
3253 if( *varsolvals ==
NULL )
3259 assert(*varsolvals !=
NULL);
3267 cutcoefs, *varsolvals, normtype, cutvars, cutvals,
3268 &(cutdata->nnonz), &(cutdata->activity), &(cutdata->norm)));
3273 cutdata->efficacy = (cutdata->activity - cutdata->rhs) / cutdata->norm;
3275 if( sepadata->forcecutstolp || sepadata->forcecutstosepastore
3276 || (
SCIPisEfficacious(scip, cutdata->efficacy) && cutdata->nnonz < sepadata->maxnnonz) )
3281 cutdata->islocal,
FALSE, sepadata->dynamiccuts));
3287 cutdata->success =
FALSE;
3290 cutdata->success =
FALSE;
3297 cutdata->success =
FALSE;
3338 assert(scip !=
NULL);
3339 assert(lpdata !=
NULL);
3340 assert(mod2data !=
NULL);
3341 assert(mod2data->relatedsubproblem !=
NULL);
3342 assert(firstrowsind >= 0);
3343 assert(lastrowsind <= mod2data->nrowsind);
3344 assert(nsepacuts !=
NULL);
3345 assert(nzerohalfcuts !=
NULL);
3346 assert(zerohalfcuts !=
NULL);
3347 assert(*nsepacuts <= *nzerohalfcuts);
3348 assert(varsolvals !=
NULL);
3349 assert(result !=
NULL);
3353 if( mod2data->nrowsind == 0 || lastrowsind - firstrowsind <= 0 )
3364 maxslack = sepadata->maxslack;
3369 for( r = 0 ; r < lastrowsind - firstrowsind && *nsepacuts < maxsepacuts && *nzerohalfcuts < maxcuts; ++r )
3371 if( mod2data->rhs[mod2data->rowsind[firstrowsind + r]] ==
TRUE )
3373 if(
SCIPisLE(scip, mod2data->slacks[mod2data->rowsind[firstrowsind + r]], maxslack ))
3376 zerorow, mod2data->rowsbitarraysize) )
3381 mod2data->rowaggregations[mod2data->rowsind[firstrowsind + r]], &weights, &nrowsincut));
3382 if( weights ==
NULL )
3386 assert(nrowsincut > 0);
3390 mod2data->relatedsubproblem, mod2data, 1, nrowsincut, cutseparatedby));
3392 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
3409 removerow[r] =
TRUE;
3417 if( ! cutoff && nrowsremoved > 0 )
3420 for( r = firstrowsind ; r < mod2data->nrowsind && r2 < mod2data->nrowsind; ++r)
3422 if( r < lastrowsind - firstrowsind )
3423 while( removerow[r2] && r2 < mod2data->nrowsind )
3425 if( r < r2 && r2 < mod2data->nrowsind )
3426 mod2data->rowsind[r] = mod2data->rowsind[r2];
3429 mod2data->nrowsind -= nrowsremoved;
3459 int nzerorowsremoved;
3460 int nlargeslackrowsremoved;
3461 int nidenticalrowsremoved;
3465 assert(scip !=
NULL);
3466 assert(lpdata !=
NULL);
3467 assert(mod2data !=
NULL);
3468 assert(mod2data->relatedsubproblem !=
NULL);
3469 assert(firstrowsind >= 0);
3470 assert(lastrowsind <= mod2data->nrowsind);
3474 if( mod2data->nrowsind == 0 || lastrowsind - firstrowsind <= 0 )
3481 if( removezerorows )
3488 if( removezerorows )
3492 maxslack = sepadata->maxslack;
3493 nzerorowsremoved = 0;
3494 nlargeslackrowsremoved = 0;
3495 nidenticalrowsremoved = 0;
3498 for( r1 = 0 ; r1 < lastrowsind - firstrowsind ; ++r1)
3499 if( !rowisprocessed[r1] )
3501 rowisprocessed[r1] =
TRUE;
3503 if( removezerorows && !removerow[r1] )
3504 if( mod2data->rhs[mod2data->rowsind[firstrowsind + r1]] ==
FALSE )
3506 assert(zerorow !=
NULL);
3508 zerorow, mod2data->rowsbitarraysize) )
3511 removerow[r1] =
TRUE;
3515 if( removelargeslackrows && !removerow[r1] )
3516 if(
SCIPisGT(scip, mod2data->slacks[mod2data->rowsind[firstrowsind + r1]], maxslack) )
3519 removerow[r1] =
TRUE;
3520 nlargeslackrowsremoved++;
3523 if( removeidenticalrows && !removerow[r1] )
3524 for( r2 = r1 + 1 ; r2 < lastrowsind - firstrowsind ; ++r2)
3525 if( !rowisprocessed[r2] )
3526 if( mod2data->rhs[mod2data->rowsind[firstrowsind + r1]]
3527 == mod2data->rhs[mod2data->rowsind[firstrowsind + r2]] )
3529 mod2data->rows[mod2data->rowsind[firstrowsind + r2]], mod2data->rowsbitarraysize) )
3531 if(
SCIPisLT(scip, mod2data->slacks[mod2data->rowsind[firstrowsind + r1]],
3532 mod2data->slacks[mod2data->rowsind[firstrowsind + r2]]) )
3535 removerow[r2] =
TRUE;
3536 nidenticalrowsremoved++;
3537 rowisprocessed[r2] =
TRUE;
3542 removerow[r1] =
TRUE;
3543 nidenticalrowsremoved++;
3550 if( nzerorowsremoved + nlargeslackrowsremoved + nidenticalrowsremoved > 0 )
3553 for( r1 = firstrowsind ; r1 < mod2data->nrowsind && r2 < mod2data->nrowsind; ++r1)
3555 if( r1 < lastrowsind - firstrowsind )
3556 while( removerow[r2] && r2 < mod2data->nrowsind )
3558 if( r1 < r2 && r2 < mod2data->nrowsind )
3559 mod2data->rowsind[r1] = mod2data->rowsind[r2];
3562 mod2data->nrowsind -= (nzerorowsremoved + nlargeslackrowsremoved + nidenticalrowsremoved);
3567 if( removezerorows && zerorow !=
NULL )
3593 int maxnnonzentries;
3594 int nzerocolsremoved;
3595 int ncolsingletonsremoved;
3596 int nunprocessedcols;
3597 int nconsideredcols;
3601 int rowofcolsingleton;
3608 assert(scip !=
NULL);
3609 assert(sepadata !=
NULL);
3610 assert(lpdata !=
NULL);
3611 assert(mod2data !=
NULL);
3612 assert(mod2data->relatedsubproblem !=
NULL);
3613 assert(firstcolsind >= 0);
3614 assert(lastcolsind <= mod2data->ncolsind);
3615 assert(removezerocols || removecolsingletons);
3618 nconsideredcols = lastcolsind - firstcolsind;
3621 if( mod2data->ncolsind == 0 || mod2data->nrowsind == 0 || nconsideredcols <= 0 )
3632 maxslack = sepadata->maxslack;
3633 nunprocessedcols = nconsideredcols;
3634 nzerocolsremoved = 0;
3635 ncolsingletonsremoved = 0;
3637 rowofcolsingleton = -1;
3638 if( removecolsingletons )
3639 maxnnonzentries = 1;
3641 maxnnonzentries = 0;
3644 while(nunprocessedcols > 0)
3646 for( c = 0 ; c < nconsideredcols ; ++c )
3647 if( colisprocessed[c] ==
FALSE )
3649 assert(firstcolsind + c < mod2data->ncolsind);
3655 for( r = 0 ; r < mod2data->nrowsind ; ++r)
3656 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
3659 if( nnonzentries > maxnnonzentries )
3661 rowofcolsingleton = r;
3665 if( removezerocols )
3666 if( nnonzentries == 0 )
3669 removecol[c] =
TRUE;
3675 if( removecolsingletons && !removecol[c] )
3676 if( nnonzentries == 1 )
3678 r = rowofcolsingleton;
3679 removecol[c] =
TRUE;
3682 mod2data->slacks[mod2data->rowsind[r]] += mod2data->fracsol[mod2data->colsind[firstcolsind + c]];
3686 if( checkresultingrows &&
SCIPisGT(scip, mod2data->slacks[mod2data->rowsind[r]], maxslack) )
3689 for( j = 0 ; j < nconsideredcols ; ++j)
3690 if( !removecol[j] && colisprocessed[j] )
3692 mod2data->colsind[firstcolsind + j]) )
3694 colisprocessed[j] =
FALSE;
3699 mod2data->nrowsind - r - 1);
3701 mod2data->nrowsind--;
3705 ncolsingletonsremoved++;
3709 colisprocessed[c] =
TRUE;
3712 if( nzerocolsremoved + ncolsingletonsremoved == nconsideredcols || mod2data->nrowsind == 0 )
3717 if( mod2data->nrowsind == 0 )
3719 for( c = firstcolsind ; c < mod2data->ncolsind; ++c)
3722 removecol[c] =
TRUE;
3725 nzerocolsremoved = nconsideredcols - ncolsingletonsremoved;
3726 assert(nzerocolsremoved + ncolsingletonsremoved == nconsideredcols);
3730 if( mod2data->nrowsind == 0 )
3731 mod2data->ncolsind = 0;
3733 if( nzerocolsremoved + ncolsingletonsremoved > 0 )
3736 for( c = firstcolsind ; c < mod2data->ncolsind && j < mod2data->ncolsind; ++c)
3738 if( c < nconsideredcols )
3739 while( removecol[j] && j < mod2data->ncolsind )
3741 if( c < j && j < mod2data->ncolsind )
3742 mod2data->colsind[c] = mod2data->colsind[j];
3745 mod2data->ncolsind -= (nzerocolsremoved + ncolsingletonsremoved);
3769 int identsubmatrixsize;
3775 assert(scip !=
NULL);
3776 assert(sepadata !=
NULL);
3777 assert(lpdata !=
NULL);
3778 assert(mod2data !=
NULL);
3779 assert(mod2data->relatedsubproblem !=
NULL);
3782 if( mod2data->ncolsind == 0 || mod2data->nrowsind == 0 )
3787 while( nslackzerorows < mod2data->nrowsind
3788 &&
SCIPisZero(scip, mod2data->slacks[mod2data->rowsind[nslackzerorows]]) )
3791 if( nslackzerorows == 0 )
3796 if( mod2data->ncolsind > 1 )
3798 SCIPsortInd( mod2data->colsind , compRealNonIncreasing , (
void*) mod2data->fracsol , mod2data->ncolsind );
3802 if( mod2data->nrowsind > 1 )
3804 SCIPsortInd( mod2data->rowsind , compRealNonDecreasing , (
void*) mod2data->slacks , mod2data->nrowsind );
3808 identsubmatrixsize = 0;
3812 for( pivotcol = 0 ; pivotcol < mod2data->ncolsind ; ++pivotcol)
3814 if( identsubmatrixsize == mod2data->nrowsind )
3820 for( pivotrow = identsubmatrixsize ; pivotrow < nslackzerorows ; ++pivotrow)
3821 if( mod2data->rows[mod2data->rowsind[pivotrow]][rowsbind] & rowsbmask )
3823 if( pivotrow == nslackzerorows )
3827 for( r = 0 ; r < nslackzerorows ; ++r)
3831 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
3834 BITARRAYSXOR(mod2data->rows[mod2data->rowsind[pivotrow]],
3835 mod2data->rows[mod2data->rowsind[r]],mod2data->rowsbitarraysize);
3836 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[pivotrow]],
3837 mod2data->rowaggregations[mod2data->rowsind[r]],mod2data->rowaggregationsbitarraysize);
3838 mod2data->rhs[mod2data->rowsind[r]] =
3839 XOR(mod2data->rhs[mod2data->rowsind[pivotrow]],mod2data->rhs[mod2data->rowsind[r]]);
3846 temp = mod2data->rowsind[pivotrow];
3847 mod2data->rowsind[pivotrow] = mod2data->rowsind[identsubmatrixsize];
3848 mod2data->rowsind[identsubmatrixsize] = temp;
3849 temp = mod2data->colsind[pivotcol];
3850 mod2data->colsind[pivotcol] = mod2data->colsind[identsubmatrixsize];
3851 mod2data->colsind[identsubmatrixsize] = temp;
3853 identsubmatrixsize++;
3856 if( identsubmatrixsize > 0 )
3860 for( pivot = 0 ; pivot < identsubmatrixsize ; ++pivot)
3864 for( r = nslackzerorows ; r < mod2data->nrowsind ; ++r)
3865 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
3869 mod2data->rows[mod2data->rowsind[r]],mod2data->rowsbitarraysize);
3870 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[pivot]],
3871 mod2data->rowaggregations[mod2data->rowsind[r]],mod2data->rowaggregationsbitarraysize);
3872 mod2data->rhs[mod2data->rowsind[r]] =
3873 XOR(mod2data->rhs[mod2data->rowsind[pivot]],mod2data->rhs[mod2data->rowsind[r]]);
3901 #ifdef WITHDECOMPOSE 3922 int processedrowsbitarraysize;
3923 int unprocessedrowidx;
3927 int processedcolsbitarraysize;
3953 ZEROHALF_SUBLPDATA* problem;
3955 ZEROHALF_SUBLPDATA* subproblem;
3957 int* rrowsinsubprob;
3958 int* rcolsinsubprob;
3960 int nrrowsinsubprob;
3961 int nrcolsinsubprob;
3975 assert(scip !=
NULL);
3976 assert(sepadata !=
NULL);
3977 assert(lpdata !=
NULL);
3978 assert(lpdata->subproblems !=
NULL);
3979 assert(lpdata->nsubproblems > 0);
3983 assert(problemindex >= 0);
3984 assert(problemindex <= lpdata->nsubproblems);
3986 problem = lpdata->subproblems[problemindex];
3988 assert(problem !=
NULL);
3989 assert(problem->rcols !=
NULL);
3990 assert(problem->nrcols > 0);
3991 assert(problem->rcolslbslack !=
NULL);
3992 assert(problem->rcolsubslack !=
NULL);
3993 assert(problem->rrows !=
NULL);
3994 assert(problem->nrrows > 0);
3995 assert(problem->rrowsrhs !=
NULL);
3996 assert(problem->rrowsslack !=
NULL);
3998 if( sepadata->dtimer ==
NULL )
4000 ZEROHALFcreateTimer((sepadata->dtimer));
4002 ZEROHALFstartTimer(sepadata->dtimer);
4021 lpdata->nsubproblems = 0;
4022 maxslack = sepadata->maxslack;
4024 nrrowsinitial = problem->nrrows;
4025 nrcolsinitial = problem->nrcols;
4032 unprocessedrowidx = 0;
4034 while( nprocessedrows < problem->nrrows )
4037 nrrowsinsubprob = 0;
4038 nrcolsinsubprob = 0;
4040 for( i = unprocessedrowidx ; i < problem->nrrows ; ++i)
4043 unprocessedrowidx++;
4053 while( queuelast > queuefirst )
4055 assert(queuelast <= problem->nrrows);
4057 i = queue[queuefirst];
4060 rrowsinsubprob[nrrowsinsubprob] = i;
4069 for( cidx = 0 ; cidx < ncolvals ; ++cidx)
4074 rcolsidx = lpdata->rcolsindexofcol[lppos];
4076 if( lpdata->subproblemsindexofcol[lppos] != problemindex || rcolsidx < 0 )
4078 if(
ISODD(scip, colvals[cidx]) )
4079 fliplhsrhs =
XOR(fliplhsrhs,
4087 if( nprocessedcols == problem->nrcols )
4093 if(
ISEVEN(scip, colvals[cidx]) )
4096 rcolsinsubprob[nrcolsinsubprob] = rcolsidx;
4103 for( ridx = 0 ; ridx < nrowvals ; ++ridx)
4108 rrowsidx = lpdata->rrowsindexofleftrow[lppos];
4109 if( lpdata->subproblemsindexofrow[lppos] == problemindex
4113 if(
ISODD(scip, rowvals[ridx]) )
4115 queue[queuelast] = rrowsidx;
4120 rrowsidx = lpdata->rrowsindexofrightrow[lppos];
4121 if( lpdata->subproblemsindexofrow[lppos] == problemindex
4125 if(
ISODD(scip, rowvals[ridx]) )
4127 queue[queuelast] = rrowsidx;
4135 rrowsinsubproboddrhs[nrrowsinsubprob-1] =
XOR(
ISODD(scip, problem->rrowsrhs[i]),fliplhsrhs);
4141 for( i = 0 ; i < nrrowsinsubprob ; ++i)
4142 if( rrowsinsubproboddrhs[i] )
4144 for( j = 0 ; j < nrcolsinsubprob ; ++j)
4145 if( (
SCIPisLE(scip, problem->rcolsubslack[rcolsinsubprob[j]], maxslack)
4147 || (
SCIPisLE(scip, problem->rcolslbslack[rcolsinsubprob[j]], maxslack)
4148 &&
ISODD(scip,
SCIPcolGetLb(lpdata->cols[problem->rcols[rcolsinsubprob[j]]]))) )
4150 if( i == nrrowsinsubprob && j == nrcolsinsubprob )
4153 for( i = 0 ; i < nrrowsinsubprob ; ++i)
4155 lppos =
SCIProwGetLPPos(lpdata->rows[problem->rrows[rrowsinsubprob[i]]]);
4156 lpdata->subproblemsindexofrow[lppos] =
IRRELEVANT;
4157 if( lpdata->rrowsindexofleftrow[lppos] == rrowsinsubprob[i] )
4158 lpdata->rrowsindexofleftrow[lppos] = ROW_IN_SUBPROB_WITHOUT_ODD_RHS;
4159 if( lpdata->rrowsindexofrightrow[lppos] == rrowsinsubprob[i] )
4160 lpdata->rrowsindexofrightrow[lppos] = ROW_IN_SUBPROB_WITHOUT_ODD_RHS;
4162 for( j = 0 ; j < nrcolsinsubprob ; ++j)
4164 lppos =
SCIPcolGetLPPos(lpdata->cols[problem->rcols[rcolsinsubprob[j]]]);
4165 lpdata->subproblemsindexofcol[lppos] =
IRRELEVANT;
4166 lpdata->rcolsindexofcol[lppos] = COLUMN_IN_SUBPROB_WITHOUT_ODD_RHS;
4169 if( !
SCIPisInfinity(scip, problem->rcolslbslack[rcolsinsubprob[j]]) )
4171 if( !
SCIPisInfinity(scip, problem->rcolsubslack[rcolsinsubprob[j]]) )
4178 if( lpdata->nsubproblems == 0 && nprocessedrows == problem->nrrows )
4186 subproblem->nrrows = nrrowsinsubprob;
4190 subproblem->nrcols = nrcolsinsubprob;
4192 for( i = 0 ; i < nrrowsinsubprob ; ++i)
4194 rowindex = problem->rrows[rrowsinsubprob[i]];
4196 subproblem->rrows[i] = rowindex;
4197 subproblem->rrowsrhs[i] = problem->rrowsrhs[rrowsinsubprob[i]];
4198 subproblem->rrowsslack[i] = problem->rrowsslack[rrowsinsubprob[i]];
4200 if( lpdata->subproblemsindexofrow[rowindex] !=
IRRELEVANT )
4202 assert(lpdata->rrowsindexofleftrow[rowindex] >= 0
4203 || lpdata->rrowsindexofrightrow[rowindex] >= 0);
4204 lpdata->subproblemsindexofrow[rowindex] = lpdata->nsubproblems;
4205 if( lpdata->rrowsindexofleftrow[rowindex] >= 0 )
4206 lpdata->rrowsindexofleftrow[rowindex] = i;
4207 if( lpdata->rrowsindexofrightrow[rowindex] >= 0 )
4208 lpdata->rrowsindexofrightrow[rowindex] = i;
4212 for( i = 0 ; i < nrcolsinsubprob ; ++i)
4214 colindex = problem->rcols[rcolsinsubprob[i]];
4216 subproblem->rcols[i] = colindex;
4217 subproblem->rcolslbslack[i] = problem->rcolslbslack[rcolsinsubprob[i]];
4218 subproblem->rcolsubslack[i] = problem->rcolsubslack[rcolsinsubprob[i]];
4220 if( lpdata->subproblemsindexofcol[colindex] !=
IRRELEVANT )
4222 assert(lpdata->rcolsindexofcol[colindex] >= 0);
4223 lpdata->subproblemsindexofcol[colindex] = lpdata->nsubproblems;
4224 lpdata->rcolsindexofcol[colindex] = i;
4228 lpdata->subproblems[lpdata->nsubproblems] = subproblem;
4229 lpdata->nsubproblems++;
4231 totalnrrows += subproblem->nrrows;
4232 totalnrcols += subproblem->nrcols;
4234 SCIPdebugMessage(
"subproblem %d: %d rrows, %d rcols\n", k, subproblem->nrrows, subproblem->nrcols);
4236 if( lpdata->nsubproblems == 0 )
4239 lpdata->subproblems[0] = problem;
4240 lpdata->nsubproblems = 1;
4241 totalnrrows = problem->nrrows;
4242 totalnrcols = problem->nrcols;
4259 ZEROHALFstopTimer(sepadata->dtimer);
4260 ZEROHALFstatisticsMessage(
"\n");
4261 ZEROHALFstatisticsMessage(
" | --------------------------------- problem \ 4262 -------------------------------- | ----- callback ---- | --total-\n");
4263 ZEROHALFstatisticsMessage(
" | nrrows | nrcols | ndlrrows | ndlrcols \ 4264 | nsubprob | ndelsubp | ndlvbnds | nsepcuts | ncutsfnd | time\n");
4265 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f\n",
4266 "DECOMPOSITION", totalnrrows, totalnrcols, nrrowsinitial - totalnrrows, nrcolsinitial - totalnrcols,
4267 lpdata->nsubproblems, k - lpdata->nsubproblems,
4269 0, 0, ZEROHALFevalTimer(sepadata->dtimer));
4272 assert(scip !=
NULL);
4273 assert(sepadata !=
NULL);
4274 assert(lpdata !=
NULL);
4296 assert(scip !=
NULL);
4297 assert(sepadata !=
NULL);
4298 assert(mod2data !=
NULL);
4299 assert(delta >= 0.0);
4300 assert(delta <= 1.0);
4304 if( mod2data->ncolsind == 0 || mod2data->nrowsind == 0 )
4314 maxsumfracsols = sepadata->maxslack * delta;
4317 if( mod2data->ncolsind > 1 )
4319 SCIPsortInd( mod2data->colsind , compRealNonIncreasing , (
void*) mod2data->fracsol , mod2data->ncolsind );
4322 for( c = mod2data->ncolsind - 1 ; c >= 0 ; --c)
4324 if(
SCIPisGT(scip, sumfracsols + mod2data->fracsol[mod2data->colsind[c]], maxsumfracsols) )
4327 sumfracsols += mod2data->fracsol[mod2data->colsind[c]];
4332 if( ncolsremoved > 0 )
4334 mod2data->ncolsind -= ncolsremoved;
4335 sepadata->maxslack -= sumfracsols;
4359 int nlslrowsremoved;
4360 int nlcolrowsremoved;
4371 assert(scip !=
NULL);
4372 assert(sepadata !=
NULL);
4373 assert(lpdata !=
NULL);
4374 assert(mod2data !=
NULL);
4375 assert(removelargeslackrows || removelargecolrows);
4379 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
4385 last = mod2data->nrowsind - 1;
4388 if( !mod2data->rhs[mod2data->rowsind[first]] )
4390 temp = mod2data->rowsind[first];
4391 mod2data->rowsind[first] = mod2data->rowsind[last];
4392 mod2data->rowsind[last] = temp;
4398 noddrhsrows = first + (mod2data->rhs[mod2data->rowsind[first]] ? 1 : 0);
4402 if( noddrhsrows == 0 )
4406 assert(noddrhsrows >= 0);
4407 SCIPsortInd( mod2data->rowsind , compRealNonDecreasing , (
void*) mod2data->slacks , noddrhsrows );
4408 if( noddrhsrows < mod2data->nrowsind )
4410 SCIPsortInd( mod2data->rowsind + noddrhsrows , compRealNonDecreasing , (
void*) mod2data->slacks ,
4411 mod2data->nrowsind - noddrhsrows );
4414 minslackoddrhsrows = mod2data->slacks[mod2data->rowsind[0]];
4415 nlslrowsremoved = 0;
4416 nlcolrowsremoved = 0;
4422 if(
SCIPisGT(scip, minslackoddrhsrows, sepadata->maxslack) )
4424 if( removelargeslackrows )
4426 for( i = 0 ; i < mod2data->nrowsind ; ++i )
4428 for( i = 0 ; i < mod2data->ncolsind ; ++i )
4430 mod2data->nrowsind = 0;
4431 mod2data->ncolsind = 0;
4440 if( removelargeslackrows )
4442 for( i = noddrhsrows ; i < mod2data->nrowsind ; ++i)
4443 if(
SCIPisGT(scip, minslackoddrhsrows + mod2data->slacks[mod2data->rowsind[i]], sepadata->maxslack) )
4445 nlslrowsremoved += mod2data->nrowsind - i;
4446 while(i < mod2data->nrowsind)
4449 r = mod2data->rowsind[i];
4451 assert(!mod2data->rhs[r]);
4452 assert(
SCIPisGT(scip, minslackoddrhsrows + mod2data->slacks[r], sepadata->maxslack));
4454 removerow[i] =
TRUE;
4460 if( removelargecolrows )
4462 if( mod2data->ncolsind > 0 )
4465 if( mod2data->ncolsind > 1 )
4467 SCIPsortInd( mod2data->colsind , compRealNonIncreasing , (
void*) mod2data->fracsol , mod2data->ncolsind );
4471 while( j < mod2data->ncolsind &&
SCIPisGT(scip, mod2data->fracsol[mod2data->colsind[j]] + minslackoddrhsrows, sepadata->maxslack) )
4473 c = mod2data->colsind[j];
4474 minslackrowwithnonz = 1.0;
4477 for( i = 0 ; i < mod2data->nrowsind ; ++i)
4479 if( mod2data->rows[mod2data->rowsind[i]][rowsbind] & rowsbmask )
4480 if(
SCIPisLT(scip, mod2data->slacks[mod2data->rowsind[i]], minslackrowwithnonz) )
4481 minslackrowwithnonz = mod2data->slacks[mod2data->rowsind[i]];
4483 if( minslackrowwithnonz < 1.0 )
4485 for( i = 0 ; i < mod2data->nrowsind ; ++i)
4487 if( mod2data->rows[mod2data->rowsind[i]][rowsbind] & rowsbmask )
4488 if(
SCIPisGT(scip, minslackrowwithnonz + mod2data->slacks[mod2data->rowsind[i]], sepadata->maxslack) )
4491 removerow[i] =
TRUE;
4501 if( nlslrowsremoved + nlcolrowsremoved > 0 )
4504 for( i = 0 ; i < mod2data->nrowsind && j < mod2data->nrowsind; ++i)
4506 if( i < mod2data->nrowsind )
4507 while( removerow[j] && j < mod2data->nrowsind )
4509 if( i < j && j < mod2data->nrowsind )
4510 mod2data->rowsind[i] = mod2data->rowsind[j];
4513 mod2data->nrowsind -= (nlslrowsremoved + nlcolrowsremoved);
4541 assert(scip !=
NULL);
4542 assert(mod2data !=
NULL);
4545 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
4556 for( c1 = 0 ; c1 < mod2data->ncolsind - 1 ; ++c1)
4560 for( c2 = c1 + 1 ; c2 < mod2data->ncolsind ; ++c2)
4564 for( r = 0 ; r < mod2data->nrowsind ; ++r)
4565 if( (mod2data->rows[mod2data->rowsind[r]][rowsbind1] & rowsbmask1)
4566 != (mod2data->rows[mod2data->rowsind[r]][rowsbind2] & rowsbmask2) )
4568 if( r == mod2data->nrowsind )
4572 mod2data->fracsol[mod2data->colsind[c2]] += mod2data->fracsol[mod2data->colsind[c1]];
4573 removecol[c1] =
TRUE;
4581 if( ncolsremoved > 0 )
4584 for( c2 = 0 ; c2 < mod2data->ncolsind && c1 < mod2data->ncolsind; ++c2)
4586 if( c2 < mod2data->ncolsind )
4587 while( removecol[c1] && c1 < mod2data->ncolsind )
4589 if( c2 < c1 && c1 < mod2data->ncolsind )
4590 mod2data->colsind[c2] = mod2data->colsind[c1];
4593 mod2data->ncolsind -= ncolsremoved;
4622 #ifdef ZEROHALF__PRINT_STATISTICS 4627 int nsepacutsbeforeppm;
4628 int nsepacutsinitial;
4629 int nzerohalfcutsbeforeppm;
4630 int nzerohalfcutsinitial;
4636 assert(scip !=
NULL);
4637 assert(sepadata !=
NULL);
4638 assert(lpdata !=
NULL);
4639 assert(mod2data !=
NULL);
4640 assert(maxsepacuts >= 0);
4641 assert(maxcuts >= 0);
4642 assert(result !=
NULL);
4643 assert(nsepacuts !=
NULL);
4644 assert(nzerohalfcuts !=
NULL);
4645 assert(zerohalfcuts !=
NULL);
4646 assert(*nsepacuts <= *nzerohalfcuts);
4648 assert(mod2data->relatedsubproblem !=
NULL);
4649 assert(mod2data->rows !=
NULL);
4650 assert(mod2data->rowaggregations !=
NULL);
4651 assert(mod2data->rhs !=
NULL);
4652 assert(mod2data->slacks !=
NULL);
4653 assert(mod2data->fracsol !=
NULL);
4654 assert(mod2data->nrows > 0);
4655 assert(mod2data->rowsind !=
NULL);
4656 assert(mod2data->colsind !=
NULL);
4658 if( sepadata->nppmethods == -1 )
4660 sepadata->nppmethods = (int) strlen(sepadata->ppmethods);
4661 if( sepadata->nppmethods > 0 && sepadata->ppmethods[0] ==
'-' )
4662 sepadata->nppmethods = 0;
4665 if( sepadata->nppmethods == 0 )
4669 #ifdef ZEROHALF__PRINT_STATISTICS 4670 if( sepadata->pptimers ==
NULL )
4673 for( i = 0 ; i < sepadata->nppmethods + 1 ; ++i)
4675 ZEROHALFcreateTimer((sepadata->pptimers[i]));
4678 ZEROHALFstartTimer(sepadata->pptimers[sepadata->nppmethods]);
4681 if( mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
4684 #ifdef ZEROHALF__PRINT_STATISTICS 4685 ncolsinitial = mod2data->ncolsind;
4686 nrowsinitial = mod2data->nrowsind;
4687 nsepacutsinitial = *nsepacuts;
4688 nzerohalfcutsinitial = *nzerohalfcuts;
4691 #ifdef ZEROHALF__PRINT_STATISTICS 4692 ZEROHALFstatisticsMessage(
"\n");
4693 ZEROHALFstatisticsMessage(
" | ------------------------------- subproblem\ 4694 ------------------------------- | ----- callback ---- | --total-\n");
4695 ZEROHALFstatisticsMessage(
" | nrowsind | ncolsind | ndelrows | ndelcols \ 4696 | nsepcuts | ncutsfnd | time | nsepcuts | ncutsfnd | time\n");
4697 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8.4f\n",
4698 "START PREPROCSS", mod2data->nrowsind, mod2data->ncolsind, 0, 0, 0, 0, 0.0,
4699 *nsepacuts, *nzerohalfcuts, ZEROHALFevalTimer(sepadata->pptimers[sepadata->nppmethods]));
4700 ZEROHALFcreateNewTimer(timer);
4701 ZEROHALFstartTimer(timer);
4703 ZEROHALFcreateNewTimer(pptimer);
4706 for( i = 0 ; i < sepadata->nppmethods ; ++i)
4709 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
4711 #ifndef ZEROHALF__PRINT_STATISTICS 4713 if( mod2data->nrowsind == 0 && mod2data->ncolsind == 0 )
4717 #ifdef ZEROHALF__PRINT_STATISTICS 4719 ZEROHALFstartTimer(pptimer);
4720 ZEROHALFstartTimer(sepadata->pptimers[i]);
4721 ncolsbeforeppm = mod2data->ncolsind;
4722 nrowsbeforeppm = mod2data->nrowsind;
4723 nsepacutsbeforeppm = *nsepacuts;
4724 nzerohalfcutsbeforeppm = *nzerohalfcuts;
4728 switch(sepadata->ppmethods[i])
4751 0, mod2data->nrowsind, normtype, maxsepacuts, maxcuts, nsepacuts,
4752 nzerohalfcuts, zerohalfcuts, varsolvals,
PPZEROONEROW, result));
4781 sepadata->ppdelta));
4789 SCIPerrorMessage(
"invalid preprocessing method '%c'\n", sepadata->ppmethods[i]);
4793 #ifdef ZEROHALF__PRINT_STATISTICS 4795 ZEROHALFstopTimer(sepadata->pptimers[i]);
4796 ZEROHALFstopTimer(pptimer);
4797 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8.4f\n",
4798 ppname, mod2data->nrowsind, mod2data->ncolsind,
4799 nrowsbeforeppm - mod2data->nrowsind, ncolsbeforeppm - mod2data->ncolsind,
4800 *nsepacuts - nsepacutsbeforeppm, *nzerohalfcuts - nzerohalfcutsbeforeppm,
4801 ZEROHALFevalTimer(pptimer), *nsepacuts, *nzerohalfcuts,
4802 ZEROHALFevalTimer(sepadata->pptimers[i]));
4803 ZEROHALFresetTimer(pptimer);
4807 #ifdef ZEROHALF__PRINT_STATISTICS 4809 ZEROHALFstopTimer(timer);
4810 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8.4f\n",
4811 "PREPROCESSED", mod2data->nrowsind, mod2data->ncolsind,
4812 nrowsinitial - mod2data->nrowsind, ncolsinitial - mod2data->ncolsind,
4813 *nsepacuts - nsepacutsinitial, *nzerohalfcuts - nzerohalfcutsinitial,
4814 ZEROHALFevalTimer(timer), *nsepacuts, *nzerohalfcuts,
4815 ZEROHALFevalTimer(sepadata->pptimers[sepadata->nppmethods]));
4816 ZEROHALFstatisticsMessage(
"\n");
4817 ZEROHALFfreeTimer(timer);
4818 ZEROHALFfreeTimer(pptimer);
4819 ZEROHALFstopTimer(sepadata->pptimers[sepadata->nppmethods]);
4821 ZEROHALFstatisticsMessage(
" | ------------------------------- subproblem ------------------------------- | ------------------------------\n");
4822 ZEROHALFstatisticsMessage(
" | | max2/row | max2/col | A^T ept | \n");
4823 ZEROHALFstatisticsMessage(
"%15s | | %8s | %8s | %8s |\n",
4826 ZEROHALFstatisticsMessage(
"\n");
4846 int naggregatedrrows;
4848 assert(rowaggregation !=
NULL);
4851 naggregatedrrows = 0;
4852 for( i = 0 ; i < nrrows ; ++i)
4870 #define BRANCHPRIORITY__AVOID_BRANCHING 0 4871 #define BRANCHPRIORITY__PREFER_BRANCHING 0 4878 ZEROHALF_AUXIPDATA* auxipdata,
4905 assert(scip !=
NULL);
4906 assert(sepadata !=
NULL);
4907 assert(lpdata !=
NULL);
4908 assert(mod2data !=
NULL);
4909 assert(auxipdata !=
NULL);
4911 assert(mod2data->relatedsubproblem !=
NULL);
4912 assert(mod2data->rows !=
NULL);
4913 assert(mod2data->rowaggregations !=
NULL);
4914 assert(mod2data->rhs !=
NULL);
4915 assert(mod2data->slacks !=
NULL);
4916 assert(mod2data->fracsol !=
NULL);
4917 assert(mod2data->rowsind !=
NULL);
4918 assert(mod2data->colsind !=
NULL);
4920 assert(auxipdata->subscip ==
NULL);
4921 assert(auxipdata->v ==
NULL);
4922 assert(auxipdata->y ==
NULL);
4923 assert(auxipdata->r ==
NULL);
4924 assert(auxipdata->q ==
NULL);
4925 assert(auxipdata->feasipcons ==
NULL);
4926 assert(auxipdata->oddrhscons ==
NULL);
4927 assert(auxipdata->columnsumcons ==
NULL);
4930 auxipdata->m = mod2data->nrowsind;
4931 auxipdata->n = mod2data->ncolsind;
4945 maxslack = sepadata->maxslack;
4946 nrrows = mod2data->relatedsubproblem->nrrows;
4961 if( setnodelimit ==
TRUE )
4962 auxipdata->nodelimit = 3000;
4964 auxipdata->nodelimit = -1;
4967 auxipdata->objectivelimit =
MIN(1.0, maxslack + feastol);
4974 if( auxipdata->timelimit <= 0.0 )
4978 maxnconsvars = auxipdata->m + auxipdata->n + 2;
4988 TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE, &success) );
4991 TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
TRUE, &success) );
4993 SCIPdebugMessage(
"Copying the plugins was %s successful.\n", success ?
"" :
"not");
4998 settingsfileexists =
TRUE;
4999 if( strlen(sepadata->subscipsettings) == 0 )
5000 settingsfileexists =
FALSE;
5001 if( strlen(sepadata->subscipsettings) == 1 && sepadata->subscipsettings[0] ==
'-' )
5002 settingsfileexists =
FALSE;
5004 if( settingsfileexists )
5071 isfeasip = (sepadata->subscipobjective ==
'v' ?
FALSE :
TRUE);
5072 isweighted = (sepadata->subscipobjective ==
'w' ?
TRUE :
FALSE);
5073 ispenalized = (sepadata->subscipobjective ==
'p' ?
TRUE :
FALSE);
5094 for( j = 0 ; j < auxipdata->n ; ++j)
5103 for( i = 0 ; i < auxipdata->m ; ++i)
5106 assert(mod2data->rows[mod2data->rowsind[i]] !=
NULL);
5113 objcoef =
calcObjWeight(mod2data->rowaggregations[mod2data->rowsind[i]], nrrows);
5115 else if( ispenalized )
5117 objcoef = mod2data->slacks[mod2data->rowsind[i]]
5118 + (sepadata->subscipobjpen
5119 *
calcObjWeight(mod2data->rowaggregations[mod2data->rowsind[i]], nrrows));
5125 objcoef = mod2data->slacks[mod2data->rowsind[i]];
5133 for( j = 0 ; j < auxipdata->n ; ++j)
5140 objcoef = mod2data->fracsol[mod2data->colsind[j]];
5151 for( i = 0 ; i < auxipdata->m ; ++i)
5153 consvals[nconsvars] = mod2data->slacks[mod2data->rowsind[i]];
5154 consvars[nconsvars] = auxipdata->v[i];
5157 for( j = 0 ; j < auxipdata->n ; ++j)
5159 consvals[nconsvars] = mod2data->fracsol[mod2data->colsind[j]];
5160 consvars[nconsvars] = auxipdata->y[j];
5164 nconsvars, consvars, consvals, 0.0, auxipdata->objectivelimit,
5170 for( i = 0 ; i < auxipdata->m ; ++i)
5171 if( mod2data->rhs[mod2data->rowsind[i]] ==
TRUE )
5173 consvals[nconsvars] = 1.0;
5174 consvars[nconsvars] = auxipdata->v[i];
5177 consvals[nconsvars] = -2.0;
5178 consvars[nconsvars] = auxipdata->q;
5181 nconsvars, consvars, consvals, 1.0, 1.0,
5185 for( j = 0 ; j < auxipdata->n ; ++j)
5191 for( i = 0 ; i < auxipdata->m ; ++i) {
5192 if( mod2data->rows[mod2data->rowsind[i]][rowsbind] & rowsbmask )
5194 consvals[nconsvars] = 1.0;
5195 consvars[nconsvars] = auxipdata->v[i];
5199 consvals[nconsvars] = -1.0;
5200 consvars[nconsvars] = auxipdata->y[j];
5202 consvals[nconsvars] = -2.0;
5203 consvars[nconsvars] = auxipdata->r[j];
5228 ZEROHALF_AUXIPDATA* auxipdata,
5239 assert(sepadata !=
NULL);
5240 assert(mod2data !=
NULL);
5241 assert(auxipdata !=
NULL);
5242 assert(auxipdata->subscip !=
NULL);
5243 assert(sols !=
NULL);
5244 assert(*sols ==
NULL);
5245 assert(*nsols == 0);
5248 retcode =
SCIPsolve(auxipdata->subscip);
5257 SCIPwarningMessage(scip,
"Error while solving subproblem in zerohalf separator; sub-SCIP terminated with code <%d>\n", retcode);
5265 maxslack = sepadata->maxslack;
5277 if( !sepadata->subscipuseallsols )
5282 if( sepadata->subscipobjective ==
'v' )
5284 for( i = 0 ; i < *nsols ; ++i)
5304 for( i = 0 ; i < *nsols ; ++i)
5307 for( j = 0 ; j < auxipdata->m ; ++j)
5308 z += mod2data->slacks[mod2data->rowsind[j]]
5309 *
SCIPgetSolVal(auxipdata->subscip, (*sols)[i], auxipdata->v[j]);
5310 for( j = 0 ; j < auxipdata->n ; ++j)
5311 z += mod2data->fracsol[mod2data->colsind[j]]
5312 *
SCIPgetSolVal(auxipdata->subscip, (*sols)[i], auxipdata->y[j]);
5317 propersols[npropersols] = (*sols)[i];
5318 viols[npropersols] = z;
5325 for( i = 1 ; i < npropersols && swapped; ++i)
5328 for( j = 0 ; j < npropersols - i ; ++j)
5330 if( viols[j] > viols[j+1] )
5332 tempviol = viols[j+1];
5333 viols[j+1] = viols[j];
5334 viols[j] = tempviol;
5335 tempsol = propersols[j+1];
5336 propersols[j+1] = propersols[j];
5337 propersols[j] = tempsol;
5344 *nsols = npropersols;
5367 assert(scip !=
NULL);
5368 assert(lpdata !=
NULL);
5369 assert(lpdata->nrows > 0);
5370 assert(0 <= rowsindex);
5371 assert(rowsindex < lpdata->nrows);
5372 assert(lpdata->rrowsindexofleftrow[rowsindex] == rrowsindex
5373 || lpdata->rrowsindexofrightrow[rowsindex] == rrowsindex);
5374 assert(weights !=
NULL);
5375 assert(*weights ==
NULL);
5385 if( lpdata->rrowsindexofleftrow[rowsindex] == rrowsindex )
5386 (*weights)[rowsindex] = lpdata->intscalarsleftrow[rowsindex] * (-0.5);
5388 (*weights)[rowsindex] = lpdata->intscalarsrightrow[rowsindex] * 0.5;
5405 ZEROHALF_AUXIPDATA* auxipdata,
5413 assert(scip !=
NULL);
5414 assert(mod2data !=
NULL);
5415 assert(mod2data->nrowsind > 0);
5416 assert(auxipdata !=
NULL);
5417 assert(auxipdata->subscip !=
NULL);
5418 assert(auxipdata->v !=
NULL);
5419 assert(solution !=
NULL);
5420 assert(rrowsincut !=
NULL);
5421 assert(*rrowsincut ==
NULL);
5422 assert(nrrowsincut !=
NULL);
5427 BITARRAYCLEAR(*rrowsincut, mod2data->rowaggregationsbitarraysize);
5432 for( i = 0 ; i < mod2data->nrowsind ; ++i)
5433 if( auxipdata->v[i] !=
NULL )
5436 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[i]], (*rrowsincut) ,
5437 mod2data->rowaggregationsbitarraysize);
5464 ZEROHALF_AUXIPDATA* auxipdata;
5474 assert(scip !=
NULL);
5475 assert(sepadata !=
NULL);
5476 assert(lpdata !=
NULL);
5477 assert(mod2data !=
NULL);
5478 assert(maxsepacuts >= 0);
5479 assert(maxcuts >= 0);
5480 assert(nsepacuts !=
NULL);
5481 assert(nzerohalfcuts !=
NULL);
5482 assert(zerohalfcuts !=
NULL);
5483 assert(*nsepacuts <= *nzerohalfcuts);
5484 assert(varsolvals !=
NULL);
5485 assert(result !=
NULL);
5487 assert(mod2data->relatedsubproblem !=
NULL);
5488 assert(mod2data->rows !=
NULL);
5489 assert(mod2data->rowaggregations !=
NULL);
5490 assert(mod2data->rhs !=
NULL);
5491 assert(mod2data->slacks !=
NULL);
5492 assert(mod2data->fracsol !=
NULL);
5493 assert(mod2data->rowsind !=
NULL);
5494 assert(mod2data->colsind !=
NULL);
5498 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
5502 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
5512 if( auxipdata->subscip ==
NULL )
5525 for( s = 0; s < nsols ; ++s)
5528 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
5534 &rrowsincut, &nrrowsincut));
5535 assert(nrrowsincut > 0);
5540 mod2data, rrowsincut, &weights, &nrowsincut));
5541 if ( weights ==
NULL )
5546 assert(nrowsincut > 0);
5550 SCIP_CALL( debugPrintLPRowsAndCols(scip, lpdata) );
5552 debugPrintSubLpData(scip, lpdata, mod2data->relatedsubproblem);
5553 debugPrintMod2Data(scip, lpdata, mod2data,
TRUE);
5562 mod2data->relatedsubproblem, mod2data, nrrowsincut, nrowsincut,
AUXIP));
5564 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
5584 if( sepadata->subscipobjective !=
'v' )
5607 assert(scip !=
NULL);
5608 assert(mod2data !=
NULL);
5609 assert(row !=
NULL);
5610 assert(maxinnerproduct >= 0);
5611 assert(innerproduct !=
NULL);
5614 *innerproduct = 0.0;
5617 if( mod2data->nrows == 0 || mod2data->nrowsind == 0
5618 || mod2data->ncolsind == 0 )
5622 for( c = 0 ; c < mod2data->ncolsind ; ++c)
5624 rcolindex = mod2data->colsind[c];
5626 *innerproduct += mod2data->fracsol[rcolindex];
5627 if(
SCIPisGT(scip, *innerproduct, maxinnerproduct) )
5651 int maxncombinedrows
5673 assert(scip !=
NULL);
5674 assert(sepadata !=
NULL);
5675 assert(lpdata !=
NULL);
5676 assert(mod2data !=
NULL);
5677 assert(maxsepacuts >= 0);
5678 assert(maxcuts >= 0);
5679 assert(nsepacuts !=
NULL);
5680 assert(nzerohalfcuts !=
NULL);
5681 assert(zerohalfcuts !=
NULL);
5682 assert(*nsepacuts <= *nzerohalfcuts);
5683 assert(varsolvals !=
NULL);
5684 assert(result !=
NULL);
5685 assert(maxncombinedrows >= 1);
5687 assert(mod2data->relatedsubproblem !=
NULL);
5688 assert(mod2data->rows !=
NULL);
5689 assert(mod2data->rowaggregations !=
NULL);
5690 assert(mod2data->rhs !=
NULL);
5691 assert(mod2data->slacks !=
NULL);
5692 assert(mod2data->fracsol !=
NULL);
5693 assert(mod2data->rowsind !=
NULL);
5694 assert(mod2data->colsind !=
NULL);
5698 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
5702 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
5708 last = mod2data->nrowsind - 1;
5711 if( !mod2data->rhs[mod2data->rowsind[first]] )
5713 temp = mod2data->rowsind[first];
5714 mod2data->rowsind[first] = mod2data->rowsind[last];
5715 mod2data->rowsind[last] = temp;
5721 noddrhsrows = first + (mod2data->rhs[mod2data->rowsind[first]] ? 1 : 0);
5724 if( noddrhsrows == 0 )
5730 if( maxncombinedrows > 1 )
5734 BITARRAYCLEAR(rrowsincut, mod2data->rowaggregationsbitarraysize);
5738 assert(noddrhsrows >= 0);
5739 SCIPsortInd( mod2data->rowsind , compRealNonDecreasing , (
void*) mod2data->slacks , noddrhsrows );
5741 if( noddrhsrows < mod2data->nrowsind )
5743 SCIPsortInd( mod2data->rowsind + noddrhsrows , compRealNonDecreasing , (
void*) mod2data->slacks , mod2data->nrowsind - noddrhsrows );
5746 minslackoddrhsrows = mod2data->slacks[mod2data->rowsind[0]];
5748 if(
SCIPisLE(scip, minslackoddrhsrows, sepadata->maxslack) )
5750 for( ncombinedrows = 1 ; ncombinedrows <= maxncombinedrows ; ++ncombinedrows )
5752 switch( ncombinedrows )
5756 for( i = 0 ; i < noddrhsrows ; ++i)
5758 r1 = mod2data->rowsind[i];
5759 assert(mod2data->rhs[r1]);
5760 if( *nzerohalfcuts == maxcuts || *nsepacuts == maxsepacuts )
5762 slack1 = mod2data->slacks[r1];
5763 if(
SCIPisGT(scip, slack1, sepadata->maxslack) )
5766 sepadata->maxslack, &roundingdownweakening));
5767 if(
SCIPisLE(scip, roundingdownweakening + slack1, sepadata->maxslack) )
5774 mod2data, mod2data->rowaggregations[r1], &weights, &nrowsincut));
5775 if( weights ==
NULL )
5779 assert(nrowsincut > 0);
5783 mod2data->relatedsubproblem, mod2data, 2, nrowsincut,
HEURISTICSENUM));
5785 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
5802 assert(combinedrow !=
NULL);
5803 assert(rrowsincut !=
NULL);
5804 if( noddrhsrows == mod2data->nrowsind )
5806 if( mod2data->nrowsind < 2 )
5810 for( i = 0 ; i < noddrhsrows ; ++i)
5812 r1 = mod2data->rowsind[i];
5813 assert(mod2data->rhs[r1]);
5814 if( *nzerohalfcuts == maxcuts || *nsepacuts == maxsepacuts )
5816 slack1 = mod2data->slacks[r1];
5817 if(
SCIPisGT(scip, slack1, sepadata->maxslack) )
5820 for( j = noddrhsrows ; j < mod2data->ncolsind ; ++j)
5822 r2 = mod2data->rowsind[j];
5823 assert(!mod2data->rhs[r2]);
5824 if( *nzerohalfcuts == maxcuts || *nsepacuts == maxsepacuts )
5826 slack2 = mod2data->slacks[r2];
5827 if(
SCIPisGT(scip, slack1 + slack2, sepadata->maxslack) )
5830 BITARRAYSXOR(mod2data->rows[r2], combinedrow, mod2data->rowsbitarraysize);
5832 sepadata->maxslack, &roundingdownweakening));
5833 if(
SCIPisLE(scip, roundingdownweakening + slack1 + slack2, sepadata->maxslack) )
5839 mod2data->rowaggregationsbitarraysize);
5840 BITARRAYSXOR(mod2data->rowaggregations[r2], rrowsincut,
5841 mod2data->rowaggregationsbitarraysize);
5846 mod2data, rrowsincut, &weights, &nrowsincut));
5847 if ( weights ==
NULL )
5851 assert(nrowsincut > 0);
5855 mod2data->relatedsubproblem, mod2data, 2, nrowsincut,
HEURISTICSENUM));
5857 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
5885 if( rrowsincut !=
NULL )
5889 if( combinedrow !=
NULL )
5900 void debugPrintAuxGraphNode(
5906 assert(node !=
NULL);
5909 for( i = 0 ; i < node->nneighbors ; ++i)
5912 i, node->neighbors[i], node->edgeweights[i], node->relatedrows[i]);
5915 node->nneighbors, node->distance, node->previous);
5924 ZEROHALF_AUXGRAPH* graph,
5939 int maxnumberofneighbors;
5941 assert(scip !=
NULL);
5942 assert(graph !=
NULL);
5943 assert(node1index >= 0);
5944 assert(node1index < graph->nnodes);
5945 assert(node2index >= 0);
5946 assert(node2index < graph->nnodes);
5949 maxnumberofneighbors = 2 * graph->nnodes - 2;
5953 node1 = graph->nodes[node1index];
5954 node2 = graph->nodecopies[node2index];
5955 node1copy = graph->nodecopies[node1index];
5956 node2copy = graph->nodes[node2index];
5960 node1 = graph->nodes[node1index];
5961 node2 = graph->nodes[node2index];
5962 node1copy = graph->nodecopies[node1index];
5963 node2copy = graph->nodecopies[node2index];
5966 if( node1->nneighbors == 0 )
5968 assert(maxnumberofneighbors > 0);
5978 if( node2->nneighbors == 0 )
5980 assert(maxnumberofneighbors > 0);
5990 n2 = node2->nneighbors;
5991 for( n1 = 0 ; n1 < node1->nneighbors ; ++n1)
5992 if( node1->neighbors[n1] == node2 )
5994 if( n1 < node1->nneighbors)
5995 for( n2 = 0 ; n2 < node2->nneighbors ; ++n2)
5996 if( node2->neighbors[n2] == node1 )
5998 if( n1 < node1->nneighbors )
6001 assert(node1->neighbors[n1] == node2);
6002 assert(n2 < node2->nneighbors);
6003 assert(node2->neighbors[n2] == node1);
6004 assert(node1->edgeweights[n1] == node2->edgeweights[n2]);
6007 if( n1 == node1->nneighbors ||
SCIPisLT(scip, weight, node1->edgeweights[n1]) )
6009 node1->neighbors[n1] = node2;
6010 node1->edgeweights[n1] = weight;
6011 node1->relatedrows[n1] = relatedrow;
6012 node1->nneighbors++;
6014 node2->neighbors[n2] = node1;
6015 node2->edgeweights[n2] = weight;
6016 node2->relatedrows[n2] = relatedrow;
6017 node2->nneighbors++;
6019 node1copy->neighbors[n1] = node2copy;
6020 node1copy->edgeweights[n1] = weight;
6021 node1copy->relatedrows[n1] = relatedrow;
6022 node1copy->nneighbors++;
6024 node2copy->neighbors[n2] = node1copy;
6025 node2copy->edgeweights[n2] = weight;
6026 node2copy->relatedrows[n2] = relatedrow;
6027 node2copy->nneighbors++;
6040 ZEROHALF_AUXGRAPH* graph,
6048 int nunprocessednodes;
6057 assert(scip !=
NULL);
6058 assert(graph !=
NULL);
6059 assert(graph->nnodes > 0);
6060 assert(sourcenode !=
NULL);
6061 assert(targetnode !=
NULL);
6062 assert(maxdistance > 0.0);
6063 assert(maxdistance <= 1.0);
6069 nunprocessednodes = 0;
6071 for( v = 0; v < graph->nnodes ; ++v)
6073 graph->nodes[v]->distance = 1.0;
6074 graph->nodes[v]->previous =
NULL;
6076 graph->nodecopies[v]->distance = 1.0;
6077 graph->nodecopies[v]->previous =
NULL;
6079 unprocessednodes[nunprocessednodes] = graph->nodes[v];
6080 ++nunprocessednodes;
6081 unprocessednodes[nunprocessednodes] = graph->nodecopies[v];
6082 ++nunprocessednodes;
6084 sourcenode->distance = 0.0;
6085 sourcenode->previous =
NULL;
6087 assert(nunprocessednodes == 2 * graph->nnodes);
6088 assert(nunprocessednodes > 0);
6091 while( nunprocessednodes > 0 )
6095 mindistance = unprocessednodes[0]->distance;
6096 for( v = 1 ; v < nunprocessednodes ; ++v)
6097 if( unprocessednodes[v]->distance < mindistance )
6100 mindistance = unprocessednodes[v]->distance;
6103 if(
SCIPisGT(scip, mindistance, maxdistance) )
6106 currentnode = unprocessednodes[u];
6107 unprocessednodes[u] = unprocessednodes[nunprocessednodes-1];
6108 nunprocessednodes--;
6111 for( n = 0 ; n < currentnode->nneighbors ; ++n)
6113 newdistance = currentnode->distance + currentnode->edgeweights[n];
6115 if(
SCIPisLT(scip, newdistance , currentnode->neighbors[n]->distance) )
6117 currentnode->neighbors[n]->distance = newdistance;
6118 currentnode->neighbors[n]->previous = currentnode;
6120 if( currentnode->neighbors[n] == targetnode )
6153 ZEROHALF_AUXGRAPH* auxgraph;
6168 assert(scip !=
NULL);
6169 assert(sepadata !=
NULL);
6170 assert(lpdata !=
NULL);
6171 assert(mod2data !=
NULL);
6172 assert(maxsepacuts >= 0);
6173 assert(maxcuts >= 0);
6174 assert(nsepacuts !=
NULL);
6175 assert(nzerohalfcuts !=
NULL);
6176 assert(zerohalfcuts !=
NULL);
6177 assert(*nsepacuts <= *nzerohalfcuts);
6178 assert(varsolvals !=
NULL);
6179 assert(result !=
NULL);
6180 assert(wrongstructure !=
NULL);
6182 *wrongstructure =
FALSE;
6185 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
6189 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
6195 *wrongstructure =
TRUE;
6200 if( mod2data->nrowsind == 1 )
6203 normtype, maxsepacuts, maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts,
6204 varsolvals, result, 1));
6213 auxgraph->nnodes = mod2data->ncolsind + 1;
6216 q = auxgraph->nnodes - 1;
6218 for( j = 0 ; j < auxgraph->nnodes ; ++j)
6224 for( i = 0 ; i < mod2data->nrowsind ; ++i)
6226 rowsindex = mod2data->rowsind[i];
6227 for( j = 0 ; j < mod2data->ncolsind; ++j)
6230 for( k = j+1 ; k < mod2data->ncolsind; ++k)
6235 if( j >= mod2data->ncolsind )
6237 if( mod2data->rhs[rowsindex] )
6239 if(
SCIPisLE(scip, mod2data->slacks[rowsindex], sepadata->maxslack) )
6246 mod2data->rowaggregations[rowsindex], &weights, &nrowsincut));
6247 if( weights ==
NULL )
6251 assert(nrowsincut > 0);
6255 mod2data->relatedsubproblem, mod2data, nrrowsincut, nrowsincut,
AUXGRAPH));
6257 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
6269 assert( weights !=
NULL );
6282 if( k >= mod2data->ncolsind )
6286 mod2data->rhs[rowsindex], mod2data->slacks[rowsindex], rowsindex));
6293 mod2data->rhs[rowsindex], mod2data->slacks[rowsindex], rowsindex));
6300 for( n = 0 ; n < auxgraph->nnodes && n != q ; ++n)
6303 FALSE, mod2data->fracsol[mod2data->colsind[n]], -1));
6306 if( cutoff || auxgraph->nnodes == 0 )
6316 for( n = 0 ; n < auxgraph->nnodes && n != q ; ++n)
6319 auxgraph->nodes[n], auxgraph->nodecopies[n], sepadata->maxslack));
6321 if(
SCIPisLE(scip, auxgraph->nodecopies[n]->distance, sepadata->maxslack) )
6327 BITARRAYCLEAR(rrowsincut, mod2data->rowaggregationsbitarraysize);
6331 node = auxgraph->nodecopies[n];
6332 while( node->previous !=
NULL )
6334 for( i = 0 ; i < node->nneighbors ; ++i)
6335 if( node->neighbors[i] == node->previous )
6337 assert(i < node->nneighbors);
6338 rowsindex = node->relatedrows[i];
6339 BITARRAYSXOR(mod2data->rowaggregations[rowsindex], rrowsincut ,
6340 mod2data->rowaggregationsbitarraysize);
6341 node = node->previous;
6346 assert(weights ==
NULL);
6348 mod2data, rrowsincut, &weights, &nrowsincut));
6349 if( weights ==
NULL )
6354 assert(nrowsincut > 0);
6358 mod2data->relatedsubproblem, mod2data, nrrowsincut, nrowsincut,
AUXGRAPH));
6360 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
6372 assert( weights !=
NULL );
6376 if( rrowsincut !=
NULL )
6414 int identsubmatrixsize;
6420 assert(scip !=
NULL);
6421 assert(sepadata !=
NULL);
6422 assert(lpdata !=
NULL);
6423 assert(mod2data !=
NULL);
6424 assert(maxsepacuts >= 0);
6425 assert(maxcuts >= 0);
6426 assert(nsepacuts !=
NULL);
6427 assert(nzerohalfcuts !=
NULL);
6428 assert(zerohalfcuts !=
NULL);
6429 assert(*nsepacuts <= *nzerohalfcuts);
6430 assert(varsolvals !=
NULL);
6431 assert(result !=
NULL);
6435 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
6439 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
6442 if( mod2data->nrowsind == 1 )
6445 normtype, maxsepacuts, maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts,
6446 varsolvals, result, 1));
6450 identsubmatrixsize = 0;
6455 for( pivotcol = 0; pivotcol < mod2data->ncolsind; ++pivotcol )
6457 if( identsubmatrixsize == mod2data->nrowsind )
6461 SCIPsortInd(mod2data->rowsind + identsubmatrixsize , compRealNonDecreasing ,
6462 (
void*) mod2data->slacks , mod2data->nrowsind - identsubmatrixsize);
6465 if(
SCIPisGT(scip, mod2data->slacks[mod2data->rowsind[identsubmatrixsize]], sepadata->maxslack) )
6471 for( pivotrow = identsubmatrixsize ; pivotrow < mod2data->nrowsind ; ++pivotrow)
6472 if( mod2data->rows[mod2data->rowsind[pivotrow]][rowsbind] & rowsbmask )
6474 if( pivotrow == mod2data->nrowsind )
6478 for( r = 0 ; r < mod2data->nrowsind
6479 &&
SCIPisLE(scip, mod2data->slacks[mod2data->rowsind[r]], sepadata->maxslack) ; ++r)
6483 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
6486 mod2data->slacks[mod2data->rowsind[r]] += mod2data->slacks[mod2data->rowsind[pivotrow]];
6490 if(
SCIPisLE(scip, mod2data->slacks[mod2data->rowsind[r]], sepadata->maxslack) )
6493 BITARRAYSXOR(mod2data->rows[mod2data->rowsind[pivotrow]],
6494 mod2data->rows[mod2data->rowsind[r]],mod2data->rowsbitarraysize);
6495 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[pivotrow]],
6496 mod2data->rowaggregations[mod2data->rowsind[r]],mod2data->rowaggregationsbitarraysize);
6497 mod2data->rhs[mod2data->rowsind[r]] =
6498 XOR(mod2data->rhs[mod2data->rowsind[pivotrow]],mod2data->rhs[mod2data->rowsind[r]]);
6504 temp = mod2data->rowsind[pivotrow];
6505 mod2data->rowsind[pivotrow] = mod2data->rowsind[identsubmatrixsize];
6506 mod2data->rowsind[identsubmatrixsize] = temp;
6507 temp = mod2data->colsind[pivotcol];
6508 mod2data->colsind[pivotcol] = mod2data->colsind[identsubmatrixsize];
6509 mod2data->colsind[identsubmatrixsize] = temp;
6511 identsubmatrixsize++;
6524 0, mod2data->nrowsind, normtype, maxsepacuts, maxcuts, nsepacuts,
6554 #ifdef ZEROHALF__PRINT_STATISTICS 6555 int nsepacutsbefore;
6556 int nsepacutsinitial;
6557 int nzerohalfcutsbefore;
6558 int nzerohalfcutsinitial;
6563 int ncutsfoundbefore;
6566 assert(scip !=
NULL);
6567 assert(sepadata !=
NULL);
6568 assert(lpdata !=
NULL);
6569 assert(mod2data !=
NULL);
6570 assert(maxsepacuts >= 0);
6571 assert(maxcuts >= 0);
6572 assert(result !=
NULL);
6573 assert(nsepacuts !=
NULL);
6574 assert(nzerohalfcuts !=
NULL);
6575 assert(zerohalfcuts !=
NULL);
6576 assert(*nsepacuts <= *nzerohalfcuts);
6578 assert(mod2data->relatedsubproblem !=
NULL);
6579 assert(mod2data->rows !=
NULL);
6580 assert(mod2data->rowaggregations !=
NULL);
6581 assert(mod2data->rhs !=
NULL);
6582 assert(mod2data->slacks !=
NULL);
6583 assert(mod2data->fracsol !=
NULL);
6584 assert(mod2data->nrows > 0);
6585 assert(mod2data->rowsind !=
NULL);
6586 assert(mod2data->colsind !=
NULL);
6588 sepadata->nsepamethods = (int) strlen(sepadata->sepamethods);
6589 if( sepadata->nsepamethods > 0 && sepadata->sepamethods[0] ==
'-' )
6590 sepadata->nsepamethods = 0;
6592 if( sepadata->nsepamethods == 0 )
6597 #ifdef ZEROHALF__PRINT_STATISTICS 6598 if( sepadata->sepatimers ==
NULL )
6601 for( i = 0 ; i < sepadata->nsepamethods + 1 ; ++i)
6603 ZEROHALFcreateTimer((sepadata->sepatimers[i]));
6611 nsepacutsinitial = *nsepacuts;
6612 nzerohalfcutsinitial = *nzerohalfcuts;
6614 ZEROHALFstatisticsMessage(
"\n");
6615 ZEROHALFstatisticsMessage(
" | -------------------------- subproblem ----\ 6616 ---------- | - callback (algo) - | ----- callback ---- | --total-\n");
6617 ZEROHALFstatisticsMessage(
" | nrowsind | ncolsind | nsepcuts | ncutsfnd \ 6618 | time | nsepcuts | ncutsfnd | nsepcuts | ncutsfnd | time\n");
6619 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8.4f | %8s | %8s | %8d | %8d | %8.4f\n",
6620 "START PROCESSG", mod2data->nrowsind, mod2data->ncolsind,
6621 0, 0, 0.0,
" ",
" ", *nsepacuts, *nzerohalfcuts, ZEROHALFevalTimer(sepadata->sepatimers[sepadata->nsepamethods]));
6624 if( mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
6627 #ifdef ZEROHALF__PRINT_STATISTICS 6628 ZEROHALFcreateNewTimer(timer);
6629 ZEROHALFcreateNewTimer(sepatimer);
6630 ZEROHALFstartTimer(sepadata->sepatimers[sepadata->nsepamethods]);
6631 ZEROHALFstartTimer(timer);
6635 for( i = 0 ; i < sepadata->nsepamethods && !stop; ++i)
6638 #ifdef ZEROHALF__PRINT_STATISTICS 6639 ZEROHALFstartTimer(sepatimer);
6640 ZEROHALFstartTimer(sepadata->sepatimers[i]);
6641 nsepacutsbefore = *nsepacuts;
6642 nzerohalfcutsbefore = *nzerohalfcuts;
6645 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
6648 if( mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
6653 sepamethod = sepadata->sepamethods[i];
6658 if( *nsepacuts > 0 )
6666 ncutsfoundbefore = *nzerohalfcuts;
6669 nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result));
6671 if( *nzerohalfcuts == ncutsfoundbefore )
6679 maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result, 1));
6684 maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result, 2));
6689 nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result));
6693 ncutsfoundbefore = *nzerohalfcuts;
6695 nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result, &wrongstructure));
6697 if( ! wrongstructure )
6699 if( *nzerohalfcuts == ncutsfoundbefore )
6711 #ifdef ZEROHALF__PRINT_STATISTICS 6713 ZEROHALFstopTimer(sepadata->sepatimers[i]);
6714 ZEROHALFstopTimer(sepatimer);
6715 sepadata->nsepacutsalgo[i] += *nsepacuts - nsepacutsbefore;
6716 sepadata->nzerohalfcutsalgo[i] += *nzerohalfcuts - nzerohalfcutsbefore;
6717 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8d | %8d | %8.4f\n",
6718 sepaname, mod2data->nrowsind, mod2data->ncolsind,
6719 *nsepacuts - nsepacutsbefore, *nzerohalfcuts - nzerohalfcutsbefore,
6720 ZEROHALFevalTimer(sepatimer),
6721 sepadata->nsepacutsalgo[i], sepadata->nzerohalfcutsalgo[i],
6722 *nsepacuts, *nzerohalfcuts, ZEROHALFevalTimer(sepadata->sepatimers[i]));
6723 ZEROHALFresetTimer(sepatimer);
6727 #ifdef ZEROHALF__PRINT_STATISTICS 6729 ZEROHALFstopTimer(timer);
6730 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8.4f | %8s | %8s | %8d | %8d | %8.4f\n",
6731 "PROCESSED", mod2data->nrowsind, mod2data->ncolsind,
6732 *nsepacuts - nsepacutsinitial , *nzerohalfcuts - nzerohalfcutsinitial,
6733 ZEROHALFevalTimer(timer),
" ",
" ", *nsepacuts, *nzerohalfcuts,
6734 ZEROHALFevalTimer(sepadata->sepatimers[sepadata->nsepamethods]));
6735 ZEROHALFfreeTimer(timer);
6736 ZEROHALFfreeTimer(sepatimer);
6737 ZEROHALFstopTimer(sepadata->sepatimers[sepadata->nsepamethods]);
6744 #ifdef ZEROHALF__PRINT_STATISTICS 6747 void printZerohalfCutsStatistics(
6751 int* zerohalfcutsindices,
6761 assert(scip !=
NULL);
6762 assert(zerohalfcuts !=
NULL);
6763 assert(nzerohalfcuts >= 0);
6765 ZEROHALFstatisticsMessage(
"\n");
6766 ZEROHALFstatisticsMessage(
" NZEROHALFCUTS: %6d\n", nzerohalfcuts);
6767 ZEROHALFstatisticsMessage(
" NSEPACUTS: %6d\n", nsepacuts);
6769 if( nzerohalfcuts == 0 )
6772 ZEROHALFstatisticsMessage(
"%15s | index | A | viol | efficacy | ef? \ 6773 | minortho | #nonz | norm | #origrows | #preprows | by | priority\n",
" ");
6774 for( i = 0 ; i < nzerohalfcuts ; ++i)
6776 if( zerohalfcutsindices ==
NULL )
6779 si = zerohalfcutsindices[i];
6781 assert(i < nzerohalfcuts);
6782 cut = zerohalfcuts[si];
6783 ZEROHALFstatisticsMessage(
"%15s | %6d | %1s | %8f | %8f | %3s | %8f | %8d | %8.2f | %9d | %9d | %2s | %8.6f\n",
6785 cut->addedtolp ?
"A" :
"-",
6786 cut->violation, cut->efficacy,
6788 zerohalfcutsminortho !=
NULL ? zerohalfcutsminortho[i] : 0.0,
6789 cut->nnonz, cut->norm, cut->nrowsincut, cut->nrrowsincut,
6790 (cut->separatedby ==
AUXIP ?
"IP" :
6795 (cut->separatedby ==
AUXGRAPH ?
"2R" :
6798 zerohalfcutsprios !=
NULL ? zerohalfcutsprios[i] : 0.0
6815 assert(scip !=
NULL);
6816 assert(sepa !=
NULL);
6835 assert(sepadata !=
NULL);
6837 if( sepadata->pptimers !=
NULL )
6839 #ifdef ZEROHALF__PRINT_STATISTICS 6842 for( i = 0 ; i < sepadata->nppmethods + 1 ; ++i)
6844 ZEROHALFfreeTimer((sepadata->pptimers[i]));
6850 if( sepadata->sepatimers !=
NULL )
6852 #ifdef ZEROHALF__PRINT_STATISTICS 6855 for( i = 0 ; i < sepadata->nsepamethods + 1 ; ++i)
6857 ZEROHALFfreeTimer((sepadata->sepatimers[i]));
6863 #ifdef ZEROHALF__PRINT_STATISTICS 6864 if( sepadata->dtimer !=
NULL )
6866 ZEROHALFfreeTimer((sepadata->dtimer));
6870 if( sepadata->nsepacutsalgo !=
NULL )
6874 if( sepadata->nzerohalfcutsalgo !=
NULL )
6878 if( sepadata->origrows !=
NULL )
6899 int* sortedsubproblems;
6906 int subproblemindex;
6914 assert(sepa !=
NULL);
6916 assert(scip !=
NULL);
6917 assert(result !=
NULL);
6921 assert(sepadata !=
NULL);
6931 if( sepadata->maxncalls > -1 && totalncalls > sepadata->maxncalls - 1 )
6935 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
6936 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
6940 if( sepadata->maxdepth > -1 && depth > sepadata->maxdepth )
6960 if( lpdata->ncols == 0 || lpdata->nrows == 0 )
6967 if( sepadata->onlyorigrows && sepadata->origrows ==
NULL )
6973 for( i = 0 ; i < lpdata->nrows ; ++i )
6975 sepadata->norigrows = lpdata->nrows;
6981 for( i = 0 ; i < sepadata->norigrows - 1 ; ++i )
6983 if( sepadata->origrows[i] > sepadata->origrows[i+1] )
6985 temp = sepadata->origrows[i];
6986 sepadata->origrows[i] = sepadata->origrows[i+1];
6987 sepadata->origrows[i+1] = temp;
6998 maxcuts = sepadata->maxcutsroot;
6999 maxsepacuts =
MIN(maxcuts, sepadata->maxsepacutsroot);
7003 maxcuts = sepadata->maxcuts;
7004 maxsepacuts =
MIN(maxcuts, sepadata->maxsepacuts);
7008 if( maxsepacuts == 0 )
7015 #ifdef ZEROHALF__PRINT_STATISTICS 7016 ZEROHALFstatisticsMessage(
"= SEPA_ZEROHALF ================================================================\ 7017 s=============================================\n");
7029 sepadata->maxslack = 1.0 - 2.0 * sepadata->minviolation;
7035 #ifdef ZEROHALF__PRINT_STATISTICS 7036 if( sepadata->nsepamethods > 0 )
7038 assert(sepadata->nsepacutsalgo !=
NULL);
7039 assert(sepadata->nzerohalfcutsalgo !=
NULL);
7046 sepadata->maxnnonz = 0;
7047 for( i = 0 ; i < lpdata->nrows ; i++ )
7051 sepadata->maxnnonz = (int) floor( 10.0 * sepadata->maxnnonz / (
double) lpdata->nrows);
7052 sepadata->maxnnonz = (int) floor(
MIN(0.1 * lpdata->ncols, sepadata->maxnnonz)) +
NNONZOFFSET;
7056 if( lpdata->subproblems[0]->nrcols == 0 )
7064 if( lpdata->subproblems[0]->nrrows == 0 )
7070 #ifdef ZEROHALF__PRINT_STATISTICS 7071 SCIP_CALL( printPreprocessingStatistics(scip, lpdata) );
7075 if( sepadata->decomposeproblem )
7083 nrcolsfactor = 1.0 / (2.0 * lpdata->ncols);
7084 for( i = 0 ; i < lpdata->nsubproblems; ++i)
7086 sortedsubproblems[i] = i;
7087 subproblempriorities[i] = ((
SCIP_Real) lpdata->subproblems[i]->nrrows)
7088 + nrcolsfactor * ((
SCIP_Real) lpdata->subproblems[i]->nrcols);
7090 SCIPsortRealInt(subproblempriorities, sortedsubproblems, lpdata->nsubproblems);
7096 for( i = 0; i < lpdata->nsubproblems; ++i )
7099 if( nsepacuts >= maxsepacuts || nzerohalfcuts >= maxcuts )
7102 subproblemindex = sortedsubproblems[i];
7103 sepadata->maxslack = 1.0 - 2.0 * sepadata->minviolation;
7108 if( lpdata->subproblems[subproblemindex]->nrrows == 1 && lpdata->subproblems[subproblemindex]->nrcols == 0 )
7113 SCIP_CALL( debugPrintLPRowsAndCols(scip, lpdata) );
7115 debugPrintSubLpData(scip, lpdata, lpdata->subproblems[subproblemindex]);
7122 if( weights ==
NULL )
7129 lpdata, weights, normtype, nzerohalfcuts, &varsolvals, zerohalfcuts[nzerohalfcuts], &cutoff) );
7146 if( lpdata->rrowsindexofleftrow[lpdata->subproblems[subproblemindex]->rrows[0]] >= 0 )
7147 lpdata->rrowsindexofleftrow[lpdata->subproblems[subproblemindex]->rrows[0]] =
7150 if( lpdata->rrowsindexofrightrow[lpdata->subproblems[subproblemindex]->rrows[0]] >= 0 )
7151 lpdata->rrowsindexofrightrow[lpdata->subproblems[subproblemindex]->rrows[0]] =
7159 if( nsepacuts >= maxsepacuts || nzerohalfcuts >= maxcuts )
7169 SCIP_CALL(
preprocess(scip, sepa, sepadata, lpdata, mod2data, normtype, maxsepacuts, maxcuts,
7170 &nsepacuts, &nzerohalfcuts, zerohalfcuts, &varsolvals, result) );
7172 if( nsepacuts < maxsepacuts || nzerohalfcuts < maxcuts )
7175 SCIP_CALL(
process(scip, sepa, sepadata, lpdata, mod2data, normtype, maxsepacuts, maxcuts,
7176 &nsepacuts, &nzerohalfcuts, zerohalfcuts, &varsolvals, result) );
7183 for( j = 0 ; j < nzerohalfcuts ; ++j)
7184 zerohalfcuts[j]->relatedmod2data =
NULL;
7187 #ifdef ZEROHALF__PRINT_STATISTICS 7188 if( !sepadata->usezhcutpool )
7189 printZerohalfCutsStatistics(scip, zerohalfcuts, nzerohalfcuts,
NULL,
NULL,
NULL, nsepacuts);
7192 if( ! cutoff && sepadata->usezhcutpool )
7198 int* sortedzerohalfcuts;
7211 violationbucketsize = 10.0;
7216 for( i = 0 ; i < nzerohalfcuts; ++i)
7218 sortedzerohalfcuts[i] = i;
7219 zerohalfcutpriorities[i] =
SCIPfloor(scip, violationbucketsize * (zerohalfcuts[i])->violation)
7225 for( si = 0; si < nzerohalfcuts; ++si )
7227 cutdatai = zerohalfcuts[sortedzerohalfcuts[si]];
7228 if( cutdatai->cut ==
NULL || !cutdatai->addedtolp )
7230 hasminorthogonality =
TRUE;
7231 for( sj = 0; hasminorthogonality && sj < si; ++sj )
7233 cutdataj = zerohalfcuts[sortedzerohalfcuts[sj]];
7234 if( cutdataj->cut !=
NULL && cutdataj->addedtolp )
7237 hasminorthogonality =
FALSE;
7241 if( hasminorthogonality && cutdatai->addedtolp )
7244 if( sepadata->delayedcuts && !cutdatai->islocal )
7256 if( !cutdatai->islocal )
7260 cutdatai->addedtolp =
TRUE;
7265 cutdatai->addedtolp =
FALSE;
7269 nsepacuts -= nignoredcuts;
7271 #ifdef ZEROHALF__PRINT_STATISTICS 7272 printZerohalfCutsStatistics(scip, zerohalfcuts, nzerohalfcuts, sortedzerohalfcuts,
7273 zerohalfcutpriorities,
NULL, nsepacuts);
7283 for( i = 0 ; i < nzerohalfcuts; ++i )
7285 cutdatai = zerohalfcuts[i];
7287 if( cutdatai->cut ==
NULL || !cutdatai->addedtolp )
7290 sortedzerohalfcuts[ncutpool] = i;
7291 zerohalfcutminortho[ncutpool] = 1.0;
7292 zerohalfcutpriorities[ncutpool] =
SCIPfloor(scip, violationbucketsize * cutdatai->efficacy)
7294 +
SCIPfloor(scip, violationbucketsize * zerohalfcutminortho[ncutpool]);
7298 ncutpoolold = ncutpool;
7301 while( ncutpool > 0 )
7310 assert(cutdatai->addedtolp);
7316 for( i = 0; i < ncutpool; i++ )
7319 if( zerohalfcutpriorities[i] > bestscore )
7321 bestscore = zerohalfcutpriorities[i];
7326 cutdatai = zerohalfcuts[sortedzerohalfcuts[bestpos]];
7335 if( !cutdatai->islocal )
7340 priotmp = zerohalfcutpriorities[bestpos];
7341 minorthotmp = zerohalfcutminortho[bestpos];
7342 sortidxtmp = sortedzerohalfcuts[bestpos];
7345 zerohalfcutpriorities[bestpos] = zerohalfcutpriorities[ncutpool-1];
7346 zerohalfcutminortho[bestpos] = zerohalfcutminortho[ncutpool-1];
7347 sortedzerohalfcuts[bestpos] = sortedzerohalfcuts[ncutpool-1];
7351 zerohalfcutpriorities[ncutpool] = priotmp;
7352 zerohalfcutminortho[ncutpool] = minorthotmp;
7353 sortedzerohalfcuts[ncutpool] = sortidxtmp;
7357 while( j < ncutpool )
7361 cutdataj = zerohalfcuts[sortedzerohalfcuts[j]];
7366 priotmp = zerohalfcutpriorities[j];
7367 minorthotmp = zerohalfcutminortho[j];
7368 sortidxtmp = sortedzerohalfcuts[j];
7371 zerohalfcutpriorities[j] = zerohalfcutpriorities[ncutpool-1];
7372 zerohalfcutminortho[j] = zerohalfcutminortho[ncutpool-1];
7373 sortedzerohalfcuts[j] = sortedzerohalfcuts[ncutpool-1];
7374 cutdataj->addedtolp =
FALSE;
7379 zerohalfcutpriorities[ncutpool] = priotmp;
7380 zerohalfcutminortho[ncutpool] = minorthotmp;
7381 sortedzerohalfcuts[ncutpool] = sortidxtmp;
7386 if( thisortho < zerohalfcutminortho[j] )
7388 zerohalfcutminortho[j] = thisortho;
7389 zerohalfcutpriorities[j] =
SCIPfloor(scip, violationbucketsize * cutdataj->efficacy)
7391 +
SCIPfloor(scip, violationbucketsize * zerohalfcutminortho[j]);
7397 nsepacuts -= nignoredcuts;
7399 #ifdef ZEROHALF__PRINT_STATISTICS 7400 printZerohalfCutsStatistics(scip, zerohalfcuts, ncutpoolold, sortedzerohalfcuts,
7401 zerohalfcutpriorities, zerohalfcutminortho, nsepacuts);
7412 sepadata->totalncutsfound += nzerohalfcuts;
7413 sepadata->totalnsepacuts += nsepacuts;
7416 if( varsolvals !=
NULL )
7421 for( i = 0 ; i < nzerohalfcuts ; ++i)
7454 ncharsprinted =
SCIPmemccpy(preprocessingmethodsdescription,
7455 "preprocessing methods and ordering:\n" 7456 " # 'd' columns with small LP solution,\n" 7457 " # 'G' modified Gaussian elimination,\n" 7458 " # 'i' identical columns,\n" 7459 " # 'I' identical rows,\n" 7460 " # 'L' large slack rows,\n" 7461 " # 'M' large slack rows (minslack),\n" 7466 ncharsprinted +=
SCIPmemccpy(&(preprocessingmethodsdescription[ncharsprinted - 1]),
7467 " # 'X' add trivial zerohalf cuts,\n" 7468 " # 'z' zero columns,\n" 7469 " # 'Z' zero rows,\n" 7470 " # 'C' fast {'z','s'},\n" 7471 " # 'R' fast {'Z','L','I'}\n" 7473 " # '-' no preprocessing\n" 7474 " #",
'\0', (
unsigned int) (
SCIP_MAXSTRLEN - ncharsprinted - 1));
7478 ncharsprinted =
SCIPmemccpy(sepamethodsdescription,
7479 "separating methods and ordering:\n" 7480 " # '!' stop further processing if a cut was found,\n" 7481 " # '2' exact polynomial time algorithm (only if matrix has max 2 odd entries per row),\n" 7482 " # 'e' enumeration heuristics (k=1: try all preprocessed rows),\n" 7483 " # 'E' enumeration heuristics (k=2: try all combinations of up to two preprocessed rows),\n" 7484 " # 'g' Extended Gaussian elimination heuristics,\n",
'\0',
SCIP_MAXSTRLEN - 1);
7488 ncharsprinted +=
SCIPmemccpy(&(sepamethodsdescription[ncharsprinted - 1]),
7489 " # 's' auxiliary IP heuristics (i.e. number of solved nodes is limited)\n" 7490 " # 'S' auxiliary IP exact (i.e. unlimited number of nodes)\n" 7492 " # '-' no processing\n" 7493 " #",
'\0', (
unsigned int) (
SCIP_MAXSTRLEN - ncharsprinted - 1));
7497 ncharsprinted =
SCIPmemccpy(subscipobjectivedescription,
7498 "auxiliary IP objective:\n" 7499 " # 'v' maximize cut violation,\n" 7500 " # 'u' minimize number of aggregated rows in cut,\n" 7501 " # 'w' minimize number of aggregated rows in cut\n" 7502 " # weighted by the number of rows in the aggregation,\n",
'\0',
SCIP_MAXSTRLEN - 1);
7506 ncharsprinted +=
SCIPmemccpy(&(subscipobjectivedescription[ncharsprinted - 1]),
7507 " # 'p' maximize cut violation and penalize a high number\n" 7508 " # of aggregated rows in the cut weighted by the number\n" 7509 " # of rows in the aggregation and the penalty factor p\n" 7510 " #",
'\0', (
unsigned int) (
SCIP_MAXSTRLEN - ncharsprinted - 1));
7518 sepadata->totalncutsfound = 0;
7519 sepadata->totalnsepacuts = 0;
7520 sepadata->pptimers =
NULL;
7521 sepadata->dtimer =
NULL;
7522 sepadata->sepatimers =
NULL;
7523 sepadata->nsepacutsalgo =
NULL;
7524 sepadata->nzerohalfcutsalgo =
NULL;
7526 sepadata->ppmethods =
NULL;
7527 sepadata->sepamethods =
NULL;
7528 sepadata->nppmethods = -1;
7529 sepadata->nsepamethods = -1;
7530 sepadata->subscipsettings =
NULL;
7532 sepadata->norigrows = 0;
7533 sepadata->origrows =
NULL;
7538 sepaExeclpZerohalf,
NULL,
7541 assert(sepa !=
NULL);
7549 "separating/zerohalf/maxrounds",
7550 "maximal number of zerohalf separation rounds per node (-1: unlimited)",
7553 "separating/zerohalf/maxroundsroot",
7554 "maximal number of zerohalf separation rounds in the root node (-1: unlimited)",
7557 "separating/zerohalf/maxsepacuts",
7558 "maximal number of {0,1/2}-cuts separated per separation round",
7561 "separating/zerohalf/maxsepacutsroot",
7562 "maximal number of {0,1/2}-cuts separated per separation round in the root node",
7565 "separating/zerohalf/dynamiccuts",
7566 "should generated cuts be removed from the LP if they are no longer tight?",
7571 "separating/zerohalf/maxcutsfound",
7572 "maximal number of {0,1/2}-cuts determined per separation round\n\ 7573 # (this includes separated but inefficacious cuts)",
7576 "separating/zerohalf/maxcutsfoundroot",
7577 "maximal number of {0,1/2}-cuts determined per separation round in the root node\n\ 7578 # (this includes separated but inefficacious cuts)",
7583 "separating/zerohalf/maxdepth",
7584 "separating cuts only if depth <= maxdepth (-1: unlimited)",
7587 "separating/zerohalf/maxncalls",
7588 "maximal number of calls (-1: unlimited)",
7591 "separating/zerohalf/relaxcontvars",
7592 "should continuous variables be relaxed by adding variable bounds?",
7595 "separating/zerohalf/scalefraccoeffs",
7596 "should rows be scaled to make fractional coefficients integer?",
7599 "separating/zerohalf/ignoreprevzhcuts",
7600 "should zerohalf cuts found in previous callbacks ignored?",
7603 "separating/zerohalf/onlyorigrows",
7604 "should only original LP rows be considered (i.e. ignore previously added LP rows)?",
7608 "separating/zerohalf/usezhcutpool",
7609 "should zerohalf cuts be filtered using a cutpool?",
7612 "separating/zerohalf/delayedcuts",
7613 "should cuts be added to the delayed cut pool?",
7616 "separating/zerohalf/maxtestdelta",
7617 "maximal number of different deltas to try for cmir (-1: unlimited, 0: delta=1)",
7620 "separating/zerohalf/trynegscaling",
7621 "should negative values also be tested in scaling for cmir?",
7626 "separating/zerohalf/preprocessing/decomposeproblem",
7627 "should problem be decomposed into subproblems (if possible) before applying preprocessing?",
7630 "separating/zerohalf/preprocessing/delta",
7631 "value of delta parameter used in preprocessing method 'd'",
7634 "separating/zerohalf/preprocessing/ppmethods",
7635 preprocessingmethodsdescription,
7641 "separating/zerohalf/separating/forcecutstolp",
7642 "should the cuts be forced to enter the LP?",
7645 "separating/zerohalf/separating/forcecutstosepastore",
7646 "should the cuts be forced to enter SCIP's sepastore?",
7649 "separating/zerohalf/separating/minviolation",
7650 "minimal violation of a {0,1/2}-cut to be separated",
7653 "separating/zerohalf/separating/sepamethods",
7654 sepamethodsdescription,
7660 "separating/zerohalf/separating/auxip/settingsfile",
7661 "optional settings file of the auxiliary IP (-: none)",
7664 "separating/zerohalf/separating/auxip/sollimit",
7665 "limits/solutions setting of the auxiliary IP",
7668 "separating/zerohalf/separating/auxip/penaltyfactor",
7669 "penalty factor used with objective function 'p' of auxiliary IP",
7672 "separating/zerohalf/separating/auxip/useallsols",
7673 "should all (proper) solutions of the auxiliary IP be used to generate cuts instead of using only the best?",
7676 "separating/zerohalf/separating/auxip/objective",
7677 subscipobjectivedescription,
enum SCIP_Result SCIP_RESULT
int SCIPgetNLPBranchCands(SCIP *scip)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
static SCIP_RETCODE ZerohalfMod2DataFree(SCIP *scip, ZEROHALF_MOD2DATA **mod2data)
#define DEFAULT_SCALEFRACCOEFFS
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
static SCIP_RETCODE preprocessConsiderMinSlack(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, SCIP_Bool removelargeslackrows, SCIP_Bool removelargecolrows)
#define SCIPallocMemory(scip, ptr)
static SCIP_RETCODE ZerohalfAuxGraphNodeCreate(SCIP *scip, ZEROHALF_AUXGRAPH_NODE **node)
#define DEFAULT_SUBSCIPSOLLIMIT
int SCIPmemccpy(char *dest, const char *src, char stop, unsigned int cnt)
const char * SCIPvarGetName(SCIP_VAR *var)
static SCIP_RETCODE ZerohalfSubLPDataCreate(SCIP *scip, ZEROHALF_SUBLPDATA **subproblem)
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE getBitarrayOfSelectedRows(SCIP *scip, ZEROHALF_MOD2DATA *mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_SOL *solution, BITARRAY *rrowsincut, int *nrrowsincut)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
static SCIP_RETCODE preprocess(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
#define DEFAULT_FORCECUTSTOSEPASTORE
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
#define ISEVEN(scip, value)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
#define ISODD(scip, value)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
#define DEFAULT_RELAXCONTVARS
#define IDENT_TO_ROW_WITH_SMALLER_SLACK
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
#define DEFAULT_MAXCUTSROOT
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
#define DEFAULT_FORCECUTSTOLP
static SCIP_RETCODE preprocessTrivialZerohalfCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, int firstrowsind, int lastrowsind, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, CUTSEPARATEDBY cutseparatedby, SCIP_RESULT *result)
static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
#define CONTINUOUS_VARIABLE
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
#define SCIPfreeMemoryArray(scip, ptr)
int SCIProwGetNLPNonz(SCIP_ROW *row)
static SCIP_RETCODE process(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
SCIP_RETCODE SCIPincludeSepaZerohalf(SCIP *scip)
int SCIProwGetIndex(SCIP_ROW *row)
#define SCIPallocMemoryArray(scip, ptr, num)
#define DEFAULT_SEPAMETHODS
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
int SCIPsnprintf(char *t, int len, const char *s,...)
enum SCIP_Retcode SCIP_RETCODE
#define SLACK_GREATER_THAN_MSL_MINUS_SODD
static SCIP_RETCODE preprocessRows(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, int firstrowsind, int lastrowsind, SCIP_Bool removezerorows, SCIP_Bool removelargeslackrows, SCIP_Bool removeidenticalrows)
static SCIP_RETCODE ZerohalfAuxGraphNodeFree(SCIP *scip, ZEROHALF_AUXGRAPH_NODE **node)
#define BRANCHPRIORITY__PREFER_BRANCHING
static SCIP_RETCODE getRelevantColumns(SCIP *scip, ZEROHALF_LPDATA *lpdata)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
static SCIP_RETCODE ZerohalfLPDataFree(SCIP *scip, ZEROHALF_LPDATA **lpdata)
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_Bool setnodelimit)
#define DEFAULT_DELAYEDCUTS
static SCIP_RETCODE getZerohalfWeightvectorForSingleRow(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, int rowsindex, int rrowsindex, SCIP_Real **weights)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define BITARRAYBITMASKTYPE
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_DECL_SORTINDCOMP(compRealNonDecreasing)
static const unsigned int Zerohalf_bitarraybasetypesize_nbits
#define BMSclearMemoryArray(ptr, num)
enum cutseparatedby CUTSEPARATEDBY
#define BITARRAYCLEAR(barray, barraysize)
#define DEFAULT_SUBSCIPSETTINGS
static SCIP_RETCODE preprocessColumns(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, int firstcolsind, int lastcolsind, SCIP_Bool removezerocols, SCIP_Bool removecolsingletons, SCIP_Bool checkresultingrows)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
#define DEFAULT_SUBSCIPOBJPEN
static void findClosestLb(SCIP *scip, ZEROHALF_LPDATA *lpdata, SCIP_COL *col, SCIP_Real *bestlbsol, int *bestlbtype, SCIP_VAR **bestzvlb, SCIP_Real *bestbvlb, SCIP_Real *bestdvlb)
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_MAXROUNDSROOT
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
static SCIP_RETCODE createZerohalfCutFromZerohalfWeightvector(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, SCIP_Real *weights, char normtype, int nzerohalfcuts, SCIP_Real **varsolvals, ZEROHALF_CUTDATA *cutdata, SCIP_Bool *cutoff)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
int SCIPgetNSols(SCIP *scip)
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_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
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)
static SCIP_RETCODE ZerohalfCutDataCreate(SCIP *scip, ZEROHALF_CUTDATA **cutdata, ZEROHALF_SUBLPDATA *relatedsubproblem, ZEROHALF_MOD2DATA *relatedmod2data, int nrrowsincut, int nrowsincut, CUTSEPARATEDBY separatedby)
static SCIP_RETCODE ZerohalfLPDataCreate(SCIP *scip, ZEROHALF_LPDATA **lpdata)
struct Zerohalf_LPData ZEROHALF_LPDATA
#define BITARRAYSXOR(barray1, barray2, size)
static void findClosestUb(SCIP *scip, ZEROHALF_LPDATA *lpdata, SCIP_COL *col, SCIP_Real *bestubsol, int *bestubtype, SCIP_VAR **bestzvub, SCIP_Real *bestbvub, SCIP_Real *bestdvub)
int SCIPcolGetLPPos(SCIP_COL *col)
#define SCIPfreeMemory(scip, ptr)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void ZerohalfSubLPDataFree(SCIP *scip, ZEROHALF_SUBLPDATA **subproblem)
#define GETBITARRAYINDEX(pos)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
static SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf)
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE
static SCIP_RETCODE solveSubscip(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_MOD2DATA *mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_SOL ***sols, int *nsols)
static SCIP_RETCODE getRelevantRows(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata)
#define DEFAULT_DECOMPOSEPROBLEM
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define DEFAULT_IGNOREPREVIOUSZHCUTS
SCIP_Real SCIPepsilon(SCIP *scip)
#define BMSmoveMemoryArray(ptr, source, num)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define BITARRAYSAREEQUAL(barray1, barray2, size)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE addEdgeToAuxGraph(SCIP *scip, ZEROHALF_AUXGRAPH *graph, int node1index, int node2index, SCIP_Bool isodd, SCIP_Real weight, int relatedrow)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
static void markColAsRemovedAndClearCol(ZEROHALF_MOD2DATA *mod2data, int c, int flag)
static SCIP_RETCODE preprocessIdenticalColums(SCIP *scip, ZEROHALF_MOD2DATA *mod2data)
static SCIP_RETCODE preprocessColumnsWithSmallFracsol(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_MOD2DATA *mod2data, SCIP_Real delta)
#define BOUNDTYPESFORTRANS
static SCIP_RETCODE separateByEnumerationHeuristics(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result, int maxncombinedrows)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
static SCIP_RETCODE separateByAuxGraph(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result, SCIP_Bool *wrongstructure)
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIPinfinity(SCIP *scip)
#define BRANCHPRIORITY__AVOID_BRANCHING
static SCIP_Real calcObjWeight(BITARRAY rowaggregation, int nrrows)
#define BITARRAYBITSET(barray, pos)
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_PPMETHODS
#define BITARRAYBITISSET(barray, pos)
SCIP_RETCODE SCIPfree(SCIP **scip)
static SCIP_RETCODE ZerohalfAuxGraphCreate(SCIP *scip, ZEROHALF_AUXGRAPH **auxgraph)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define NO_RELEVANT_COLUMNS
static SCIP_RETCODE ZerohalfAuxIPDataFree(SCIP *scip, ZEROHALF_AUXIPDATA **auxipdata)
static SCIP_RETCODE decomposeProblem(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata)
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
static SCIP_RETCODE separateByGaussHeuristics(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SMALL_FRACSOL_HEUR
#define DEFAULT_MINVIOLATION
static SCIP_RETCODE ZerohalfAuxIPDataCreate(SCIP *scip, ZEROHALF_AUXIPDATA **auxipdata)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
static const unsigned int Zerohalf_bitarraybasetypesize
static void markRowAsRemoved(ZEROHALF_MOD2DATA *mod2data, int r, int flag)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
static SCIP_RETCODE addZerohalfCutToLP(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_CUTDATA *cutdata, int *nsepacuts, SCIP_RESULT *result)
#define DEFAULT_SUBSCIPUSEALLSOLS
static SCIP_RETCODE ZerohalfAuxGraphFree(SCIP *scip, ZEROHALF_AUXGRAPH **auxgraph)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
struct Zerohalf_CutData ZEROHALF_CUTDATA
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
static SCIP_RETCODE dijkstra(SCIP *scip, ZEROHALF_AUXGRAPH *graph, ZEROHALF_AUXGRAPH_NODE *sourcenode, ZEROHALF_AUXGRAPH_NODE *targetnode, SCIP_Real maxdistance)
#define IDENT_TO_ANOTHER_COLUMN
#define SLACK_GREATER_THAN_MAXSLACK
#define ALL_MATRIX_ROWS_DELETED
int SCIPvarGetNVlbs(SCIP_VAR *var)
#define BMScopyMemoryArray(ptr, source, num)
SCIP_RETCODE SCIPchgVarBranchPriority(SCIP *scip, SCIP_VAR *var, int branchpriority)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
SCIP_RETCODE SCIPprintOrigProblem(SCIP *scip, FILE *file, const char *extension, SCIP_Bool genericnames)
Constraint handler for linear constraints in their most general form, .
int SCIPgetDepth(SCIP *scip)
static SCIP_RETCODE ZerohalfMod2DataCreate(SCIP *scip, ZEROHALF_MOD2DATA **mod2data)
SCIP_Real SCIProwGetOrthogonality(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPreadParams(SCIP *scip, const char *filename)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
#define LP_SOL_EQUALS_ODD_LB
#define XOR(bool1, bool2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPcreate(SCIP **scip)
#define DEFAULT_SUBSCIPOBJECTIVE
#define DEFAULT_DYNAMICCUTS
#define LP_SOL_EQUALS_ODD_UB
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE getZerohalfWeightvectorFromSelectedRowsBitarray(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, BITARRAY rrowsincut, SCIP_Real **weights, int *nrowsincut)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
int SCIPvarGetProbindex(SCIP_VAR *var)
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE calcInnerProductOfRowAndFracsol(SCIP *scip, ZEROHALF_MOD2DATA *mod2data, BITARRAY row, SCIP_Real maxinnerproduct, SCIP_Real *innerproduct)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
enum SCIP_Stage SCIP_STAGE
#define GETBITARRAYMASK(pos)
#define DEFAULT_MAXROUNDS
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
#define DEFAULT_MAXNCALLS
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
#define DEFAULT_USEZHCUTPOOL
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
#define LP_SOL_EQUALS_EVEN_LB
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcopyPlugins(SCIP *sourcescip, SCIP *targetscip, SCIP_Bool copyreaders, SCIP_Bool copypricers, SCIP_Bool copyconshdlrs, SCIP_Bool copyconflicthdlrs, SCIP_Bool copypresolvers, SCIP_Bool copyrelaxators, SCIP_Bool copyseparators, SCIP_Bool copypropagators, SCIP_Bool copyheuristics, SCIP_Bool copyeventhdlrs, SCIP_Bool copynodeselectors, SCIP_Bool copybranchrules, SCIP_Bool copydisplays, SCIP_Bool copydialogs, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
static SCIP_RETCODE storeMod2Data(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, int subproblemindex, ZEROHALF_MOD2DATA *mod2data)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPcutGenerationHeuristicCmir(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *varsolvals, int maxtestdelta, SCIP_Real *rowweights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Bool trynegscaling, SCIP_Bool cutremovable, const char *cutclassname, SCIP_Bool *cutoff, int *ncuts, SCIP_Real *delta, SCIP_Bool *deltavalid)
#define DEFAULT_TRYNEGSCALING
#define GETREQUIREDBITARRAYSIZE(nvalstostore)
static SCIP_RETCODE separateBySolvingAuxIP(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, SCIP_Bool setnodelimit, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
#define LP_SOL_EQUALS_EVEN_UB
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
#define DEFINES_VIOLATED_ZEROHALF_CUT
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIProwGetSumNorm(SCIP_ROW *row)
#define DEFAULT_ONLYORIGROWS
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
int SCIPcolGetNNonz(SCIP_COL *col)
static SCIP_RETCODE preprocessModGaussElim(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data)
static SCIP_RETCODE ZerohalfCutDataFree(SCIP *scip, ZEROHALF_CUTDATA **cutdata)
SCIP_RETCODE SCIPprintBestSol(SCIP *scip, FILE *file, SCIP_Bool printzeros)
static SCIP_DECL_SEPAFREE(sepaFreeZerohalf)
struct SCIP_SepaData SCIP_SEPADATA
#define DEFAULT_MAXSEPACUTSROOT
static SCIP_Bool hasMatrixMax2EntriesPerRow(ZEROHALF_MOD2DATA *mod2data)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
#define DEFAULT_MAXTESTDELTA
static SCIP_DECL_SEPACOPY(sepaCopyZerohalf)