55 #define SEPA_NAME "zerohalf" 56 #define SEPA_DESC "{0,1/2}-cuts separator" 57 #define SEPA_PRIORITY -6000 59 #define SEPA_MAXBOUNDDIST 0.0 60 #define SEPA_USESSUBSCIP TRUE 61 #define SEPA_DELAY FALSE 63 #define DEFAULT_MAXROUNDS 5 64 #define DEFAULT_MAXROUNDSROOT 10 65 #define DEFAULT_MAXSEPACUTS 50 66 #define DEFAULT_MAXSEPACUTSROOT 500 67 #define DEFAULT_DYNAMICCUTS TRUE 68 #define DEFAULT_DECOMPOSEPROBLEM FALSE 69 #define DEFAULT_MAXDEPTH -1 70 #define DEFAULT_MINVIOLATION 0.30 71 #define DEFAULT_FORCECUTSTOLP FALSE 72 #define DEFAULT_FORCECUTSTOSEPASTORE FALSE 74 #define DEFAULT_MAXCUTS 100 76 #define DEFAULT_MAXCUTSROOT 1000 78 #define DEFAULT_SUBSCIPOBJECTIVE 'v' 79 #define DEFAULT_RELAXCONTVARS FALSE 80 #define DEFAULT_SCALEFRACCOEFFS TRUE 81 #define DEFAULT_SUBSCIPSETTINGS "-" 82 #define DEFAULT_SUBSCIPSOLLIMIT -1 83 #define DEFAULT_SUBSCIPUSEALLSOLS TRUE 85 #define DEFAULT_PPDELTA 0.500 86 #define DEFAULT_SUBSCIPOBJPEN 0.001 88 #define DEFAULT_PPMETHODS "CXGXIM" 89 #define DEFAULT_SEPAMETHODS "2g" 90 #define DEFAULT_MAXNCALLS -1LL 91 #define DEFAULT_IGNOREPREVIOUSZHCUTS FALSE 92 #define DEFAULT_ONLYORIGROWS FALSE 93 #define DEFAULT_USEZHCUTPOOL TRUE 94 #define DEFAULT_DELAYEDCUTS TRUE 95 #define DEFAULT_MAXTESTDELTA 10 96 #define DEFAULT_TRYNEGSCALING TRUE 103 #define NNONZOFFSET 500 104 #define BOUNDSWITCH 0.50 106 #define ALLOWLOCAL TRUE 107 #define FIXINTEGRALRHS TRUE 108 #define BOUNDSFORTRANS NULL 109 #define BOUNDTYPESFORTRANS NULL 110 #define MAXWEIGHTRANGE 10000.00 116 #define MAXSCALE 1000.0 119 #define USEVARBOUNDS TRUE 174 #define ISEVEN(scip, value) (SCIPisEQ((scip) , SCIPfloor(scip , (value) / 2) , (value) / 2)) 175 #define ISODD(scip, value) (!(ISEVEN((scip), (value)))) 176 #define XOR(bool1, bool2) ((bool1) ^ (bool2)) 177 #define DIV(value1, powerof2value) (((unsigned int)(value1)) / ((unsigned int)(powerof2value))) 178 #define MOD(value1, powerof2value) (((unsigned int)(value1)) % ((unsigned int)(powerof2value))) 180 #ifndef BMSmoveMemoryArray 182 #define BMSmoveMemoryArray(ptr, source, num) \ 184 size_t size__ = (num) * sizeof(*(ptr)); \ 187 assert((void*)(ptr) != NULL); \ 188 assert((void*)(source) != NULL); \ 189 memmove((void*)(ptr), (void*)(source), size__); \ 194 #ifdef ZEROHALF__PRINT_STATISTICS 196 #define ZEROHALFstatistics(x) x 197 #define ZEROHALFstatisticsMessage printf("#### ") ; printf 198 #define ZEROHALFcreateNewTimer(timervar) SCIP_CALL(SCIPcreateClock(scip, &timervar)) 199 #define ZEROHALFcreateTimer(timervar) SCIP_CALL(SCIPcreateClock(scip, &timervar)) 200 #define ZEROHALFfreeTimer(timervar) SCIP_CALL(SCIPfreeClock(scip, &timervar)) 201 #define ZEROHALFresetTimer(timervar) SCIP_CALL(SCIPresetClock(scip, timervar)) 202 #define ZEROHALFstartTimer(timervar) SCIP_CALL(SCIPstartClock(scip, timervar)) 203 #define ZEROHALFstopTimer(timervar) SCIP_CALL(SCIPstopClock(scip, timervar)) 204 #define ZEROHALFevalTimer(timervar) (SCIPgetClockTime(scip, timervar)) 209 #define ZEROHALFstatistics(x) 210 #define ZEROHALFstatisticsMessage while( FALSE ) printf 211 #define ZEROHALFcreateNewTimer(timervar) 212 #define ZEROHALFcreateTimer(timervar) 213 #define ZEROHALFfreeTimer(timervar) 214 #define ZEROHALFresetTimer(timervar) 215 #define ZEROHALFstartTimer(timervar) 216 #define ZEROHALFstopTimer(timervar) 217 #define ZEROHALFevalTimer(timervar) (0.0) 228 #define IRRELEVANT -1 231 #define ZERO_ROW -100 232 #define IDENT_TO_ROW_WITH_SMALLER_SLACK -101 233 #define SLACK_GREATER_THAN_MAXSLACK -102 234 #define DEFINES_VIOLATED_ZEROHALF_CUT -103 236 #define ROW_IN_SUBPROB_WITHOUT_ODD_RHS -104 238 #define NONEXISTENT_ROW -105 239 #define NO_RELEVANT_COLUMNS -106 240 #define SLACK_GREATER_THAN_MSL_MINUS_SODD -107 242 #define LARGE_COL_EXISTS -108 247 #define ZERO_COLUMN -200 248 #define IDENT_TO_ANOTHER_COLUMN -201 249 #define ZERO_LP_SOL -202 250 #define LP_SOL_EQUALS_EVEN_LB -203 251 #define LP_SOL_EQUALS_ODD_LB -204 252 #define LP_SOL_EQUALS_EVEN_UB -205 253 #define LP_SOL_EQUALS_ODD_UB -206 254 #define SINGLETON_COLUMN -207 255 #define CONTINUOUS_VARIABLE -208 256 #define SMALL_FRACSOL_HEUR -209 257 #define ALL_MATRIX_ROWS_DELETED -210 259 #define COLUMN_IN_SUBPROB_WITHOUT_ODD_RHS -211 268 #define BITARRAYBASETYPE unsigned int 269 #define BITARRAYBITMASKTYPE BITARRAYBASETYPE 278 #define BITARRAY BITARRAYBASETYPE* 281 #define BITMASK(pos) ((unsigned int)(1u << (pos))) 284 #define BITSET(var, pos) (var) |= BITMASK(pos) 287 #define BITISSET(var, pos) (var & BITMASK(pos)) 290 #define BITARRAYBITSET(barray, pos) BITSET(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \ 291 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 294 #define BITARRAYBITISSET(barray, pos) BITISSET(barray[DIV(pos,Zerohalf_bitarraybasetypesize_nbits)], \ 295 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 298 #define BITARRAYCLEAR(barray, barraysize) BMSclearMemoryArray(barray,barraysize) 301 #define GETREQUIREDBITARRAYSIZE(nvalstostore) \ 302 ((((unsigned int)(nvalstostore)) % (Zerohalf_bitarraybasetypesize_nbits) == 0) \ 303 ? (((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) \ 304 : ((((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) + 1)) 307 #define GETBITARRAYINDEX(pos) DIV((pos),Zerohalf_bitarraybasetypesize_nbits) 310 #define GETBITARRAYMASK(pos) BITMASK(MOD((pos),Zerohalf_bitarraybasetypesize_nbits)) 313 #define BITARRAYSFOREACH(barray1, barray2, size, op) \ 316 for( idx__ = 0 ; idx__ < (size) ; ++idx__) \ 318 barray2[idx__] op barray1[idx__]; \ 323 #define BITARRAYSXOR(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,^=) 326 #define BITARRAYSAREEQUAL(barray1, barray2, size) \ 327 (memcmp((void*)(barray1), (void*)(barray2), (size_t)((size) * (Zerohalf_bitarraybasetypesize))) == 0) 331 #define BITCLEAR(var, pos) (var) &= ~BITMASK(pos) 334 #define BITFLIP(var, pos) (var) ^= BITMASK(pos) 337 #define BITARRAYBITCLEAR(barray, pos) BITCLEAR(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \ 338 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 341 #define BITARRAYBITFLIP(barray, pos) BITFLIP(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \ 342 MOD(pos,Zerohalf_bitarraybasetypesize_nbits)) 345 #define BITARRAYSAND(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,&=) 348 #define BITARRAYSOR(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,|=) 351 #define BITARRAYSNOT(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,= ~) 388 char* subscipsettings;
389 char subscipobjective;
414 int* nzerohalfcutsalgo;
419 struct Zerohalf_SubLPData
433 typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA;
437 struct Zerohalf_LPData
447 ZEROHALF_SUBLPDATA** subproblems;
454 int* subproblemsindexofrow;
456 int* rrowsindexofleftrow;
457 int* rrowsindexofrightrow;
460 int* subproblemsindexofcol;
462 int* rcolsindexofcol;
499 struct Zerohalf_AuxIPData
519 typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA;
523 struct Zerohalf_Mod2Data
525 ZEROHALF_SUBLPDATA* relatedsubproblem;
537 int rowsbitarraysize;
538 int rowaggregationsbitarraysize;
555 struct Zerohalf_CutData
557 ZEROHALF_SUBLPDATA* relatedsubproblem;
586 struct Zerohalf_AuxGraph_Node;
589 struct Zerohalf_AuxGraph_Node
601 struct Zerohalf_AuxGraph
607 typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH;
619 ZEROHALF_SUBLPDATA** subproblem
622 assert(scip !=
NULL);
623 assert(subproblem !=
NULL);
627 (*subproblem)->rrowsrhs =
NULL;
628 (*subproblem)->rrowsslack =
NULL;
629 (*subproblem)->nrrows = 0;
630 (*subproblem)->rrowssize = 0;
632 (*subproblem)->rcols =
NULL;
633 (*subproblem)->rcolslbslack =
NULL;
634 (*subproblem)->rcolsubslack =
NULL;
635 (*subproblem)->nrcols = 0;
636 (*subproblem)->rcolssize = 0;
646 ZEROHALF_SUBLPDATA** subproblem
649 assert(scip !=
NULL);
650 assert(subproblem !=
NULL);
651 assert(*subproblem !=
NULL);
672 assert(scip !=
NULL);
673 assert(lpdata !=
NULL);
677 (*lpdata)->rows =
NULL;
678 (*lpdata)->cols =
NULL;
680 (*lpdata)->subproblems =
NULL;
681 (*lpdata)->nsubproblems = 0;
683 (*lpdata)->intscalarsleftrow =
NULL;
684 (*lpdata)->intscalarsrightrow =
NULL;
686 (*lpdata)->subproblemsindexofrow =
NULL;
687 (*lpdata)->rrowsindexofleftrow =
NULL;
688 (*lpdata)->rrowsindexofrightrow =
NULL;
690 (*lpdata)->subproblemsindexofcol =
NULL;
691 (*lpdata)->rcolsindexofcol =
NULL;
693 (*lpdata)->bestlbidxofcol =
NULL;
694 (*lpdata)->bestubidxofcol =
NULL;
709 assert(scip !=
NULL);
710 assert(lpdata !=
NULL);
714 assert(((*lpdata)->nsubproblems == 0 && (*lpdata)->subproblems ==
NULL)
715 || ((*lpdata)->nsubproblems > 0 && (*lpdata)->subproblems !=
NULL));
717 if( (*lpdata)->subproblems !=
NULL )
719 for( sp = 0; sp < (*lpdata)->nsubproblems; ++sp )
721 if( (*lpdata)->subproblems[sp] !=
NULL )
749 assert(scip !=
NULL);
750 assert(mod2data !=
NULL);
754 (*mod2data)->relatedsubproblem =
NULL;
756 (*mod2data)->rows =
NULL;
757 (*mod2data)->rowaggregations =
NULL;
758 (*mod2data)->rhs =
NULL;
760 (*mod2data)->slacks =
NULL;
761 (*mod2data)->fracsol =
NULL;
763 (*mod2data)->nrows = 0;
764 (*mod2data)->nrcols = 0;
766 (*mod2data)->rowstatistics =
NULL;
767 (*mod2data)->colstatistics =
NULL;
769 (*mod2data)->rowsind =
NULL;
770 (*mod2data)->colsind =
NULL;
785 assert(scip !=
NULL);
786 assert(mod2data !=
NULL);
789 if( (*mod2data)->rows !=
NULL )
791 for( i = 0 ; i < (*mod2data)->nrows ; ++i)
793 if( (*mod2data)->rows[i] !=
NULL )
801 if( (*mod2data)->rowaggregations !=
NULL )
803 for( i = 0 ; i < (*mod2data)->nrows ; ++i)
805 if( (*mod2data)->rowaggregations[i] !=
NULL )
830 ZEROHALF_AUXIPDATA** auxipdata
833 assert(scip !=
NULL);
834 assert(auxipdata !=
NULL);
838 (*auxipdata)->subscip =
NULL;
840 (*auxipdata)->v =
NULL;
841 (*auxipdata)->y =
NULL;
842 (*auxipdata)->r =
NULL;
843 (*auxipdata)->q =
NULL;
845 (*auxipdata)->feasipcons =
NULL;
846 (*auxipdata)->oddrhscons =
NULL;
847 (*auxipdata)->columnsumcons =
NULL;
857 ZEROHALF_AUXIPDATA** auxipdata
860 assert(scip !=
NULL);
861 assert(auxipdata !=
NULL);
862 assert(*auxipdata !=
NULL);
864 if( (*auxipdata)->subscip !=
NULL )
885 ZEROHALF_SUBLPDATA* relatedsubproblem,
892 assert(scip !=
NULL);
893 assert(cutdata !=
NULL);
894 assert(nrrowsincut >= 0);
895 assert(nrowsincut >= 0);
899 (*cutdata)->relatedsubproblem = relatedsubproblem;
900 (*cutdata)->relatedmod2data = relatedmod2data;
902 (*cutdata)->cut =
NULL;
904 (*cutdata)->success =
FALSE;
905 (*cutdata)->isfeasviolated =
FALSE;
906 (*cutdata)->islocal =
TRUE;
908 (*cutdata)->activity = 0.0;
909 (*cutdata)->rhs = 0.0;
910 (*cutdata)->norm = 0.0;
911 (*cutdata)->efficacy = 0.0;
912 (*cutdata)->violation = 0.0;
913 (*cutdata)->cutrank = 0;
914 (*cutdata)->nnonz = 0;
916 (*cutdata)->nrrowsincut = nrrowsincut;
917 (*cutdata)->nrowsincut = nrowsincut;
918 (*cutdata)->separatedby = separatedby;
919 (*cutdata)->addedtolp =
FALSE;
932 assert(scip !=
NULL);
933 assert(cutdata !=
NULL);
934 assert(*cutdata !=
NULL);
953 assert(scip !=
NULL);
954 assert(node !=
NULL);
958 (*node)->neighbors =
NULL;
959 (*node)->edgeweights =
NULL;
960 (*node)->relatedrows =
NULL;
961 (*node)->nneighbors = 0;
963 (*node)->distance = -1.0;
964 (*node)->previous =
NULL;
974 ZEROHALF_AUXGRAPH* graph,
978 int maxnumberofneighbors;
980 assert(scip !=
NULL);
983 maxnumberofneighbors = 2 * graph->nnodes - 2;
1000 ZEROHALF_AUXGRAPH** auxgraph
1003 assert(scip !=
NULL);
1004 assert(auxgraph !=
NULL);
1008 (*auxgraph)->nodes =
NULL;
1009 (*auxgraph)->nodecopies =
NULL;
1011 (*auxgraph)->nnodes = 0;
1021 ZEROHALF_AUXGRAPH** auxgraph
1026 assert(scip !=
NULL);
1027 assert(auxgraph !=
NULL);
1029 if( (*auxgraph)->nodes !=
NULL )
1031 assert((*auxgraph)->nnodes > 0);
1032 for( n = 0; n < (*auxgraph)->nnodes; ++n )
1034 if( (*auxgraph)->nodes[n] !=
NULL )
1042 if( (*auxgraph)->nodecopies !=
NULL )
1044 assert((*auxgraph)->nnodes > 0);
1045 for( n = 0; n < (*auxgraph)->nnodes; ++n )
1047 if( (*auxgraph)->nodecopies[n] !=
NULL )
1068 char* getconstantname(
1085 #ifdef WITHDECOMPOSE 1086 case ROW_IN_SUBPROB_WITHOUT_ODD_RHS:
1119 #ifdef WITHDECOMPOSE 1120 case COLUMN_IN_SUBPROB_WITHOUT_ODD_RHS:
1133 #ifdef ZEROHALF__PRINT_STATISTICS 1144 int nirrelevantrows;
1147 int nirrelevantcols;
1150 int nnonexistingrows;
1152 assert(lpdata !=
NULL);
1155 nirrelevantrows = 0;
1156 nnonexistingrows = 0;
1158 nirrelevantcols = 0;
1161 for( i = 0 ; i < lpdata->nrows ; ++i)
1163 if( lpdata->rrowsindexofleftrow[i] >= 0 )
1167 if( lpdata->rrowsindexofleftrow[i] < -199 )
1175 if( lpdata->rrowsindexofrightrow[i] >= 0 )
1179 if( lpdata->rrowsindexofrightrow[i] < -199 )
1191 for( i = 0 ; i < lpdata->ncols ; ++i)
1193 if( lpdata->rcolsindexofcol[i] >= 0 )
1197 if( lpdata->rcolsindexofcol[i] == -1 )
1201 if( lpdata->rcolsindexofcol[i] > -200 || lpdata->rcolsindexofcol[i] < -299 )
1209 nrows = nrelevantrows + nirrelevantrows - nnonexistingrows;
1210 ncols = nrelevantcols + nirrelevantcols;
1212 ZEROHALFstatisticsMessage(
"\n");
1213 ZEROHALFstatisticsMessage(
" | ----- lp data ----- | --- (reductions) -- | --- problem data -- | -lpdata- | -(red.)- | -probd.- | --------\n");
1214 ZEROHALFstatisticsMessage(
" | nrows | ncols | ndelrows | ndelcols | nrrows | nrcols | nvarbnds | ndlvbnds | nvarbnds | \n");
1215 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d |\n",
1216 "READING LPDATA", nrows, ncols, nirrelevantrows - nnonexistingrows, nirrelevantcols, nrelevantrows, nrelevantcols,
1217 lpdata->nvarbounds, lpdata->ndelvarbounds, lpdata->nvarbounds - lpdata->ndelvarbounds);
1227 void debugPrintSubLpData(
1230 ZEROHALF_SUBLPDATA* sublpdata
1236 assert(scip !=
NULL);
1237 assert(lpdata !=
NULL);
1238 assert(sublpdata !=
NULL);
1241 SCIPdebugMsg(scip,
" rrows: (nrrows=%d)\n", sublpdata->nrrows);
1243 for( i = 0 ; i < sublpdata->nrrows ; ++i)
1245 SCIPdebugMsg(scip,
" %6d: rrows: %6d rhs: %6g slack: %6g name: %s\n",
1246 i, sublpdata->rrows[i], sublpdata->rrowsrhs[i], sublpdata->rrowsslack[i],
1249 SCIPdebugMsg(scip,
"\n rcols: (nrcols=%d)\n", sublpdata->nrcols);
1250 for( j = 0 ; j < sublpdata->nrcols ; ++j)
1252 SCIPdebugMsg(scip,
" %6d: rcols: %6d lbslack: %6g ubslack: %6g\n",
1253 i, sublpdata->rcols[i], sublpdata->rcolslbslack[i], sublpdata->rcolsubslack[i]);
1262 void debugPrintMod2Data(
1273 assert(scip !=
NULL);
1274 assert(lpdata !=
NULL);
1275 assert(mod2data !=
NULL);
1279 SCIPdebugMsg(scip,
" nrows = %d, nvarbounds = %d, nrcols = %d, nrowsind = %d, ncolsind = %d\n",
1280 mod2data->nrows, mod2data->nvarbounds, mod2data->relatedsubproblem->nrcols,
1281 mod2data->nrowsind, mod2data->ncolsind);
1282 SCIPdebugMsg(scip,
" rowsbitarraysize = %d, rowaggregationsbitarraysize = %d\n",
1283 mod2data->rowsbitarraysize, mod2data->rowaggregationsbitarraysize);
1287 for( j = 0 ; j < mod2data->relatedsubproblem->nrcols ; ++j )
1289 for( k = 0; k < mod2data->ncolsind; ++k )
1291 if( mod2data->colsind[k] == j )
1293 SCIPdebugMsg(scip,
" rcols[%6d]: fracsol: %6g colsind: %6d name: %s\n", j, mod2data->fracsol[j],
1294 k < mod2data->ncolsind ? k : -1,
1299 SCIPdebugMsg(scip,
"\n (A mod 2, b mod 2, [#nonz] (slacks), R, name(rrows), left(-)/right(+):\n");
1300 if( mod2data->nrowsind == 0 )
1304 for( i = 0 ; i < mod2data->nrowsind ; ++i )
1308 for( j = 0 ; j < mod2data->ncolsind; ++j )
1309 if(
BITARRAYBITISSET(mod2data->rows[mod2data->rowsind[i]], mod2data->colsind[j]) )
1318 if( mod2data->rhs[mod2data->rowsind[i]] )
1329 if( printaggregations )
1331 for( j = 0 ; j < mod2data->relatedsubproblem->nrrows; ++j )
1342 if( mod2data->rowsind[i] < mod2data->nrows - mod2data->nvarbounds )
1345 if( lpdata->rrowsindexofleftrow[mod2data->relatedsubproblem->rrows[mod2data->rowsind[i]]] == mod2data->rowsind[i] )
1376 assert(scip !=
NULL);
1377 assert(lpdata !=
NULL);
1380 for( i = 0 ; i < lpdata->nrows ; ++i)
1382 SCIPdebugMsg(scip,
"\nrow %d (left): %s[%d,%d] %s:\n", i,
1383 (lpdata->subproblemsindexofrow[i] ==
IRRELEVANT)
1384 || (lpdata->rrowsindexofleftrow[i] < 0) ?
"IRRELEVANT" :
"RELEVANT",
1385 lpdata->subproblemsindexofrow[i], lpdata->rrowsindexofleftrow[i],
1386 lpdata->rrowsindexofleftrow[i] < 0 ? getconstantname(temp, lpdata->rrowsindexofleftrow[i]) :
"");
1387 SCIPdebugMsg(scip,
"row %d (right): %s[%d,%d] %s:\n", i,
1388 (lpdata->subproblemsindexofrow[i] ==
IRRELEVANT)
1389 || (lpdata->rrowsindexofrightrow[i] < 0) ?
"IRRELEVANT" :
"RELEVANT",
1390 lpdata->subproblemsindexofrow[i], lpdata->rrowsindexofrightrow[i],
1391 lpdata->rrowsindexofrightrow[i] < 0 ? getconstantname(temp, lpdata->rrowsindexofrightrow[i]) :
"");
1396 for( j = 0 ; j < lpdata->ncols ; ++j)
1399 || (lpdata->rcolsindexofcol[j] < 0) ?
"IRRELEVANT" :
"RELEVANT",
1400 lpdata->subproblemsindexofcol[j], lpdata->rcolsindexofcol[j],
1401 lpdata->rcolsindexofcol[j] < 0 ? getconstantname(temp, lpdata->rcolsindexofcol[j]) :
"");
1423 if( scores[ind1] < scores[ind2] )
1425 else if( scores[ind1] > scores[ind2] )
1440 if( scores[ind1] < scores[ind2] )
1442 else if( scores[ind1] > scores[ind2] )
1468 ZEROHALF_SUBLPDATA* problem;
1470 #ifdef ZEROHALF__PRINT_STATISTICS 1475 assert(scip !=
NULL);
1476 assert(lpdata !=
NULL);
1477 assert(lpdata->cols !=
NULL);
1478 assert(lpdata->ncols > 0);
1479 assert(lpdata->nrows > 0);
1480 assert(lpdata->subproblems ==
NULL);
1481 assert(lpdata->nsubproblems == 0);
1482 assert(lpdata->subproblemsindexofrow ==
NULL);
1483 assert(lpdata->rrowsindexofleftrow ==
NULL);
1484 assert(lpdata->rrowsindexofrightrow ==
NULL);
1485 assert(lpdata->subproblemsindexofcol ==
NULL);
1486 assert(lpdata->rcolsindexofcol ==
NULL);
1487 assert(lpdata->bestlbidxofcol ==
NULL);
1488 assert(lpdata->bestubidxofcol ==
NULL);
1503 problem->rcolssize = lpdata->ncols;
1509 lpdata->nsubproblems = 1;
1510 lpdata->subproblems[0] = problem;
1511 lpdata->nvarbounds = 0;
1512 lpdata->ndelvarbounds = 0;
1515 for( j = 0 ; j < lpdata->ncols ; ++j)
1518 lpdata->bestlbidxofcol[j] = -2;
1519 lpdata->bestubidxofcol[j] = -2;
1521 col = lpdata->cols[j];
1535 lbslack = primsol - lb;
1536 ubslack = ub - primsol;
1545 #ifdef ZEROHALF__PRINT_STATISTICS 1551 lpdata->nvarbounds += tempnvarbnds;
1565 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1572 #ifdef ZEROHALF__PRINT_STATISTICS 1573 lpdata->ndelvarbounds += tempnvarbnds;
1575 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1576 if(
ISODD(scip, lb) )
1585 #ifdef ZEROHALF__PRINT_STATISTICS 1586 lpdata->ndelvarbounds += tempnvarbnds;
1588 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1589 if(
ISODD(scip, ub) )
1597 problem->rcols[problem->nrcols] = j;
1598 problem->rcolslbslack[problem->nrcols] = lbslack;
1599 problem->rcolsubslack[problem->nrcols] = ubslack;
1600 lpdata->subproblemsindexofcol[j] = 0;
1601 lpdata->rcolsindexofcol[j] = problem->nrcols;
1608 #ifdef ZEROHALF__PRINT_STATISTICS 1609 lpdata->ndelvarbounds += tempnvarbnds;
1611 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1618 lpdata->subproblemsindexofcol[j] =
IRRELEVANT;
1651 assert(lpdata !=
NULL);
1652 assert(bestlbsol !=
NULL);
1653 assert(bestlbtype !=
NULL);
1654 assert(bestzvlb !=
NULL);
1655 assert(bestbvlb !=
NULL);
1656 assert(bestdvlb !=
NULL);
1662 *bestlbtype = lpdata->bestlbidxofcol[collppos];
1667 if( *bestlbtype == -1 )
1677 assert(zvlb !=
NULL || nvlb == 0);
1678 assert(bvlb !=
NULL || nvlb == 0);
1679 assert(dvlb !=
NULL || nvlb == 0);
1682 if( *bestlbtype == -2 )
1688 for( j = 0; j < nvlb; j++ )
1690 assert(zvlb !=
NULL);
1691 assert(bvlb !=
NULL);
1692 assert(dvlb !=
NULL);
1702 if( vlbsol > *bestlbsol )
1704 *bestlbsol = vlbsol;
1712 if( *bestlbtype == -2 )
1716 lpdata->bestlbidxofcol[collppos] = *bestlbtype;
1718 assert(lpdata->bestlbidxofcol[collppos] > -2);
1720 if( *bestlbtype >= 0 )
1723 assert(*bestlbtype < nvlb);
1724 assert(zvlb !=
NULL);
1725 assert(bvlb !=
NULL);
1726 assert(dvlb !=
NULL);
1727 *bestzvlb = zvlb[*bestlbtype];
1728 *bestbvlb = bvlb[*bestlbtype];
1729 *bestdvlb = dvlb[*bestlbtype];
1758 assert(lpdata !=
NULL);
1759 assert(bestubsol !=
NULL);
1760 assert(bestubtype !=
NULL);
1761 assert(bestzvub !=
NULL);
1762 assert(bestbvub !=
NULL);
1763 assert(bestdvub !=
NULL);
1768 *bestubtype = lpdata->bestubidxofcol[collppos];
1773 if( *bestubtype == -1 )
1783 assert(zvub !=
NULL || nvub == 0);
1784 assert(bvub !=
NULL || nvub == 0);
1785 assert(dvub !=
NULL || nvub == 0);
1788 if( *bestubtype == -2 )
1793 for( j = 0; j < nvub; j++ )
1795 assert(zvub !=
NULL);
1796 assert(bvub !=
NULL);
1797 assert(dvub !=
NULL);
1807 if( vubsol < *bestubsol )
1809 *bestubsol = vubsol;
1816 if( *bestubtype == -2 )
1820 lpdata->bestubidxofcol[collppos] = *bestubtype;
1822 assert(lpdata->bestubidxofcol[collppos] > -2);
1824 if( *bestubtype >= 0 )
1827 assert(*bestubtype < nvub);
1828 assert(zvub !=
NULL);
1829 assert(bvub !=
NULL);
1830 assert(dvub !=
NULL);
1831 *bestzvub = zvub[*bestubtype];
1832 *bestbvub = bvub[*bestubtype];
1833 *bestdvub = dvub[*bestubtype];
1868 int nnonzcurrentrow;
1879 ZEROHALF_SUBLPDATA* problem;
1884 assert(scip !=
NULL);
1885 assert(sepadata !=
NULL);
1886 assert(lpdata !=
NULL);
1887 assert(lpdata->rows !=
NULL);
1888 assert(lpdata->nrows > 0);
1889 assert(lpdata->subproblemsindexofcol !=
NULL);
1890 assert(lpdata->rcolsindexofcol !=
NULL);
1891 assert(lpdata->subproblems !=
NULL);
1892 assert(lpdata->nsubproblems > 0);
1894 assert(lpdata->subproblemsindexofrow ==
NULL);
1895 assert(lpdata->rrowsindexofleftrow ==
NULL);
1896 assert(lpdata->rrowsindexofrightrow ==
NULL);
1899 problem = lpdata->subproblems[k];
1902 assert(k <= lpdata->nsubproblems);
1903 assert(problem !=
NULL);
1904 assert(problem->rcols !=
NULL);
1905 assert(problem->nrcols > 0);
1906 assert(problem->rcolslbslack !=
NULL);
1907 assert(problem->rcolsubslack !=
NULL);
1909 assert(problem->rrows ==
NULL);
1910 assert(problem->rrowsrhs ==
NULL);
1911 assert(problem->rrowsslack ==
NULL);
1921 problem->rrowssize = 2 * lpdata->nrows;
1935 maxslack = sepadata->maxslack;
1936 problem->nrrows = 0;
1937 for( r = 0 ; r < lpdata->nrows ; ++r)
1939 row = lpdata->rows[r];
1941 if( sepadata->ignoreprevzhcuts )
1946 if( strlen(rowname) > 8 )
1948 if(rowname[0] ==
'z' 1949 && rowname[1] ==
'e' 1950 && rowname[2] ==
'r' 1951 && rowname[3] ==
'o' 1952 && rowname[4] ==
'h' 1953 && rowname[5] ==
'a' 1954 && rowname[6] ==
'l' 1955 && rowname[7] ==
'f' )
1957 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
1966 if( sepadata->onlyorigrows )
1973 assert(sepadata->origrows !=
NULL);
1974 assert(sepadata->norigrows > 0);
1978 right = sepadata->norigrows - 1;
1980 while( left <= right && center > -1 )
1982 center = left + ((right - left) / 2);
1983 if( sepadata->origrows[center] == rowindex )
1985 if( sepadata->origrows[center] > rowindex )
1992 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2009 for( c = 0; c < nnonzcurrentrow; ++c)
2012 assert(0 <= collppos && collppos < lpdata->ncols);
2035 &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2036 assert( bestbndtype > -2 && lpdata->bestlbidxofcol[collppos] == bestbndtype);
2038 if( bestbndtype > -1 )
2043 assert(0 <= zlppos && zlppos < lpdata->ncols);
2045 if( valscurrentrow[c] > 0 )
2046 densecoeffscurrentrightrow[zlppos] += valscurrentrow[c] * bestbvbnd;
2048 densecoeffscurrentleftrow[zlppos] -= valscurrentrow[c] * bestbvbnd;
2052 &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2053 assert(bestbndtype > -2 && lpdata->bestubidxofcol[collppos] == bestbndtype);
2055 if( bestbndtype > -1 )
2060 assert(0 <= zlppos && zlppos < lpdata->ncols);
2062 if( valscurrentrow[c] > 0 )
2063 densecoeffscurrentleftrow[zlppos] -= valscurrentrow[c] * bestbvbnd;
2065 densecoeffscurrentrightrow[zlppos] += valscurrentrow[c] * bestbvbnd;
2070 densecoeffscurrentleftrow[collppos] -= valscurrentrow[c];
2071 densecoeffscurrentrightrow[collppos] += valscurrentrow[c];
2078 intscalarleftrow = 1.0;
2079 intscalarrightrow = 1.0;
2101 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2106 lpdata->intscalarsleftrow[r] = intscalarleftrow;
2107 lpdata->intscalarsrightrow[r] = intscalarrightrow;
2121 lhs = (lhs - cst) * intscalarleftrow;
2122 rhs = (rhs - cst) * intscalarrightrow;
2127 lhsslack = lhsslack * intscalarleftrow;
2128 rhsslack = rhsslack * intscalarrightrow;
2131 if( (!lhsisinfinity &&
SCIPisLE(scip, lhsslack, maxslack))
2132 || (!rhsisinfinity &&
SCIPisLE(scip, rhsslack, maxslack)) )
2138 lhsiseven =
ISEVEN(scip, lhs);
2139 rhsiseven =
ISEVEN(scip, rhs);
2141 rowisrelevant =
FALSE;
2142 for( c = 0 ; c < nnonzcurrentrow ; ++c )
2152 lhsiseven = !lhsiseven;
2153 rhsiseven = !rhsiseven;
2159 if( !rhsisinfinity )
2161 if( valscurrentrow[c] * intscalarrightrow > 0 )
2163 findClosestLb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2164 assert(bestbndtype > -2 && lpdata->bestlbidxofcol[collppos] == bestbndtype);
2168 assert(valscurrentrow[c] * intscalarrightrow < 0);
2169 findClosestUb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2170 assert(bestbndtype > -2 && lpdata->bestubidxofcol[collppos] == bestbndtype);
2172 assert(bestbndtype == -1 || bestzvbnd !=
NULL);
2175 rhsisinfinity =
TRUE;
2179 if ( bestbndtype == -1 )
2180 rhs -= intscalarrightrow *
REALABS(valscurrentrow[c]) * bestbndsol;
2182 rhs -= intscalarrightrow *
REALABS(valscurrentrow[c]) * bestdvbnd;
2183 rhsslack += intscalarrightrow *
REALABS(valscurrentrow[c])
2185 assert(
SCIPisGE(scip, rhsslack, 0.0));
2190 if( !lhsisinfinity )
2192 if( valscurrentrow[c] * intscalarleftrow < 0 )
2194 findClosestLb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2195 assert(bestbndtype > -2 && lpdata->bestlbidxofcol[collppos] == bestbndtype);
2199 assert(valscurrentrow[c] * intscalarleftrow > 0);
2200 findClosestUb(scip, lpdata, colscurrentrow[c], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2201 assert(bestbndtype > -2 && lpdata->bestubidxofcol[collppos] == bestbndtype);
2203 assert(bestbndtype == -1 || bestzvbnd !=
NULL);
2206 lhsisinfinity =
TRUE;
2210 if( bestbndtype == -1 )
2211 lhs -= intscalarleftrow *
REALABS(valscurrentrow[c]) * bestbndsol;
2213 lhs -= intscalarleftrow *
REALABS(valscurrentrow[c]) * bestdvbnd;
2214 lhsslack += intscalarleftrow *
REALABS(valscurrentrow[c])
2216 assert(
SCIPisGE(scip, lhsslack, 0.0));
2222 if( lhsisinfinity && rhsisinfinity )
2224 rowisrelevant =
FALSE;
2228 rowisrelevant =
TRUE;
2232 if( lpdata->subproblemsindexofcol[collppos] == k )
2233 rowisrelevant =
TRUE;
2236 if( c == nnonzcurrentrow - 1 && (!lhsiseven || !rhsiseven) )
2237 rowisrelevant =
TRUE;
2240 assert(
SCIPisGE(scip, lhsslack, 0.0));
2241 assert(
SCIPisGE(scip, rhsslack, 0.0));
2248 problem->rrows[problem->nrrows] = r;
2250 lhsslackislessequalmaxslack =
SCIPisLE(scip, lhsslack, maxslack);
2251 rhsslackislessequalmaxslack =
SCIPisLE(scip, rhsslack, maxslack);
2257 if( !lhsisinfinity && lhsslackislessequalmaxslack )
2260 lpdata->subproblemsindexofrow[r] = k;
2261 lpdata->rrowsindexofleftrow[r] = problem->nrrows;
2263 problem->rrows[problem->nrrows] = r;
2267 problem->rrowsrhs[problem->nrrows] = lhs;
2268 problem->rrowsslack[problem->nrrows] = lhsslack;
2278 if( !rhsisinfinity && rhsslackislessequalmaxslack )
2281 lpdata->subproblemsindexofrow[r] = k;
2282 lpdata->rrowsindexofrightrow[r] = problem->nrrows;
2284 problem->rrows[problem->nrrows] = r;
2285 problem->rrowsrhs[problem->nrrows] = rhs;
2286 problem->rrowsslack[problem->nrrows] = rhsslack;
2294 if( lpdata->rrowsindexofleftrow[r] > -1 || lpdata->rrowsindexofrightrow[r] > -1 )
2300 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2307 lpdata->subproblemsindexofrow[r] =
IRRELEVANT;
2332 assert(mod2data !=
NULL);
2334 if( mod2data->nrowsind == 0 )
2337 if( mod2data->ncolsind <= 2 )
2340 for( r = 0; r < mod2data->nrowsind ; ++r )
2343 for( c = 0; c < mod2data->ncolsind ; ++c )
2345 if(
BITARRAYBITISSET(mod2data->rows[mod2data->rowsind[r]], mod2data->colsind[c]) )
2359 #ifdef ZEROHALF__PRINT_STATISTICS 2362 SCIP_Bool hasMatrixMax2EntriesPerColumn(
2370 assert(mod2data !=
NULL);
2372 if( mod2data->ncolsind == 0 )
2375 if( mod2data->nrowsind <= 2 )
2378 for( c = 0; c < mod2data->ncolsind ; ++c )
2381 for( r = 0; r < mod2data->nrowsind ; ++r )
2383 if(
BITARRAYBITISSET(mod2data->rows[mod2data->rowsind[r]], mod2data->colsind[c]) )
2404 int subproblemindex,
2408 ZEROHALF_SUBLPDATA* problem;
2415 int* varboundstoadd;
2416 int nnonzcurrentrow;
2421 #ifdef ZEROHALF__PRINT_STATISTICS 2422 int nirrelevantvarbounds;
2430 assert(scip !=
NULL);
2431 assert(sepadata !=
NULL);
2432 assert(lpdata !=
NULL);
2433 assert(lpdata->rows !=
NULL);
2434 assert(lpdata->nrows > 0);
2435 assert(lpdata->cols !=
NULL);
2436 assert(lpdata->ncols > 0);
2437 assert(lpdata->subproblems !=
NULL);
2438 assert(lpdata->nsubproblems > 0);
2439 assert(lpdata->subproblemsindexofrow !=
NULL);
2440 assert(lpdata->rrowsindexofleftrow !=
NULL);
2441 assert(lpdata->rrowsindexofrightrow !=
NULL);
2442 assert(lpdata->subproblemsindexofcol !=
NULL);
2443 assert(lpdata->rcolsindexofcol !=
NULL);
2444 assert(0 <= subproblemindex);
2445 assert(subproblemindex <= lpdata->nsubproblems);
2446 problem = lpdata->subproblems[subproblemindex];
2447 assert(problem !=
NULL);
2448 assert(problem->rrows !=
NULL);
2449 assert(problem->nrrows > 0);
2450 assert(problem->rrowsrhs !=
NULL);
2451 assert(problem->rrowsslack !=
NULL);
2452 assert(problem->rcols !=
NULL);
2453 assert(problem->nrcols > 0);
2454 assert(problem->rcolslbslack !=
NULL);
2455 assert(problem->rcolsubslack !=
NULL);
2456 assert(mod2data !=
NULL);
2461 maxslack = sepadata->maxslack;
2463 #ifdef ZEROHALF__PRINT_STATISTICS 2464 nirrelevantvarbounds = 0;
2466 mod2data->nvarbounds = 0;
2467 for( c = 0 ; c < problem->nrcols ; c++ )
2472 lbslackisok =
SCIPisLE(scip, problem->rcolslbslack[c], maxslack);
2473 ubslackisok =
SCIPisLE(scip, problem->rcolsubslack[c], maxslack);
2475 if( lbslackisok && ubslackisok )
2485 varboundstoadd[mod2data->nvarbounds] = (-1) * (c + 1);
2486 mod2data->nvarbounds++;
2487 varboundstoadd[mod2data->nvarbounds] = c + 1;
2488 mod2data->nvarbounds++;
2492 if(
SCIPisLE(scip, problem->rcolslbslack[c], problem->rcolsubslack[c]) )
2493 varboundstoadd[mod2data->nvarbounds] = (-1) * (c + 1);
2495 varboundstoadd[mod2data->nvarbounds] = c + 1;
2496 mod2data->nvarbounds++;
2497 #ifdef ZEROHALF__PRINT_STATISTICS 2498 nirrelevantvarbounds++;
2506 varboundstoadd[mod2data->nvarbounds] = (-1) * (c + 1);
2507 mod2data->nvarbounds++;
2509 #ifdef ZEROHALF__PRINT_STATISTICS 2511 nirrelevantvarbounds++;
2515 varboundstoadd[mod2data->nvarbounds] = c + 1;
2516 mod2data->nvarbounds++;
2518 #ifdef ZEROHALF__PRINT_STATISTICS 2520 nirrelevantvarbounds++;
2524 mod2data->nrows = problem->nrrows + mod2data->nvarbounds;
2525 mod2data->nrcols = problem->nrcols;
2540 mod2data->relatedsubproblem = problem;
2544 for( c = 0 ; c < problem->nrcols ; ++c)
2546 for( c = 0 ; c < problem->nrcols ; c++)
2547 mod2data->colsind[c] = c;
2548 mod2data->nrowsind = 0;
2549 mod2data->ncolsind = problem->nrcols;
2552 tempcurrentrow =
NULL;
2555 for( i = 0; i < problem->nrrows; ++i )
2557 row = lpdata->rows[problem->rrows[i]];
2561 assert(nnonzcurrentrow > 0);
2562 tempcurrentrow =
NULL;
2567 if( lpdata->rrowsindexofleftrow[problem->rrows[i]] == i )
2571 assert(lpdata->rrowsindexofrightrow[problem->rrows[i]] == i);
2574 intscalar = isrhsrow ? lpdata->intscalarsrightrow[problem->rrows[i]]
2575 : lpdata->intscalarsleftrow[problem->rrows[i]];
2581 for( j = 0 ; j < nnonzcurrentrow; ++j )
2593 if( nonzvalscurrentrow[j] * intscalar > 0.0 )
2594 ispositivecoeff =
TRUE;
2596 ispositivecoeff =
FALSE;
2599 if( isrhsrow == ispositivecoeff )
2600 findClosestLb(scip, lpdata, colscurrentrow[j], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2602 findClosestUb(scip, lpdata, colscurrentrow[j], &bestbndsol, &bestbndtype, &bestzvbnd, &bestbvbnd, &bestdvbnd );
2605 assert(bestbndtype > -2);
2607 assert(bestbndtype == -1);
2610 if( bestbndtype == -1 )
2619 densecoeffscurrentrow[
SCIPcolGetLPPos(colscurrentrow[j])] += (nonzvalscurrentrow[j] * intscalar);
2623 for( j = 0 ; j < lpdata->ncols; ++j )
2627 if(
SCIPisZero(scip, densecoeffscurrentrow[j]) )
2630 if( intscalar == 1.0 && !
SCIPisIntegral(scip, densecoeffscurrentrow[j]) )
2636 assert(sepadata->scalefraccoeffs);
2641 densecoeffscurrentrow[j] =
SCIPfloor(scip, densecoeffscurrentrow[j]);
2643 densecoeffscurrentrow[j] =
SCIPceil(scip, densecoeffscurrentrow[j]);
2645 if(
ISODD(scip, densecoeffscurrentrow[j]) )
2647 rcolsindex = lpdata->rcolsindexofcol[j];
2648 fliplhsrhs =
XOR((
int) fliplhsrhs,
2650 if( rcolsindex >= 0 )
2652 if( tempcurrentrow ==
NULL )
2657 assert(rcolsindex < problem->nrcols);
2672 if(
XOR((
int)
ISODD(scip, problem->rrowsrhs[i]), (
int) fliplhsrhs) )
2675 tempmod2rhs =
FALSE;
2677 if( tempcurrentrow ==
NULL && tempmod2rhs )
2682 assert(tempcurrentrow !=
NULL || !tempmod2rhs);
2685 if( tempcurrentrow !=
NULL )
2687 mod2data->rows[i] = tempcurrentrow;
2688 mod2data->rhs[i] = tempmod2rhs;
2690 assert(mod2data->rowaggregationsbitarraysize > 0);
2692 BITARRAYCLEAR(mod2data->rowaggregations[i], mod2data->rowaggregationsbitarraysize);
2695 mod2data->rowsind[mod2data->nrowsind] = i;
2696 mod2data->nrowsind++;
2698 tempcurrentrow =
NULL;
2703 lpdata->subproblemsindexofrow[problem->rrows[i]] =
IRRELEVANT;
2704 if( lpdata->rrowsindexofleftrow[problem->rrows[i]] >= 0 )
2705 lpdata->rrowsindexofleftrow[problem->rrows[i]] =
ZERO_ROW;
2706 if( lpdata->rrowsindexofrightrow[problem->rrows[i]] >= 0 )
2707 lpdata->rrowsindexofrightrow[problem->rrows[i]] =
ZERO_ROW;
2713 i = problem->nrrows;
2714 for( j = 0 ; j < mod2data->nvarbounds ; ++j)
2718 if( varboundstoadd[j] < 0 )
2719 c = (-1) * varboundstoadd[j] - 1;
2721 c = varboundstoadd[j] - 1;
2723 assert(mod2data->rowsbitarraysize > 0);
2725 BITARRAYCLEAR(mod2data->rows[i], mod2data->rowsbitarraysize);
2730 BITARRAYCLEAR(mod2data->rowaggregations[i], mod2data->rowaggregationsbitarraysize);
2732 if( varboundstoadd[j] < 0 )
2735 mod2data->rhs[i] =
ISODD(scip, bound);
2736 mod2data->slacks[i] = problem->rcolslbslack[c];
2741 mod2data->rhs[i] =
ISODD(scip, bound);
2742 mod2data->slacks[i] = problem->rcolsubslack[c];
2745 mod2data->slacks[i] = 0.0;
2747 mod2data->rowsind[mod2data->nrowsind] = i;
2748 mod2data->nrowsind++;
2756 #ifdef ZEROHALF__PRINT_STATISTICS 2757 ZEROHALFstatisticsMessage(
"\n");
2758 ZEROHALFstatisticsMessage(
" | ------------------------------- subproblem ------------------------------- | ------------------------------\n");
2759 ZEROHALFstatisticsMessage(
" | nrrows | nrcols | nvarbnds | ndlvbnds | max2/row | max2/col | A^T ept | \n");
2760 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8s | %8s | %8s |\n",
2761 "SUBPROBLEMDATA", problem->nrrows, problem->nrcols, mod2data->nvarbounds, nirrelevantvarbounds,
2799 assert(nvars == 0 || cutcoefs !=
NULL);
2800 assert(nvars == 0 || varsolvals !=
NULL);
2801 assert(cutvars !=
NULL);
2802 assert(cutvals !=
NULL);
2803 assert(cutlen !=
NULL);
2804 assert(cutact !=
NULL);
2805 assert(cutnorm !=
NULL);
2814 for( v = 0; v < nvars; ++v)
2819 act += val * varsolvals[v];
2820 cutsqrnorm += SQR(val);
2821 cutvars[len] = vars[v];
2826 norm = SQRT(cutsqrnorm);
2829 for( v = 0; v < nvars; ++v)
2834 act += val * varsolvals[v];
2836 norm =
MAX(norm, absval);
2837 cutvars[len] = vars[v];
2844 for( v = 0; v < nvars; ++v)
2849 act += val * varsolvals[v];
2851 cutvars[len] = vars[v];
2858 for( v = 0; v < nvars; ++v)
2863 act += val * varsolvals[v];
2865 cutvars[len] = vars[v];
2895 assert(scip !=
NULL);
2897 assert(cutdata !=
NULL);
2898 assert(result !=
NULL);
2901 if( !cutdata->isfeasviolated || !cutdata->success )
2912 if( !sepadata->forcecutstolp && !sepadata->forcecutstosepastore
2919 if( !sepadata->usezhcutpool )
2928 if( !cutdata->islocal )
2934 cutdata->addedtolp =
TRUE;
2959 assert(mod2data !=
NULL);
2960 assert(mod2data->relatedsubproblem !=
NULL);
2961 assert(mod2data->nrowsind > 0);
2963 assert(r < mod2data->nrowsind);
2965 mod2data->rowstatistics[mod2data->rowsind[r]] = flag;
2982 assert(mod2data !=
NULL);
2983 assert(mod2data->relatedsubproblem !=
NULL);
2984 assert(mod2data->ncolsind > 0);
2986 assert(c < mod2data->ncolsind);
2990 mod2data->colstatistics[mod2data->colsind[c]] = flag;
2995 for( i = 0 ; i < mod2data->nrowsind ; ++i)
2996 mod2data->rows[mod2data->rowsind[i]][rowsbind] &= rowsbmask;
3017 ZEROHALF_SUBLPDATA* problem;
3022 assert(scip !=
NULL);
3023 assert(lpdata !=
NULL);
3024 assert(lpdata->nrows > 0);
3025 assert(mod2data !=
NULL);
3026 assert(mod2data->relatedsubproblem !=
NULL);
3027 assert(mod2data->nrowsind > 0);
3028 assert(rrowsincut !=
NULL);
3029 assert(weights !=
NULL);
3030 assert(*weights ==
NULL);
3031 assert(nrowsincut !=
NULL);
3038 problem = mod2data->relatedsubproblem;
3043 for( i = 0 ; i < problem->nrrows ; ++i)
3045 lppos = problem->rrows[i];
3046 assert(0 <= lppos && lppos <= lpdata->nrows);
3049 assert(lpdata->rrowsindexofleftrow[lppos] == i || lpdata->rrowsindexofrightrow[lppos] == i);
3051 SCIPdebugMsg(scip,
" %1s0.5 (int scaling: %16.4f / %16.4f) row[%d] %s\n",
3052 lpdata->rrowsindexofleftrow[lppos] == i ?
"-" :
"+",
3053 lpdata->intscalarsleftrow[lppos], lpdata->intscalarsrightrow[lppos],
3056 if( lpdata->rrowsindexofleftrow[lppos] == i )
3057 (*weights)[lppos] = lpdata->intscalarsleftrow[lppos] * (-0.5);
3059 (*weights)[lppos] = lpdata->intscalarsrightrow[lppos] * 0.5;
3067 if( nnonz >= 5 * sepadata->maxnnonz )
3096 assert(scip !=
NULL);
3097 assert(lpdata !=
NULL);
3098 assert(lpdata->nvars > 0);
3099 assert(weights !=
NULL);
3100 assert(varsolvals !=
NULL);
3101 assert(cutdata !=
NULL);
3102 assert(cutdata->relatedsubproblem !=
NULL);
3103 assert(cutoff !=
NULL);
3114 cutdata->success =
FALSE;
3115 if( sepadata->maxtestdelta == 0 )
3120 weights, -1.0,
NULL, -1, -1,
NULL, 1.0,
NULL,
NULL, cutcoefs, &(cutdata->rhs), &(cutdata->activity),
3121 &(cutdata->success), &(cutdata->islocal), &(cutdata->cutrank)) );
3123 if( sepadata->trynegscaling )
3127 weights, -1.0,
NULL, -1, -1,
NULL, -1.0,
NULL,
NULL, cutcoefs, &(cutdata->rhs), &(cutdata->activity),
3128 &(cutdata->success), &(cutdata->islocal), &(cutdata->cutrank)) );
3139 if( *varsolvals ==
NULL )
3152 for(i = lpdata->nvars - 1; i >= 0; --i )
3157 assert(*varsolvals !=
NULL);
3161 -1.0,
NULL, -1, -1,
BOUNDSWITCH,
USEVBDS,
ALLOWLOCAL,
FIXINTEGRALRHS, sepadata->maxnnonz,
MAXWEIGHTRANGE,
3162 MINFRAC,
MAXFRAC, sepadata->trynegscaling,
TRUE,
"zerohalf", cutoff, &ncuts, &bestdelta, &bestdeltavalid) );
3166 if( !(*cutoff) && bestdeltavalid )
3170 weights, -1.0,
NULL, -1, -1,
NULL, bestdelta,
NULL,
NULL, cutcoefs, &(cutdata->rhs), &(cutdata->activity),
3171 &(cutdata->success), &(cutdata->islocal), &(cutdata->cutrank)) );
3176 cutdata->violation = cutdata->activity - cutdata->rhs;
3179 if( !(*cutoff) && cutdata->success )
3181 cutdata->isfeasviolated =
SCIPisFeasGT(scip, cutdata->activity, cutdata->rhs);
3182 SCIPdebugMsg(scip,
"Cut is %sfeasviolated: (act: %e, rhs: %e, viol: %e)\n",
3183 cutdata->isfeasviolated ?
"" :
"not ", cutdata->activity, cutdata->rhs, cutdata->violation);
3185 if( cutdata->isfeasviolated )
3187 if( *varsolvals ==
NULL )
3193 assert(*varsolvals !=
NULL);
3201 cutcoefs, *varsolvals, normtype, cutvars, cutvals,
3202 &(cutdata->nnonz), &(cutdata->activity), &(cutdata->norm)));
3207 cutdata->efficacy = (cutdata->activity - cutdata->rhs) / cutdata->norm;
3209 if( sepadata->forcecutstolp || sepadata->forcecutstosepastore
3210 || (
SCIPisEfficacious(scip, cutdata->efficacy) && cutdata->nnonz < sepadata->maxnnonz) )
3215 cutdata->islocal,
FALSE, sepadata->dynamiccuts));
3221 cutdata->success =
FALSE;
3224 cutdata->success =
FALSE;
3231 cutdata->success =
FALSE;
3272 assert(scip !=
NULL);
3273 assert(lpdata !=
NULL);
3274 assert(mod2data !=
NULL);
3275 assert(mod2data->relatedsubproblem !=
NULL);
3276 assert(firstrowsind >= 0);
3277 assert(lastrowsind <= mod2data->nrowsind);
3278 assert(nsepacuts !=
NULL);
3279 assert(nzerohalfcuts !=
NULL);
3280 assert(zerohalfcuts !=
NULL);
3281 assert(*nsepacuts <= *nzerohalfcuts);
3282 assert(varsolvals !=
NULL);
3283 assert(result !=
NULL);
3286 if( mod2data->nrowsind == 0 || lastrowsind - firstrowsind <= 0 )
3296 maxslack = sepadata->maxslack;
3300 for( r = 0 ; r < lastrowsind - firstrowsind && *nsepacuts < maxsepacuts && *nzerohalfcuts < maxcuts; ++r )
3302 if( mod2data->rhs[mod2data->rowsind[firstrowsind + r]] ==
TRUE )
3304 if(
SCIPisLE(scip, mod2data->slacks[mod2data->rowsind[firstrowsind + r]], maxslack ))
3307 zerorow, mod2data->rowsbitarraysize) )
3312 mod2data->rowaggregations[mod2data->rowsind[firstrowsind + r]], &weights, &nrowsincut) );
3313 if( weights ==
NULL )
3315 assert(nrowsincut > 0);
3319 mod2data->relatedsubproblem, mod2data, 1, nrowsincut, cutseparatedby) );
3321 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff) );
3338 removerow[r] =
TRUE;
3346 if( ! cutoff && nrowsremoved > 0 )
3349 for( r = firstrowsind ; r < mod2data->nrowsind && r2 < mod2data->nrowsind; ++r)
3351 if( r < lastrowsind - firstrowsind )
3352 while( r2 < mod2data->nrowsind && removerow[r2] )
3354 if( r < r2 && r2 < mod2data->nrowsind )
3355 mod2data->rowsind[r] = mod2data->rowsind[r2];
3358 mod2data->nrowsind -= nrowsremoved;
3388 int nzerorowsremoved;
3389 int nlargeslackrowsremoved;
3390 int nidenticalrowsremoved;
3394 assert(scip !=
NULL);
3395 assert(lpdata !=
NULL);
3396 assert(mod2data !=
NULL);
3397 assert(mod2data->relatedsubproblem !=
NULL);
3398 assert(firstrowsind >= 0);
3399 assert(lastrowsind <= mod2data->nrowsind);
3403 if( mod2data->nrowsind == 0 || lastrowsind - firstrowsind <= 0 )
3410 if( removezerorows )
3417 if( removezerorows )
3421 maxslack = sepadata->maxslack;
3422 nzerorowsremoved = 0;
3423 nlargeslackrowsremoved = 0;
3424 nidenticalrowsremoved = 0;
3427 for( r1 = 0 ; r1 < lastrowsind - firstrowsind ; ++r1)
3428 if( !rowisprocessed[r1] )
3430 rowisprocessed[r1] =
TRUE;
3432 if( removezerorows && !removerow[r1] )
3433 if( mod2data->rhs[mod2data->rowsind[firstrowsind + r1]] ==
FALSE )
3435 assert(zerorow !=
NULL);
3437 zerorow, mod2data->rowsbitarraysize) )
3440 removerow[r1] =
TRUE;
3444 if( removelargeslackrows && !removerow[r1] )
3445 if(
SCIPisGT(scip, mod2data->slacks[mod2data->rowsind[firstrowsind + r1]], maxslack) )
3448 removerow[r1] =
TRUE;
3449 nlargeslackrowsremoved++;
3452 if( removeidenticalrows && !removerow[r1] )
3453 for( r2 = r1 + 1 ; r2 < lastrowsind - firstrowsind ; ++r2)
3454 if( !rowisprocessed[r2] )
3455 if( mod2data->rhs[mod2data->rowsind[firstrowsind + r1]]
3456 == mod2data->rhs[mod2data->rowsind[firstrowsind + r2]] )
3458 mod2data->rows[mod2data->rowsind[firstrowsind + r2]], mod2data->rowsbitarraysize) )
3460 if(
SCIPisLT(scip, mod2data->slacks[mod2data->rowsind[firstrowsind + r1]],
3461 mod2data->slacks[mod2data->rowsind[firstrowsind + r2]]) )
3464 removerow[r2] =
TRUE;
3465 nidenticalrowsremoved++;
3466 rowisprocessed[r2] =
TRUE;
3471 removerow[r1] =
TRUE;
3472 nidenticalrowsremoved++;
3479 if( nzerorowsremoved + nlargeslackrowsremoved + nidenticalrowsremoved > 0 )
3482 for( r1 = firstrowsind ; r1 < mod2data->nrowsind && r2 < mod2data->nrowsind; ++r1)
3484 if( r1 < lastrowsind - firstrowsind )
3485 while( r2 < mod2data->nrowsind && removerow[r2] )
3487 if( r1 < r2 && r2 < mod2data->nrowsind )
3488 mod2data->rowsind[r1] = mod2data->rowsind[r2];
3491 mod2data->nrowsind -= (nzerorowsremoved + nlargeslackrowsremoved + nidenticalrowsremoved);
3496 if( removezerorows && zerorow !=
NULL )
3522 int maxnnonzentries;
3523 int nzerocolsremoved;
3524 int ncolsingletonsremoved;
3525 int nunprocessedcols;
3526 int nconsideredcols;
3530 int rowofcolsingleton;
3537 assert(scip !=
NULL);
3538 assert(sepadata !=
NULL);
3539 assert(lpdata !=
NULL);
3540 assert(mod2data !=
NULL);
3541 assert(mod2data->relatedsubproblem !=
NULL);
3542 assert(firstcolsind >= 0);
3543 assert(lastcolsind <= mod2data->ncolsind);
3544 assert(removezerocols || removecolsingletons);
3547 nconsideredcols = lastcolsind - firstcolsind;
3550 if( mod2data->ncolsind == 0 || mod2data->nrowsind == 0 || nconsideredcols <= 0 )
3561 maxslack = sepadata->maxslack;
3562 nunprocessedcols = nconsideredcols;
3563 nzerocolsremoved = 0;
3564 ncolsingletonsremoved = 0;
3565 rowofcolsingleton = -1;
3566 if( removecolsingletons )
3567 maxnnonzentries = 1;
3569 maxnnonzentries = 0;
3572 while(nunprocessedcols > 0)
3574 for( c = 0 ; c < nconsideredcols ; ++c )
3575 if( colisprocessed[c] ==
FALSE )
3577 assert(firstcolsind + c < mod2data->ncolsind);
3583 for( r = 0 ; r < mod2data->nrowsind ; ++r)
3584 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
3587 if( nnonzentries > maxnnonzentries )
3589 rowofcolsingleton = r;
3593 if( removezerocols )
3594 if( nnonzentries == 0 )
3597 removecol[c] =
TRUE;
3603 if( removecolsingletons && !removecol[c] )
3604 if( nnonzentries == 1 )
3606 r = rowofcolsingleton;
3607 removecol[c] =
TRUE;
3610 mod2data->slacks[mod2data->rowsind[r]] += mod2data->fracsol[mod2data->colsind[firstcolsind + c]];
3614 if( checkresultingrows &&
SCIPisGT(scip, mod2data->slacks[mod2data->rowsind[r]], maxslack) )
3617 for( j = 0 ; j < nconsideredcols ; ++j)
3618 if( !removecol[j] && colisprocessed[j] )
3620 mod2data->colsind[firstcolsind + j]) )
3622 colisprocessed[j] =
FALSE;
3627 mod2data->nrowsind - r - 1);
3629 mod2data->nrowsind--;
3633 ncolsingletonsremoved++;
3637 colisprocessed[c] =
TRUE;
3640 if( nzerocolsremoved + ncolsingletonsremoved == nconsideredcols || mod2data->nrowsind == 0 )
3645 if( mod2data->nrowsind == 0 )
3647 for( c = firstcolsind ; c < mod2data->ncolsind; ++c)
3650 removecol[c] =
TRUE;
3653 nzerocolsremoved = nconsideredcols - ncolsingletonsremoved;
3654 assert(nzerocolsremoved + ncolsingletonsremoved == nconsideredcols);
3658 if( mod2data->nrowsind == 0 )
3659 mod2data->ncolsind = 0;
3661 if( nzerocolsremoved + ncolsingletonsremoved > 0 )
3664 for( c = firstcolsind ; c < mod2data->ncolsind && j < mod2data->ncolsind; ++c)
3666 if( c < nconsideredcols )
3667 while( j < mod2data->ncolsind && removecol[j] )
3669 if( c < j && j < mod2data->ncolsind )
3670 mod2data->colsind[c] = mod2data->colsind[j];
3673 mod2data->ncolsind -= (nzerocolsremoved + ncolsingletonsremoved);
3697 int identsubmatrixsize;
3703 assert(scip !=
NULL);
3704 assert(sepadata !=
NULL);
3705 assert(lpdata !=
NULL);
3706 assert(mod2data !=
NULL);
3707 assert(mod2data->relatedsubproblem !=
NULL);
3710 if( mod2data->ncolsind == 0 || mod2data->nrowsind == 0 )
3715 while( nslackzerorows < mod2data->nrowsind
3716 &&
SCIPisZero(scip, mod2data->slacks[mod2data->rowsind[nslackzerorows]]) )
3719 if( nslackzerorows == 0 )
3724 if( mod2data->ncolsind > 1 )
3726 SCIPsortInd( mod2data->colsind , compRealNonIncreasing , (
void*) mod2data->fracsol , mod2data->ncolsind );
3730 if( mod2data->nrowsind > 1 )
3732 SCIPsortInd( mod2data->rowsind , compRealNonDecreasing , (
void*) mod2data->slacks , mod2data->nrowsind );
3736 identsubmatrixsize = 0;
3740 for( pivotcol = 0 ; pivotcol < mod2data->ncolsind ; ++pivotcol)
3742 if( identsubmatrixsize == mod2data->nrowsind )
3748 for( pivotrow = identsubmatrixsize ; pivotrow < nslackzerorows ; ++pivotrow)
3749 if( mod2data->rows[mod2data->rowsind[pivotrow]][rowsbind] & rowsbmask )
3751 if( pivotrow == nslackzerorows )
3755 for( r = 0 ; r < nslackzerorows ; ++r)
3759 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
3762 BITARRAYSXOR(mod2data->rows[mod2data->rowsind[pivotrow]],
3763 mod2data->rows[mod2data->rowsind[r]],mod2data->rowsbitarraysize);
3764 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[pivotrow]],
3765 mod2data->rowaggregations[mod2data->rowsind[r]],mod2data->rowaggregationsbitarraysize);
3766 mod2data->rhs[mod2data->rowsind[r]] =
3767 XOR(mod2data->rhs[mod2data->rowsind[pivotrow]],mod2data->rhs[mod2data->rowsind[r]]);
3774 temp = mod2data->rowsind[pivotrow];
3775 mod2data->rowsind[pivotrow] = mod2data->rowsind[identsubmatrixsize];
3776 mod2data->rowsind[identsubmatrixsize] = temp;
3777 temp = mod2data->colsind[pivotcol];
3778 mod2data->colsind[pivotcol] = mod2data->colsind[identsubmatrixsize];
3779 mod2data->colsind[identsubmatrixsize] = temp;
3781 identsubmatrixsize++;
3784 if( identsubmatrixsize > 0 )
3788 for( pivot = 0 ; pivot < identsubmatrixsize ; ++pivot)
3792 for( r = nslackzerorows ; r < mod2data->nrowsind ; ++r)
3793 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
3797 mod2data->rows[mod2data->rowsind[r]],mod2data->rowsbitarraysize);
3798 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[pivot]],
3799 mod2data->rowaggregations[mod2data->rowsind[r]],mod2data->rowaggregationsbitarraysize);
3800 mod2data->rhs[mod2data->rowsind[r]] =
3801 XOR(mod2data->rhs[mod2data->rowsind[pivot]],mod2data->rhs[mod2data->rowsind[r]]);
3829 #ifdef WITHDECOMPOSE 3850 int processedrowsbitarraysize;
3851 int unprocessedrowidx;
3855 int processedcolsbitarraysize;
3881 ZEROHALF_SUBLPDATA* problem;
3883 ZEROHALF_SUBLPDATA* subproblem;
3885 int* rrowsinsubprob;
3886 int* rcolsinsubprob;
3888 int nrrowsinsubprob;
3889 int nrcolsinsubprob;
3903 assert(scip !=
NULL);
3904 assert(sepadata !=
NULL);
3905 assert(lpdata !=
NULL);
3906 assert(lpdata->subproblems !=
NULL);
3907 assert(lpdata->nsubproblems > 0);
3911 assert(problemindex >= 0);
3912 assert(problemindex <= lpdata->nsubproblems);
3914 problem = lpdata->subproblems[problemindex];
3916 assert(problem !=
NULL);
3917 assert(problem->rcols !=
NULL);
3918 assert(problem->nrcols > 0);
3919 assert(problem->rcolslbslack !=
NULL);
3920 assert(problem->rcolsubslack !=
NULL);
3921 assert(problem->rrows !=
NULL);
3922 assert(problem->nrrows > 0);
3923 assert(problem->rrowsrhs !=
NULL);
3924 assert(problem->rrowsslack !=
NULL);
3926 if( sepadata->dtimer ==
NULL )
3928 ZEROHALFcreateTimer((sepadata->dtimer));
3930 ZEROHALFstartTimer(sepadata->dtimer);
3949 lpdata->nsubproblems = 0;
3950 maxslack = sepadata->maxslack;
3952 nrrowsinitial = problem->nrrows;
3953 nrcolsinitial = problem->nrcols;
3960 unprocessedrowidx = 0;
3962 while( nprocessedrows < problem->nrrows )
3965 nrrowsinsubprob = 0;
3966 nrcolsinsubprob = 0;
3968 for( i = unprocessedrowidx ; i < problem->nrrows ; ++i)
3971 unprocessedrowidx++;
3981 while( queuelast > queuefirst )
3983 assert(queuelast <= problem->nrrows);
3985 i = queue[queuefirst];
3988 rrowsinsubprob[nrrowsinsubprob] = i;
3997 for( cidx = 0 ; cidx < ncolvals ; ++cidx)
4002 rcolsidx = lpdata->rcolsindexofcol[lppos];
4004 if( lpdata->subproblemsindexofcol[lppos] != problemindex || rcolsidx < 0 )
4006 if(
ISODD(scip, colvals[cidx]) )
4007 fliplhsrhs =
XOR(fliplhsrhs,
4015 if( nprocessedcols == problem->nrcols )
4021 if(
ISEVEN(scip, colvals[cidx]) )
4024 rcolsinsubprob[nrcolsinsubprob] = rcolsidx;
4031 for( ridx = 0 ; ridx < nrowvals ; ++ridx)
4036 rrowsidx = lpdata->rrowsindexofleftrow[lppos];
4037 if( lpdata->subproblemsindexofrow[lppos] == problemindex
4041 if(
ISODD(scip, rowvals[ridx]) )
4043 queue[queuelast] = rrowsidx;
4048 rrowsidx = lpdata->rrowsindexofrightrow[lppos];
4049 if( lpdata->subproblemsindexofrow[lppos] == problemindex
4053 if(
ISODD(scip, rowvals[ridx]) )
4055 queue[queuelast] = rrowsidx;
4063 rrowsinsubproboddrhs[nrrowsinsubprob-1] =
XOR((
SCIP_Bool)
ISODD(scip, problem->rrowsrhs[i]),fliplhsrhs);
4069 for( i = 0 ; i < nrrowsinsubprob ; ++i)
4070 if( rrowsinsubproboddrhs[i] )
4072 for( j = 0; j < nrcolsinsubprob; ++j)
4074 if( (
SCIPisLE(scip, problem->rcolsubslack[rcolsinsubprob[j]], maxslack)
4076 || (
SCIPisLE(scip, problem->rcolslbslack[rcolsinsubprob[j]], maxslack)
4077 &&
ISODD(scip,
SCIPcolGetLb(lpdata->cols[problem->rcols[rcolsinsubprob[j]]]))) )
4080 if( i == nrrowsinsubprob && j == nrcolsinsubprob )
4083 for( i = 0 ; i < nrrowsinsubprob ; ++i)
4085 lppos =
SCIProwGetLPPos(lpdata->rows[problem->rrows[rrowsinsubprob[i]]]);
4086 lpdata->subproblemsindexofrow[lppos] =
IRRELEVANT;
4087 if( lpdata->rrowsindexofleftrow[lppos] == rrowsinsubprob[i] )
4088 lpdata->rrowsindexofleftrow[lppos] = ROW_IN_SUBPROB_WITHOUT_ODD_RHS;
4089 if( lpdata->rrowsindexofrightrow[lppos] == rrowsinsubprob[i] )
4090 lpdata->rrowsindexofrightrow[lppos] = ROW_IN_SUBPROB_WITHOUT_ODD_RHS;
4092 for( j = 0 ; j < nrcolsinsubprob ; ++j)
4094 lppos =
SCIPcolGetLPPos(lpdata->cols[problem->rcols[rcolsinsubprob[j]]]);
4095 lpdata->subproblemsindexofcol[lppos] =
IRRELEVANT;
4096 lpdata->rcolsindexofcol[lppos] = COLUMN_IN_SUBPROB_WITHOUT_ODD_RHS;
4099 if( !
SCIPisInfinity(scip, problem->rcolslbslack[rcolsinsubprob[j]]) )
4101 if( !
SCIPisInfinity(scip, problem->rcolsubslack[rcolsinsubprob[j]]) )
4108 if( lpdata->nsubproblems == 0 && nprocessedrows == problem->nrrows )
4116 subproblem->nrrows = nrrowsinsubprob;
4120 subproblem->nrcols = nrcolsinsubprob;
4122 for( i = 0 ; i < nrrowsinsubprob ; ++i)
4124 rowindex = problem->rrows[rrowsinsubprob[i]];
4126 subproblem->rrows[i] = rowindex;
4127 subproblem->rrowsrhs[i] = problem->rrowsrhs[rrowsinsubprob[i]];
4128 subproblem->rrowsslack[i] = problem->rrowsslack[rrowsinsubprob[i]];
4130 if( lpdata->subproblemsindexofrow[rowindex] !=
IRRELEVANT )
4132 assert(lpdata->rrowsindexofleftrow[rowindex] >= 0
4133 || lpdata->rrowsindexofrightrow[rowindex] >= 0);
4134 lpdata->subproblemsindexofrow[rowindex] = lpdata->nsubproblems;
4135 if( lpdata->rrowsindexofleftrow[rowindex] >= 0 )
4136 lpdata->rrowsindexofleftrow[rowindex] = i;
4137 if( lpdata->rrowsindexofrightrow[rowindex] >= 0 )
4138 lpdata->rrowsindexofrightrow[rowindex] = i;
4142 for( i = 0 ; i < nrcolsinsubprob ; ++i)
4144 colindex = problem->rcols[rcolsinsubprob[i]];
4146 subproblem->rcols[i] = colindex;
4147 subproblem->rcolslbslack[i] = problem->rcolslbslack[rcolsinsubprob[i]];
4148 subproblem->rcolsubslack[i] = problem->rcolsubslack[rcolsinsubprob[i]];
4150 if( lpdata->subproblemsindexofcol[colindex] !=
IRRELEVANT )
4152 assert(lpdata->rcolsindexofcol[colindex] >= 0);
4153 lpdata->subproblemsindexofcol[colindex] = lpdata->nsubproblems;
4154 lpdata->rcolsindexofcol[colindex] = i;
4158 lpdata->subproblems[lpdata->nsubproblems] = subproblem;
4159 lpdata->nsubproblems++;
4161 totalnrrows += subproblem->nrrows;
4162 totalnrcols += subproblem->nrcols;
4164 SCIPdebugMsg(scip,
"subproblem %d: %d rrows, %d rcols\n", k, subproblem->nrrows, subproblem->nrcols);
4166 if( lpdata->nsubproblems == 0 )
4169 lpdata->subproblems[0] = problem;
4170 lpdata->nsubproblems = 1;
4171 totalnrrows = problem->nrrows;
4172 totalnrcols = problem->nrcols;
4188 ZEROHALFstopTimer(sepadata->dtimer);
4189 ZEROHALFstatisticsMessage(
"\n");
4190 ZEROHALFstatisticsMessage(
" | --------------------------------- problem \ 4191 -------------------------------- | ----- callback ---- | --total-\n");
4192 ZEROHALFstatisticsMessage(
" | nrrows | nrcols | ndlrrows | ndlrcols \ 4193 | nsubprob | ndelsubp | ndlvbnds | nsepcuts | ncutsfnd | time\n");
4194 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f\n",
4195 "DECOMPOSITION", totalnrrows, totalnrcols, nrrowsinitial - totalnrrows, nrcolsinitial - totalnrcols,
4196 lpdata->nsubproblems, k - lpdata->nsubproblems,
4198 0, 0, ZEROHALFevalTimer(sepadata->dtimer));
4201 assert(scip !=
NULL);
4202 assert(sepadata !=
NULL);
4203 assert(lpdata !=
NULL);
4225 assert(scip !=
NULL);
4226 assert(sepadata !=
NULL);
4227 assert(mod2data !=
NULL);
4228 assert(delta >= 0.0);
4229 assert(delta <= 1.0);
4233 if( mod2data->ncolsind == 0 || mod2data->nrowsind == 0 )
4243 maxsumfracsols = sepadata->maxslack * delta;
4246 if( mod2data->ncolsind > 1 )
4248 SCIPsortInd( mod2data->colsind , compRealNonIncreasing , (
void*) mod2data->fracsol , mod2data->ncolsind );
4251 for( c = mod2data->ncolsind - 1 ; c >= 0 ; --c)
4253 if(
SCIPisGT(scip, sumfracsols + mod2data->fracsol[mod2data->colsind[c]], maxsumfracsols) )
4256 sumfracsols += mod2data->fracsol[mod2data->colsind[c]];
4261 if( ncolsremoved > 0 )
4263 mod2data->ncolsind -= ncolsremoved;
4264 sepadata->maxslack -= sumfracsols;
4288 int nlslrowsremoved;
4289 int nlcolrowsremoved;
4300 assert(scip !=
NULL);
4301 assert(sepadata !=
NULL);
4302 assert(lpdata !=
NULL);
4303 assert(mod2data !=
NULL);
4304 assert(removelargeslackrows || removelargecolrows);
4308 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
4314 last = mod2data->nrowsind - 1;
4317 if( !mod2data->rhs[mod2data->rowsind[first]] )
4319 temp = mod2data->rowsind[first];
4320 mod2data->rowsind[first] = mod2data->rowsind[last];
4321 mod2data->rowsind[last] = temp;
4327 noddrhsrows = first + (mod2data->rhs[mod2data->rowsind[first]] ? 1 : 0);
4331 if( noddrhsrows == 0 )
4335 assert(noddrhsrows >= 0);
4336 SCIPsortInd( mod2data->rowsind , compRealNonDecreasing , (
void*) mod2data->slacks , noddrhsrows );
4337 if( noddrhsrows < mod2data->nrowsind )
4339 SCIPsortInd( mod2data->rowsind + noddrhsrows , compRealNonDecreasing , (
void*) mod2data->slacks ,
4340 mod2data->nrowsind - noddrhsrows );
4343 minslackoddrhsrows = mod2data->slacks[mod2data->rowsind[0]];
4344 nlslrowsremoved = 0;
4345 nlcolrowsremoved = 0;
4351 if(
SCIPisGT(scip, minslackoddrhsrows, sepadata->maxslack) )
4353 if( removelargeslackrows )
4355 for( i = 0 ; i < mod2data->nrowsind ; ++i )
4357 for( i = 0 ; i < mod2data->ncolsind ; ++i )
4359 mod2data->nrowsind = 0;
4360 mod2data->ncolsind = 0;
4369 if( removelargeslackrows )
4371 for( i = noddrhsrows ; i < mod2data->nrowsind ; ++i)
4372 if(
SCIPisGT(scip, minslackoddrhsrows + mod2data->slacks[mod2data->rowsind[i]], sepadata->maxslack) )
4374 nlslrowsremoved += mod2data->nrowsind - i;
4375 while(i < mod2data->nrowsind)
4378 r = mod2data->rowsind[i];
4380 assert(!mod2data->rhs[r]);
4381 assert(
SCIPisGT(scip, minslackoddrhsrows + mod2data->slacks[r], sepadata->maxslack));
4383 removerow[i] =
TRUE;
4389 if( removelargecolrows )
4391 if( mod2data->ncolsind > 0 )
4394 if( mod2data->ncolsind > 1 )
4396 SCIPsortInd( mod2data->colsind , compRealNonIncreasing , (
void*) mod2data->fracsol , mod2data->ncolsind );
4400 while( j < mod2data->ncolsind &&
SCIPisGT(scip, mod2data->fracsol[mod2data->colsind[j]] + minslackoddrhsrows, sepadata->maxslack) )
4402 c = mod2data->colsind[j];
4403 minslackrowwithnonz = 1.0;
4406 for( i = 0 ; i < mod2data->nrowsind ; ++i)
4408 if( mod2data->rows[mod2data->rowsind[i]][rowsbind] & rowsbmask )
4409 if(
SCIPisLT(scip, mod2data->slacks[mod2data->rowsind[i]], minslackrowwithnonz) )
4410 minslackrowwithnonz = mod2data->slacks[mod2data->rowsind[i]];
4412 if( minslackrowwithnonz < 1.0 )
4414 for( i = 0 ; i < mod2data->nrowsind ; ++i)
4416 if( mod2data->rows[mod2data->rowsind[i]][rowsbind] & rowsbmask )
4417 if(
SCIPisGT(scip, minslackrowwithnonz + mod2data->slacks[mod2data->rowsind[i]], sepadata->maxslack) )
4420 removerow[i] =
TRUE;
4430 if( nlslrowsremoved + nlcolrowsremoved > 0 )
4433 for( i = 0 ; i < mod2data->nrowsind && j < mod2data->nrowsind; ++i)
4435 if( i < mod2data->nrowsind )
4436 while( j < mod2data->nrowsind && removerow[j] )
4438 if( i < j && j < mod2data->nrowsind )
4439 mod2data->rowsind[i] = mod2data->rowsind[j];
4442 mod2data->nrowsind -= (nlslrowsremoved + nlcolrowsremoved);
4470 assert(scip !=
NULL);
4471 assert(mod2data !=
NULL);
4474 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
4485 for( c1 = 0 ; c1 < mod2data->ncolsind - 1 ; ++c1)
4489 for( c2 = c1 + 1 ; c2 < mod2data->ncolsind ; ++c2)
4493 for( r = 0 ; r < mod2data->nrowsind ; ++r)
4494 if( (mod2data->rows[mod2data->rowsind[r]][rowsbind1] & rowsbmask1)
4495 != (mod2data->rows[mod2data->rowsind[r]][rowsbind2] & rowsbmask2) )
4497 if( r == mod2data->nrowsind )
4501 mod2data->fracsol[mod2data->colsind[c2]] += mod2data->fracsol[mod2data->colsind[c1]];
4502 removecol[c1] =
TRUE;
4510 if( ncolsremoved > 0 )
4513 for( c2 = 0 ; c2 < mod2data->ncolsind && c1 < mod2data->ncolsind; ++c2)
4515 if( c2 < mod2data->ncolsind )
4516 while( c1 < mod2data->ncolsind && removecol[c1] )
4518 if( c2 < c1 && c1 < mod2data->ncolsind )
4519 mod2data->colsind[c2] = mod2data->colsind[c1];
4522 mod2data->ncolsind -= ncolsremoved;
4551 #ifdef ZEROHALF__PRINT_STATISTICS 4556 int nsepacutsbeforeppm;
4557 int nsepacutsinitial;
4558 int nzerohalfcutsbeforeppm;
4559 int nzerohalfcutsinitial;
4565 assert(scip !=
NULL);
4566 assert(sepadata !=
NULL);
4567 assert(lpdata !=
NULL);
4568 assert(mod2data !=
NULL);
4569 assert(maxsepacuts >= 0);
4570 assert(maxcuts >= 0);
4571 assert(result !=
NULL);
4572 assert(nsepacuts !=
NULL);
4573 assert(nzerohalfcuts !=
NULL);
4574 assert(zerohalfcuts !=
NULL);
4575 assert(*nsepacuts <= *nzerohalfcuts);
4577 assert(mod2data->relatedsubproblem !=
NULL);
4578 assert(mod2data->rows !=
NULL);
4579 assert(mod2data->rowaggregations !=
NULL);
4580 assert(mod2data->rhs !=
NULL);
4581 assert(mod2data->slacks !=
NULL);
4582 assert(mod2data->fracsol !=
NULL);
4583 assert(mod2data->nrows > 0);
4584 assert(mod2data->rowsind !=
NULL);
4585 assert(mod2data->colsind !=
NULL);
4587 if( sepadata->nppmethods == -1 )
4589 sepadata->nppmethods = (int) strlen(sepadata->ppmethods);
4590 if( sepadata->nppmethods > 0 && sepadata->ppmethods[0] ==
'-' )
4591 sepadata->nppmethods = 0;
4594 if( sepadata->nppmethods == 0 )
4598 #ifdef ZEROHALF__PRINT_STATISTICS 4599 if( sepadata->pptimers ==
NULL )
4602 for( i = 0 ; i <= sepadata->nppmethods; ++i)
4604 ZEROHALFcreateTimer((sepadata->pptimers[i]));
4607 ZEROHALFstartTimer(sepadata->pptimers[sepadata->nppmethods]);
4610 if( mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
4613 #ifdef ZEROHALF__PRINT_STATISTICS 4614 ncolsinitial = mod2data->ncolsind;
4615 nrowsinitial = mod2data->nrowsind;
4616 nsepacutsinitial = *nsepacuts;
4617 nzerohalfcutsinitial = *nzerohalfcuts;
4620 #ifdef ZEROHALF__PRINT_STATISTICS 4621 ZEROHALFstatisticsMessage(
"\n");
4622 ZEROHALFstatisticsMessage(
" | ------------------------------- subproblem\ 4623 ------------------------------- | ----- callback ---- | --total-\n");
4624 ZEROHALFstatisticsMessage(
" | nrowsind | ncolsind | ndelrows | ndelcols \ 4625 | nsepcuts | ncutsfnd | time | nsepcuts | ncutsfnd | time\n");
4626 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8.4f\n",
4627 "START PREPROCSS", mod2data->nrowsind, mod2data->ncolsind, 0, 0, 0, 0, 0.0,
4628 *nsepacuts, *nzerohalfcuts, ZEROHALFevalTimer(sepadata->pptimers[sepadata->nppmethods]));
4629 ZEROHALFcreateNewTimer(timer);
4630 ZEROHALFstartTimer(timer);
4632 ZEROHALFcreateNewTimer(pptimer);
4635 for( i = 0 ; i < sepadata->nppmethods ; ++i)
4638 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
4640 #ifndef ZEROHALF__PRINT_STATISTICS 4642 if( mod2data->nrowsind == 0 && mod2data->ncolsind == 0 )
4646 #ifdef ZEROHALF__PRINT_STATISTICS 4648 ZEROHALFstartTimer(pptimer);
4649 ZEROHALFstartTimer(sepadata->pptimers[i]);
4650 ncolsbeforeppm = mod2data->ncolsind;
4651 nrowsbeforeppm = mod2data->nrowsind;
4652 nsepacutsbeforeppm = *nsepacuts;
4653 nzerohalfcutsbeforeppm = *nzerohalfcuts;
4657 switch(sepadata->ppmethods[i])
4680 0, mod2data->nrowsind, normtype, maxsepacuts, maxcuts, nsepacuts,
4681 nzerohalfcuts, zerohalfcuts, varsolvals,
PPZEROONEROW, result));
4710 sepadata->ppdelta));
4718 SCIPerrorMessage(
"invalid preprocessing method '%c'\n", sepadata->ppmethods[i]);
4722 #ifdef ZEROHALF__PRINT_STATISTICS 4724 ZEROHALFstopTimer(sepadata->pptimers[i]);
4725 ZEROHALFstopTimer(pptimer);
4726 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8.4f\n",
4727 ppname, mod2data->nrowsind, mod2data->ncolsind,
4728 nrowsbeforeppm - mod2data->nrowsind, ncolsbeforeppm - mod2data->ncolsind,
4729 *nsepacuts - nsepacutsbeforeppm, *nzerohalfcuts - nzerohalfcutsbeforeppm,
4730 ZEROHALFevalTimer(pptimer), *nsepacuts, *nzerohalfcuts,
4731 ZEROHALFevalTimer(sepadata->pptimers[i]));
4732 ZEROHALFresetTimer(pptimer);
4736 #ifdef ZEROHALF__PRINT_STATISTICS 4738 ZEROHALFstopTimer(timer);
4739 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8.4f\n",
4740 "PREPROCESSED", mod2data->nrowsind, mod2data->ncolsind,
4741 nrowsinitial - mod2data->nrowsind, ncolsinitial - mod2data->ncolsind,
4742 *nsepacuts - nsepacutsinitial, *nzerohalfcuts - nzerohalfcutsinitial,
4743 ZEROHALFevalTimer(timer), *nsepacuts, *nzerohalfcuts,
4744 ZEROHALFevalTimer(sepadata->pptimers[sepadata->nppmethods]));
4745 ZEROHALFstatisticsMessage(
"\n");
4746 ZEROHALFfreeTimer(timer);
4747 ZEROHALFfreeTimer(pptimer);
4748 ZEROHALFstopTimer(sepadata->pptimers[sepadata->nppmethods]);
4750 ZEROHALFstatisticsMessage(
" | ------------------------------- subproblem ------------------------------- | ------------------------------\n");
4751 ZEROHALFstatisticsMessage(
" | | max2/row | max2/col | A^T ept | \n");
4752 ZEROHALFstatisticsMessage(
"%15s | | %8s | %8s | %8s |\n",
4755 ZEROHALFstatisticsMessage(
"\n");
4775 int naggregatedrrows;
4777 assert(rowaggregation !=
NULL);
4780 naggregatedrrows = 0;
4781 for( i = 0 ; i < nrrows ; ++i)
4799 #define BRANCHPRIORITY__AVOID_BRANCHING 0 4800 #define BRANCHPRIORITY__PREFER_BRANCHING 0 4807 ZEROHALF_AUXIPDATA* auxipdata,
4834 assert(scip !=
NULL);
4835 assert(sepadata !=
NULL);
4836 assert(lpdata !=
NULL);
4837 assert(mod2data !=
NULL);
4838 assert(auxipdata !=
NULL);
4840 assert(mod2data->relatedsubproblem !=
NULL);
4841 assert(mod2data->rows !=
NULL);
4842 assert(mod2data->rowaggregations !=
NULL);
4843 assert(mod2data->rhs !=
NULL);
4844 assert(mod2data->slacks !=
NULL);
4845 assert(mod2data->fracsol !=
NULL);
4846 assert(mod2data->rowsind !=
NULL);
4847 assert(mod2data->colsind !=
NULL);
4849 assert(auxipdata->subscip ==
NULL);
4850 assert(auxipdata->v ==
NULL);
4851 assert(auxipdata->y ==
NULL);
4852 assert(auxipdata->r ==
NULL);
4853 assert(auxipdata->q ==
NULL);
4854 assert(auxipdata->feasipcons ==
NULL);
4855 assert(auxipdata->oddrhscons ==
NULL);
4856 assert(auxipdata->columnsumcons ==
NULL);
4858 auxipdata->m = mod2data->nrowsind;
4859 auxipdata->n = mod2data->ncolsind;
4873 maxslack = sepadata->maxslack;
4874 nrrows = mod2data->relatedsubproblem->nrrows;
4889 if( setnodelimit ==
TRUE )
4890 auxipdata->nodelimit = 3000;
4892 auxipdata->nodelimit = -1;
4895 auxipdata->objectivelimit =
MIN(1.0, maxslack + feastol);
4902 if( auxipdata->timelimit <= 0.0 )
4906 maxnconsvars = auxipdata->m + auxipdata->n + 2;
4916 TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE, &success) );
4919 TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
TRUE, &success) );
4921 SCIPdebugMsg(scip,
"Copying the plugins was %s successful.\n", success ?
"" :
"not");
4926 settingsfileexists =
TRUE;
4927 if( strlen(sepadata->subscipsettings) == 0 )
4928 settingsfileexists =
FALSE;
4929 if( strlen(sepadata->subscipsettings) == 1 && sepadata->subscipsettings[0] ==
'-' )
4930 settingsfileexists =
FALSE;
4932 if( settingsfileexists )
4999 isfeasip = (sepadata->subscipobjective ==
'v' ?
FALSE :
TRUE);
5000 isweighted = (sepadata->subscipobjective ==
'w' ?
TRUE :
FALSE);
5001 ispenalized = (sepadata->subscipobjective ==
'p' ?
TRUE :
FALSE);
5022 for( j = 0 ; j < auxipdata->n ; ++j)
5031 for( i = 0 ; i < auxipdata->m ; ++i)
5034 assert(mod2data->rows[mod2data->rowsind[i]] !=
NULL);
5041 objcoef =
calcObjWeight(mod2data->rowaggregations[mod2data->rowsind[i]], nrrows);
5043 else if( ispenalized )
5045 objcoef = mod2data->slacks[mod2data->rowsind[i]]
5046 + (sepadata->subscipobjpen
5047 *
calcObjWeight(mod2data->rowaggregations[mod2data->rowsind[i]], nrrows));
5053 objcoef = mod2data->slacks[mod2data->rowsind[i]];
5061 for( j = 0 ; j < auxipdata->n ; ++j)
5068 objcoef = mod2data->fracsol[mod2data->colsind[j]];
5079 for( i = 0 ; i < auxipdata->m ; ++i)
5081 consvals[nconsvars] = mod2data->slacks[mod2data->rowsind[i]];
5082 consvars[nconsvars] = auxipdata->v[i];
5085 for( j = 0 ; j < auxipdata->n ; ++j)
5087 consvals[nconsvars] = mod2data->fracsol[mod2data->colsind[j]];
5088 consvars[nconsvars] = auxipdata->y[j];
5092 nconsvars, consvars, consvals, 0.0, auxipdata->objectivelimit,
5098 for( i = 0 ; i < auxipdata->m ; ++i)
5099 if( mod2data->rhs[mod2data->rowsind[i]] ==
TRUE )
5101 consvals[nconsvars] = 1.0;
5102 consvars[nconsvars] = auxipdata->v[i];
5105 consvals[nconsvars] = -2.0;
5106 consvars[nconsvars] = auxipdata->q;
5109 nconsvars, consvars, consvals, 1.0, 1.0,
5113 for( j = 0 ; j < auxipdata->n ; ++j)
5119 for( i = 0 ; i < auxipdata->m ; ++i) {
5120 if( mod2data->rows[mod2data->rowsind[i]][rowsbind] & rowsbmask )
5122 consvals[nconsvars] = 1.0;
5123 consvars[nconsvars] = auxipdata->v[i];
5127 consvals[nconsvars] = -1.0;
5128 consvars[nconsvars] = auxipdata->y[j];
5130 consvals[nconsvars] = -2.0;
5131 consvars[nconsvars] = auxipdata->r[j];
5156 ZEROHALF_AUXIPDATA* auxipdata,
5167 assert(sepadata !=
NULL);
5168 assert(mod2data !=
NULL);
5169 assert(auxipdata !=
NULL);
5170 assert(auxipdata->subscip !=
NULL);
5171 assert(sols !=
NULL);
5172 assert(*sols ==
NULL);
5173 assert(*nsols == 0);
5176 retcode =
SCIPsolve(auxipdata->subscip);
5185 SCIPwarningMessage(scip,
"Error while solving subproblem in zerohalf separator; sub-SCIP terminated with code <%d>\n", retcode);
5193 maxslack = sepadata->maxslack;
5205 if( !sepadata->subscipuseallsols )
5210 if( sepadata->subscipobjective ==
'v' )
5212 for( i = 0 ; i < *nsols ; ++i)
5232 for( i = 0 ; i < *nsols ; ++i)
5235 for( j = 0 ; j < auxipdata->m ; ++j)
5236 z += mod2data->slacks[mod2data->rowsind[j]]
5237 *
SCIPgetSolVal(auxipdata->subscip, (*sols)[i], auxipdata->v[j]);
5238 for( j = 0 ; j < auxipdata->n ; ++j)
5239 z += mod2data->fracsol[mod2data->colsind[j]]
5240 *
SCIPgetSolVal(auxipdata->subscip, (*sols)[i], auxipdata->y[j]);
5245 propersols[npropersols] = (*sols)[i];
5246 viols[npropersols] = z;
5253 for( i = 1 ; i < npropersols && swapped; ++i)
5256 for( j = 0 ; j < npropersols - i ; ++j)
5258 if( viols[j] > viols[j+1] )
5260 tempviol = viols[j+1];
5261 viols[j+1] = viols[j];
5262 viols[j] = tempviol;
5263 tempsol = propersols[j+1];
5264 propersols[j+1] = propersols[j];
5265 propersols[j] = tempsol;
5272 *nsols = npropersols;
5295 assert(scip !=
NULL);
5296 assert(lpdata !=
NULL);
5297 assert(lpdata->nrows > 0);
5298 assert(0 <= rowsindex);
5299 assert(rowsindex < lpdata->nrows);
5300 assert(lpdata->rrowsindexofleftrow[rowsindex] == rrowsindex
5301 || lpdata->rrowsindexofrightrow[rowsindex] == rrowsindex);
5302 assert(weights !=
NULL);
5303 assert(*weights ==
NULL);
5312 if( lpdata->rrowsindexofleftrow[rowsindex] == rrowsindex )
5313 (*weights)[rowsindex] = lpdata->intscalarsleftrow[rowsindex] * (-0.5);
5315 (*weights)[rowsindex] = lpdata->intscalarsrightrow[rowsindex] * 0.5;
5331 ZEROHALF_AUXIPDATA* auxipdata,
5339 assert(scip !=
NULL);
5340 assert(mod2data !=
NULL);
5341 assert(mod2data->nrowsind > 0);
5342 assert(auxipdata !=
NULL);
5343 assert(auxipdata->subscip !=
NULL);
5344 assert(auxipdata->v !=
NULL);
5345 assert(solution !=
NULL);
5346 assert(rrowsincut !=
NULL);
5347 assert(*rrowsincut ==
NULL);
5348 assert(nrrowsincut !=
NULL);
5353 BITARRAYCLEAR(*rrowsincut, mod2data->rowaggregationsbitarraysize);
5358 for( i = 0 ; i < mod2data->nrowsind ; ++i)
5359 if( auxipdata->v[i] !=
NULL )
5362 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[i]], (*rrowsincut) ,
5363 mod2data->rowaggregationsbitarraysize);
5390 ZEROHALF_AUXIPDATA* auxipdata;
5400 assert(scip !=
NULL);
5401 assert(sepadata !=
NULL);
5402 assert(lpdata !=
NULL);
5403 assert(mod2data !=
NULL);
5404 assert(maxsepacuts >= 0);
5405 assert(maxcuts >= 0);
5406 assert(nsepacuts !=
NULL);
5407 assert(nzerohalfcuts !=
NULL);
5408 assert(zerohalfcuts !=
NULL);
5409 assert(*nsepacuts <= *nzerohalfcuts);
5410 assert(varsolvals !=
NULL);
5411 assert(result !=
NULL);
5413 assert(mod2data->relatedsubproblem !=
NULL);
5414 assert(mod2data->rows !=
NULL);
5415 assert(mod2data->rowaggregations !=
NULL);
5416 assert(mod2data->rhs !=
NULL);
5417 assert(mod2data->slacks !=
NULL);
5418 assert(mod2data->fracsol !=
NULL);
5419 assert(mod2data->rowsind !=
NULL);
5420 assert(mod2data->colsind !=
NULL);
5424 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
5428 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
5438 if( auxipdata->subscip ==
NULL )
5450 for( s = 0; s < nsols ; ++s)
5453 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
5459 assert(nrrowsincut > 0);
5464 if ( weights ==
NULL )
5469 assert(nrowsincut > 0);
5472 SCIP_CALL( debugPrintLPRowsAndCols(scip, lpdata) );
5474 debugPrintSubLpData(scip, lpdata, mod2data->relatedsubproblem);
5475 debugPrintMod2Data(scip, lpdata, mod2data,
TRUE);
5484 mod2data->relatedsubproblem, mod2data, nrrowsincut, nrowsincut,
AUXIP));
5486 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
5506 if( sepadata->subscipobjective !=
'v' )
5529 assert(scip !=
NULL);
5530 assert(mod2data !=
NULL);
5531 assert(row !=
NULL);
5532 assert(maxinnerproduct >= 0);
5533 assert(innerproduct !=
NULL);
5535 *innerproduct = 0.0;
5538 if( mod2data->nrows == 0 || mod2data->nrowsind == 0
5539 || mod2data->ncolsind == 0 )
5543 for( c = 0 ; c < mod2data->ncolsind ; ++c)
5545 rcolindex = mod2data->colsind[c];
5547 *innerproduct += mod2data->fracsol[rcolindex];
5548 if(
SCIPisGT(scip, *innerproduct, maxinnerproduct) )
5572 int maxncombinedrows
5594 assert(scip !=
NULL);
5595 assert(sepadata !=
NULL);
5596 assert(lpdata !=
NULL);
5597 assert(mod2data !=
NULL);
5598 assert(maxsepacuts >= 0);
5599 assert(maxcuts >= 0);
5600 assert(nsepacuts !=
NULL);
5601 assert(nzerohalfcuts !=
NULL);
5602 assert(zerohalfcuts !=
NULL);
5603 assert(*nsepacuts <= *nzerohalfcuts);
5604 assert(varsolvals !=
NULL);
5605 assert(result !=
NULL);
5606 assert(maxncombinedrows >= 1);
5608 assert(mod2data->relatedsubproblem !=
NULL);
5609 assert(mod2data->rows !=
NULL);
5610 assert(mod2data->rowaggregations !=
NULL);
5611 assert(mod2data->rhs !=
NULL);
5612 assert(mod2data->slacks !=
NULL);
5613 assert(mod2data->fracsol !=
NULL);
5614 assert(mod2data->rowsind !=
NULL);
5615 assert(mod2data->colsind !=
NULL);
5619 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
5623 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
5629 last = mod2data->nrowsind - 1;
5632 if( !mod2data->rhs[mod2data->rowsind[first]] )
5634 temp = mod2data->rowsind[first];
5635 mod2data->rowsind[first] = mod2data->rowsind[last];
5636 mod2data->rowsind[last] = temp;
5642 noddrhsrows = first + (mod2data->rhs[mod2data->rowsind[first]] ? 1 : 0);
5645 if( noddrhsrows == 0 )
5651 if( maxncombinedrows > 1 )
5655 BITARRAYCLEAR(rrowsincut, mod2data->rowaggregationsbitarraysize);
5659 assert(noddrhsrows >= 0);
5660 SCIPsortInd( mod2data->rowsind , compRealNonDecreasing , (
void*) mod2data->slacks , noddrhsrows );
5662 if( noddrhsrows < mod2data->nrowsind )
5664 SCIPsortInd( mod2data->rowsind + noddrhsrows , compRealNonDecreasing , (
void*) mod2data->slacks , mod2data->nrowsind - noddrhsrows );
5667 minslackoddrhsrows = mod2data->slacks[mod2data->rowsind[0]];
5669 if(
SCIPisLE(scip, minslackoddrhsrows, sepadata->maxslack) )
5671 for( ncombinedrows = 1 ; ncombinedrows <= maxncombinedrows ; ++ncombinedrows )
5673 switch( ncombinedrows )
5677 for( i = 0 ; i < noddrhsrows ; ++i)
5679 r1 = mod2data->rowsind[i];
5680 assert(mod2data->rhs[r1]);
5681 if( *nzerohalfcuts == maxcuts || *nsepacuts == maxsepacuts )
5683 slack1 = mod2data->slacks[r1];
5684 if(
SCIPisGT(scip, slack1, sepadata->maxslack) )
5687 sepadata->maxslack, &roundingdownweakening));
5688 if(
SCIPisLE(scip, roundingdownweakening + slack1, sepadata->maxslack) )
5695 mod2data, mod2data->rowaggregations[r1], &weights, &nrowsincut));
5696 if( weights ==
NULL )
5698 assert(nrowsincut > 0);
5702 mod2data->relatedsubproblem, mod2data, 2, nrowsincut,
HEURISTICSENUM));
5704 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
5721 assert(combinedrow !=
NULL);
5722 assert(rrowsincut !=
NULL);
5723 if( noddrhsrows == mod2data->nrowsind )
5725 if( mod2data->nrowsind < 2 )
5729 for( i = 0 ; i < noddrhsrows ; ++i)
5731 r1 = mod2data->rowsind[i];
5732 assert(mod2data->rhs[r1]);
5733 if( *nzerohalfcuts == maxcuts || *nsepacuts == maxsepacuts )
5735 slack1 = mod2data->slacks[r1];
5736 if(
SCIPisGT(scip, slack1, sepadata->maxslack) )
5739 for( j = noddrhsrows ; j < mod2data->ncolsind ; ++j)
5741 r2 = mod2data->rowsind[j];
5742 assert(!mod2data->rhs[r2]);
5743 if( *nzerohalfcuts == maxcuts || *nsepacuts == maxsepacuts )
5745 slack2 = mod2data->slacks[r2];
5746 if(
SCIPisGT(scip, slack1 + slack2, sepadata->maxslack) )
5749 BITARRAYSXOR(mod2data->rows[r2], combinedrow, mod2data->rowsbitarraysize);
5751 sepadata->maxslack, &roundingdownweakening));
5752 if(
SCIPisLE(scip, roundingdownweakening + slack1 + slack2, sepadata->maxslack) )
5757 BMScopyMemoryArray(rrowsincut, mod2data->rowaggregations[r1], mod2data->rowaggregationsbitarraysize);
5758 BITARRAYSXOR(mod2data->rowaggregations[r2], rrowsincut, mod2data->rowaggregationsbitarraysize);
5763 mod2data, rrowsincut, &weights, &nrowsincut));
5764 if ( weights ==
NULL )
5768 assert(nrowsincut > 0);
5772 mod2data->relatedsubproblem, mod2data, 2, nrowsincut,
HEURISTICSENUM));
5774 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
5812 void debugPrintAuxGraphNode(
5818 assert(node !=
NULL);
5821 for( i = 0 ; i < node->nneighbors ; ++i)
5823 SCIPdebugMsg(scip,
" neighbor %4d: %p weight: %6f rrow: %4d\n", i, node->neighbors[i], node->edgeweights[i], node->relatedrows[i]);
5825 SCIPdebugMsg(scip,
" nneighbors: %d distance: %6f previous: %p\n", node->nneighbors, node->distance, node->previous);
5834 ZEROHALF_AUXGRAPH* graph,
5849 int maxnumberofneighbors;
5851 assert(scip !=
NULL);
5852 assert(graph !=
NULL);
5853 assert(node1index >= 0);
5854 assert(node1index < graph->
nnodes);
5855 assert(node2index >= 0);
5856 assert(node2index < graph->nnodes);
5859 maxnumberofneighbors = 2 * graph->nnodes - 2;
5863 node1 = graph->nodes[node1index];
5864 node2 = graph->nodecopies[node2index];
5865 node1copy = graph->nodecopies[node1index];
5866 node2copy = graph->nodes[node2index];
5870 node1 = graph->nodes[node1index];
5871 node2 = graph->nodes[node2index];
5872 node1copy = graph->nodecopies[node1index];
5873 node2copy = graph->nodecopies[node2index];
5876 if( node1->nneighbors == 0 )
5878 assert(maxnumberofneighbors > 0);
5888 if( node2->nneighbors == 0 )
5890 assert(maxnumberofneighbors > 0);
5900 n2 = node2->nneighbors;
5901 for( n1 = 0 ; n1 < node1->nneighbors ; ++n1)
5902 if( node1->neighbors[n1] == node2 )
5904 if( n1 < node1->nneighbors)
5905 for( n2 = 0 ; n2 < node2->nneighbors ; ++n2)
5906 if( node2->neighbors[n2] == node1 )
5908 if( n1 < node1->nneighbors )
5911 assert(node1->neighbors[n1] == node2);
5912 assert(n2 < node2->nneighbors);
5913 assert(node2->neighbors[n2] == node1);
5914 assert(node1->edgeweights[n1] == node2->edgeweights[n2]);
5917 if( n1 == node1->nneighbors ||
SCIPisLT(scip, weight, node1->edgeweights[n1]) )
5919 node1->neighbors[n1] = node2;
5920 node1->edgeweights[n1] = weight;
5921 node1->relatedrows[n1] = relatedrow;
5922 node1->nneighbors++;
5924 node2->neighbors[n2] = node1;
5925 node2->edgeweights[n2] = weight;
5926 node2->relatedrows[n2] = relatedrow;
5927 node2->nneighbors++;
5929 node1copy->neighbors[n1] = node2copy;
5930 node1copy->edgeweights[n1] = weight;
5931 node1copy->relatedrows[n1] = relatedrow;
5932 node1copy->nneighbors++;
5934 node2copy->neighbors[n2] = node1copy;
5935 node2copy->edgeweights[n2] = weight;
5936 node2copy->relatedrows[n2] = relatedrow;
5937 node2copy->nneighbors++;
5950 ZEROHALF_AUXGRAPH* graph,
5958 int nunprocessednodes;
5967 assert(scip !=
NULL);
5968 assert(graph !=
NULL);
5969 assert(graph->nnodes > 0);
5970 assert(sourcenode !=
NULL);
5971 assert(targetnode !=
NULL);
5972 assert(maxdistance > 0.0);
5973 assert(maxdistance <= 1.0);
5979 nunprocessednodes = 0;
5980 for( v = 0; v < graph->nnodes ; ++v)
5982 graph->nodes[v]->distance = 1.0;
5983 graph->nodes[v]->previous =
NULL;
5985 graph->nodecopies[v]->distance = 1.0;
5986 graph->nodecopies[v]->previous =
NULL;
5988 unprocessednodes[nunprocessednodes] = graph->nodes[v];
5989 ++nunprocessednodes;
5990 unprocessednodes[nunprocessednodes] = graph->nodecopies[v];
5991 ++nunprocessednodes;
5993 sourcenode->distance = 0.0;
5994 sourcenode->previous =
NULL;
5996 assert(nunprocessednodes == 2 * graph->nnodes);
5997 assert(nunprocessednodes > 0);
6000 while( nunprocessednodes > 0 )
6004 mindistance = unprocessednodes[0]->distance;
6005 for( v = 1 ; v < nunprocessednodes ; ++v)
6006 if( unprocessednodes[v]->distance < mindistance )
6009 mindistance = unprocessednodes[v]->distance;
6012 if(
SCIPisGT(scip, mindistance, maxdistance) )
6015 currentnode = unprocessednodes[u];
6016 unprocessednodes[u] = unprocessednodes[nunprocessednodes-1];
6017 nunprocessednodes--;
6020 for( n = 0 ; n < currentnode->nneighbors ; ++n)
6022 newdistance = currentnode->distance + currentnode->edgeweights[n];
6024 if(
SCIPisLT(scip, newdistance , currentnode->neighbors[n]->distance) )
6026 currentnode->neighbors[n]->distance = newdistance;
6027 currentnode->neighbors[n]->previous = currentnode;
6029 if( currentnode->neighbors[n] == targetnode )
6062 ZEROHALF_AUXGRAPH* auxgraph;
6077 assert(scip !=
NULL);
6078 assert(sepadata !=
NULL);
6079 assert(lpdata !=
NULL);
6080 assert(mod2data !=
NULL);
6081 assert(maxsepacuts >= 0);
6082 assert(maxcuts >= 0);
6083 assert(nsepacuts !=
NULL);
6084 assert(nzerohalfcuts !=
NULL);
6085 assert(zerohalfcuts !=
NULL);
6086 assert(*nsepacuts <= *nzerohalfcuts);
6087 assert(varsolvals !=
NULL);
6088 assert(result !=
NULL);
6089 assert(wrongstructure !=
NULL);
6091 *wrongstructure =
FALSE;
6094 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
6098 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
6104 *wrongstructure =
TRUE;
6109 if( mod2data->nrowsind == 1 )
6112 normtype, maxsepacuts, maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts,
6113 varsolvals, result, 1));
6122 auxgraph->nnodes = mod2data->ncolsind + 1;
6125 q = auxgraph->nnodes - 1;
6127 for( j = 0 ; j < auxgraph->nnodes ; ++j)
6133 for( i = 0 ; i < mod2data->nrowsind ; ++i)
6135 rowsindex = mod2data->rowsind[i];
6136 for( j = 0 ; j < mod2data->ncolsind; ++j)
6139 for( k = j+1 ; k < mod2data->ncolsind; ++k)
6144 if( j >= mod2data->ncolsind )
6146 if( mod2data->rhs[rowsindex] )
6148 if(
SCIPisLE(scip, mod2data->slacks[rowsindex], sepadata->maxslack) )
6155 mod2data->rowaggregations[rowsindex], &weights, &nrowsincut));
6156 if( weights ==
NULL )
6160 assert(nrowsincut > 0);
6164 mod2data->relatedsubproblem, mod2data, nrrowsincut, nrowsincut,
AUXGRAPH) );
6166 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff) );
6178 assert( weights !=
NULL );
6191 if( k >= mod2data->ncolsind )
6195 mod2data->rhs[rowsindex], mod2data->slacks[rowsindex], rowsindex));
6202 mod2data->rhs[rowsindex], mod2data->slacks[rowsindex], rowsindex));
6209 for( n = 0 ; n < auxgraph->nnodes && n != q ; ++n)
6212 FALSE, mod2data->fracsol[mod2data->colsind[n]], -1));
6215 if( cutoff || auxgraph->nnodes == 0 )
6225 for( n = 0 ; n < auxgraph->nnodes && n != q ; ++n)
6228 auxgraph->nodes[n], auxgraph->nodecopies[n], sepadata->maxslack));
6230 if(
SCIPisLE(scip, auxgraph->nodecopies[n]->distance, sepadata->maxslack) )
6236 BITARRAYCLEAR(rrowsincut, mod2data->rowaggregationsbitarraysize);
6240 node = auxgraph->nodecopies[n];
6241 while( node->previous !=
NULL )
6243 for( i = 0 ; i < node->nneighbors ; ++i)
6244 if( node->neighbors[i] == node->previous )
6246 assert(i < node->nneighbors);
6247 rowsindex = node->relatedrows[i];
6248 BITARRAYSXOR(mod2data->rowaggregations[rowsindex], rrowsincut ,
6249 mod2data->rowaggregationsbitarraysize);
6250 node = node->previous;
6255 assert(weights ==
NULL);
6257 mod2data, rrowsincut, &weights, &nrowsincut));
6258 if( weights ==
NULL )
6263 assert(nrowsincut > 0);
6267 mod2data->relatedsubproblem, mod2data, nrrowsincut, nrowsincut,
AUXGRAPH));
6269 lpdata, weights, normtype, *nzerohalfcuts, varsolvals, zerohalfcuts[*nzerohalfcuts], &cutoff));
6281 assert( weights !=
NULL );
6285 if( rrowsincut !=
NULL )
6323 int identsubmatrixsize;
6329 assert(scip !=
NULL);
6330 assert(sepadata !=
NULL);
6331 assert(lpdata !=
NULL);
6332 assert(mod2data !=
NULL);
6333 assert(maxsepacuts >= 0);
6334 assert(maxcuts >= 0);
6335 assert(nsepacuts !=
NULL);
6336 assert(nzerohalfcuts !=
NULL);
6337 assert(zerohalfcuts !=
NULL);
6338 assert(*nsepacuts <= *nzerohalfcuts);
6339 assert(varsolvals !=
NULL);
6340 assert(result !=
NULL);
6344 if( mod2data->nrows == 0 || mod2data->nrowsind == 0 )
6348 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
6351 if( mod2data->nrowsind == 1 )
6354 normtype, maxsepacuts, maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts,
6355 varsolvals, result, 1));
6359 identsubmatrixsize = 0;
6364 for( pivotcol = 0; pivotcol < mod2data->ncolsind; ++pivotcol )
6366 if( identsubmatrixsize == mod2data->nrowsind )
6370 SCIPsortInd(mod2data->rowsind + identsubmatrixsize , compRealNonDecreasing ,
6371 (
void*) mod2data->slacks , mod2data->nrowsind - identsubmatrixsize);
6374 if(
SCIPisGT(scip, mod2data->slacks[mod2data->rowsind[identsubmatrixsize]], sepadata->maxslack) )
6380 for( pivotrow = identsubmatrixsize ; pivotrow < mod2data->nrowsind ; ++pivotrow)
6381 if( mod2data->rows[mod2data->rowsind[pivotrow]][rowsbind] & rowsbmask )
6383 if( pivotrow == mod2data->nrowsind )
6387 for( r = 0 ; r < mod2data->nrowsind
6388 &&
SCIPisLE(scip, mod2data->slacks[mod2data->rowsind[r]], sepadata->maxslack) ; ++r)
6392 if( mod2data->rows[mod2data->rowsind[r]][rowsbind] & rowsbmask )
6395 mod2data->slacks[mod2data->rowsind[r]] += mod2data->slacks[mod2data->rowsind[pivotrow]];
6399 if(
SCIPisLE(scip, mod2data->slacks[mod2data->rowsind[r]], sepadata->maxslack) )
6402 BITARRAYSXOR(mod2data->rows[mod2data->rowsind[pivotrow]],
6403 mod2data->rows[mod2data->rowsind[r]],mod2data->rowsbitarraysize);
6404 BITARRAYSXOR(mod2data->rowaggregations[mod2data->rowsind[pivotrow]],
6405 mod2data->rowaggregations[mod2data->rowsind[r]],mod2data->rowaggregationsbitarraysize);
6406 mod2data->rhs[mod2data->rowsind[r]] =
6407 XOR(mod2data->rhs[mod2data->rowsind[pivotrow]],mod2data->rhs[mod2data->rowsind[r]]);
6413 temp = mod2data->rowsind[pivotrow];
6414 mod2data->rowsind[pivotrow] = mod2data->rowsind[identsubmatrixsize];
6415 mod2data->rowsind[identsubmatrixsize] = temp;
6416 temp = mod2data->colsind[pivotcol];
6417 mod2data->colsind[pivotcol] = mod2data->colsind[identsubmatrixsize];
6418 mod2data->colsind[identsubmatrixsize] = temp;
6420 identsubmatrixsize++;
6433 0, mod2data->nrowsind, normtype, maxsepacuts, maxcuts, nsepacuts,
6463 #ifdef ZEROHALF__PRINT_STATISTICS 6464 int nsepacutsbefore;
6465 int nsepacutsinitial;
6466 int nzerohalfcutsbefore;
6467 int nzerohalfcutsinitial;
6472 int ncutsfoundbefore;
6475 assert(scip !=
NULL);
6476 assert(sepadata !=
NULL);
6477 assert(lpdata !=
NULL);
6478 assert(mod2data !=
NULL);
6479 assert(maxsepacuts >= 0);
6480 assert(maxcuts >= 0);
6481 assert(result !=
NULL);
6482 assert(nsepacuts !=
NULL);
6483 assert(nzerohalfcuts !=
NULL);
6484 assert(zerohalfcuts !=
NULL);
6485 assert(*nsepacuts <= *nzerohalfcuts);
6487 assert(mod2data->relatedsubproblem !=
NULL);
6488 assert(mod2data->rows !=
NULL);
6489 assert(mod2data->rowaggregations !=
NULL);
6490 assert(mod2data->rhs !=
NULL);
6491 assert(mod2data->slacks !=
NULL);
6492 assert(mod2data->fracsol !=
NULL);
6493 assert(mod2data->nrows > 0);
6494 assert(mod2data->rowsind !=
NULL);
6495 assert(mod2data->colsind !=
NULL);
6497 sepadata->nsepamethods = (int) strlen(sepadata->sepamethods);
6498 if( sepadata->nsepamethods > 0 && sepadata->sepamethods[0] ==
'-' )
6499 sepadata->nsepamethods = 0;
6501 if( sepadata->nsepamethods == 0 )
6506 #ifdef ZEROHALF__PRINT_STATISTICS 6507 if( sepadata->sepatimers ==
NULL )
6510 for( i = 0 ; i < sepadata->nsepamethods + 1 ; ++i)
6512 ZEROHALFcreateTimer((sepadata->sepatimers[i]));
6520 nsepacutsinitial = *nsepacuts;
6521 nzerohalfcutsinitial = *nzerohalfcuts;
6523 ZEROHALFstatisticsMessage(
"\n");
6524 ZEROHALFstatisticsMessage(
" | -------------------------- subproblem ----\ 6525 ---------- | - callback (algo) - | ----- callback ---- | --total-\n");
6526 ZEROHALFstatisticsMessage(
" | nrowsind | ncolsind | nsepcuts | ncutsfnd \ 6527 | time | nsepcuts | ncutsfnd | nsepcuts | ncutsfnd | time\n");
6528 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8.4f | %8s | %8s | %8d | %8d | %8.4f\n",
6529 "START PROCESSG", mod2data->nrowsind, mod2data->ncolsind,
6530 0, 0, 0.0,
" ",
" ", *nsepacuts, *nzerohalfcuts, ZEROHALFevalTimer(sepadata->sepatimers[sepadata->nsepamethods]));
6533 if( mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
6536 #ifdef ZEROHALF__PRINT_STATISTICS 6537 ZEROHALFcreateNewTimer(timer);
6538 ZEROHALFcreateNewTimer(sepatimer);
6539 ZEROHALFstartTimer(sepadata->sepatimers[sepadata->nsepamethods]);
6540 ZEROHALFstartTimer(timer);
6544 for( i = 0 ; i < sepadata->nsepamethods && !stop; ++i)
6547 #ifdef ZEROHALF__PRINT_STATISTICS 6548 ZEROHALFstartTimer(sepatimer);
6549 ZEROHALFstartTimer(sepadata->sepatimers[i]);
6550 nsepacutsbefore = *nsepacuts;
6551 nzerohalfcutsbefore = *nzerohalfcuts;
6554 if( *nsepacuts >= maxsepacuts || *nzerohalfcuts >= maxcuts )
6557 if( mod2data->nrowsind == 0 || mod2data->ncolsind == 0 )
6562 sepamethod = sepadata->sepamethods[i];
6567 if( *nsepacuts > 0 )
6575 ncutsfoundbefore = *nzerohalfcuts;
6578 nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result));
6580 if( *nzerohalfcuts == ncutsfoundbefore )
6588 maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result, 1));
6593 maxcuts, nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result, 2));
6598 nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result));
6602 ncutsfoundbefore = *nzerohalfcuts;
6604 nsepacuts, nzerohalfcuts, zerohalfcuts, varsolvals, result, &wrongstructure));
6606 if( ! wrongstructure )
6608 if( *nzerohalfcuts == ncutsfoundbefore )
6620 #ifdef ZEROHALF__PRINT_STATISTICS 6622 ZEROHALFstopTimer(sepadata->sepatimers[i]);
6623 ZEROHALFstopTimer(sepatimer);
6624 sepadata->nsepacutsalgo[i] += *nsepacuts - nsepacutsbefore;
6625 sepadata->nzerohalfcutsalgo[i] += *nzerohalfcuts - nzerohalfcutsbefore;
6626 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8.4f | %8d | %8d | %8d | %8d | %8.4f\n",
6627 sepaname, mod2data->nrowsind, mod2data->ncolsind,
6628 *nsepacuts - nsepacutsbefore, *nzerohalfcuts - nzerohalfcutsbefore,
6629 ZEROHALFevalTimer(sepatimer),
6630 sepadata->nsepacutsalgo[i], sepadata->nzerohalfcutsalgo[i],
6631 *nsepacuts, *nzerohalfcuts, ZEROHALFevalTimer(sepadata->sepatimers[i]));
6632 ZEROHALFresetTimer(sepatimer);
6636 #ifdef ZEROHALF__PRINT_STATISTICS 6638 ZEROHALFstopTimer(timer);
6639 ZEROHALFstatisticsMessage(
"%15s | %8d | %8d | %8d | %8d | %8.4f | %8s | %8s | %8d | %8d | %8.4f\n",
6640 "PROCESSED", mod2data->nrowsind, mod2data->ncolsind,
6641 *nsepacuts - nsepacutsinitial , *nzerohalfcuts - nzerohalfcutsinitial,
6642 ZEROHALFevalTimer(timer),
" ",
" ", *nsepacuts, *nzerohalfcuts,
6643 ZEROHALFevalTimer(sepadata->sepatimers[sepadata->nsepamethods]));
6644 ZEROHALFfreeTimer(timer);
6645 ZEROHALFfreeTimer(sepatimer);
6646 ZEROHALFstopTimer(sepadata->sepatimers[sepadata->nsepamethods]);
6653 #ifdef ZEROHALF__PRINT_STATISTICS 6656 void printZerohalfCutsStatistics(
6660 int* zerohalfcutsindices,
6670 assert(scip !=
NULL);
6671 assert(zerohalfcuts !=
NULL);
6672 assert(nzerohalfcuts >= 0);
6674 ZEROHALFstatisticsMessage(
"\n");
6675 ZEROHALFstatisticsMessage(
" NZEROHALFCUTS: %6d\n", nzerohalfcuts);
6676 ZEROHALFstatisticsMessage(
" NSEPACUTS: %6d\n", nsepacuts);
6678 if( nzerohalfcuts == 0 )
6681 ZEROHALFstatisticsMessage(
"%15s | index | A | viol | efficacy | ef? \ 6682 | minortho | #nonz | norm | #origrows | #preprows | by | priority\n",
" ");
6683 for( i = 0 ; i < nzerohalfcuts ; ++i)
6685 if( zerohalfcutsindices ==
NULL )
6688 si = zerohalfcutsindices[i];
6690 assert(i < nzerohalfcuts);
6691 cut = zerohalfcuts[si];
6692 ZEROHALFstatisticsMessage(
"%15s | %6d | %1s | %8f | %8f | %3s | %8f | %8d | %8.2f | %9d | %9d | %2s | %8.6f\n",
6694 cut->addedtolp ?
"A" :
"-",
6695 cut->violation, cut->efficacy,
6697 zerohalfcutsminortho !=
NULL ? zerohalfcutsminortho[i] : 0.0,
6698 cut->nnonz, cut->norm, cut->nrowsincut, cut->nrrowsincut,
6699 (cut->separatedby ==
AUXIP ?
"IP" :
6704 (cut->separatedby ==
AUXGRAPH ?
"2R" :
6707 zerohalfcutsprios !=
NULL ? zerohalfcutsprios[i] : 0.0
6724 assert(scip !=
NULL);
6725 assert(sepa !=
NULL);
6744 assert(sepadata !=
NULL);
6746 if( sepadata->pptimers !=
NULL )
6748 #ifdef ZEROHALF__PRINT_STATISTICS 6751 for( i = 0; i <= sepadata->nppmethods; ++i)
6753 ZEROHALFfreeTimer((sepadata->pptimers[i]));
6759 if( sepadata->sepatimers !=
NULL )
6761 #ifdef ZEROHALF__PRINT_STATISTICS 6764 for( i = 0 ; i <= sepadata->nsepamethods; ++i)
6766 ZEROHALFfreeTimer((sepadata->sepatimers[i]));
6772 #ifdef ZEROHALF__PRINT_STATISTICS 6773 if( sepadata->dtimer !=
NULL )
6775 ZEROHALFfreeTimer(sepadata->dtimer);
6799 int* sortedsubproblems;
6806 int subproblemindex;
6814 assert(sepa !=
NULL);
6816 assert(scip !=
NULL);
6817 assert(result !=
NULL);
6821 assert(sepadata !=
NULL);
6831 if( sepadata->maxncalls > -1 && totalncalls > sepadata->maxncalls - 1 )
6835 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
6836 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
6840 if( sepadata->maxdepth > -1 && depth > sepadata->maxdepth )
6860 if( lpdata->ncols == 0 || lpdata->nrows == 0 )
6867 if( sepadata->onlyorigrows && sepadata->origrows ==
NULL )
6873 for( i = 0; i < lpdata->nrows; ++i )
6875 sepadata->norigrows = lpdata->nrows;
6881 for( i = 0; i < sepadata->norigrows - 1; ++i )
6883 if( sepadata->origrows[i] > sepadata->origrows[i+1] )
6885 temp = sepadata->origrows[i];
6886 sepadata->origrows[i] = sepadata->origrows[i+1];
6887 sepadata->origrows[i+1] = temp;
6898 maxcuts = sepadata->maxcutsroot;
6899 maxsepacuts =
MIN(maxcuts, sepadata->maxsepacutsroot);
6903 maxcuts = sepadata->maxcuts;
6904 maxsepacuts =
MIN(maxcuts, sepadata->maxsepacuts);
6908 if( maxsepacuts == 0 )
6915 #ifdef ZEROHALF__PRINT_STATISTICS 6916 ZEROHALFstatisticsMessage(
"= SEPA_ZEROHALF ================================================================\ 6917 s=============================================\n");
6929 sepadata->maxslack = 1.0 - 2.0 * sepadata->minviolation;
6935 #ifdef ZEROHALF__PRINT_STATISTICS 6936 if( sepadata->nsepamethods > 0 )
6938 assert(sepadata->nsepacutsalgo !=
NULL);
6939 assert(sepadata->nzerohalfcutsalgo !=
NULL);
6946 sepadata->maxnnonz = 0;
6947 for( i = 0 ; i < lpdata->nrows ; i++ )
6951 sepadata->maxnnonz = (int) floor( 10.0 * sepadata->maxnnonz / (
double) lpdata->nrows);
6952 sepadata->maxnnonz = (int) floor(
MIN(0.1 * lpdata->ncols, sepadata->maxnnonz)) +
NNONZOFFSET;
6956 if( lpdata->subproblems[0]->nrcols == 0 )
6964 if( lpdata->subproblems[0]->nrrows == 0 )
6970 #ifdef ZEROHALF__PRINT_STATISTICS 6971 SCIP_CALL( printPreprocessingStatistics(scip, lpdata) );
6975 if( sepadata->decomposeproblem )
6983 nrcolsfactor = 1.0 / (2.0 * lpdata->ncols);
6984 for( i = 0 ; i < lpdata->nsubproblems; ++i)
6986 sortedsubproblems[i] = i;
6987 subproblempriorities[i] = ((
SCIP_Real) lpdata->subproblems[i]->nrrows)
6988 + nrcolsfactor * ((
SCIP_Real) lpdata->subproblems[i]->nrcols);
6990 SCIPsortRealInt(subproblempriorities, sortedsubproblems, lpdata->nsubproblems);
6996 for( i = 0; i < lpdata->nsubproblems; ++i )
6999 if( nsepacuts >= maxsepacuts || nzerohalfcuts >= maxcuts )
7002 subproblemindex = sortedsubproblems[i];
7003 sepadata->maxslack = 1.0 - 2.0 * sepadata->minviolation;
7008 if( lpdata->subproblems[subproblemindex]->nrrows == 1 && lpdata->subproblems[subproblemindex]->nrcols == 0 )
7013 SCIP_CALL( debugPrintLPRowsAndCols(scip, lpdata) );
7015 debugPrintSubLpData(scip, lpdata, lpdata->subproblems[subproblemindex]);
7022 if( weights ==
NULL )
7029 lpdata, weights, normtype, nzerohalfcuts, &varsolvals, zerohalfcuts[nzerohalfcuts], &cutoff) );
7046 if( lpdata->rrowsindexofleftrow[lpdata->subproblems[subproblemindex]->rrows[0]] >= 0 )
7047 lpdata->rrowsindexofleftrow[lpdata->subproblems[subproblemindex]->rrows[0]] =
7050 if( lpdata->rrowsindexofrightrow[lpdata->subproblems[subproblemindex]->rrows[0]] >= 0 )
7051 lpdata->rrowsindexofrightrow[lpdata->subproblems[subproblemindex]->rrows[0]] =
7059 if( nsepacuts >= maxsepacuts || nzerohalfcuts >= maxcuts )
7069 SCIP_CALL(
preprocess(scip, sepa, sepadata, lpdata, mod2data, normtype, maxsepacuts, maxcuts,
7070 &nsepacuts, &nzerohalfcuts, zerohalfcuts, &varsolvals, result) );
7072 if( nsepacuts < maxsepacuts || nzerohalfcuts < maxcuts )
7075 SCIP_CALL(
process(scip, sepa, sepadata, lpdata, mod2data, normtype, maxsepacuts, maxcuts,
7076 &nsepacuts, &nzerohalfcuts, zerohalfcuts, &varsolvals, result) );
7083 for( j = 0 ; j < nzerohalfcuts ; ++j)
7084 zerohalfcuts[j]->relatedmod2data =
NULL;
7087 #ifdef ZEROHALF__PRINT_STATISTICS 7088 if( !sepadata->usezhcutpool )
7089 printZerohalfCutsStatistics(scip, zerohalfcuts, nzerohalfcuts,
NULL,
NULL,
NULL, nsepacuts);
7092 if( ! cutoff && sepadata->usezhcutpool )
7098 int* sortedzerohalfcuts;
7111 violationbucketsize = 10.0;
7116 for( i = 0 ; i < nzerohalfcuts; ++i)
7118 sortedzerohalfcuts[i] = i;
7119 zerohalfcutpriorities[i] =
SCIPfloor(scip, violationbucketsize * (zerohalfcuts[i])->violation)
7125 for( si = 0; si < nzerohalfcuts; ++si )
7127 cutdatai = zerohalfcuts[sortedzerohalfcuts[si]];
7128 if( cutdatai->cut ==
NULL || !cutdatai->addedtolp )
7130 hasminorthogonality =
TRUE;
7131 for( sj = 0; hasminorthogonality && sj < si; ++sj )
7133 cutdataj = zerohalfcuts[sortedzerohalfcuts[sj]];
7134 if( cutdataj->cut !=
NULL && cutdataj->addedtolp )
7137 hasminorthogonality =
FALSE;
7141 if( hasminorthogonality && cutdatai->addedtolp )
7144 if( sepadata->delayedcuts && !cutdatai->islocal )
7156 if( !cutdatai->islocal )
7160 cutdatai->addedtolp =
TRUE;
7165 cutdatai->addedtolp =
FALSE;
7169 nsepacuts -= nignoredcuts;
7171 #ifdef ZEROHALF__PRINT_STATISTICS 7172 printZerohalfCutsStatistics(scip, zerohalfcuts, nzerohalfcuts, sortedzerohalfcuts,
7173 zerohalfcutpriorities,
NULL, nsepacuts);
7183 for( i = 0 ; i < nzerohalfcuts; ++i )
7185 cutdatai = zerohalfcuts[i];
7187 if( cutdatai->cut ==
NULL || !cutdatai->addedtolp )
7190 sortedzerohalfcuts[ncutpool] = i;
7191 zerohalfcutminortho[ncutpool] = 1.0;
7192 zerohalfcutpriorities[ncutpool] =
SCIPfloor(scip, violationbucketsize * cutdatai->efficacy)
7194 +
SCIPfloor(scip, violationbucketsize * zerohalfcutminortho[ncutpool]);
7198 ncutpoolold = ncutpool;
7201 while( ncutpool > 0 )
7210 assert(cutdatai->addedtolp);
7216 for( i = 0; i < ncutpool; i++ )
7219 if( zerohalfcutpriorities[i] > bestscore )
7221 bestscore = zerohalfcutpriorities[i];
7226 cutdatai = zerohalfcuts[sortedzerohalfcuts[bestpos]];
7235 if( !cutdatai->islocal )
7240 priotmp = zerohalfcutpriorities[bestpos];
7241 minorthotmp = zerohalfcutminortho[bestpos];
7242 sortidxtmp = sortedzerohalfcuts[bestpos];
7245 zerohalfcutpriorities[bestpos] = zerohalfcutpriorities[ncutpool-1];
7246 zerohalfcutminortho[bestpos] = zerohalfcutminortho[ncutpool-1];
7247 sortedzerohalfcuts[bestpos] = sortedzerohalfcuts[ncutpool-1];
7251 zerohalfcutpriorities[ncutpool] = priotmp;
7252 zerohalfcutminortho[ncutpool] = minorthotmp;
7253 sortedzerohalfcuts[ncutpool] = sortidxtmp;
7257 while( j < ncutpool )
7261 cutdataj = zerohalfcuts[sortedzerohalfcuts[j]];
7266 priotmp = zerohalfcutpriorities[j];
7267 minorthotmp = zerohalfcutminortho[j];
7268 sortidxtmp = sortedzerohalfcuts[j];
7271 zerohalfcutpriorities[j] = zerohalfcutpriorities[ncutpool-1];
7272 zerohalfcutminortho[j] = zerohalfcutminortho[ncutpool-1];
7273 sortedzerohalfcuts[j] = sortedzerohalfcuts[ncutpool-1];
7274 cutdataj->addedtolp =
FALSE;
7279 zerohalfcutpriorities[ncutpool] = priotmp;
7280 zerohalfcutminortho[ncutpool] = minorthotmp;
7281 sortedzerohalfcuts[ncutpool] = sortidxtmp;
7286 if( thisortho < zerohalfcutminortho[j] )
7288 zerohalfcutminortho[j] = thisortho;
7289 zerohalfcutpriorities[j] =
SCIPfloor(scip, violationbucketsize * cutdataj->efficacy)
7291 +
SCIPfloor(scip, violationbucketsize * zerohalfcutminortho[j]);
7297 nsepacuts -= nignoredcuts;
7299 #ifdef ZEROHALF__PRINT_STATISTICS 7300 printZerohalfCutsStatistics(scip, zerohalfcuts, ncutpoolold, sortedzerohalfcuts,
7301 zerohalfcutpriorities, zerohalfcutminortho, nsepacuts);
7312 sepadata->totalncutsfound += nzerohalfcuts;
7313 sepadata->totalnsepacuts += nsepacuts;
7318 for( i = 0 ; i < nzerohalfcuts ; ++i)
7351 ncharsprinted =
SCIPmemccpy(preprocessingmethodsdescription,
7352 "preprocessing methods and ordering:\n" 7353 " # 'd' columns with small LP solution,\n" 7354 " # 'G' modified Gaussian elimination,\n" 7355 " # 'i' identical columns,\n" 7356 " # 'I' identical rows,\n" 7357 " # 'L' large slack rows,\n" 7358 " # 'M' large slack rows (minslack),\n" 7363 ncharsprinted +=
SCIPmemccpy(&(preprocessingmethodsdescription[ncharsprinted - 1]),
7364 " # 'X' add trivial zerohalf cuts,\n" 7365 " # 'z' zero columns,\n" 7366 " # 'Z' zero rows,\n" 7367 " # 'C' fast {'z','s'},\n" 7368 " # 'R' fast {'Z','L','I'}\n" 7370 " # '-' no preprocessing\n" 7371 " #",
'\0', (
unsigned int) (
SCIP_MAXSTRLEN - ncharsprinted - 1));
7375 ncharsprinted =
SCIPmemccpy(sepamethodsdescription,
7376 "separating methods and ordering:\n" 7377 " # '!' stop further processing if a cut was found,\n" 7378 " # '2' exact polynomial time algorithm (only if matrix has max 2 odd entries per row),\n" 7379 " # 'e' enumeration heuristics (k=1: try all preprocessed rows),\n" 7380 " # 'E' enumeration heuristics (k=2: try all combinations of up to two preprocessed rows),\n" 7381 " # 'g' Extended Gaussian elimination heuristics,\n",
'\0',
SCIP_MAXSTRLEN - 1);
7385 ncharsprinted +=
SCIPmemccpy(&(sepamethodsdescription[ncharsprinted - 1]),
7386 " # 's' auxiliary IP heuristics (i.e. number of solved nodes is limited)\n" 7387 " # 'S' auxiliary IP exact (i.e. unlimited number of nodes)\n" 7389 " # '-' no processing\n" 7390 " #",
'\0', (
unsigned int) (
SCIP_MAXSTRLEN - ncharsprinted - 1));
7394 ncharsprinted =
SCIPmemccpy(subscipobjectivedescription,
7395 "auxiliary IP objective:\n" 7396 " # 'v' maximize cut violation,\n" 7397 " # 'u' minimize number of aggregated rows in cut,\n" 7398 " # 'w' minimize number of aggregated rows in cut\n" 7399 " # weighted by the number of rows in the aggregation,\n",
'\0',
SCIP_MAXSTRLEN - 1);
7403 ncharsprinted +=
SCIPmemccpy(&(subscipobjectivedescription[ncharsprinted - 1]),
7404 " # 'p' maximize cut violation and penalize a high number\n" 7405 " # of aggregated rows in the cut weighted by the number\n" 7406 " # of rows in the aggregation and the penalty factor p\n" 7407 " #",
'\0', (
unsigned int) (
SCIP_MAXSTRLEN - ncharsprinted - 1));
7415 sepadata->totalncutsfound = 0;
7416 sepadata->totalnsepacuts = 0;
7417 sepadata->pptimers =
NULL;
7418 sepadata->dtimer =
NULL;
7419 sepadata->sepatimers =
NULL;
7420 sepadata->nsepacutsalgo =
NULL;
7421 sepadata->nzerohalfcutsalgo =
NULL;
7423 sepadata->ppmethods =
NULL;
7424 sepadata->sepamethods =
NULL;
7425 sepadata->nppmethods = -1;
7426 sepadata->nsepamethods = -1;
7427 sepadata->subscipsettings =
NULL;
7429 sepadata->norigrows = 0;
7430 sepadata->origrows =
NULL;
7435 sepaExeclpZerohalf,
NULL,
7438 assert(sepa !=
NULL);
7446 "separating/zerohalf/maxrounds",
7447 "maximal number of zerohalf separation rounds per node (-1: unlimited)",
7450 "separating/zerohalf/maxroundsroot",
7451 "maximal number of zerohalf separation rounds in the root node (-1: unlimited)",
7454 "separating/zerohalf/maxsepacuts",
7455 "maximal number of {0,1/2}-cuts separated per separation round",
7458 "separating/zerohalf/maxsepacutsroot",
7459 "maximal number of {0,1/2}-cuts separated per separation round in the root node",
7462 "separating/zerohalf/dynamiccuts",
7463 "should generated cuts be removed from the LP if they are no longer tight?",
7468 "separating/zerohalf/maxcutsfound",
7469 "maximal number of {0,1/2}-cuts determined per separation round\n\ 7470 # (this includes separated but inefficacious cuts)",
7473 "separating/zerohalf/maxcutsfoundroot",
7474 "maximal number of {0,1/2}-cuts determined per separation round in the root node\n\ 7475 # (this includes separated but inefficacious cuts)",
7480 "separating/zerohalf/maxdepth",
7481 "separating cuts only if depth <= maxdepth (-1: unlimited)",
7484 "separating/zerohalf/maxncalls",
7485 "maximal number of calls (-1: unlimited)",
7488 "separating/zerohalf/relaxcontvars",
7489 "should continuous variables be relaxed by adding variable bounds?",
7492 "separating/zerohalf/scalefraccoeffs",
7493 "should rows be scaled to make fractional coefficients integer?",
7496 "separating/zerohalf/ignoreprevzhcuts",
7497 "should zerohalf cuts found in previous callbacks ignored?",
7500 "separating/zerohalf/onlyorigrows",
7501 "should only original LP rows be considered (i.e. ignore previously added LP rows)?",
7505 "separating/zerohalf/usezhcutpool",
7506 "should zerohalf cuts be filtered using a cutpool?",
7509 "separating/zerohalf/delayedcuts",
7510 "should cuts be added to the delayed cut pool?",
7513 "separating/zerohalf/maxtestdelta",
7514 "maximal number of different deltas to try for cmir (-1: unlimited, 0: delta=1)",
7517 "separating/zerohalf/trynegscaling",
7518 "should negative values also be tested in scaling for cmir?",
7523 "separating/zerohalf/preprocessing/decomposeproblem",
7524 "should problem be decomposed into subproblems (if possible) before applying preprocessing?",
7527 "separating/zerohalf/preprocessing/delta",
7528 "value of delta parameter used in preprocessing method 'd'",
7531 "separating/zerohalf/preprocessing/ppmethods",
7532 preprocessingmethodsdescription,
7538 "separating/zerohalf/separating/forcecutstolp",
7539 "should the cuts be forced to enter the LP?",
7542 "separating/zerohalf/separating/forcecutstosepastore",
7543 "should the cuts be forced to enter SCIP's sepastore?",
7546 "separating/zerohalf/separating/minviolation",
7547 "minimal violation of a {0,1/2}-cut to be separated",
7550 "separating/zerohalf/separating/sepamethods",
7551 sepamethodsdescription,
7557 "separating/zerohalf/separating/auxip/settingsfile",
7558 "optional settings file of the auxiliary IP (-: none)",
7561 "separating/zerohalf/separating/auxip/sollimit",
7562 "limits/solutions setting of the auxiliary IP",
7565 "separating/zerohalf/separating/auxip/penaltyfactor",
7566 "penalty factor used with objective function 'p' of auxiliary IP",
7569 "separating/zerohalf/separating/auxip/useallsols",
7570 "should all (proper) solutions of the auxiliary IP be used to generate cuts instead of using only the best?",
7573 "separating/zerohalf/separating/auxip/objective",
7574 subscipobjectivedescription,
enum SCIP_Result SCIP_RESULT
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPprintBestSol(SCIP *scip, FILE *file, SCIP_Bool printzeros)
static SCIP_RETCODE ZerohalfMod2DataFree(SCIP *scip, ZEROHALF_MOD2DATA **mod2data)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_SCALEFRACCOEFFS
static SCIP_RETCODE preprocessConsiderMinSlack(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, SCIP_Bool removelargeslackrows, SCIP_Bool removelargecolrows)
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
static SCIP_RETCODE ZerohalfAuxGraphNodeCreate(SCIP *scip, ZEROHALF_AUXGRAPH_NODE **node)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Real SCIPfeastol(SCIP *scip)
#define DEFAULT_SUBSCIPSOLLIMIT
int SCIPmemccpy(char *dest, const char *src, char stop, unsigned int cnt)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
static SCIP_RETCODE ZerohalfSubLPDataCreate(SCIP *scip, ZEROHALF_SUBLPDATA **subproblem)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA
SCIP_STAGE SCIPgetStage(SCIP *scip)
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
int SCIPvarGetNVlbs(SCIP_VAR *var)
#define ISEVEN(scip, value)
#define ISODD(scip, value)
#define DEFAULT_RELAXCONTVARS
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
#define IDENT_TO_ROW_WITH_SMALLER_SLACK
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)
#define DEFAULT_MAXCUTSROOT
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#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)
const char * SCIProwGetName(SCIP_ROW *row)
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
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, 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)
#define BITARRAYCLEAR(barray, barraysize)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
#define DEFAULT_SEPAMETHODS
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 SCIPcolGetUb(SCIP_COL *col)
#define BITARRAYBITISSET(barray, pos)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
#define SLACK_GREATER_THAN_MSL_MINUS_SODD
int SCIPvarGetNVubs(SCIP_VAR *var)
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)
#define BRANCHPRIORITY__PREFER_BRANCHING
int SCIPvarGetProbindex(SCIP_VAR *var)
static SCIP_RETCODE getRelevantColumns(SCIP *scip, ZEROHALF_LPDATA *lpdata)
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 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)
#define SCIPfreeBlockMemory(scip, ptr)
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)
#define BITARRAYBITMASKTYPE
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
static SCIP_DECL_SORTINDCOMP(compRealNonDecreasing)
static const unsigned int Zerohalf_bitarraybasetypesize_nbits
enum cutseparatedby CUTSEPARATEDBY
#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)
#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)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcreate(SCIP **scip)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
#define SCIPdebugMsgPrint
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_MAXROUNDSROOT
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
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)
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 GETREQUIREDBITARRAYSIZE(nvalstostore)
#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)
static void ZerohalfSubLPDataFree(SCIP *scip, ZEROHALF_SUBLPDATA **subproblem)
SCIP_Real SCIProwGetSumNorm(SCIP_ROW *row)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_RETCODE SCIPsolve(SCIP *scip)
static SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
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)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE getRelevantRows(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
#define DEFAULT_DECOMPOSEPROBLEM
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
#define DEFAULT_IGNOREPREVIOUSZHCUTS
#define BMSmoveMemoryArray(ptr, source, num)
#define SCIPfreeBufferArrayNull(scip, ptr)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
static SCIP_RETCODE addEdgeToAuxGraph(SCIP *scip, ZEROHALF_AUXGRAPH *graph, int node1index, int node2index, SCIP_Bool isodd, SCIP_Real weight, int relatedrow)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
const char * SCIPvarGetName(SCIP_VAR *var)
static void markColAsRemovedAndClearCol(ZEROHALF_MOD2DATA *mod2data, int c, int flag)
static SCIP_RETCODE preprocessIdenticalColums(SCIP *scip, ZEROHALF_MOD2DATA *mod2data)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE preprocessColumnsWithSmallFracsol(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_MOD2DATA *mod2data, SCIP_Real delta)
SCIP_RETCODE SCIPprintOrigProblem(SCIP *scip, FILE *file, const char *extension, SCIP_Bool genericnames)
#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)
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)
#define BRANCHPRIORITY__AVOID_BRANCHING
static SCIP_Real calcObjWeight(BITARRAY rowaggregation, int nrrows)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_PPMETHODS
static SCIP_RETCODE ZerohalfAuxGraphCreate(SCIP *scip, ZEROHALF_AUXGRAPH **auxgraph)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
#define NO_RELEVANT_COLUMNS
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
static SCIP_RETCODE ZerohalfAuxIPDataFree(SCIP *scip, ZEROHALF_AUXIPDATA **auxipdata)
static SCIP_RETCODE decomposeProblem(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
#define GETBITARRAYMASK(pos)
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_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)
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
#define SMALL_FRACSOL_HEUR
#define DEFAULT_MINVIOLATION
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
static SCIP_RETCODE ZerohalfAuxIPDataCreate(SCIP *scip, ZEROHALF_AUXIPDATA **auxipdata)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
static const unsigned int Zerohalf_bitarraybasetypesize
static void markRowAsRemoved(ZEROHALF_MOD2DATA *mod2data, int r, int flag)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
#define BITARRAYBITSET(barray, pos)
int SCIPgetDepth(SCIP *scip)
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)
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_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
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)
struct Zerohalf_CutData ZEROHALF_CUTDATA
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
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 BITARRAYSAREEQUAL(barray1, barray2, size)
int SCIPgetNSols(SCIP *scip)
#define SLACK_GREATER_THAN_MAXSLACK
#define ALL_MATRIX_ROWS_DELETED
#define BMScopyMemoryArray(ptr, source, num)
SCIP_RETCODE SCIPchgVarBranchPriority(SCIP *scip, SCIP_VAR *var, int branchpriority)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE ZerohalfMod2DataCreate(SCIP *scip, ZEROHALF_MOD2DATA **mod2data)
static SCIP_RETCODE ZerohalfAuxGraphNodeFree(SCIP *scip, ZEROHALF_AUXGRAPH *graph, ZEROHALF_AUXGRAPH_NODE **node)
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)
#define LP_SOL_EQUALS_ODD_LB
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
#define XOR(bool1, bool2)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
int SCIPcolGetNNonz(SCIP_COL *col)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_SUBSCIPOBJECTIVE
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
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)
#define DEFAULT_DYNAMICCUTS
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
#define LP_SOL_EQUALS_ODD_UB
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_RETCODE SCIPreadParams(SCIP *scip, const char *filename)
static SCIP_RETCODE getZerohalfWeightvectorFromSelectedRowsBitarray(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, BITARRAY rrowsincut, SCIP_Real **weights, int *nrowsincut)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE calcInnerProductOfRowAndFracsol(SCIP *scip, ZEROHALF_MOD2DATA *mod2data, BITARRAY row, SCIP_Real maxinnerproduct, SCIP_Real *innerproduct)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
enum SCIP_Stage SCIP_STAGE
SCIP_Bool SCIPisStopped(SCIP *scip)
#define DEFAULT_MAXROUNDS
#define DEFAULT_MAXNCALLS
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
#define DEFAULT_USEZHCUTPOOL
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)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIProwGetIndex(SCIP_ROW *row)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define LP_SOL_EQUALS_EVEN_LB
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
static SCIP_RETCODE storeMod2Data(SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, int subproblemindex, ZEROHALF_MOD2DATA *mod2data)
#define GETBITARRAYINDEX(pos)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
#define DEFAULT_TRYNEGSCALING
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
#define DEFINES_VIOLATED_ZEROHALF_CUT
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define DEFAULT_ONLYORIGROWS
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_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
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)
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
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_DECL_SEPAFREE(sepaFreeZerohalf)
struct SCIP_SepaData SCIP_SEPADATA
SCIP_Real SCIProwGetOrthogonality(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
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)
#define DEFAULT_MAXSEPACUTSROOT
static SCIP_Bool hasMatrixMax2EntriesPerRow(ZEROHALF_MOD2DATA *mod2data)
SCIP_RETCODE SCIPfree(SCIP **scip)
#define DEFAULT_MAXTESTDELTA
static SCIP_DECL_SEPACOPY(sepaCopyZerohalf)