dec_stairheur.cpp File Reference

Detailed Description

detector for staircase structures via ROC algorithms

Author

Martin Bergner

Mathias Luers

This detector is based on Jayakumar, Maliyakal D., and Ranga V. Ramasesh. A clustering heuristic to detect staircase structures in large scale linear programming models. European journal of operational research 76.1 (1994): 229-239.

Definition in file dec_stairheur.cpp.

#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include "dec_stairheur.h"
#include "cons_decomp.h"
#include "struct_decomp.h"
#include "pub_decomp.h"
#include "scip_misc.h"
#include "scip/pub_misc.h"
#include "scip/struct_var.h"
#include "gcg.h"
#include "class_partialdecomp.h"
#include "class_detprobdata.h"
#include "scip/clock.h"

Go to the source code of this file.

Data Structures
struct	IndexMap
struct	DEC_DetectorData

Macros
#define	DEC_DETECTORNAME   "stairheur"
#define	DEC_DESC   "detects staircase matrices via matrix reordering"
#define	DEC_PRIORITY   1200
#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	DEFAULT_NCONSSPERBLOCK   32
#define	DEFAULT_MAXBLOCKS   20
#define	DEFAULT_MINBLOCKS   2
#define	DEFAULT_DESIREDBLOCKS   0
#define	DEFAULT_DYNAMICBLOCKING   FALSE
#define	DEFAULT_STATICBLOCKING   TRUE
#define	DEFAULT_BLOCKINGASSOONASPOSSIBLE   FALSE
#define	DEFAULT_MULTIPLEDECOMPS   TRUE
#define	DEFAULT_MAXITERATIONSROC   1000000
#define	detectorExitStairheur   NULL
#define	detectorFinishPartialdecStairheur   NULL
#define	detectorPostprocessPartialdecStairheur   NULL

Typedefs
typedef struct IndexMap	INDEXMAP

