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   pub_benders.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  public methods 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_PUB_BENDERS_H__
34   	#define __SCIP_PUB_BENDERS_H__
35   	
36   	#include "scip/def.h"
37   	#include "scip/type_benders.h"
38   	#include "scip/type_benderscut.h"
39   	#include "scip/type_misc.h"
40   	#include "scip/type_retcode.h"
41   	#include "scip/type_scip.h"
42   	#include "scip/type_var.h"
43   	#include "scip/type_stat.h"
44   	#include "scip/type_nlpi.h"
45   	
46   	#ifdef __cplusplus
47   	extern "C" {
48   	#endif
49   	
50   	/**@addtogroup PublicBendersMethods
51   	 *
52   	 * @{
53   	 */
54   	
55   	/** compares two benderss w. r. to their priority */
56   	SCIP_EXPORT
57   	SCIP_DECL_SORTPTRCOMP(SCIPbendersComp);
58   	
59   	/** comparison method for sorting benderss w.r.t. to their name */
60   	SCIP_EXPORT
61   	SCIP_DECL_SORTPTRCOMP(SCIPbendersCompName);
62   	
63   	/** gets user data of Benders' decomposition */
64   	SCIP_EXPORT
65   	SCIP_BENDERSDATA* SCIPbendersGetData(
66   	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
67   	   );
68   	
69   	/** sets user data of Benders' decomposition; user has to free old data in advance! */
70   	SCIP_EXPORT
71   	void SCIPbendersSetData(
72   	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
73   	   SCIP_BENDERSDATA*     bendersdata         /**< new Benders' decomposition user data */
74   	   );
75   	
76   	/** gets name of Benders' decomposition */
77   	SCIP_EXPORT
78   	const char* SCIPbendersGetName(
79   	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
80   	   );
81   	
82   	/** gets description of Benders' decomposition */
83   	SCIP_EXPORT
84   	const char* SCIPbendersGetDesc(
85   	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
86   	   );
87   	
88   	/** gets priority of Benders' decomposition */
89   	SCIP_EXPORT
90   	int SCIPbendersGetPriority(
91   	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
92   	   );
93   	
94   	/** gets the number of subproblems for the Benders' decomposition */
95   	SCIP_EXPORT
96   	int SCIPbendersGetNSubproblems(
97   	   SCIP_BENDERS*         benders             /**< the Benders' decomposition data structure */
98   	   );
99   	
100  	/** returns the SCIP instance for a given subproblem */
101  	SCIP_EXPORT
102  	SCIP* SCIPbendersSubproblem(
103  	   SCIP_BENDERS*         benders,            /**< the Benders' decomposition data structure */
104  	   int                   probnumber          /**< the subproblem number */
105  	   );
106  	
107  	/** gets the number of times, the Bender' decomposition was called and tried to find a violated second stage constraint */
108  	SCIP_EXPORT
109  	int SCIPbendersGetNCalls(
110  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
111  	   );
112  	
113  	/** gets the number of optimality cuts found by the collection of Benders' decomposition subproblems */
114  	SCIP_EXPORT
115  	int SCIPbendersGetNCutsFound(
116  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
117  	   );
118  	
119  	/** gets the number of cuts found from the strengthening round */
120  	SCIP_EXPORT
121  	int SCIPbendersGetNStrengthenCutsFound(
122  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
123  	   );
124  	
125  	/** gets the number of calls to the strengthening round */
126  	SCIP_EXPORT
127  	int SCIPbendersGetNStrengthenCalls(
128  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
129  	   );
130  	
131  	/** gets the number of calls to the strengthening round that fail */
132  	SCIP_EXPORT
133  	int SCIPbendersGetNStrengthenFails(
134  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
135  	   );
136  	
137  	/** gets time in seconds used in this Benders' decomposition for setting up for next stages */
138  	SCIP_EXPORT
139  	SCIP_Real SCIPbendersGetSetupTime(
140  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
141  	   );
142  	
143  	/** gets execution time in seconds used in this Benders' decomposition */
144  	SCIP_EXPORT
145  	SCIP_Real SCIPbendersGetTime(
146  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
147  	   );
148  	
149  	/** Is Benders' decomposition initialized? */
150  	SCIP_EXPORT
151  	SCIP_Bool SCIPbendersIsInitialized(
152  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
153  	   );
154  	
155  	/** returns whether the given Benders' decomposition is in use in the current problem */
156  	SCIP_EXPORT
157  	SCIP_Bool SCIPbendersIsActive(
158  	   SCIP_BENDERS*         benders             /**< the Benders' decomposition structure */
159  	   );
160  	
161  	/** Returns whether only the convex relaxations will be checked in this solve loop
162  	 *  when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
163  	 *  i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
164  	 *  that all subproblems are convex relaxations.
165  	 */
166  	SCIP_EXPORT
167  	SCIP_Bool SCIPbendersOnlyCheckConvexRelax(
168  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
169  	   SCIP_Bool             subscipsoff         /**< flag indicating whether plugins using sub-SCIPs are deactivated */
170  	   );
171  	
172  	/** returns NLP solver parameters used for solving NLP subproblems */
173  	SCIP_EXPORT
174  	SCIP_NLPPARAM SCIPbendersGetNLPParam(
175  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
176  	);
177  	
178  	/** Are Benders' cuts generated from the LP solutions? */
179  	SCIP_EXPORT
180  	SCIP_Bool SCIPbendersCutLP(
181  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
182  	   );
183  	
184  	/** Are Benders' cuts generated from the pseudo solutions? */
185  	SCIP_EXPORT
186  	SCIP_Bool SCIPbendersCutPseudo(
187  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
188  	   );
189  	
190  	/** Are Benders' cuts generated from the relaxation solutions? */
191  	SCIP_EXPORT
192  	SCIP_Bool SCIPbendersCutRelaxation(
193  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
194  	   );
195  	
196  	/** Should this Benders' use the auxiliary variables from the highest priority Benders'? */
197  	SCIP_EXPORT
198  	SCIP_Bool SCIPbendersShareAuxVars(
199  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
200  	   );
201  	
202  	/** sets the subproblem setup flag */
203  	SCIP_EXPORT
204  	void SCIPbendersSetSubproblemIsSetup(
205  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
206  	   int                   probnumber,         /**< the subproblem number */
207  	   SCIP_Bool             issetup             /**< flag to indicate whether the subproblem has been setup */
208  	   );
209  	
210  	/** returns the subproblem setup flag */
211  	SCIP_EXPORT
212  	SCIP_Bool SCIPbendersSubproblemIsSetup(
213  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
214  	   int                   probnumber          /**< the subproblem number */
215  	   );
216  	
217  	/** returns the auxiliary variable for the given subproblem */
218  	SCIP_EXPORT
219  	SCIP_VAR* SCIPbendersGetAuxiliaryVar(
220  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
221  	   int                   probnumber          /**< the subproblem number */
222  	   );
223  	
224  	/** returns all auxiliary variables */
225  	SCIP_EXPORT
226  	SCIP_VAR** SCIPbendersGetAuxiliaryVars(
227  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
228  	   );
229  	
230  	/** stores the objective function value of the subproblem for use in cut generation */
231  	SCIP_EXPORT
232  	void SCIPbendersSetSubproblemObjval(
233  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
234  	   int                   probnumber,         /**< the subproblem number */
235  	   SCIP_Real             objval              /**< the objective function value for the subproblem */
236  	   );
237  	
238  	/** returns the objective function value of the subproblem for use in cut generation */
239  	SCIP_EXPORT
240  	SCIP_Real SCIPbendersGetSubproblemObjval(
241  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
242  	   int                   probnumber          /**< the subproblem number */
243  	   );
244  	
245  	/** returns the number of cuts that have been added for storage */
246  	SCIP_EXPORT
247  	int SCIPbendersGetNStoredCuts(
248  	   SCIP_BENDERS*         benders             /**< Benders' decomposition cut */
249  	   );
250  	
251  	/** returns the data for the cuts that have been added by the Benders' cut plugin */
252  	SCIP_EXPORT
253  	SCIP_RETCODE SCIPbendersGetStoredCutData(
254  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition cut */
255  	   int                   cutidx,             /**< the index for the cut data that is requested */
256  	   SCIP_VAR***           vars,               /**< the variables that have non-zero coefficients in the cut */
257  	   SCIP_Real**           vals,               /**< the coefficients of the variables in the cut */
258  	   SCIP_Real*            lhs,                /**< the left hand side of the cut */
259  	   SCIP_Real*            rhs,                /**< the right hand side of the cut */
260  	   int*                  nvars               /**< the number of variables with non-zero coefficients in the cut */
261  	   );
262  	
263  	/** returns the original problem data for the cuts that have been added by the Benders' cut plugin. The stored
264  	 *  variables and values will populate the input vars and vals arrays. Thus, memory must be allocated for the vars and
265  	 *  vals arrays
266  	 */
267  	SCIP_EXPORT
268  	SCIP_RETCODE SCIPbendersGetStoredCutOrigData(
269  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition cut */
270  	   int                   cutidx,             /**< the index for the cut data that is requested */
271  	   SCIP_VAR***           vars,               /**< the variables that have non-zero coefficients in the cut */
272  	   SCIP_Real**           vals,               /**< the coefficients of the variables in the cut */
273  	   SCIP_Real*            lhs,                /**< the left hand side of the cut */
274  	   SCIP_Real*            rhs,                /**< the right hand side of the cut */
275  	   int*                  nvars,              /**< the number of variables with non-zero coefficients in the cut */
276  	   int                   varssize            /**< the available slots in the array */
277  	   );
278  	
279  	/*
280  	 * Public functions associated with Benders' cuts
281  	 */
282  	
283  	/** returns the Benders' cut of the given name, or NULL if not existing */
284  	SCIP_EXPORT
285  	SCIP_BENDERSCUT* SCIPfindBenderscut(
286  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
287  	   const char*           name                /**< name of Benderscut' decomposition */
288  	   );
289  	
290  	
291  	/** returns the array of currently available Benders' cuts; active Benders' decomposition are in the first slots of
292  	 * the array
293  	 */
294  	SCIP_EXPORT
295  	SCIP_BENDERSCUT** SCIPbendersGetBenderscuts(
296  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
297  	   );
298  	
299  	
300  	/** returns the number of currently available Benders' cuts */
301  	SCIP_EXPORT
302  	int SCIPbendersGetNBenderscuts(
303  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
304  	   );
305  	
306  	/** sets the priority of a Benders' decomposition */
307  	SCIP_EXPORT
308  	SCIP_RETCODE SCIPbendersSetBenderscutPriority(
309  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
310  	   SCIP_BENDERSCUT*      benderscut,         /**< Benders' cut */
311  	   int                   priority            /**< new priority of the Benders' decomposition */
312  	   );
313  	
314  	/** returns whether the solution has non-zero slack variables */
315  	SCIP_EXPORT
316  	SCIP_RETCODE SCIPbendersSolSlackVarsActive(
317  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
318  	   SCIP_Bool*            activeslack         /**< flag to indicate whether a slack variable is active */
319  	   );
320  	
321  	/** sets the subproblem type
322  	 *
323  	 * The subproblem types are:
324  	 *    - Convex constraints with continuous variables
325  	 *    - Convex constraints with discrete variables
326  	 *    - Non-convex constraints with continuous variables
327  	 *    - Non-convex constraints with discrete variables
328  	 */
329  	SCIP_EXPORT
330  	void SCIPbendersSetSubproblemType(
331  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
332  	   int                   probnumber,         /**< the subproblem number */
333  	   SCIP_BENDERSSUBTYPE   subprobtype         /**< the subproblem type */
334  	   );
335  	
336  	/** returns the type of the subproblem
337  	 *
338  	 *  This type is used to determine whether the duals of the problem can be used to generate cuts
339  	 */
340  	SCIP_EXPORT
341  	SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(
342  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
343  	   int                   probnumber          /**< the subproblem number */
344  	   );
345  	
346  	/** sets the flag indicating whether a subproblem is convex
347  	 *
348  	 *  It is possible that this can change during the solving process. One example is when the three-phase method is
349  	 *  employed, where the first phase solves the convex relaxation of both the master and subproblems, the second phase
350  	 *  reintroduces the integrality constraints to the master problem and the third phase then reintroduces integrality
351  	 *  constraints to the subproblems.
352  	 */
353  	SCIP_EXPORT
354  	void SCIPbendersSetSubproblemIsConvex(
355  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
356  	   int                   probnumber,         /**< the subproblem number */
357  	   SCIP_Bool             isconvex            /**< flag to indicate whether the subproblem is convex */
358  	   );
359  	
360  	/** returns whether the subproblem is convex
361  	 *
362  	 *  This means that the dual solution can be used to generate cuts.
363  	 */
364  	SCIP_EXPORT
365  	SCIP_Bool SCIPbendersSubproblemIsConvex(
366  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
367  	   int                   probnumber          /**< the subproblem number */
368  	   );
369  	
370  	/** returns the number of subproblems that are convex */
371  	SCIP_EXPORT
372  	int SCIPbendersGetNConvexSubproblems(
373  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
374  	   );
375  	
376  	/** sets the flag indicating whether a subproblem contains non-linear constraints */
377  	SCIP_EXPORT
378  	void SCIPbendersSetSubproblemIsNonlinear(
379  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
380  	   int                   probnumber,         /**< the subproblem number */
381  	   SCIP_Bool             isnonlinear         /**< flag to indicate whether the subproblem contains non-linear constraints */
382  	   );
383  	
384  	/** returns whether the subproblem contains non-linear constraints. */
385  	SCIP_EXPORT
386  	SCIP_Bool SCIPbendersSubproblemIsNonlinear(
387  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
388  	   int                   probnumber          /**< the subproblem number */
389  	   );
390  	
391  	/** returns the number of subproblems that contain non-linear constraints  */
392  	SCIP_EXPORT
393  	int SCIPbendersGetNNonlinearSubproblems(
394  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
395  	   );
396  	
397  	/** sets the flag indicating whether the master problem contains non-linear constraints */
398  	SCIP_EXPORT
399  	void SCIPbendersSetMasterIsNonlinear(
400  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
401  	   SCIP_Bool             isnonlinear         /**< flag to indicate whether the subproblem contains non-linear constraints */
402  	   );
403  	
404  	/** returns whether the master problem contains non-linear constraints. */
405  	SCIP_EXPORT
406  	SCIP_Bool SCIPbendersMasterIsNonlinear(
407  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
408  	   );
409  	
410  	/** returns the flag indicating that Benders' decomposition is in a cut strengthening round */
411  	SCIP_EXPORT
412  	SCIP_Bool SCIPbendersInStrengthenRound(
413  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
414  	   );
415  	
416  	/** solves the LP of the Benders' decomposition subproblem
417  	 *
418  	 *  This requires that the subproblem is in probing mode.
419  	 */
420  	SCIP_EXPORT
421  	SCIP_RETCODE SCIPbendersSolveSubproblemLP(
422  	   SCIP*                 scip,               /**< the SCIP data structure */
423  	   SCIP_BENDERS*         benders,            /**< the Benders' decomposition data structure */
424  	   int                   probnumber,         /**< the subproblem number */
425  	   SCIP_STATUS*          solvestatus,        /**< status of subproblem solve */
426  	   SCIP_Real*            objective           /**< optimal value of subproblem, if solved to optimality */
427  	   );
428  	
429  	/** solves the Benders' decomposition subproblem */
430  	SCIP_EXPORT
431  	SCIP_RETCODE SCIPbendersSolveSubproblemCIP(
432  	   SCIP*                 scip,               /**< the SCIP data structure */
433  	   SCIP_BENDERS*         benders,            /**< the Benders' decomposition data structure */
434  	   int                   probnumber,         /**< the subproblem number */
435  	   SCIP_STATUS*          solvestatus,        /**< status of subproblem solve */
436  	   SCIP_Bool             solvecip            /**< directly solve the CIP subproblem */
437  	   );
438  	
439  	/** returns the number of cuts that have been transferred from sub SCIPs to the master SCIP */
440  	SCIP_EXPORT
441  	int SCIPbendersGetNTransferredCuts(
442  	   SCIP_BENDERS*         benders             /**< the Benders' decomposition data structure */
443  	   );
444  	
445  	/** updates the lower bound for the subproblem. If the lower bound is not greater than the previously stored lowerbound,
446  	 * then no update occurs.
447  	 */
448  	SCIP_EXPORT
449  	void SCIPbendersUpdateSubproblemLowerbound(
450  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
451  	   int                   probnumber,         /**< the subproblem number */
452  	   SCIP_Real             lowerbound          /**< the lower bound */
453  	   );
454  	
455  	/** returns the stored lower bound for the given subproblem */
456  	SCIP_EXPORT
457  	SCIP_Real SCIPbendersGetSubproblemLowerbound(
458  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
459  	   int                   probnumber          /**< the subproblem number */
460  	   );
461  	
462  	/** sets the independent subproblem flag */
463  	SCIP_EXPORT
464  	void SCIPbendersSetSubproblemIsIndependent(
465  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
466  	   int                   probnumber,         /**< the subproblem number */
467  	   SCIP_Bool             isindep             /**< flag to indicate whether the subproblem is independent */
468  	   );
469  	
470  	/** returns whether the subproblem is independent */
471  	SCIP_EXPORT
472  	SCIP_Bool SCIPbendersSubproblemIsIndependent(
473  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
474  	   int                   probnumber          /**< the subproblem number */
475  	   );
476  	
477  	/** returns whether the subproblem is enabled, i.e. the subproblem is still solved in the solving loop. */
478  	SCIP_EXPORT
479  	SCIP_Bool SCIPbendersSubproblemIsEnabled(
480  	   SCIP_BENDERS*         benders,            /**< Benders' decomposition */
481  	   int                   probnumber          /**< the subproblem number */
482  	   );
483  	
484  	/** @} */
485  	
486  	#ifdef __cplusplus
487  	}
488  	#endif
489  	
490  	#endif
491