dec_hrcgpartition.cpp File Reference

Detailed Description

arrowhead and bordered detector via graph partitioning (uses hmetis)

Author

Martin Bergner

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_hrcgpartition.cpp.

#include "dec_hrcgpartition.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/hyperrowcolgraph.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

Macros
#define	HMETIS_EXECUTABLE   "hmetis"
#define	DEC_DETECTORNAME   "hrcgpartition"
#define	DEC_DESC   "enforces arrowhead structures using graph partitioning"
#define	DEC_FREQCALLROUND   1
#define	DEC_MAXCALLROUND   1
#define	DEC_MINCALLROUND   0
#define	DEC_FREQCALLROUNDORIGINAL   1
#define	DEC_MAXCALLROUNDORIGINAL   1
#define	DEC_MINCALLROUNDORIGINAL   0
#define	DEC_PRIORITY   1000
#define	DEC_DECCHAR   'a'
#define	DEC_ENABLED   FALSE
#define	DEC_ENABLEDFINISHING   FALSE
#define	DEC_ENABLEDPOSTPROCESSING   FALSE
#define	DEC_SKIP   FALSE
#define	DEC_USEFULRECALL   TRUE
#define	DEFAULT_VARWEIGHT   2
#define	DEFAULT_VARWEIGHTBIN   3
#define	DEFAULT_VARWEIGHTINT   3
#define	DEFAULT_VARWEIGHTIMPL   3
#define	DEFAULT_VARWEIGHTCONT   2
#define	DEFAULT_CONSWEIGHT   1
#define	DEFAULT_RANDSEED   1
#define	DEFAULT_TIDY   TRUE
#define	DEFAULT_DUMMYNODES   0.2
#define	DEFAULT_CONSWEIGHT_SETPPC   5
#define	DEFAULT_MINBLOCKS   2
#define	DEFAULT_MAXBLOCKS   20
#define	DEFAULT_MAXNBLOCKCANDIDATES   3
#define	DEFAULT_ALPHA   0.0
#define	DEFAULT_BETA   0.5
#define	DEFAULT_METIS_UBFACTOR   5.0
#define	DEFAULT_METIS_VERBOSE   FALSE
#define	DEFAULT_METISUSEPTYPE_RB   TRUE
#define	DEFAULT_REALNAME   FALSE
#define	DEFAULT_TYPE   'a'
#define	FAST_MAXHALFPERIMETER   25000
#define	SET_MULTIPLEFORSIZETRANSF   12500
#define	detectorPostprocessPartialdecHrcgpartition   NULL

Functions
static	DEC_DECL_FREEDETECTOR (freeHrcgpartition)
static	DEC_DECL_INITDETECTOR (initHrcgpartition)
static	DEC_DECL_EXITDETECTOR (exitHrcgpartition)
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 (propagatePartialdecHrcgpartition)
static	DEC_DECL_FINISHPARTIALDEC (finishPartialdecHrcgpartition)
static	DEC_DECL_SETPARAMAGGRESSIVE (setParamAggressiveHrcgpartition)
static	DEC_DECL_SETPARAMDEFAULT (setParamDefaultHrcgpartition)
static	DEC_DECL_SETPARAMFAST (setParamFastHrcgpartition)
SCIP_RETCODE	SCIPincludeDetectorHrcgpartition (SCIP *scip)

Macro Definition Documentation

HMETIS_EXECUTABLE

#define HMETIS_EXECUTABLE   "hmetis"

Definition at line 57 of file dec_hrcgpartition.cpp.

DEC_DETECTORNAME

#define DEC_DETECTORNAME   "hrcgpartition"

name of the detector

Definition at line 82 of file dec_hrcgpartition.cpp.

DEC_DESC

#define DEC_DESC   "enforces arrowhead structures using graph partitioning"

description of detector

Definition at line 83 of file dec_hrcgpartition.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 84 of file dec_hrcgpartition.cpp.

DEC_MAXCALLROUND

#define DEC_MAXCALLROUND   1

last round the detector gets called

Definition at line 85 of file dec_hrcgpartition.cpp.

