Detailed Description

type definitions for symmetry computations

Author: Marc Pfetsch; Christopher Hojny

#include "scip/scip.h"

Macros
#define	SYM_SPEC_INTEGER UINT32_C(0x00000001)

#define	SYM_SPEC_BINARY UINT32_C(0x00000002)

#define	SYM_SPEC_REAL UINT32_C(0x00000004)

#define	SYM_TIMING_BEFOREPRESOL 0

#define	SYM_TIMING_DURINGPRESOL 1

#define	SYM_TIMING_AFTERPRESOL 2

#define	SYM_COMPUTETIMING_BEFOREPRESOL SYM_TIMING_BEFOREPRESOL

#define	SYM_COMPUTETIMING_DURINGPRESOL SYM_TIMING_DURINGPRESOL

#define	SYM_COMPUTETIMING_AFTERPRESOL SYM_TIMING_AFTERPRESOL

#define	SYM_HANDLETYPE_NONE UINT32_C(0x00000000)

#define	SYM_HANDLETYPE_SYMBREAK UINT32_C(0x00000001)

#define	SYM_HANDLETYPE_ORBITALREDUCTION UINT32_C(0x00000002)

#define	SYM_HANDLETYPE_SST UINT32_C(0x00000004)

#define	SYM_HANDLETYPE_SYMCONS (SYM_HANDLETYPE_SYMBREAK \| SYM_HANDLETYPE_SST)

Typedefs
typedef uint32_t	SYM_SPEC

typedef enum SYM_Symtype	SYM_SYMTYPE

typedef enum SYM_Nodetype	SYM_NODETYPE

typedef enum SYM_Consoptype	SYM_CONSOPTYPE

typedef uint32_t	SYM_HANDLETYPE

typedef enum SCIP_LeaderRule	SCIP_LEADERRULE

typedef enum SCIP_SSTType	SCIP_SSTTYPE

typedef enum SCIP_OrbitopeType	SCIP_ORBITOPETYPE

Enumerations
enum	SYM_Symtype { SYM_SYMTYPE_PERM = 0 , SYM_SYMTYPE_SIGNPERM = 1 }

enum	SYM_Nodetype { SYM_NODETYPE_OPERATOR = 0 , SYM_NODETYPE_VAL = 1 , SYM_NODETYPE_CONS = 2 , SYM_NODETYPE_VAR = 3 }

enum	SYM_Consoptype { SYM_CONSOPTYPE_UNKNOWN = 0 , SYM_CONSOPTYPE_BDDISJ = 1 , SYM_CONSOPTYPE_EQ = 2 , SYM_CONSOPTYPE_SOS2_TUPLE = 3 , SYM_CONSOPTYPE_SUM = 4 , SYM_CONSOPTYPE_SLACK = 5 , SYM_CONSOPTYPE_COEF = 6 , SYM_CONSOPTYPE_SQDIFF = 7 , SYM_CONSOPTYPE_CARD_TUPLE = 8 , SYM_CONSOPTYPE_PB_AND = 9 , SYM_CONSOPTYPE_PB_LINEAR = 10 , SYM_CONSOPTYPE_PB_SOFT = 11 , SYM_CONSOPTYPE_PB_OBJ = 12 , SYM_CONSOPTYPE_AND = 13 , SYM_CONSOPTYPE_OR = 14 , SYM_CONSOPTYPE_XORINT = 15 , SYM_CONSOPTYPE_LAST = 16 }

enum	SCIP_LeaderRule { SCIP_LEADERRULE_FIRSTINORBIT = 0 , SCIP_LEADERRULE_LASTINORBIT = 1 , SCIP_LEADERRULE_MAXCONFLICTSINORBIT = 2 }

enum	SCIP_LeaderTiebreakRule { SCIP_LEADERTIEBREAKRULE_MINORBIT = 0 , SCIP_LEADERTIEBREAKRULE_MAXORBIT = 1 , SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT = 2 }

enum	SCIP_SSTType { SCIP_SSTTYPE_BINARY = 1 , SCIP_SSTTYPE_INTEGER = 2 , SCIP_SSTTYPE_CONTINUOUS = 4 }

enum	SCIP_OrbitopeType { SCIP_ORBITOPETYPE_FULL = 0 , SCIP_ORBITOPETYPE_PARTITIONING = 1 , SCIP_ORBITOPETYPE_PACKING = 2 }

Macro Definition Documentation

