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