dec_staircase_lsp.cpp File Reference

Detailed Description

detector for staircase_lsp matrices

Author

Martin Bergner

Michael Bastubbe

This detector detects staircase_lsp structures in the constraint matrix by searching for the longest shortest path in the row graph of the matrix.

Definition in file dec_staircase_lsp.cpp.

#include <assert.h>
#include <string.h>
#include <iostream>
#include "dec_staircase_lsp.h"
#include "cons_decomp.h"
#include "scip_misc.h"
#include "pub_decomp.h"
#include "tclique/tclique.h"
#include "class_partialdecomp.h"
#include "class_detprobdata.h"
#include "scip/clock.h"

Go to the source code of this file.

Data Structures
struct	DEC_DetectorData

Macros
#define	DEC_DETECTORNAME   "staircase_lsp"
#define	DEC_DESC   "Staircase detection via shortest paths"
#define	DEC_PRIORITY   200
#define	DEC_FREQCALLROUND   1
#define	DEC_MAXCALLROUND   INT_MAX
#define	DEC_MINCALLROUND   0
#define	DEC_FREQCALLROUNDORIGINAL   1
#define	DEC_MAXCALLROUNDORIGINAL   INT_MAX
#define	DEC_MINCALLROUNDORIGINAL   0
#define	DEC_DECCHAR   'S'
#define	DEC_ENABLED   FALSE
#define	DEC_ENABLEDFINISHING   FALSE
#define	DEC_ENABLEDPOSTPROCESSING   FALSE
#define	DEC_SKIP   FALSE
#define	DEC_USEFULRECALL   FALSE
#define	TCLIQUE_CALL(x)
#define	detectorPostprocessPartialdecStaircaseLsp   NULL

