Scippy

SCIP

Solving Constraint Integer Programs

pub_dive.h
Go to the documentation of this file.
1 
2 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
3 /* */
4 /* This file is part of the program and library */
5 /* SCIP --- Solving Constraint Integer Programs */
6 /* */
7 /* Copyright (C) 2002-2016 Konrad-Zuse-Zentrum */
8 /* fuer Informationstechnik Berlin */
9 /* */
10 /* SCIP is distributed under the terms of the ZIB Academic License. */
11 /* */
12 /* You should have received a copy of the ZIB Academic License */
13 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
14 /* */
15 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
16 
17 /**@file pub_dive.h
18  * @brief library methods for diving heuristics
19  * @author Gregor Hendel
20  */
21 
22 #ifndef PUB_DIVE_H_
23 #define PUB_DIVE_H_
24 
25 #include "scip/scip.h"
26 
27 #ifdef __cplusplus
28 extern "C" {
29 #endif
30 
31 /** performs a diving within the limits of the diveset parameters
32  *
33  * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
34  * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
35  * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
36  *
37  * Starting from the current LP solution, the algorithm selects candidates which maximize the
38  * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
39  * and propagates the bound change on this candidate.
40  *
41  * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
42  * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
43  * or the last node is proven to be infeasible. It optionally backtracks and tries the
44  * other branching direction.
45  *
46  * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
47  * solved, and the old candidates are replaced by the new LP candidates.
48  *
49  * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
50  *
51  * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
52  * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
53  *
54  * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
55  * call will be executed, @see SCIPgetLastDiveNode().
56  */
57 extern
59  SCIP* scip, /**< SCIP data structure */
60  SCIP_DIVESET* diveset, /**< settings for diving */
61  SCIP_SOL* worksol, /**< non-NULL working solution */
62  SCIP_HEUR* heur, /**< the calling primal heuristic */
63  SCIP_RESULT* result, /**< SCIP result pointer */
64  SCIP_Bool nodeinfeasible /**< is the current node known to be infeasible? */
65  );
66 
67 #ifdef __cplusplus
68 }
69 #endif
70 
71 #endif /* PUB_DIVE_H_ */
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:51
struct SCIP_Heur SCIP_HEUR
Definition: type_heur.h:50
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct SCIP_Diveset SCIP_DIVESET
Definition: type_heur.h:52
struct Scip SCIP
Definition: type_scip.h:30
struct SCIP_Sol SCIP_SOL
Definition: type_sol.h:45
#define SCIP_Bool
Definition: def.h:53
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)
SCIP callable library.