cons_orbitope.h File Reference

Detailed Description

constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group

Author

Timo Berthold

Marc Pfetsch

Christopher Hojny

Definition in file cons_orbitope.h.

#include "scip/def.h"
#include "scip/type_cons.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_var.h"
#include "symmetry/type_symmetry.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeConshdlrOrbitope (SCIP *scip)
Orbitope Constraints
This constraint handler can be used to handle symmetries in certain 0/1-programs. The principle structure is that some variables can be ordered in matrix form, such that permuting columns does not change the validity and objective function value of a solution. That is, the symmetry group of the program contains the full symmetric group obtained by permuting the columns of this matrix. These symmetries can be handled by so-called full orbitopes. Moreover, if the variables in each row are contained in set packing or partitioning constraint, these symmetries can be handled by specialized packing or partitioning orbitopes. In more mathematical terms the structure has to be as follows: There are 0/1-variables \(x_{ij}\), \(i \in \{1, \dots, p\}\), \(j \in \{1, \dots, q\}\). The variables may be coupled through set packing or partitioning constraints: \[ \sum_{j = 1}^q x_{ij} \leq 1 \quad \mbox{or} \quad \sum_{j = 1}^q x_{ij} = 1 \quad \mbox{for all }i = 1, \ldots, p. \] Permuting columns of \(x\) does not change the validity and objective function value of any feasible solution. We distinguish whether an orbitope is a model constraint or not. If it is a model constraint, then its information are copied to subSCIPs. Otherwise, the constraint was added just for the purpose of symmetry handling and we do not copy its information to subSCIPs.
SCIP_RETCODE	SCIPcreateConsOrbitope (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool mayinteract, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE	SCIPcreateConsBasicOrbitope (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool mayinteract)