class_partialdecomp.cpp
Go to the documentation of this file.
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
82 const int PARTIALDECOMP::primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
83 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
84 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349};
95 mastervars( 0 ), conssforblocks( 0 ), varsforblocks( 0 ), linkingvars( 0 ), stairlinkingvars( 0 ),
96 ncoeffsforblock(std::vector<int>(0)), calculatedncoeffsforblock(FALSE), ncoeffsforblockformastercons(0),
99 masterconsssorted(true), hashvalue( 0 ), hvoutdated(true), isselected( false ), isagginfoalreadytoexpensive(false), isfinishedbyfinisher( false ),
100 nrepblocks(0), reptoblocks(std::vector<std::vector<int>>(0)), blockstorep(std::vector<int>(0) ), pidtopidvarmaptofirst(std::vector<std::vector<std::vector<int> > >(0)),
102 pctvarstoblock( 0 ), pctvarsfromfree( 0 ), pctconsstoborder( 0 ), pctconsstoblock( 0 ), pctconssfromfree( 0 ),
103 nnewblocks( 0 ), usedpartition(0 ), classestomaster(0 ), classestolinking(0 ), listofancestorids(0 ),
106 setpartfwhitescore(-1.), maxforeseeingwhitescoreagg(-1.), setpartfwhitescoreagg(-1.), bendersscore(-1.), strongdecompositionscore(-1.),
302 pctconssfromfree.push_back( getNConss() != 0 ? ( ancestor->getNOpenconss() - getNOpenconss() ) / (SCIP_Real) getNConss() : 0. );
303 pctvarsfromfree.push_back( getNVars() != 0 ? ( ancestor->getNOpenvars() - getNOpenvars() ) / (SCIP_Real) getNVars() : 0. );
305 ( - getNOpenconss() - getNMasterconss() + ancestor->getNOpenconss() + ancestor->getNMasterconss() ) / getNConss() : 0. );
306 pctvarstoblock.push_back( getNVars() != 0 ? ( - getNOpenvars() - getNMastervars() - getNLinkingvars() - getNTotalStairlinkingvars() + ancestor->getNOpenvars()
307 + ancestor->getNMastervars() + ancestor->getNLinkingvars() + ancestor->getNTotalStairlinkingvars() ) / getNVars() : 0. );
308 pctconsstoborder.push_back( getNConss() != 0 ? ( getNMasterconss() - ancestor->getNMasterconss() ) / (SCIP_Real) getNConss() : 0. );
309 pctvarstoborder.push_back( getNVars() != 0 ? ( getNMastervars() + getNLinkingvars() + getNTotalStairlinkingvars() - ancestor->getNMastervars()
310 - ancestor->getNLinkingvars() - ancestor->getNTotalStairlinkingvars() ) / (SCIP_Real) getNVars() : 0. );
412 if( (int) (size_t) SCIPhashmapGetImage( constoblock, (void*) (size_t) cons ) - 1 == givenNBlocks )
485 std::vector<int> blocksOfStairlinkingvars; /* first block of the stairlinkingvars which can be found in the conss */
522 std::vector<int>::iterator lb = lower_bound( stairlinkingvars[b].begin(), stairlinkingvars[b].end(), var2 );
856 consblock = oldNBlocks + ( (int) (size_t) SCIPhashmapGetImage( constoblock, (void*) (size_t) cons ) - 1 );
1005 std::vector<int>::iterator consiter = std::lower_bound(constoconsider.begin(), constoconsider.end(), cons);
1088 SCIPdebugMessage("Checking if agg info is too expensive for blocks %d and %d, nconss: %d, nvars: %d . \n", b1, b2, getNConssForBlock(b2), getNVarsForBlock(b2) );
1091 SCIPdebugMessage("Calculating agg info is too expensive, nconss: %d, nvars: %d . \n", getNConssForBlock(b2), getNVarsForBlock(b2) );
1328 std::vector< std::pair< int, std::vector< int > > > blocksOfVars = findLinkingVarsPotentiallyStairlinking( );
1330 /* if there are no vars that are potentially stairlinking, return without further calculations */
1336 /* create block graph: every block is represented by a node and two nodes are adjacent if there exists a
1354 bool isstaircase = true; /* maintains information whether staircase structure is still possible */
1356 std::vector< bool > marks( getNBlocks() ); /* a node is marked if its degree is zero or it is reachable from a source */
1376 /* secondly, check whether there exists a circle in the graph by moving along all paths starting from a source */
1455 /* if the block is the source of an yet unconsidered path, assign whole path to ascending new block ids */
1559 SCIPwarningMessage(scip, "In (partialdec %d) nblocks %d and size of conssforblocks %ld are not identical! \n" , id, nblocks, conssforblocks.size() );
1566 SCIPwarningMessage(scip, "In (partialdec %d) nblocks %d and size of varsforblocks %ld are not identical! \n" , id, nblocks, varsforblocks.size() );
1587 SCIPwarningMessage(scip, "In (partialdec %d) linking variable with index %d is already assigned! \n" , id, * varIter );
1602 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is already assigned but also assigned to block %d! \n" , id, * varIter, b );
1615 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is already assigned but also assigned to master! \n" , id, * varIter);
1630 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is already assigned but also assigned to stairlinking block %d! \n" , id, * varIter, b );
1638 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is is as assigned as stairlinking var of last block! \n" , id, * varIter );
1649 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is not assigned and not an open var! \n" , id, v );
1660 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is an open var but assigned! \n" , id, openvars[i] );
1670 SCIPwarningMessage(scip, "In (partialdec %d) variable with index %d is causes asynchronity with isvaropen array ! \n" , id, openvars[i] );
1687 SCIPwarningMessage(scip, "In (partialdec %d) constraint with index %d is at least two times assigned as a master constraint! \n" , id, * consIter );
1701 SCIPwarningMessage(scip, "In (partialdec %d) constraint with index %d is already assigned but also assigned to block %d! \n" , id, * consIter, b );
1714 SCIPwarningMessage(scip, "In (partialdec %d) constraint with index %d is not assigned and not an open cons! \n" , id, v );
1725 SCIPwarningMessage(scip, "In (partialdec %d) constraint with index %d is an open cons but assigned! \n" , id, openconss[i] );
1739 SCIPwarningMessage(scip, "In (partialdec %d) variables of block %d are not sorted! \n" , id, b );
1753 SCIPwarningMessage(scip, "In (partialdec %d) stairlinking variables of block %d are not sorted! \n" , id, b );
1789 SCIPwarningMessage(scip, "In (partialdec %d) constraints of block %d are not sorted! \n" , id, b );
1818 if( !(isVarBlockvarOfBlock(varid, b) || isVarLinkingvar(varid) || isVarStairlinkingvarOfBlock(varid, b)
1826 "This should only happen during translation of (partial) decompositions from orginal to transformed problem, and means that translation has failed for this particaluar partial decomposition. Variable %d is not part of block %d or linking or open as constraint %d suggests! \n ", varid, b,
1954 SCIPdebugMessage("--> obj differs for var %s and var %s!\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
1959 SCIPdebugMessage("--> lb differs for var %s and var %s!\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
1964 SCIPdebugMessage("--> ub differs for var %s and var %s!\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
1969 SCIPdebugMessage("--> type differs for var %s and var %s!\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
1976 if( !SCIPisEQ(scip, detprobdata->getVal(getMasterconss()[mc], getVarsForBlock(b1)[i]), detprobdata->getVal(getMasterconss()[mc], getVarsForBlock(b2)[i]) ))
1978 SCIPdebugMessage("--> master coefficients differ for var %s (%f) and var %s (%f) !\n", SCIPvarGetName(
1979 detprobdata->getVar(getVarsForBlock(b1)[i]) ), detprobdata->getVal(getMasterconss()[mc], getVarsForBlock(b1)[i]), SCIPvarGetName(
1980 detprobdata->getVar(getVarsForBlock(b2)[i])), detprobdata->getVal(getMasterconss()[mc], getVarsForBlock(b2)[i]) );
2008 SCIPdebugMessage("--> nvars differs for cons %s and cons %s!\n", SCIPconsGetName(cons1), SCIPconsGetName(cons2));
2014 SCIPdebugMessage("--> lhs differs for cons %s and cons %s!\n", SCIPconsGetName(cons1), SCIPconsGetName(cons2));
2020 SCIPdebugMessage("--> rhs differs for cons %s and cons %s!\n", SCIPconsGetName(cons1), SCIPconsGetName(cons2));
2033 SCIPdebugMessage("--> coefs differ for cons %s and cons %s!\n", SCIPconsGetName(cons1), SCIPconsGetName(cons2));
2041 if( varmap[detprobdata->getVarsForCons(cons2id)[v]] != detprobdata->getVarsForCons(cons1id)[v])
2045 SCIPdebugMessage("--> vars differ for cons %s and cons %s!\n", SCIPconsGetName(cons1), SCIPconsGetName(cons2));
2133 // assign the open components to the master (without removing them to avoid screwing with the vector indices)
2424 if( varinblocks.size() == 1 ) /* if the variable can be found in one block set the variable to a variable of the block*/
2430 else if( varinblocks.size() == 2 ) /* if the variable can be found in two blocks check if it is a linking var or a stairlinking var*/
2445 else if( varinblocks.size() > 2 ) /* if the variable can be found in more than two blocks it is a linking var */
2503 /* check if all vars of the constraint are a block var of the current block, an open var, a linkingvar or a mastervar*/
2511 || ( j != 0 && isVarStairlinkingvarOfBlock( detprobdata->getVarsForCons( openconss[i] )[k], j - 1 ) ) )
2521 consGotBlockcons = false; /* the constraint can't be constraint of the block, check the next block */
2529 for( size_t k = 0; k < vecOpenvarsOfBlock.size(); ++ k ) /* the openvars in the constraint get block vars */
2592 std::vector<int>::iterator todelete = lower_bound( masterconss.begin(), masterconss.end(), consid );
2678 /* also assign open constraints that only have vars assigned to one single block and no open vars*/
2795 bool variables /* if TRUE a block is only considered to be empty if it contains neither constraints or variables */
2954 std::cout << " Max-foreseeing-white-aggregated-score: " << maxforeseeingwhitescoreagg << std::endl;
2959 std::cout << " PPC-max-foreseeing-white-aggregated-score: " << setpartfwhitescoreagg << std::endl;
2970 std::cout << " PARTIALDECOMP is for the " << (original ? "original" : "presolved" ) << " problem and "
2980 std::cout << " PARTIALDECOMP stems from the " << ( stemsfromorig ? "original" : "presolved" ) << " problem." << std::endl;
2991 std::cout << " " << getNDetectors() << " detector" << ( getNDetectors() > 1 ? "s" : "" ) << " worked on this partialdec:";
3217 std::cout << " cons with name " << SCIPconsGetName(detprobdata->getCons(consid)) << " is no setppccard constraint." << std::endl;
3339 assert( (int) (size_t) SCIPhashmapGetImage( constoblock, (void*) (size_t) c ) - 1 <= nblocks );
3374 for( int l = 0; l < detprobdata->getNVarsForCons( conssforblocks[b][k] ) && ! varInBlock; ++ l )
3384 if( varinblocks.size() == 1 ) /* if the var can be found in one block set the var to block var */
3386 else if( varinblocks.size() == 2 ) /* if the variable can be found in two blocks check if it is a linking var or a stairlinking var*/
3393 else if( varinblocks.size() > 2 ) /* if the variable can be found in more than two blocks it is a linking var */
3535 std::vector< std::pair< int, std::vector< int > > > PARTIALDECOMP::findLinkingVarsPotentiallyStairlinking(
3717 output << " % newly assigned constraints: " << getPctConssFromFree( detectorchainindex ) << std::endl;
3719 output << " % constraints the detector assigned to border: " << getPctConssToBorder( detectorchainindex ) << std::endl;
3721 output << " % constraints the detector assigned to blocks: " << getPctConssToBlock( detectorchainindex ) << std::endl;
3723 output << " % newly assigned variables: " << getPctVarsFromFree( detectorchainindex ) << std::endl;
3725 output << " % variables the detector assigned to border: " << getPctVarsToBorder( detectorchainindex ) << std::endl;
3727 output << " % variables the detector assigned to blocks: " << getPctVarsToBlock( detectorchainindex ) << std::endl;
4484 std::vector<int>::iterator lb = lower_bound( varsforblocks[block].begin(), varsforblocks[block].end(), varid );
4507 std::vector<int>::iterator lb = lower_bound( conssforblocks[block].begin(), conssforblocks[block].end(), cons );
4561 if( getNMasterconss() != other->getNMasterconss() || getNMastervars() != other->getNMastervars()
4653 std::vector<DEC_DETECTOR*>::const_iterator iter = std::find(detectorchain.begin(), detectorchain.end(), detector);
4691 std::vector<int>::iterator lb = lower_bound(varsforblocks[block].begin(), varsforblocks[block].end(), var);
4736 std::vector<int>::iterator lb = lower_bound(stairlinkingvars[b].begin(), stairlinkingvars[b].end(), var);
4751 std::vector<int>::iterator lb = lower_bound(stairlinkingvars[block].begin(), stairlinkingvars[block].end(), var);
4807 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "%s\n", usedpartition[i]->getClassName(classid));
4826 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "%s : %s\n", usedpartition[i]->getClassName(classid), usedpartition[i]->getClassDescription(classid));
4833 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "%s : %s\n", usedpartition[i]->getClassName(classid), usedpartition[i]->getClassDescription(classid));
5386 SCIPinfoMessage(scip, NULL, "Please note that the generated pdf file was not deleted automatically! \n");
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
Definition: class_partialdecomp.cpp:286
void removeAncestorID(int ancestorid)
Definition: class_partialdecomp.cpp:3625
void setFinishedByFinisher(bool finished)
sets whether this partialdec was finished by a finishing detector
Definition: class_partialdecomp.cpp:5009
bool isConsSetppc(int consindexd)
is cons with specified index partitioning packing, or covering constraint?
Definition: class_detprobdata.cpp:991
int getNConss()
returns the number of variables considered in the detprobdata
Definition: class_detprobdata.cpp:796
bool aggInfoCalculated()
Checks if the aggregation information was already calculated.
Definition: class_partialdecomp.cpp:5634
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
Definition: cons_decomp.cpp:2618
SCIP_Bool hasSetppMaster()
checks iff all master constraints set partitioning, or set packing constraints
Definition: class_partialdecomp.cpp:3250
structure information for decomposition information in GCG projects
SCIP_RETCODE GCGconshdlrDecompCalcSetPartForseeingWhiteScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the setpartitioning maximum foreseeing white area score of a partialdec
Definition: cons_decomp.cpp:4437
std::vector< int > & getMastervars()
Gets array containing all master vars indices.
Definition: class_partialdecomp.cpp:3998
bool isVarStairlinkingvar(int var)
Checks whether the var is a stairlinking var.
Definition: class_partialdecomp.cpp:4730
std::vector< int > & getVarsForBlock(int block)
Gets array containing vars of a block.
Definition: class_partialdecomp.cpp:4470
void fixVarToMaster(int var)
adds a variable to the master variables
Definition: class_partialdecomp.cpp:5210
SCIP_RETCODE GCGconshdlrDecompCalcStrongDecompositionScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the strong decomposition score of a partialdec
Definition: cons_decomp.cpp:4523
void setVarToStairlinking(int varToStairLinking, int block1, int block2)
adds a variable to the stairlinking variables, does not delete this var from list of open vars
Definition: class_partialdecomp.cpp:5234
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4198
std::vector< int > & getOpenvarsVec()
Definition: class_partialdecomp.cpp:4265
void copyPartitionStatistics(const PARTIALDECOMP *otherpartialdec)
copies the given partialdec's partition statistics
Definition: class_partialdecomp.cpp:2784
SCIP_RETCODE GCGconshdlrDecompCalcClassicScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the classic score of a partialdec
Definition: cons_decomp.cpp:4005
std::vector< int >::const_iterator fixConsToMaster(std::vector< int >::const_iterator itr)
fixes a constraint to the master constraints
Definition: class_partialdecomp.cpp:4938
void setMaxForWhiteAggScore(SCIP_Real score)
set the maximum foreseeing white area score with respect to aggregatable blocks
Definition: class_partialdecomp.cpp:5575
std::vector< int > & getConssForCons(int consIndex)
return array of constraint indices that have a common variable with the given constraint
Definition: class_detprobdata.cpp:706
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
void setAncestorList(std::vector< int > &newlist)
Definition: class_partialdecomp.cpp:3608
USERGIVEN
enumeration to display if a decomposition was given by the user and if so, how it was processed after...
Definition: class_partialdecomp.h:61
SCIP_Real getPctVarsFromFree(int detectorchainindex)
Gets fraction of variables that are not longer open for a detector.
Definition: class_partialdecomp.cpp:4320
SCIP_Real getPctConssFromFree(int detectorchainindex)
Gets fraction of constraints that are not longer open for a detector.
Definition: class_partialdecomp.cpp:4392
void setNBlocks(int nblocks)
sets number of blocks, only increasing number allowed
Definition: class_partialdecomp.cpp:5025
void setFinishedByFinisherOrig(bool finished)
sets whether this partialdec was finished by a finishing detector in the original problem
Definition: class_partialdecomp.cpp:5017
std::vector< int > & getOpenconssVec()
Gets a vector containing constraint ids not assigned yet as vector.
Definition: class_partialdecomp.cpp:4253
bool checkAllConssAssigned()
checks if all conss are assigned
Definition: class_partialdecomp.cpp:1511
void setVarToMaster(int varToMaster)
adds a variable to the master variables, does not delete this var from list of open vars
Definition: class_partialdecomp.cpp:5198
SCIP_Real getMaxForWhiteAggScore()
gets the maximum foreseeing white area score with respect to aggregatable blocks
Definition: class_partialdecomp.cpp:5570
void displayInfo(int detailLevel)
displays the relevant information of the partialdec
Definition: class_partialdecomp.cpp:2933
void writeVisualizationFile(char *filename, char *outname, GP_OUTPUT_FORMAT outputformat=GP_OUTPUT_FORMAT_PDF)
writes a gp visualization of the partialdec to a file
Definition: class_partialdecomp.cpp:5416
int getNCoeffsForMaster()
Definition: class_partialdecomp.cpp:4015
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
Definition: class_partialdecomp.cpp:4721
virtual double getEdgeWeight(int node_i, int node_j)
Definition: graph_gcg.cpp:704
std::vector< SCIP_Real > & getPctConssToBlockVector()
Gets fraction of constraints assigned to a block for detectors in detectorchain.
Definition: class_partialdecomp.cpp:4378
void setPctVarsToBlockVector(std::vector< SCIP_Real > &newvector)
set statistical vector of fractions of variables assigned to a block per involved detector
Definition: class_partialdecomp.cpp:4312
int getVarProbindexForBlock(int varid, int block)
Gets index in variables array of a block for a variable.
Definition: class_partialdecomp.cpp:4479
bool isVarBlockvarOfBlock(int var, int block)
Checks whether the var is assigned to the block.
Definition: class_partialdecomp.cpp:4683
Definition: class_conspartition.cpp:43
void setVarToLinking(int varToLinking)
adds a variable to the linking variables, does not delete this var from list of open vars
Definition: class_partialdecomp.cpp:5143
void findVarsLinkingToStairlinking()
reassigns variables classified as linking to stairlinking if appropriate
Definition: class_partialdecomp.cpp:3457
void addPctConssToBorder(SCIP_Real pct)
adds percentage of constraints assigned to border
Definition: class_partialdecomp.cpp:358
std::vector< int > & getMasterconss()
Gets array containing all master conss indices.
Definition: class_partialdecomp.cpp:3992
bool isComplete()
Gets whether this partialdec is complete, i.e. it has no more open constraints and variables.
Definition: class_partialdecomp.cpp:4494
Definition: class_conspartition.h:53
void fixVarToLinking(int var)
adds a variable to the linking variables
Definition: class_partialdecomp.cpp:5154
void setTranslatedpartialdecid(int decid)
Definition: class_partialdecomp.cpp:5644
void setDetectorClockTimes(std::vector< SCIP_Real > &newvector)
set statistical vector of the times that the detectors needed for detecting per involved detector
Definition: class_partialdecomp.cpp:3675
std::vector< SCIP_Real > & getPctVarsToBlockVector()
returns fraction of variables assigned to a block for detectors in detectorchain
Definition: class_partialdecomp.cpp:4305
USERGIVEN getUsergiven()
Gets the USERGIVEN status of this partialdecs.
Definition: class_partialdecomp.cpp:4097
DETPROBDATA * GCGconshdlrDecompGetDetprobdataOrig(SCIP *scip)
help method to access detprobdata for unpresolved problem
Definition: cons_decomp.cpp:5249
int getNVarsForBlock(int block)
Gets size of the vector containing vars assigned to a block.
Definition: class_partialdecomp.cpp:4226
void setDetectorchain(std::vector< DEC_DETECTOR * > &givenDetectorChain)
sets the detectorchain with the given vector of detector pointers
Definition: class_partialdecomp.cpp:4974
SCIP_RETCODE filloutBorderFromConstoblock(SCIP_HASHMAP *constoblock, int givenNBlocks)
every constraint is either assigned to master or open
Definition: class_partialdecomp.cpp:3274
void showVisualization()
generates and opens a gp visualization of the partialdec
Definition: class_partialdecomp.cpp:5359
bool getFinishedByFinisher()
returns true iff this partialdec was finished by finishPartialdec() method of a detector
Definition: class_partialdecomp.cpp:3967
std::vector< int > getNNewBlocksVector()
gets number of blocks the detectors in the detectorchain added
Definition: class_partialdecomp.cpp:4164
void setMaxForWhiteScore(SCIP_Real score)
set the maximum foreseeing white area score
Definition: class_partialdecomp.cpp:5549
void complete()
assigns all open constraints and open variables trivially
Definition: class_partialdecomp.cpp:2125
bool fixVarToMasterByName(const char *varname)
assigns a variable with given name as master
Definition: class_partialdecomp.cpp:5331
data structures for detectors
void addPctVarsFromFree(SCIP_Real pct)
adds percentage of closed variables
Definition: class_partialdecomp.cpp:366
SCIP_Real getSetPartForWhiteScore()
gets the setpartitioning maximum foreseeing white area score
Definition: class_partialdecomp.cpp:5557
int getNTotalStairlinkingvars()
Gets total number of stairlinking vars.
Definition: class_partialdecomp.cpp:4182
void fixVarToStairlinking(int var, int firstblock)
adds a variable to the stairlinking variables
Definition: class_partialdecomp.cpp:5255
void deleteOpencons(int opencons)
deletes a cons from list of open conss
Definition: class_partialdecomp.cpp:2865
static SCIP_Bool realArraysAreEqual(SCIP *scip, SCIP_Real *array1, int array1length, SCIP_Real *array2, int array2length)
checks whether two arrays of SCIP_Real's are identical
Definition: class_partialdecomp.cpp:229
void completeByConnected()
assigns all open constraints and open variables
Definition: class_partialdecomp.cpp:2157
Definition: class_varpartition.h:54
std::vector< int > & getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
Definition: class_detprobdata.cpp:714
void buildDecChainString(char *buffer)
creates a detector chain short string for this partialdec, is built from detector chain
Definition: class_partialdecomp.cpp:5480
void addAncestorID(int ancestor)
Definition: class_partialdecomp.cpp:3616
int GCGconshdlrDecompGetNextPartialdecID(SCIP *scip)
Gets the next partialdec id managed by cons_decomp.
Definition: cons_decomp.cpp:5359
various SCIP helper methods
bool fixVarToLinkingByName(const char *varname)
assigns a variable by name to the linking variables
Definition: class_partialdecomp.cpp:5345
void setSetPartForWhiteScore(SCIP_Real score)
set the setpartitioning maximum foreseeing white area score
Definition: class_partialdecomp.cpp:5562
void setMaxWhiteScore(SCIP_Real score)
set the maximum white area score
Definition: class_partialdecomp.cpp:5536
SCIP_Real getMaxWhiteScore()
gets the maximum white area score
Definition: class_partialdecomp.cpp:5531
void setUsergiven(USERGIVEN usergiven)
sets whether this partialdec is user given
Definition: class_partialdecomp.cpp:5063
bool isConsMastercons(int cons)
Gets whether the cons is a master cons.
Definition: class_partialdecomp.cpp:4515
SCIP_Bool hasSetppccardMaster()
checks if all master constraints set partitioning, set packing, set cover, or cardinality constraints
Definition: class_partialdecomp.cpp:3197
std::vector< int > & getRepVarmap(int repid, int blockrepid)
Gets the represenation varmap.
Definition: class_partialdecomp.cpp:4415
void setDetectorFinished(DEC_DETECTOR *detector)
sets detector that finished the partialdec
Definition: class_partialdecomp.cpp:4991
void calcStairlinkingVars()
reassigns linking vars to stairlinkingvars if possible
Definition: class_partialdecomp.cpp:1322
int getNStairlinkingvars(int block)
Gets size of the vector containing stairlinking vars.
Definition: class_partialdecomp.cpp:4210
int getNConssForBlock(int block)
Gets size of the vector containing conss assigned to a block.
Definition: class_partialdecomp.cpp:4121
SCIP_RETCODE GCGconshdlrDecompCalcMaxForeseeingWhiteAggScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the maxforeseeingwhiteagg score of a partialdec
Definition: cons_decomp.cpp:4180
static SCIP_RETCODE partition(SCIP *scip, SCIP_VAR **J, int *Jsize, SCIP_Longint *priority, SCIP_VAR **F, int Fsize, SCIP_VAR **origvar, SCIP_Real *median)
Definition: branch_generic.c:832
SCIP_CONS * getCons(int consIndex)
returns the SCIP constraint related to a constraint index
Definition: class_detprobdata.cpp:698
void deleteOpenvar(int openvar)
deletes a var from the list of open vars
Definition: class_partialdecomp.cpp:2887
SCIP_RETCODE GCGconshdlrDecompCalcBendersScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the benders score of a partialdec
Definition: cons_decomp.cpp:3705
SCIP_Bool hasSetppcMaster()
checks iff all master constraints set partitioning, set packing, or set cover constraints
Definition: class_partialdecomp.cpp:3226
void setStrongDecompScore(SCIP_Real score)
set the strong decomposition score
Definition: class_partialdecomp.cpp:5613
SCIP_Bool shouldCompletedByConsToMaster()
Checks whether this partialdec is a userpartialdec that should be completed.
Definition: class_partialdecomp.cpp:5439
SCIP_Real getPctConssToBorder(int detectorchainindex)
Gets fraction of constraints assigned to the border for a detector.
Definition: class_partialdecomp.cpp:4344
void addDecChangesFromAncestor(PARTIALDECOMP *ancestor)
adds the statistical differences to an ancestor
Definition: class_partialdecomp.cpp:294
void GCGconshdlrDecompDeregisterPartialdec(SCIP *scip, PARTIALDECOMP *partialdec)
deregisters a partialdec in the conshdlr
Definition: cons_decomp.cpp:5095
void exportVisualization()
generates a gp visualization of the partialdec without compilation or opening
Definition: class_partialdecomp.cpp:5427
void setConsToBlock(int consToBlock, int block)
adds a constraint to a block, does not delete this cons from list of open conss
Definition: class_partialdecomp.cpp:4879
void setPctVarsToBorderVector(std::vector< SCIP_Real > &newvector)
set statistical vector of fraction of variables assigned to the border per involved detector
Definition: class_partialdecomp.cpp:4287
SCIP_RETCODE filloutPartialdecFromConstoblock(SCIP_HASHMAP *constoblock, int givenNBlocks)
assigns all conss to master or a block
Definition: class_partialdecomp.cpp:3313
Definition: struct_detector.h:46
void addPctVarsToBorder(SCIP_Real pct)
adds percentage of variables assigned to border
Definition: class_partialdecomp.cpp:382
SCIP_RETCODE GCGconshdlrDecompCalcMaxForseeingWhiteScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the maximum foreseeing white area score of a partialdec
Definition: cons_decomp.cpp:4280
void addPctConssToBlock(SCIP_Real pct)
adds percentage of constraints assigned to blocks
Definition: class_partialdecomp.cpp:350
SCIP_Real getPctConssToBlock(int detectorchainindex)
Gets fraction of constraints assigned to a block for a detector.
Definition: class_partialdecomp.cpp:4368
char DECdetectorGetChar(DEC_DETECTOR *detector)
Gets the character of the detector.
Definition: cons_decomp.cpp:2598
bool isVarStairlinkingvarOfBlock(int var, int block)
Checks whether the var is a stairlinkingvar of a specified block.
Definition: class_partialdecomp.cpp:4744
automorphism recognition (C++ interface)
SCIP_Real getSetPartForWhiteAggScore()
gets the setpartitioning maximum foreseeing white area score with respect to aggregateable
Definition: class_partialdecomp.cpp:5583
miscellaneous methods for visualizations
void completeGreedily()
assigns all open constraints and open variables
Definition: class_partialdecomp.cpp:2382
int getNVars()
return the number of variables considered in the detprobdata
Definition: class_detprobdata.cpp:848
SCIP_RETCODE assignBorderFromConstoblock(SCIP_HASHMAP *constoblock, int givenNBlocks)
assigns open conss to master
Definition: class_partialdecomp.cpp:399
void setStemsFromOrig(bool fromorig)
sets whether this partialdec stems from an orig problem partialdec
Definition: class_partialdecomp.cpp:5055
int getRepForBlock(int blockid)
Gets index of the representative block for a block, this might be blockid itself.
Definition: class_partialdecomp.cpp:4408
int getIndexForCons(SCIP_CONS *cons)
returns the constraint index related to a SCIP constraint
Definition: class_detprobdata.cpp:744
int getNLinkingvars()
Gets size of the vector containing linking vars.
Definition: class_partialdecomp.cpp:4148
bool assignCurrentStairlinking()
assigns open vars to stairlinking if appropriate
Definition: class_partialdecomp.cpp:429
void setConsPartitionStatistics(int detectorchainindex, ConsPartition *partition, std::vector< int > &consclassesmaster)
registers statistics for a used conspartition
Definition: class_partialdecomp.cpp:4860
void setPctConssToBorderVector(std::vector< SCIP_Real > &newvector)
set statistical vector of fractions of constraints assigned to the border per involved detector
Definition: class_partialdecomp.cpp:4360
bool sort()
sorts the vars and conss data structures by their indices
Definition: class_partialdecomp.cpp:5445
int getIndexForVar(SCIP_VAR *var)
returns the variable index related to a SCIP variable
Definition: class_detprobdata.cpp:776
SCIP_RETCODE GCGwriteGpVisualizationFormat(SCIP *scip, char *filename, char *outputname, int partialdecid, GP_OUTPUT_FORMAT outputformat)
Definition: reader_gp.cpp:449
void setPctConssFromFreeVector(std::vector< SCIP_Real > &newvector)
set statistical vector of fractions of constraints that are not longer open per involved detector
Definition: class_partialdecomp.cpp:4438
C++ interface of cons_decomp.
SCIP_Real getStrongDecompScore()
gets the strong decomposition score
Definition: class_partialdecomp.cpp:5608
std::vector< SCIP_Real > & getPctConssFromFreeVector()
Gets fraction of constraints that are not longer open for detectors in detectorchain.
Definition: class_partialdecomp.cpp:4402
void setConsToMaster(int consToMaster)
adds a constraint to the master constraints, does not delete this cons from list of open conss
Definition: class_partialdecomp.cpp:4926
void printPartitionInformation(SCIP *givenscip, FILE *file)
prints partition information as described in
Definition: class_partialdecomp.cpp:4767
const int * getStairlinkingvars(int block)
Gets array containing stairlinking vars,.
Definition: class_partialdecomp.cpp:4446
void findVarsLinkingToMaster()
reassigns linking variables to master if appropriate
Definition: class_partialdecomp.cpp:3413
void createConssAdjacency()
create the constraint adjacency datastructure that is used (if created) for some methods to faster ac...
Definition: class_detprobdata.cpp:641
SCIP_Real getPctVarsToBorder(int detectorchainindex)
Gets fraction of variables assigned to the border for a detector.
Definition: class_partialdecomp.cpp:4271
const int * getOpenconss()
Gets array containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4247
SCIP_RETCODE GCGwriteGpVisualization(SCIP *scip, char *filename, char *outputname, int partialdecid)
Definition: reader_gp.cpp:483
void assignSmallestComponentsButOneConssAdjacency()
computes components by connectedness of conss and vars
Definition: class_partialdecomp.cpp:928
Definition: class_detprobdata.h:106
const std::vector< int > & getBlocksForRep(int repid)
get a vector of block ids that are identical to block with id repid
Definition: class_partialdecomp.cpp:3602
int getNNewBlocks(int detectorchainindex)
Gets number of blocks a detector added.
Definition: class_partialdecomp.cpp:4154
unsigned long getHashValue()
returns the calculated hash value of this partialdec
Definition: class_partialdecomp.cpp:3973
virtual std::vector< int > getNeighbors(int node)
Definition: graph_gcg.cpp:475
int getTranslatedpartialdecid() const
Definition: class_partialdecomp.cpp:5639
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:621
std::vector< SCIP_Real > & getPctConssToBorderVector()
Gets fraction of constraints assigned to the border for detectors in detectorchain.
Definition: class_partialdecomp.cpp:4354
void setSelected(bool selected)
set the selection status of this partialdecs
Definition: class_partialdecomp.cpp:5047
void addNNewBlocks(int nnewblocks)
adds how many new blocks were introduced
Definition: class_partialdecomp.cpp:334
int getAncestorID(int ancestorindex)
gets partialdec id of given ancestor id
Definition: class_partialdecomp.cpp:3587
bool isConsCardinalityCons(int consindexd)
returns whether a constraint is a cardinality constraint, i.e. of the
Definition: class_detprobdata.cpp:971
bool checkConsistency()
Checks whether the assignments in the partialdec are consistent.
Definition: class_partialdecomp.cpp:1546
int getNDetectors()
Gets the number of detectors the partialdec is propagated by.
Definition: class_partialdecomp.cpp:4136
void setBorderAreaScore(SCIP_Real score)
set the border area score
Definition: class_partialdecomp.cpp:5523
bool isConsSetpp(int consindexd)
is cons with specified indec partitioning, or packing covering constraint?
Definition: class_detprobdata.cpp:1035
std::vector< std::string > & getDetectorchainInfo()
Gets the detectorchain info vector.
Definition: class_partialdecomp.cpp:4130
int getNCoeffsForBlock(int blockid)
Gets the number of nonzero coeffs in a certain block.
Definition: class_partialdecomp.cpp:4004
void setPctConssToBlockVector(std::vector< SCIP_Real > &newvector)
set statistical vector of fractions of constraints set to blocks per involved detector
Definition: class_partialdecomp.cpp:4384
PARTIALDECOMP(SCIP *scip, bool originalProblem)
Standard constructor, creates empty partialdec with unique id.
Definition: class_partialdecomp.cpp:90
automorphism recognition of SCIPs
SCIP_RETCODE GCGconshdlrDecompCalcMaxWhiteScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the maximum white area score of a partialdec
Definition: cons_decomp.cpp:4397
std::vector< SCIP_Real > & getDetectorClockTimes()
returns a vector of the clock times that each detector needed that was involved in this partialdec
Definition: class_partialdecomp.cpp:3656
std::vector< int > & getConssForBlock(int block)
returns array containing constraints assigned to a block
Definition: class_partialdecomp.cpp:3693
Definition: graph_gcg.h:57
int getNVarsForBlocks()
Gets overall number of vars assigned to a block.
Definition: class_partialdecomp.cpp:4235
bool fixConsToMasterByName(const char *consname)
assgins a constraint by name as master
Definition: class_partialdecomp.cpp:5317
bool isVarMastervar(int var)
Checks whether the var is a master var.
Definition: class_partialdecomp.cpp:4699
void fixVarToBlock(int var, int block)
adds a variable to the linking variables
Definition: class_partialdecomp.cpp:5109
SCIP_Real getScore(SCORETYPE type)
returns the score of the partialdec (depending on used scoretype)
Definition: class_partialdecomp.cpp:4025
void setVarToBlock(int varToBlock, int block)
adds a variable to the linking variables, does not delete this var from list of open vars
Definition: class_partialdecomp.cpp:5094
DETPROBDATA * getDetprobdata()
Gets the corresponding detprobdata.
Definition: class_partialdecomp.cpp:4424
void removeMastercons(int consid)
removes the given cons from master
Definition: class_partialdecomp.cpp:2588
SCIP_RETCODE assignPartialdecFromConstoblockVector(std::vector< int > constoblock, int additionalNBlocks)
assigns conss structure according to given vector
Definition: class_partialdecomp.cpp:881
bool isVarLinkingvar(int var)
Checks whether the var is a linking var.
Definition: class_partialdecomp.cpp:4708
void setVarPartitionStatistics(int detectorchainindex, VarPartition *partition, std::vector< int > &varclasseslinking, std::vector< int > &varclassesmaster)
registers statistics for a used varpartition
Definition: class_partialdecomp.cpp:5071
void setSetPartForWhiteAggScore(SCIP_Real score)
set the setpartitioning maximum foreseeing white area score with respect to aggregateable
Definition: class_partialdecomp.cpp:5588
virtual SCIP_RETCODE setEdge(int node_i, int node_j, double weight)
Definition: graph_gcg.cpp:657
std::vector< int > & getLinkingvars()
returns array containing all linking vars indices
Definition: class_partialdecomp.cpp:3986
void addPctConssFromFree(SCIP_Real pct)
adds percentage of closed constraints
Definition: class_partialdecomp.cpp:342
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
Definition: class_detprobdata.cpp:854
bool fixVarToBlockByName(const char *varname, int blockid)
assigns a variable by name to a block
Definition: class_partialdecomp.cpp:5299
SCIP_Bool isConssAdjInitialized()
determines whether or not the constraint-constraint adjacency data structure is initilized
Definition: class_detprobdata.cpp:985
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
DETPROBDATA * GCGconshdlrDecompGetDetprobdataPresolved(SCIP *scip)
help method to access detprobdata for transformed problem
Definition: cons_decomp.cpp:5263
SCIP_RETCODE isEqual(PARTIALDECOMP *otherpartialdec, SCIP_Bool *isequal, bool sortpartialdecs)
method to check whether this partialdec is equal to a given other partialdec (
Definition: class_partialdecomp.cpp:4539
SCIP_RETCODE GCGconshdlrDecompCalcBorderAreaScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the border area score of a partialdec
Definition: cons_decomp.cpp:3849
static bool compare_blocks(std::pair< int, int > const &a, std::pair< int, int > const &b)
Definition: class_partialdecomp.cpp:261
bool isPropagatedBy(DEC_DETECTOR *detector)
Gets whether this partialdec was propagated by specified detector.
Definition: class_partialdecomp.cpp:4649
void addPctVarsToBlock(SCIP_Real pct)
adds percentage of variables assigned to blocks
Definition: class_partialdecomp.cpp:374
void setPctVarsFromFreeVector(std::vector< SCIP_Real > &newvector)
set statistical vector of variables that are not longer open per involved detector
Definition: class_partialdecomp.cpp:4336
void calcAggregationInformation(bool ignoreDetectionLimits)
computes if aggregation of sub problems is possible
Definition: class_partialdecomp.cpp:1105
bool fixConsToBlockByName(const char *consname, int blockid)
assigns a constraint by name to a block
Definition: class_partialdecomp.cpp:5283
void setDetectorPropagated(DEC_DETECTOR *detector)
sets partialdec to be propagated by a detector
Definition: class_partialdecomp.cpp:4982
SCIP_Real getPctVarsToBlock(int detectorchainindex)
Gets fraction of variables assigned to a block for a detector.
Definition: class_partialdecomp.cpp:4295
void GCGconshdlrDecompRegisterPartialdec(SCIP *scip, PARTIALDECOMP *partialdec)
registers a partialdec in the conshdlr
Definition: cons_decomp.cpp:5733
class storing (potentially incomplete) decompositions
std::vector< int > & getAncestorList()
get ancestor ids as vector
Definition: class_partialdecomp.cpp:3597
GP file reader writing decompositions to gnuplot files.
SCIP_Real getVal(int row, int col)
returns a coefficient from the coefficient matrix
Definition: class_detprobdata.cpp:916
SCIP_RETCODE cmpGraphPair(SCIP *origscip, SCIP *scip1, SCIP *scip2, int prob1, int prob2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, unsigned int searchnodelimit, unsigned int generatorlimit)
Definition: bliss_automorph.cpp:1334
bool alreadyAssignedConssToBlocks()
method to check if at least one constraint is assigned to some block
Definition: class_partialdecomp.cpp:390
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
std::vector< DEC_DETECTOR * > & getDetectorchain()
returns detector chain as vector of detector pointers
Definition: class_partialdecomp.cpp:3702
bool isTrivial()
Gets whether this partialdec is considered to be trivial.
Definition: class_partialdecomp.cpp:4659
int getNMasterconss()
Gets size of the vector containing master conss.
Definition: class_partialdecomp.cpp:4170
bool isAssignedToOrigProb()
Gets whether the partialdec is from the presolved problem.
Definition: class_partialdecomp.cpp:4533
std::vector< SCIP_Real > & getPctVarsToBorderVector()
Gets fraction of variables assigned to the border for detectors in detectorchain.
Definition: class_partialdecomp.cpp:4281
SCIP_Real getDetectorClockTime(int detectorchainindex)
returns the time that the detector related to the given detectorchainindex needed for detecting
Definition: class_partialdecomp.cpp:3646
const int * getOpenvars()
Gets array containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4259
void setDetectorFinishedOrig(DEC_DETECTOR *detectorID)
sets detector that finished the partialdec in the original problem
Definition: class_partialdecomp.cpp:5001
SCIP_VAR * getVar(int varIndex)
returns SCIP variable related to a variable index
Definition: class_detprobdata.cpp:955
void deleteEmptyBlocks(bool variables)
deletes empty blocks and sets nblocks accordingly
Definition: class_partialdecomp.cpp:2794
int getNMastervars()
Gets size of the vector containing master vars.
Definition: class_partialdecomp.cpp:4176
class storing partialdecs and the problem matrix
std::vector< SCIP_Real > & getPctVarsFromFreeVector()
Gets fraction of variables that are not longer open for detectors in detectorchain.
Definition: class_partialdecomp.cpp:4330
void GCGgetVisualizationFilename(SCIP *scip, PARTIALDECOMP *partialdec, const char *extension, char *filename)
Definition: miscvisualization.cpp:54
void fixConsToBlock(int cons, int block)
adds a constraint to a block
Definition: class_partialdecomp.cpp:4894
void completeByConnectedConssAdjacency()
assigns all open constraints and open variables
Definition: class_partialdecomp.cpp:2273
SCIP_RETCODE GCGconshdlrDecompCalcSetPartForWhiteAggScore(SCIP *scip, int partialdecid, SCIP_Real *score)
calculates the setpartfwhiteagg score of a partialdec
Definition: cons_decomp.cpp:4480
SCIP_Real getMaxForWhiteScore()
gets the maximum foreseeing white area score
Definition: class_partialdecomp.cpp:5544
void generateVisualization(char *filename, char *outname, GP_OUTPUT_FORMAT outputformat=GP_OUTPUT_FORMAT_PDF)
generates a visualization of the partialdec using gnuplot
Definition: class_partialdecomp.cpp:5389
std::vector< std::vector< int > > & getConssForBlocks()
Definition: class_partialdecomp.cpp:5629