Functions
void	printnested (vector< vector< int > > l)
void	printvector (vector< int > l)
static vector< int >	SCIPvectorCreateInt (int from, int to)
static void	SCIPvectorRearrange (vector< vector< int > > &l, vector< int > order)
static SCIP_RETCODE	indexmapCreate (SCIP *scip, INDEXMAP **indexmap, int nconss, int nvars)
static void	indexmapFree (SCIP *scip, INDEXMAP **indexmap)
static SCIP_RETCODE	indexmapInit (INDEXMAP *indexmap, gcg::PARTIALDECOMP *partialdec, int *hashmapindices)
static SCIP_RETCODE	initData (SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE	freeData (SCIP *scip, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE	createRowindexList (SCIP *scip, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata, SCIP_HASHMAP *indexcons, SCIP_HASHMAP *varindex, vector< vector< int > > &rowindices)
static SCIP_RETCODE	createColumnindexList (SCIP *scip, gcg::PARTIALDECOMP *partialdec, vector< vector< int > > &rowindices, vector< vector< int > > &columnindices)
static vector< int >	rowOrdering (SCIP *scip, vector< vector< int > > &columnindices, int nrows)
static SCIP_RETCODE	formIndexArray (int *begin, int *end, vector< vector< int > > &indices)
static SCIP_Bool	arraysAreEqual (int *new_array, int *old_array, int num_elements)
static SCIP_RETCODE	rankOrderClusteringIteration (SCIP *scip, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata, INDEXMAP *inputmap, INDEXMAP *outputmap)
static SCIP_RETCODE	rankOrderClustering (SCIP *scip, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata, int max_iterations, int *iterations)
static SCIP_RETCODE	rowsWithConstriction (SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE	assignConsToBlock (SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata, int block, int first_cons, int last_cons)
static int	getMaxColIndex (DEC_DETECTORDATA *detectordata, int from_row, int to_row)
static int	getMinColIndex (DEC_DETECTORDATA *detectordata, int row)
static SCIP_Bool	isValidBlocking (DEC_DETECTORDATA *detectordata, int prev_block_first_row, int prev_block_last_row, int block_at_row)
static vector< int >::iterator	findBlockingCandidate (vector< int >::iterator it_constrictions, vector< int > *it_vector, int min_block_size, int prev_block_last_row)
static vector< int >::iterator	nextRowToBlockAt (DEC_DETECTORDATA *detectordata, vector< int >::iterator it_constrictions, vector< int > *it_vector, int min_block_size, int prev_block_first_row, int prev_block_last_row)
static int	calculateNdecompositions (DEC_DETECTORDATA *detectordata)
static void	checkParameterConsistency (DEC_DETECTORDATA *detectordata, SCIP_RESULT *result)
static SCIP_RETCODE	blockingDynamic (SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata, int tau, int nvars)
static SCIP_RETCODE	blockingStatic (SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE	blockingAsSoonAsPossible (SCIP *scip, DEC_DETECTORDATA *detectordata, int desired_blocks, int nvars)
static SCIP_RETCODE	resetDetectordata (SCIP *scip, DEC_DETECTORDATA *detectordata)
static SCIP_RETCODE	blocking (SCIP *scip, DEC_DETECTORDATA *detectordata, gcg::PARTIALDECOMP *partialdec, PARTIALDEC_DETECTION_DATA *detectiondata, SCIP_Real time, int maxndecs, SCIP_RESULT *result)
static	DEC_DECL_FREEDETECTOR (detectorFreeStairheur)
static	DEC_DECL_INITDETECTOR (detectorInitStairheur)
static	DEC_DECL_PROPAGATEPARTIALDEC (detectorPropagatePartialdecStairheur)
static	DEC_DECL_SETPARAMFAST (setParamAggressiveStairheur)
static	DEC_DECL_SETPARAMFAST (setParamDefaultStairheur)
static	DEC_DECL_SETPARAMFAST (setParamFastStairheur)
SCIP_RETCODE	SCIPincludeDetectorStairheur (SCIP *scip)

Macro Definition Documentation

DEC_DETECTORNAME

#define DEC_DETECTORNAME   "stairheur"

name of the detector

Definition at line 59 of file dec_stairheur.cpp.

DEC_DESC

#define DEC_DESC   "detects staircase matrices via matrix reordering"

detector description

Definition at line 60 of file dec_stairheur.cpp.

DEC_PRIORITY

#define DEC_PRIORITY   1200

priority of the detector

Definition at line 61 of file dec_stairheur.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 62 of file dec_stairheur.cpp.

DEC_MAXCALLROUND

#define DEC_MAXCALLROUND   INT_MAX

last round the detector gets called

Definition at line 63 of file dec_stairheur.cpp.

DEC_MINCALLROUND

#define DEC_MINCALLROUND   0

first round the detector gets called

Definition at line 64 of file dec_stairheur.cpp.

DEC_FREQCALLROUNDORIGINAL

#define DEC_FREQCALLROUNDORIGINAL   1

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

Definition at line 65 of file dec_stairheur.cpp.

DEC_MAXCALLROUNDORIGINAL

#define DEC_MAXCALLROUNDORIGINAL   INT_MAX

last round the detector gets called while detecting the original problem

Definition at line 66 of file dec_stairheur.cpp.

DEC_MINCALLROUNDORIGINAL

#define DEC_MINCALLROUNDORIGINAL   0

first round the detector gets called while detecting the original problem

Definition at line 67 of file dec_stairheur.cpp.

DEC_DECCHAR

#define DEC_DECCHAR   's'

display character of detector

Definition at line 68 of file dec_stairheur.cpp.

DEC_ENABLED

#define DEC_ENABLED   FALSE

should detector be called by default

Definition at line 69 of file dec_stairheur.cpp.

DEC_ENABLEDFINISHING

#define DEC_ENABLEDFINISHING   FALSE

should the finishing be enabled

Definition at line 70 of file dec_stairheur.cpp.

DEC_ENABLEDPOSTPROCESSING

#define DEC_ENABLEDPOSTPROCESSING   FALSE

should the postprocessing be enabled

Definition at line 71 of file dec_stairheur.cpp.

DEC_SKIP

#define DEC_SKIP   FALSE

should detector be skipped if others found detections

Definition at line 72 of file dec_stairheur.cpp.

DEC_USEFULRECALL

#define DEC_USEFULRECALL   FALSE

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

Definition at line 73 of file dec_stairheur.cpp.

DEFAULT_NCONSSPERBLOCK

#define DEFAULT_NCONSSPERBLOCK   32

number of constraints per block (static blocking only)

Definition at line 76 of file dec_stairheur.cpp.

DEFAULT_MAXBLOCKS

#define DEFAULT_MAXBLOCKS   20

value for the maximum number of blocks to be considered

Definition at line 77 of file dec_stairheur.cpp.

DEFAULT_MINBLOCKS

#define DEFAULT_MINBLOCKS   2

value for the minimum number of blocks to be considered

Definition at line 78 of file dec_stairheur.cpp.

DEFAULT_DESIREDBLOCKS

#define DEFAULT_DESIREDBLOCKS   0

value for the desired number of blocks (for all blocking types). Set to zero for self determination of block number

Definition at line 79 of file dec_stairheur.cpp.

DEFAULT_DYNAMICBLOCKING

#define DEFAULT_DYNAMICBLOCKING   FALSE

Enable blocking type 'dynamic'

Definition at line 80 of file dec_stairheur.cpp.

DEFAULT_STATICBLOCKING

#define DEFAULT_STATICBLOCKING   TRUE

Enable blocking type 'static'

Definition at line 81 of file dec_stairheur.cpp.

DEFAULT_BLOCKINGASSOONASPOSSIBLE

#define DEFAULT_BLOCKINGASSOONASPOSSIBLE   FALSE

Enable blocking type 'as soon as possible'

Definition at line 82 of file dec_stairheur.cpp.

DEFAULT_MULTIPLEDECOMPS

#define DEFAULT_MULTIPLEDECOMPS   TRUE

Enables multiple decompositions for all enabled blocking types. Ranging from minblocks to maxblocks'

Definition at line 83 of file dec_stairheur.cpp.

DEFAULT_MAXITERATIONSROC

#define DEFAULT_MAXITERATIONSROC   1000000

The maximum of iterations of the ROC-algorithm. -1 for no iteration limit

Definition at line 84 of file dec_stairheur.cpp.

detectorExitStairheur

#define detectorExitStairheur   NULL

Definition at line 1796 of file dec_stairheur.cpp.

detectorFinishPartialdecStairheur

#define detectorFinishPartialdecStairheur   NULL

Definition at line 1797 of file dec_stairheur.cpp.

detectorPostprocessPartialdecStairheur

#define detectorPostprocessPartialdecStairheur   NULL

Definition at line 1798 of file dec_stairheur.cpp.

Typedef Documentation

INDEXMAP

typedef struct IndexMap INDEXMAP

Definition at line 109 of file dec_stairheur.cpp.

Function Documentation

printnested()

void printnested

(

vector< vector< int > >

l

)

Definition at line 145 of file dec_stairheur.cpp.

printvector()

void printvector

(

vector< int >

l

)

Definition at line 164 of file dec_stairheur.cpp.

SCIPvectorCreateInt()

static vector<int> SCIPvectorCreateInt ( int  from, int  to  )

static

TODO: currently, all vars from the first column where a linking var appears until the end of the block are considered as linking vars, although there might be empty columns. This could be changed so that these empty columns are considered as subscipvars and not linking vars.

In some cases a block can consist of linking vars exclusively. This makes no real sense.

For some instances the assertion regarding the consistency of the arrays ibegin and jbegin fails creates a list with integers running from 'from' to 'to'.

Parameters

from	Start index
to	End index

Definition at line 187 of file dec_stairheur.cpp.

Referenced by rowOrdering().

SCIPvectorRearrange()

static void SCIPvectorRearrange ( vector< vector< int > > &  l, vector< int >  order  )

static

rearranges elements of vector according to the ordering of order.

example: vector = (a b c d); order = (3 2 4 1) after calling SCIPvectorRearrange(vector, order): vector = (c b d a) both vectors must have the same size order must have elements from 1 to vector->size

Definition at line 209 of file dec_stairheur.cpp.

Referenced by rankOrderClusteringIteration().

indexmapCreate()

static SCIP_RETCODE indexmapCreate ( SCIP *  scip, INDEXMAP **  indexmap, int  nconss, int  nvars  )

static

allocates memory for an indexmap.

Parameters

scip	SCIP data structure
indexmap	address of the pointer which shall store the index map
nconss	number of constraints
nvars	number of variables

Definition at line 228 of file dec_stairheur.cpp.

References IndexMap::consindex, IndexMap::indexcons, IndexMap::indexvar, and IndexMap::varindex.

Referenced by initData(), and rankOrderClustering().

indexmapFree()

static void indexmapFree ( SCIP *  scip, INDEXMAP **  indexmap  )

static

deallocates memory of indexmap.

Parameters

scip	SCIP data structure
indexmap	index map

Definition at line 253 of file dec_stairheur.cpp.

Referenced by freeData(), and rankOrderClustering().

indexmapInit()

static SCIP_RETCODE indexmapInit ( INDEXMAP *  indexmap, gcg::PARTIALDECOMP *  partialdec, int *  hashmapindices  )

static

initialization method for the indexmap for partialdecs

Parameters

indexmap	index map
partialdec	partial decomposition to create indexmap for
hashmapindices	indices of variables and constraints

Definition at line 268 of file dec_stairheur.cpp.

References IndexMap::consindex, gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), gcg::PARTIALDECOMP::getOpenconss(), gcg::PARTIALDECOMP::getOpenvars(), IndexMap::indexcons, IndexMap::indexvar, and IndexMap::varindex.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC(), and rankOrderClustering().

initData()

static SCIP_RETCODE initData ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, DEC_DETECTORDATA *  detectordata  )

static

initialization method of detector data for partialdecs

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use for initialization
detectordata	detector data structure

Definition at line 484 of file dec_stairheur.cpp.

References DEC_DetectorData::blockedAfterrow, gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), DEC_DetectorData::hashmapindices, DEC_DetectorData::ibegin, DEC_DetectorData::iend, DEC_DetectorData::indexmap, indexmapCreate(), DEC_DetectorData::jbegin, DEC_DetectorData::jend, DEC_DetectorData::jmax, DEC_DetectorData::jmin, DEC_DetectorData::maxblocks, DEC_DetectorData::minV, DEC_DetectorData::rowsWithConstrictions, and DEC_DetectorData::width.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

freeData()

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

static

deinitialization method of detector data (called after detection has been finished)

Parameters

scip	SCIP data structure
detectordata	detector data structure

Definition at line 525 of file dec_stairheur.cpp.

References DEC_DetectorData::blockedAfterrow, DEC_DetectorData::constoblock, DEC_DetectorData::hashmapindices, DEC_DetectorData::ibegin, DEC_DetectorData::iend, DEC_DetectorData::indexmap, indexmapFree(), DEC_DetectorData::jbegin, DEC_DetectorData::jend, DEC_DetectorData::jmax, DEC_DetectorData::jmin, DEC_DetectorData::minV, DEC_DetectorData::rowsWithConstrictions, and DEC_DetectorData::width.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

createRowindexList()

static SCIP_RETCODE createRowindexList ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, gcg::DETPROBDATA *  detprobdata, DEC_DETECTORDATA *  detectordata, SCIP_HASHMAP *  indexcons, SCIP_HASHMAP *  varindex, vector< vector< int > > &  rowindices  )

