Scippy

SCIP

Solving Constraint Integer Programs

cons_symresack.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_symresack.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for symresack constraints
19  * @author Christopher Hojny
20  *
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_CONS_SYMRESACK_H__
26 #define __SCIP_CONS_SYMRESACK_H__
27 
28 #include "scip/def.h"
29 #include "scip/type_cons.h"
30 #include "scip/type_retcode.h"
31 #include "scip/type_scip.h"
32 #include "scip/type_var.h"
33 
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37 
38 
39 
40 /** creates the handler for symresack constraints and includes it in SCIP
41  *
42  * @ingroup ConshdlrIncludes
43  */
44 SCIP_EXPORT
45 SCIP_RETCODE SCIPincludeConshdlrSymresack(
46  SCIP* scip /**< SCIP data structure */
47  );
48 
49 /**@addtogroup CONSHDLRS
50  *
51  * @{
52  *
53  * @name Symresack Constraints
54  *
55  * @{
56  *
57  * Given a permutation that acts on the order of the variables of a (mixed) 0/1-program
58  * such that the permutation is a symmetry of the program, this constraint handler can
59  * be used to handle the symmetries corresponding to the permutation. The symmetries
60  * are handled by enforcing that a binary solution is lexicographically not smaller than
61  * its permutation. In a presolving step, we check whether the permutation acts only on
62  * binary points. Otherwise, we eliminate the non-binary variables from the permutation.
63  * Furthermore, we delete fixed points from the permutation.
64  *
65  * Moreover, the constraint handler checks whether each cycle of the permutation is
66  * contained in a set packing or partitioning constraint. In this case, the symresack
67  * is strengthened to a ppsymresack and strong symmetry handling inequalities are added during
68  * the initialization of the constraint handler.
69  *
70  * @pre The permutation is encoded by an array perm for which perm[i] = j if and only if
71  * the image of i under the permutation is j.
72  *
73  * @pre The permutation given to the constraint handler has to be a symmetry of the
74  * underlying problem. This is NOT checked by the constraint handler.
75  */
76 
77 /** creates a symmetry breaking constraint
78  *
79  * Depending on the given permutation, either an orbisack or symresack constraint
80  * is created.
81  */
82 SCIP_EXPORT
83 SCIP_RETCODE SCIPcreateSymbreakCons(
84  SCIP* scip, /**< SCIP data structure */
85  SCIP_CONS** cons, /**< pointer to hold the created constraint */
86  const char* name, /**< name of constraint */
87  int* perm, /**< permutation */
88  SCIP_VAR** vars, /**< variables */
89  int nvars, /**< number of variables in vars array */
90  SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */
91  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
92  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
93  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
94  * Usually set to TRUE. */
95  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
96  * TRUE for model constraints, FALSE for additional, redundant constraints. */
97  SCIP_Bool check, /**< should the constraint be checked for feasibility?
98  * TRUE for model constraints, FALSE for additional, redundant constraints. */
99  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
100  * Usually set to TRUE. */
101  SCIP_Bool local, /**< is constraint only valid locally?
102  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
103  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
104  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
105  * adds coefficients to this constraint. */
106  SCIP_Bool dynamic, /**< is constraint subject to aging?
107  * Usually set to FALSE. Set to TRUE for own cuts which
108  * are separated as constraints. */
109  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
110  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
111  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
112  * if it may be moved to a more global node?
113  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
114  );
115 
116 
117 /** creates and captures a symresack constraint
118  *
119  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
120  */
121 SCIP_EXPORT
122 SCIP_RETCODE SCIPcreateConsSymresack(
123  SCIP* scip, /**< SCIP data structure */
124  SCIP_CONS** cons, /**< pointer to hold the created constraint */
125  const char* name, /**< name of constraint */
126  int* perm, /**< permutation */
127  SCIP_VAR** vars, /**< variables */
128  int nvars, /**< number of variables in vars array */
129  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
130  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
131  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
132  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
133  * Usually set to TRUE. */
134  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
135  * TRUE for model constraints, FALSE for additional, redundant constraints. */
136  SCIP_Bool check, /**< should the constraint be checked for feasibility?
137  * TRUE for model constraints, FALSE for additional, redundant constraints. */
138  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
139  * Usually set to TRUE. */
140  SCIP_Bool local, /**< is constraint only valid locally?
141  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
142  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
143  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
144  * adds coefficients to this constraint. */
145  SCIP_Bool dynamic, /**< is constraint subject to aging?
146  * Usually set to FALSE. Set to TRUE for own cuts which
147  * are separated as constraints. */
148  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
149  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
150  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
151  * if it may be moved to a more global node?
152  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
153  );
154 
155 /** creates and captures a symresack constraint
156  * in its most basic variant, i.e., with all constraint flags set to their default values, which can be set
157  * afterwards using SCIPsetConsFLAGNAME() in scip.h
158  *
159  * @see SCIPcreateConsSymresack() for the default constraint flag configuration
160  *
161  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
162  */
163 SCIP_EXPORT
164 SCIP_RETCODE SCIPcreateConsBasicSymresack(
165  SCIP* scip, /**< SCIP data structure */
166  SCIP_CONS** cons, /**< pointer to hold the created constraint */
167  const char* name, /**< name of constraint */
168  int* perm, /**< permutation */
169  SCIP_VAR** vars, /**< variables */
170  int nvars, /**< number of variables in vars array */
171  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
172  );
173 
174 /** @} */
175 
176 /** @} */
177 
178 #ifdef __cplusplus
179 }
180 #endif
181 
182 #endif
SCIP_EXPORT
#define SCIP_EXPORT
Definition: def.h:100
SCIP_Var
Definition: struct_var.h:198
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIPincludeConshdlrSymresack
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
Definition: cons_symresack.c:2556
type_retcode.h
type definitions for return codes for SCIP methods
SCIP_Cons
Definition: struct_cons.h:37
SCIPcreateConsBasicSymresack
SCIP_EXPORT SCIP_RETCODE SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons)
Definition: cons_symresack.c:2682
type_scip.h
type definitions for SCIP&#39;s main datastructure
type_var.h
type definitions for problem variables
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
SCIPcreateSymbreakCons
SCIP_EXPORT SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, 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)
Definition: cons_symresack.c:1430
def.h
common defines and data types used in all packages of SCIP
SCIPcreateConsSymresack
SCIP_EXPORT SCIP_RETCODE SCIPcreateConsSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, 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)
Definition: cons_symresack.c:2617
type_cons.h
type definitions for constraints and constraint handlers