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   sepa_intobj.c
26   	 * @ingroup DEFPLUGINS_SEPA
27   	 * @brief  integer objective value separator
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 */
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/pub_event.h"
34   	#include "scip/pub_lp.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_sepa.h"
37   	#include "scip/pub_var.h"
38   	#include "scip/scip_branch.h"
39   	#include "scip/scip_cut.h"
40   	#include "scip/scip_event.h"
41   	#include "scip/scip_general.h"
42   	#include "scip/scip_lp.h"
43   	#include "scip/scip_message.h"
44   	#include "scip/scip_mem.h"
45   	#include "scip/scip_numerics.h"
46   	#include "scip/scip_prob.h"
47   	#include "scip/scip_sepa.h"
48   	#include "scip/scip_sol.h"
49   	#include "scip/scip_solvingstats.h"
50   	#include "scip/scip_var.h"
51   	#include "scip/sepa_intobj.h"
52   	#include <string.h>
53   	
54   	
55   	#define SEPA_NAME              "intobj"
56   	#define SEPA_DESC              "integer objective value separator"
57   	#define SEPA_PRIORITY              -100
58   	#define SEPA_FREQ                    -1
59   	#define SEPA_MAXBOUNDDIST           0.0
60   	#define SEPA_USESSUBSCIP          FALSE /**< does the separator use a secondary SCIP instance? */
61   	#define SEPA_DELAY                FALSE /**< should separation method be delayed, if other separators found cuts? */
62   	
63   	#define EVENTHDLR_NAME         "intobj"
64   	#define EVENTHDLR_DESC         "objective change event handler for integer objective value separator"
65   	
66   	
67   	/*
68   	 * Data structures
69   	 */
70   	
71   	/** separator data */
72   	struct SCIP_SepaData
73   	{
74   	   SCIP_ROW*             objrow;             /**< objective value inequality */
75   	   SCIP_VAR*             objvar;             /**< objective value variable */
76   	   SCIP_Real             setoff;             /**< setoff of the inequality */
77   	};
78   	
79   	
80   	/*
81   	 * Local methods
82   	 */
83   	
84   	/** creates separator data */
85   	static
86   	SCIP_RETCODE sepadataCreate(
87   	   SCIP*                 scip,               /**< SCIP data structure */
88   	   SCIP_SEPADATA**       sepadata            /**< pointer to store separator data */
89   	   )
90   	{
91   	   assert(sepadata != NULL);
92   	
93   	   SCIP_CALL( SCIPallocBlockMemory(scip, sepadata) );
94   	   (*sepadata)->objrow = NULL;
95   	   (*sepadata)->objvar = NULL;
96   	   (*sepadata)->setoff = 0.0;
97   	
98   	   return SCIP_OKAY;
99   	}
100  	
101  	/** frees separator data */
102  	static
103  	SCIP_RETCODE sepadataFree(
104  	   SCIP*                 scip,               /**< SCIP data structure */
105  	   SCIP_SEPADATA**       sepadata            /**< pointer to separator data */
106  	   )
107  	{
108  	   assert(sepadata != NULL);
109  	   assert(*sepadata != NULL);
110  	   assert((*sepadata)->objrow == NULL);
111  	   assert((*sepadata)->objvar == NULL);
112  	
113  	   SCIPfreeBlockMemory(scip, sepadata);
114  	
115  	   return SCIP_OKAY;
116  	}
117  	
118  	/** creates the objective value inequality and the objective value variable, if not yet existing */
119  	static
120  	SCIP_RETCODE createObjRow(
121  	   SCIP*                 scip,               /**< SCIP data structure */
122  	   SCIP_SEPA*            sepa,               /**< separator */
123  	   SCIP_SEPADATA*        sepadata            /**< separator data */
124  	   )
125  	{
126  	   assert(sepadata != NULL);
127  	
128  	   if( sepadata->objrow == NULL )
129  	   {
130  	      SCIP_VAR** vars;
131  	      SCIP_Real obj;
132  	      SCIP_Real intobjval;
133  	      int nvars;
134  	      int v;
135  	      SCIP_Bool attendobjvarbound;
136  	
137  	      attendobjvarbound = FALSE;
138  	      /* create and add objective value variable */
139  	      if( sepadata->objvar == NULL )
140  	      {
141  	         SCIP_CALL( SCIPcreateVar(scip, &sepadata->objvar, "objvar", -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
142  	               SCIP_VARTYPE_IMPLINT, FALSE, TRUE, NULL, NULL, NULL, NULL, NULL) );
143  	         SCIPvarMarkRelaxationOnly(sepadata->objvar);
144  	         SCIP_CALL( SCIPaddVar(scip, sepadata->objvar) );
145  	         SCIP_CALL( SCIPaddVarLocksType(scip, sepadata->objvar, SCIP_LOCKTYPE_MODEL, +1, +1) );
146  	      }
147  	      else
148  	         attendobjvarbound = TRUE;
149  	
150  	      /* get problem variables */
151  	      vars = SCIPgetVars(scip);
152  	      nvars = SCIPgetNVars(scip);
153  	
154  	      /* create objective value inequality */
155  	      if( attendobjvarbound )
156  	         intobjval = SCIPceil(scip, SCIPgetLowerbound(scip)) - SCIPvarGetLbGlobal(sepadata->objvar);
157  	      else
158  	         intobjval = SCIPceil(scip, SCIPgetLowerbound(scip));
159  	      SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &sepadata->objrow, sepa, "objrow", intobjval, SCIPinfinity(scip),
160  	            FALSE, !SCIPallVarsInProb(scip), TRUE) );
161  	      sepadata->setoff = intobjval;
162  	
163  	      SCIP_CALL( SCIPcacheRowExtensions(scip, sepadata->objrow) );
164  	      for( v = 0; v < nvars; ++v )
165  	      {
166  	         obj = SCIPvarGetObj(vars[v]);
167  	         if( !SCIPisZero(scip, obj) )
168  	         {
169  	            SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, vars[v], obj) );
170  	         }
171  	      }
172  	      SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, sepadata->objvar, -1.0) );
173  	      SCIP_CALL( SCIPflushRowExtensions(scip, sepadata->objrow) );
174  	
175  	      SCIPdebugMsg(scip, "created objective value row: ");
176  	      SCIPdebug( SCIP_CALL( SCIPprintRow(scip, sepadata->objrow, NULL) ) );
177  	   }
178  	
179  	   return SCIP_OKAY;
180  	}
181  	
182  	/** searches and adds integral objective cuts that separate the given primal solution */
183  	static
184  	SCIP_RETCODE separateCuts(
185  	   SCIP*                 scip,               /**< SCIP data structure */ 
186  	   SCIP_SEPA*            sepa,               /**< the intobj separator */
187  	   SCIP_SOL*             sol,                /**< the solution that should be separated, or NULL for LP solution */
188  	   SCIP_RESULT*          result              /**< pointer to store the result */
189  	   )
190  	{
191  	   SCIP_SEPADATA* sepadata;
192  	   SCIP_Real objval;
193  	   SCIP_Real intbound;
194  	   SCIP_Bool infeasible;
195  	   SCIP_Bool tightened;
196  	
197  	   assert(result != NULL);
198  	   assert(*result == SCIP_DIDNOTRUN);
199  	
200  	   /* if the objective value may be fractional, we cannot do anything */
201  	   if( !SCIPisObjIntegral(scip) )
202  	      return SCIP_OKAY;
203  	
204  	   *result = SCIP_DIDNOTFIND;
205  	
206  	   /* if the current objective value is integral, there is no integral objective value cut */
207  	   if( sol == NULL )
208  	      objval = SCIPgetLPObjval(scip);
209  	   else
210  	      objval = SCIPgetSolTransObj(scip, sol);
211  	   if( SCIPisFeasIntegral(scip, objval) )
212  	      return SCIP_OKAY;
213  	
214  	   sepadata = SCIPsepaGetData(sepa);
215  	   assert(sepadata != NULL);
216  	
217  	   /* the objective value is fractional: create the objective value inequality, if not yet existing */
218  	   SCIP_CALL( createObjRow(scip, sepa, sepadata) );
219  	
220  	   /* adjust the bounds of the objective value variable */
221  	   intbound = SCIPceil(scip, objval) - sepadata->setoff;
222  	   SCIP_CALL( SCIPtightenVarLb(scip, sepadata->objvar, intbound, FALSE, &infeasible, &tightened) );
223  	   SCIPdebugMsg(scip, "new objective variable lower bound: <%s>[%g,%g]\n",
224  	      SCIPvarGetName(sepadata->objvar), SCIPvarGetLbLocal(sepadata->objvar), SCIPvarGetUbLocal(sepadata->objvar));
225  	
226  	   /* add the objective value inequality as a cut to the LP */
227  	   if( infeasible )
228  	      *result = SCIP_CUTOFF;
229  	   else
230  	   {
231  	      if( !SCIProwIsInLP(sepadata->objrow) )
232  	      {
233  	         SCIP_CALL( SCIPaddRow(scip, sepadata->objrow, FALSE, &infeasible) );
234  	      }
235  	      if ( infeasible )
236  	         *result = SCIP_CUTOFF;
237  	      else if ( tightened )
238  	         *result = SCIP_REDUCEDDOM;
239  	      else
240  	         *result = SCIP_SEPARATED;
241  	   }
242  	
243  	   return SCIP_OKAY;
244  	}
245  	
246  	
247  	/*
248  	 * Callback methods of separator
249  	 */
250  	
251  	/** copy method for separator plugins (called when SCIP copies plugins) */
252  	static
253  	SCIP_DECL_SEPACOPY(sepaCopyIntobj)
254  	{  /*lint --e{715}*/
255  	   assert(scip != NULL);
256  	   assert(sepa != NULL);
257  	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
258  	
259  	   /* call inclusion method of constraint handler */
260  	   SCIP_CALL( SCIPincludeSepaIntobj(scip) );
261  	
262  	   return SCIP_OKAY;
263  	}
264  	
265  	/** destructor of separator to free user data (called when SCIP is exiting) */
266  	static
267  	SCIP_DECL_SEPAFREE(sepaFreeIntobj)
268  	{  /*lint --e{715}*/
269  	   SCIP_SEPADATA* sepadata;
270  	
271  	   /* free separator data */
272  	   sepadata = SCIPsepaGetData(sepa);
273  	   assert(sepadata != NULL);
274  	
275  	   SCIP_CALL( sepadataFree(scip, &sepadata) );
276  	
277  	   SCIPsepaSetData(sepa, NULL);
278  	
279  	   return SCIP_OKAY;
280  	}
281  	
282  	
283  	/** solving process deinitialization method of separator (called before branch and bound process data is freed) */
284  	static
285  	SCIP_DECL_SEPAEXITSOL(sepaExitsolIntobj)
286  	{  /*lint --e{715}*/
287  	   SCIP_SEPADATA* sepadata;
288  	
289  	   sepadata = SCIPsepaGetData(sepa);
290  	   assert(sepadata != NULL);
291  	
292  	   /* release objective row */
293  	   if( sepadata->objrow != NULL )
294  	   {
295  	      SCIP_CALL( SCIPreleaseRow(scip, &sepadata->objrow) );
296  	   }
297  	
298  	   /* release objective variable */
299  	   if( sepadata->objvar != NULL )
300  	   {
301  	      /* remove locks in createObjRow() */
302  	      SCIP_CALL( SCIPaddVarLocksType(scip, sepadata->objvar, SCIP_LOCKTYPE_MODEL, -1, -1) );
303  	      SCIP_CALL( SCIPreleaseVar(scip, &sepadata->objvar) );
304  	   }
305  	
306  	   return SCIP_OKAY;
307  	}
308  	
309  	
310  	/** LP solution separation method of separator */
311  	static
312  	SCIP_DECL_SEPAEXECLP(sepaExeclpIntobj)
313  	{  /*lint --e{715}*/
314  	   *result = SCIP_DIDNOTRUN;
315  	
316  	   /* only call separator, if we are not close to terminating */
317  	   if( SCIPisStopped(scip) )
318  	      return SCIP_OKAY;
319  	
320  	   /* only call separator, if an optimal LP solution is at hand */
321  	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
322  	      return SCIP_OKAY;
323  	
324  	   /* only call separator, if there are fractional variables */
325  	   if( SCIPgetNLPBranchCands(scip) == 0 )
326  	      return SCIP_OKAY;
327  	
328  	   SCIP_CALL( separateCuts(scip, sepa, NULL, result) );
329  	
330  	   return SCIP_OKAY;
331  	}
332  	
333  	
334  	/** arbitrary primal solution separation method of separator */
335  	static
336  	SCIP_DECL_SEPAEXECSOL(sepaExecsolIntobj)
337  	{  /*lint --e{715}*/
338  	   *result = SCIP_DIDNOTRUN;
339  	
340  	   /* only call separator, if we are not close to terminating */
341  	   if( SCIPisStopped(scip) )
342  	      return SCIP_OKAY;
343  	
344  	   /* only call separator, if there can be no feasible integral objective value at least as good */
345  	   if( SCIPfloor(scip, SCIPgetSolTransObj(scip, sol)) >= SCIPceil(scip, SCIPgetLocalLowerbound(scip)) )
346  	      return SCIP_OKAY;
347  	
348  	   SCIP_CALL( separateCuts(scip, sepa, sol, result) );
349  	
350  	   return SCIP_OKAY;
351  	}
352  	
353  	
354  	/*
355  	 * event handler for objective changes
356  	 */
357  	
358  	
359  	/** initialization method of event handler (called after problem was transformed) */
360  	static
361  	SCIP_DECL_EVENTINIT(eventInitIntobj)
362  	{  /*lint --e{715}*/
363  	   SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_VARADDED | SCIP_EVENTTYPE_OBJCHANGED, eventhdlr, NULL, NULL) );
364  	
365  	   return SCIP_OKAY;
366  	}
367  	
368  	/** deinitialization method of event handler (called before transformed problem is freed) */
369  	static
370  	SCIP_DECL_EVENTEXIT(eventExitIntobj)
371  	{  /*lint --e{715}*/
372  	   SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_VARADDED | SCIP_EVENTTYPE_OBJCHANGED, eventhdlr, NULL, -1) );
373  	
374  	   return SCIP_OKAY;
375  	}
376  	
377  	
378  	/** execution method of objective change event handler */
379  	static
380  	SCIP_DECL_EVENTEXEC(eventExecIntobj)
381  	{  /*lint --e{715}*/
382  	   SCIP_EVENTHDLRDATA* eventhdlrdata;
383  	   SCIP_SEPADATA* sepadata;
384  	   SCIP_VAR* var;
385  	   SCIP_Real objdelta;
386  	
387  	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
388  	   sepadata = (SCIP_SEPADATA*)eventhdlrdata;
389  	   assert(sepadata != NULL);
390  	
391  	   /* we don't have anything to do, if the objective value inequality doesn't yet exist */
392  	   if( sepadata->objrow == NULL )
393  	      return SCIP_OKAY;
394  	
395  	   var = SCIPeventGetVar(event);
396  	
397  	   switch( SCIPeventGetType(event) )
398  	   {
399  	   case SCIP_EVENTTYPE_VARADDED:
400  	      SCIPdebugMsg(scip, "variable <%s> with obj=%g was added to the problem\n", SCIPvarGetName(var), SCIPvarGetObj(var));
401  	      objdelta = SCIPvarGetObj(var);
402  	      if( !SCIPisZero(scip, objdelta) )
403  	      {
404  	         SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, var, SCIPvarGetObj(var)) );
405  	      }
406  	      break;
407  	
408  	   case SCIP_EVENTTYPE_OBJCHANGED:
409  	      SCIPdebugMsg(scip, "variable <%s> changed objective value from %g to %g\n", SCIPvarGetName(var), SCIPeventGetOldobj(event), SCIPeventGetNewobj(event));
410  	      objdelta = SCIPeventGetNewobj(event) - SCIPeventGetOldobj(event);
411  	      SCIP_CALL( SCIPaddVarToRow(scip, sepadata->objrow, var, objdelta) );
412  	      break;
413  	
414  	   default:
415  	      SCIPerrorMessage("invalid event type %" SCIP_EVENTTYPE_FORMAT "\n", SCIPeventGetType(event));
416  	      return SCIP_INVALIDDATA;
417  	   }
418  	
419  	   return SCIP_OKAY;
420  	}
421  	
422  	
423  	/*
424  	 * separator specific interface methods
425  	 */
426  	
427  	/** creates the integer objective value separator and includes it in SCIP */
428  	SCIP_RETCODE SCIPincludeSepaIntobj(
429  	   SCIP*                 scip                /**< SCIP data structure */
430  	   )
431  	{
432  	   SCIP_SEPADATA* sepadata;
433  	   SCIP_EVENTHDLRDATA* eventhdlrdata;
434  	   SCIP_SEPA* sepa;
435  	   SCIP_EVENTHDLR* eventhdlr;
436  	
437  	   /* create intobj separator data */
438  	   SCIP_CALL( sepadataCreate(scip, &sepadata) );
439  	
440  	   /* include separator */
441  	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
442  	         SEPA_USESSUBSCIP, SEPA_DELAY,
443  	         sepaExeclpIntobj, sepaExecsolIntobj,
444  	         sepadata) );
445  	
446  	   assert(sepa != NULL);
447  	
448  	   /* set non-NULL pointers to callback methods */
449  	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyIntobj) );
450  	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeIntobj) );
451  	   SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolIntobj) );
452  	
453  	   /* include event handler for objective change events */
454  	   eventhdlr = NULL;
455  	   eventhdlrdata = (SCIP_EVENTHDLRDATA*)sepadata;
456  	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
457  	         eventExecIntobj, eventhdlrdata) );
458  	   assert(eventhdlr != NULL);
459  	
460  	   SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitIntobj) );
461  	   SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitIntobj) );
462  	
463  	   return SCIP_OKAY;
464  	}
465