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"
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) */
62static
63SCIP_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 */
77static
78SCIP_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
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
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 */
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 NULL
Definition: def.h:266
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:172
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:373
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeHeurTrivialnegation(SCIP *scip)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_SOL * SCIPgetReoptLastOptSol(SCIP *scip)
Definition: scip_solve.c:3137
SCIP_RETCODE SCIPgetReoptOldObjCoef(SCIP *scip, SCIP_VAR *var, int run, SCIP_Real *objcoef)
Definition: scip_solve.c:3164
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3504
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:180
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:837
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1627
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2804
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:2950
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1073
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1343
int SCIPgetNReoptRuns(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17747
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17583
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18087
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17418
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18077
static SCIP_DECL_HEURCOPY(heurCopyTrivialnegation)
#define HEUR_TIMING
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
static SCIP_DECL_HEUREXEC(heurExecTrivialnegation)
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
trivialnegation primal heuristic
public methods for primal heuristics
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
public methods for primal CIP solutions
public methods for problem variables
public methods for primal heuristic plugins and divesets
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
public solving methods
public methods for querying solving statistics
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62