Decomposition

class pygcgopt.gcg.PartialDecomposition

class to manage partial decompositions

each partialdec corresponds to one DetProbData which contains the problem information, there is one detprobdata for the original and the transformed problem.

addAncestorID(self, int ancestor_id)

adds ancestor id to back of list

Parameters:

ancestor – id of ancestor that is to be added

addBlock(self)

adds a new block

Returns:

the number (id) of the new block

addClockTime(self, double clocktime)

adds detection time of one detector

incorporates the needed time of some detector in the detector chain.

addDecChangesFromAncestor(self, PartialDecomposition ancestor)

adds the statistical differences to an ancestor

incorporates the changes from ancestor partialdec into the statistical data structures

addDetectorChainInfo(self, decinfo)

adds information about the detector chain

adds a detectorchain information string to the corresponding vector (that carries information for each detector call)

addNNewBlocks(self, int nnewblocks)

adds how many new blocks were introduced

bookkeeping information: adds number of new blocks created by a detector added to detector chain

addPctConssFromFree(self, double pct)

adds percentage of closed constraints

bookkeeping information: fraction of constraints that are not longer open for a detector added to detector chain

addPctConssToBlock(self, double pct)

adds percentage of constraints assigned to blocks

bookkeeping information: adds fraction of constraints assigned to a block for a detector added to detector chain

addPctConssToBorder(self, double pct)

adds percentage of constraints assigned to border

bookkeeping information: adds fraction of constraints assigned to the border for a detector added to detector chain

addPctVarsFromFree(self, double pct)

adds percentage of closed variables

bookkeeping information: adds fraction of variables that are not longer open for a detector added to detector chain

addPctVarsToBlock(self, double pct)

adds percentage of variables assigned to blocks

bookkeeping information: adds fraction of variables assigned to a block for a detector added to detector chain

addPctVarsToBorder(self, double pct)

adds percentage of variables assigned to border

bookkeeping information: adds fraction of variables assigned to the border for a detector added to detector chain

aggInfoCalculated(self)

checks if the aggregation information was already calculated

Returns:

True iff the aggregation information was already calculated

alreadyAssignedConssToBlocks(self)

checks if at least one constraint is assigned to some block

Returns:

True iff at least one constraint is assigned to a block

assignCurrentStairlinking(self)

assigns open variables to stairlinking if appropriate

assigns open variables to stairlinking if they can be found in exactly two consecutive blocks

Returns:

True iff at least one stairlinkingvariable was assigned

assignOpenConssToMaster(self)

assigns open constraints to master

assignSmallestComponentsButOneConssAdjacency(self)

computes components by connectedness of constraints and variables

computes components corresponding to connectedness of constraints and variables and assigns them accordingly (all but one of largest components)

strategy: assigns all conss same block if they are connected two constraints are adjacent if there is a common variable

Note

this relies on the consadjacency structure of the detprobdata

hence it cannot be applied in presence of linking variables.

buildDecChainString(self, buffer)

creates a detector chain short string for this partialdec, is built from detector chain

calcAggregationInformation(self, bool ignoreDetectionLimits)

computes if aggregation of sub problems is possible

checks if aggregation of sub problems is possible and stores the corresponding aggregation information

Parameters:

ignoreDetectionLimits – Set to True if computation should ignore detection limits

This parameter is ignored if the patched bliss version is not present.

calcStairlinkingVars(self)

reassigns linking variables to stairlinkingvars if possible

potentially reorders blocks for making a maximum number of linking vars stairlinking if all vars that connect exactly two blocks have a staircase structure, all of them become stairlinkingvars otherwise, the stairlinking assignment is done greedily .. note:: precondition: partialdec does not have any stairlinking vars.

checkAllConssAssigned(self)

checks if all constraints are assigned and deletes the open constraint vector if so

Returns:

True iff all constraints are assigned

checkConsistency(self)

checks whether the assignments in the partialdec are consistent

The following checks are performed: - check if nblocks is set appropriately - check for empty (row- and col-wise) blocks - every variable is assigned at most once - check if all not assigned variables are open vars - check if all open vars are not assigned - every constraint is assigned at most once - check if all not assigned constraints are open cons - check if all open conss are not assigned - check if the data structures are sorted - check if variables hitting a cons are either in the cons’s block or border or still open

