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-2024 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
48extern "C" {
49#endif
50
51typedef struct SCIP_Prop SCIP_PROP; /**< propagator */
52typedef 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
common defines and data types used in all packages of SCIP
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:52
result codes for SCIP callback methods
type definitions for return codes for SCIP methods
type definitions for SCIP's main datastructure
timing definitions for SCIP