Scippy

SCIP

Solving Constraint Integer Programs

heur_oneopt.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_oneopt.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief improvement heuristic that alters single variable values
28 * @author Timo Berthold
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/heur_oneopt.h"
35#include "scip/pub_heur.h"
36#include "scip/pub_lp.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_misc_sort.h"
40#include "scip/pub_sol.h"
41#include "scip/pub_var.h"
42#include "scip/scip_copy.h"
43#include "scip/scip_general.h"
44#include "scip/scip_heur.h"
45#include "scip/scip_lp.h"
46#include "scip/scip_mem.h"
47#include "scip/scip_message.h"
48#include "scip/scip_numerics.h"
49#include "scip/scip_param.h"
50#include "scip/scip_prob.h"
51#include "scip/scip_sol.h"
52#include "scip/scip_solve.h"
54#include "scip/scip_tree.h"
55#include <string.h>
56
57/* @note If the heuristic runs in the root node, the timing is changed to (SCIP_HEURTIMING_DURINGLPLOOP |
58 * SCIP_HEURTIMING_BEFORENODE), see SCIP_DECL_HEURINITSOL callback.
59 */
60
61#define HEUR_NAME "oneopt"
62#define HEUR_DESC "1-opt heuristic which tries to improve setting of single integer variables"
63#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE
64#define HEUR_PRIORITY -20000
65#define HEUR_FREQ 1
66#define HEUR_FREQOFS 0
67#define HEUR_MAXDEPTH -1
68#define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_AFTERNODE
69#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
70
71#define DEFAULT_WEIGHTEDOBJ TRUE /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */
72#define DEFAULT_DURINGROOT TRUE /**< should the heuristic be called before and during the root node? */
73#define DEFAULT_BEFOREPRESOL FALSE /**< should the heuristic be called before presolving */
74#define DEFAULT_FORCELPCONSTRUCTION FALSE /**< should the construction of the LP be forced even if LP solving is deactivated? */
75#define DEFAULT_USELOOP TRUE /**< should the heuristic continue to run as long as improvements are found? */
76/*
77 * Data structures
78 */
79
80/** primal heuristic data */
81struct SCIP_HeurData
82{
83 int lastsolindex; /**< index of the last solution for which oneopt was performed */
84 SCIP_Bool weightedobj; /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */
85 SCIP_Bool duringroot; /**< should the heuristic be called before and during the root node? */
86 SCIP_Bool forcelpconstruction;/**< should the construction of the LP be forced even if LP solving is deactivated? */
87 SCIP_Bool beforepresol; /**< should the heuristic be called before presolving */
88 SCIP_Bool useloop; /**< should the heuristic continue to run as long as improvements are found? */
89};
90
91
92/*
93 * Local methods
94 */
95
96/** compute value by which the solution of variable @p var can be shifted */
97static
99 SCIP* scip, /**< SCIP data structure */
100 SCIP_VAR* var, /**< variable that should be shifted */
101 SCIP_Real solval, /**< current solution value */
102 SCIP_Real* activities /**< LP row activities */
103 )
104{
105 SCIP_Real lb;
106 SCIP_Real ub;
107 SCIP_Real obj;
108 SCIP_Real newsolval;
109
110 SCIP_COL* col;
111 SCIP_ROW** colrows;
112 SCIP_Real* colvals;
113 SCIP_Bool shiftdown;
114
115 int ncolrows;
116
117 /* get variable's solution value, global bounds and objective coefficient */
118 lb = SCIPvarGetLbGlobal(var);
119 ub = SCIPvarGetUbGlobal(var);
120 obj = SCIPvarGetObj(var);
121 shiftdown = TRUE;
122
123 /* determine shifting direction and maximal possible shifting w.r.t. corresponding bound */
124 if( obj > 0.0 )
125 newsolval = SCIPfeasCeil(scip, lb);
126 else if( obj < 0.0 )
127 {
128 newsolval = SCIPfeasFloor(scip, ub);
129 shiftdown = FALSE;
130 }
131 else
132 newsolval = solval;
133
134 /* newsolval might be bounding solval -> avoid numerical shifting */
135 if( ( shiftdown && SCIPisFeasGE(scip, newsolval, solval) )
136 || ( !shiftdown && SCIPisFeasLE(scip, newsolval, solval) ) )
137 return 0.0;
138
139 SCIPdebugMsg(scip, "Try to shift %s variable <%s> with\n", shiftdown ? "down" : "up", SCIPvarGetName(var) );
140 SCIPdebugMsg(scip, " lb:<%g> <= val:<%g> <= ub:<%g> and obj:<%g> by at most: <%g>\n", lb, solval, ub, obj, newsolval - solval );
141
142 /* get data of LP column */
143 col = SCIPvarGetCol(var);
144 colrows = SCIPcolGetRows(col);
145 colvals = SCIPcolGetVals(col);
146 ncolrows = SCIPcolGetNLPNonz(col);
147
148 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
149
150 /* find maximal shift value, st. all rows stay valid */
151 for( int i = 0; i < ncolrows; ++i )
152 {
153 SCIP_ROW* row;
154 int rowpos;
155
156 row = colrows[i];
157 rowpos = SCIProwGetLPPos(row);
158 assert( -1 <= rowpos && rowpos < SCIPgetNLPRows(scip) );
159
160 /* only global rows need to be valid */
161 if( rowpos >= 0 && !SCIProwIsLocal(row) )
162 {
163 SCIP_Real side;
164 SCIP_Bool left;
165
166 left = shiftdown == ( colvals[i] > 0 );
167 side = left ? SCIProwGetLhs(row) : SCIProwGetRhs(row);
168
169 /* only finite bounds need to be considered */
170 if( !SCIPisInfinity(scip, left ? -side : side) )
171 {
172 SCIP_Real newsolvalrow;
173
174 assert( SCIProwIsInLP(row) );
175 newsolvalrow = solval + (side - activities[rowpos]) / colvals[i];
176
177 /* update shifting value */
178 if( ( shiftdown && newsolvalrow > newsolval ) || ( !shiftdown && newsolvalrow < newsolval ) )
179 {
180 SCIP_Real activity;
181
182 activity = activities[rowpos] + colvals[i] * ((shiftdown ? floor(newsolvalrow) : ceil(newsolvalrow)) - solval);
183
184 /* ensure that shifting preserves feasibility */
185 if( shiftdown == ( ( left && SCIPisFeasGE(scip, activity, side) )
186 || ( !left && SCIPisFeasLE(scip, activity, side) ) ) )
187 newsolval = floor(newsolvalrow);
188 else
189 newsolval = ceil(newsolvalrow);
190
191 SCIPdebugMsg(scip, " -> The shift value has to be set to <%g>, because of row <%s>.\n",
192 newsolval - solval, SCIProwGetName(row));
193 SCIPdebugMsg(scip, " lhs:<%g> <= act:<%g> <= rhs:<%g>, colval:<%g>\n",
194 SCIProwGetLhs(row), activities[rowpos], SCIProwGetRhs(row), colvals[i]);
195
196 /* newsolval might have reached solval -> avoid numerical shifting */
197 if( ( shiftdown && SCIPisFeasGE(scip, newsolval, solval) )
198 || ( !shiftdown && SCIPisFeasLE(scip, newsolval, solval) ) )
199 return 0.0;
200 }
201 }
202 }
203 }
204
205 /* we must not shift variables to infinity */
206 return SCIPisInfinity(scip, shiftdown ? -newsolval : newsolval) ? 0.0 : newsolval - solval;
207}
208
209
210/** update row activities after a variable's solution value changed */
211static
213 SCIP* scip, /**< SCIP data structure */
214 SCIP_Real* activities, /**< LP row activities */
215 SCIP_VAR* var, /**< variable that has been changed */
216 SCIP_Real shiftval /**< value that is added to variable */
217 )
218{
219 SCIP_Real* colvals;
220 SCIP_ROW** colrows;
221 SCIP_COL* col;
222
223 int ncolrows;
224
225 assert(activities != NULL);
226
227 /* get data of column associated to variable */
228 col = SCIPvarGetCol(var);
229 colrows = SCIPcolGetRows(col);
230 colvals = SCIPcolGetVals(col);
231 ncolrows = SCIPcolGetNLPNonz(col);
232 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
233
234 /* enumerate all rows with nonzero entry in this column */
235 for( int i = 0; i < ncolrows; ++i )
236 {
237 SCIP_ROW* row;
238 int rowpos;
239
240 row = colrows[i];
241 rowpos = SCIProwGetLPPos(row);
242 assert(-1 <= rowpos && rowpos < SCIPgetNLPRows(scip) );
243
244 /* update row activity, only regard global rows in the LP */
245 if( rowpos >= 0 && !SCIProwIsLocal(row) )
246 {
247 activities[rowpos] += shiftval * colvals[i];
248
249 if( SCIPisInfinity(scip, activities[rowpos]) )
250 activities[rowpos] = SCIPinfinity(scip);
251 else if( SCIPisInfinity(scip, -activities[rowpos]) )
252 activities[rowpos] = -SCIPinfinity(scip);
253 }
254 }
255
256 return SCIP_OKAY;
257}
258
259/** setup and solve oneopt sub-SCIP */
260static
262 SCIP* scip, /**< SCIP data structure */
263 SCIP* subscip, /**< sub-SCIP data structure */
264 SCIP_HEUR* heur, /**< oneopt heuristic */
265 SCIP_VAR** vars, /**< SCIP variables */
266 SCIP_VAR** subvars, /**< subproblem's variables */
267 SCIP_SOL* bestsol, /**< incumbent solution */
268 SCIP_RESULT* result, /**< pointer to store the result */
269 SCIP_Bool* valid /**< pointer to store the valid value */
270 )
271{
272 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
273 SCIP_SOL* startsol;
274 int nvars; /* number of original problem's variables */
275
276 assert(scip != NULL);
277 assert(subscip != NULL);
278 assert(heur != NULL);
279
280 nvars = SCIPgetNVars(scip);
281
282 /* create the variable mapping hash map */
283 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
284
285 /* copy complete SCIP instance */
286 *valid = FALSE;
287 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "oneopt", TRUE, FALSE, FALSE, TRUE, valid) );
288 SCIP_CALL( SCIPtransformProb(subscip) );
289
290 /* get variable image and create start solution for the subproblem */
291 SCIP_CALL( SCIPcreateOrigSol(subscip, &startsol, NULL) );
292 for( int i = 0; i < nvars; ++i )
293 {
294 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
295 if( subvars[i] != NULL )
296 SCIP_CALL( SCIPsetSolVal(subscip, startsol, subvars[i], SCIPgetSolVal(scip, bestsol, vars[i])) );
297 }
298
299 /* try to add new solution to sub-SCIP and free it immediately */
300 *valid = FALSE;
301 SCIP_CALL( SCIPtrySolFree(subscip, &startsol, FALSE, FALSE, FALSE, FALSE, FALSE, valid) );
302 SCIPhashmapFree(&varmapfw);
303
304 /* deactivate basically everything except oneopt in the sub-SCIP */
308
309 /* set limits for the subproblem */
310 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
311 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
312
313 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
314
315#ifdef SCIP_DEBUG
316 /* for debugging, enable full output */
317 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
318 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
319#else
320 /* disable statistic timing inside sub SCIP and output to console */
321 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
322 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
323#endif
324
325 /* if necessary, some of the parameters have to be unfixed first */
326 if( SCIPisParamFixed(subscip, "lp/solvefreq") )
327 {
328 SCIPwarningMessage(scip, "unfixing parameter lp/solvefreq in subscip of oneopt heuristic\n");
329 SCIP_CALL( SCIPunfixParam(subscip, "lp/solvefreq") );
330 }
331 SCIP_CALL( SCIPsetIntParam(subscip, "lp/solvefreq", -1) );
332
333 if( SCIPisParamFixed(subscip, "heuristics/oneopt/freq") )
334 {
335 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/freq in subscip of oneopt heuristic\n");
336 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/freq") );
337 }
338 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) );
339
340 if( SCIPisParamFixed(subscip, "heuristics/oneopt/forcelpconstruction") )
341 {
342 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/forcelpconstruction in subscip of oneopt heuristic\n");
343 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/forcelpconstruction") );
344 }
345 SCIP_CALL( SCIPsetBoolParam(subscip, "heuristics/oneopt/forcelpconstruction", TRUE) );
346
347 /* avoid recursive call, which would lead to an endless loop */
348 if( SCIPisParamFixed(subscip, "heuristics/oneopt/beforepresol") )
349 {
350 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/beforepresol in subscip of oneopt heuristic\n");
351 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/beforepresol") );
352 }
353 SCIP_CALL( SCIPsetBoolParam(subscip, "heuristics/oneopt/beforepresol", FALSE) );
354
355 /* speed up sub-SCIP by not checking dual LP feasibility */
356 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
357
358 if( *valid )
359 {
360 /* errors in solving the subproblem should not kill the overall solving process;
361 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
362 */
363 SCIP_CALL_ABORT( SCIPsolve(subscip) );
364
365#ifdef SCIP_DEBUG
367#endif
368
369 /* check, whether a solution was found;
370 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
371 */
372 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, valid, NULL) );
373 if( *valid )
374 *result = SCIP_FOUNDSOL;
375 }
376
377 return SCIP_OKAY;
378}
379
380/*
381 * Callback methods of primal heuristic
382 */
383
384/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
385static
386SCIP_DECL_HEURCOPY(heurCopyOneopt)
387{ /*lint --e{715}*/
388 assert(scip != NULL);
389 assert(heur != NULL);
390 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
391
392 /* call inclusion method of primal heuristic */
394
395 return SCIP_OKAY;
396}
397
398/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
399static
400SCIP_DECL_HEURFREE(heurFreeOneopt)
401{ /*lint --e{715}*/
402 SCIP_HEURDATA* heurdata;
403
404 assert(heur != NULL);
405 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
406 assert(scip != NULL);
407
408 /* free heuristic data */
409 heurdata = SCIPheurGetData(heur);
410 assert(heurdata != NULL);
411 SCIPfreeBlockMemory(scip, &heurdata);
412 SCIPheurSetData(heur, NULL);
413
414 return SCIP_OKAY;
415}
416
417
418/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
419static
420SCIP_DECL_HEURINITSOL(heurInitsolOneopt)
421{
422 SCIP_HEURDATA* heurdata;
423
424 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
425
426 /* create heuristic data */
427 heurdata = SCIPheurGetData(heur);
428 assert(heurdata != NULL);
429
430 /* if the heuristic is called at the root node, we may want to be called during the cut-and-price loop and even before the first LP solve */
431 if( heurdata->duringroot && SCIPheurGetFreqofs(heur) == 0 )
433
434 return SCIP_OKAY;
435}
436
437/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
438static
439SCIP_DECL_HEUREXITSOL(heurExitsolOneopt)
440{
441 assert(heur != NULL);
442 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
443
444 /* reset the timing mask to its default value */
446
447 return SCIP_OKAY;
448}
449
450/** initialization method of primal heuristic (called after problem was transformed) */
451static
452SCIP_DECL_HEURINIT(heurInitOneopt)
453{ /*lint --e{715}*/
454 SCIP_HEURDATA* heurdata;
455
456 assert(heur != NULL);
457 assert(scip != NULL);
458
459 /* get heuristic data */
460 heurdata = SCIPheurGetData(heur);
461 assert(heurdata != NULL);
462
463 /* initialize last solution index */
464 heurdata->lastsolindex = -1;
465
466 return SCIP_OKAY;
467}
468
469/** execution method of primal heuristic */
470static
471SCIP_DECL_HEUREXEC(heurExecOneopt)
472{ /*lint --e{715}*/
473 SCIP_HEURDATA* heurdata;
474 SCIP_SOL* bestsol; /* incumbent solution */
475 SCIP_SOL* worksol; /* heuristic's working solution */
476 SCIP_VAR** vars; /* SCIP variables */
477 SCIP_VAR** shiftcands; /* shiftable variables */
478 SCIP_ROW** lprows; /* SCIP LP rows */
479 SCIP_Real* activities; /* row activities for working solution */
480 SCIP_Real* shiftvals;
481 SCIP_Bool shifted;
482
483 SCIP_RETCODE retcode;
484
485 SCIP_Real lb;
486 SCIP_Real ub;
487 SCIP_Bool valid;
488 int nchgbound;
489 int nbinvars;
490 int nintvars;
491 int nvars;
492 int nlprows;
493 int nshiftcands;
494 int shiftcandssize;
495 int nsuccessfulshifts;
496 int niterations;
497
498 assert(heur != NULL);
499 assert(scip != NULL);
500 assert(result != NULL);
501
502 /* get heuristic's data */
503 heurdata = SCIPheurGetData(heur);
504 assert(heurdata != NULL);
505
506 *result = SCIP_DELAYED;
507
508 /* we only want to process each solution once */
509 bestsol = SCIPgetBestSol(scip);
510 if( bestsol == NULL || heurdata->lastsolindex == SCIPsolGetIndex(bestsol) )
511 return SCIP_OKAY;
512
513 /* reset the timing mask to its default value (at the root node it could be different) */
514 if( SCIPgetNNodes(scip) > 1 )
516
517 /* get problem variables */
518 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
519 nintvars += nbinvars;
520
521 /* do not run if there are no discrete variables */
522 if( nintvars == 0 )
523 {
524 *result = SCIP_DIDNOTRUN;
525 return SCIP_OKAY;
526 }
527
528 if( heurtiming == SCIP_HEURTIMING_BEFOREPRESOL )
529 {
530 SCIP* subscip; /* the subproblem created by oneopt */
531 SCIP_VAR** subvars; /* subproblem's variables */
532
533 SCIP_Bool success;
534
535 if( !heurdata->beforepresol )
536 return SCIP_OKAY;
537
538 /* check whether there is enough time and memory left */
539 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
540
541 if( !success )
542 return SCIP_OKAY;
543
544 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
545
546 /* initialize the subproblem */
547 SCIP_CALL( SCIPcreate(&subscip) );
548
549 /* setup and solve the subproblem and catch the return code */
550 retcode = setupAndSolveSubscipOneopt(scip, subscip, heur, vars, subvars, bestsol, result, &valid);
551
552 /* free the subscip in any case */
553 SCIP_CALL( SCIPfree(&subscip) );
554 SCIP_CALL( retcode );
555
556 SCIPfreeBufferArray(scip, &subvars);
557
558 return SCIP_OKAY;
559 }
560
561 /* we can only work on solutions valid in the transformed space */
562 if( SCIPsolIsOriginal(bestsol) )
563 return SCIP_OKAY;
564
565 if( heurtiming == SCIP_HEURTIMING_BEFORENODE && (SCIPhasCurrentNodeLP(scip) || heurdata->forcelpconstruction) )
566 {
567 SCIP_Bool cutoff;
568
569 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
570
571 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
572 if( cutoff )
573 {
575 return SCIP_OKAY;
576 }
577
579
580 /* get problem variables again, SCIPconstructLP() might have added new variables */
581 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
582 nintvars += nbinvars;
583 }
584
585 /* we need an LP */
586 if( SCIPgetNLPRows(scip) == 0 )
587 return SCIP_OKAY;
588
589 *result = SCIP_DIDNOTFIND;
590
591 heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
592 SCIP_CALL( SCIPcreateSolCopy(scip, &worksol, bestsol) );
593 SCIPsolSetHeur(worksol,heur);
594
595 SCIPdebugMsg(scip, "Starting bound adjustment in 1-opt heuristic\n");
596
597 nchgbound = 0;
598 /* change solution values due to possible global bound changes first */
599 for( int i = nvars - 1; i >= 0; --i )
600 {
601 SCIP_VAR* var;
602 SCIP_Real solval;
603
604 var = vars[i];
605 lb = SCIPvarGetLbGlobal(var);
606 ub = SCIPvarGetUbGlobal(var);
607
608 solval = SCIPgetSolVal(scip, worksol, var);
609 /* old solution value is smaller than the actual lower bound */
610 if( SCIPisFeasLT(scip, solval, lb) )
611 {
612 /* set the solution value to the global lower bound */
613 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, lb) );
614 ++nchgbound;
615 SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to lb %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, lb);
616 }
617 /* old solution value is greater than the actual upper bound */
618 else if( SCIPisFeasGT(scip, solval, SCIPvarGetUbGlobal(var)) )
619 {
620 /* set the solution value to the global upper bound */
621 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, ub) );
622 ++nchgbound;
623 SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to ub %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, ub);
624 }
625 }
626
627 SCIPdebugMsg(scip, "number of bound changes (due to global bounds) = %d\n", nchgbound);
628
629 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
630 SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
631
632 valid = TRUE;
633
634 /* initialize LP row activities */
635 for( int i = 0; i < nlprows; ++i )
636 {
637 SCIP_ROW* row;
638
639 row = lprows[i];
640 assert(SCIProwGetLPPos(row) == i);
641
642 if( !SCIProwIsLocal(row) )
643 {
644 activities[i] = SCIPgetRowSolActivity(scip, row, worksol);
645 SCIPdebugMsg(scip, "Row <%s> has activity %g\n", SCIProwGetName(row), activities[i]);
646 if( SCIPisFeasLT(scip, activities[i], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, activities[i], SCIProwGetRhs(row)) )
647 {
648 valid = FALSE;
650 SCIPdebugMsg(scip, "row <%s> activity %g violates bounds, lhs = %g, rhs = %g\n", SCIProwGetName(row), activities[i], SCIProwGetLhs(row), SCIProwGetRhs(row));
651 break;
652 }
653 }
654 }
655
656 if( !valid )
657 {
658 /** @todo try to correct lp rows */
659 SCIPdebugMsg(scip, "Some global bound changes were not valid in lp rows.\n");
660
661 SCIPfreeBufferArray(scip, &activities);
662 SCIP_CALL( SCIPfreeSol(scip, &worksol) );
663
664 return SCIP_OKAY;
665 }
666
667 /* allocate buffer storage for possible shift candidates */
668 shiftcandssize = 8;
669 SCIP_CALL( SCIPallocBufferArray(scip, &shiftcands, shiftcandssize) );
670 SCIP_CALL( SCIPallocBufferArray(scip, &shiftvals, shiftcandssize) );
671 nsuccessfulshifts = 0;
672 niterations = 0;
673 do
674 {
675 /* initialize data */
676 shifted = FALSE;
677 nshiftcands = 0;
678 ++niterations;
679 SCIPdebugMsg(scip, "Starting 1-opt heuristic iteration #%d\n", niterations);
680
681 /* enumerate all integer variables and find out which of them are shiftable */
682 /* @todo if useloop=TRUE store for each variable which constraint blocked it and only iterate over those variables
683 * in the following rounds for which the constraint slack was increased by previous shifts
684 */
685 for( int i = 0; i < nintvars; ++i )
686 {
688 {
689 SCIP_Real shiftval;
690 SCIP_Real solval;
691
692 /* find out whether the variable can be shifted */
693 solval = SCIPgetSolVal(scip, worksol, vars[i]);
694 shiftval = calcShiftVal(scip, vars[i], solval, activities);
695
696 /* insert the variable into the list of shifting candidates */
697 if( !SCIPisFeasZero(scip, shiftval) )
698 {
699 SCIPdebugMsg(scip, " -> Variable <%s> can be shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval);
700
701 if( nshiftcands == shiftcandssize)
702 {
703 shiftcandssize *= 8;
704 SCIP_CALL( SCIPreallocBufferArray(scip, &shiftcands, shiftcandssize) );
705 SCIP_CALL( SCIPreallocBufferArray(scip, &shiftvals, shiftcandssize) );
706 }
707 shiftcands[nshiftcands] = vars[i];
708 shiftvals[nshiftcands] = shiftval;
709 nshiftcands++;
710 }
711 }
712 }
713
714 /* if at least one variable can be shifted, shift variables sorted by their objective */
715 if( nshiftcands > 0 )
716 {
717 SCIP_Real shiftval;
718 SCIP_Real solval;
719 SCIP_VAR* var;
720
721 /* the case that exactly one variable can be shifted is slightly easier */
722 if( nshiftcands == 1 )
723 {
724 var = shiftcands[0];
725 assert(var != NULL);
726 solval = SCIPgetSolVal(scip, worksol, var);
727 shiftval = shiftvals[0];
728 assert(!SCIPisFeasZero(scip,shiftval));
729 SCIPdebugMsg(scip, " Only one shiftcand found, var <%s>, which is now shifted by<%1.1f> \n",
730 SCIPvarGetName(var), shiftval);
731 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, solval+shiftval) );
732 SCIP_CALL( updateRowActivities(scip, activities, var, shiftval) );
733 ++nsuccessfulshifts;
734 }
735 else
736 {
737 SCIP_Real* objcoeffs;
738
739 SCIP_CALL( SCIPallocBufferArray(scip, &objcoeffs, nshiftcands) );
740
741 SCIPdebugMsg(scip, " %d shiftcands found \n", nshiftcands);
742
743 /* sort the variables by their objective, optionally weighted with the shiftval */
744 if( heurdata->weightedobj )
745 {
746 for( int i = 0; i < nshiftcands; ++i )
747 objcoeffs[i] = SCIPvarGetObj(shiftcands[i])*shiftvals[i];
748 }
749 else
750 {
751 for( int i = 0; i < nshiftcands; ++i )
752 objcoeffs[i] = SCIPvarGetObj(shiftcands[i]);
753 }
754
755 /* sort arrays with respect to the first one */
756 SCIPsortRealPtr(objcoeffs, (void**)shiftcands, nshiftcands);
757
758 /* try to shift each variable -> Activities have to be updated */
759 for( int i = 0; i < nshiftcands; ++i )
760 {
761 var = shiftcands[i];
762 assert(var != NULL);
763 solval = SCIPgetSolVal(scip, worksol, var);
764 shiftval = calcShiftVal(scip, var, solval, activities);
765 assert(i > 0 || !SCIPisFeasZero(scip, shiftval));
766 assert(SCIPisFeasGE(scip, solval+shiftval, SCIPvarGetLbGlobal(var)) && SCIPisFeasLE(scip, solval+shiftval, SCIPvarGetUbGlobal(var)));
767
768 /* update data structures for nonzero shift value */
769 if( ! SCIPisFeasZero(scip, shiftval) )
770 {
771 SCIPdebugMsg(scip, " -> Variable <%s> is now shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval);
772 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, solval+shiftval) );
773 SCIP_CALL( updateRowActivities(scip, activities, var, shiftval) );
774 ++nsuccessfulshifts;
775 }
776 }
777
778 SCIPfreeBufferArray(scip, &objcoeffs);
779 }
780 shifted = TRUE;
781 }
782 }
783 while( heurdata->useloop && shifted );
784
785 if( nsuccessfulshifts > 0 )
786 {
787 /* if the problem is a pure IP, try to install the solution, if it is a MIP, solve LP again to set the continuous
788 * variables to the best possible value
789 */
790 if( nvars == nintvars || !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
791 {
792 SCIP_Bool success;
793
794 /* since activities are maintained iteratively, we cannot guarantee the feasibility of the shiftings and have
795 * to set the checklprows flag to TRUE
796 */
797 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
798
799 if( success )
800 {
801 SCIPdebugMsg(scip, "found feasible shifted solution:\n");
802 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
803 *result = SCIP_FOUNDSOL;
804 }
805 }
806 else
807 {
808 SCIP_Bool lperror;
809#ifdef NDEBUG
810 SCIP_RETCODE retstat;
811#endif
812
813 SCIPdebugMsg(scip, "shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
814
815 /* start diving to calculate the LP relaxation */
817
818 /* set the bounds of the variables: fixed for integers, global bounds for continuous */
819 for( int i = 0; i < nvars; ++i )
820 {
822 {
823 SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], SCIPvarGetLbGlobal(vars[i])) );
824 SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], SCIPvarGetUbGlobal(vars[i])) );
825 }
826 }
827 /* apply this after global bounds to not cause an error with intermediate empty domains */
828 for( int i = 0; i < nintvars; ++i )
829 {
831 {
832 SCIP_Real solval;
833 solval = SCIPgetSolVal(scip, worksol, vars[i]);
834 SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], solval) );
835 SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], solval) );
836 }
837 }
838
839 /* solve LP */
840 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
841
842 /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE, say, rather solve the NLP instead of the LP */
843 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
844 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
845 */
846#ifdef NDEBUG
847 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
848 if( retstat != SCIP_OKAY )
849 {
850 SCIPwarningMessage(scip, "Error while solving LP in 1-opt heuristic; LP solve terminated with code <%d>\n",retstat);
851 }
852#else
853 SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
854#endif
855
856 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
857 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
858
859 /* check if this is a feasible solution */
860 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
861 {
862 SCIP_Bool success;
863
864 /* copy the current LP solution to the working solution */
865 SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
866 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
867
868 /* check solution for feasibility */
869 if( success )
870 {
871 SCIPdebugMsg(scip, "found feasible shifted solution:\n");
872 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
873 *result = SCIP_FOUNDSOL;
874 }
875 }
876
877 /* terminate the diving */
879 }
880 }
881
882 /* heuristic should not rerun on this incumbent because the heuristic loop finishes only after no further
883 * improvements of the incumbent solution are possible
884 */
885 if( heurdata->useloop )
886 heurdata->lastsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
887
888 SCIPfreeBufferArray(scip, &shiftvals);
889 SCIPfreeBufferArray(scip, &shiftcands);
890 SCIPfreeBufferArray(scip, &activities);
891
892 SCIP_CALL( SCIPfreeSol(scip, &worksol) );
893
894 SCIPdebugMsg(scip, "Finished 1-opt heuristic\n");
895
896 return SCIP_OKAY;
897}
898
899/*
900 * primal heuristic specific interface methods
901 */
902
903/** creates the oneopt primal heuristic and includes it in SCIP */
905 SCIP* scip /**< SCIP data structure */
906 )
907{
908 SCIP_HEURDATA* heurdata;
909 SCIP_HEUR* heur;
910
911 /* create Oneopt primal heuristic data */
912 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
913
914 /* include primal heuristic */
917 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecOneopt, heurdata) );
918
919 assert(heur != NULL);
920
921 /* set non-NULL pointers to callback methods */
922 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyOneopt) );
923 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeOneopt) );
924 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolOneopt) );
925 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolOneopt) );
926 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitOneopt) );
927
928 /* add oneopt primal heuristic parameters */
929 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/weightedobj",
930 "should the objective be weighted with the potential shifting value when sorting the shifting candidates?",
931 &heurdata->weightedobj, TRUE, DEFAULT_WEIGHTEDOBJ, NULL, NULL) );
932
933 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/duringroot",
934 "should the heuristic be called before and during the root node?",
935 &heurdata->duringroot, TRUE, DEFAULT_DURINGROOT, NULL, NULL) );
936
937 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/forcelpconstruction",
938 "should the construction of the LP be forced even if LP solving is deactivated?",
939 &heurdata->forcelpconstruction, TRUE, DEFAULT_FORCELPCONSTRUCTION, NULL, NULL) );
940
941 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/beforepresol",
942 "should the heuristic be called before presolving?",
943 &heurdata->beforepresol, TRUE, DEFAULT_BEFOREPRESOL, NULL, NULL) );
944
945 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/useloop",
946 "should the heuristic continue to run as long as improvements are found?",
947 &heurdata->useloop, TRUE, DEFAULT_USELOOP, NULL, NULL) );
948
949 return SCIP_OKAY;
950}
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1448
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2875
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:927
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:385
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
SCIP_RETCODE SCIPincludeHeurOneopt(SCIP *scip)
Definition: heur_oneopt.c:904
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17140
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1493
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1559
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2419
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2451
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2242
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2678
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2291
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:148
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:124
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17523
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2144
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:474
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:421
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2835
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 SCIPtrySolFree(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:3050
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
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
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2849
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
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
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
static SCIP_RETCODE setupAndSolveSubscipOneopt(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_SOL *bestsol, SCIP_RESULT *result, SCIP_Bool *valid)
Definition: heur_oneopt.c:261
#define DEFAULT_FORCELPCONSTRUCTION
Definition: heur_oneopt.c:74
static SCIP_DECL_HEUREXEC(heurExecOneopt)
Definition: heur_oneopt.c:471
#define HEUR_TIMING
Definition: heur_oneopt.c:68
#define HEUR_FREQOFS
Definition: heur_oneopt.c:66
#define HEUR_DESC
Definition: heur_oneopt.c:62
static SCIP_RETCODE updateRowActivities(SCIP *scip, SCIP_Real *activities, SCIP_VAR *var, SCIP_Real shiftval)
Definition: heur_oneopt.c:212
static SCIP_DECL_HEURINITSOL(heurInitsolOneopt)
Definition: heur_oneopt.c:420
#define DEFAULT_WEIGHTEDOBJ
Definition: heur_oneopt.c:71
#define HEUR_DISPCHAR
Definition: heur_oneopt.c:63
#define HEUR_MAXDEPTH
Definition: heur_oneopt.c:67
#define HEUR_PRIORITY
Definition: heur_oneopt.c:64
#define DEFAULT_DURINGROOT
Definition: heur_oneopt.c:72
#define HEUR_NAME
Definition: heur_oneopt.c:61
static SCIP_Real calcShiftVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real *activities)
Definition: heur_oneopt.c:98
static SCIP_DECL_HEURFREE(heurFreeOneopt)
Definition: heur_oneopt.c:400
#define DEFAULT_BEFOREPRESOL
Definition: heur_oneopt.c:73
static SCIP_DECL_HEUREXITSOL(heurExitsolOneopt)
Definition: heur_oneopt.c:439
static SCIP_DECL_HEURCOPY(heurCopyOneopt)
Definition: heur_oneopt.c:386
#define HEUR_FREQ
Definition: heur_oneopt.c:65
static SCIP_DECL_HEURINIT(heurInitOneopt)
Definition: heur_oneopt.c:452
#define HEUR_USESSUBSCIP
Definition: heur_oneopt.c:69
#define DEFAULT_USELOOP
Definition: heur_oneopt.c:75
Improvement heuristic that alters single variable values.
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for problem variables
public methods for problem copies
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for the branch-and-bound tree
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DELAYED
Definition: type_result.h:43
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define SCIP_HEURTIMING_BEFOREPRESOL
Definition: type_timing.h:90
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition: type_timing.h:79
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:78
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51