Returns:

True iff the partialdec seems to be consistent

complete(self)

assigns all open constraints and open variables trivially

strategy: assigns all open conss and vars to blocks if they can be refined there, otherwise to the master

Note:

partialdecomps should usually be completed by a detector, only use this function if you know what you are doing

completeByConnected(self)

assigns all open constraints and open variables

strategy: assigns all constraints and variables to the same block if they are connected, a constraint and a variable are adjacent if the variable appears in the constraint

completeByConnectedConssAdjacency(self)

assigns all open constraints and open variables

strategy: assigns all constraints and variables to the same block if they are connected a constraint and a variable are adjacent if the variable appears in the constraint .. note:: this relies on the consadjacency structure of the detprobdata hence it cannot be applied in presence of linking variables.

completeGreedily(self)

assigns all open constraints and open variables

strategy: assigns a constraint (and related variables) to a new block if possible, if not to an existing block if possible (by means of prior var assignments) and finally to master, if there does not exist such a block.

considerImplicits(self)

assigns every open constraint/variable

Assignments happen as follows: - to the respective block if it hits exactly one blockvariable/blockconstraint and no open variables/constraints - to master/linking if it hits blockvariables/blockconstraints assigned to different blocks - and every constraint to master that hits a master variable - and every variable to master if it does not hit any blockconstraint and has no open constraint - leave the constraitn/variable open if nothing from the above holds

copy(self)
copyPartitionStatistics(self, PartialDecomposition otherpartialdec)

copies the given partialdec’s partition statistics

Parameters:

otherpartialdec – partialdec whose partition statistics are to be copied

deleteEmptyBlocks(self, bool variables)

deletes empty blocks and sets nblocks accordingly

A block is considered to be empty if no constraint is assigned to it, variables in blocks with no constraints become open

Parameters:

variables – if True, then blocks with no constraints but at least one variable are considered to be nonempty

deleteOpencons(self, Constraint cons)

deletes constraint from list of open constraints

Parameters:

cons (Constraint) – scip#Constraint that is not considered open anymore

deleteOpenvar(self, Variable var)

deletes variable from the list of open variables

Parameters:

var (Variable) – scip#Variable that is not considered open anymore

displayInfo(self, int detailLevel)

displays the relevant information of the partialdec

Parameters:

detailLevel – pass a value that indicates how detailed the output should be:

0: brief overview 1: block and detector info 2: cons and var assignments

findVarsLinkingToMaster(self)

reassigns linking variables to master if appropriate

Variables are reassigned as master if the variable only hits master conss

findVarsLinkingToStairlinking(self)

reassigns variables classified as linking to stairlinking if appropriate

Variables are reassigned as master if the variable hits conss in exactly two consecutive blocks

fixConsToBlock(self, Constraint cons, block)

Adds a constraint to a block.

Parameters:

  • cons – scip#Constraint to add

  • block – identifier of block to add. Can be any hashable Python object.

Returns:

the internal block_id assigned to the block.

This method will automatically manage the blocks of the decomposition and create blocks if neccessary. The passed block identifiers will be mapped to internal block ids.

To address the internal blocks directly, use fixConsToBlockId().

See also

fixConsToBlockId(self, Constraint cons, int block_id)

Adds a constraint to a block.

Parameters:

  • cons (Constraint) – scip#Constraint to add

  • block_id (int) – id of block to add.

Note:

The passed block_id has to by of type integer and use the internal numbering of blocks. Before

calling this method, one has to ensure that the specified block exists. A more convenient alternative is fixConsToBlock().

See also

fixConsToMaster(self, Constraint cons)

fixes a Constraint to the master constraints

Parameters:

cons (Constraint) – scip#Constraint to add

fixConssToBlock(self, conss, block)

Adds all constraints to a block.

Parameters:

  • conss – An iterable of scip#Constraint objects

  • block – identifier of block to add. Can be any hashable Python object.

Returns:

the internal block_id assigned to the block.

See also

fixConssToBlockId(self, conss, int block_id)

Adds all constraints to a block.

Parameters:

  • conss – An iterable of scip#Constraint objects

  • block_id – id of block to add

See also

fixConssToMaster(self, conss)

fixes all constraints to the master constraints.

Parameters:

