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   heur_trivialnegation.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  trivialnegation primal heuristic
28   	 * @author Jakob Witzig
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/heur_trivialnegation.h"
34   	#include "scip/pub_heur.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_sol.h"
37   	#include "scip/pub_var.h"
38   	#include "scip/scip_heur.h"
39   	#include "scip/scip_message.h"
40   	#include "scip/scip_numerics.h"
41   	#include "scip/scip_prob.h"
42   	#include "scip/scip_sol.h"
43   	#include "scip/scip_solve.h"
44   	#include "scip/scip_solvingstats.h"
45   	#include <string.h>
46   	
47   	#define HEUR_NAME             "trivialnegation"
48   	#define HEUR_DESC             "negate solution entries if an objective coefficient changes the sign, enters or leaves the objective."
49   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_PROP
50   	#define HEUR_PRIORITY         39990
51   	#define HEUR_FREQ             0
52   	#define HEUR_FREQOFS          0
53   	#define HEUR_MAXDEPTH         0
54   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFORENODE
55   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
56   	
57   	/*
58   	 * Local methods
59   	 */
60   	
61   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
62   	static
63   	SCIP_DECL_HEURCOPY(heurCopyTrivialnegation)
64   	{  /*lint --e{715}*/
65   	   assert(scip != NULL);
66   	   assert(heur != NULL);
67   	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
68   	
69   	   /* call inclusion method of primal heuristic */
70   	   SCIP_CALL( SCIPincludeHeurTrivialnegation(scip) );
71   	
72   	   return SCIP_OKAY;
73   	}
74   	
75   	
76   	/** execution method of primal heuristic */
77   	static
78   	SCIP_DECL_HEUREXEC(heurExecTrivialnegation)
79   	{  /*lint --e{715}*/
80   	   SCIP_SOL* lastbestsol;         /* best solution from last run */
81   	   SCIP_SOL* allchanged;          /* solution with all entries negated */
82   	   SCIP_SOL* feasiblechanged;     /* solution with all feasible entries negated */
83   	   SCIP_SOL* singlenegatedsol;    /* solution with exactly one negated entry */
84   	   SCIP_VAR** vars;
85   	   int nbinvars;
86   	   int i;
87   	
88   	   SCIP_Real solval;
89   	
90   	   vars = SCIPgetVars(scip);
91   	   nbinvars = SCIPgetNBinVars(scip);
92   	
93   	   *result = SCIP_DIDNOTRUN;
94   	
95   	   if( !SCIPisReoptEnabled(scip) )
96   	      return SCIP_OKAY;
97   	
98   	   if( nbinvars < SCIPgetNVars(scip) )
99   	      return SCIP_OKAY;
100  	
101  	   *result = SCIP_DIDNOTFIND;
102  	
103  	   /* get best solution from the run */
104  	   lastbestsol = SCIPgetReoptLastOptSol(scip);
105  	
106  	   if( lastbestsol == NULL )
107  	      return SCIP_OKAY;
108  	
109  	   /* initialize data structure */
110  	   SCIP_CALL( SCIPcreateSol(scip, &allchanged, heur) );
111  	   SCIP_CALL( SCIPcreateSol(scip, &feasiblechanged, heur) );
112  	   SCIP_CALL( SCIPcreateSol(scip, &singlenegatedsol, heur) );
113  	
114  	   /* copy the solutions */
115  	   for( i = 0; i < nbinvars; i++ )
116  	   {
117  	      solval = SCIPgetSolVal(scip, lastbestsol, vars[i]);
118  	      SCIP_CALL( SCIPsetSolVal(scip, allchanged, vars[i], solval) );
119  	      SCIP_CALL( SCIPsetSolVal(scip, feasiblechanged, vars[i], solval) );
120  	      SCIP_CALL( SCIPsetSolVal(scip, singlenegatedsol, vars[i], solval) );
121  	   }
122  	
123  	   assert(SCIPsolGetHeur(allchanged) == heur);
124  	   assert(SCIPsolGetHeur(feasiblechanged) == heur);
125  	   assert(SCIPsolGetHeur(singlenegatedsol) == heur);
126  	
127  	   /* change the entries */
128  	   for( i = 0; i < nbinvars; i++ )
129  	   {
130  	      SCIP_VAR* transvar;
131  	
132  	      assert(SCIPvarIsActive(vars[i]));
133  	
134  	      transvar = vars[i];
135  	
136  	      if( SCIPvarGetType(vars[i]) == SCIP_VARTYPE_BINARY )
137  	      {
138  	         SCIP_Real obj;
139  	         SCIP_Real newcoef;
140  	         SCIP_Real oldcoef;
141  	         SCIP_Bool changed;
142  	
143  	         /* perform negation only on variables that are not globally fixed */
144  	         if( SCIPvarGetLbGlobal(vars[i]) > 0.5 || SCIPvarGetUbGlobal(vars[i]) < 0.5 )
145  	            continue;
146  	
147  	         SCIP_CALL( SCIPgetReoptOldObjCoef(scip, transvar, SCIPgetNReoptRuns(scip), &oldcoef));
148  	         SCIP_CALL( SCIPgetReoptOldObjCoef(scip, transvar, SCIPgetNReoptRuns(scip)-1, &newcoef));
149  	
150  	         /* check if variable entered or left the objective, or if its objective coefficient changed sign */
151  	         changed = FALSE;
152  	         if( !SCIPisFeasEQ(scip, oldcoef, newcoef) )
153  	         {
154  	            changed = SCIPisZero(scip, oldcoef) != SCIPisZero(scip, newcoef);
155  	            changed |= SCIPisPositive(scip, oldcoef) == SCIPisNegative(scip, newcoef); /*lint !e514*/
156  	         }
157  	
158  	         SCIPdebugMsg(scip, "check variable <%s> which has %schanged from %g to %g\n", SCIPvarGetName(transvar), changed ? "" : "not ", oldcoef, newcoef);
159  	
160  	         if( changed )
161  	         {
162  	            SCIP_Bool success;
163  	
164  	            solval = SCIPgetSolVal(scip, lastbestsol, vars[i]);
165  	
166  	            /* change solution value */
167  	            SCIP_CALL( SCIPsetSolVal(scip, allchanged, vars[i], 1 - solval) );
168  	            SCIP_CALL( SCIPsetSolVal(scip, feasiblechanged, vars[i], 1 - solval) );
169  	            SCIP_CALL( SCIPsetSolVal(scip, singlenegatedsol, vars[i], 1 - solval) );
170  	
171  	            /* try solution with all changes */
172  	            success = FALSE;
173  	            obj = SCIPgetSolTransObj(scip, allchanged);
174  	            if( SCIPisFeasLT(scip, obj, SCIPgetCutoffbound(scip)) )
175  	            {
176  	               SCIPdebugMsg(scip, "try solution with all negations\n");
177  	#ifdef SCIP_DEBUG
178  	               SCIP_CALL( SCIPtrySol(scip, allchanged, TRUE, FALSE, TRUE, FALSE, TRUE, &success) );
179  	#else
180  	               SCIP_CALL( SCIPtrySol(scip, allchanged, FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
181  	#endif
182  	
183  	               if( success )
184  	               {
185  	                  SCIPdebugMsg(scip, "found feasible solution solution:\n");
186  	                  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, allchanged, NULL, FALSE) ) );
187  	
188  	                  *result = SCIP_FOUNDSOL;
189  	               }
190  	            }
191  	
192  	            /* try solution with feasible changes */
193  	            success = FALSE;
194  	            obj = SCIPgetSolTransObj(scip, feasiblechanged);
195  	            if( SCIPisFeasLT(scip, obj, SCIPgetCutoffbound(scip)) )
196  	            {
197  	               SCIPdebugMsg(scip, "try solution with feasible negations\n");
198  	#ifdef SCIP_DEBUG
199  	               SCIP_CALL( SCIPtrySol(scip, feasiblechanged, TRUE, FALSE, TRUE, FALSE, TRUE, &success) );
200  	#else
201  	               SCIP_CALL( SCIPtrySol(scip, feasiblechanged, FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
202  	#endif
203  	               if( success )
204  	               {
205  	                  SCIPdebugMsg(scip, "found feasible solution solution:\n");
206  	                  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, feasiblechanged, NULL, FALSE) ) );
207  	
208  	                  *result = SCIP_FOUNDSOL;
209  	               }
210  	            }
211  	
212  	            if( !success )
213  	            {
214  	               /* reset solution with feasible changes */
215  	               SCIP_CALL( SCIPsetSolVal(scip, feasiblechanged, vars[i], solval) );
216  	            }
217  	
218  	            /* try solution with exactly one changed value */
219  	            obj = SCIPgetSolTransObj(scip, singlenegatedsol);
220  	            if( SCIPisFeasLT(scip, obj, SCIPgetCutoffbound(scip)) )
221  	            {
222  	               success = FALSE;
223  	               SCIPdebugMsg(scip, "try solution with a single negation\n");
224  	#ifdef SCIP_DEBUG
225  	               SCIP_CALL( SCIPtrySol(scip, singlenegatedsol, TRUE, FALSE, TRUE, FALSE, TRUE, &success) );
226  	#else
227  	               SCIP_CALL( SCIPtrySol(scip, singlenegatedsol, FALSE, FALSE, TRUE, FALSE, TRUE, &success) );
228  	#endif
229  	               if( success )
230  	               {
231  	                  SCIPdebugMsg(scip, "found feasible solution:\n");
232  	                  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, singlenegatedsol, NULL, FALSE) ) );
233  	
234  	                  *result = SCIP_FOUNDSOL;
235  	               }
236  	            }
237  	
238  	            /* reset solution with exactly one changed value */
239  	            SCIP_CALL( SCIPsetSolVal(scip, singlenegatedsol, vars[i], solval) );
240  	         }
241  	      }
242  	   }
243  	
244  	   /* free solutions */
245  	   SCIP_CALL( SCIPfreeSol(scip, &allchanged) );
246  	   SCIP_CALL( SCIPfreeSol(scip, &feasiblechanged) );
247  	   SCIP_CALL( SCIPfreeSol(scip, &singlenegatedsol) );
248  	
249  	   return SCIP_OKAY;
250  	}
251  	
252  	
253  	/*
254  	 * primal heuristic specific interface methods
255  	 */
256  	
257  	/** creates the trivialnegation primal heuristic and includes it in SCIP */
258  	SCIP_RETCODE SCIPincludeHeurTrivialnegation(
259  	   SCIP*                 scip                /**< SCIP data structure */
260  	   )
261  	{
262  	   SCIP_HEUR* heur;
263  	
264  	   /* include heuristic */
265  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
266  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
267  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivialnegation, NULL) );
268  	
269  	   assert(heur != NULL);
270  	
271  	   /* set non fundamental callbacks via setter functions */
272  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivialnegation) );
273  	
274  	   return SCIP_OKAY;
275  	}
276