Functions
static SCIP_RETCODE	createGraphFromPartialMatrix (SCIP *scip, TCLIQUE_GRAPH **graph, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE	findDiameter (SCIP *scip, DEC_DETECTORDATA *detectordata, int *maxdistance, int *ncomp, int *vertices, int *distances, int component)
static SCIP_RETCODE	findConnectedComponents (SCIP *scip, DEC_DETECTORDATA *detectordata)
static	DEC_DECL_FREEDETECTOR (detectorFreeStaircaseLsp)
static	DEC_DECL_INITDETECTOR (detectorInitStaircaseLsp)
static	DEC_DECL_EXITDETECTOR (detectorExitStaircaseLsp)
static SCIP_RETCODE	detection (SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata)
static	DEC_DECL_PROPAGATEPARTIALDEC (detectorPropagatePartialdecStaircaseLsp)
static	DEC_DECL_FINISHPARTIALDEC (detectorFinishPartialdecStaircaseLsp)
static	DEC_DECL_SETPARAMFAST (setParamAggressiveStaircaseLsp)
static	DEC_DECL_SETPARAMFAST (setParamDefaultStaircaseLsp)
static	DEC_DECL_SETPARAMFAST (setParamFastStaircaseLsp)
SCIP_RETCODE	SCIPincludeDetectorStaircaseLsp (SCIP *scip)

Macro Definition Documentation

DEC_DETECTORNAME

#define DEC_DETECTORNAME   "staircase_lsp"

name of detector

Definition at line 57 of file dec_staircase_lsp.cpp.

DEC_DESC

#define DEC_DESC   "Staircase detection via shortest paths"

description of detector

Definition at line 58 of file dec_staircase_lsp.cpp.

DEC_PRIORITY

#define DEC_PRIORITY   200

priority of the detector

Definition at line 59 of file dec_staircase_lsp.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 60 of file dec_staircase_lsp.cpp.

DEC_MAXCALLROUND

#define DEC_MAXCALLROUND   INT_MAX

last round the detector gets called

Definition at line 61 of file dec_staircase_lsp.cpp.

DEC_MINCALLROUND

#define DEC_MINCALLROUND   0

first round the detector gets called

Definition at line 62 of file dec_staircase_lsp.cpp.

DEC_FREQCALLROUNDORIGINAL

#define DEC_FREQCALLROUNDORIGINAL   1

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

Definition at line 63 of file dec_staircase_lsp.cpp.

DEC_MAXCALLROUNDORIGINAL

#define DEC_MAXCALLROUNDORIGINAL   INT_MAX

last round the detector gets called while detecting the original problem

Definition at line 64 of file dec_staircase_lsp.cpp.

DEC_MINCALLROUNDORIGINAL

#define DEC_MINCALLROUNDORIGINAL   0

first round the detector gets called while detecting the original problem

Definition at line 65 of file dec_staircase_lsp.cpp.

DEC_DECCHAR

#define DEC_DECCHAR   'S'

display character of detector

Definition at line 66 of file dec_staircase_lsp.cpp.

DEC_ENABLED

#define DEC_ENABLED   FALSE

should the detection be enabled

Definition at line 67 of file dec_staircase_lsp.cpp.

DEC_ENABLEDFINISHING

#define DEC_ENABLEDFINISHING   FALSE

should the finishing be enabled

Definition at line 68 of file dec_staircase_lsp.cpp.

DEC_ENABLEDPOSTPROCESSING

#define DEC_ENABLEDPOSTPROCESSING   FALSE

should the postprocessing be enabled

Definition at line 69 of file dec_staircase_lsp.cpp.

DEC_SKIP

#define DEC_SKIP   FALSE

should detector be skipped if others found detections

Definition at line 70 of file dec_staircase_lsp.cpp.

DEC_USEFULRECALL

#define DEC_USEFULRECALL   FALSE

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

Definition at line 71 of file dec_staircase_lsp.cpp.

TCLIQUE_CALL

#define TCLIQUE_CALL

(

x

)

Value:

                       do                                                                                    \
                       {                                                                                      \
                          if((x) != TRUE )                                                      \
                          {                                                                                   \
                             SCIPerrorMessage("Error in function call\n");                                    \
                             return SCIP_ERROR;                                                               \
                           }                                                                                  \
                       }                                                                                      \
                       while( FALSE )

Definition at line 73 of file dec_staircase_lsp.cpp.

detectorPostprocessPartialdecStaircaseLsp

#define detectorPostprocessPartialdecStaircaseLsp   NULL

Definition at line 704 of file dec_staircase_lsp.cpp.

Function Documentation

createGraphFromPartialMatrix()

static SCIP_RETCODE createGraphFromPartialMatrix ( SCIP *  scip, TCLIQUE_GRAPH **  graph, gcg::PARTIALDECOMP *  partialdec, gcg::DETPROBDATA *  detprobdata, DEC_DETECTORDATA *  detectordata  )

static

creates the graph from the constraint matrix

Parameters

scip	SCIP data structure
graph	Graph data structure
partialdec	partial decomposition to use for matrix
detprobdata	detection process information and data
detectordata	detector data data structure

Definition at line 110 of file dec_staircase_lsp.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(), gcg::PARTIALDECOMP::isVarOpenvar(), DEC_DetectorData::newToOld, DEC_DetectorData::oldToNew, and TCLIQUE_CALL.

Referenced by detection().

findDiameter()

static SCIP_RETCODE findDiameter ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, int *  maxdistance, int *  ncomp, int *  vertices, int *  distances, int  component  )

static

finds the diameter of a connected component of a graph and computes all distances from some vertex of maximum eccentricity to all other vertices

Parameters

scip	SCIP data structure
detectordata	constraint handler data structure
maxdistance	diameter of the graph
ncomp	number of vertices the component contains
vertices	vertices of the connected component (ordered by BFS)
distances	distances of vertices to some vertex of maximum eccentricity
component	connected component to investigate

Definition at line 184 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::components, and DEC_DetectorData::graph.

Referenced by detection().

findConnectedComponents()

static SCIP_RETCODE findConnectedComponents ( SCIP *  scip, DEC_DETECTORDATA *  detectordata  )

static

finds the connected components of the row graph. a staircase_lsp decomposition will be built for each component separately.

Parameters

scip	SCIP data structure
detectordata	constraint handler data structure

Definition at line 365 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::components, DEC_DetectorData::graph, and DEC_DetectorData::ncomponents.

Referenced by detection().

DEC_DECL_FREEDETECTOR()

static DEC_DECL_FREEDETECTOR ( detectorFreeStaircaseLsp  )

static

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

Definition at line 449 of file dec_staircase_lsp.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), DEC_DetectorData::newToOld, and DEC_DetectorData::oldToNew.

DEC_DECL_INITDETECTOR()

static DEC_DECL_INITDETECTOR ( detectorInitStaircaseLsp  )

static

detector initialization method (called after the problem has been transformed)

Definition at line 471 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::components, DEC_DetectorData::constoblock, DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), DEC_DetectorData::graph, DEC_DetectorData::nblocks, DEC_DetectorData::ncomponents, and DEC_DetectorData::vartoblock.

