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