Scippy

SCIP

Solving Constraint Integer Programs

type_prop.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-2023 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 type_prop.h
26  * @ingroup TYPEDEFINITIONS
27  * @brief type definitions for propagators
28  * @author Tobias Achterberg
29  */
30 
31 /** @defgroup DEFPLUGINS_PROP Default Propagators
32  * @ingroup DEFPLUGINS
33  * @brief implementation files (.c files) of the default propagators of SCIP
34  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #ifndef __SCIP_TYPE_PROP_H__
39 #define __SCIP_TYPE_PROP_H__
40 
41 #include "scip/def.h"
42 #include "scip/type_retcode.h"
43 #include "scip/type_result.h"
44 #include "scip/type_scip.h"
45 #include "scip/type_timing.h"
46 
47 #ifdef __cplusplus
48 extern "C" {
49 #endif
50 
51 typedef struct SCIP_Prop SCIP_PROP; /**< propagator */
52 typedef struct SCIP_PropData SCIP_PROPDATA; /**< locally defined propagator data */
53 
54 
55 /** copy method for propagator plugins (called when SCIP copies plugins)
56  *
57  * input:
58  * - scip : SCIP main data structure
59  * - prop : the propagator itself
60  */
61 #define SCIP_DECL_PROPCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
62 
63 /** destructor of propagator to free user data (called when SCIP is exiting)
64  *
65  * input:
66  * - scip : SCIP main data structure
67  * - prop : the propagator itself
68  */
69 #define SCIP_DECL_PROPFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
70 
71 /** initialization method of propagator (called after problem was transformed)
72  *
73  * input:
74  * - scip : SCIP main data structure
75  * - prop : the propagator itself
76  */
77 #define SCIP_DECL_PROPINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
78 
79 /** deinitialization method of propagator (called before transformed problem is freed)
80  *
81  * input:
82  * - scip : SCIP main data structure
83  * - prop : the propagator itself
84  */
85 #define SCIP_DECL_PROPEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
86 
87 /** presolving initialization method of propagator (called when presolving is about to begin)
88  *
89  * This method is called when the presolving process is about to begin, even if presolving is turned off. The
90  * propagator may use this call to initialize its presolving data, before the presolving process begins.
91  *
92  * Necessary modifications that have to be performed even if presolving is turned off should be done here or in the
93  * presolving deinitialization call (SCIP_DECL_PROPEXITPRE()).
94  *
95  * input:
96  * - scip : SCIP main data structure
97  * - prop : the propagator itself
98  */
99 #define SCIP_DECL_PROPINITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
100 
101 /** presolving deinitialization method of propagator (called after presolving has been finished)
102  *
103  * This method is called after the presolving has been finished, even if presolving is turned off.
104  * The propagator may use this call e.g. to clean up its presolving data.
105  *
106  * Besides necessary modifications and clean up, no time consuming operations should be performed, especially if the
107  * problem has already been solved. Use the method SCIPgetStatus(), which in this case returns SCIP_STATUS_OPTIMAL,
108  * SCIP_STATUS_INFEASIBLE, SCIP_STATUS_UNBOUNDED, or SCIP_STATUS_INFORUNBD.
109  *
110  * input:
111  * - scip : SCIP main data structure
112  * - prop : the propagator itself
113  */
114 #define SCIP_DECL_PROPEXITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
115 
116 /** solving process initialization method of propagator (called when branch and bound process is about to begin)
117  *
118  * This method is called when the presolving was finished and the branch and bound process is about to begin.
119  * The propagator may use this call to initialize its branch and bound specific data.
120  *
121  * Besides necessary modifications and clean up, no time consuming operations should be performed, especially if the
122  * problem has already been solved. Use the method SCIPgetStatus(), which in this case returns SCIP_STATUS_OPTIMAL,
123  * SCIP_STATUS_INFEASIBLE, SCIP_STATUS_UNBOUNDED, or SCIP_STATUS_INFORUNBD.
124  *
125  * input:
126  * - scip : SCIP main data structure
127  * - prop : the propagator itself
128  */
129 #define SCIP_DECL_PROPINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop)
130 
131 /** solving process deinitialization method of propagator (called before branch and bound process data is freed)
132  *
133  * This method is called before the branch and bound process is freed.
134  * The propagator should use this call to clean up its branch and bound data.
135  *
136  * input:
137  * - scip : SCIP main data structure
138  * - prop : the propagator itself
139  * - restart : was this exit solve call triggered by a restart?
140  */
141 #define SCIP_DECL_PROPEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, SCIP_Bool restart)
142 
143 /** presolving method of propagator
144  *
145  * The presolver should go through the variables and constraints and tighten the domains or
146  * constraints. Each tightening should increase the given total numbers of changes.
147  *
148  * input:
149  * - scip : SCIP main data structure
150  * - prop : the propagator itself
151  * - nrounds : number of presolving rounds already done
152  * - presoltiming : current presolving timing
153  * - nnewfixedvars : number of variables fixed since the last call to the presolving method
154  * - nnewaggrvars : number of variables aggregated since the last call to the presolving method
155  * - nnewchgvartypes : number of variable type changes since the last call to the presolving method
156  * - nnewchgbds : number of variable bounds tightened since the last call to the presolving method
157  * - nnewholes : number of domain holes added since the last call to the presolving method
158  * - nnewdelconss : number of deleted constraints since the last call to the presolving method
159  * - nnewaddconss : number of added constraints since the last call to the presolving method
160  * - nnewupgdconss : number of upgraded constraints since the last call to the presolving method
161  * - nnewchgcoefs : number of changed coefficients since the last call to the presolving method
162  * - nnewchgsides : number of changed left or right hand sides since the last call to the presolving method
163  *
164  * @note the counters state the changes since the last call including the changes of this presolving method during its
165  * last call
166  *
167  * @note if the propagator uses dual information for presolving it is nesassary to check via calling SCIPallowWeakDualReds
168  * or SCIPallowStrongDualReds if dual reductions are allowed.
169  *
170  * input/output:
171  * - nfixedvars : pointer to total number of variables fixed of all presolvers
172  * - naggrvars : pointer to total number of variables aggregated of all presolvers
173  * - nchgvartypes : pointer to total number of variable type changes of all presolvers
174  * - nchgbds : pointer to total number of variable bounds tightened of all presolvers
175  * - naddholes : pointer to total number of domain holes added of all presolvers
176  * - ndelconss : pointer to total number of deleted constraints of all presolvers
177  * - naddconss : pointer to total number of added constraints of all presolvers
178  * - nupgdconss : pointer to total number of upgraded constraints of all presolvers
179  * - nchgcoefs : pointer to total number of changed coefficients of all presolvers
180  * - nchgsides : pointer to total number of changed left/right hand sides of all presolvers
181  *
182  * output:
183  * - result : pointer to store the result of the presolving call
184  *
185  * possible return values for *result:
186  * - SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in obj. direction -> problem is unbounded
187  * - SCIP_CUTOFF : at least one constraint is infeasible in the variable's bounds -> problem is infeasible
188  * - SCIP_SUCCESS : the presolving method found a reduction
189  * - SCIP_DIDNOTFIND : the presolving method searched, but did not find a presolving change
190  * - SCIP_DIDNOTRUN : the presolving method was skipped
191  * - SCIP_DELAYED : the presolving method was skipped, but should be called again
192  */
193 #define SCIP_DECL_PROPPRESOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, int nrounds, SCIP_PRESOLTIMING presoltiming, \
194  int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, \
195  int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, \
196  int* nfixedvars, int* naggrvars, int* nchgvartypes, int* nchgbds, int* naddholes, \
197  int* ndelconss, int* naddconss, int* nupgdconss, int* nchgcoefs, int* nchgsides, SCIP_RESULT* result)
198 
199 /** execution method of propagator
200  *
201  * Searches for domain propagations. The method is called in the node processing loop.
202  *
203  * input:
204  * - scip : SCIP main data structure
205  * - prop : the propagator itself
206  * - proptiming : current point in the node solving loop
207  * - result : pointer to store the result of the propagation call
208  *
209  * possible return values for *result:
210  * - SCIP_CUTOFF : the current node is infeasible for the current domains
211  * - SCIP_REDUCEDDOM : at least one domain reduction was found
212  * - SCIP_DIDNOTFIND : the propagator searched, but did not find a domain reduction
213  * - SCIP_DIDNOTRUN : the propagator was skipped
214  * - SCIP_DELAYED : the propagator was skipped, but should be called again
215  * - SCIP_DELAYNODE : the current node should be postponed (return value only valid for BEFORELP propagation)
216  */
217 #define SCIP_DECL_PROPEXEC(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, SCIP_PROPTIMING proptiming, SCIP_RESULT* result)
218 
219 
220 /** propagation conflict resolving method of propagator
221  *
222  * This method is called during conflict analysis. If the propagator wants to support conflict analysis,
223  * it should call SCIPinferVarLbProp() or SCIPinferVarUbProp() in domain propagation instead of SCIPchgVarLb() or
224  * SCIPchgVarUb() in order to deduce bound changes on variables.
225  * In the SCIPinferVarLbProp() and SCIPinferVarUbProp() calls, the propagator provides a pointer to itself
226  * and an integer value "inferinfo" that can be arbitrarily chosen.
227  * The propagation conflict resolving method can then be implemented, to provide a "reasons" for the bound
228  * changes, i.e. the bounds of variables at the time of the propagation, that forced the propagator to set the
229  * conflict variable's bound to its current value. It can use the "inferinfo" tag to identify its own propagation
230  * rule and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided
231  * by calls to SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(),
232  * SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), and/or SCIPaddConflictBinvar() in the propagation conflict
233  * resolving method.
234  *
235  * See the description of the propagation conflict resolving method of constraint handlers for further details.
236  *
237  * @note if the propagtor uses dual information it is nesassary to check via calling SCIPallowWeakDualReds and
238  * SCIPallowStrongDualReds if dual reductions and propgation with the current cutoff bound, resp., are allowed.
239  *
240  * input:
241  * - scip : SCIP main data structure
242  * - prop : the propagator itself
243  * - infervar : the conflict variable whose bound change has to be resolved
244  * - inferinfo : the user information passed to the corresponding SCIPinferVarLbProp() or SCIPinferVarUbProp() call
245  * - boundtype : the type of the changed bound (lower or upper bound)
246  * - bdchgidx : the index of the bound change, representing the point of time where the change took place
247  * - relaxedbd : the relaxed bound which is sufficient to be explained
248  *
249  * output:
250  * - result : pointer to store the result of the propagation conflict resolving call
251  *
252  * possible return values for *result:
253  * - SCIP_SUCCESS : the conflicting bound change has been successfully resolved by adding all reason bounds
254  * - SCIP_DIDNOTFIND : the conflicting bound change could not be resolved and has to be put into the conflict set
255  *
256  * @note it is sufficient to explain/resolve the relaxed bound
257  */
258 #define SCIP_DECL_PROPRESPROP(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, SCIP_VAR* infervar, int inferinfo, \
259  SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX* bdchgidx, SCIP_Real relaxedbd, SCIP_RESULT* result)
260 
261 #ifdef __cplusplus
262 }
263 #endif
264 
265 #endif
timing definitions for SCIP
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:52
result codes for SCIP callback methods
common defines and data types used in all packages of SCIP