Scippy

SCIP

Solving Constraint Integer Programs

heur_trivialnegation.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 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 
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 */
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 
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);
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);
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);
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 */
259  SCIP* scip /**< SCIP data structure */
260  )
261 {
262  SCIP_HEUR* heur;
263 
264  /* include heuristic */
265  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
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 }
#define HEUR_NAME
#define NULL
Definition: def.h:267
#define HEUR_TIMING
trivialnegation primal heuristic
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURCOPY(heurCopyTrivialnegation)
public solving methods
#define HEUR_DISPCHAR
#define FALSE
Definition: def.h:94
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:93
#define SCIPdebug(x)
Definition: pub_message.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
public methods for problem variables
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
static SCIP_DECL_HEUREXEC(heurExecTrivialnegation)
#define HEUR_FREQOFS
#define HEUR_FREQ
#define SCIPdebugMsg
Definition: scip_message.h:78
public methods for numerical tolerances
public methods for querying solving statistics
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3488
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_SOL * SCIPgetReoptLastOptSol(SCIP *scip)
Definition: scip_solve.c:3121
#define HEUR_DESC
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2804
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
public methods for primal CIP solutions
#define SCIP_CALL(x)
Definition: def.h:380
#define HEUR_PRIORITY
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:2954
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPincludeHeurTrivialnegation(SCIP *scip)
public methods for solutions
int SCIPgetNReoptRuns(SCIP *scip)
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
#define SCIP_Real
Definition: def.h:173
public methods for message handling
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetReoptOldObjCoef(SCIP *scip, SCIP_VAR *var, int run, SCIP_Real *objcoef)
Definition: scip_solve.c:3148
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
public methods for primal heuristics
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
#define HEUR_MAXDEPTH
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17749
#define HEUR_USESSUBSCIP
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631