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   type_benders.h
26   	 * @ingroup TYPEDEFINITIONS
27   	 * @brief  type definitions for Benders' decomposition methods
28   	 * @author Stephen J. Maher
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_TYPE_BENDERS_H__
34   	#define __SCIP_TYPE_BENDERS_H__
35   	
36   	#include "scip/def.h"
37   	#include "scip/type_retcode.h"
38   	#include "scip/type_scip.h"
39   	
40   	#ifdef __cplusplus
41   	extern "C" {
42   	#endif
43   	
44   	enum SCIP_BendersEnfoType
45   	{
46   	    SCIP_BENDERSENFOTYPE_LP      = 1,        /**< the Benders' subproblems are solved during the enforcement of an LP solution */
47   	    SCIP_BENDERSENFOTYPE_RELAX   = 2,        /**< the Benders' subproblems are solved during the enforcement of a relaxation solution */
48   	    SCIP_BENDERSENFOTYPE_PSEUDO  = 3,        /**< the Benders' subproblems are solved during the enforcement of a pseudo solution */
49   	    SCIP_BENDERSENFOTYPE_CHECK   = 4         /**< the Benders' subproblems are solved during the checking of a solution for feasibility */
50   	};
51   	typedef enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE;  /**< indicates the callback in cons_benders and cons_benderslp that triggered the subproblem solve */
52   	
53   	enum SCIP_BendersSolveLoop
54   	{
55   	   SCIP_BENDERSSOLVELOOP_CONVEX     = 0,     /**< the relaxation is solved in this iteration of the loop */
56   	   SCIP_BENDERSSOLVELOOP_CIP        = 1,     /**< the CIP is solved in this iteration of the loop */
57   	   SCIP_BENDERSSOLVELOOP_USERCONVEX = 2,     /**< the user defined solve function is called */
58   	   SCIP_BENDERSSOLVELOOP_USERCIP    = 3      /**< the user defined solve function is called */
59   	};
60   	typedef enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP;   /**< identifies the type of problem solved in each solve loop */
61   	
62   	enum SCIP_BendersSubStatus
63   	{
64   	   SCIP_BENDERSSUBSTATUS_UNKNOWN    = 0,     /**< the subsystem status is unknown */
65   	   SCIP_BENDERSSUBSTATUS_OPTIMAL    = 1,     /**< the subsystem is solved to be optimal */
66   	   SCIP_BENDERSSUBSTATUS_AUXVIOL    = 2,     /**< the subproblem is optimal, but the auxiliary variable is violated */
67   	   SCIP_BENDERSSUBSTATUS_INFEAS     = 3      /**< the subproblem is solved to be infeasible */
68   	};
69   	typedef enum SCIP_BendersSubStatus SCIP_BENDERSSUBSTATUS;
70   	
71   	enum SCIP_BendersSubType
72   	{
73   	   SCIP_BENDERSSUBTYPE_CONVEXCONT      = 0,  /**< the subproblem has convex constraints and continuous variables */
74   	   SCIP_BENDERSSUBTYPE_CONVEXDIS       = 1,  /**< the subproblem has convex constraints and discrete variables */
75   	   SCIP_BENDERSSUBTYPE_NONCONVEXCONT   = 2,  /**< the subproblem has non-convex constraints and continuous variables */
76   	   SCIP_BENDERSSUBTYPE_NONCONVEXDIS    = 3,  /**< the subproblem has non-convex constraints and discrete variables */
77   	   SCIP_BENDERSSUBTYPE_UNKNOWN         = 4,  /**< the default type before the type is known */
78   	};
79   	typedef enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE;
80   	
81   	typedef struct SCIP_Benders SCIP_BENDERS;           /**< Benders' decomposition data */
82   	typedef struct SCIP_BendersData SCIP_BENDERSDATA;   /**< locally defined Benders' decomposition data */
83   	typedef struct SCIP_SubproblemSolveStat SCIP_SUBPROBLEMSOLVESTAT; /**< the solving statistics of the subproblems */
84   	
85   	
86   	/** copy method for Benders' decomposition plugins (called when SCIP copies plugins). If there is an active Benders'
87   	 *  decomposition, all copies are not valid. As such, there is no valid parameter that is passed to the callback
88   	 *  function
89   	 *
90   	 *  input:
91   	 *  - scip            : SCIP main data structure
92   	 *  - benders         : the Benders' decomposition itself
93   	 *  - threadsafe      : must the Benders' decomposition copy be thread safe
94   	 */
95   	#define SCIP_DECL_BENDERSCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_Bool threadsafe)
96   	
97   	/** destructor of Benders' decomposition to free user data (called when SCIP is exiting)
98   	 *
99   	 *  input:
100  	 *  - scip            : SCIP main data structure
101  	 *  - benders         : the Benders' decomposition itself
102  	 */
103  	#define SCIP_DECL_BENDERSFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
104  	
105  	/** initialization method of Benders' decomposition (called after problem was transformed and the Benders' decomposition
106  	 * is active)
107  	 *
108  	 *  input:
109  	 *  - scip            : SCIP main data structure
110  	 *  - benders         : the Benders' decomposition itself
111  	 */
112  	#define SCIP_DECL_BENDERSINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
113  	
114  	/** deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders'
115  	 * decomposition is active)
116  	 *
117  	 *  input:
118  	 *  - scip            : SCIP main data structure
119  	 *  - benders         : the Benders' decomposition itself
120  	 */
121  	#define SCIP_DECL_BENDERSEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
122  	
123  	/** presolving initialization method of the Benders' decomposition (called when presolving is about to begin)
124  	 *
125  	 *  This function is called immediately after the auxiliary variables are created in the master problem. The callback
126  	 *  provides the user an opportunity to add variable data to the auxiliary variables.
127  	 *
128  	 *  input:
129  	 *  - scip            : SCIP main data structure
130  	 *  - benders         : the Benders' decomposition itself
131  	 */
132  	#define SCIP_DECL_BENDERSINITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
133  	
134  	/** presolving deinitialization method of the Benders' decomposition (called after presolving has been finished)
135  	 *
136  	 *  input:
137  	 *  - scip            : SCIP main data structure
138  	 *  - benders         : the Benders' decomposition itself
139  	 */
140  	#define SCIP_DECL_BENDERSEXITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
141  	
142  	/** solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin)
143  	 *
144  	 *  This method is called when the presolving was finished and the branch and bound process is about to begin.
145  	 *  The Benders' decomposition may use this call to initialize its branch and bound specific data.
146  	 *
147  	 *  input:
148  	 *  - scip            : SCIP main data structure
149  	 *  - benders         : the Benders' decomposition itself
150  	 */
151  	#define SCIP_DECL_BENDERSINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
152  	
153  	/** solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed)
154  	 *
155  	 *  This method is called before the branch and bound process is freed.
156  	 *  The Benders' decomposition should use this call to clean up its branch and bound data.
157  	 *
158  	 *  input:
159  	 *  - scip            : SCIP main data structure
160  	 *  - benders         : the Benders' decomposition itself
161  	 */
162  	#define SCIP_DECL_BENDERSEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders)
163  	
164  	/** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage
165  	 *  (after the master problem was transformed).
166  	 *
167  	 *  @note When the create subproblem callback is invoked, the mapping between the  master problem and subproblem
168  	 *  variables must be available. The create subproblem callback is invoked immediately after BENDERSINIT. So, it is
169  	 *  possible to construct the variable mapping within the BENDERSINIT callback.
170  	 *
171  	 *  This method must register the SCIP instance for the subproblem with the Benders' decomposition core by calling
172  	 *  SCIPaddBendersSubproblem. Typically, the user must create the SCIP instances for the subproblems. These can be
173  	 *  created within a reader or probdata and then registered with the Benders' decomposition core during the call of this
174  	 *  callback. If there are any settings required for solving the subproblems, then they should be set here. However,
175  	 *  some settings will be overridden by the standard solving method included in the Benders' decomposition framework.
176  	 *  If a special solving method is desired, the user can implement the bendersSolvesubXyz callback. In this latter case,
177  	 *  it is possible to provide a NULL pointer to SCIPaddBendersSubproblem. This will ensure that no internal solving
178  	 *  methods available within the Benders' decomposition core are invoked during the solving process.
179  	 *
180  	 *  If the user defines a subproblem solving method, then in BENDERSCREATESUB, the user must explicitly specify the
181  	 *  subproblem type. This is necessary because the dual solutions from convex problems can be used to generate cuts.
182  	 *  The classical Benders' optimality and feasibility cuts require that the subproblems are convex. The subproblem type
183  	 *  is specified by calling SCIPbendersSetSubproblemType. The available subproblem types are defined in
184  	 *  SCIP_BENDERSSUBTYPE.
185  	 *
186  	 *  If the user does NOT implement a subproblem solving method, then the convexity of the problem is determined
187  	 *  internally.
188  	 *
189  	 *  input:
190  	 *  - scip            : SCIP main data structure
191  	 *  - benders         : the Benders' decomposition data structure
192  	 *  - probnumber      : the subproblem problem number
193  	 */
194  	#define SCIP_DECL_BENDERSCREATESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
195  	
196  	/** called before the subproblem solving loop for Benders' decomposition. The pre subproblem solve function gives the
197  	 *  user an oppportunity to perform any global set up for the Benders' decomposition.
198  	 *
199  	 *  input:
200  	 *  - scip            : SCIP main data structure
201  	 *  - benders         : the Benders' decomposition data structure
202  	 *  - sol             : the solution that will be checked in the subproblem. Can be NULL.
203  	 *  - type            : the enforcement type that called the Benders' decomposition solve.
204  	 *  - checkint        : should the integer subproblems be checked.
205  	 *  - infeasible      : flag to return whether the master problem in infeasible with respect to the added cuts
206  	 *  - auxviol         : set to TRUE only if the solution is feasible but the aux vars are violated
207  	 *  - skipsolve       : flag to return whether the current subproblem solving loop should be skipped
208  	 *  - result          : a result to be returned to the Benders' constraint handler if the solve is skipped. If the
209  	 *                      solve is not skipped, then the returned result is ignored.
210  	 *
211  	 *  possible return values for *result (if more than one applies, the first in the list should be used):
212  	 *  - SCIP_DIDNOTRUN  : the subproblem was not solved in this iteration. Other decompositions will be checked.
213  	 *  - SCIP_CONSADDED  : a constraint has been added to the master problem. No other decompositions will be checked.
214  	 *  - SCIP_SEPARATED  : a cut has been added to the master problem. No other decompositions will be checked.
215  	 *  - SCIP_FEASIBLE   : feasibility of the solution is reported to SCIP. Other decompositions will be checked.
216  	 *  - SCIP_INFEASIBLE : infeasibility of the solution is reported to SCIP. No other decompositions will be checked.
217  	 */
218  	#define SCIP_DECL_BENDERSPRESUBSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
219  	   SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint, SCIP_Bool* infeasible, SCIP_Bool* auxviol, SCIP_Bool* skipsolve,\
220  	   SCIP_RESULT* result)
221  	
222  	/** the solving method for a convex Benders' decomposition subproblem. This call back is provided to solve problems
223  	 *  for which the dual soluitons are used to generate Benders' decomposition cuts. In the classical Benders'
224  	 *  decomposition implementation, this would be an LP. However, it can be any convex problem where the dual solutions
225  	 *  are given by a single vector of reals.
226  	 *
227  	 *  In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex
228  	 *  subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving
229  	 *  loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the FIRST solving
230  	 *  loop only.
231  	 *
232  	 *  In the classical Benders' decomposition implementation, if the subproblems are all LPs the only the
233  	 *  BENDERSSOLVESUBCONVEX need to be implemented. If the subproblems are MIPs, then it is useful to only implement a
234  	 *  single SCIP instance for the subproblem and then change the variable types of the appropriate variables to
235  	 *  CONTINUOUS for the CONVEX subproblem solve and to INTEGER for the CIP subproblem solve.
236  	 *
237  	 *  The solving methods are separated so that they can be called in parallel.
238  	 *
239  	 *  NOTE: The solving methods must be thread safe.
240  	 *
241  	 *  This method is called from within the execution method.
242  	 *
243  	 *  input:
244  	 *  - scip            : SCIP main data structure
245  	 *  - benders         : the Benders' decomposition data structure
246  	 *  - sol             : the solution that will be checked in the subproblem. Can be NULL.
247  	 *  - probnumber      : the subproblem problem number
248  	 *  - onlyconvexcheck : flag to indicate that only the convex relaxations will be checked in this solving loop. This is
249  	 *                      a feature of the Large Neighbourhood Benders' Search
250  	 *  - objective       : variable to return the objective function value of the subproblem
251  	 *  - result          : the result from solving the subproblem
252  	 *
253  	 *  possible return values for *result (if more than one applies, the first in the list should be used):
254  	 *  - SCIP_DIDNOTRUN  : the subproblem was not solved in this iteration
255  	 *  - SCIP_FEASIBLE   : the subproblem is solved and is feasible
256  	 *  - SCIP_INFEASIBLE : the subproblem is solved and is infeasible
257  	 *  - SCIP_UNBOUNDED  : the subproblem is solved and is unbounded
258  	 */
259  	#define SCIP_DECL_BENDERSSOLVESUBCONVEX(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
260  	   int probnumber, SCIP_Bool onlyconvexcheck, SCIP_Real* objective, SCIP_RESULT* result)
261  	
262  	/** the solving method for a Benders' decomposition subproblem as a CIP. This call back is provided to solve problems
263  	 *  for which the dual solutions are not well defined. In this case, the cuts are typically generated from the primal
264  	 *  solution to the CIP. In the classical Benders' decomposition implementation, this would be a MIP. However, it can
265  	 *  be any CIP.
266  	 *
267  	 *  In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex
268  	 *  subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving
269  	 *  loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the SECOND solving
270  	 *  loop only.
271  	 *
272  	 *  The solving methods are separated so that they can be called in parallel.
273  	 *
274  	 *  NOTE: The solving methods must be thread safe.
275  	 *
276  	 *  This method is called from within the execution method.
277  	 *
278  	 *  input:
279  	 *  - scip            : SCIP main data structure
280  	 *  - benders         : the Benders' decomposition data structure
281  	 *  - sol             : the solution that will be checked in the subproblem. Can be NULL.
282  	 *  - probnumber      : the subproblem problem number
283  	 *  - objective       : variable to return the objective function value of the subproblem
284  	 *  - result          : the result from solving the subproblem
285  	 *
286  	 *  possible return values for *result (if more than one applies, the first in the list should be used):
287  	 *  - SCIP_DIDNOTRUN  : the subproblem was not solved in this iteration
288  	 *  - SCIP_FEASIBLE   : the subproblem is solved and is feasible
289  	 *  - SCIP_INFEASIBLE : the subproblem is solved and is infeasible
290  	 *  - SCIP_UNBOUNDED  : the subproblem is solved and is unbounded
291  	 */
292  	#define SCIP_DECL_BENDERSSOLVESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol, int probnumber,\
293  	  SCIP_Real* objective, SCIP_RESULT* result)
294  	
295  	/** the post-solve method for Benders' decomposition. The post-solve method is called after the subproblems have
296  	 * been solved but before they have been freed. After the solving of the Benders' decomposition subproblems, the
297  	 * subproblem solving data is freed in the SCIP_DECL_BENDERSFREESUB callback. However, it is not necessary to implement
298  	 * SCIP_DECL_BENDERSFREESUB.
299  	 *
300  	 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default
301  	 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem
302  	 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is
303  	 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
304  	 *
305  	 * This callback provides the opportunity for the user to clean up any data structures that should not exist beyond the current
306  	 * iteration.
307  	 * The user has full access to the master and subproblems in this callback. So it is possible to construct solution for
308  	 * the master problem in the method.
309  	 * Additionally, if there are any subproblems that are infeasibility and this can not be resolved, then the it is
310  	 * possible to merge these subproblems into the master problem. The subproblem indices are given in the mergecands
311  	 * array. The merging can be perform by a user defined function or by calling SCIPmergeBendersSubproblemIntoMaster. If a
312  	 * subproblem was merged into the master problem, then the merged flag must be set to TRUE.
313  	 *
314  	 *  input:
315  	 *  - scip            : SCIP main data structure
316  	 *  - benders         : the Benders' decomposition data structure
317  	 *  - sol             : the solution that was checked by solving the subproblems. Can be NULL.
318  	 *  - type            : the enforcement type that called the Benders' decomposition solve.
319  	 *  - mergecands      : the subproblems that are candidates for merging into the master problem, the first
320  	 *                      npriomergecands are the priority candidates (they should be merged). The remaining
321  	 *                      (nmergecands - npriomergecands) are subproblems that could be merged if desired.
322  	 *  - npriomergecands : the number of priority merge candidates.
323  	 *  - nmergecands     : the total number of subproblems that are candidates for merging into the master problem
324  	 *  - checkint        : should the integer subproblems be checked.
325  	 *  - infeasible      : indicates whether at least one subproblem is infeasible
326  	 *  - merged          : flag to indicate whether a subproblem was merged into the master problem.
327  	 */
328  	#define SCIP_DECL_BENDERSPOSTSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\
329  	   SCIP_BENDERSENFOTYPE type, int* mergecands, int npriomergecands, int nmergecands, SCIP_Bool checkint,\
330  	   SCIP_Bool infeasible, SCIP_Bool* merged)
331  	
332  	/** frees the subproblem so that it can be resolved in the next iteration. As stated above, it is not necessary to
333  	 *  implement this callback. If the callback is implemented, the subproblems should be freed by calling
334  	 *  SCIPfreeTransform(). However, if the subproblems are LPs, then it could be more efficient to put the subproblem
335  	 *  into probing mode prior to solving and then exiting the probing mode during the callback. To put the subproblem into
336  	 *  probing mode, the subproblem must be in SCIP_STAGE_SOLVING. This can be achieved by using eventhandlers.
337  	 *
338  	 *  If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default
339  	 *  freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem
340  	 *  solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is
341  	 *  solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve.
342  	 *
343  	 *  NOTE: The freeing methods must be thread safe.
344  	 *
345  	 *  input:
346  	 *  - scip            : SCIP main data structure
347  	 *  - benders         : the Benders' decomposition data structure
348  	 *  - probnumber      : the subproblem problem number
349  	 */
350  	#define SCIP_DECL_BENDERSFREESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber)
351  	
352  	/** the variable mapping from the subproblem to the master problem. It is neccessary to have a mapping between every
353  	 *  master problem variable and its counterpart in the subproblem. This mapping must go both ways: from master to sub
354  	 *  and sub to master.
355  	 *
356  	 *  This method is called when generating the cuts. The cuts are generated by using the solution to the subproblem to
357  	 *  eliminate a solution to the master problem.
358  	 *
359  	 *  input:
360  	 *  - scip            : SCIP main data structure
361  	 *  - benders         : the Benders' decomposition structure
362  	 *  - var             : the variable for which the corresponding variable in the master or subproblem is required
363  	 *  - mappedvar       : pointer to store the variable that is mapped to var
364  	 *  - probnumber      : the number of the subproblem that the desired variable belongs to, -1 for the master problem
365  	 */
366  	#define SCIP_DECL_BENDERSGETVAR(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_VAR* var,\
367  	   SCIP_VAR** mappedvar, int probnumber)
368  	
369  	#ifdef __cplusplus
370  	}
371  	#endif
372  	
373  	#endif
374