DEC_DECL_EXITDETECTOR()

static DEC_DECL_EXITDETECTOR ( detectorExitStaircaseLsp  )

static

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

Definition at line 496 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::components, DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), and DEC_DetectorData::graph.

detection()

static SCIP_RETCODE detection ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, Partialdec_Detection_Data *  partialdecdetectiondata  )

static

detection function for partialdecs

Parameters

scip	SCIP data structure
detectordata	detectordata of the detector
partialdecdetectiondata	partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs

Definition at line 524 of file dec_staircase_lsp.cpp.

References gcg::PARTIALDECOMP::addClockTime(), gcg::PARTIALDECOMP::addDetectorChainInfo(), gcg::PARTIALDECOMP::assignCurrentStairlinking(), gcg::PARTIALDECOMP::assignPartialdecFromConstoblock(), gcg::PARTIALDECOMP::checkConsistency(), DEC_DetectorData::components, DEC_DetectorData::constoblock, createGraphFromPartialMatrix(), Partialdec_Detection_Data::detectiontime, Partialdec_Detection_Data::detprobdata, findConnectedComponents(), findDiameter(), gcg::DETPROBDATA::getNConss(), DEC_DetectorData::graph, DEC_DetectorData::nblocks, DEC_DetectorData::ncomponents, Partialdec_Detection_Data::newpartialdecs, DEC_DetectorData::newToOld, Partialdec_Detection_Data::nnewpartialdecs, gcg::PARTIALDECOMP::prepare(), gcg::PARTIALDECOMP::refineToMaster(), gcg::PARTIALDECOMP::sort(), DEC_DetectorData::vartoblock, and Partialdec_Detection_Data::workonpartialdec.

Referenced by DEC_DECL_FINISHPARTIALDEC(), and DEC_DECL_PROPAGATEPARTIALDEC().

DEC_DECL_PROPAGATEPARTIALDEC()

static DEC_DECL_PROPAGATEPARTIALDEC ( detectorPropagatePartialdecStaircaseLsp  )

static

detector structure detection method, tries to detect a structure in the problem

Definition at line 643 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::components, DEC_DetectorData::constoblock, detection(), DEC_DetectorData::graph, DEC_DetectorData::nblocks, DEC_DetectorData::ncomponents, DEC_DetectorData::newToOld, DEC_DetectorData::oldToNew, and DEC_DetectorData::vartoblock.

DEC_DECL_FINISHPARTIALDEC()

static DEC_DECL_FINISHPARTIALDEC ( detectorFinishPartialdecStaircaseLsp  )

static

Definition at line 674 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::components, DEC_DetectorData::constoblock, detection(), DEC_DetectorData::graph, DEC_DetectorData::nblocks, DEC_DetectorData::ncomponents, DEC_DetectorData::newToOld, DEC_DetectorData::oldToNew, and DEC_DetectorData::vartoblock.

DEC_DECL_SETPARAMFAST() [1/3]

static DEC_DECL_SETPARAMFAST ( setParamAggressiveStaircaseLsp  )

static

Definition at line 708 of file dec_staircase_lsp.cpp.

References DECdetectorGetName().

DEC_DECL_SETPARAMFAST() [2/3]

static DEC_DECL_SETPARAMFAST ( setParamDefaultStaircaseLsp  )

static

Definition at line 724 of file dec_staircase_lsp.cpp.

References DEC_ENABLED, DEC_ENABLEDFINISHING, and DECdetectorGetName().

DEC_DECL_SETPARAMFAST() [3/3]

static DEC_DECL_SETPARAMFAST ( setParamFastStaircaseLsp  )

static

Definition at line 742 of file dec_staircase_lsp.cpp.

References DECdetectorGetName().

SCIPincludeDetectorStaircaseLsp()

SCIP_RETCODE SCIPincludeDetectorStaircaseLsp

(

SCIP *

scip

)

creates the handler for staircase constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 763 of file dec_staircase_lsp.cpp.

References DEC_DetectorData::constoblock, 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(), detectorPostprocessPartialdecStaircaseLsp, DEC_DetectorData::graph, DEC_DetectorData::nblocks, DEC_DetectorData::newToOld, DEC_DetectorData::oldToNew, and DEC_DetectorData::vartoblock.

Referenced by SCIPincludeGcgPlugins().