dec_hcgpartition.cpp
Go to the documentation of this file.
37 * This detector needs hmetis and works only under Linux/MacOS, it further needs the Z-shell (zsh)
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
87 #define DEC_DESC "enforces arrowhead structures using graph partitioning" /**< description of detector */
88 #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 */
91 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
92 #define DEC_MAXCALLROUNDORIGINAL 0 /**< last round the detector gets called while detecting the original problem */
93 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
100 #define DEC_USEFULRECALL TRUE /**< is it useful to call this detector on a descendant of the propagated partialdec */
113 #define DEFAULT_CONSWEIGHT_SETPPC 5 /**< weight for constraint hyperedges that are setpartitioning or covering
117 #define DEFAULT_MAXNBLOCKCANDIDATES 1 /**< number of block number candidates to be considered */
119 #define DEFAULT_BETA 0.5 /**< factor of how the weight for equality and inequality constraints is
121 #define DEFAULT_METIS_UBFACTOR 5.0 /**< default unbalance factor given to metis on the commandline */
123 #define DEFAULT_METISUSEPTYPE_RB TRUE /**< Should metis use the rb or kway partitioning algorithm */
125 #define DEFAULT_TYPE 'r' /**< type of the decomposition 'c' column hypergraph (single bordered, no
162 SCIP_Bool realname; /**< flag to indicate real problem name or temporary filename for metis files */
267 (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"ulimit -t %.0f;" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
278 (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
293 SCIPdebugMessage("time left before metis started: %f, time metis spend %f, remainingtime: %f\n", remainingtime, SCIPgetClockTime(scip, metisclock), remainingtime-SCIPgetClockTime(scip, metisclock) );
306 SCIPerrorMessage("Calling hmetis unsuccessful! See the above error message for more details.\n");
358 (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%c-%d.metis.XXXXXX", DEC_DECCHAR, partialdecid );
362 (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%s-%c-%d.metis.XXXXXX", SCIPgetProbName(scip), DEC_DECCHAR, partialdecid);
430 Partialdec_Detection_Data* partialdecdetectiondata, /**< partialdecdetectiondata where to store the new Partialdecs */
432 bool allowopenpartialdecs, /**< whether new partialdecs should be stored in which this detector only assigns conss to master */
463 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/hcgpartition/maxnblockcandidates");
479 Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
514 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], &newpartialdecs[j+1], partialdecdetectiondata->detprobdata));
518 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], NULL, partialdecdetectiondata->detprobdata));
554 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d partialdecs found.\n", nnewpartialdecs);
555 SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
560 partialdecdetectiondata->newpartialdecs[s]->addClockTime(clockTimes[s] + SCIPgetClockTime(scip, temporaryClock) / nnewpartialdecs);
597 if( !connected(partialdecdetectiondata->detprobdata, partialdec) || partialdec->alreadyAssignedConssToBlocks() )
602 detection(scip, DECdetectorGetData(detector), partialdecdetectiondata, partialdec, true, result);
629 detection(scip, DECdetectorGetData(detector), partialdecdetectiondata, partialdec, false, result);
669 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
675 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
686 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
715 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
726 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
754 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
761 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
772 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
796 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, freeHcgpartition, initHcgpartition, exitHcgpartition, propagatePartialdecHcgpartition, finishPartialdecHcgpartition, detectorPostprocessPartialdecHcgpartition, setParamAggressiveHcgpartition, setParamDefaultHcgpartition, setParamFastHcgpartition) );
800 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/maxnblockcandidates", "The maximal number of block number candidates", &detectordata->maxnblockcandidates, FALSE, DEFAULT_MAXNBLOCKCANDIDATES, 0, 1000000, NULL, NULL) );
801 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/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) );
802 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/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) );
803 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/beta", "Factor on how heavy equality (beta) and inequality constraints are measured", &detectordata->beta, FALSE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL ) );
804 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/alpha", "Factor on how heavy the standard deviation of the coefficients is measured", &detectordata->alpha, FALSE, DEFAULT_ALPHA, 0.0, 1E20, NULL, NULL ) );
805 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeight", "Weight of a variable hyperedge", &detectordata->varWeight, FALSE, DEFAULT_VARWEIGHT, 0, 1000000, NULL, NULL) );
806 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightBinary", "Weight of a binary variable hyperedge", &detectordata->varWeightBinary, FALSE, DEFAULT_VARWEIGHTBIN, 0, 1000000, NULL, NULL) );
807 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightContinous", "Weight of a continuos variable hyperedge", &detectordata->varWeightContinous, FALSE, DEFAULT_VARWEIGHTCONT, 0, 1000000, NULL, NULL) );
808 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightImplint", "Weight of a implicit integer variable hyperedge", &detectordata->varWeightImplint, FALSE, DEFAULT_VARWEIGHTIMPL, 0, 1000000, NULL, NULL) );
809 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightInteger", "Weight of a integer variable hyperedge", &detectordata->varWeightInteger, FALSE, DEFAULT_VARWEIGHTINT, 0, 1000000, NULL, NULL) );
810 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/consWeight", "Weight of a constraint hyperedge", &detectordata->consWeight, FALSE, DEFAULT_CONSWEIGHT, 0, 1000000, NULL, NULL) );
811 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/tidy", "Whether to clean up temporary files", &detectordata->tidy, FALSE, DEFAULT_TIDY, NULL, NULL) );
812 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/randomseed", "Random seed for hmetis", &detectordata->randomseed, FALSE, DEFAULT_RANDSEED, -1, INT_MAX, NULL, NULL) );
813 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/dummynodes", "Percentage of dummy nodes for metis", &detectordata->dummynodes, FALSE, DEFAULT_DUMMYNODES, 0.0, 1.0, NULL, NULL) );
814 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/consWeightSetppc", "Weight for constraint hyperedges that are setpartitioning or covering constraints", &detectordata->consWeightSetppc, FALSE, DEFAULT_CONSWEIGHT_SETPPC, 0, 1000000, NULL, NULL) );
815 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/ubfactor", "Unbalance factor for metis", &detectordata->metisubfactor, FALSE, DEFAULT_METIS_UBFACTOR, 0.0, 1E20, NULL, NULL ) );
816 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/metisverbose", "Should the metis output be displayed", &detectordata->metisverbose, FALSE, DEFAULT_METIS_VERBOSE, NULL, NULL ) );
817 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/metisuseptyperb", "Should the rb or kway method be used for partitioning by metis", &detectordata->metisuseptyperb, FALSE, DEFAULT_METISUSEPTYPE_RB, NULL, NULL) );
818 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/realname", "Should the problem be used for metis files or a temporary name", &detectordata->realname, FALSE, DEFAULT_REALNAME, NULL, NULL) );
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
Definition: class_partialdecomp.cpp:286
int getNConss()
returns the number of variables considered in the detprobdata
Definition: class_detprobdata.cpp:796
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
Definition: cons_decomp.cpp:2618
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultHcgpartition)
Definition: dec_hcgpartition.cpp:696
static DEC_DECL_INITDETECTOR(initHcgpartition)
Definition: dec_hcgpartition.cpp:198
SCIP_RETCODE SCIPincludeDetectorHcgpartition(SCIP *scip)
Definition: dec_hcgpartition.cpp:784
static DEC_DECL_FINISHPARTIALDEC(finishPartialdecHcgpartition)
Definition: dec_hcgpartition.cpp:613
structure information for decomposition information in GCG projects
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
miscellaneous matrixgraph methods for structure detection
arrowhead and bordered detector via graph partitioning (uses hmetis)
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 DEC_DECL_EXITDETECTOR(exitHcgpartition)
Definition: dec_hcgpartition.cpp:220
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
Definition: hypercolgraph.h:46
static SCIP_RETCODE createMetisFile(SCIP *scip, DEC_DETECTORDATA *detectordata, int partialdecid, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN])
Definition: dec_hcgpartition.cpp:340
static bool connected(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
Definition: dec_hcgpartition.cpp:374
Column hypergraph.
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHcgpartition)
Definition: dec_hcgpartition.cpp:641
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
Definition: cons_decomp.cpp:2609
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata, gcg::PARTIALDECOMP *partialdec, bool allowopenpartialdecs, SCIP_RESULT *result)
Definition: dec_hcgpartition.cpp:427
interface data structure for the detector calling methods
Definition: class_detprobdata.h:672
static DEC_DECL_SETPARAMFAST(setParamFastHcgpartition)
Definition: dec_hcgpartition.cpp:737
interface to the SCIP tclique graph library
gcg::DETPROBDATA * detprobdata
Definition: class_detprobdata.h:674
const int * getOpenconss()
Gets array containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4247
void assignSmallestComponentsButOneConssAdjacency()
computes components by connectedness of conss and vars
Definition: class_partialdecomp.cpp:928
Definition: class_detprobdata.h:106
#define detectorPostprocessPartialdecHcgpartition
Definition: dec_hcgpartition.cpp:638
Definition: matrixgraph.h:54
gcg::PARTIALDECOMP ** newpartialdecs
Definition: class_detprobdata.h:676
virtual SCIP_RETCODE readPartition(const char *filename)
Definition: matrixgraph.h:113
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
Definition: class_detprobdata.cpp:854
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
int getNOpenconss()
Gets size of vector containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4192
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecHcgpartition)
Definition: dec_hcgpartition.cpp:586
bool isConsOpencons(int cons)
Gets whether the cons is an open cons.
Definition: class_partialdecomp.cpp:4524
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
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
class storing partialdecs and the problem matrix
static SCIP_RETCODE callMetis(SCIP *scip, DEC_DETECTORDATA *detectordata, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN], int nblocks, SCIP_RESULT *result)
Definition: dec_hcgpartition.cpp:233
static DEC_DECL_FREEDETECTOR(freeHcgpartition)
Definition: dec_hcgpartition.cpp:180
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: matrixgraph.h:99
public methods for working with decomposition structures