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-2019 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 scip.zib.de. */
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 initial, /**< should the LP relaxation of constraint be in the initial LP?
91  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
92  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
93  * Usually set to TRUE. */
94  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
95  * TRUE for model constraints, FALSE for additional, redundant constraints. */
96  SCIP_Bool check, /**< should the constraint be checked for feasibility?
97  * TRUE for model constraints, FALSE for additional, redundant constraints. */
98  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
99  * Usually set to TRUE. */
100  SCIP_Bool local, /**< is constraint only valid locally?
101  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
102  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
103  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
104  * adds coefficients to this constraint. */
105  SCIP_Bool dynamic, /**< is constraint subject to aging?
106  * Usually set to FALSE. Set to TRUE for own cuts which
107  * are separated as constraints. */
108  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
109  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
110  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
111  * if it may be moved to a more global node?
112  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
113  );
114 
115 
116 /** creates and captures a symresack constraint
117  *
118  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
119  */
120 SCIP_EXPORT
121 SCIP_RETCODE SCIPcreateConsSymresack(
122  SCIP* scip, /**< SCIP data structure */
123  SCIP_CONS** cons, /**< pointer to hold the created constraint */
124  const char* name, /**< name of constraint */
125  int* perm, /**< permutation */
126  SCIP_VAR** vars, /**< variables */
127  int nvars, /**< number of variables in vars array */
128  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
129  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
130  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
131  * Usually set to TRUE. */
132  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
133  * TRUE for model constraints, FALSE for additional, redundant constraints. */
134  SCIP_Bool check, /**< should the constraint be checked for feasibility?
135  * TRUE for model constraints, FALSE for additional, redundant constraints. */
136  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
137  * Usually set to TRUE. */
138  SCIP_Bool local, /**< is constraint only valid locally?
139  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
140  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
141  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
142  * adds coefficients to this constraint. */
143  SCIP_Bool dynamic, /**< is constraint subject to aging?
144  * Usually set to FALSE. Set to TRUE for own cuts which
145  * are separated as constraints. */
146  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
147  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
148  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
149  * if it may be moved to a more global node?
150  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
151  );
152 
153 /** creates and captures a symresack constraint
154  * in its most basic variant, i.e., with all constraint flags set to their default values, which can be set
155  * afterwards using SCIPsetConsFLAGNAME() in scip.h
156  *
157  * @see SCIPcreateConsSymresack() for the default constraint flag configuration
158  *
159  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
160  */
161 SCIP_EXPORT
162 SCIP_RETCODE SCIPcreateConsBasicSymresack(
163  SCIP* scip, /**< SCIP data structure */
164  SCIP_CONS** cons, /**< pointer to hold the created constraint */
165  const char* name, /**< name of constraint */
166  int* perm, /**< permutation */
167  SCIP_VAR** vars, /**< variables */
168  int nvars /**< number of variables in vars array */
169  );
170 
171 /* @} */
172 
173 /* @} */
174 
175 #ifdef __cplusplus
176 }
177 #endif
178 
179 #endif
SCIP_EXPORT
#define SCIP_EXPORT
Definition: def.h:98
SCIP_Var
Definition: struct_var.h:198
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPincludeConshdlrSymresack
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
Definition: cons_symresack.c:2328
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)
Definition: cons_symresack.c:2447
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
SCIPcreateConsSymresack
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)
Definition: cons_symresack.c:2383
SCIPcreateSymbreakCons
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)
Definition: cons_symresack.c:1314
def.h
common defines and data types used in all packages of SCIP
type_cons.h
type definitions for constraints and constraint handlers