Detailed Description
arrowhead and bordered detector via graph partitioning (uses hmetis)
Detects arrowhead (double bordered) decompositions as well as decompositions with only linking variables or linking constraints.
This detector needs hmetis and works only under Linux/MacOS, it further needs the Z-shell (zsh) to enforce memory and time limits on hmetis as this is the only shell reliably doing that.
Definition in file dec_hcgpartition.cpp.
#include "dec_hcgpartition.h"
#include <cassert>
#include <cstring>
#include <cerrno>
#include <unistd.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include "cons_decomp.h"
#include "struct_decomp.h"
#include "pub_decomp.h"
#include "scip_misc.h"
#include "scip/pub_misc.h"
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "graph/matrixgraph.h"
#include "graph/hypercolgraph.h"
#include "graph/graph_tclique.h"
#include "graph/weights.h"
#include "class_partialdecomp.h"
#include "class_detprobdata.h"
#include "scip/clock.h"
#include <set>
Go to the source code of this file.
Data Structures | |
struct | DEC_DetectorData |
Functions | |
static | DEC_DECL_FREEDETECTOR (freeHcgpartition) |
static | DEC_DECL_INITDETECTOR (initHcgpartition) |
static | DEC_DECL_EXITDETECTOR (exitHcgpartition) |
static SCIP_RETCODE | callMetis (SCIP *scip, DEC_DETECTORDATA *detectordata, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN], int nblocks, SCIP_RESULT *result) |
static SCIP_RETCODE | createMetisFile (SCIP *scip, DEC_DETECTORDATA *detectordata, int partialdecid, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN]) |
static bool | connected (gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec) |
static SCIP_RETCODE | detection (SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata, gcg::PARTIALDECOMP *partialdec, bool allowopenpartialdecs, SCIP_RESULT *result) |
static | DEC_DECL_PROPAGATEPARTIALDEC (propagatePartialdecHcgpartition) |
static | DEC_DECL_FINISHPARTIALDEC (finishPartialdecHcgpartition) |
static | DEC_DECL_SETPARAMAGGRESSIVE (setParamAggressiveHcgpartition) |
static | DEC_DECL_SETPARAMDEFAULT (setParamDefaultHcgpartition) |
static | DEC_DECL_SETPARAMFAST (setParamFastHcgpartition) |
SCIP_RETCODE | SCIPincludeDetectorHcgpartition (SCIP *scip) |
Macro Definition Documentation
◆ HMETIS_EXECUTABLE
#define HMETIS_EXECUTABLE "hmetis" |
Definition at line 61 of file dec_hcgpartition.cpp.
◆ DEC_DETECTORNAME
#define DEC_DETECTORNAME "hcgpartition" |
name of the detector
Definition at line 86 of file dec_hcgpartition.cpp.
◆ DEC_DESC
#define DEC_DESC "enforces arrowhead structures using graph partitioning" |
description of detector
Definition at line 87 of file dec_hcgpartition.cpp.
◆ DEC_FREQCALLROUND
#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
Definition at line 88 of file dec_hcgpartition.cpp.
◆ DEC_MAXCALLROUND
#define DEC_MAXCALLROUND 0 |
last round the detector gets called
Definition at line 89 of file dec_hcgpartition.cpp.
◆ DEC_MINCALLROUND
#define DEC_MINCALLROUND 0 |
first round the detector gets called
Definition at line 90 of file dec_hcgpartition.cpp.
◆ DEC_FREQCALLROUNDORIGINAL
#define DEC_FREQCALLROUNDORIGINAL 1 |
frequency the detector gets called in detection loop while detecting the original problem
Definition at line 91 of file dec_hcgpartition.cpp.
◆ DEC_MAXCALLROUNDORIGINAL
#define DEC_MAXCALLROUNDORIGINAL 0 |
last round the detector gets called while detecting the original problem
Definition at line 92 of file dec_hcgpartition.cpp.
◆ DEC_MINCALLROUNDORIGINAL
#define DEC_MINCALLROUNDORIGINAL 0 |
first round the detector gets called while detecting the original problem
Definition at line 93 of file dec_hcgpartition.cpp.
◆ DEC_PRIORITY
#define DEC_PRIORITY 1000 |
priority of the detector
Definition at line 94 of file dec_hcgpartition.cpp.
◆ DEC_DECCHAR
#define DEC_DECCHAR 'G' |
display character of detector
Definition at line 95 of file dec_hcgpartition.cpp.
◆ DEC_ENABLED
#define DEC_ENABLED FALSE |
should detector be called by default
Definition at line 96 of file dec_hcgpartition.cpp.
◆ DEC_ENABLEDFINISHING
#define DEC_ENABLEDFINISHING FALSE |
should detector be called by default
Definition at line 97 of file dec_hcgpartition.cpp.
◆ DEC_ENABLEDPOSTPROCESSING
#define DEC_ENABLEDPOSTPROCESSING FALSE |
should the postprocessing be enabled
Definition at line 98 of file dec_hcgpartition.cpp.
◆ DEC_SKIP
#define DEC_SKIP FALSE |
should detector be skipped if others found detections
Definition at line 99 of file dec_hcgpartition.cpp.
◆ DEC_USEFULRECALL
#define DEC_USEFULRECALL TRUE |
is it useful to call this detector on a descendant of the propagated partialdec
Definition at line 100 of file dec_hcgpartition.cpp.
◆ DEFAULT_VARWEIGHT
#define DEFAULT_VARWEIGHT 1 |
weight for variable nodes
Definition at line 104 of file dec_hcgpartition.cpp.
◆ DEFAULT_VARWEIGHTBIN
#define DEFAULT_VARWEIGHTBIN 2 |
weight for binary variable nodes
Definition at line 105 of file dec_hcgpartition.cpp.
◆ DEFAULT_VARWEIGHTINT
#define DEFAULT_VARWEIGHTINT 2 |
weight for integer variable nodes
Definition at line 106 of file dec_hcgpartition.cpp.
◆ DEFAULT_VARWEIGHTIMPL
#define DEFAULT_VARWEIGHTIMPL 2 |
weight for implicit integer variable nodes
Definition at line 107 of file dec_hcgpartition.cpp.
◆ DEFAULT_VARWEIGHTCONT
#define DEFAULT_VARWEIGHTCONT 1 |
weight for continous variable nodes
Definition at line 108 of file dec_hcgpartition.cpp.
◆ DEFAULT_CONSWEIGHT
#define DEFAULT_CONSWEIGHT 5 |
weight for constraint hyperedges
Definition at line 109 of file dec_hcgpartition.cpp.
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 1 |
random seed for the hmetis call
Definition at line 110 of file dec_hcgpartition.cpp.
◆ DEFAULT_TIDY
#define DEFAULT_TIDY TRUE |
whether to clean up afterwards
Definition at line 111 of file dec_hcgpartition.cpp.
◆ DEFAULT_DUMMYNODES
#define DEFAULT_DUMMYNODES 0.2 |
percentage of dummy vertices
Definition at line 112 of file dec_hcgpartition.cpp.
◆ DEFAULT_CONSWEIGHT_SETPPC
#define DEFAULT_CONSWEIGHT_SETPPC 5 |
weight for constraint hyperedges that are setpartitioning or covering constraints
Definition at line 113 of file dec_hcgpartition.cpp.
◆ DEFAULT_MINBLOCKS
#define DEFAULT_MINBLOCKS 2 |
value for the minimum number of blocks to be considered
Definition at line 115 of file dec_hcgpartition.cpp.
◆ DEFAULT_MAXBLOCKS
#define DEFAULT_MAXBLOCKS 20 |
value for the maximum number of blocks to be considered
Definition at line 116 of file dec_hcgpartition.cpp.
◆ DEFAULT_MAXNBLOCKCANDIDATES
#define DEFAULT_MAXNBLOCKCANDIDATES 1 |
number of block number candidates to be considered
Definition at line 117 of file dec_hcgpartition.cpp.
◆ DEFAULT_ALPHA
#define DEFAULT_ALPHA 0.0 |
factor for standard deviation of constraint weights
Definition at line 118 of file dec_hcgpartition.cpp.
◆ DEFAULT_BETA
#define DEFAULT_BETA 0.5 |
factor of how the weight for equality and inequality constraints is distributed (keep 1/2 for the same on both)
Definition at line 119 of file dec_hcgpartition.cpp.
◆ DEFAULT_METIS_UBFACTOR
#define DEFAULT_METIS_UBFACTOR 5.0 |
default unbalance factor given to metis on the commandline
Definition at line 121 of file dec_hcgpartition.cpp.
◆ DEFAULT_METIS_VERBOSE
#define DEFAULT_METIS_VERBOSE FALSE |
should metis be verbose
Definition at line 122 of file dec_hcgpartition.cpp.
◆ DEFAULT_METISUSEPTYPE_RB
#define DEFAULT_METISUSEPTYPE_RB TRUE |
Should metis use the rb or kway partitioning algorithm
Definition at line 123 of file dec_hcgpartition.cpp.
◆ DEFAULT_REALNAME
#define DEFAULT_REALNAME FALSE |
whether the metis name should be real or temporary
Definition at line 124 of file dec_hcgpartition.cpp.
◆ DEFAULT_TYPE
#define DEFAULT_TYPE 'r' |
type of the decomposition 'c' column hypergraph (single bordered, no linking constraints), 'r' row hypergraph (single bordered, no linking variables) and 'a' column-row hypergraph (arrowhead)
Definition at line 125 of file dec_hcgpartition.cpp.
◆ SET_MULTIPLEFORSIZETRANSF
#define SET_MULTIPLEFORSIZETRANSF 12500 |
Definition at line 129 of file dec_hcgpartition.cpp.
◆ detectorPostprocessPartialdecHcgpartition
#define detectorPostprocessPartialdecHcgpartition NULL |
Definition at line 638 of file dec_hcgpartition.cpp.
Function Documentation
◆ DEC_DECL_FREEDETECTOR()
|
static |
destructor of detector to free user data (called when GCG is exiting)
Definition at line 180 of file dec_hcgpartition.cpp.
References DEC_DETECTORNAME, DECdetectorGetData(), and DECdetectorGetName().
◆ DEC_DECL_INITDETECTOR()
|
static |
detector initialization method (called after problem was transformed)
Definition at line 198 of file dec_hcgpartition.cpp.
References DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), DEC_DetectorData::found, and DEC_DetectorData::maxblocks.
◆ DEC_DECL_EXITDETECTOR()
|
static |
detector deinitialization method (called before the transformed problem is freed)
Definition at line 220 of file dec_hcgpartition.cpp.
References DEC_DETECTORNAME, and DECdetectorGetName().
◆ callMetis()
|
static |
will call hmetis via a system call
- Parameters
-
scip SCIP data struture detectordata detector data data structure graph the graph of the matrix tempfile filename for the metis input file nblocks number of blocks result result indicating whether the detection was successful
Definition at line 233 of file dec_hcgpartition.cpp.
References DECgetRemainingTime(), HMETIS_EXECUTABLE, DEC_DetectorData::metisubfactor, DEC_DetectorData::metisuseptyperb, DEC_DetectorData::metisverbose, DEC_DetectorData::randomseed, gcg::MatrixGraph< T >::readPartition(), and DEC_DetectorData::tidy.
Referenced by detection().
◆ createMetisFile()
|
static |
creates the temporary metis input file
- Parameters
-
scip SCIP data struture detectordata detector data structure partialdecid used for speaking filenames graph the graph of the matrix tempfile filename for the metis input file
Definition at line 340 of file dec_hcgpartition.cpp.
References DEC_DECCHAR, DEC_DetectorData::dummynodes, gcg::MatrixGraph< T >::getNNonzeroes(), DEC_DetectorData::realname, gcg::MatrixGraph< T >::setDummynodes(), and gcg::MatrixGraph< T >::writeToFile().
Referenced by detection().
◆ connected()
|
static |
returns, whether the hypercolgraph is connected
Definition at line 374 of file dec_hcgpartition.cpp.
References gcg::DETPROBDATA::getConssForVar(), gcg::DETPROBDATA::getNConss(), gcg::DETPROBDATA::getNConssForVar(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::DETPROBDATA::getNVarsForCons(), gcg::PARTIALDECOMP::getOpenconss(), gcg::DETPROBDATA::getVarsForCons(), gcg::PARTIALDECOMP::isConsOpencons(), and gcg::PARTIALDECOMP::isVarOpenvar().
Referenced by DEC_DECL_FINISHPARTIALDEC(), and DEC_DECL_PROPAGATEPARTIALDEC().
◆ detection()
|
static |
detection function for partialdecs
< filename for the metis input file
- Parameters
-
scip SCIP data structure detectordata detectordata of the detector partialdecdetectiondata partialdecdetectiondata where to store the new Partialdecs partialdec partialdec to propagate allowopenpartialdecs whether new partialdecs should be stored in which this detector only assigns conss to master result pointer where to store the result
Definition at line 427 of file dec_hcgpartition.cpp.
References gcg::PARTIALDECOMP::addClockTime(), gcg::PARTIALDECOMP::addDetectorChainInfo(), callMetis(), gcg::PARTIALDECOMP::considerImplicits(), DEC_DetectorData::consWeight, gcg::MatrixGraph< T >::createFromPartialMatrix(), createMetisFile(), gcg::MatrixGraph< T >::createPartialdecFromPartition(), DEC_DETECTORNAME, Partialdec_Detection_Data::detprobdata, DEC_DetectorData::found, gcg::PARTIALDECOMP::getID(), gcg::PARTIALDECOMP::getNBlocks(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::DETPROBDATA::getSortedCandidatesNBlocks(), DEC_DetectorData::maxblocks, DEC_DetectorData::minblocks, Partialdec_Detection_Data::newpartialdecs, Partialdec_Detection_Data::nnewpartialdecs, gcg::PARTIALDECOMP::refineToBlocks(), DEC_DetectorData::tidy, DEC_DetectorData::varWeight, DEC_DetectorData::varWeightBinary, DEC_DetectorData::varWeightContinous, and DEC_DetectorData::varWeightInteger.
Referenced by DEC_DECL_FINISHPARTIALDEC(), and DEC_DECL_PROPAGATEPARTIALDEC().
◆ DEC_DECL_PROPAGATEPARTIALDEC()
|
static |
Definition at line 586 of file dec_hcgpartition.cpp.
References gcg::PARTIALDECOMP::alreadyAssignedConssToBlocks(), gcg::PARTIALDECOMP::assignSmallestComponentsButOneConssAdjacency(), connected(), gcg::PARTIALDECOMP::considerImplicits(), DECdetectorGetData(), detection(), and gcg::PARTIALDECOMP::refineToMaster().
◆ DEC_DECL_FINISHPARTIALDEC()
|
static |
Definition at line 613 of file dec_hcgpartition.cpp.
References gcg::PARTIALDECOMP::assignSmallestComponentsButOneConssAdjacency(), connected(), gcg::PARTIALDECOMP::considerImplicits(), DECdetectorGetData(), detection(), and gcg::PARTIALDECOMP::refineToBlocks().
◆ DEC_DECL_SETPARAMAGGRESSIVE()
|
static |
Definition at line 641 of file dec_hcgpartition.cpp.
References DECdetectorGetName(), DEFAULT_MAXNBLOCKCANDIDATES, and SET_MULTIPLEFORSIZETRANSF.
◆ DEC_DECL_SETPARAMDEFAULT()
|
static |
Definition at line 696 of file dec_hcgpartition.cpp.
References DEC_ENABLED, DEC_ENABLEDFINISHING, DECdetectorGetName(), DEFAULT_MAXNBLOCKCANDIDATES, and SET_MULTIPLEFORSIZETRANSF.
◆ DEC_DECL_SETPARAMFAST()
|
static |
Definition at line 737 of file dec_hcgpartition.cpp.
References DECdetectorGetName(), DEFAULT_MAXNBLOCKCANDIDATES, and SET_MULTIPLEFORSIZETRANSF.
◆ SCIPincludeDetectorHcgpartition()
SCIP_RETCODE SCIPincludeDetectorHcgpartition | ( | SCIP * | scip | ) |
creates the hcgpartition presolver and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 784 of file dec_hcgpartition.cpp.
References DEC_DetectorData::alpha, DEC_DetectorData::beta, DEC_DetectorData::consWeight, DEC_DetectorData::consWeightSetppc, DEC_DECCHAR, DEC_DESC, DEC_DETECTORNAME, DEC_ENABLED, DEC_ENABLEDFINISHING, DEC_ENABLEDPOSTPROCESSING, DEC_FREQCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUND, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUND, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_SKIP, DEC_USEFULRECALL, DECincludeDetector(), DEFAULT_ALPHA, DEFAULT_BETA, DEFAULT_CONSWEIGHT, DEFAULT_CONSWEIGHT_SETPPC, DEFAULT_DUMMYNODES, DEFAULT_MAXBLOCKS, DEFAULT_MAXNBLOCKCANDIDATES, DEFAULT_METIS_UBFACTOR, DEFAULT_METIS_VERBOSE, DEFAULT_METISUSEPTYPE_RB, DEFAULT_MINBLOCKS, DEFAULT_RANDSEED, DEFAULT_REALNAME, DEFAULT_TIDY, DEFAULT_VARWEIGHT, DEFAULT_VARWEIGHTBIN, DEFAULT_VARWEIGHTCONT, DEFAULT_VARWEIGHTIMPL, DEFAULT_VARWEIGHTINT, detectorPostprocessPartialdecHcgpartition, DEC_DetectorData::dummynodes, DEC_DetectorData::maxblocks, DEC_DetectorData::maxnblockcandidates, DEC_DetectorData::metisubfactor, DEC_DetectorData::metisuseptyperb, DEC_DetectorData::metisverbose, DEC_DetectorData::minblocks, DEC_DetectorData::randomseed, DEC_DetectorData::realname, DEC_DetectorData::tidy, DEC_DetectorData::varWeight, DEC_DetectorData::varWeightBinary, DEC_DetectorData::varWeightContinous, DEC_DetectorData::varWeightImplint, and DEC_DetectorData::varWeightInteger.
Referenced by SCIPincludeGcgPlugins().