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