SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
64{ /*lint --e{715}*/
65 assert(scip != NULL);
66 assert(heur != NULL);
68
69 /* call inclusion method of primal heuristic */
71
72 return SCIP_OKAY;
73}
74
75
76/** execution method of primal heuristic */
77static
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
92
94
96 return SCIP_OKAY;
97
99 return SCIP_OKAY;
100
102
103 /* get best solution from the run */
105
106 if( lastbestsol == NULL )
107 return SCIP_OKAY;
108
109 /* initialize data structure */
113
114 /* copy the solutions */
115 for( i = 0; i < nbinvars; i++ )
116 {
117 solval = SCIPgetSolVal(scip, lastbestsol, vars[i]);
121 }
122
126
127 /* change the entries */
128 for( i = 0; i < nbinvars; i++ )
129 {
130 SCIP_VAR* transvar;
131
133
134 transvar = vars[i];
135
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;
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) );
170
171 /* try solution with all changes */
172 success = FALSE;
175 {
176 SCIPdebugMsg(scip, "try solution with all negations\n");
177#ifdef SCIP_DEBUG
179#else
181#endif
182
183 if( success )
184 {
185 SCIPdebugMsg(scip, "found feasible solution solution:\n");
187
189 }
190 }
191
192 /* try solution with feasible changes */
193 success = FALSE;
196 {
197 SCIPdebugMsg(scip, "try solution with feasible negations\n");
198#ifdef SCIP_DEBUG
200#else
202#endif
203 if( success )
204 {
205 SCIPdebugMsg(scip, "found feasible solution solution:\n");
207
209 }
210 }
211
212 if( !success )
213 {
214 /* reset solution with feasible changes */
216 }
217
218 /* try solution with exactly one changed value */
221 {
222 success = FALSE;
223 SCIPdebugMsg(scip, "try solution with a single negation\n");
224#ifdef SCIP_DEBUG
226#else
228#endif
229 if( success )
230 {
231 SCIPdebugMsg(scip, "found feasible solution:\n");
233
235 }
236 }
237
238 /* reset solution with exactly one changed value */
240 }
241 }
242 }
243
244 /* free solutions */
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 */
268
269 assert(heur != NULL);
270
271 /* set non fundamental callbacks via setter functions */
273
274 return SCIP_OKAY;
275}
#define NULL
Definition def.h:267
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_CALL(x)
Definition def.h:374
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
SCIP_RETCODE SCIPincludeHeurTrivialnegation(SCIP *scip)
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
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
SCIP_SOL * SCIPgetReoptLastOptSol(SCIP *scip)
SCIP_RETCODE SCIPgetReoptOldObjCoef(SCIP *scip, SCIP_VAR *var, int run, SCIP_Real *objcoef)
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1631
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:2954
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1347
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:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIP_Real obj
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_VAR ** vars
int nbinvars
#define HEUR_TIMING
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
#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
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62