◆ SYM_SPEC_INTEGER

#define SYM_SPEC_INTEGER UINT32_C(0x00000001)

symmetry type specification need symmetries for integer variables only

Definition at line 43 of file type_symmetry.h.

◆ SYM_SPEC_BINARY

#define SYM_SPEC_BINARY UINT32_C(0x00000002)

need symmetries for binary variables only

Definition at line 44 of file type_symmetry.h.

◆ SYM_SPEC_REAL

#define SYM_SPEC_REAL UINT32_C(0x00000004)

need symmetries also for continuous variables

Definition at line 45 of file type_symmetry.h.

◆ SYM_TIMING_BEFOREPRESOL

#define SYM_TIMING_BEFOREPRESOL 0

symmetry timings compute and handle symmetries before presolving

Definition at line 50 of file type_symmetry.h.

◆ SYM_TIMING_DURINGPRESOL

#define SYM_TIMING_DURINGPRESOL 1

compute and handle symmetries during presolving

Definition at line 51 of file type_symmetry.h.

◆ SYM_TIMING_AFTERPRESOL

#define SYM_TIMING_AFTERPRESOL 2

compute and handle symmetries after presolving

Definition at line 52 of file type_symmetry.h.

◆ SYM_COMPUTETIMING_BEFOREPRESOL

#define SYM_COMPUTETIMING_BEFOREPRESOL SYM_TIMING_BEFOREPRESOL

compute symmetries before presolving

Definition at line 54 of file type_symmetry.h.

◆ SYM_COMPUTETIMING_DURINGPRESOL

#define SYM_COMPUTETIMING_DURINGPRESOL SYM_TIMING_DURINGPRESOL

compute symmetries during presolving

Definition at line 55 of file type_symmetry.h.

◆ SYM_COMPUTETIMING_AFTERPRESOL

#define SYM_COMPUTETIMING_AFTERPRESOL SYM_TIMING_AFTERPRESOL

compute symmetries after presolving

Definition at line 56 of file type_symmetry.h.

◆ SYM_HANDLETYPE_NONE

#define SYM_HANDLETYPE_NONE UINT32_C(0x00000000)

no symmetry handling

Definition at line 101 of file type_symmetry.h.

◆ SYM_HANDLETYPE_SYMBREAK

#define SYM_HANDLETYPE_SYMBREAK UINT32_C(0x00000001)

symmetry breaking inequalities (orbitopes/ orbisacks/symresacks) and lexicographic reduction

Definition at line 103 of file type_symmetry.h.

◆ SYM_HANDLETYPE_ORBITALREDUCTION

#define SYM_HANDLETYPE_ORBITALREDUCTION UINT32_C(0x00000002)

orbital reduction

Definition at line 104 of file type_symmetry.h.

◆ SYM_HANDLETYPE_SST

#define SYM_HANDLETYPE_SST UINT32_C(0x00000004)

Schreier Sims cuts

Definition at line 105 of file type_symmetry.h.

◆ SYM_HANDLETYPE_SYMCONS

#define SYM_HANDLETYPE_SYMCONS (SYM_HANDLETYPE_SYMBREAK | SYM_HANDLETYPE_SST)

Definition at line 106 of file type_symmetry.h.

Typedef Documentation

◆ SYM_SPEC

typedef uint32_t SYM_SPEC

types of variables handled by symmetry

Definition at line 47 of file type_symmetry.h.

◆ SYM_SYMTYPE

typedef enum SYM_Symtype SYM_SYMTYPE

Definition at line 64 of file type_symmetry.h.

◆ SYM_NODETYPE

typedef enum SYM_Nodetype SYM_NODETYPE

Definition at line 74 of file type_symmetry.h.

◆ SYM_CONSOPTYPE

typedef enum SYM_Consoptype SYM_CONSOPTYPE

Definition at line 98 of file type_symmetry.h.

◆ SYM_HANDLETYPE

typedef uint32_t SYM_HANDLETYPE

type of symmetry handling

Definition at line 108 of file type_symmetry.h.

◆ SCIP_LEADERRULE

typedef enum SCIP_LeaderRule SCIP_LEADERRULE

Definition at line 117 of file type_symmetry.h.

◆ SCIP_SSTTYPE

typedef enum SCIP_SSTType SCIP_SSTTYPE

Definition at line 135 of file type_symmetry.h.

◆ SCIP_ORBITOPETYPE