static

creates a nested vector with the indices of the nonzero entries of each row.

example: constraint matrix:

1 1 0 1 0

0 1 1 0 0

0 0 0 0 1

resulting vector: ( (1 2 4) (2 3) (5) )

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use for matrix
detprobdata	detection process information and data
detectordata	detector data data structure
indexcons	hashmap index -> constraint
varindex	hashmap variable -> index
rowindices	vector to store the row indices vector

Definition at line 578 of file dec_stairheur.cpp.

References gcg::PARTIALDECOMP::getNOpenconss(), gcg::DETPROBDATA::getNVarsForCons(), gcg::DETPROBDATA::getVarsForCons(), DEC_DetectorData::hashmapindices, and gcg::PARTIALDECOMP::isVarOpenvar().

Referenced by DEC_DECL_PROPAGATEPARTIALDEC(), rankOrderClustering(), and rankOrderClusteringIteration().

createColumnindexList()

static SCIP_RETCODE createColumnindexList ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, vector< vector< int > > &  rowindices, vector< vector< int > > &  columnindices  )

static

creates a nested vector with the indices of the nonzero entries of each column.

example:

constraint matrix:

1 1 0 1 0

0 1 1 0 0

0 0 0 0 1

resulting vector: ( (1) (1 2) (2) (1) (3) )

