dec_hrgpartition.cpp
Go to the documentation of this file.
36 * This detector needs hmetis and works only under Linux/MacOS, it further needs the Z-shell (zsh)
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
84 #define DEC_DESC "enforces arrowhead structures using graph partitioning" /**< description of detector */
85 #define DEC_FREQCALLROUND 1 /**< frequency the detector gets called in detection loop ,ie it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0 */
88 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
89 #define DEC_MAXCALLROUNDORIGINAL 0 /**< last round the detector gets called while detecting the original problem */
90 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
97 #define DEC_USEFULRECALL TRUE /**< is it useful to call this detector on a descendant of the propagated partialdec */
110 #define DEFAULT_CONSWEIGHT_SETPPC 5 /**< weight for constraint hyperedges that are setpartitioning or covering
113 #define DEFAULT_LIMITNCONSSNVARSDEFAULT 10000 /**< limit for sum of nvars and nconss for enabling this detector in default */
114 #define DEFAULT_ENABLEDFORLARGEPROBLEMS FALSE /** should this detector be enabled even the limit nconssnvars is exceeded */
118 #define DEFAULT_MAXNBLOCKCANDIDATES 3 /**< number of block number candidates to be considered */
120 #define DEFAULT_BETA 0.5 /**< factor of how the weight for equality and inequality constraints is
122 #define DEFAULT_METIS_UBFACTOR 5.0 /**< default unbalance factor given to metis on the commandline */
124 #define DEFAULT_METISUSEPTYPE_RB TRUE /**< Should metis use the rb or kway partitioning algorithm */
126 #define DEFAULT_TYPE 'r' /**< type of the decomposition 'c' column hypergraph (single bordered, no
154 int limitnconssnvarsdefault; /**< limit for sum of nvars and nconss for enabling this detector in default*/
166 SCIP_Bool realname; /**< flag to indicate real problem name or temporary filename for metis files */
226 /** presolving deinitialization method of presolver (called after presolving has been finished) */
274 (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"ulimit -t %.0f;" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
285 (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
300 SCIPdebugMessage("time left before metis started: %f, time metis spend %f, remainingtime: %f\n", remainingtime, SCIPgetClockTime(scip, metisclock), remainingtime-SCIPgetClockTime(scip, metisclock) );
313 SCIPerrorMessage("Calling hmetis unsuccessful! See the above error message for more details.\n");
365 (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%c-%d.metis.XXXXXX", DEC_DECCHAR, partialdecID );
369 (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%s-%s-%c.metis.XXXXXX", SCIPgetProbName(scip), DEC_DECCHAR, partialdecID);
436 Partialdec_Detection_Data* partialdecdetectiondata, /**< partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs */
438 bool allowopenpartialdecs, /**< whether new partialdecs should be stored in which this detector only assignes conss to master */
469 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/hrgpartition/maxnblockcandidates");
487 Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
522 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], &newpartialdecs[j+1], partialdecdetectiondata->detprobdata));
526 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], NULL, partialdecdetectiondata->detprobdata));
562 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d partialdecs found.\n", nnewpartialdecs);
563 SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
568 partialdecdetectiondata->newpartialdecs[s]->addClockTime(clockTimes[s] + SCIPgetClockTime(scip, temporaryClock) / nnewpartialdecs);
601 SCIPgetBoolParam(scip, "detection/detectors/hrgpartition/enabledforlargeproblems", &enabledforlarge);
612 SCIPdebugMessage("Started propagate partialdec of detector %s and partial decomp %d \n", DEC_DETECTORNAME, partialdec->getID() );
635 detection(scip, DECdetectorGetData(detector), partialdecdetectiondata, partialdec, true, result);
678 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
684 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
695 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
721 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
727 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
738 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
755 if ( SCIPgetStage(scip) >= SCIP_STAGE_PROBLEM && SCIPgetNConss(scip) + SCIPgetNVars(scip) < 6000 )
765 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
771 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
782 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
805 SCIP_CALL( DECincludeDetector(scip, DEC_DETECTORNAME, DEC_DECCHAR, DEC_DESC, DEC_FREQCALLROUND, DEC_MAXCALLROUND, DEC_MINCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_ENABLED, DEC_ENABLEDFINISHING,DEC_ENABLEDPOSTPROCESSING, DEC_SKIP, DEC_USEFULRECALL, detectordata, freeHrgpartition, initHrgpartition, exitHrgpartition, propagatePartialdecHrgpartition, finishPartialdecHrgpartition, detectorPostprocessPartialdecHrgpartition, setParamAggressiveHrgpartition, setParamDefaultHrgpartition, setParamFastHrgpartition) );
807 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/limitnconssnvarsdefault", "Limit for sum of nvars and nconss for enabling this detector in default", &detectordata->limitnconssnvarsdefault, TRUE, DEFAULT_LIMITNCONSSNVARSDEFAULT, 0, INT_MAX, NULL, NULL) );
809 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/enabledforlargeproblems", "Should this detector be enabled even the limit nconssnvars is exceeded",&detectordata->enabledforlargeproblems, TRUE, DEFAULT_ENABLEDFORLARGEPROBLEMS, NULL, NULL) );
812 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/maxnblockcandidates", "The maximal number of block number candidates", &detectordata->maxnblockcandidates, FALSE, DEFAULT_MAXNBLOCKCANDIDATES, 0, 1000000, NULL, NULL) );
813 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/maxblocks", "The maximal number of blocks (detector is called for all block numbers in [minblocks,maxblocks])", &detectordata->maxblocks, FALSE, DEFAULT_MAXBLOCKS, 2, 1000000, NULL, NULL) );
814 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/minblocks", "The minimal number of blocks (detector is called for all block numbers in [minblocks,maxblocks])", &detectordata->minblocks, FALSE, DEFAULT_MINBLOCKS, 2, 1000000, NULL, NULL) );
815 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrgpartition/beta", "Factor on how heavy equality (beta) and inequality constraints are measured", &detectordata->beta, FALSE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL ) );
816 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrgpartition/alpha", "Factor on how heavy the standard deviation of the coefficients is measured", &detectordata->alpha, FALSE, DEFAULT_ALPHA, 0.0, 1E20, NULL, NULL ) );
817 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeight", "Weight of a variable hyperedge", &detectordata->varWeight, FALSE, DEFAULT_VARWEIGHT, 0, 1000000, NULL, NULL) );
818 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightBinary", "Weight of a binary variable hyperedge", &detectordata->varWeightBinary, FALSE, DEFAULT_VARWEIGHTBIN, 0, 1000000, NULL, NULL) );
819 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightContinous", "Weight of a continuos variable hyperedge", &detectordata->varWeightContinous, FALSE, DEFAULT_VARWEIGHTCONT, 0, 1000000, NULL, NULL) );
820 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightImplint", "Weight of a implicit integer variable hyperedge", &detectordata->varWeightImplint, FALSE, DEFAULT_VARWEIGHTIMPL, 0, 1000000, NULL, NULL) );
821 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightInteger", "Weight of a integer variable hyperedge", &detectordata->varWeightInteger, FALSE, DEFAULT_VARWEIGHTINT, 0, 1000000, NULL, NULL) );
822 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/consWeight", "Weight of a constraint hyperedge", &detectordata->consWeight, FALSE, DEFAULT_CONSWEIGHT, 0, 1000000, NULL, NULL) );
823 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/tidy", "Whether to clean up temporary files", &detectordata->tidy, FALSE, DEFAULT_TIDY, NULL, NULL) );
824 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/randomseed", "Random seed for hmetis", &detectordata->randomseed, FALSE, DEFAULT_RANDSEED, -1, INT_MAX, NULL, NULL) );
825 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrgpartition/dummynodes", "Percentage of dummy nodes for metis", &detectordata->dummynodes, FALSE, DEFAULT_DUMMYNODES, 0.0, 1.0, NULL, NULL) );
826 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/consWeightSetppc", "Weight for constraint hyperedges that are setpartitioning or covering constraints", &detectordata->consWeightSetppc, FALSE, DEFAULT_CONSWEIGHT_SETPPC, 0, 1000000, NULL, NULL) );
827 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrgpartition/ubfactor", "Unbalance factor for metis", &detectordata->metisubfactor, FALSE, DEFAULT_METIS_UBFACTOR, 0.0, 1E20, NULL, NULL ) );
828 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/metisverbose", "Should the metis output be displayed", &detectordata->metisverbose, FALSE, DEFAULT_METIS_VERBOSE, NULL, NULL ) );
829 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/metisuseptyperb", "Should the rb or kway method be used for partitioning by metis", &detectordata->metisuseptyperb, FALSE, DEFAULT_METISUSEPTYPE_RB, NULL, NULL) );
830 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/realname", "Should the problem be used for metis files or a temporary name", &detectordata->realname, FALSE, DEFAULT_REALNAME, NULL, NULL) );
static bool connected(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
Definition: dec_hrgpartition.cpp:381
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
Definition: class_partialdecomp.cpp:286
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
Definition: cons_decomp.cpp:2618
structure information for decomposition information in GCG projects
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4198
static SCIP_RETCODE createMetisFile(SCIP *scip, DEC_DETECTORDATA *detectordata, int partialdecID, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN])
Definition: dec_hrgpartition.cpp:346
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
miscellaneous matrixgraph methods for structure detection
static DEC_DECL_INITDETECTOR(initHrgpartition)
Definition: dec_hrgpartition.cpp:207
Definition: hyperrowgraph.h:48
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
Definition: class_partialdecomp.cpp:4721
weight class for graphs
void getSortedCandidatesNBlocks(std::vector< int > &candidates)
gets the candidates for number of blocks added by the user followed by the found ones sorted in desce...
Definition: class_detprobdata.cpp:886
Definition: weights.h:41
virtual SCIP_RETCODE writeToFile(int fd, SCIP_Bool writeweights)
Definition: matrixgraph.h:79
static SCIP_RETCODE callMetis(SCIP *scip, DEC_DETECTORDATA *detectordata, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN], int nblocks, SCIP_RESULT *result)
Definition: dec_hrgpartition.cpp:241
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec)
Definition: matrixgraph.h:146
std::vector< int > & getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
Definition: class_detprobdata.cpp:714
various SCIP helper methods
SCIP_Real DECgetRemainingTime(SCIP *scip)
returns the remaining time of scip that the decomposition may use
Definition: cons_decomp.cpp:2979
int getNVars()
return the number of variables considered in the detprobdata
Definition: class_detprobdata.cpp:848
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
Definition: cons_decomp.cpp:2609
interface data structure for the detector calling methods
Definition: class_detprobdata.h:672
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHrgpartition)
Definition: dec_hrgpartition.cpp:650
interface to the SCIP tclique graph library
#define DEFAULT_LIMITNCONSSNVARSDEFAULT
Definition: dec_hrgpartition.cpp:113
gcg::DETPROBDATA * detprobdata
Definition: class_detprobdata.h:674
void assignSmallestComponentsButOneConssAdjacency()
computes components by connectedness of conss and vars
Definition: class_partialdecomp.cpp:928
Definition: class_detprobdata.h:106
static DEC_DECL_EXITDETECTOR(exitHrgpartition)
Definition: dec_hrgpartition.cpp:228
arrowhead and bordered detector via graph partitioning (uses hmetis)
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecHrgpartition)
Definition: dec_hrgpartition.cpp:594
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata, gcg::PARTIALDECOMP *partialdec, bool allowopenpartialdecs, SCIP_RESULT *result)
Definition: dec_hrgpartition.cpp:433
Definition: matrixgraph.h:54
static DEC_DECL_FREEDETECTOR(freeHrgpartition)
Definition: dec_hrgpartition.cpp:188
#define detectorPostprocessPartialdecHrgpartition
Definition: dec_hrgpartition.cpp:646
Column hypergraph.
gcg::PARTIALDECOMP ** newpartialdecs
Definition: class_detprobdata.h:676
virtual SCIP_RETCODE readPartition(const char *filename)
Definition: matrixgraph.h:113
int limitnconssnvarsdefault
Definition: dec_hrgpartition.cpp:154
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
Definition: class_detprobdata.cpp:854
#define DEFAULT_ENABLEDFORLARGEPROBLEMS
Definition: dec_hrgpartition.cpp:114
SCIP_RETCODE DECincludeDetector(SCIP *scip, const char *name, const char decchar, const char *description, int freqCallRound, int maxCallRound, int minCallRound, int freqCallRoundOriginal, int maxCallRoundOriginal, int minCallRoundOriginal, int priority, SCIP_Bool enabled, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, DEC_DETECTORDATA *detectordata, DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATEPARTIALDEC((*propagatePartialdecDetector)), DEC_DECL_FINISHPARTIALDEC((*finishPartialdecDetector)), DEC_DECL_POSTPROCESSPARTIALDEC((*postprocessPartialdecDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
Definition: cons_decomp.cpp:3041
bool isConsOpencons(int cons)
Gets whether the cons is an open cons.
Definition: class_partialdecomp.cpp:4524
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultHrgpartition)
Definition: dec_hrgpartition.cpp:704
Definition: dec_compgreedily.cpp:73
class storing (potentially incomplete) decompositions
bool alreadyAssignedConssToBlocks()
method to check if at least one constraint is assigned to some block
Definition: class_partialdecomp.cpp:390
SCIP_Bool enabledforlargeproblems
Definition: dec_hrgpartition.cpp:155
int getNConssForVar(int varIndex)
returns the number of constraints for a given variable where the var has a nonzero entry in
Definition: class_detprobdata.cpp:810
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
Definition: class_detprobdata.cpp:963
#define finishPartialdecHrgpartition
Definition: dec_hrgpartition.cpp:645
const int * getOpenvars()
Gets array containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4259
class storing partialdecs and the problem matrix
SCIP_RETCODE SCIPincludeDetectorHrgpartition(SCIP *scip)
Definition: dec_hrgpartition.cpp:792
static DEC_DECL_SETPARAMFAST(setParamFastHrgpartition)
Definition: dec_hrgpartition.cpp:746
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: matrixgraph.h:99
public methods for working with decomposition structures