SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group
Definition in file cons_orbitope.h.
#include "scip/scip.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. | |
| enum | SCIP_OrbitopeType { SCIP_ORBITOPETYPE_FULL = 0, SCIP_ORBITOPETYPE_PARTITIONING = 1, SCIP_ORBITOPETYPE_PACKING = 2 } |
| typedef enum SCIP_OrbitopeType | SCIP_ORBITOPETYPE |
| SCIP_RETCODE | SCIPcreateConsOrbitope (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool resolveprop, 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 resolveprop) |