DEC_MINCALLROUND

#define DEC_MINCALLROUND   0

first round the detector gets called

Definition at line 86 of file dec_hrcgpartition.cpp.

DEC_FREQCALLROUNDORIGINAL

#define DEC_FREQCALLROUNDORIGINAL   1

frequency the detector gets called in detection loop while detecting the original problem

Definition at line 87 of file dec_hrcgpartition.cpp.

DEC_MAXCALLROUNDORIGINAL

#define DEC_MAXCALLROUNDORIGINAL   1

last round the detector gets called while detecting the original problem

Definition at line 88 of file dec_hrcgpartition.cpp.

DEC_MINCALLROUNDORIGINAL

#define DEC_MINCALLROUNDORIGINAL   0

first round the detector gets called while detecting the original problem

Definition at line 89 of file dec_hrcgpartition.cpp.

DEC_PRIORITY

#define DEC_PRIORITY   1000

priority of the detector

Definition at line 90 of file dec_hrcgpartition.cpp.

DEC_DECCHAR

#define DEC_DECCHAR   'a'

display character of detector

Definition at line 91 of file dec_hrcgpartition.cpp.

DEC_ENABLED

#define DEC_ENABLED   FALSE

should detector be called by default

Definition at line 92 of file dec_hrcgpartition.cpp.

DEC_ENABLEDFINISHING

#define DEC_ENABLEDFINISHING   FALSE

should the finishing be enabled

Definition at line 93 of file dec_hrcgpartition.cpp.

DEC_ENABLEDPOSTPROCESSING

#define DEC_ENABLEDPOSTPROCESSING   FALSE

should the postprocessing be enabled

Definition at line 94 of file dec_hrcgpartition.cpp.

DEC_SKIP

#define DEC_SKIP   FALSE

should detector be skipped if others found detections

Definition at line 95 of file dec_hrcgpartition.cpp.

DEC_USEFULRECALL

#define DEC_USEFULRECALL   TRUE

is it useful to call this detector on a descendant of the propagated partialdec

Definition at line 96 of file dec_hrcgpartition.cpp.

DEFAULT_VARWEIGHT

#define DEFAULT_VARWEIGHT   2

weight for variable nodes

Definition at line 100 of file dec_hrcgpartition.cpp.

DEFAULT_VARWEIGHTBIN

#define DEFAULT_VARWEIGHTBIN   3

weight for binary variable nodes

Definition at line 101 of file dec_hrcgpartition.cpp.

DEFAULT_VARWEIGHTINT

#define DEFAULT_VARWEIGHTINT   3

weight for integer variable nodes

Definition at line 102 of file dec_hrcgpartition.cpp.

DEFAULT_VARWEIGHTIMPL

#define DEFAULT_VARWEIGHTIMPL   3

weight for implicit integer variable nodes

Definition at line 103 of file dec_hrcgpartition.cpp.

DEFAULT_VARWEIGHTCONT

#define DEFAULT_VARWEIGHTCONT   2

weight for continous variable nodes

Definition at line 104 of file dec_hrcgpartition.cpp.

DEFAULT_CONSWEIGHT

#define DEFAULT_CONSWEIGHT   1

weight for constraint hyperedges

Definition at line 105 of file dec_hrcgpartition.cpp.

DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   1

random seed for the hmetis call

Definition at line 106 of file dec_hrcgpartition.cpp.

DEFAULT_TIDY

#define DEFAULT_TIDY   TRUE

whether to clean up afterwards

Definition at line 107 of file dec_hrcgpartition.cpp.

DEFAULT_DUMMYNODES

#define DEFAULT_DUMMYNODES   0.2

percentage of dummy vertices

Definition at line 108 of file dec_hrcgpartition.cpp.

DEFAULT_CONSWEIGHT_SETPPC

#define DEFAULT_CONSWEIGHT_SETPPC   5

weight for constraint hyperedges that are setpartitioning or covering constraints

Definition at line 109 of file dec_hrcgpartition.cpp.

DEFAULT_MINBLOCKS