typedef enum SCIP_OrbitopeType SCIP_ORBITOPETYPE

Definition at line 144 of file type_symmetry.h.

Enumeration Type Documentation

◆ SYM_Symtype

enum SYM_Symtype

define symmetry types detectable by SCIP

Enumerator
SYM_SYMTYPE_PERM	permutation symmetries
SYM_SYMTYPE_SIGNPERM	signed permutation symmetries

Definition at line 59 of file type_symmetry.h.

◆ SYM_Nodetype

enum SYM_Nodetype

define type of nodes in symmetry detection expression trees

Enumerator
SYM_NODETYPE_OPERATOR	operator node
SYM_NODETYPE_VAL	numerical value node
SYM_NODETYPE_CONS	constraint node
SYM_NODETYPE_VAR	variable node

Definition at line 67 of file type_symmetry.h.

◆ SYM_Consoptype

enum SYM_Consoptype

define type of simple constraints/operators in symmetry detection

Enumerator
SYM_CONSOPTYPE_UNKNOWN	unknown constraint type
SYM_CONSOPTYPE_BDDISJ	constraint of type bounddisjunction
SYM_CONSOPTYPE_EQ	encodes == in indicator constraints for activation variable
SYM_CONSOPTYPE_SOS2_TUPLE	encodes pairs in SOS2 constraints
SYM_CONSOPTYPE_SUM	indicates sums if sum-expr undefined
SYM_CONSOPTYPE_SLACK	indicates slack vars in indicator constraints
SYM_CONSOPTYPE_COEF	indicates coefficients from parent expressions
SYM_CONSOPTYPE_SQDIFF	indicates a squared difference
SYM_CONSOPTYPE_CARD_TUPLE	encodes pairs in cardinality constraints
SYM_CONSOPTYPE_PB_AND	indicates AND conss in pseudoboolean conss
SYM_CONSOPTYPE_PB_LINEAR	indicates linear conss in pseudoboolean conss
SYM_CONSOPTYPE_PB_SOFT	indicates pseudoboolean cons is soft constraint
SYM_CONSOPTYPE_PB_OBJ	indicates pseudoboolean cons is objective function
SYM_CONSOPTYPE_AND	encodes the AND-operator in AND-constraints
SYM_CONSOPTYPE_OR	encodes the OR-operator in OR-constraints
SYM_CONSOPTYPE_XORINT	encodes the internal variable in XOR-constraints
SYM_CONSOPTYPE_LAST	number of predefined enum types, needs to always hold the biggest value

Definition at line 77 of file type_symmetry.h.

◆ SCIP_LeaderRule

enum SCIP_LeaderRule

selection rules for leaders in SST cuts

Enumerator
SCIP_LEADERRULE_FIRSTINORBIT	first var in orbit
SCIP_LEADERRULE_LASTINORBIT	last var in orbit
SCIP_LEADERRULE_MAXCONFLICTSINORBIT	var with most conflicting vars in its orbit

Definition at line 111 of file type_symmetry.h.

◆ SCIP_LeaderTiebreakRule

enum SCIP_LeaderTiebreakRule

tie breaks for leader rule based on the leader's orbit

Enumerator
SCIP_LEADERTIEBREAKRULE_MINORBIT	orbit of minimum size
SCIP_LEADERTIEBREAKRULE_MAXORBIT	orbit of maximum size
SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT	orbit with maximum number of vars in conflict with leader

Definition at line 120 of file type_symmetry.h.

◆ SCIP_SSTType

enum SCIP_SSTType

variable types for leader in Schreier Sims cuts

Enumerator
SCIP_SSTTYPE_BINARY	binary variables
SCIP_SSTTYPE_INTEGER	integer variables
SCIP_SSTTYPE_CONTINUOUS	continuous variables

Definition at line 128 of file type_symmetry.h.

◆ SCIP_OrbitopeType

enum SCIP_OrbitopeType

type of orbitope constraint: full, packing, or partitioning orbitope

Enumerator
SCIP_ORBITOPETYPE_FULL	constraint is a full orbitope constraint: rowsum(x) unrestricted
SCIP_ORBITOPETYPE_PARTITIONING	constraint is a partitioning orbitope constraint: rowsum(x) == 1
SCIP_ORBITOPETYPE_PACKING	constraint is a packing orbitope constraint: rowsum(x) <= 1

Definition at line 138 of file type_symmetry.h.

SCIP