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.

Visualization of an instance with a single-bordered stucture with master constraints, generated by GCG's explore menu. Instance: traininstance6.

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.

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.

Visualization of an instance with an staircase stucture, generated by GCG's explore menu. Instance: ic97_potential.