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   cons_benderslp.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for benderslp decomposition
28   	 * @author Stephen J. Maher
29   	 *
30   	 * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
31   	 * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
32   	 * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
33   	 * respect to the subproblem constraints.
34   	 *
35   	 * This constraint handler has an enforcement priority that is greater than the integer constraint handler. This means
36   	 * that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage
37   	 * constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer
38   	 * programs by Benders' decomposition.
39   	 *
40   	 * A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the
41   	 * Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions
42   	 * are enforced only at the root node.
43   	 */
44   	
45   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46   	
47   	#include <assert.h>
48   	
49   	#include "scip/scip.h"
50   	#include "scip/cons_benderslp.h"
51   	#include "scip/cons_benders.h"
52   	
53   	
54   	/* fundamental constraint handler properties */
55   	#define CONSHDLR_NAME          "benderslp"
56   	#define CONSHDLR_DESC          "constraint handler for Benders' Decomposition to separate LP solutions"
57   	#define CONSHDLR_ENFOPRIORITY  10000000 /**< priority of the constraint handler for constraint enforcing */
58   	#define CONSHDLR_CHECKPRIORITY 10000000 /**< priority of the constraint handler for checking feasibility */
59   	#define CONSHDLR_EAGERFREQ          100 /**< frequency for using all instead of only the useful constraints in separation,
60   	                                         *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
61   	#define CONSHDLR_NEEDSCONS        FALSE /**< should the constraint handler be skipped, if no constraints are available? */
62   	
63   	
64   	#define DEFAULT_CONSBENDERSLP_MAXDEPTH 0/**< depth at which Benders' decomposition cuts are generated from the LP
65   	                                         *   solution (-1: always, 0: only at root) */
66   	#define DEFAULT_CONSBENDERSLP_FREQ     0/**< the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...) */
67   	#define DEFAULT_CONSBENDERSLP_STALLLIMIT 100/**< the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied */
68   	#define DEFAULT_CONSBENDERSLP_ITERLIMIT 100 /**< after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts. */
69   	#define DEFAULT_ACTIVE            FALSE /**< is the constraint handler active? */
70   	
71   	/*
72   	 * Data structures
73   	 */
74   	
75   	/** constraint handler data */
76   	struct SCIP_ConshdlrData
77   	{
78   	   /* parameters for controlling the two-phase method for Benders' decomposition */
79   	   int                   maxdepth;           /**< the maximum depth at which Benders' cuts are generated from the LP */
80   	   int                   freq;               /**< the depth frequency of generating LP cuts after the max depth is reached */
81   	   SCIP_Bool             active;             /**< is the constraint handler active? */
82   	
83   	   /* variable used to control the behaviour of the two-phase method for Benders' decomposition */
84   	   SCIP_Longint          ncallsnode;         /**< the number of calls at the current node */
85   	   SCIP_NODE*            currnode;           /**< the current node */
86   	   SCIP_Real             prevbound;          /**< the previous dual bound */
87   	   int                   iterlimit;          /**< the iteration limit for the first phase of the two-phase method at a node lower than the root. */
88   	   int                   stallcount;         /**< the number of nodes processed since the last lower bound increase */
89   	   int                   stalllimit;         /**< the number of nodes processed without bound improvement before enforcing the LP relaxation */
90   	};
91   	
92   	
93   	/*
94   	 * Local methods
95   	 */
96   	
97   	
98   	/*
99   	 * Callback methods of constraint handler
100  	 */
101  	
102  	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
103  	static
104  	SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
105  	{  /*lint --e{715}*/
106  	   assert(scip != NULL);
107  	
108  	   SCIP_CALL( SCIPincludeConshdlrBenderslp(scip) );
109  	
110  	   *valid = TRUE;
111  	
112  	   return SCIP_OKAY;
113  	}
114  	
115  	
116  	/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
117  	static
118  	SCIP_DECL_CONSFREE(consFreeBenderslp)
119  	{  /*lint --e{715}*/
120  	   SCIP_CONSHDLRDATA* conshdlrdata;
121  	
122  	   assert(scip != NULL);
123  	   assert(conshdlr != NULL);
124  	
125  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
126  	   assert(conshdlrdata != NULL);
127  	
128  	   /* freeing the constraint handler data */
129  	   SCIPfreeMemory(scip, &conshdlrdata);
130  	
131  	   return SCIP_OKAY;
132  	}
133  	
134  	
135  	
136  	/** constraint enforcing method of constraint handler for LP solutions */
137  	static
138  	SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
139  	{  /*lint --e{715}*/
140  	   SCIP_CONSHDLRDATA* conshdlrdata;
141  	
142  	   assert(conshdlr != NULL);
143  	
144  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
145  	
146  	   /* updating the stall count. If the bound has improved since the last call, then the stall count is set to zero */
147  	   conshdlrdata->stallcount++;
148  	   if( SCIPisLT(scip, conshdlrdata->prevbound, SCIPgetLowerbound(scip)) )
149  	      conshdlrdata->stallcount = 0;
150  	
151  	   conshdlrdata->prevbound = SCIPgetLowerbound(scip);
152  	   conshdlrdata->ncallsnode++;
153  	
154  	   /* if a new node is being processed, then the iteration counts are reset. */
155  	   if( conshdlrdata->currnode != SCIPgetCurrentNode(scip) )
156  	   {
157  	      conshdlrdata->currnode = SCIPgetCurrentNode(scip);
158  	      conshdlrdata->ncallsnode = 0;
159  	   }
160  	
161  	   /* the result is initially set to FEASIBLE. If the two-phase method is not executed, then the result will remain as
162  	    * FEASIBLE. The actual feasibility of the Benders' decomposition subproblems is checked in cons_benders.
163  	   */
164  	   (*result) = SCIP_FEASIBLE;
165  	
166  	   /* only check the Benders' decomposition subproblems for fractional LP solutions if the two-phase method is activated */
167  	   if( !conshdlrdata->active )
168  	      return SCIP_OKAY;
169  	
170  	   /* checking whether the two-phase method is performed.
171  	    * - If a maxdepth is specified
172  	    *   - current depth is checked
173  	    *   - the frequency is checked, if a frequency is specified
174  	    *   - the stalllimit is checked if a stalllimit is specified.
175  	    */
176  	   if( conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth
177  	         && (conshdlrdata->freq == 0 || SCIPgetDepth(scip) % conshdlrdata->freq != 0)
178  	         && (conshdlrdata->stalllimit == 0 || conshdlrdata->stallcount < conshdlrdata->stalllimit) )
179  	      return SCIP_OKAY;
180  	
181  	   /* if an iteration limit is specified, then this is imposed at nodes after the root node */
182  	   if( SCIPgetDepth(scip) > 0 && conshdlrdata->ncallsnode >= conshdlrdata->iterlimit )
183  	      return SCIP_OKAY;
184  	
185  	   /* the two phase method is only performed at the root node for sub-SCIPs */
186  	   if( SCIPgetSubscipDepth(scip) > 0 && SCIPgetDepth(scip) > 0 )
187  	      return SCIP_OKAY;
188  	
189  	   /* checking the Benders' decomposition subproblems for feasibility. */
190  	   SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, FALSE) );
191  	
192  	   /* if the stalllimit is exceeded and the subproblem were checked, then the stall count is reset to zero */
193  	   if( conshdlrdata->stallcount >= conshdlrdata->stalllimit )
194  	      conshdlrdata->stallcount = 0;
195  	
196  	   return SCIP_OKAY;
197  	}
198  	
199  	
200  	/** constraint enforcing method of constraint handler for relaxation solutions */
201  	static
202  	SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
203  	{  /*lint --e{715}*/
204  	   SCIP_CONSHDLRDATA* conshdlrdata;
205  	
206  	   assert(conshdlr != NULL);
207  	
208  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
209  	
210  	   if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
211  	      (*result) = SCIP_FEASIBLE;
212  	   else
213  	      SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, FALSE) );
214  	
215  	   return SCIP_OKAY;
216  	}
217  	
218  	
219  	/** constraint enforcing method of constraint handler for pseudo solutions */
220  	static
221  	SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
222  	{  /*lint --e{715}*/
223  	   SCIP_CONSHDLRDATA* conshdlrdata;
224  	
225  	   assert(conshdlr != NULL);
226  	
227  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
228  	
229  	   if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
230  	      (*result) = SCIP_FEASIBLE;
231  	   else
232  	      SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, FALSE) );
233  	
234  	   return SCIP_OKAY;
235  	}
236  	
237  	
238  	/** feasibility check method of constraint handler for integral solutions.
239  	 *  The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform
240  	 *  the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in
241  	 *  cons_benders if the solution is infeasible with respect to the second stage constraints
242  	 */
243  	static
244  	SCIP_DECL_CONSCHECK(consCheckBenderslp)
245  	{  /*lint --e{715}*/
246  	   (*result) = SCIP_FEASIBLE;
247  	
248  	   return SCIP_OKAY;
249  	}
250  	
251  	
252  	/** variable rounding lock method of constraint handler */
253  	static
254  	SCIP_DECL_CONSLOCK(consLockBenderslp)
255  	{  /*lint --e{715}*/
256  	   return SCIP_OKAY;
257  	}
258  	
259  	
260  	
261  	/*
262  	 * constraint specific interface methods
263  	 */
264  	
265  	/** creates the handler for executing the Benders' decomposition subproblem solve on fractional LP solution and
266  	 * includes it in SCIP */
267  	SCIP_RETCODE SCIPincludeConshdlrBenderslp(
268  	   SCIP*                 scip                /**< SCIP data structure */
269  	   )
270  	{
271  	   SCIP_CONSHDLRDATA* conshdlrdata = NULL;
272  	   SCIP_CONSHDLR* conshdlr;
273  	
274  	   /* create benderslp constraint handler data */
275  	   SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
276  	   BMSclearMemory(conshdlrdata);
277  	   conshdlrdata->prevbound = -SCIPinfinity(scip);
278  	
279  	   conshdlr = NULL;
280  	
281  	   /* include constraint handler */
282  	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
283  	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
284  	         consEnfolpBenderslp, consEnfopsBenderslp, consCheckBenderslp, consLockBenderslp,
285  	         conshdlrdata) );
286  	   assert(conshdlr != NULL);
287  	
288  	   /* set non-fundamental callbacks via specific setter functions */
289  	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenderslp, NULL) );
290  	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenderslp) );
291  	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenderslp) );
292  	
293  	   /* add Benders' decomposition LP constraint handler parameters */
294  	   SCIP_CALL( SCIPaddIntParam(scip,
295  	         "constraints/" CONSHDLR_NAME "/maxdepth",
296  	         "depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)",
297  	         &conshdlrdata->maxdepth, TRUE, DEFAULT_CONSBENDERSLP_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
298  	
299  	   SCIP_CALL( SCIPaddIntParam(scip,
300  	         "constraints/" CONSHDLR_NAME "/depthfreq",
301  	         "the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...)",
302  	         &conshdlrdata->freq, TRUE, DEFAULT_CONSBENDERSLP_FREQ, 0, SCIP_MAXTREEDEPTH, NULL, NULL) );
303  	
304  	   SCIP_CALL( SCIPaddIntParam(scip,
305  	         "constraints/" CONSHDLR_NAME "/stalllimit",
306  	         "the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied",
307  	         &conshdlrdata->stalllimit, TRUE, DEFAULT_CONSBENDERSLP_STALLLIMIT, 0, INT_MAX, NULL, NULL) );
308  	
309  	   SCIP_CALL( SCIPaddIntParam(scip,
310  	         "constraints/" CONSHDLR_NAME "/iterlimit",
311  	         "after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts.",
312  	         &conshdlrdata->iterlimit, TRUE, DEFAULT_CONSBENDERSLP_ITERLIMIT, 0, INT_MAX, NULL, NULL) );
313  	
314  	   SCIP_CALL( SCIPaddBoolParam(scip,
315  	         "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition LP cut constraint handler active?",
316  	         &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
317  	
318  	   conshdlrdata->stallcount = 0;
319  	   return SCIP_OKAY;
320  	}
321