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