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   benderscut_nogood.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  Generates a no good cut for integer solutions that are infeasible for the subproblems
28   	 * @author Stephen J. Maher
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/benderscut_nogood.h"
34   	#include "scip/cons_linear.h"
35   	#include "scip/pub_benderscut.h"
36   	#include "scip/pub_benders.h"
37   	#include "scip/pub_lp.h"
38   	#include "scip/pub_message.h"
39   	#include "scip/pub_misc.h"
40   	#include "scip/pub_var.h"
41   	#include "scip/scip_benders.h"
42   	#include "scip/scip_cons.h"
43   	#include "scip/scip_cut.h"
44   	#include "scip/scip_general.h"
45   	#include "scip/scip_lp.h"
46   	#include "scip/scip_mem.h"
47   	#include "scip/scip_message.h"
48   	#include "scip/scip_numerics.h"
49   	#include "scip/scip_param.h"
50   	#include "scip/scip_prob.h"
51   	#include "scip/scip_sol.h"
52   	#include <string.h>
53   	
54   	#define BENDERSCUT_NAME             "nogood"
55   	#define BENDERSCUT_DESC             "no good Benders' decomposition integer cut"
56   	#define BENDERSCUT_PRIORITY       500
57   	#define BENDERSCUT_LPCUT        FALSE
58   	
59   	
60   	
61   	#define SCIP_DEFAULT_ADDCUTS             FALSE  /** Should cuts be generated, instead of constraints */
62   	
63   	/*
64   	 * Data structures
65   	 */
66   	
67   	/** Benders' decomposition cuts data */
68   	struct SCIP_BenderscutData
69   	{
70   	   SCIP_BENDERS*         benders;            /**< the Benders' decomposition data structure */
71   	   int                   curriter;           /**< the current Benders' decomposition subproblem solve iteration */
72   	   SCIP_Bool             addcuts;            /**< should cuts be generated instead of constraints */
73   	   SCIP_Bool             cutadded;           /**< has a cut been added in the current iteration. Only one cut per round */
74   	};
75   	
76   	
77   	/*
78   	 * Local methods
79   	 */
80   	
81   	/** compute no good cut */
82   	static
83   	SCIP_RETCODE computeNogoodCut(
84   	   SCIP*                 masterprob,         /**< the SCIP instance of the master problem */
85   	   SCIP_BENDERS*         benders,            /**< the benders' decomposition structure */
86   	   SCIP_SOL*             sol,                /**< primal CIP solution */
87   	   SCIP_CONS*            cons,               /**< the constraint for the generated cut, can be NULL */
88   	   SCIP_ROW*             row,                /**< the row for the generated cut, can be NULL */
89   	   SCIP_Bool             addcut              /**< indicates whether a cut is created instead of a constraint */
90   	   )
91   	{
92   	   SCIP_VAR** vars;
93   	   int nvars;
94   	   SCIP_Real lhs;
95   	   int i;
96   	#ifndef NDEBUG
97   	   SCIP_Real verifycons;
98   	#endif
99   	
100  	   assert(masterprob != NULL);
101  	   assert(benders != NULL);
102  	   assert(cons != NULL || addcut);
103  	   assert(row != NULL || !addcut);
104  	
105  	   nvars = SCIPgetNVars(masterprob);
106  	   vars = SCIPgetVars(masterprob);
107  	
108  	   /* adding the subproblem objective function value to the lhs */
109  	   if( addcut )
110  	      lhs = SCIProwGetLhs(row);
111  	   else
112  	      lhs = SCIPgetLhsLinear(masterprob, cons);
113  	
114  	   /* adding the violation to the lhs */
115  	   lhs += 1.0;
116  	
117  	   /* looping over all master problem variables to update the coefficients in the computed cut. */
118  	   for( i = 0; i < nvars; i++ )
119  	   {
120  	      SCIP_Real coef;
121  	
122  	      if( !SCIPvarIsBinary(vars[i]) )
123  	         continue;
124  	
125  	      /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
126  	      if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) )
127  	      {
128  	         coef = -1.0;
129  	         lhs -= 1.0;
130  	      }
131  	      else
132  	         coef = 1.0;
133  	
134  	      /* adding the variable to the cut. The coefficient is the subproblem objective value */
135  	      if( addcut )
136  	      {
137  	         SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) );
138  	      }
139  	      else
140  	      {
141  	         SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) );
142  	      }
143  	   }
144  	
145  	   /* Update the lhs of the cut */
146  	   if( addcut )
147  	   {
148  	      SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
149  	   }
150  	   else
151  	   {
152  	      SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
153  	   }
154  	
155  	#ifndef NDEBUG
156  	   if( addcut )
157  	      verifycons = SCIPgetRowSolActivity(masterprob, row, sol);
158  	   else
159  	      verifycons = SCIPgetActivityLinear(masterprob, cons, sol);
160  	#endif
161  	
162  	   assert(SCIPisFeasEQ(masterprob, verifycons, lhs - 1));
163  	
164  	   return SCIP_OKAY;
165  	}
166  	
167  	
168  	
169  	/** generates and applies Benders' cuts */
170  	static
171  	SCIP_RETCODE generateAndApplyBendersNogoodCut(
172  	   SCIP*                 masterprob,         /**< the SCIP instance of the master problem */
173  	   SCIP_BENDERS*         benders,            /**< the benders' decomposition */
174  	   SCIP_BENDERSCUT*      benderscut,         /**< the benders' decomposition cut method */
175  	   SCIP_SOL*             sol,                /**< primal CIP solution */
176  	   SCIP_BENDERSENFOTYPE  type,               /**< the enforcement type calling this function */
177  	   SCIP_RESULT*          result              /**< the result from solving the subproblems */
178  	   )
179  	{
180  	   SCIP_BENDERSCUTDATA* benderscutdata;
181  	   SCIP_CONSHDLR* consbenders;
182  	   SCIP_CONS* cons;
183  	   SCIP_ROW* row;
184  	   char cutname[SCIP_MAXSTRLEN];
185  	   SCIP_Bool addcut;
186  	
187  	   assert(masterprob != NULL);
188  	   assert(benders != NULL);
189  	   assert(benderscut != NULL);
190  	   assert(result != NULL);
191  	
192  	   row = NULL;
193  	   cons = NULL;
194  	
195  	   /* retrieving the Benders' cut data */
196  	   benderscutdata = SCIPbenderscutGetData(benderscut);
197  	
198  	   /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
199  	    * added to the master problem.
200  	    */
201  	   if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
202  	      addcut = FALSE;
203  	   else
204  	      addcut = benderscutdata->addcuts;
205  	
206  	   /* retrieving the Benders' decomposition constraint handler */
207  	   consbenders = SCIPfindConshdlr(masterprob, "benders");
208  	
209  	   /* setting the name of the generated cut */
210  	   (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "nogoodcut_%" SCIP_LONGINT_FORMAT, SCIPbenderscutGetNFound(benderscut) );
211  	
212  	   /* creating an empty row or constraint for the Benders' cut */
213  	   if( addcut )
214  	   {
215  	      SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
216  	            FALSE, TRUE) );
217  	   }
218  	   else
219  	   {
220  	      SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
221  	      SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
222  	      SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
223  	   }
224  	
225  	   /* computing the coefficients of the optimality cut */
226  	   SCIP_CALL( computeNogoodCut(masterprob, benders, sol, cons, row, addcut) );
227  	
228  	   /* adding the constraint to the master problem */
229  	   if( addcut )
230  	   {
231  	      SCIP_Bool infeasible;
232  	
233  	      if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
234  	      {
235  	         SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
236  	         assert(!infeasible);
237  	      }
238  	      else
239  	      {
240  	         assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
241  	         SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
242  	      }
243  	
244  	#ifdef SCIP_DEBUG
245  	      SCIP_CALL( SCIPprintRow(masterprob, row, NULL) );
246  	      SCIPinfoMessage(masterprob, NULL, ";\n");
247  	#endif
248  	
249  	      /* release the row */
250  	      SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
251  	
252  	      (*result) = SCIP_SEPARATED;
253  	   }
254  	   else
255  	   {
256  	      SCIP_CALL( SCIPaddCons(masterprob, cons) );
257  	
258  	      SCIPdebugPrintCons(masterprob, cons, NULL);
259  	
260  	      SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
261  	
262  	      (*result) = SCIP_CONSADDED;
263  	   }
264  	
265  	   /* updating the cut added flag */
266  	   benderscutdata->cutadded = TRUE;
267  	
268  	   return SCIP_OKAY;
269  	}
270  	
271  	/*
272  	 * Callback methods of Benders' decomposition cuts
273  	 */
274  	
275  	/** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
276  	static
277  	SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood)
278  	{  /*lint --e{715}*/
279  	   SCIP_BENDERSCUTDATA* benderscutdata;
280  	
281  	   assert( benderscut != NULL );
282  	   assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
283  	
284  	   /* free Benders' cut data */
285  	   benderscutdata = SCIPbenderscutGetData(benderscut);
286  	   assert( benderscutdata != NULL );
287  	
288  	   SCIPfreeBlockMemory(scip, &benderscutdata);
289  	
290  	   SCIPbenderscutSetData(benderscut, NULL);
291  	
292  	   return SCIP_OKAY;
293  	}
294  	
295  	
296  	/** execution method of Benders' decomposition cuts */
297  	static
298  	SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood)
299  	{  /*lint --e{715}*/
300  	   SCIP* subproblem;
301  	   SCIP_BENDERSCUTDATA* benderscutdata;
302  	
303  	   assert(scip != NULL);
304  	   assert(benders != NULL);
305  	   assert(benderscut != NULL);
306  	   assert(result != NULL);
307  	
308  	   subproblem = SCIPbendersSubproblem(benders, probnumber);
309  	
310  	   if( subproblem == NULL )
311  	   {
312  	      SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
313  	         probnumber, BENDERSCUT_NAME);
314  	
315  	      (*result) = SCIP_DIDNOTRUN;
316  	      return SCIP_OKAY;
317  	   }
318  	
319  	   benderscutdata = SCIPbenderscutGetData(benderscut);
320  	   assert(benderscutdata != NULL);
321  	
322  	   /* if the curriter is less than the number of Benders' decomposition calls, then we are in a new round.
323  	    * So the cutadded flag must be set to FALSE
324  	    */
325  	   if( benderscutdata->curriter < SCIPbendersGetNCalls(benders) )
326  	   {
327  	      benderscutdata->curriter = SCIPbendersGetNCalls(benders);
328  	      benderscutdata->cutadded = FALSE;
329  	   }
330  	
331  	   /* if a cut has been added in this Benders' decomposition call, then no more must be added */
332  	   if( benderscutdata->cutadded )
333  	      return SCIP_OKAY;
334  	
335  	   /* it is only possible to generate the no-good cut for pure binary master problems */
336  	   if( SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders))
337  	      && (!SCIPbendersMasterIsNonlinear(benders)
338  	         || SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders) - 1)) )
339  	   {
340  	      SCIPinfoMessage(scip, NULL, "The no-good cuts can only be applied to problems with a pure binary master problem. "
341  	         "The no-good Benders' decomposition cuts will be disabled.\n");
342  	
343  	      SCIPbenderscutSetEnabled(benderscut, FALSE);
344  	
345  	      return SCIP_OKAY;
346  	   }
347  	
348  	   /* We can not rely on complete recourse for the subproblems. As such, the subproblems may be feasible for the LP, but
349  	    * infeasible for the IP. As such, if one subproblem is infeasible, then a no good cut is generated.
350  	    */
351  	   if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE )
352  	   {
353  	      /* generating a cut */
354  	      SCIP_CALL( generateAndApplyBendersNogoodCut(scip, benders, benderscut, sol, type, result) );
355  	   }
356  	
357  	   return SCIP_OKAY;
358  	}
359  	
360  	
361  	/*
362  	 * Benders' decomposition cuts specific interface methods
363  	 */
364  	
365  	/** creates the nogood Benders' decomposition cuts and includes it in SCIP */
366  	SCIP_RETCODE SCIPincludeBenderscutNogood(
367  	   SCIP*                 scip,               /**< SCIP data structure */
368  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
369  	   )
370  	{
371  	   SCIP_BENDERSCUTDATA* benderscutdata;
372  	   SCIP_BENDERSCUT* benderscut;
373  	   char paramname[SCIP_MAXSTRLEN];
374  	
375  	   assert(benders != NULL);
376  	
377  	   /* create nogood Benders' decomposition cuts data */
378  	   SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
379  	   benderscutdata->benders = benders;
380  	   benderscutdata->curriter = -1;
381  	   benderscutdata->cutadded = FALSE;
382  	
383  	   benderscut = NULL;
384  	
385  	   /* include Benders' decomposition cuts */
386  	   SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC,
387  	         BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecNogood, benderscutdata) );
388  	
389  	   assert(benderscut != NULL);
390  	
391  	   /* set non fundamental callbacks via setter functions */
392  	   SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeNogood) );
393  	
394  	   /* add nogood Benders' decomposition cuts parameters */
395  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
396  	      SCIPbendersGetName(benders), BENDERSCUT_NAME);
397  	   SCIP_CALL( SCIPaddBoolParam(scip, paramname,
398  	         "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
399  	         &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
400  	
401  	   return SCIP_OKAY;
402  	}
403