dec_hrcgpartition.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*/
83 #define DEC_DESC "enforces arrowhead structures using graph partitioning" /**< description of detector */
84 #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 */
87 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
88 #define DEC_MAXCALLROUNDORIGINAL 1 /**< last round the detector gets called while detecting the original problem */
89 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
96 #define DEC_USEFULRECALL TRUE /**< is it useful to call this detector on a descendant of the propagated partialdec */
109 #define DEFAULT_CONSWEIGHT_SETPPC 5 /**< weight for constraint hyperedges that are setpartitioning or covering
113 #define DEFAULT_MAXNBLOCKCANDIDATES 3 /**< number of block number candidates to be considered */
115 #define DEFAULT_BETA 0.5 /**< factor of how the weight for equality and inequality constraints is
117 #define DEFAULT_METIS_UBFACTOR 5.0 /**< default unbalance factor given to metis on the commandline */
119 #define DEFAULT_METISUSEPTYPE_RB TRUE /**< Should metis use the rb or kway partitioning algorithm */
121 #define DEFAULT_TYPE 'a' /**< type of the decomposition 'c' column hypergraph (single bordered, no
159 SCIP_Bool realname; /**< flag to indicate real problem name or temporary filename for metis files */
260 (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"ulimit -t %.0f;" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
271 (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
286 SCIPdebugMessage("time left before metis started: %f, time metis spend %f, remainingtime: %f\n", remainingtime, SCIPgetClockTime(scip, metisclock), remainingtime-SCIPgetClockTime(scip, metisclock) );
299 SCIPerrorMessage("Calling hmetis unsuccessful! See the above error message for more details.\n");
350 (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%c-%d.metis.XXXXXX", DEC_DECCHAR, partialdecID );
354 (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%s-%c-%d.metis.XXXXXX", SCIPgetProbName(scip), DEC_DECCHAR, partialdecID);
462 Partialdec_Detection_Data* partialdecdetectiondata, /**< partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs */
464 bool allowopenpartialdecs, /**< whether new partialdecs should be stored in which this detector only assignes conss to master */
493 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/hrcgpartition/maxnblockcandidates");
508 Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
541 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], &newpartialdecs[j+1], partialdecdetectiondata->detprobdata));
545 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], NULL, partialdecdetectiondata->detprobdata));
581 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d partialdecs found.\n", nnewpartialdecs);
582 SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
587 partialdecdetectiondata->newpartialdecs[s]->addClockTime(clockTimes[s] + SCIPgetClockTime(scip, temporaryClock) / nnewpartialdecs);
623 if( !connected(partialdecdetectiondata->detprobdata, partialdec) || partialdec->alreadyAssignedConssToBlocks() )
628 detection(scip, DECdetectorGetData(detector), partialdecdetectiondata, partialdec, true, result);
655 detection(scip, DECdetectorGetData(detector), partialdecdetectiondata, partialdec, false, result);
698 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
705 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
716 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
743 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
750 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
761 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
790 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
796 modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
809 (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
832 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, freeHrcgpartition, initHrcgpartition, exitHrcgpartition, propagatePartialdecHrcgpartition, finishPartialdecHrcgpartition, detectorPostprocessPartialdecHrcgpartition, setParamAggressiveHrcgpartition, setParamDefaultHrcgpartition, setParamFastHrcgpartition) );
836 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/maxnblockcandidates", "The maximal number of block number candidates", &detectordata->maxnblockcandidates, FALSE, DEFAULT_MAXNBLOCKCANDIDATES, 0, 1000000, NULL, NULL) );
837 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/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) );
838 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/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) );
839 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrcgpartition/beta", "Factor on how heavy equality (beta) and inequality constraints are measured", &detectordata->beta, FALSE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL ) );
840 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrcgpartition/alpha", "Factor on how heavy the standard deviation of the coefficients is measured", &detectordata->alpha, FALSE, DEFAULT_ALPHA, 0.0, 1E20, NULL, NULL ) );
841 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/varWeight", "Weight of a variable hyperedge", &detectordata->varWeight, FALSE, DEFAULT_VARWEIGHT, 0, 1000000, NULL, NULL) );
842 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/varWeightBinary", "Weight of a binary variable hyperedge", &detectordata->varWeightBinary, FALSE, DEFAULT_VARWEIGHTBIN, 0, 1000000, NULL, NULL) );
843 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/varWeightContinous", "Weight of a continuos variable hyperedge", &detectordata->varWeightContinous, FALSE, DEFAULT_VARWEIGHTCONT, 0, 1000000, NULL, NULL) );
844 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/varWeightImplint", "Weight of a implicit integer variable hyperedge", &detectordata->varWeightImplint, FALSE, DEFAULT_VARWEIGHTIMPL, 0, 1000000, NULL, NULL) );
845 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/varWeightInteger", "Weight of a integer variable hyperedge", &detectordata->varWeightInteger, FALSE, DEFAULT_VARWEIGHTINT, 0, 1000000, NULL, NULL) );
846 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/consWeight", "Weight of a constraint hyperedge", &detectordata->consWeight, FALSE, DEFAULT_CONSWEIGHT, 0, 1000000, NULL, NULL) );
847 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrcgpartition/tidy", "Whether to clean up temporary files", &detectordata->tidy, FALSE, DEFAULT_TIDY, NULL, NULL) );
848 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/randomseed", "Random seed for hmetis", &detectordata->randomseed, FALSE, DEFAULT_RANDSEED, -1, INT_MAX, NULL, NULL) );
849 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrcgpartition/dummynodes", "Percentage of dummy nodes for metis", &detectordata->dummynodes, FALSE, DEFAULT_DUMMYNODES, 0.0, 1.0, NULL, NULL) );
850 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrcgpartition/consWeightSetppc", "Weight for constraint hyperedges that are setpartitioning or covering constraints", &detectordata->consWeightSetppc, FALSE, DEFAULT_CONSWEIGHT_SETPPC, 0, 1000000, NULL, NULL) );
851 SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrcgpartition/ubfactor", "Unbalance factor for metis", &detectordata->metisubfactor, FALSE, DEFAULT_METIS_UBFACTOR, 0.0, 1E20, NULL, NULL ) );
852 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrcgpartition/metisverbose", "Should the metis output be displayed", &detectordata->metisverbose, FALSE, DEFAULT_METIS_VERBOSE, NULL, NULL ) );
853 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrcgpartition/metisuseptyperb", "Should the rb or kway method be used for partitioning by metis", &detectordata->metisuseptyperb, FALSE, DEFAULT_METISUSEPTYPE_RB, NULL, NULL) );
854 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrcgpartition/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
arrowhead and bordered detector via graph partitioning (uses hmetis)
structure information for decomposition information in GCG projects
static DEC_DECL_SETPARAMFAST(setParamFastHrcgpartition)
Definition: dec_hrcgpartition.cpp:772
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecHrcgpartition)
Definition: dec_hrcgpartition.cpp:612
static SCIP_RETCODE callMetis(SCIP *scip, DEC_DETECTORDATA *detectordata, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN], int nblocks, SCIP_RESULT *result)
Definition: dec_hrcgpartition.cpp:226
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4198
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
miscellaneous matrixgraph methods for structure detection
A hypergraph with row and column nodes.
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultHrcgpartition)
Definition: dec_hrcgpartition.cpp:726
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
static SCIP_RETCODE createMetisFile(SCIP *scip, DEC_DETECTORDATA *detectordata, int partialdecID, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN])
Definition: dec_hrcgpartition.cpp:332
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
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata, gcg::PARTIALDECOMP *partialdec, bool allowopenpartialdecs, SCIP_RESULT *result)
Definition: dec_hrcgpartition.cpp:459
virtual SCIP_RETCODE writeToFile(int fd, SCIP_Bool writeweights)
Definition: matrixgraph.h:79
#define detectorPostprocessPartialdecHrcgpartition
Definition: dec_hrcgpartition.cpp:665
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
static DEC_DECL_FREEDETECTOR(freeHrcgpartition)
Definition: dec_hrcgpartition.cpp:176
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
static DEC_DECL_FINISHPARTIALDEC(finishPartialdecHrcgpartition)
Definition: dec_hrcgpartition.cpp:639
static bool connected(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
Definition: dec_hrcgpartition.cpp:366
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
static DEC_DECL_EXITDETECTOR(exitHrcgpartition)
Definition: dec_hrcgpartition.cpp:215
interface data structure for the detector calling methods
Definition: class_detprobdata.h:672
SCIP_RETCODE SCIPincludeDetectorHrcgpartition(SCIP *scip)
Definition: dec_hrcgpartition.cpp:821
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHrcgpartition)
Definition: dec_hrcgpartition.cpp:669
interface to the SCIP tclique graph library
static DEC_DECL_INITDETECTOR(initHrcgpartition)
Definition: dec_hrcgpartition.cpp:194
Definition: hyperrowcolgraph.h:45
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
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
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
const int * getOpenvars()
Gets array containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4259
class storing partialdecs and the problem matrix
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: matrixgraph.h:99
public methods for working with decomposition structures