Scippy

SCIP

Solving Constraint Integer Programs

cons_orbisack.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_orbisack.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for orbisack constraints
19  * @author Christopher Hojny
20  *
21  * The constraint works on two vectors of variables, which are interpreted as columns of a matrix such that the first
22  * column is lexicographically not smaller than the second.
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #ifndef __SCIP_CONS_ORBISACK_H__
28 #define __SCIP_CONS_ORBISACK_H__
29 
30 #include "scip/def.h"
31 #include "scip/type_cons.h"
32 #include "scip/type_retcode.h"
33 #include "scip/type_scip.h"
34 #include "scip/type_sol.h"
35 #include "scip/type_var.h"
36 
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40 
41 
42 /** creates the handler for orbisack constraints and includes it in SCIP
43  *
44  * @ingroup ConshdlrIncludes
45  */
48  SCIP* scip /**< SCIP data structure */
49  );
50 
51 /**@addtogroup CONSHDLRS
52  *
53  * @{
54  *
55  * @name Orbisack Constraints
56  *
57  * @{
58  *
59  * This constraint handler can be used to handle symmetries in certain 0/1-programs. The principle
60  * structure is that some variables can be ordered in matrix form with two columns, such that
61  * permuting both columns does not change the validity and objective function value of a solution.
62  * That is, there exists a permutation symmetry of the program that permutes the variables of the
63  * first and second column row-wise.
64  *
65  * In more mathematical terms the structure has to be as follows: There are 0/1-variables
66  * \f$x_{ij}\f$, \f$i \in \{1, \dots, n\}\f$, \f$j \in \{1, 2\}\f$. Permuting columns of
67  * \f$x\f$ does not change the validity and objective function value of any feasible solution.
68  */
69 
70 /** separate orbisack solutions */
73  SCIP* scip, /**< pointer to scip */
74  SCIP_CONS* cons, /**< pointer to constraint for which cover inequality should be added */
75  SCIP_SOL* sol, /**< solution to be separated */
76  SCIP_VAR** vars1, /**< variables of first columns */
77  SCIP_VAR** vars2, /**< variables of second columns */
78  int nrows, /**< number of rows */
79  SCIP_Bool* infeasible, /**< memory address to store whether we detected infeasibility */
80  int* ngen /**< memory address to store number of generated cuts */
81  );
82 
83 
84 /** checks whether a given binary solution is feasible for the orbisack */
87  SCIP* scip, /**< SCIP data structure */
88  SCIP_SOL* sol, /**< solution to check for feasibility */
89  SCIP_VAR** vars1, /**< variables of first column */
90  SCIP_VAR** vars2, /**< variables of second column */
91  int nrows, /**< number of rows */
92  SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */
93  SCIP_Bool* feasible /**< memory address to store whether sol is feasible */
94  );
95 
96 /** creates and captures a orbisack constraint
97  *
98  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
99  */
102  SCIP* scip, /**< SCIP data structure */
103  SCIP_CONS** cons, /**< pointer to hold the created constraint */
104  const char* name, /**< name of constraint */
105  SCIP_VAR*const* vars1, /**< first column matrix of variables on which the symmetry acts */
106  SCIP_VAR*const* vars2, /**< second column matrix of variables on which the symmetry acts */
107  int nrows, /**< number of rows in variable matrix */
108  SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */
109  SCIP_Bool isparttype, /**< whether the orbisack is a partitioning orbisack */
110  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
111  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
112  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
113  * Usually set to TRUE. */
114  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
115  * TRUE for model constraints, FALSE for additional, redundant constraints. */
116  SCIP_Bool check, /**< should the constraint be checked for feasibility?
117  * TRUE for model constraints, FALSE for additional, redundant constraints. */
118  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
119  * Usually set to TRUE. */
120  SCIP_Bool local, /**< is constraint only valid locally?
121  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
122  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
123  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
124  * adds coefficients to this constraint. */
125  SCIP_Bool dynamic, /**< is constraint subject to aging?
126  * Usually set to FALSE. Set to TRUE for own cuts which
127  * are separated as constraints. */
128  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
129  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
130  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
131  * if it may be moved to a more global node?
132  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
133  );
134 
135 /** creates and captures an orbisack constraint in its most basic variant
136  *
137  * All constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h.
138  *
139  * @see SCIPcreateConsOrbisack() for the default constraint flag configuration
140  *
141  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
142  */
145  SCIP* scip, /**< SCIP data structure */
146  SCIP_CONS** cons, /**< pointer to hold the created constraint */
147  const char* name, /**< name of constraint */
148  SCIP_VAR** vars1, /**< first column of matrix of variables on which the symmetry acts */
149  SCIP_VAR** vars2, /**< second column of matrix of variables on which the symmetry acts */
150  int nrows, /**< number of rows in constraint matrix */
151  SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */
152  SCIP_Bool isparttype /**< whether the orbisack is a partitioning orbisack */
153  );
154 
155 /* @} */
156 
157 /* @} */
158 
159 #ifdef __cplusplus
160 }
161 #endif
162 
163 #endif
#define SCIP_EXPORT
Definition: def.h:98
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPcheckSolutionOrbisack(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool printreason, SCIP_Bool *feasible)
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_RETCODE SCIPcreateConsOrbisack(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype, 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)
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_RETCODE SCIPseparateCoversOrbisack(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool *infeasible, int *ngen)
type definitions for storing primal CIP solutions
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrOrbisack(SCIP *scip)
SCIP_EXPORT SCIP_RETCODE SCIPcreateConsBasicOrbisack(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype)
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers