1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   struct_benders.h
26   	 * @ingroup INTERNALAPI
27   	 * @brief  data structures required for Benders' decomposition
28   	 * @author Stephen J. Maher
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_STRUCT_BENDERS_H__
34   	#define __SCIP_STRUCT_BENDERS_H__
35   	
36   	
37   	#include "scip/def.h"
38   	#include "scip/type_clock.h"
39   	#include "scip/type_benders.h"
40   	#include "scip/type_benderscut.h"
41   	
42   	#ifdef __cplusplus
43   	extern "C" {
44   	#endif
45   	
46   	struct SCIP_BenderscutCut
47   	{
48   	   SCIP_VAR**            vars;               /**< the variables forming the cut */
49   	   SCIP_Real*            vals;               /**< the coefficients of the variables in the cut */
50   	   SCIP_Real             lhs;                /**< the left hand side of the cut */
51   	   SCIP_Real             rhs;                /**< the right hand side of the cut */
52   	   int                   nvars;              /**< the number of variables in the cut */
53   	};
54   	typedef struct SCIP_BenderscutCut SCIP_BENDERSCUTCUT;
55   	
56   	/** Benders' decomposition data */
57   	struct SCIP_Benders
58   	{
59   	   char*                 name;               /**< name of Benders' decomposition */
60   	   char*                 desc;               /**< description of Benders' decomposition */
61   	   SCIP_DECL_BENDERSCOPY ((*benderscopy));   /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
62   	   SCIP_DECL_BENDERSFREE ((*bendersfree));   /**< destructor of Benders' decomposition */
63   	   SCIP_DECL_BENDERSINIT ((*bendersinit));   /**< initialize Benders' decomposition */
64   	   SCIP_DECL_BENDERSEXIT ((*bendersexit));   /**< deinitialize Benders' decomposition */
65   	   SCIP_DECL_BENDERSINITPRE((*bendersinitpre));/**< presolving initialization method for Benders' decomposition */
66   	   SCIP_DECL_BENDERSEXITPRE((*bendersexitpre));/**< presolving deinitialization method for Benders' decomposition */
67   	   SCIP_DECL_BENDERSINITSOL((*bendersinitsol));/**< solving process initialization method of Benders' decomposition */
68   	   SCIP_DECL_BENDERSEXITSOL((*bendersexitsol));/**< solving process deinitialization method of Benders' decomposition */
69   	   SCIP_DECL_BENDERSGETVAR((*bendersgetvar)); /**< returns the corresponding variable from the master or subproblem */
70   	   SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve));/**< called prior to the subproblem solving loop */
71   	   SCIP_DECL_BENDERSCREATESUB((*benderscreatesub));/**< creates the Benders' decomposition subproblems */
72   	   SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex));/**< the solving method for convex Benders' decomposition subproblems */
73   	   SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub));/**< the solving method for the Benders' decomposition subproblems */
74   	   SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve));/**< called after the subproblems are solved. */
75   	   SCIP_DECL_BENDERSFREESUB((*bendersfreesub));/**< the freeing method for the Benders' decomposition subproblems */
76   	   SCIP_DECL_SORTPTRCOMP((*benderssubcomp)); /**< a comparator for defining the solving order of the subproblems */
77   	   SCIP_BENDERSDATA*     bendersdata;        /**< Benders' decomposition local data */
78   	   SCIP_CLOCK*           setuptime;          /**< time spend for setting up this Benders' decomposition for the next stages */
79   	   SCIP_CLOCK*           bendersclock;       /**< Benders' decomposition execution time */
80   	   int                   priority;           /**< priority of the Benders' decomposition */
81   	   int                   ncalls;             /**< number of times, this Benders' decomposition was called */
82   	   int                   ncutsfound;         /**< number of cuts found by the Benders' decomposition */
83   	   int                   ntransferred;       /**< number of cuts transferred from sub SCIP to the master SCIP */
84   	   SCIP_Bool             active;             /**< is the Benders' decomposition active? */
85   	   SCIP_Bool             initialized;        /**< is Benders' decomposition initialized? */
86   	   SCIP_Bool             cutlp;              /**< should Benders' cuts be generated for LP solutions? */
87   	   SCIP_Bool             cutpseudo;          /**< should Benders' cuts be generated for pseudo solutions? */
88   	   SCIP_Bool             cutrelax;           /**< should Benders' cuts be generated for relaxation solutions? */
89   	   SCIP_Bool             shareauxvars;       /**< should this Benders' share the highest priority Benders' auxiliary vars */
90   	
91   	   /* additional Benders' decomposition parameters */
92   	   SCIP_Bool             transfercuts;       /**< should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
93   	   SCIP_Bool             lnscheck;           /**< should Benders' decomposition be used in LNS heuristics? */
94   	   int                   lnsmaxdepth;        /**< maximum depth at which the LNS check is performed */
95   	   int                   lnsmaxcalls;        /**< maximum number of Benders' decomposition call in LNS heuristics */
96   	   int                   lnsmaxcallsroot;    /**< maximum number of root node Benders' decomposition call in LNS heuristics */
97   	   SCIP_Bool             cutsasconss;        /**< should the transferred cuts be added as constraints? */
98   	   SCIP_Real             subprobfrac;        /**< fraction of subproblems that are solved in each iteration */
99   	   SCIP_Bool             updateauxvarbound;  /**< should the auxiliary variable lower bound be updated by solving the subproblem? */
100  	   SCIP_Bool             auxvarsimplint;     /**< if subproblem objective is integer, then set the auxiliary variables as implint */
101  	   SCIP_Bool             cutcheck;           /**< should cuts be generated while checking solutions? */
102  	   SCIP_Bool             threadsafe;         /**< has the copy been created requiring thread safety */
103  	   SCIP_Real             solutiontol;        /**< storing the tolerance for optimality in Benders' decomposition */
104  	   int                   numthreads;         /**< the number of threads to use when solving the subproblem */
105  	   SCIP_Bool             execfeasphase;      /**< should a feasibility phase be executed during the root node, i.e.
106  	                                                  adding slack variables to constraints to ensure feasibility */
107  	   SCIP_Real             slackvarcoef;       /**< the initial objective coefficient of the slack variables in the subproblem */
108  	   SCIP_Real             maxslackvarcoef;    /**< the maximal objective coefficient of the slack variables in the subproblem */
109  	   SCIP_Bool             checkconsconvexity; /**< should the constraints of the subproblems be checked for convexity? */
110  	   SCIP_NLPPARAM         nlpparam;           /**< parameters for NLP solves */
111  	
112  	   /* information for heuristics */
113  	   SCIP*                 sourcescip;         /**< the source scip from when the Benders' was copied */
114  	   SCIP_Bool             iscopy;             /**< is the Benders' decomposition struct a copy */
115  	   SCIP_HASHMAP*         mastervarsmap;      /**< hash map for the master variables from the subscip to the master */
116  	
117  	   /* the subproblem information */
118  	   SCIP**                subproblems;        /**< the Benders' decomposition subproblems */
119  	   SCIP_VAR**            auxiliaryvars;      /**< the auxiliary variables for the Benders' optimality cuts */
120  	   SCIP_PQUEUE*          subprobqueue;       /**< the priority queue for the subproblems */
121  	   SCIP_SUBPROBLEMSOLVESTAT** solvestat;     /**< storing the solving statistics of all the subproblems */
122  	   SCIP_Real*            subprobobjval;      /**< the objective value of the subproblem in the current iteration */
123  	   SCIP_Real*            bestsubprobobjval;  /**< the best objective value of the subproblem */
124  	   SCIP_Real*            subproblowerbound;  /**< a lower bound on the subproblem - used for the integer cuts */
125  	   int                   naddedsubprobs;     /**< subproblems added to the Benders' decomposition data */
126  	   int                   nsubproblems;       /**< number of subproblems */
127  	   SCIP_BENDERSSUBTYPE*  subprobtype;        /**< the convexity type of the subproblem */
128  	   SCIP_Bool*            subprobisconvex;    /**< is the subproblem convex? This implies that the dual sol can be used for cuts */
129  	   SCIP_Bool*            subprobisnonlinear; /**< does the subproblem contain non-linear constraints */
130  	   int                   nconvexsubprobs;    /**< the number of subproblems that are convex */
131  	   int                   nnonlinearsubprobs; /**< the number of subproblems that are non-linear */
132  	   SCIP_Bool             subprobscreated;    /**< have the subproblems been created for this Benders' decomposition.
133  	                                                  This flag is used when retransforming the problem.*/
134  	   SCIP_Bool*            mastervarscont;     /**< flag to indicate that the master problem variable have been converted
135  	                                               to continuous variables. */
136  	   SCIP_Bool*            subprobsetup;       /**< flag to indicate whether the subproblem has been set up. */
137  	   SCIP_Bool*            indepsubprob;       /**< flag to indicate if a subproblem is independent of the master prob */
138  	   SCIP_Bool*            subprobenabled;     /**< flag to indicate whether the subproblem is enabled */
139  	   int                   nactivesubprobs;    /**< the number of active subproblems */
140  	   SCIP_Bool             freesubprobs;       /**< do the subproblems need to be freed by the Benders' decomposition core? */
141  	   SCIP_Bool             masterisnonlinear;  /**< flag to indicate whether the master problem contains non-linear constraints */
142  	
143  	   /* cut strengthening details */
144  	   SCIP_SOL*             corepoint;          /**< the point that is separated for stabilisation */
145  	   SCIP_SOL*             initcorepoint;      /**< the point that was used to initialise the core point */
146  	   SCIP_Real             convexmult;         /**< the multiplier for the convex comb of the LP and sepa point */
147  	   SCIP_Real             perturbeps;         /**< epsilon value to perturb the LP solution */
148  	   int                   noimprovecount;     /**< count of the iterations without improvement */
149  	   int                   noimprovelimit;     /**< limit used to change behaviour of stabilitation */
150  	   SCIP_NODE*            prevnode;           /**< the previous node where the cut strengthening was performed */
151  	   SCIP_Longint          prevnlpiter;        /**< number of LP iters at the previous call of the cut strengthening */
152  	   SCIP_Real             prevlowerbound;     /**< the lowerbound from the previous LP enforcement iteration */
153  	   SCIP_Bool             strengthenenabled;  /**< is the core point cut strengthening enabled */
154  	   char                  strengthenintpoint; /**< where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros)  */
155  	   SCIP_Bool             strengthenround;    /**< flag to indicate whether a cut strengthening round is being performed */
156  	   int                   nstrengthencuts;    /**< the number of strengthened cuts found */
157  	   int                   nstrengthencalls;   /**< the number of calls to the strengthening round */
158  	   int                   nstrengthenfails;   /**< the number of calls to the strengthening round that fail to find cuts */
159  	
160  	   /* solving process information */
161  	   int                   npseudosols;        /**< the number of pseudo solutions checked since the last generated cut */
162  	   SCIP_Bool             feasibilityphase;   /**< is the Benders' decomposition in a feasibility phase, i.e. using slack variables */
163  	
164  	   /* Bender's cut information */
165  	   SCIP_BENDERSCUT**     benderscuts;        /**< the available Benders' cut algorithms */
166  	   int                   nbenderscuts;       /**< the number of Benders' cut algorithms */
167  	   int                   benderscutssize;    /**< the size of the Benders' cuts algorithms array */
168  	   SCIP_Bool             benderscutssorted;  /**< are the Benders' cuts algorithms sorted by priority */
169  	   SCIP_Bool             benderscutsnamessorted;/**< are the Benders' cuts algorithms sorted by name */
170  	
171  	   /* cut storage information */
172  	   SCIP_BENDERSCUTCUT**  storedcuts;         /**< array to store the data required to form a cut/constraint */
173  	   int                   storedcutssize;     /**< the size of the added cuts array */
174  	   int                   nstoredcuts;        /**< the number of the added cuts */
175  	
176  	};
177  	
178  	/** statistics for solving the subproblems. Used for prioritising the solving of the subproblem */
179  	struct SCIP_SubproblemSolveStat
180  	{
181  	   int                   idx;                /**< the index of the subproblem */
182  	   int                   ncalls;             /**< the number of times this subproblems has been solved */
183  	   SCIP_Real             avgiter;            /**< the average number of LP/NLP iterations performed */
184  	};
185  	
186  	/** parameters that are set to solve the subproblem. This will be changed from what the user inputs, so they are stored
187  	 *  and reset after the solving loop. */
188  	struct SCIP_SubproblemParams
189  	{
190  	   SCIP_Real limits_memory;
191  	   SCIP_Real limits_time;
192  	   int cons_linear_propfreq;
193  	   int lp_disablecutoff;
194  	   int lp_scaling;
195  	   int prop_maxrounds;
196  	   int prop_maxroundsroot;
197  	   char lp_initalg;
198  	   char lp_resolvealg;
199  	   SCIP_Bool conflict_enable;
200  	   SCIP_Bool lp_alwaysgetduals;
201  	   SCIP_Bool misc_catchctrlc;
202  	   SCIP_Bool misc_scaleobj;
203  	};
204  	typedef struct SCIP_SubproblemParams SCIP_SUBPROBPARAMS;
205  	
206  	#ifdef __cplusplus
207  	}
208  	#endif
209  	
210  	#endif
211