Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for symresack constraints

Author
Christopher Hojny

Definition in file cons_symresack.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"

Go to the source code of this file.

Functions

SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrSymresack (SCIP *scip)
 
Symresack Constraints

Given a permutation that acts on the order of the variables of a (mixed) 0/1-program such that the permutation is a symmetry of the program, this constraint handler can be used to handle the symmetries corresponding to the permutation. The symmetries are handled by enforcing that a binary solution is lexicographically not smaller than its permutation. In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate the non-binary variables from the permutation. Furthermore, we delete fixed points from the permutation.

Moreover, the constraint handler checks whether each cycle of the permutation is contained in a set packing or partitioning constraint. In this case, the symresack is strengthened to a ppsymresack and strong symmetry handling inequalities are added during the initialization of the constraint handler.

Precondition
The permutation is encoded by an array perm for which perm[i] = j if and only if the image of i under the permutation is j.
The permutation given to the constraint handler has to be a symmetry of the underlying problem. This is NOT checked by the constraint handler.
SCIP_EXPORT SCIP_RETCODE SCIPcreateSymbreakCons (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, 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_EXPORT SCIP_RETCODE SCIPcreateConsSymresack (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, 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_EXPORT SCIP_RETCODE SCIPcreateConsBasicSymresack (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars)