dec_stairheur.cpp
Go to the documentation of this file.
39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 #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 */
65 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
66 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /**< last round the detector gets called while detecting the original problem */
67 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
73 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
79 #define DEFAULT_DESIREDBLOCKS 0 /**< value for the desired number of blocks (for all blocking types). Set to zero for self determination of block number */
82 #define DEFAULT_BLOCKINGASSOONASPOSSIBLE FALSE /**< Enable blocking type 'as soon as possible' */
83 #define DEFAULT_MULTIPLEDECOMPS TRUE /**< Enables multiple decompositions for all enabled blocking types. Ranging from minblocks to maxblocks' */
84 #define DEFAULT_MAXITERATIONSROC 1000000 /**< The maximum of iterations of the ROC-algorithm. -1 for no iteration limit */
94 #define DWSOLVER_REFNAME(name, blocks, cons, dummy) "%s_%d_%d_%.1f_ref.txt", (name), (blocks), (cons), (dummy)
95 #define GP_NAME(name, blocks, cons, dummy) "%s_%d_%d_%.1f_%d.gp", (name), (blocks), (cons), (dummy)
101 /** A struct that contains 4 hashmaps, which maps variables and constraints to their position in the constraint matrix (Ax<=b) and vice versa */
125 int* jmax; /**< array, jmax[i]: the last nonzero entry among all rows prior to and including the i-th row */
126 int* minV; /**< array, minV[i]: number of linking variables corresponding to a partitioning after the i-th row */
128 int* hashmapindices; /**< array with integers running from 0 to maximum(nvars, ncons)+1 (for usage of hash maps) */
135 SCIP_Bool multipledecomps; /**< Enables multiple decompositions for all enabled blocking types. Ranging from minblocks to maxblocks */
177 * 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.
181 * For some instances the assertion regarding the consistency of the arrays ibegin and jbegin fails
282 /* careful: hashmapindex+1, because '0' is treated as an empty hashmap entry, which causes an error */
293 /* careful: hashmapindex+1, because '0' is treated as an empty hashmap entry, which causes an error */
296 SCIP_CALL( SCIPhashmapInsert(indexmap->indexcons, (void*) hashmapindex, (void*)(size_t) cons) );
298 SCIP_CALL( SCIPhashmapInsert(indexmap->consindex, (void*)(size_t) cons, (void*) hashmapindex) );
326 static void checkConsistencyOfIndexarrays(DEC_DETECTORDATA* detectordata, int nvars, int nconss)
408 fprintf(output, "set terminal pdf\nset output \"%s\"\nunset xtics\nunset ytics\nunset border\nset pointsize 0.05\nset xrange [0:%i]\nset yrange[%i:0]\nplot '%s' lt 0 pt 5 notitle", pdffile, SCIPgetNVars(scip), nconss, datafile);
413 /** creates a data and a gnuplot file for the graph representing the array minV (number of linking variables).
466 for( it1 = detectordata->blockedAfterrow->begin(); it1 != detectordata->blockedAfterrow->end(); ++it1 )
474 fprintf(output, "set terminal pdf\nset output \"%s\"\nset style line 1 lt 1 lc rgb \"black\"\nplot '%s' title '# verb. Variablen' ls 1 with lines, \\\n '%s' lt 0 pt 4 with points title \"Blockgrenze\"", pdffile, datafile, blockingfile);
509 SCIP_CALL( SCIPallocMemoryArray(scip, &detectordata->hashmapindices, (size_t)MAX(nvars, nconss) + 1) );
610 probindices[j] = *(int*) SCIPhashmapGetImage(varindex, (void*)(size_t)detprobdata->getVarsForCons(cons)[j]);
657 vector<vector<int> > &rowindices, /**< A vector with the row indices (achieved from calling rowindices_vector() ) */
691 * It also works for the column ordering. In this case the terms row<->column have to be exchanged.
693 * @return A vector with the new row order. E.g. (2 3 1) means the second row comes first now, and so on. */
728 /** stores the first and last entry of the i-th column(row) in begin[i] and end[i] respectively.
815 SCIP_CALL( createRowindexList(scip, partialdec, detprobdata, detectordata, inputmap->indexcons, inputmap->varindex, rowindices) );
837 SCIP_CALL( SCIPhashmapSetImage(outputmap->consindex, (void*)(size_t) cons, (void*) hashmapindex) );
841 SCIP_CALL( SCIPhashmapSetImage(outputmap->indexcons, (void*) hashmapindex, (void*)(size_t) cons) );
845 for( it1 = columnorder.begin(), i = 0; it1 != columnorder.end() &&i < (size_t) nvars; ++i, ++it1 )
855 SCIP_CALL( SCIPhashmapSetImage(outputmap->varindex, (void*)(size_t) var, (void*) hashmapindex) );
859 SCIP_CALL( SCIPhashmapSetImage(outputmap->indexvar, (void*) hashmapindex, (void*)(size_t) var) );
916 SCIP_CALL( rankOrderClusteringIteration(scip, partialdec, detprobdata, detectordata, detectordata->indexmap, indexmap_permuted) );
919 SCIP_CALL( createRowindexList(scip, partialdec, detprobdata, detectordata, indexmap_permuted->indexcons, indexmap_permuted->varindex, rowindices) );
955 /** finds rows with local minima regarding the number of linking variables and stores them in detectordata->rowsWithConstrictions */
969 if( detectordata->minV[i] < detectordata->minV[i-1] && detectordata->minV[i] < detectordata->minV[i+1] )
978 /** assigns constraints in the interval [first_cons, last_cons] to 'block'. (for partialdecs) */
995 int cons = (int)(size_t) SCIPhashmapGetImage(detectordata->indexmap->indexcons, (void*) hashmapindex);
998 SCIP_CALL( SCIPhashmapInsert(detectordata->constoblock, (void*)(size_t) cons, (void*) (size_t) (detectordata->hashmapindices[block])) );
1013 return std::max_element(detectordata->iend + (from_row), detectordata->iend+((size_t)to_row + 1))-detectordata->iend; /*lint !e712*/
1016 /** returns the column index of the first nonzero entry in 'row'. Rows start counting at 1, not 0. */
1046 last_column_prev_block = getMaxColIndex(detectordata, prev_block_first_row, prev_block_last_row);
1051 /** this functions looks for rows to block at, which creates block of size min_block_size or bigger
1053 * @return Iterator pointing to a node which contains a suitable row for blocking; If the iterator points after the last element, no candidate was found
1057 vector<int>::iterator it_constrictions, /**< Iterator pointing to a vector of constraints (detectordata->rowsWithConstrictions) */
1070 /* does a blocking to the next row forming a constriction comprise more rows than min_block_size */
1082 * @return Iterator pointing to a node which contains a suitable row for blocking; If the iterator points after the last element, no row was found
1087 vector<int>::iterator it_constrictions, /**< Iterator pointing to a vector of constraints (detectordata->rowsWithConstrictions) */
1104 it_constrictions = findBlockingCandidate(it_constrictions, it_vector, min_block_size, prev_block_last_row);
1114 if( isValidBlocking(detectordata, prev_block_first_row, prev_block_last_row, *it_constrictions) )
1187 if( ! detectordata->blockingassoonaspossible && ! detectordata->staticblocking &&! detectordata->dynamicblocking )
1222 min_block_size = (int) SCIPround(scip, ((SCIP_Real)partialdec->getNOpenconss()) / (2.0 * tau ));
1225 for( it1 = nextRowToBlockAt(detectordata, it1, detectordata->rowsWithConstrictions, min_block_size, prev_block_first_row, prev_block_last_row);
1227 it1 = nextRowToBlockAt(detectordata, it1, detectordata->rowsWithConstrictions, min_block_size, prev_block_first_row, prev_block_last_row) )
1233 SCIPdebugMessage("vars in block: %i - %i, linking vars: %i - %i\n", max_col_index_im1+1, max_col_index_i, min_col_index_ip1, max_col_index_i);
1236 SCIP_CALL( assignConsToBlock(scip, partialdec, detectordata, block, prev_block_last_row + 1, current_row) );
1246 /* assign the remaining (< M/2tau) cons and vars to the last block; no new linking vars are added */
1248 SCIPdebugMessage("last time: vars in block: %i - %i, linking vars: %i - %i\n", max_col_index_im1+1, nvars, nvars+1, nvars);
1250 SCIP_CALL( assignConsToBlock(scip, partialdec, detectordata, block, prev_block_last_row + 1, SCIPgetNConss(scip)) );
1297 SCIPdebugMessage("Blocking from %d to %d in block %d",prev_block_last_row + 1, current_row, block);
1298 SCIP_CALL( assignConsToBlock(scip, partialdec, detectordata, block, prev_block_last_row + 1, current_row) );
1307 SCIPdebugMessage("last time: assignVarsToBlock: block, from_row, to_row: %i, %i, %i\n", block, prev_block_last_row + 1, SCIPgetNConss(scip));
1309 SCIP_CALL( assignConsToBlock(scip, partialdec, detectordata, block, prev_block_last_row + 1, nconss) );
1358 SCIP_CALL( SCIPhashmapCreate(&(detectordata->constoblock), SCIPblkmem(scip), SCIPgetNConss(scip)) );
1405 SCIPdebugMessage("detectordata->enablemultipledecomps = 0. detectordata->desiredblocks == 0. Calculating tau = %i\n", tau);
1434 SCIPdebugMessage("detectordata->enablemultipledecomps = %ud.\n", detectordata->multipledecomps);
1457 SCIP_CALL(detectiondata->newpartialdecs[*nnewpartialdecs]->assignPartialdecFromConstoblock(detectordata->constoblock, detectordata->blocks) );
1481 SCIP_CALL(detectiondata->newpartialdecs[*nnewpartialdecs]->assignPartialdecFromConstoblock(detectordata->constoblock, detectordata->blocks) );
1508 SCIPdebugMessage("nconssperblock = %i, dec = %i\n", detectordata->nconssperblock, *nnewpartialdecs);
1516 SCIP_CALL(detectiondata->newpartialdecs[*nnewpartialdecs]->assignPartialdecFromConstoblock(detectordata->constoblock, detectordata->blocks) );
1536 SCIPdebugMessage("detectordata->blockingassoonaspossible = %ud. \n", detectordata->blockingassoonaspossible);
1557 SCIP_CALL(detectiondata->newpartialdecs[*nnewpartialdecs]->assignPartialdecFromConstoblock(detectordata->constoblock, detectordata->blocks) );
1579 SCIP_CALL(detectiondata->newpartialdecs[*nnewpartialdecs]->assignPartialdecFromConstoblock(detectordata->constoblock, detectordata->blocks) );
1693 SCIPwarningMessage(scip, "WRITEALLOUTPUT in detector stairheur is not implemented for partialdecs.\n");
1718 SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nPartialdecs) );
1722 /* initialize hash maps for keeping track of variables and constraints and their corresponding indices after being permuted by the ROC2-algorithm */
1733 SCIP_CALL( createRowindexList(scip, partialdec, partialdecdetectiondata->detprobdata, detectordata, detectordata->indexmap->indexcons, detectordata->indexmap->varindex, rowindices) );
1747 SCIP_CALL( rankOrderClustering(scip, partialdec, partialdecdetectiondata->detprobdata, detectordata, detectordata->maxiterationsROC, &ROC_iterations) );
1750 //if( ROC_iterations < detectordata->maxiterationsROC || detectordata->maxiterationsROC == -1 )
1755 SCIP_CALL( rankOrderClustering(scip, partialdec, partialdecdetectiondata->detprobdata, detectordata, detectordata->maxiterationsROC, NULL) );
1776 SCIP_CALL( blocking(scip, detectordata, partialdec, partialdecdetectiondata, temptime, nPartialdecs, result) );
1780 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " found %d partialdecs.\n", partialdecdetectiondata->nnewpartialdecs);
1789 SCIP_CALL( SCIPreallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), partialdecdetectiondata->nnewpartialdecs) );
1864 SCIP_CALL( DECincludeDetector(scip, DEC_DETECTORNAME, DEC_DECCHAR, DEC_DESC, DEC_FREQCALLROUND, DEC_MAXCALLROUND, DEC_MINCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_ENABLED, DEC_ENABLEDFINISHING,DEC_ENABLEDPOSTPROCESSING, DEC_SKIP, DEC_USEFULRECALL,
1865 detectordata, detectorFreeStairheur, detectorInitStairheur, detectorExitStairheur, detectorPropagatePartialdecStairheur, detectorFinishPartialdecStairheur, detectorPostprocessPartialdecStairheur, setParamAggressiveStairheur, setParamDefaultStairheur, setParamFastStairheur) );
1875 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/stairheur/minblocks", "The minimal number of blocks",
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
Definition: class_partialdecomp.cpp:286
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
Definition: cons_decomp.cpp:2618
structure information for decomposition information in GCG projects
GCG interface methods.
static SCIP_Bool isValidBlocking(DEC_DETECTORDATA *detectordata, int prev_block_first_row, int prev_block_last_row, int block_at_row)
Definition: dec_stairheur.cpp:1031
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4198
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
static SCIP_Bool arraysAreEqual(int *new_array, int *old_array, int num_elements)
Definition: dec_stairheur.cpp:764
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)
Definition: dec_stairheur.cpp:578
static SCIP_RETCODE createColumnindexList(SCIP *scip, gcg::PARTIALDECOMP *partialdec, vector< vector< int > > &rowindices, vector< vector< int > > &columnindices)
Definition: dec_stairheur.cpp:654
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
Definition: class_partialdecomp.cpp:4721
Definition: dec_stairheur.cpp:102
static SCIP_RETCODE blockingDynamic(SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata, int tau, int nvars)
Definition: dec_stairheur.cpp:1197
SCIP_RETCODE SCIPincludeDetectorStairheur(SCIP *scip)
Definition: dec_stairheur.cpp:1852
detector for staircase structures via ROC algorithms
static DEC_DECL_FREEDETECTOR(detectorFreeStairheur)
Definition: dec_stairheur.cpp:1623
various SCIP helper methods
#define detectorPostprocessPartialdecStairheur
Definition: dec_stairheur.cpp:1798
static SCIP_RETCODE initData(SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata)
Definition: dec_stairheur.cpp:484
static SCIP_RETCODE rankOrderClustering(SCIP *scip, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata, int max_iterations, int *iterations)
Definition: dec_stairheur.cpp:867
#define DEFAULT_BLOCKINGASSOONASPOSSIBLE
Definition: dec_stairheur.cpp:82
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
Definition: cons_decomp.cpp:2609
static SCIP_RETCODE indexmapCreate(SCIP *scip, INDEXMAP **indexmap, int nconss, int nvars)
Definition: dec_stairheur.cpp:228
static vector< int > SCIPvectorCreateInt(int from, int to)
Definition: dec_stairheur.cpp:187
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
static SCIP_RETCODE indexmapInit(INDEXMAP *indexmap, gcg::PARTIALDECOMP *partialdec, int *hashmapindices)
Definition: dec_stairheur.cpp:268
const int * getOpenconss()
Gets array containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4247
static vector< int > rowOrdering(SCIP *scip, vector< vector< int > > &columnindices, int nrows)
Definition: dec_stairheur.cpp:695
Definition: class_detprobdata.h:106
static SCIP_RETCODE blockingStatic(SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata)
Definition: dec_stairheur.cpp:1273
static SCIP_RETCODE formIndexArray(int *begin, int *end, vector< vector< int > > &indices)
Definition: dec_stairheur.cpp:734
static SCIP_RETCODE resetDetectordata(SCIP *scip, DEC_DETECTORDATA *detectordata)
Definition: dec_stairheur.cpp:1347
static SCIP_RETCODE blocking(SCIP *scip, DEC_DETECTORDATA *detectordata, gcg::PARTIALDECOMP *partialdec, PARTIALDEC_DETECTION_DATA *detectiondata, SCIP_Real time, int maxndecs, SCIP_RESULT *result)
Definition: dec_stairheur.cpp:1364
gcg::PARTIALDECOMP ** newpartialdecs
Definition: class_detprobdata.h:676
#define detectorFinishPartialdecStairheur
Definition: dec_stairheur.cpp:1797
static DEC_DECL_INITDETECTOR(detectorInitStairheur)
Definition: dec_stairheur.cpp:1646
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
static int getMinColIndex(DEC_DETECTORDATA *detectordata, int row)
Definition: dec_stairheur.cpp:1018
static SCIP_RETCODE freeData(SCIP *scip, DEC_DETECTORDATA *detectordata)
Definition: dec_stairheur.cpp:525
static int getMaxColIndex(DEC_DETECTORDATA *detectordata, int from_row, int to_row)
Definition: dec_stairheur.cpp:1006
Definition: dec_compgreedily.cpp:73
class storing (potentially incomplete) decompositions
SCIP_Bool blockingassoonaspossible
Definition: dec_stairheur.cpp:134
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)
Definition: dec_stairheur.cpp:1085
static void checkParameterConsistency(DEC_DETECTORDATA *detectordata, SCIP_RESULT *result)
Definition: dec_stairheur.cpp:1167
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
Definition: class_detprobdata.cpp:963
static DEC_DECL_PROPAGATEPARTIALDEC(detectorPropagatePartialdecStairheur)
Definition: dec_stairheur.cpp:1673
const int * getOpenvars()
Gets array containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4259
static SCIP_RETCODE assignConsToBlock(SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata, int block, int first_cons, int last_cons)
Definition: dec_stairheur.cpp:980
static void indexmapFree(SCIP *scip, INDEXMAP **indexmap)
Definition: dec_stairheur.cpp:253
class storing partialdecs and the problem matrix
static DEC_DECL_SETPARAMFAST(setParamAggressiveStairheur)
Definition: dec_stairheur.cpp:1802
static SCIP_RETCODE rankOrderClusteringIteration(SCIP *scip, gcg::PARTIALDECOMP *partialdec, gcg::DETPROBDATA *detprobdata, DEC_DETECTORDATA *detectordata, INDEXMAP *inputmap, INDEXMAP *outputmap)
Definition: dec_stairheur.cpp:787
static SCIP_RETCODE rowsWithConstriction(SCIP *scip, gcg::PARTIALDECOMP *partialdec, DEC_DETECTORDATA *detectordata)
Definition: dec_stairheur.cpp:957
static SCIP_RETCODE blockingAsSoonAsPossible(SCIP *scip, DEC_DETECTORDATA *detectordata, int desired_blocks, int nvars)
Definition: dec_stairheur.cpp:1331
static void SCIPvectorRearrange(vector< vector< int > > &l, vector< int > order)
Definition: dec_stairheur.cpp:209
static int calculateNdecompositions(DEC_DETECTORDATA *detectordata)
Definition: dec_stairheur.cpp:1130
vector< int > * rowsWithConstrictions
Definition: dec_stairheur.cpp:129
static vector< int >::iterator findBlockingCandidate(vector< int >::iterator it_constrictions, vector< int > *it_vector, int min_block_size, int prev_block_last_row)
Definition: dec_stairheur.cpp:1056
public methods for working with decomposition structures