Scippy

SCIP

Solving Constraint Integer Programs

prop_probing.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 prop_probing.h
26  * @ingroup PROPAGATORS
27  * @brief probing propagator
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_PROP_PROBING_H__
34 #define __SCIP_PROP_PROBING_H__
35 
36 #include "scip/def.h"
37 #include "scip/type_lp.h"
38 #include "scip/type_retcode.h"
39 #include "scip/type_scip.h"
40 #include "scip/type_var.h"
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 
46 /** creates the probing propagator and includes it in SCIP
47  *
48  * @ingroup PropagatorIncludes
49  */
50 SCIP_EXPORT
52  SCIP* scip /**< SCIP data structure */
53  );
54 
55 /**@addtogroup PROPAGATORS
56  *
57  * @{
58  */
59 
60 /** applies and evaluates probing of a single variable in the given direction and bound */
61 SCIP_EXPORT
63  SCIP* scip, /**< SCIP data structure */
64  SCIP_VAR** vars, /**< problem variables */
65  int nvars, /**< number of problem variables */
66  int probingpos, /**< variable number to apply probing on */
67  SCIP_BOUNDTYPE boundtype, /**< which bound should be changed */
68  SCIP_Real bound, /**< which bound should be set */
69  int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
70  SCIP_Real* impllbs, /**< array to store lower bounds after applying implications and cliques */
71  SCIP_Real* implubs, /**< array to store upper bounds after applying implications and cliques */
72  SCIP_Real* proplbs, /**< array to store lower bounds after full propagation */
73  SCIP_Real* propubs, /**< array to store upper bounds after full propagation */
74  SCIP_Bool* cutoff /**< pointer to store whether the probing direction is infeasible */
75  );
76 
77 /** analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings
78  *
79  * Given a variable probingvar with domain [l,u] and bound tightening results from reducing the
80  * domain once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting
81  * variable fixations, aggregations, implications, and bound changes. Variable probingvar does not
82  * need to be binary. The whole domain of probingvar need to be covered by the left and right
83  * branches, i.e., we assume leftub >= rightlb for continuous variables or floor(leftub) >=
84  * ceil(rightlb)-1 for discrete variables. Bounds after applying implications and cliques do not
85  * need to be provided, but if they are omitted and probingvar is a binary variable, then already
86  * existing implications may be added.
87  */
88 SCIP_EXPORT
90  SCIP* scip, /**< SCIP data structure */
91  SCIP_VAR* probingvar, /**< the probing variable */
92  SCIP_Real leftub, /**< upper bound of probing variable in left branch */
93  SCIP_Real rightlb, /**< lower bound of probing variable in right branch */
94  int nvars, /**< number of variables which bound changes should be analyzed */
95  SCIP_VAR** vars, /**< variables which bound changes should be analyzed */
96  SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
97  SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
98  SCIP_Real* leftproplbs, /**< lower bounds after applying domain propagation in left branch */
99  SCIP_Real* leftpropubs, /**< upper bounds after applying domain propagation in left branch */
100  SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
101  SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
102  SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
103  SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
104  int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
105  int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */
106  int* nimplications, /**< pointer to counter which is increased by the number of deduced implications */
107  int* nchgbds, /**< pointer to counter which is increased by the number of deduced bound tightenings */
108  SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
109  );
110 
111 /** @} */
112 
113 #ifdef __cplusplus
114 }
115 #endif
116 
117 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
static long bound
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
type definitions for LP management
type definitions for SCIP&#39;s main datastructure
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPanalyzeDeductionsProbing(SCIP *scip, SCIP_VAR *probingvar, SCIP_Real leftub, SCIP_Real rightlb, int nvars, SCIP_VAR **vars, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, int *naggrvars, int *nimplications, int *nchgbds, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPapplyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Bool *cutoff)
#define SCIP_Real
Definition: def.h:186
SCIP_RETCODE SCIPincludePropProbing(SCIP *scip)
common defines and data types used in all packages of SCIP