Scippy

SCIP

Solving Constraint Integer Programs

heuristics.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 heuristics.h
17  * @ingroup PUBLICCOREAPI
18  * @brief methods commonly used by primal heuristics
19  * @author Gregor Hendel
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_HEURISTICS_H__
25 #define __SCIP_HEURISTICS_H__
26 
27 
28 #include "scip/scip.h"
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 /**@defgroup PublicSpecialHeuristicMethods Special Methods
35  * @ingroup PublicHeuristicMethods
36  * @brief methods commonly used by primal heuristics
37  *
38  * @{
39  */
40 
41 /** performs a diving within the limits of the diveset parameters
42  *
43  * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
44  * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
45  * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
46  *
47  * Starting from the current LP solution, the algorithm selects candidates which maximize the
48  * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
49  * and propagates the bound change on this candidate.
50  *
51  * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
52  * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
53  * or the last node is proven to be infeasible. It optionally backtracks and tries the
54  * other branching direction.
55  *
56  * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
57  * solved, and the old candidates are replaced by the new LP candidates.
58  *
59  * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
60  *
61  * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
62  * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
63  *
64  * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
65  * call will be executed, @see SCIPgetLastDiveNode().
66  */
67 extern
69  SCIP* scip, /**< SCIP data structure */
70  SCIP_DIVESET* diveset, /**< settings for diving */
71  SCIP_SOL* worksol, /**< non-NULL working solution */
72  SCIP_HEUR* heur, /**< the calling primal heuristic */
73  SCIP_RESULT* result, /**< SCIP result pointer */
74  SCIP_Bool nodeinfeasible /**< is the current node known to be infeasible? */
75  );
76 
77 /** get a sub-SCIP copy of the transformed problem */
78 extern
80  SCIP* sourcescip, /**< source SCIP data structure */
81  SCIP* subscip, /**< sub-SCIP used by the heuristic */
82  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
83  * target variables */
84  const char* suffix, /**< suffix for the problem name */
85  SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
86  SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
87  int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
88  SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
89  SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
90  SCIP_Bool* success, /**< was the copying successful? */
91  SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
92  );
93 
94 /* @} */
95 
96 #ifdef __cplusplus
97 }
98 #endif
99 
100 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)
Definition: heuristics.c:192
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:899
#define SCIP_Real
Definition: def.h:145
SCIP callable library.