Parameters

scip	SCIP data structure
partialdec	partial decomposition to create column index for
rowindices	A vector with the row indices (achieved from calling rowindices_vector() )
columnindices	vector to store the column indices vector

Definition at line 654 of file dec_stairheur.cpp.

References gcg::PARTIALDECOMP::getNOpenvars().

Referenced by DEC_DECL_PROPAGATEPARTIALDEC(), rankOrderClustering(), and rankOrderClusteringIteration().

rowOrdering()

static vector<int> rowOrdering ( SCIP *  scip, vector< vector< int > > &  columnindices, int  nrows  )

static

does the row ordering of the ROC2 algorithm.

It also works for the column ordering. In this case the terms row<->column have to be exchanged.

Returns

A vector with the new row order. E.g. (2 3 1) means the second row comes first now, and so on.

Parameters

scip	SCIP data structure
columnindices	A vector of the nonzero entries in each column
nrows	The number of rows of the constraint matrix (=number of relevant constraints)

Definition at line 695 of file dec_stairheur.cpp.

References SCIPvectorCreateInt().

Referenced by rankOrderClusteringIteration().

formIndexArray()

static SCIP_RETCODE formIndexArray ( int *  begin, int *  end, vector< vector< int > > &  indices  )

static

stores the first and last entry of the i-th column(row) in begin[i] and end[i] respectively.