#define DEFAULT_MINBLOCKS   2

value for the minimum number of blocks to be considered

Definition at line 111 of file dec_hrcgpartition.cpp.

DEFAULT_MAXBLOCKS

#define DEFAULT_MAXBLOCKS   20

value for the maximum number of blocks to be considered

Definition at line 112 of file dec_hrcgpartition.cpp.

DEFAULT_MAXNBLOCKCANDIDATES

#define DEFAULT_MAXNBLOCKCANDIDATES   3

number of block number candidates to be considered

Definition at line 113 of file dec_hrcgpartition.cpp.

DEFAULT_ALPHA

#define DEFAULT_ALPHA   0.0

factor for standard deviation of constraint weights

Definition at line 114 of file dec_hrcgpartition.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 115 of file dec_hrcgpartition.cpp.

DEFAULT_METIS_UBFACTOR

#define DEFAULT_METIS_UBFACTOR   5.0

default unbalance factor given to metis on the commandline

Definition at line 117 of file dec_hrcgpartition.cpp.

DEFAULT_METIS_VERBOSE

#define DEFAULT_METIS_VERBOSE   FALSE

should metis be verbose

Definition at line 118 of file dec_hrcgpartition.cpp.

DEFAULT_METISUSEPTYPE_RB

#define DEFAULT_METISUSEPTYPE_RB   TRUE

Should metis use the rb or kway partitioning algorithm

Definition at line 119 of file dec_hrcgpartition.cpp.

DEFAULT_REALNAME

#define DEFAULT_REALNAME   FALSE

whether the metis name should be real or temporary

Definition at line 120 of file dec_hrcgpartition.cpp.

DEFAULT_TYPE

#define DEFAULT_TYPE   'a'

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 121 of file dec_hrcgpartition.cpp.

FAST_MAXHALFPERIMETER

#define FAST_MAXHALFPERIMETER   25000

if nrows + ncols does not exceeds this value

Definition at line 125 of file dec_hrcgpartition.cpp.

SET_MULTIPLEFORSIZETRANSF

#define SET_MULTIPLEFORSIZETRANSF   12500

Definition at line 127 of file dec_hrcgpartition.cpp.

detectorPostprocessPartialdecHrcgpartition

#define detectorPostprocessPartialdecHrcgpartition   NULL

Definition at line 665 of file dec_hrcgpartition.cpp.

Function Documentation

DEC_DECL_FREEDETECTOR()

static DEC_DECL_FREEDETECTOR ( freeHrcgpartition  )

static

destructor of detector to free user data (called when GCG is exiting)

Definition at line 176 of file dec_hrcgpartition.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), and DECdetectorGetName().

DEC_DECL_INITDETECTOR()

static DEC_DECL_INITDETECTOR ( initHrcgpartition  )

static

detector initialization method

Definition at line 194 of file dec_hrcgpartition.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), DEC_DetectorData::found, and DEC_DetectorData::maxblocks.

DEC_DECL_EXITDETECTOR()

static DEC_DECL_EXITDETECTOR ( exitHrcgpartition  )

static

detector deinitialization method (called before the transformed problem is freed)

Definition at line 215 of file dec_hrcgpartition.cpp.

References DEC_DETECTORNAME, and DECdetectorGetName().

callMetis()

static SCIP_RETCODE callMetis ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, MatrixGraph< gcg::GraphTclique > *  graph, char  tempfile[SCIP_MAXSTRLEN], int  nblocks, SCIP_RESULT *  result  )

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 226 of file dec_hrcgpartition.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 SCIP_RETCODE createMetisFile ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, int  partialdecID, MatrixGraph< gcg::GraphTclique > *  graph, char  tempfile[SCIP_MAXSTRLEN]  )

static

creates the temporary metis input file

Parameters

scip	SCIP data struture
detectordata	detector data structure
partialdecID	ID of partial decomposition to be used
graph	the graph of the matrix
tempfile	filename for the metis input file

Definition at line 332 of file dec_hrcgpartition.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 bool connected ( gcg::DETPROBDATA *  detprobdata, gcg::PARTIALDECOMP *  partialdec  )

