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