Parameters

begin	Array to store the first nonzero entry of the i-th column (row)
end	Array to store the last nonzero entry of the i-th column (row)
indices	columnindices vector (rowindices vector)

Definition at line 734 of file dec_stairheur.cpp.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC(), and rankOrderClustering().

arraysAreEqual()

static SCIP_Bool arraysAreEqual ( int *  new_array, int *  old_array, int  num_elements  )

static

returns FALSE if at least one entry of new_array and old_array are different.

Parameters

new_array	new array
old_array	old array
num_elements	length of arrays

Definition at line 764 of file dec_stairheur.cpp.

Referenced by rankOrderClustering().

rankOrderClusteringIteration()

static SCIP_RETCODE rankOrderClusteringIteration ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, gcg::DETPROBDATA *  detprobdata, DEC_DETECTORDATA *  detectordata, INDEXMAP *  inputmap, INDEXMAP *  outputmap  )

static

permutes the order of rows and columns in inputmap and stores the result in outputmap.

One call of this function is equivalent to one iteration of the ROC2-algortihm.

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use for permutation
detprobdata	detection process information and data
detectordata	detector data data structure
inputmap	indexmap for input
outputmap	indexmap for output

Definition at line 787 of file dec_stairheur.cpp.

References IndexMap::consindex, createColumnindexList(), createRowindexList(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), DEC_DetectorData::hashmapindices, IndexMap::indexcons, IndexMap::indexvar, rowOrdering(), SCIPvectorRearrange(), and IndexMap::varindex.

Referenced by rankOrderClustering().

rankOrderClustering()

static SCIP_RETCODE rankOrderClustering ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, gcg::DETPROBDATA *  detprobdata, DEC_DETECTORDATA *  detectordata, int  max_iterations, int *  iterations  )

static

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use for clustering
detprobdata	detection process information and data
detectordata	detector data structure
max_iterations	number of maximal iterations
iterations	number of performed iterations

Definition at line 867 of file dec_stairheur.cpp.

References arraysAreEqual(), createColumnindexList(), createRowindexList(), formIndexArray(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), DEC_DetectorData::hashmapindices, DEC_DetectorData::ibegin, DEC_DetectorData::iend, IndexMap::indexcons, DEC_DetectorData::indexmap, indexmapCreate(), indexmapFree(), indexmapInit(), DEC_DetectorData::jbegin, DEC_DetectorData::jend, rankOrderClusteringIteration(), and IndexMap::varindex.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

rowsWithConstriction()

static SCIP_RETCODE rowsWithConstriction ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, DEC_DETECTORDATA *  detectordata  )

static

finds rows with local minima regarding the number of linking variables and stores them in detectordata->rowsWithConstrictions

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use
detectordata	detector data structure

Definition at line 957 of file dec_stairheur.cpp.

References gcg::PARTIALDECOMP::getNOpenconss(), DEC_DetectorData::minV, and DEC_DetectorData::rowsWithConstrictions.

Referenced by blocking().

assignConsToBlock()

