Structure Types
Table of Contents
Types of Structures GCG can detect
Using different detectors, GCG can find structures in your model. The following structure types are being detected in the current release (c.f. DEC_DECTYPE):
DEC_DECTYPE_DIAGONAL
: "pure" block diagonal structure (no linking variables and constraints)DEC_DECTYPE_BORDERED
: bordered block diagonal structure (linking constraints only)DEC_DECTYPE_ARROWHEAD
: arrowhead structure (linking variables and constraints)DEC_DECTYPE_STAIRCASE
: staircase structure (linking variables between consecutive blocks)DEC_DECTYPE_UNKNOWN
: unknown structure (used for initialization)
Pure Block-Diagonal
Single-Bordered Block-Diagonal
In a single-bordered structure, the blocks are either connected by master constraints or by linking variables, but not both.
![](singleborder1.traininstance6.cCp.png)
Visualization of an instance with a single-bordered stucture with master constraints, generated by GCG's explore menu. Instance: traininstance6.
![](singleborder2.noswot.vC.png)
Visualization of an instance with a single-bordered stucture with linking variables, generated by GCG's explore menu. Instance: noswot.
Double-Bordered Block-Diagonal (Arrowhead)
The arrowhead structure is a double bordered decomposition. It consists of master constraints and linking variables.
![](arrowhead.b2c1s1.png)
Visualization of an instance with an arrowhead stucture, generated by GCG's explore menu. Instance: b2c1s1.
Staircase
So-called staircase structures define decompositions where each block is connected with the next one via linking variables. This often happens for programs that possess a time dependency, where one time step influences the following.
![](staircase.ic97_potential.S.png)
Visualization of an instance with an staircase stucture, generated by GCG's explore menu. Instance: ic97_potential.