SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_rounding.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-2023 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_rounding.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP rounding heuristic that tries to recover from intermediate infeasibilities
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/heur_rounding.h"
35#include "scip/pub_heur.h"
36#include "scip/pub_lp.h"
37#include "scip/pub_message.h"
38#include "scip/pub_var.h"
39#include "scip/scip_branch.h"
40#include "scip/scip_heur.h"
41#include "scip/scip_lp.h"
42#include "scip/scip_mem.h"
43#include "scip/scip_message.h"
44#include "scip/scip_numerics.h"
45#include "scip/scip_param.h"
46#include "scip/scip_sol.h"
48#include <string.h>
49
50#define HEUR_NAME "rounding"
51#define HEUR_DESC "LP rounding heuristic with infeasibility recovering"
52#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
53#define HEUR_PRIORITY -1000
54#define HEUR_FREQ 1
55#define HEUR_FREQOFS 0
56#define HEUR_MAXDEPTH -1
57#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP
58#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
59
60#define DEFAULT_SUCCESSFACTOR 100 /**< number of calls per found solution that are considered as standard success,
61 * a higher factor causes the heuristic to be called more often
62 */
63#define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */
64
65/* locally defined heuristic data */
66struct SCIP_HeurData
67{
68 SCIP_SOL* sol; /**< working solution */
69 SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
70 int successfactor; /**< number of calls per found solution that are considered as standard success,
71 * a higher factor causes the heuristic to be called more often
72 */
73 SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */
74};
75
76
77/*
78 * local methods
79 */
80
81/** update row violation arrays after a row's activity value changed */
82static
84 SCIP* scip, /**< SCIP data structure */
85 SCIP_ROW* row, /**< LP row */
86 SCIP_ROW** violrows, /**< array with currently violated rows */
87 int* violrowpos, /**< position of LP rows in violrows array */
88 int* nviolrows, /**< pointer to the number of currently violated rows */
89 SCIP_Real oldactivity, /**< old activity value of LP row */
90 SCIP_Real newactivity /**< new activity value of LP row */
91 )
92{
93 SCIP_Real lhs;
94 SCIP_Real rhs;
95 SCIP_Bool oldviol;
96 SCIP_Bool newviol;
97
101
102 lhs = SCIProwGetLhs(row);
103 rhs = SCIProwGetRhs(row);
106 if( oldviol != newviol )
107 {
108 int rowpos;
109 int violpos;
110
111 rowpos = SCIProwGetLPPos(row);
112 assert(rowpos >= 0);
113
114 if( oldviol )
115 {
116 /* the row violation was repaired: remove row from violrows array, decrease violation count */
118 assert(0 <= violpos && violpos < *nviolrows);
119 assert(violrows[violpos] == row);
120 violrowpos[rowpos] = -1;
121 if( violpos != *nviolrows-1 )
122 {
125 }
126 (*nviolrows)--;
127 }
128 else
129 {
130 /* the row is now violated: add row to violrows array, increase violation count */
131 assert(violrowpos[rowpos] == -1);
132 violrows[*nviolrows] = row;
134 (*nviolrows)++;
135 }
136 }
137}
138
139/** update row activities after a variable's solution value changed */
140static
142 SCIP* scip, /**< SCIP data structure */
143 SCIP_Real* activities, /**< LP row activities */
144 SCIP_ROW** violrows, /**< array with currently violated rows */
145 int* violrowpos, /**< position of LP rows in violrows array */
146 int* nviolrows, /**< pointer to the number of currently violated rows */
147 int nlprows, /**< number of rows in current LP */
148 SCIP_VAR* var, /**< variable that has been changed */
149 SCIP_Real oldsolval, /**< old solution value of variable */
150 SCIP_Real newsolval /**< new solution value of variable */
151 )
152{
153 SCIP_COL* col;
155 SCIP_Real* colvals;
156 SCIP_Real delta;
157 int ncolrows;
158 int r;
159
162 assert(0 <= *nviolrows && *nviolrows <= nlprows);
163
164 delta = newsolval - oldsolval;
165 col = SCIPvarGetCol(var);
166 colrows = SCIPcolGetRows(col);
167 colvals = SCIPcolGetVals(col);
169 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
170
171 for( r = 0; r < ncolrows; ++r )
172 {
173 SCIP_ROW* row;
174 int rowpos;
175
176 row = colrows[r];
177 rowpos = SCIProwGetLPPos(row);
178 assert(-1 <= rowpos && rowpos < nlprows);
179
180 if( rowpos >= 0 && !SCIProwIsLocal(row) )
181 {
182 SCIP_Real oldactivity;
183 SCIP_Real newactivity;
184
185 assert(SCIProwIsInLP(row));
186
187 /* update row activity */
190 {
191 newactivity = oldactivity + delta * colvals[r];
194 else if( SCIPisInfinity(scip, -newactivity) )
197
198 /* update row violation arrays */
200 }
201 }
202 }
203
204 return SCIP_OKAY;
205}
206
207/** returns a variable, that pushes activity of the row in the given direction with minimal negative impact on other rows;
208 * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
209 * rounding in a direction is forbidden, if this forces the objective value over the upper bound
210 */
211static
213 SCIP* scip, /**< SCIP data structure */
214 SCIP_SOL* sol, /**< primal solution */
215 SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
216 SCIP_ROW* row, /**< LP row */
217 int direction, /**< should the activity be increased (+1) or decreased (-1)? */
218 SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
219 SCIP_Real* oldsolval, /**< pointer to store old (fractional) solution value of rounding variable */
220 SCIP_Real* newsolval /**< pointer to store new (rounded) solution value of rounding variable */
221 )
222{
223 SCIP_COL* col;
224 SCIP_VAR* var;
225 SCIP_Real val;
227 SCIP_Real* rowvals;
228 SCIP_Real solval;
229 SCIP_Real roundval;
230 SCIP_Real obj;
231 SCIP_Real deltaobj;
232 SCIP_Real bestdeltaobj;
233 SCIP_VARTYPE vartype;
234 int nrowcols;
235 int nlocks;
236 int minnlocks;
237 int c;
238
239 assert(direction == +1 || direction == -1);
240 assert(roundvar != NULL);
243
244 /* get row entries */
245 rowcols = SCIProwGetCols(row);
246 rowvals = SCIProwGetVals(row);
248
249 /* select rounding variable */
252 *roundvar = NULL;
253 for( c = 0; c < nrowcols; ++c )
254 {
255 col = rowcols[c];
256 var = SCIPcolGetVar(col);
257
258 vartype = SCIPvarGetType(var);
259 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
260 {
261 solval = SCIPgetSolVal(scip, sol, var);
262
263 if( !SCIPisFeasIntegral(scip, solval) )
264 {
265 val = rowvals[c];
267
268 if( direction * val < 0.0 )
269 {
270 /* rounding down */
272 if( nlocks <= minnlocks )
273 {
274 roundval = SCIPfeasFloor(scip, solval);
275 deltaobj = obj * (roundval - solval);
276 if( (nlocks < minnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
277 {
278 minnlocks = nlocks;
280 *roundvar = var;
281 *oldsolval = solval;
283 }
284 }
285 }
286 else
287 {
288 /* rounding up */
289 assert(direction * val > 0.0);
291 if( nlocks <= minnlocks )
292 {
293 roundval = SCIPfeasCeil(scip, solval);
294 deltaobj = obj * (roundval - solval);
295 if( (nlocks < minnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
296 {
297 minnlocks = nlocks;
299 *roundvar = var;
300 *oldsolval = solval;
302 }
303 }
304 }
305 }
306 }
307 }
308
309 return SCIP_OKAY;
310}
311
312/** returns a variable, that increases the activity of the row */
313static
315 SCIP* scip, /**< SCIP data structure */
316 SCIP_SOL* sol, /**< primal solution */
317 SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
318 SCIP_ROW* row, /**< LP row */
319 SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
320 SCIP_Real* oldsolval, /**< old (fractional) solution value of rounding variable */
321 SCIP_Real* newsolval /**< new (rounded) solution value of rounding variable */
322 )
323{
325}
326
327/** returns a variable, that decreases the activity of the row */
328static
330 SCIP* scip, /**< SCIP data structure */
331 SCIP_SOL* sol, /**< primal solution */
332 SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
333 SCIP_ROW* row, /**< LP row */
334 SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
335 SCIP_Real* oldsolval, /**< old (fractional) solution value of rounding variable */
336 SCIP_Real* newsolval /**< new (rounded) solution value of rounding variable */
337 )
338{
340}
341
342/** returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to
343 * fix in the other direction;
344 * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
345 * rounding in a direction is forbidden, if this forces the objective value over the upper bound
346 */
347static
349 SCIP* scip, /**< SCIP data structure */
350 SCIP_SOL* sol, /**< primal solution */
351 SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
352 SCIP_VAR** lpcands, /**< fractional variables in LP */
353 int nlpcands, /**< number of fractional variables in LP */
354 SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
355 SCIP_Real* oldsolval, /**< old (fractional) solution value of rounding variable */
356 SCIP_Real* newsolval /**< new (rounded) solution value of rounding variable */
357 )
358{
359 SCIP_VAR* var;
360 SCIP_Real solval;
361 SCIP_Real roundval;
362 SCIP_Real obj;
363 SCIP_Real deltaobj;
364 SCIP_Real bestdeltaobj;
365 int maxnlocks;
366 int nlocks;
367 int v;
368
369 assert(roundvar != NULL);
372
373 /* select rounding variable */
374 maxnlocks = -1;
376 *roundvar = NULL;
377 for( v = 0; v < nlpcands; ++v )
378 {
379 var = lpcands[v];
381
382 solval = SCIPgetSolVal(scip, sol, var);
383 if( !SCIPisFeasIntegral(scip, solval) )
384 {
386
387 /* rounding down */
389 if( nlocks >= maxnlocks )
390 {
391 roundval = SCIPfeasFloor(scip, solval);
392 deltaobj = obj * (roundval - solval);
393 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
394 {
395 maxnlocks = nlocks;
397 *roundvar = var;
398 *oldsolval = solval;
400 }
401 }
402
403 /* rounding up */
405 if( nlocks >= maxnlocks )
406 {
407 roundval = SCIPfeasCeil(scip, solval);
408 deltaobj = obj * (roundval - solval);
409 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
410 {
411 maxnlocks = nlocks;
413 *roundvar = var;
414 *oldsolval = solval;
416 }
417 }
418 }
419 }
420
421 return SCIP_OKAY;
422}
423
424
425/*
426 * Callback methods
427 */
428
429/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
430static
432{ /*lint --e{715}*/
433 assert(scip != NULL);
434 assert(heur != NULL);
436
437 /* call inclusion method of primal heuristic */
439
440 return SCIP_OKAY;
441}
442
443/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
444static
445SCIP_DECL_HEURFREE(heurFreeRounding) /*lint --e{715}*/
446{ /*lint --e{715}*/
448
449 assert(heur != NULL);
452
453 /* free heuristic data */
458
459 return SCIP_OKAY;
460}
461
462/** initialization method of primal heuristic (called after problem was transformed) */
463static
464SCIP_DECL_HEURINIT(heurInitRounding) /*lint --e{715}*/
465{ /*lint --e{715}*/
467
469
471 assert(heurdata != NULL);
472
473 /* create heuristic data */
475 heurdata->lastlp = -1;
476
477 return SCIP_OKAY;
478}
479
480/** deinitialization method of primal heuristic (called before transformed problem is freed) */
481static
482SCIP_DECL_HEUREXIT(heurExitRounding) /*lint --e{715}*/
483{ /*lint --e{715}*/
485
487
488 /* free heuristic data */
490 assert(heurdata != NULL);
492
493 return SCIP_OKAY;
494}
495
496/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
497static
499{
501
503
505 assert(heurdata != NULL);
506 heurdata->lastlp = -1;
507
508 /* change the heuristic's timingmask, if nit should be called only once per node */
509 if( heurdata->oncepernode )
511
512 return SCIP_OKAY;
513}
514
515/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
516static
518{
519 /* reset the timing mask to its default value */
521
522 return SCIP_OKAY;
523}
524
525
526/** execution method of primal heuristic */
527static
528SCIP_DECL_HEUREXEC(heurExecRounding) /*lint --e{715}*/
529{ /*lint --e{715}*/
533 SCIP_Real* lpcandssol;
535 SCIP_Real* activities;
538 SCIP_Real obj;
539 SCIP_Real bestroundval;
540 SCIP_Real minobj;
543 int nfrac;
545 int c;
546 int r;
547 SCIP_Longint nlps;
548 SCIP_Longint ncalls;
549 SCIP_Longint nsolsfound;
550 SCIP_Longint nnodes;
551
553 assert(scip != NULL);
556
558
559 /* only call heuristic, if an optimal LP solution is at hand */
561 return SCIP_OKAY;
562
563 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
565 return SCIP_OKAY;
566
567 /* get heuristic data */
569 assert(heurdata != NULL);
570
571 /* don't call heuristic, if we have already processed the current LP solution */
573 if( nlps == heurdata->lastlp )
574 return SCIP_OKAY;
575 heurdata->lastlp = nlps;
576
577 /* don't call heuristic, if it was not successful enough in the past */
581 if( nnodes % ((ncalls/heurdata->successfactor)/(nsolsfound+1)+1) != 0 )
582 return SCIP_OKAY;
583
584 /* get fractional variables, that should be integral */
586 nfrac = nlpcands;
587
588 /* only call heuristic, if LP solution is fractional */
589 if( nfrac == 0 )
590 return SCIP_OKAY;
591
593
594 /* get LP rows */
596
597 SCIPdebugMsg(scip, "executing rounding heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
598
599 /* get memory for activities, violated rows, and row violation positions */
603
604 /* get the activities for all globally valid rows;
605 * the rows should be feasible, but due to numerical inaccuracies in the LP solver, they can be violated
606 */
607 nviolrows = 0;
608 for( r = 0; r < nlprows; ++r )
609 {
610 SCIP_ROW* row;
611
612 row = lprows[r];
613 assert(SCIProwGetLPPos(row) == r);
614
615 if( !SCIProwIsLocal(row) )
616 {
620 {
621 violrows[nviolrows] = row;
623 nviolrows++;
624 }
625 else
626 violrowpos[r] = -1;
627 }
628 }
629
630 /* get the working solution from heuristic's local data */
631 sol = heurdata->sol;
633
634 /* copy the current LP solution to the working solution */
636
637 /* calculate the minimal objective value possible after rounding fractional variables */
640 for( c = 0; c < nlpcands; ++c )
641 {
645 }
646
647 /* try to round remaining variables in order to become/stay feasible */
648 while( nfrac > 0 )
649 {
651 SCIP_Real oldsolval;
652 SCIP_Real newsolval;
653
654 SCIPdebugMsg(scip, "rounding heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
656
657 /* minobj < SCIPgetCutoffbound(scip) should be true, otherwise the rounding variable selection
658 * should have returned NULL. Due to possible cancellation we use SCIPisLE. */
660
661 /* choose next variable to process:
662 * - if a violated row exists, round a variable decreasing the violation, that has least impact on other rows
663 * - otherwise, round a variable, that has strongest devastating impact on rows in opposite direction
664 */
665 if( nviolrows > 0 )
666 {
667 SCIP_ROW* row;
668 int rowpos;
669
670 row = violrows[nviolrows-1];
671 rowpos = SCIProwGetLPPos(row);
672 assert(0 <= rowpos && rowpos < nlprows);
674
675 SCIPdebugMsg(scip, "rounding heuristic: try to fix violated row <%s>: %g <= %g <= %g\n",
678 {
679 /* lhs is violated: select a variable rounding, that increases the activity */
681 }
682 else
683 {
685 /* rhs is violated: select a variable rounding, that decreases the activity */
687 }
688 }
689 else
690 {
691 SCIPdebugMsg(scip, "rounding heuristic: search rounding variable and try to stay feasible\n");
693 }
694
695 /* check, whether rounding was possible */
696 if( roundvar == NULL )
697 {
698 SCIPdebugMsg(scip, "rounding heuristic: -> didn't find a rounding variable\n");
699 break;
700 }
701
702 SCIPdebugMsg(scip, "rounding heuristic: -> round var <%s>, oldval=%g, newval=%g, obj=%g\n",
704
705 /* update row activities of globally valid rows */
708
709 /* store new solution value and decrease fractionality counter */
711 nfrac--;
712
713 /* update minimal objective value possible after rounding remaining variables */
715 if( obj > 0.0 && newsolval > oldsolval )
716 minobj += obj;
717 else if( obj < 0.0 && newsolval < oldsolval )
718 minobj -= obj;
719
720 SCIPdebugMsg(scip, "rounding heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
722 }
723
724 /* check, if the new solution is feasible */
725 if( nfrac == 0 && nviolrows == 0 )
726 {
727 SCIP_Bool stored;
728
729 /* check solution for feasibility, and add it to solution store if possible
730 * neither integrality nor feasibility of LP rows has to be checked, because this is already
731 * done in the rounding heuristic itself; however, be better check feasibility of LP rows,
732 * because of numerical problems with activity updating
733 */
735
736 if( stored )
737 {
738#ifdef SCIP_DEBUG
739 SCIPdebugMsg(scip, "found feasible rounded solution:\n");
741#endif
743 }
744 }
745
746 /* free memory buffers */
750
751 return SCIP_OKAY;
752}
753
754
755/*
756 * heuristic specific interface methods
757 */
758
759/** creates the rounding heuristic with infeasibility recovering and includes it in SCIP */
761 SCIP* scip /**< SCIP data structure */
762 )
763{
765 SCIP_HEUR* heur;
766
767 /* create Rounding primal heuristic data */
769
770 /* include primal heuristic */
774
775 assert(heur != NULL);
776
777 /* set non-NULL pointers to callback methods */
784
785 /* add rounding primal heuristic parameters */
786 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/successfactor",
787 "number of calls per found solution that are considered as standard success, a higher factor causes the heuristic to be called more often",
788 &heurdata->successfactor, TRUE, DEFAULT_SUCCESSFACTOR, -1, INT_MAX, NULL, NULL) );
789
790 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/oncepernode",
791 "should the heuristic only be called once per node?",
792 &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) );
793
794 return SCIP_OKAY;
795}
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
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 SCIPincludeHeurRounding(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition lp.c:17042
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1361
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_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition heur.c:1586
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1596
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition heur.c:1490
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1576
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:242
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition scip_lp.c:83
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition scip_lp.c:570
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition scip_lp.c:247
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#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_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition lp.c:17227
int SCIProwGetLPPos(SCIP_ROW *row)
Definition lp.c:17501
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition lp.c:17401
const char * SCIProwGetName(SCIP_ROW *row)
Definition lp.c:17351
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:2104
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition lp.c:17523
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition lp.c:17248
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1775
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:3098
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1444
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1491
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1576
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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 SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17611
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
heurdata lastlp
static SCIP_SOL * sol
SCIP_VAR * var
int nlprows
static SCIP_RETCODE selectEssentialRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
* result
SCIP_Longint nsolsfound
heurdata
SCIPheurSetData(heur, NULL)
#define DEFAULT_SUCCESSFACTOR
SCIP_Longint ncalls
#define HEUR_TIMING
return SCIP_OKAY
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, SCIP_Real oldactivity, SCIP_Real newactivity)
#define HEUR_FREQOFS
int c
#define HEUR_DESC
SCIP_ROW ** violrows
#define DEFAULT_ONCEPERNODE
int nfrac
SCIP_ROW ** lprows
static SCIP_SOL * sol
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
SCIP_Real * lpcandssol
SCIPfreeSol(scip, &heurdata->sol))
static SCIP_RETCODE selectIncreaseRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
int * violrowpos
SCIP_Real bestroundval
#define HEUR_NAME
SCIP_VAR ** lpcands
int nlpcands
SCIP_Longint nlps
static SCIP_RETCODE selectDecreaseRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
SCIP_Real * activities
static SCIP_RETCODE selectRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, int direction, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
int r
int nviolrows
#define HEUR_FREQ
SCIP_Real minobj
SCIP_Real obj
#define HEUR_USESSUBSCIP
assert(minobj< SCIPgetCutoffbound(scip))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPlinkLPSol(scip, sol))
SCIP_Longint nnodes
LP rounding heuristic that tries to recover from intermediate infeasibilities.
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
public methods for primal heuristics
public methods for LP management
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
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 solutions
public methods for querying solving statistics
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:131
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:112
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:120
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:104
#define SCIP_DECL_HEUREXITSOL(x)
Definition type_heur.h:142
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ 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
#define SCIP_HEURTIMING_AFTERLPNODE
Definition type_timing.h:81
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97
enum SCIP_Vartype SCIP_VARTYPE
Definition type_var.h:73