Scippy

SCIP

Solving Constraint Integer Programs

cons_orbitope.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-2014 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_orbitope.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for (partitioning/packing) orbitope constraints w.r.t. the full symmetric group
19  * @author Timo Berthold
20  * @author Marc Pfetsch
21  *
22  * This constraint handler can be used to handle symmetries in certain 0/1-programs. The principle
23  * structure is that some variables can be ordered in matrix form, such that permuting columns does
24  * not change the validity and objective function value of a solution. That is, the symmetry group
25  * of the program contains the full symmetric group obtained by permuting the columns of this
26  * matrix. The variables in each row have to be contained in set packing or partitioning
27  * constraints.
28  *
29  * In more mathematical terms the structure has to be as follows: There are 0/1-variables
30  * \f$x_{ij}\f$, \f$i \in \{1, \dots, p\}\f$, \f$j \in \{1, \dots, q\}\f$. The variables are coupled
31  * through set packing or partitioning constraints:
32  * \f[
33  * \sum_{j = 1}^q x_{ij} \leq 1 \quad \mbox{or} \quad \sum_{j = 1}^q x_{ij} = 1 \quad \mbox{for all }i = 1, \ldots, p.
34  * \f]
35  * Permuting columns of \f$x\f$ does not change the validity and objective function value of any feasible solution.
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 
40 #ifndef __SCIP_CONS_ORBITOPE_H__
41 #define __SCIP_CONS_ORBITOPE_H__
42 
43 #include "scip/scip.h"
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 
50 /** creates the handler for orbitope constraints and includes it in SCIP */
51 extern
52 SCIP_RETCODE SCIPincludeConshdlrOrbitope(
53  SCIP* scip /**< SCIP data structure */
54  );
55 
56 /** creates and captures a orbitope constraint
57  *
58  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
59  */
60 extern
61 SCIP_RETCODE SCIPcreateConsOrbitope(
62  SCIP* scip, /**< SCIP data structure */
63  SCIP_CONS** cons, /**< pointer to hold the created constraint */
64  const char* name, /**< name of constraint */
65  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
66  SCIP_Bool ispart, /**< whether we deal with the partitioning case (packing otherwise) */
67  int nspcons, /**< number of set partitioning/packing constraints <=> p */
68  int nblocks, /**< number of symmetric variable blocks <=> q */
69  SCIP_Bool resolveprop, /**< should propagation be resolved? */
70  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
71  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
72  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
73  * Usually set to TRUE. */
74  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
75  * TRUE for model constraints, FALSE for additional, redundant constraints. */
76  SCIP_Bool check, /**< should the constraint be checked for feasibility?
77  * TRUE for model constraints, FALSE for additional, redundant constraints. */
78  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
79  * Usually set to TRUE. */
80  SCIP_Bool local, /**< is constraint only valid locally?
81  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
82  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
83  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
84  * adds coefficients to this constraint. */
85  SCIP_Bool dynamic, /**< is constraint subject to aging?
86  * Usually set to FALSE. Set to TRUE for own cuts which
87  * are separated as constraints. */
88  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
89  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
90  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
91  * if it may be moved to a more global node?
92  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
93  );
94 
95 /** creates and captures an orbitope constraint
96  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
97  * afterwards using SCIPsetConsFLAGNAME() in scip.h
98  *
99  * @see SCIPcreateConsOrbitope() for the default constraint flag configuration
100  *
101  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
102  */
103 extern
104 SCIP_RETCODE SCIPcreateConsBasicOrbitope(
105  SCIP* scip, /**< SCIP data structure */
106  SCIP_CONS** cons, /**< pointer to hold the created constraint */
107  const char* name, /**< name of constraint */
108  SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
109  SCIP_Bool ispart, /**< whether we deal with the partitioning case (packing otherwise) */
110  int nspcons, /**< number of set partitioning/packing constraints <=> p */
111  int nblocks, /**< number of symmetric variable blocks <=> q */
112  SCIP_Bool resolveprop /**< should propagation be resolved? */
113  );
114 
115 #ifdef __cplusplus
116 }
117 #endif
118 
119 #endif
120