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