static SCIP_RETCODE assignConsToBlock ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, DEC_DETECTORDATA *  detectordata, int  block, int  first_cons, int  last_cons  )

static

assigns constraints in the interval [first_cons, last_cons] to 'block'. (for partialdecs)

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use
detectordata	detector data structure
block	id of block
first_cons	index of first constraint to assign
last_cons	index of last constraint to assign

Definition at line 980 of file dec_stairheur.cpp.

References DEC_DetectorData::blockedAfterrow, DEC_DetectorData::constoblock, DEC_DetectorData::hashmapindices, IndexMap::indexcons, and DEC_DetectorData::indexmap.

Referenced by blockingDynamic(), and blockingStatic().

getMaxColIndex()

static int getMaxColIndex ( DEC_DETECTORDATA *  detectordata, int  from_row, int  to_row  )

static

returns the largest column index of a nonzero entry between rows [from_row, to_row]

Parameters

detectordata	detector data structure
from_row	index of starting row to check
to_row	index of last row to check

Definition at line 1006 of file dec_stairheur.cpp.

References DEC_DetectorData::iend.

Referenced by blockingDynamic(), and isValidBlocking().

getMinColIndex()

static int getMinColIndex ( DEC_DETECTORDATA *  detectordata, int  row  )

static

returns the column index of the first nonzero entry in 'row'. Rows start counting at 1, not 0.

Parameters

detectordata	detector data structure
row	index of row

Definition at line 1018 of file dec_stairheur.cpp.

References DEC_DetectorData::ibegin.

Referenced by blockingDynamic(), and isValidBlocking().

isValidBlocking()

static SCIP_Bool isValidBlocking ( DEC_DETECTORDATA *  detectordata, int  prev_block_first_row, int  prev_block_last_row, int  block_at_row  )

static

determines if a blocking at 'block_at_row' is a valid blocking

Returns

TRUE if blocking is valid, else FALSE

Parameters

detectordata	detector data structure
prev_block_first_row	first row of the previous block
prev_block_last_row	last row of the previous block
block_at_row	the row for which you want to determine if the blocking is valid

Definition at line 1031 of file dec_stairheur.cpp.

References getMaxColIndex(), and getMinColIndex().

Referenced by nextRowToBlockAt().

findBlockingCandidate()

static vector<int>::iterator findBlockingCandidate ( vector< int >::iterator  it_constrictions, vector< int > *  it_vector, int  min_block_size, int  prev_block_last_row  )

static

this functions looks for rows to block at, which creates block of size min_block_size or bigger

Returns

Iterator pointing to a node which contains a suitable row for blocking; If the iterator points after the last element, no candidate was found

Parameters

it_constrictions	Iterator pointing to a vector of constraints (detectordata->rowsWithConstrictions)
it_vector	minimum number of rows to be in a block
min_block_size	the last row of the preceding block
prev_block_last_row	the last row of the preceding block

Definition at line 1056 of file dec_stairheur.cpp.

Referenced by nextRowToBlockAt().

nextRowToBlockAt()

static vector<int>::iterator nextRowToBlockAt ( DEC_DETECTORDATA *  detectordata, vector< int >::iterator  it_constrictions, vector< int > *  it_vector, int  min_block_size, int  prev_block_first_row, int  prev_block_last_row  )

static

this functions determines the next row to block at

Returns

Iterator pointing to a node which contains a suitable row for blocking; If the iterator points after the last element, no row was found

Parameters

detectordata	detector data structure
it_constrictions	Iterator pointing to a vector of constraints (detectordata->rowsWithConstrictions)
it_vector	vector of constrictions
min_block_size	minimum number of rows to be in a block
prev_block_first_row	the first row of the preceding block
prev_block_last_row	the last row of the preceding block

Definition at line 1085 of file dec_stairheur.cpp.

References findBlockingCandidate(), and isValidBlocking().

Referenced by blockingDynamic().

calculateNdecompositions()

static int calculateNdecompositions ( DEC_DETECTORDATA *  detectordata )

static

calculate the number of decompositions in order to allocate decomps array

Parameters

detectordata

detector data structure

Definition at line 1130 of file dec_stairheur.cpp.

References DEC_DetectorData::blockingassoonaspossible, DEC_DetectorData::dynamicblocking, DEC_DetectorData::maxblocks, DEC_DetectorData::minblocks, DEC_DetectorData::multipledecomps, and DEC_DetectorData::staticblocking.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

checkParameterConsistency()

static void checkParameterConsistency ( DEC_DETECTORDATA *  detectordata, SCIP_RESULT *  result  )

static

check the consistency of the parameters

Parameters

detectordata	detector data structure
result	pointer to store result

Definition at line 1167 of file dec_stairheur.cpp.

References DEC_DetectorData::blockingassoonaspossible, DEC_DetectorData::dynamicblocking, DEC_DetectorData::maxblocks, DEC_DetectorData::minblocks, DEC_DetectorData::multipledecomps, and DEC_DetectorData::staticblocking.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

blockingDynamic()

static SCIP_RETCODE blockingDynamic ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, DEC_DETECTORDATA *  detectordata, int  tau, int  nvars  )

static

tries to dynamically divide the problem into subproblems (blocks)

Parameters

scip	SCIP data structure
partialdec	partial decomposition to use
detectordata	detector data data structure
tau	desired number of blocks
nvars	number of variables in the problem

Definition at line 1197 of file dec_stairheur.cpp.

References assignConsToBlock(), DEC_DetectorData::blockedAfterrow, DEC_DetectorData::blocks, getMaxColIndex(), getMinColIndex(), gcg::PARTIALDECOMP::getNOpenconss(), DEC_DetectorData::maxblocks, nextRowToBlockAt(), and DEC_DetectorData::rowsWithConstrictions.

Referenced by blocking().

blockingStatic()

static SCIP_RETCODE blockingStatic ( SCIP *  scip, gcg::PARTIALDECOMP *  partialdec, DEC_DETECTORDATA *  detectordata  )

static

creates blocks with the same number of rows (for partialdecs)

Parameters

scip	SCIP data structure
partialdec	partial decomposition to create block in
detectordata	detector data data structure

Definition at line 1273 of file dec_stairheur.cpp.

References assignConsToBlock(), DEC_DetectorData::blockedAfterrow, DEC_DetectorData::blocks, gcg::PARTIALDECOMP::getNOpenconss(), and DEC_DetectorData::nconssperblock.

Referenced by blocking().

blockingAsSoonAsPossible()

static SCIP_RETCODE blockingAsSoonAsPossible ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, int  desired_blocks, int  nvars  )

static

Parameters

scip	SCIP data structure
detectordata	detector data data structure
desired_blocks	desired number of blocks
nvars	number of variables in the problem

Definition at line 1331 of file dec_stairheur.cpp.

References DEC_DetectorData::blocks.

Referenced by blocking().

resetDetectordata()

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

static

resets detectordata such that it can be used for the next decomposition

Parameters

scip	SCIP data structure
detectordata	detector data structure

Definition at line 1347 of file dec_stairheur.cpp.

References DEC_DetectorData::constoblock.

Referenced by blocking().

blocking()

static SCIP_RETCODE blocking ( SCIP *  scip, DEC_DETECTORDATA *  detectordata, gcg::PARTIALDECOMP *  partialdec, PARTIALDEC_DETECTION_DATA *  detectiondata, SCIP_Real  time, int  maxndecs, SCIP_RESULT *  result  )

static

Parameters

scip	SCIP data structure
detectordata	detector data structure
partialdec	partialdec to propagate
detectiondata	detection data
time	previous time
maxndecs	capacity of detectiondata->newpartialdecs
result	pointer to store result

Definition at line 1364 of file dec_stairheur.cpp.

References gcg::PARTIALDECOMP::addClockTime(), gcg::PARTIALDECOMP::addDetectorChainInfo(), gcg::PARTIALDECOMP::assignCurrentStairlinking(), gcg::PARTIALDECOMP::assignPartialdecFromConstoblock(), DEC_DetectorData::blockingassoonaspossible, blockingAsSoonAsPossible(), blockingDynamic(), blockingStatic(), DEC_DetectorData::blocks, DEC_DetectorData::constoblock, DEC_DetectorData::desiredblocks, DEC_DetectorData::dynamicblocking, gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), DEC_DetectorData::maxblocks, DEC_DetectorData::minblocks, DEC_DetectorData::multipledecomps, DEC_DetectorData::nconssperblock, Partialdec_Detection_Data::newpartialdecs, Partialdec_Detection_Data::nnewpartialdecs, resetDetectordata(), rowsWithConstriction(), DEC_DetectorData::staticblocking, and DEC_DetectorData::width.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

