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