Scippy

SCIP

Solving Constraint Integer Programs

cuts.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 cuts.h
17  * @ingroup PUBLICCOREAPI
18  * @brief common methods used to generate and strengthen cuts
19  * @author Jakob Witzig
20  *
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_CUTS_H__
26 #define __SCIP_CUTS_H__
27 
28 
29 #include "scip/def.h"
30 #include "blockmemshell/memory.h"
31 #include "scip/type_cons.h"
32 #include "scip/type_set.h"
33 #include "scip/type_stat.h"
34 #include "scip/type_misc.h"
35 #include "scip/type_prob.h"
36 #include "scip/type_sol.h"
37 #include "scip/type_lp.h"
38 
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42 
43 /**@addtogroup PublicCutMethods
44  *
45  * @{
46  */
47 
48 /** calculates a strong CG cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0 because
49  * these rows cannot participate in an MIR cut.
50  *
51  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
52  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
53  *
54  * @pre This method can be called if @p scip is in one of the following stages:
55  * - \ref SCIP_STAGE_SOLVING
56  *
57  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
58  */
59 extern
61  SCIP* scip, /**< SCIP data structure */
62  SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
63  SCIP_Bool usevbds, /**< should variable bounds be used in bound transformation? */
64  SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
65  int maxmksetcoefs, /**< maximal number of nonzeros allowed in aggregated base inequality */
66  SCIP_Real maxweightrange, /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
67  SCIP_Real minfrac, /**< minimal fractionality of rhs to produce strong CG cut for */
68  SCIP_Real maxfrac, /**< maximal fractionality of rhs to produce strong CG cut for */
69  SCIP_Real* weights, /**< row weights in row summation; some weights might be set to zero */
70  int* inds, /**< indices of non-zero entries in weights array, or NULL */
71  int ninds, /**< number of indices of non-zero entries in weights array, -1 if inds is
72  * NULL */
73  SCIP_Real scale, /**< additional scaling factor multiplied to all rows */
74  SCIP_Real* mircoef, /**< array to store strong CG coefficients: must be of size SCIPgetNVars() */
75  SCIP_Real* mirrhs, /**< pointer to store the right hand side of the strong CG row */
76  SCIP_Real* cutactivity, /**< pointer to store the activity of the resulting cut */
77  SCIP_Bool* success, /**< pointer to store whether the returned coefficients are a valid strong CG cut */
78  SCIP_Bool* cutislocal, /**< pointer to store whether the returned cut is only valid locally */
79  int* cutrank /**< pointer to store the rank of the returned cut; or NULL */
80  );
81 
82 /** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
83  * these rows cannot participate in an MIR cut.
84  *
85  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
86  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
87  *
88  * @pre This method can be called if @p scip is in one of the following stages:
89  * - \ref SCIP_STAGE_SOLVING
90  *
91  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
92  */
93 extern
95  SCIP* scip, /**< SCIP data structure */
96  SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
97  SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
98  SCIP_Bool usevbds, /**< should variable bounds be used in bound transformation? */
99  SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
100  SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
101  int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
102  * -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound;
103  * NULL for using closest bound for all variables */
104  SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
105  * NULL for using closest bound for all variables */
106  int maxmksetcoefs, /**< maximal number of nonzeros allowed in aggregated base inequality */
107  SCIP_Real maxweightrange, /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
108  SCIP_Real minfrac, /**< minimal fractionality of rhs to produce MIR cut for */
109  SCIP_Real maxfrac, /**< maximal fractionality of rhs to produce MIR cut for */
110  SCIP_Real* weights, /**< row weights in row summation; some weights might be set to zero */
111  SCIP_Real maxweight, /**< largest magnitude of weights; set to -1.0 if sparsity information is
112  * unknown */
113  int* weightinds, /**< sparsity pattern of weights; size nrowinds; NULL if sparsity info is
114  * unknown */
115  int nweightinds, /**< number of nonzeros in weights; -1 if rowinds is NULL */
116  int rowlensum, /**< total number of nonzeros in used rows (row associated with nonzero weight coefficient); -1 if unknown */
117  int* sidetypes, /**< specify row side type (-1 = lhs, 0 = unkown, 1 = rhs) or NULL for automatic choices */
118  SCIP_Real scale, /**< additional scaling factor multiplied to all rows */
119  SCIP_Real* mksetcoefs, /**< array to store mixed knapsack set coefficients: size nvars; or NULL */
120  SCIP_Bool* mksetcoefsvalid, /**< pointer to store whether mixed knapsack set coefficients are valid; or NULL */
121  SCIP_Real* mircoef, /**< array to store MIR coefficients: must be of size SCIPgetNVars() */
122  SCIP_Real* mirrhs, /**< pointer to store the right hand side of the MIR row */
123  SCIP_Real* cutactivity, /**< pointer to store the activity of the resulting cut */
124  SCIP_Bool* success, /**< pointer to store whether the returned coefficients are a valid MIR cut */
125  SCIP_Bool* cutislocal, /**< pointer to store whether the returned cut is only valid locally */
126  int* cutrank /**< pointer to store the rank of the returned cut; or NULL */
127  );
128 
129 /** applies the MIR function on a constraint; the constraint is given by pairs of variables and coefficients and a rhs.
130  *
131  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
132  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
133  *
134  * @pre This method can be called if @p scip is in one of the following stages:
135  * - \ref SCIP_STAGE_SOLVING
136  *
137  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
138  */
139 extern
141  SCIP* scip, /**< SCIP data structure */
142  SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
143  SCIP_Bool usevbds, /**< should variable bounds be used in bound transformation? */
144  SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
145  SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
146  int* boundsfortrans, /**< bounds that should be used for transformed variables: 0 vlb_idx/vub_idx,
147  * -1 for global lb/ub or -2 for local lb/ub
148  */
149  SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
150  * NULL for using closest bound for all variables */
151  SCIP_Real minfrac, /**< minimal fractionality of rhs to produce MIR cut for */
152  SCIP_Real maxfrac, /**< maximal fractionality of rhs to produce MIR cut for */
153  SCIP_Real scale, /**< additional scaling factor multiplied to all rows */
154  SCIP_Real* mksetcoefs, /**< array to store mixed knapsack set coefficients: size nvars; or NULL */
155  SCIP_Bool* mksetcoefsvalid, /**< pointer to store whether mixed knapsack set coefficients are valid; or NULL */
156  SCIP_Real* mircoef, /**< array to store MIR coefficients: must be of size SCIPgetNVars() */
157  SCIP_Real* mirrhs, /**< pointer to store the right hand side of the MIR row */
158  int* varinds, /**< array of variable indices with a mircoef != 0 */
159  int* nvarinds, /**< number of variables indices in varinds array */
160  SCIP_Real* minact, /**< pointer to store the minimal activity */
161  SCIP_Bool* varused, /**< array to store whether a variable has a mircoef != 0 */
162  SCIP_Bool* success, /**< pointer to store whether the returned coefficients are a valid MIR cut */
163  SCIP_Bool* islocal /**< pointer to store whether the returned constraint is only valid locally */
164  );
165 
166 /** removes all nearly-zero coefficients from MIR row and relaxes the right hand side accordingly in order to prevent
167  * numerical rounding errors
168  */
169 void SCIPcutsCleanupRow(
170  SCIP* scip, /**< SCIP data structure */
171  SCIP_Real* coefs, /**< array to store MIR coefficients: must be of size nvars */
172  SCIP_Real* rhs, /**< pointer to store the right hand side of the MIR row */
173  SCIP_Bool* varused, /**< array to flag variables that appear in the MIR constraint */
174  int* varinds, /**< sparsity pattern of non-zero MIR coefficients */
175  int* nvarinds, /**< pointer to number of non-zero MIR coefficients */
176  SCIP_Bool islocal /**< is the row only valid locally? */
177  );
178 
179 /* @} */
180 
181 #ifdef __cplusplus
182 }
183 #endif
184 
185 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_RETCODE SCIPcutsCalcStrongCG(SCIP *scip, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, int *inds, int ninds, SCIP_Real scale, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
Definition: cuts.c:3176
SCIP_RETCODE SCIPcutsCalcLpMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
Definition: cuts.c:3216
type definitions for miscellaneous datastructures
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for global SCIP settings
type definitions for problem statistics
type definitions for LP management
#define SCIP_Bool
Definition: def.h:61
type definitions for storing primal CIP solutions
type definitions for storing and manipulating the main problem
SCIP_RETCODE SCIPcutsApplyMIR(SCIP *scip, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, int *varinds, int *nvarinds, SCIP_Real *minact, SCIP_Bool *varused, SCIP_Bool *success, SCIP_Bool *islocal)
Definition: cuts.c:3269
void SCIPcutsCleanupRow(SCIP *scip, SCIP_Real *coefs, SCIP_Real *rhs, SCIP_Bool *varused, int *varinds, int *nvarinds, SCIP_Bool islocal)
Definition: cuts.c:3305
#define SCIP_Real
Definition: def.h:145
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers
memory allocation routines