static

returns, whether the hyperrolcolgraph is connected

Definition at line 366 of file dec_hrcgpartition.cpp.

References gcg::DETPROBDATA::getConssForVar(), gcg::DETPROBDATA::getNConss(), gcg::DETPROBDATA::getNConssForVar(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), gcg::DETPROBDATA::getNVars(), gcg::DETPROBDATA::getNVarsForCons(), gcg::PARTIALDECOMP::getOpenconss(), gcg::PARTIALDECOMP::getOpenvars(), gcg::DETPROBDATA::getVarsForCons(), gcg::PARTIALDECOMP::isConsOpencons(), and gcg::PARTIALDECOMP::isVarOpenvar().

Referenced by DEC_DECL_FINISHPARTIALDEC(), and DEC_DECL_PROPAGATEPARTIALDEC().

detection()

static SCIP_RETCODE detection ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, Partialdec_Detection_Data *  partialdecdetectiondata, gcg::PARTIALDECOMP *  partialdec, bool  allowopenpartialdecs, SCIP_RESULT *  result  )

static

detection function for partialdecs

< filename for the metis input file

Parameters

scip	SCIP data structure
detectordata	detectordata of the detector
partialdecdetectiondata	partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs
partialdec	partialdec to propagate
allowopenpartialdecs	whether new partialdecs should be stored in which this detector only assignes conss to master
result	pointer where to store the result

Definition at line 459 of file dec_hrcgpartition.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::MatrixGraph< T >::getNNonzeroes(), 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 DEC_DECL_PROPAGATEPARTIALDEC ( propagatePartialdecHrcgpartition  )

static

Definition at line 612 of file dec_hrcgpartition.cpp.

References gcg::PARTIALDECOMP::alreadyAssignedConssToBlocks(), gcg::PARTIALDECOMP::assignSmallestComponentsButOneConssAdjacency(), connected(), gcg::PARTIALDECOMP::considerImplicits(), DECdetectorGetData(), detection(), and gcg::PARTIALDECOMP::refineToMaster().

DEC_DECL_FINISHPARTIALDEC()

static DEC_DECL_FINISHPARTIALDEC ( finishPartialdecHrcgpartition  )

static

Definition at line 639 of file dec_hrcgpartition.cpp.

References gcg::PARTIALDECOMP::assignSmallestComponentsButOneConssAdjacency(), connected(), gcg::PARTIALDECOMP::considerImplicits(), DECdetectorGetData(), detection(), and gcg::PARTIALDECOMP::refineToBlocks().

DEC_DECL_SETPARAMAGGRESSIVE()

static DEC_DECL_SETPARAMAGGRESSIVE ( setParamAggressiveHrcgpartition  )

static

Definition at line 669 of file dec_hrcgpartition.cpp.

References DECdetectorGetName(), DEFAULT_MAXNBLOCKCANDIDATES, and SET_MULTIPLEFORSIZETRANSF.

DEC_DECL_SETPARAMDEFAULT()

static DEC_DECL_SETPARAMDEFAULT ( setParamDefaultHrcgpartition  )

static

Definition at line 726 of file dec_hrcgpartition.cpp.

References DEC_ENABLED, DEC_ENABLEDFINISHING, DECdetectorGetName(), DEFAULT_MAXNBLOCKCANDIDATES, and SET_MULTIPLEFORSIZETRANSF.

DEC_DECL_SETPARAMFAST()

static DEC_DECL_SETPARAMFAST ( setParamFastHrcgpartition  )

static

Definition at line 772 of file dec_hrcgpartition.cpp.

References DECdetectorGetName(), DEFAULT_MAXNBLOCKCANDIDATES, and SET_MULTIPLEFORSIZETRANSF.

SCIPincludeDetectorHrcgpartition()

SCIP_RETCODE SCIPincludeDetectorHrcgpartition

(

SCIP *

scip

)

creates the hrcgpartition presolver and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 821 of file dec_hrcgpartition.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, detectorPostprocessPartialdecHrcgpartition, 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().