Scippy

SCIP

Solving Constraint Integer Programs

cons_orbitope.h File Reference

Detailed Description

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

Author
Timo Berthold
Marc Pfetsch

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. The variables in each row have to be contained in set packing or partitioning constraints.

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 are 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.

Definition in file cons_orbitope.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeConshdlrOrbitope (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsOrbitope (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_Bool ispart, 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_Bool ispart, int nspcons, int nblocks, SCIP_Bool resolveprop)
 

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrOrbitope ( SCIP scip)

creates the handler for orbitope constraints and includes it in SCIP

Parameters
scipSCIP data structure
SCIP_RETCODE SCIPcreateConsOrbitope ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR ***  vars,
SCIP_Bool  ispart,
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 
)

creates and captures a orbitope constraint

Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
varsmatrix of variables on which the symmetry acts
ispartwhether we deal with the partitioning case (packing otherwise)
nspconsnumber of set partitioning/packing constraints <=> p
nblocksnumber of symmetric variable blocks <=> q
resolvepropshould propagation be resolved?
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.
SCIP_RETCODE SCIPcreateConsBasicOrbitope ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR ***  vars,
SCIP_Bool  ispart,
int  nspcons,
int  nblocks,
SCIP_Bool  resolveprop 
)

creates and captures an orbitope constraint in its most basic variant, i. e., with all constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h

See Also
SCIPcreateConsOrbitope() for the default constraint flag configuration
Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
varsmatrix of variables on which the symmetry acts
ispartwhether we deal with the partitioning case (packing otherwise)
nspconsnumber of set partitioning/packing constraints <=> p
nblocksnumber of symmetric variable blocks <=> q
resolvepropshould propagation be resolved?