dec_staircase_lsp.cpp
Go to the documentation of this file.
34 * This detector detects staircase_lsp structures in the constraint matrix by searching for the longest shortest path
39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
60 #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 */
63 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
64 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /**< last round the detector gets called while detecting the original problem */
65 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
71 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
164 if( isNeighbor[otherCons] || alreadyConsidered[otherCons] || !partialdec->isConsOpencons(otherCons) )
168 TCLIQUE_CALL( tcliqueAddEdge(*graph, detectordata->oldToNew->at(cons), detectordata->oldToNew->at(otherCons)) );
182 /** finds the diameter of a connected component of a graph and computes all distances from some vertex of maximum eccentricity to all other vertices */
203 int* dist; /* distances from some start vertex to all other vertices (gets updated in each BFS) */
209 int k = 50; /* number of low-degree vertices that are visited before high-degree vertices are visited */
211 /* This method computes the diameter of a connected component by starting BFS at each vertex and memorizing the depth of the search tree.
212 * If a tree has greater depth than any other tree that was computed before, the vertices itself and their distances to the root of the
215 * As these steps require $O(nm)$ time in the worst case, we apply a simple heuristic that stops BFS from vertices that do not have
217 * a) For each vertex 'v' there is an upper bound 'eccentricity[v]' on the actual eccentricity of 'v'. Initially, this is set to a very large number.
218 * b) Whenever a BFS with root 'v' has finished, 'eccentricity[v]' contains the actual eccentricity of 'v'.
219 * c) If during a BFS with root 'v' a vertex 'u' is discovered, then dist(v, u) + eccentricty[u] is an upper bound on the eccentricity of 'v',
220 * and therefore the BFS is stopped if dist(v, u) + eccentricity[u] <= diameter_lb, where diameter_lb is the greatest eccentricity known so far.
242 /* get degrees of vertices and initialize all eccentricities of vertices to values representing upper bounds */
249 eccentricity[i] = 2 * nnodes; /* do not use INT_MAX because it could lead to an overflow when adding values */
250 degree[ncompnodes] = origdegree[i]; /* we copy the degree array because we are going to sort it */
269 /* change order in which BFSes are performed: first start at 'k' low-degree vertices, then start BFS at high-degree vertices */
304 for( node = tcliqueGetFirstAdjedge(graph, currentnode); !pruned && (node <= lastneighbour); ++node )
338 SCIPdebugMessage("new incumbent in component %i: path of length %i starts at %i\n", component, eccent, startnode);
363 /** finds the connected components of the row graph. a staircase_lsp decomposition will be built for each component separately. */
527 Partialdec_Detection_Data* partialdecdetectiondata /**< partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs */
541 gcg::PARTIALDECOMP* currpartialdec = new gcg::PARTIALDECOMP(partialdecdetectiondata->workonpartialdec);
555 SCIP_CALL( createGraphFromPartialMatrix(scip, &(detectordata->graph), currpartialdec, detprobdata, detectordata) );
556 SCIP_CALL( SCIPhashmapCreate(&detectordata->constoblock, SCIPblkmem(scip), detprobdata->getNConss() ) );
562 /* find connected components of the graph. the result will be stored in 'detectordata->components' */
602 SCIP_CALL( SCIPhashmapInsert(detectordata->constoblock, (void*) (size_t) detectordata->newToOld->at(i), (void*) (size_t) (blocks[i] + 1)) );
612 SCIP_CALL( currpartialdec->assignPartialdecFromConstoblock(detectordata->constoblock, nblocks) );
632 partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
782 SCIP_CALL( DECincludeDetector( scip, DEC_DETECTORNAME, DEC_DECCHAR, DEC_DESC, DEC_FREQCALLROUND,
783 DEC_MAXCALLROUND, DEC_MINCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_ENABLED, DEC_ENABLEDFINISHING,DEC_ENABLEDPOSTPROCESSING, DEC_SKIP,
785 detectorInitStaircaseLsp, detectorExitStaircaseLsp, detectorPropagatePartialdecStaircaseLsp, detectorFinishPartialdecStaircaseLsp, detectorPostprocessPartialdecStaircaseLsp, setParamAggressiveStaircaseLsp, setParamDefaultStaircaseLsp, setParamFastStaircaseLsp) );
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 SCIP_RETCODE findDiameter(SCIP *scip, DEC_DETECTORDATA *detectordata, int *maxdistance, int *ncomp, int *vertices, int *distances, int component)
Definition: dec_staircase_lsp.cpp:184
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
Definition: class_partialdecomp.cpp:4721
static SCIP_RETCODE findConnectedComponents(SCIP *scip, DEC_DETECTORDATA *detectordata)
Definition: dec_staircase_lsp.cpp:365
static DEC_DECL_SETPARAMFAST(setParamAggressiveStaircaseLsp)
Definition: dec_staircase_lsp.cpp:708
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(detectorFreeStaircaseLsp)
Definition: dec_staircase_lsp.cpp:449
various SCIP helper methods
SCIP_RETCODE SCIPincludeDetectorStaircaseLsp(SCIP *scip)
Definition: dec_staircase_lsp.cpp:763
static DEC_DECL_FINISHPARTIALDEC(detectorFinishPartialdecStaircaseLsp)
Definition: dec_staircase_lsp.cpp:674
staircase compontent detector
static DEC_DECL_INITDETECTOR(detectorInitStaircaseLsp)
Definition: dec_staircase_lsp.cpp:471
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
bool assignCurrentStairlinking()
assigns open vars to stairlinking if appropriate
Definition: class_partialdecomp.cpp:429
bool sort()
sorts the vars and conss data structures by their indices
Definition: class_partialdecomp.cpp:5445
gcg::DETPROBDATA * detprobdata
Definition: class_detprobdata.h:674
const int * getOpenconss()
Gets array containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4247
Definition: class_detprobdata.h:106
bool checkConsistency()
Checks whether the assignments in the partialdec are consistent.
Definition: class_partialdecomp.cpp:1546
#define detectorPostprocessPartialdecStaircaseLsp
Definition: dec_staircase_lsp.cpp:704
static SCIP_RETCODE createGraphFromPartialMatrix(SCIP *scip, TCLIQUE_GRAPH **graph, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata)
Definition: dec_staircase_lsp.cpp:110
gcg::PARTIALDECOMP ** newpartialdecs
Definition: class_detprobdata.h:676
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
SCIP_RETCODE assignPartialdecFromConstoblock(SCIP_HASHMAP *constoblock, int additionalNBlocks)
assigns conss structure according to given hashmap
Definition: class_partialdecomp.cpp:835
bool isConsOpencons(int cons)
Gets whether the cons is an open cons.
Definition: class_partialdecomp.cpp:4524
Definition: dec_compgreedily.cpp:73
static DEC_DECL_PROPAGATEPARTIALDEC(detectorPropagatePartialdecStaircaseLsp)
Definition: dec_staircase_lsp.cpp:643
class storing (potentially incomplete) decompositions
static DEC_DECL_EXITDETECTOR(detectorExitStaircaseLsp)
Definition: dec_staircase_lsp.cpp:496
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
gcg::PARTIALDECOMP * workonpartialdec
Definition: class_detprobdata.h:675
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata)
Definition: dec_staircase_lsp.cpp:524
public methods for working with decomposition structures