conss (An iterable of scip#Constraint objects) – An iterable of scip#Constraint objects

Raises:

TypeError – occurs if conss is not an Iterable

See also

fixVarToLinking(self, Variable var)

adds variable to the linking variables

Parameters:

var (Variable) – scip#Variable to add

fixVarToMaster(self, Variable var)

adds variable to the master variables

master variables hit only constraints in the master

Parameters:

var (Variable) – scip#Variable to add

fixVarToStairlinking(self, Variable var, int firstblock_id)

adds variable to the stairlinking variables

Parameters:

  • var (Variable) – scip#Variable to add

  • firstblock_id (int) – stairlinking variables hit exactly two consecutive blocks, this is the index of the first of these blocks

Note

stairlinking variables are only registered in block with smaller index

getAncestorID(self, int ancestor_id)

gets partialdec id of given ancestor id

Returns:

partialdec id of given ancestor id

getAncestorList(self)

gets ancestor ids as vector

Returns:

list of ids of all ancestors id

getBlocksForRep(self, int rep_id)

get a vector of block ids that are identical to block with id rep_id

Parameters:

rep_id – id of the representative block

Returns:

vector of block ids that are identical to block with id rep_id

getConssForBlock(self, int block_id)

gets a list of constraints that are assigned to the specified block

Parameters:

block_id – id of the block the constraints is asked for

Returns:

list of constraints

getConssForBlocks(self)
getDetectorClockTime(self, int detectorchain_id)

returns the time that the detector related to the given detectorchainindex needed for detecting

Returns:

the clock time for the corresponding detector in the chain

getDetectorClockTimes(self)

returns a vector of the clock times that each detector needed that was involved in this partialdec

Returns:

vector of the clock times.

getDetectorchainInfo(self)

gets the detectorchain info vector

Returns:

detectorchain info vector

getDetprobdata(self)

gets the corresponding detprobdata

Returns:

corresponding detprobdata

getFinishedByFinisher(self)

returns True iff this partialdec was finished by finishPartialdec() method of a detector

Returns:

True iff this partialdec was finished by finishPartialdec() method of a detector

getHashValue(self)

gets the calculated hash value of the partialdecomposition

Returns:

calculated hash value of the partialdecomposition

getID(self)

gets the unique id of the partialdecomposition

Returns:

unique id of the partialdecomposition

getLinkingvars(self)

gets a list of variables that are assigned to linking variables

Returns:

list of variables

getMasterconss(self)

gets a list of constraints that are assigned to master variables

Returns:

list of constraints

getMastervars(self)

gets a list of variables that are assigned to master variables (static variables)

Returns:

list of variables

getNAncestors(self)

gets number of ancestor partialdecs

Returns:

number of ancestor partialdecs

getNBlocks(self)

gets the number of blocks

Returns:

number of blocks

getNCoeffsForBlock(self, int block_id)

gets number of nonzero coeffs in a certain block

Parameters:

block_id – of the block the number of nozerors are requested for

Returns:

number of nonzero coeffs in a certain block

getNCoeffsForMaster(self)

gets number of nonzero coefficients in master

Returns:

number of nonzero coefficients in master

getNConss(self)

gets the number of constraints

Returns:

number of constraints

getNConssForBlock(self, int block_id)

gets size of the vector containing constraints assigned to a block

Parameters:

block_id – id of the block the number of constraints is asked for

Returns:

size of the vector containing constraints assigned to a block

getNDetectors(self)

gets the number of detectors the partialdec is propagated by

Returns:

number of detectors the partialdec is propagated by

getNLinkingvars(self)

gets number of linking variables

Returns:

number of linking variables

getNMasterconss(self)

gets number of master constraints

Returns:

number of master constraints

getNMastervars(self)

gets number of master variables

Returns:

number of master variables

getNNewBlocks(self, int detectorchain_id)

gets number of blocks a detector added

Returns:

number of blocks a detector added

getNNewBlocksVector(self)

gets number of blocks the detectors in the detectorchain added

Returns:

number of blocks the detectors in the detectorchain added

getNOpenconss(self)

gets number of constraints that are opened (not assigned yet)

Returns:

number of open constraints

getNOpenvars(self)

gets number of variables that are opened (not assigned yet)

Returns:

number of open variables

getNReps(self)

gets the number of blockrepresentatives

Returns:

the number of blockrepresentatives

getNStairlinkingvars(self, int block_id)

gets number of variables that are assigned to stairlinking variables of the specified block

Parameters:

block_id – id of the block the number of stairlinking variables is asked for

Returns:

number of stairlinking variables

Note

if a stairlinking variable links block i and i+1 it is only stored in vector of block i

getNTotalStairlinkingvars(self)

gets total number of stairlinking variables

Returns:

total number of stairlinking variables

getNVars(self)

gets number of variables

Returns:

number of variables

getNVarsForBlock(self, int block_id)

gets number of variables that are assigned to the specified block

Parameters:

block_id – id of the block the number of variables is asked for

Returns:

number of variables

getNVarsForBlocks(self)

gets overall number of variables assigned to a block

Returns:

number of variables that are assigned to any block

getOpenconss(self)

gets a list of constraints that are opened (not assigned yet)

Returns:

list of constraints

getOpenvars(self)

gets a list of variables that are opened (not assigned yet)

Returns:

list of variables

getPctConssFromFree(self, int detectorchainindex)

gets fraction of constraints that are not longer open for a detector

Returns:

fraction of constraints that are not longer open for a detector.

getPctConssFromFreeVector(self)

gets fraction of constraints that are not longer open for detectors in detectorchain

Returns:

vector of fractions of constraints that are not longer open for detectors in detectorchain.

getPctConssToBlock(self, int detectorchainindex)

gets fraction of constraints assigned to a block for a detector

Returns:

fraction of constraints assigned to a block for a detector.

getPctConssToBlockVector(self)

gets fraction of constraints assigned to a block for detectors in detectorchain

Returns:

vector of fractions of constraints assigned to a block for detectors in detectorchain.

getPctConssToBorder(self, int detectorchainindex)

gets fraction of constraints assigned to the border for a detector

Returns:

returns fraction of constraints assigned to the border for a detector

getPctConssToBorderVector(self)

gets fraction of constraints assigned to the border for detectors in detectorchain

Returns:

vector of fractions of constraints assigned to the border for detectors in detectorchain

getPctVarsFromFree(self, int detectorchainindex)

Gets fraction of variables that are not longer open for a detector

Returns:

index of the detector in the detectorchain

getPctVarsFromFreeVector(self)

gets fraction of variables that are not longer open for detectors in detectorchain

Returns:

vector or fractions of variables that are not longer open for detectors in detectorchain

getPctVarsToBlock(self, int detectorchainindex)

gets fraction of variables assigned to a block for a detector

Returns:

fraction of variables assigned to a block for a detector

getPctVarsToBlockVector(self)

returns fraction of variables assigned to a block for detectors in detectorchain

Returns:

vector of fractions of variables assigned to a block for detectors in detectorchain

getPctVarsToBorder(self, int detectorchainindex)

gets fraction of variables assigned to the border for a detector

Returns:

fraction of variables assigned to the border for a detector

getPctVarsToBorderVector(self)

gets fraction of variables assigned to the border for detectors in detectorchain

Returns:

vector of fractions of variables assigned to the border for detectors in detectorchain.

getRepForBlock(self, int block_id)

gets index of the representative block for a block, this might be block_id itself

Parameters:

block_id – id of the block the representative is asked for

Returns:

index of the representative block for a block, this might be block_id itself

getRepVarmap(self, int repid, int blockrepid)

Gets the represenation varmap

Var map is vector for represenative repid and the blockrepid-th block that is represented by repid

Parameters:

  • repid – id of representative

  • blockrepid – id of block

Returns:

the represenation varmap as vector for represenative repid and the blockrepid-th block that is represented by repid.

getScore(self, Score score)

gets value of the score

Parameters:

score – score for which the value should be returned

Returns:

value of score

getTranslatedpartialdecid(self)
getUsergiven(self)

gets the PY_USERGIVEN status of this partialdecs

Returns:

the PY_USERGIVEN status of this partialdecs

getVarProbindexForBlock(self, int varid, int block)

Gets index in variables array of a block for a variable

Parameters:

  • varid – the id of the variable the index

  • block – the corresponding block id

Returns:

returns index in variables array of a block for a variable.

getVarsForBlock(self, int block_id)

gets a list of variables that are assigned to the specified block

Parameters:

block_id – id of the block the variables is asked for

Returns:

list of variables

hasSetppMaster(self)

checks if all master constraints set partitioning or set packing constraints

Returns:

True iff all master constraints set partitioning or set packing constraints

hasSetppcMaster(self)

checks if all master constraints set partitioning, set packing or set cover constraints

Returns:

True iff all master constraints set partitioning, set packing or set cover

hasSetppccardMaster(self)

checks if all master constraints set partitioning, set packing, set cover or cardinality constraints

Returns:

True iff all master constraints set partitioning, set packing, set cover or cardinality constraints

isAssignedToOrigProb(self)

gets whether the partialdec is from the presolved problem

Returns:

True iff the partialdec is from the presolved problem

isComplete(self)

gets whether this partialdec is complete, i.e. it has no more open constraints and variables

Returns:

True iff this partialdec is complete

isConsMastercons(self, Constraint cons)

gets whether the constraint is a master constraint

Parameters:

cons (scip#Constraint) – constraint to check if it is master constraint

Returns:

True iff the constraint is a master constraint

isConsOpencons(self, Constraint cons)

gets whether the constraint is an open constraint

Parameters:

cons (scip#Constraint) – constraint to check if it is open constraint

Returns:

True iff the constraint is an open constraint

isSelected

gets whether the partialdec is currently selected in explore menue

Returns:

True iff the partialdec is currently selected in explore menue.

isTrivial(self)

gets whether this partialdec is considered to be trivial

Returns:

True iff this partialdec is considered to be trivial

Note

PartialDecomposition is considered trivial if all constraints are in one block, all constraints are in border,

all variables linking or mastervariables, or all constraints and variables are open

isVarBlockvarOfBlock(self, Variable var, int block_id)

gets whether the variable is assigned to the block

Parameters:

  • var (scip#Variable) – variable to check if it is in the specified block

  • block_id – id of block to check

Returns:

True iff the variable is assigned to the specified block

isVarLinkingvar(self, Variable var)

gets whether the variable is a linking variable

Parameters:

var (scip#Variable) – variable to check if it is in a linking variable

Returns:

True iff the variable is a linking var

isVarMastervar(self, Variable var)

gets whether the variable is a master variable

Parameters:

var (scip#Variable) – variable to check if it is a master variable

Returns:

True iff the variable is a master variable

isVarOpenvar(self, Variable var)

gets whether the variable is an open variable

Parameters:

var (scip#Variable) – variable to check if it is an open variable

Returns:

True iff the variable is an open variable

isVarStairlinkingvar(self, Variable var)

gets whether the variable is a stairlinking variable

Parameters:

var (scip#Variable) – variable to check if it is a stairlinking variable

Returns:

True iff the variable is a stairlinking variable

isVarStairlinkingvarOfBlock(self, Variable var, int block_id)

checks whether the var is a stairlinkingvar of a specified block

Parameters:

  • var (scip#Variable) – variable to check if it is a stairlinking variable hitting the specified block

  • block_id – id of block to check

Returns:

True iff the variable is a stairlinking variable of the specified block

max_white_score

gets the maximum white area score

“maximum white score” is fraction of the area of the decomposed matrix that is neither block or border .. note:: -1 iff not calculated yet

Returns:

maximum white area score

prepare(self)

sorts the partialdec and calculates a its implicit assignments, hashvalue and evaluation

refineToBlocks(self)

refine partialdec with focus on blocks

strategy: assigns open conss and vars if they can be found in blocks (without respect to open vars and conss see assignHittingOpenconss(), see assignHittingOpenvars()) .. note:: partialdec might be not complete.

refineToMaster(self)

refine partialdec with focus on master

strategy: do obvious ( see considerImplicits()) assignments and assign other conss and vars to master if possible (see assignOpenPartialHittingToMaster())

removeAncestorID(self, int ancestor_id)

removes ancestor id from list

removeMastercons(self, Constraint cons)

removes the given constraint from master

Parameters:

cons (scip#Constraint) – constraint to be removed from master

setAncestorList(self, newlist)

set ancestor list directly

Parameters:

newlist – new list of ancestor ids.

setConsPartitionStatistics(self, int detectorchainindex, ConsPart partition, consclassesmaster)

registers statistics for a used conspartition.

setConsToMaster(self, Constraint cons)

adds constraint to the master constraints, does not delete this constraint from list of open constraints

Parameters:

cons (Constraint) – scip#Constraint to add

setDetectorClockTimes(self, newvector)

set statistical vector of the times that the detectors needed for detecting per involved detector

Parameters:

newvector – vector of the times that the detectors needed for detecting per involved detector

setDetectorFinished(self, Detector detector)

sets detector that finished the partialdec

Parameters:

detector – detector that has finished this partialdecs

setDetectorFinishedOrig(self, Detector detector)

sets detector that finished the partialdec in the original problem

Parameters:

detector – detector that has finished this partialdecs

Note:

does not add the detector to the detectorchain and does not modify partition statistics

setDetectorPropagated(self, Detector detector)

sets partialdec to be propagated by a detector

Parameters:

detector – detector that is registered for this partialdec

setFinishedByFinisher(self, bool finished)

sets whether this partialdec was finished by a finishing detector

Parameters:

finished – is this partialdecs finished by a finishing detector

setFinishedByFinisherOrig(self, bool finished)

sets whether this partialdec was finished by a finishing detector in the original problem (in case this partialdec was translated)

Parameters:

finished – was this partialdecs finished by a finishing detector in orig

setNBlocks(self, int nblocks)

sets number of blocks, only increasing number allowed

Parameters:

nblocks – new number of blocks

setPctConssFromFreeVector(self, newvector)

set statistical vector of fractions of constraints that are not longer open per involved detector

Parameters:

newvector – vector of fractions of constraints that are not longer open per involved detector

setPctConssToBlockVector(self, newvector)

set statistical vector of fractions of constraints set to blocks per involved detector

Parameters:

newvector – vector of fractions of constraints set to blocks per involved detector

setPctConssToBorderVector(self, newvector)

set statistical vector of fractions of constraints assigned to the border per involved detector

Parameters:

newvector – vector of fractions of constraints assigned to the border per involved detector

setPctVarsFromFreeVector(self, newvector)

set statistical vector of variables that are not longer open per involved detector

Parameters:

newvector – vector of fractions of variables that are not longer open per involved detector

setPctVarsToBlockVector(self, newvector)

set statistical vector of fractions of variables assigned to a block per involved detector

Parameters:

newvector – vector of fractions of variables assigned to a block per involved detector

setPctVarsToBorderVector(self, newvector)

set statistical vector of fraction of variables assigned to the border per involved detector

Parameters:

newvector – vector of fractions of variables assigned to the border per involved detector

setStemsFromOrig(self, bool fromorig)

sets whether this partialdec stems from an orig problem partialdec

Parameters:

fromorig – has this partialdec ancestors from the orig problem

setTranslatedpartialdecid(self, int dec_id)
setUsergiven(self, USERGIVEN value=COMPLETED_CONSTOMASTER)
setVarPartitionStatistics(self, int detectorchainindex, VarPart partition, varclasseslinking, varclassesmaster)

registers statistics for a used varpartition.

setVarToBlockId(self, Variable var, int block_id)

adds variable to the linking variables, does not delete this variable from list of open variables

Parameters:

  • var (Variable) – scip#Variable to add

  • block_id (int) – id of block to add

setVarToLinking(self, Variable var)

adds variable to the linking variables, does not delete this variable from list of open variables

Parameters:

var (Variable) – scip#Variable to add

setVarToMaster(self, Variable var)

adds variable to the master variables, does not delete this variable from list of open variables

master variables hit only constraints in the master

Parameters:

var (Variable) – scip#Variable to add

setVarToStairlinking(self, Variable var, int block1_id, int block2_id)

adds variable to the stairlinking variables, does not delete this variable from list of open variables

Parameters:

  • var (Variable) – scip#Variable to add

  • block1_id (int) – id of block one

  • block2_id (int) – id of block two

Note

stairlinking variables are only registered in block with smaller index

shouldCompletedByConsToMaster(self)

checks whether this partialdec is a userpartialdec that should be completed

the completion should be done by setting unspecified constraints to master :return: True iff this partialdec is a userpartialdec that should be completed

showVisualization(self)

generates and opens a gp visualization of the partialdec

Note

linux only

sort(self)

sorts the variables and constraints data structures by their indices

Returns:

True if the internal order of variables or constraints changed