DEC_DECL_FREEDETECTOR()

static DEC_DECL_FREEDETECTOR ( detectorFreeStairheur  )

static

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

Definition at line 1623 of file dec_stairheur.cpp.

References DEC_DetectorData::constoblock, DEC_DETECTORNAME, DECdetectorGetData(), and DECdetectorGetName().

DEC_DECL_INITDETECTOR()

static DEC_DECL_INITDETECTOR ( detectorInitStairheur  )

static

detector initialization method (called after problem was transformed)

Definition at line 1646 of file dec_stairheur.cpp.

References DEC_DetectorData::blockedAfterrow, DEC_DetectorData::constoblock, DECdetectorGetData(), DEC_DetectorData::hashmapindices, DEC_DetectorData::ibegin, DEC_DetectorData::iend, DEC_DetectorData::indexmap, DEC_DetectorData::jbegin, DEC_DetectorData::jend, DEC_DetectorData::jmax, DEC_DetectorData::jmin, DEC_DetectorData::minV, DEC_DetectorData::rowsWithConstrictions, and DEC_DetectorData::width.

DEC_DECL_PROPAGATEPARTIALDEC()

static DEC_DECL_PROPAGATEPARTIALDEC ( detectorPropagatePartialdecStairheur  )

static

Definition at line 1673 of file dec_stairheur.cpp.

References blocking(), calculateNdecompositions(), checkParameterConsistency(), createColumnindexList(), createRowindexList(), DECdetectorGetData(), formIndexArray(), freeData(), gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), DEC_DetectorData::hashmapindices, DEC_DetectorData::ibegin, DEC_DetectorData::iend, IndexMap::indexcons, DEC_DetectorData::indexmap, indexmapInit(), initData(), DEC_DetectorData::jbegin, DEC_DetectorData::jend, DEC_DetectorData::jmax, DEC_DetectorData::jmin, DEC_DetectorData::maxiterationsROC, DEC_DetectorData::minV, rankOrderClustering(), gcg::PARTIALDECOMP::refineToMaster(), IndexMap::varindex, and DEC_DetectorData::width.

DEC_DECL_SETPARAMFAST() [1/3]

static DEC_DECL_SETPARAMFAST ( setParamAggressiveStairheur  )

static

Definition at line 1802 of file dec_stairheur.cpp.

References DECdetectorGetName().

DEC_DECL_SETPARAMFAST() [2/3]

static DEC_DECL_SETPARAMFAST ( setParamDefaultStairheur  )

static

Definition at line 1818 of file dec_stairheur.cpp.

References DEC_ENABLED, DEC_ENABLEDFINISHING, and DECdetectorGetName().

DEC_DECL_SETPARAMFAST() [3/3]

static DEC_DECL_SETPARAMFAST ( setParamFastStairheur  )

static

Definition at line 1834 of file dec_stairheur.cpp.

References DECdetectorGetName().

SCIPincludeDetectorStairheur()

SCIP_RETCODE SCIPincludeDetectorStairheur

(

SCIP *

scip

)

creates the stairheur detector and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1852 of file dec_stairheur.cpp.

References DEC_DetectorData::blockingassoonaspossible, 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(), DEFAULT_BLOCKINGASSOONASPOSSIBLE, DEFAULT_DESIREDBLOCKS, DEFAULT_DYNAMICBLOCKING, DEFAULT_MAXBLOCKS, DEFAULT_MAXITERATIONSROC, DEFAULT_MINBLOCKS, DEFAULT_MULTIPLEDECOMPS, DEFAULT_NCONSSPERBLOCK, DEFAULT_STATICBLOCKING, DEC_DetectorData::desiredblocks, detectorExitStairheur, detectorFinishPartialdecStairheur, detectorPostprocessPartialdecStairheur, DEC_DetectorData::dynamicblocking, DEC_DetectorData::maxblocks, DEC_DetectorData::maxiterationsROC, DEC_DetectorData::minblocks, DEC_DetectorData::multipledecomps, DEC_DetectorData::nconssperblock, and DEC_DetectorData::staticblocking.

Referenced by SCIPincludeGcgPlugins().