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