Scippy

SCIP

Solving Constraint Integer Programs

struct_benders.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-2019 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 struct_benders.h
17  * @ingroup INTERNALAPI
18  * @brief data structures required for Benders' decomposition
19  * @author Stephen J. Maher
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_STRUCT_BENDERS_H__
25 #define __SCIP_STRUCT_BENDERS_H__
26 
27 
28 #include "scip/def.h"
29 #include "scip/type_clock.h"
30 #include "scip/type_benders.h"
31 #include "scip/type_benderscut.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 /** Benders' decomposition data */
39 {
40  char* name; /**< name of Benders' decomposition */
41  char* desc; /**< description of Benders' decomposition */
42  SCIP_DECL_BENDERSCOPY ((*benderscopy)); /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
43  SCIP_DECL_BENDERSFREE ((*bendersfree)); /**< destructor of Benders' decomposition */
44  SCIP_DECL_BENDERSINIT ((*bendersinit)); /**< initialize Benders' decomposition */
45  SCIP_DECL_BENDERSEXIT ((*bendersexit)); /**< deinitialize Benders' decomposition */
46  SCIP_DECL_BENDERSINITPRE((*bendersinitpre));/**< presolving initialization method for Benders' decomposition */
47  SCIP_DECL_BENDERSEXITPRE((*bendersexitpre));/**< presolving deinitialization method for Benders' decomposition */
48  SCIP_DECL_BENDERSINITSOL((*bendersinitsol));/**< solving process initialization method of Benders' decomposition */
49  SCIP_DECL_BENDERSEXITSOL((*bendersexitsol));/**< solving process deinitialization method of Benders' decomposition */
50  SCIP_DECL_BENDERSGETVAR((*bendersgetvar)); /**< returns the corresponding variable from the master or subproblem */
51  SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve));/**< called prior to the subproblem solving loop */
52  SCIP_DECL_BENDERSCREATESUB((*benderscreatesub));/**< creates the Benders' decomposition subproblems */
53  SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex));/**< the solving method for convex Benders' decomposition subproblems */
54  SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub));/**< the solving method for the Benders' decomposition subproblems */
55  SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve));/**< called after the subproblems are solved. */
56  SCIP_DECL_BENDERSFREESUB((*bendersfreesub));/**< the freeing method for the Benders' decomposition subproblems */
57  SCIP_BENDERSDATA* bendersdata; /**< Benders' decomposition local data */
58  SCIP_CLOCK* setuptime; /**< time spend for setting up this Benders' decomposition for the next stages */
59  SCIP_CLOCK* bendersclock; /**< Benders' decomposition execution time */
60  int priority; /**< priority of the Benders' decomposition */
61  int ncalls; /**< number of times, this Benders' decomposition was called */
62  int ncutsfound; /**< number of cuts found by the Benders' decomposition */
63  int ntransferred; /**< number of cuts transferred from sub SCIP to the master SCIP */
64  SCIP_Bool active; /**< is the Benders' decomposition active? */
65  SCIP_Bool initialized; /**< is Benders' decomposition initialized? */
66  SCIP_Bool cutlp; /**< should Benders' cuts be generated for LP solutions? */
67  SCIP_Bool cutpseudo; /**< should Benders' cuts be generated for pseudo solutions? */
68  SCIP_Bool cutrelax; /**< should Benders' cuts be generated for relaxation solutions? */
69  SCIP_Bool shareauxvars; /**< should this Benders' share the highest priority Benders' auxiliary vars */
70 
71  /* additional Benders' decomposition parameters */
72  SCIP_Bool transfercuts; /**< should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
73  SCIP_Bool lnscheck; /**< should Benders' decomposition be used in LNS heuristics? */
74  int lnsmaxdepth; /**< maximum depth at which the LNS check is performed */
75  SCIP_Bool cutsasconss; /**< should the transferred cuts be added as constraints? */
76  SCIP_Real subprobfrac; /**< fraction of subproblems that are solved in each iteration */
77  SCIP_Bool updateauxvarbound; /**< should the auxiliary variable lower bound be updated by solving the subproblem? */
78 
79  /* information for heuristics */
80  SCIP* sourcescip; /**< the source scip from when the Benders' was copied */
81  SCIP_Bool iscopy; /**< is the Benders' decomposition struct a copy */
82  SCIP_HASHMAP* mastervarsmap; /**< hash map for the master variables from the subscip to the master */
83 
84  /* the subproblem information */
85  SCIP** subproblems; /**< the Benders' decomposition subproblems */
86  SCIP_VAR** auxiliaryvars; /**< the auxiliary variables for the Benders' optimality cuts */
87  SCIP_Real* subprobobjval; /**< the objective value of the subproblem in the current iteration */
88  SCIP_Real* bestsubprobobjval; /**< the best objective value of the subproblem */
89  SCIP_Real* subproblowerbound; /**< a lower bound on the subproblem - used for the integer cuts */
90  int naddedsubprobs; /**< subproblems added to the Benders' decomposition data */
91  int nsubproblems; /**< number of subproblems */
92  SCIP_Bool* subprobisconvex; /**< is the subproblem convex? This implies that the dual sol can be used for cuts */
93  int nconvexsubprobs; /**< the number of subproblems that are convex */
94  SCIP_Bool subprobscreated; /**< have the subproblems been created for this Benders' decomposition.
95  This flag is used when retransforming the problem.*/
96  SCIP_Bool* mastervarscont; /**< flag to indicate that the master problem variable have been converted
97  to continuous variables. */
98  SCIP_Bool* subprobsetup; /**< flag to indicate whether the subproblem has been set up. */
99  SCIP_Bool* indepsubprob; /**< flag to indicate if a subproblem is independent of the master prob */
100  SCIP_Bool* subprobenabled; /**< flag to indicate whether the subproblem is enabled */
101  int nactivesubprobs; /**< the number of active subproblems */
102  int firstchecked; /**< the subproblem index first checked in the current iteration */
103  int lastchecked; /**< the subproblem index last checked in the current iteration */
104 
105  /* solving process information */
106  int npseudosols; /**< the number of pseudo solutions checked since the last generated cut */
107 
108  /* Bender's cut information */
109  SCIP_BENDERSCUT** benderscuts; /**< the available Benders' cut algorithms */
110  int nbenderscuts; /**< the number of Benders' cut algorithms */
111  int benderscutssize; /**< the size of the Benders' cuts algorithms array */
112  SCIP_Bool benderscutssorted; /**< are the Benders' cuts algorithms sorted by priority */
113  SCIP_Bool benderscutsnamessorted;/**< are the Benders' cuts algorithms sorted by name */
114 };
115 
116 /** parameters that are set to solve the subproblem. This will be changed from what the user inputs, so they are stored
117  * and reset after the solving loop. */
119 {
133 };
135 
136 #ifdef __cplusplus
137 }
138 #endif
139 
140 #endif
SCIP_BENDERSDATA * bendersdata
SCIP_HASHMAP * mastervarsmap
SCIP_DECL_BENDERSINIT((*bendersinit))
SCIP_Bool cutsasconss
SCIP_CLOCK * bendersclock
SCIP_Real * bestsubprobobjval
SCIP_Bool * subprobenabled
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))
SCIP_Bool benderscutssorted
SCIP_Bool * indepsubprob
SCIP_Bool updateauxvarbound
SCIP_Bool subprobscreated
SCIP_DECL_BENDERSFREESUB((*bendersfreesub))
SCIP ** subproblems
SCIP_Real * subprobobjval
SCIP_Bool lnscheck
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))
SCIP_DECL_BENDERSEXIT((*bendersexit))
SCIP * sourcescip
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))
SCIP_Bool * subprobisconvex
SCIP_Bool transfercuts
SCIP_Bool benderscutsnamessorted
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:63
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))
SCIP_Bool shareauxvars
SCIP_Bool cutrelax
#define SCIP_Bool
Definition: def.h:69
SCIP_DECL_BENDERSINITSOL((*bendersinitsol))
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))
type definitions for Benders&#39; decomposition methods
type definitions for clocks and timing issues
SCIP_Bool cutpseudo
type definitions for Benders&#39; decomposition cut
SCIP_DECL_BENDERSFREE((*bendersfree))
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))
SCIP_Bool * mastervarscont
SCIP_Bool active
SCIP_Bool * subprobsetup
#define SCIP_Real
Definition: def.h:157
SCIP_Bool iscopy
SCIP_Bool cutlp
common defines and data types used in all packages of SCIP
SCIP_VAR ** auxiliaryvars
SCIP_DECL_BENDERSCREATESUB((*benderscreatesub))
SCIP_DECL_BENDERSCOPY((*benderscopy))
SCIP_Bool initialized
SCIP_DECL_BENDERSGETVAR((*bendersgetvar))
SCIP_Real * subproblowerbound
SCIP_BENDERSCUT ** benderscuts
SCIP_DECL_BENDERSINITPRE((*bendersinitpre))
SCIP_Real subprobfrac
SCIP_CLOCK * setuptime