SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_intshifting.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-2025 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_intshifting.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variables, and
28 * solves a final LP to calculate feasible values for continuous variables
29 * @author Tobias Achterberg
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
36#include "scip/pub_heur.h"
37#include "scip/pub_lp.h"
38#include "scip/pub_message.h"
39#include "scip/pub_misc.h"
40#include "scip/pub_var.h"
41#include "scip/scip_branch.h"
42#include "scip/scip_general.h"
43#include "scip/scip_heur.h"
44#include "scip/scip_lp.h"
45#include "scip/scip_mem.h"
46#include "scip/scip_message.h"
47#include "scip/scip_numerics.h"
48#include "scip/scip_prob.h"
50#include "scip/scip_sol.h"
52#include <string.h>
53
54#define HEUR_NAME "intshifting"
55#define HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving"
56#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
57#define HEUR_PRIORITY -10000
58#define HEUR_FREQ 10
59#define HEUR_FREQOFS 0
60#define HEUR_MAXDEPTH -1
61#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
62#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
63
64#define MAXSHIFTINGS 50 /**< maximal number of non improving shiftings */
65#define WEIGHTFACTOR 1.1
66#define DEFAULT_RANDSEED 17
67
68/* locally defined heuristic data */
69struct SCIP_HeurData
70{
71 SCIP_SOL* sol; /**< working solution */
72 SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
73 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
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 int* nviolfracrows, /**< pointer to the number of violated rows with fractional candidates */
90 int* nfracsinrow, /**< array with number of fractional variables for every row */
91 SCIP_Real oldminactivity, /**< old minimal activity value of LP row */
92 SCIP_Real oldmaxactivity, /**< old maximal activity value of LP row */
93 SCIP_Real newminactivity, /**< new minimal activity value of LP row */
94 SCIP_Real newmaxactivity /**< new maximal activity value of LP row */
95 )
96{
97 SCIP_Real lhs;
98 SCIP_Real rhs;
99 SCIP_Bool oldviol;
100 SCIP_Bool newviol;
101
102 assert(violrows != NULL);
105
106 lhs = SCIProwGetLhs(row);
107 rhs = SCIProwGetRhs(row);
108
109 /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */
110 if( ! (SCIPisInfinity(scip, oldmaxactivity) || SCIPisInfinity(scip, -oldmaxactivity)
111 || SCIPisInfinity(scip, oldminactivity) || SCIPisInfinity(scip, -oldminactivity)) )
112 {
113 oldviol = (SCIPisFeasLT(scip, oldmaxactivity, lhs) || SCIPisFeasGT(scip, oldminactivity, rhs));
114 }
115 else
116 {
117 oldviol = (SCIPisInfinity(scip, -oldmaxactivity) && !SCIPisInfinity(scip, -lhs)) ||
118 (SCIPisInfinity(scip, oldminactivity) && !SCIPisInfinity(scip, rhs));
119 }
120
121 /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */
122 if( ! (SCIPisInfinity(scip, newmaxactivity) || SCIPisInfinity(scip, -newmaxactivity)
123 || SCIPisInfinity(scip, newminactivity) || SCIPisInfinity(scip, -newminactivity)) )
124 {
125 newviol = (SCIPisFeasLT(scip, newmaxactivity, lhs) || SCIPisFeasGT(scip, newminactivity, rhs));
126 }
127 else
128 {
129 newviol = (SCIPisInfinity(scip, -newmaxactivity) && !SCIPisInfinity(scip, -lhs)) ||
130 (SCIPisInfinity(scip, newminactivity) && !SCIPisInfinity(scip, rhs));
131 }
132
133 if( oldviol != newviol )
134 {
135 int rowpos;
136 int violpos;
137
138 rowpos = SCIProwGetLPPos(row);
139 assert(rowpos >= 0);
140
141 if( oldviol )
142 {
143 /* the row violation was repaired: remove row from violrows array, decrease violation count */
144 violpos = violrowpos[rowpos];
145 assert(0 <= violpos && violpos < *nviolrows);
146 assert(violrows[violpos] == row);
147 violrowpos[rowpos] = -1;
148 /* first, move the row to the end of the subset of violated rows with fractional variables */
149 if( nfracsinrow[rowpos] > 0 )
150 {
151 violrows[violpos] = violrows[*nviolrows-1];
152 assert(violpos < *nviolfracrows);
153
154 /* replace with last violated row containing fractional variables */
155 if( violpos != *nviolfracrows - 1 )
156 {
157 violrows[violpos] = violrows[*nviolfracrows - 1];
158 violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
159 violpos = *nviolfracrows - 1;
160 }
161 (*nviolfracrows)--;
162 }
163
164 assert(violpos >= *nviolfracrows);
165
166 /* swap row at the end of the violated array to the position of this row and decrease the counter */
167 if( violpos != *nviolrows - 1 )
168 {
169 violrows[violpos] = violrows[*nviolrows - 1];
170 violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
171 }
172 (*nviolrows)--;
173 }
174 else
175 {
176 /* the row is now violated: add row to violrows array, increase violation count */
177 assert(violrowpos[rowpos] == -1);
178 violrows[*nviolrows] = row;
179 violrowpos[rowpos] = *nviolrows;
180 (*nviolrows)++;
181
182 /* if the row contains fractional variables, swap with the last violated row that has no fractional variables
183 * at position *nviolfracrows
184 */
185 if( nfracsinrow[rowpos] > 0 )
186 {
187 if( *nviolfracrows < *nviolrows - 1 )
188 {
190
193
194 violrows[*nviolfracrows] = row;
195 violrowpos[rowpos] = *nviolfracrows;
196 }
197 (*nviolfracrows)++;
198 }
199 }
200 }
201}
202
203/** update row activities after a variable's solution value changed */
204static
206 SCIP* scip, /**< SCIP data structure */
207 SCIP_Real* minactivities, /**< LP row minimal activities */
208 SCIP_Real* maxactivities, /**< LP row maximal activities */
209 SCIP_ROW** violrows, /**< array with currently violated rows */
210 int* violrowpos, /**< position of LP rows in violrows array */
211 int* nviolrows, /**< pointer to the number of currently violated rows */
212 int* nviolfracrows, /**< pointer to the number of violated rows with fractional candidates */
213 int* nfracsinrow, /**< array with number of fractional variables for every row */
214 int nlprows, /**< number of rows in current LP */
215 SCIP_VAR* var, /**< variable that has been changed */
216 SCIP_Real oldsolval, /**< old solution value of variable */
217 SCIP_Real newsolval /**< new solution value of variable */
218 )
219{
220 SCIP_COL* col;
221 SCIP_ROW** colrows;
222 SCIP_Real* colvals;
223 SCIP_Real delta;
224 int ncolrows;
225 int r;
226
230 assert(0 <= *nviolrows && *nviolrows <= nlprows);
232
233 delta = newsolval - oldsolval;
234 col = SCIPvarGetCol(var);
235 colrows = SCIPcolGetRows(col);
236 colvals = SCIPcolGetVals(col);
237 ncolrows = SCIPcolGetNLPNonz(col);
238 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
239
240 for( r = 0; r < ncolrows; ++r )
241 {
242 SCIP_ROW* row;
243 int rowpos;
244
245 row = colrows[r];
246 rowpos = SCIProwGetLPPos(row);
247 assert(-1 <= rowpos && rowpos < nlprows);
248
249 if( rowpos >= 0 && !SCIProwIsLocal(row) )
250 {
251 SCIP_Real oldminactivity;
252 SCIP_Real oldmaxactivity;
253 SCIP_Real newminactivity;
254 SCIP_Real newmaxactivity;
255
256 assert(SCIProwIsInLP(row));
257
258 /* update row activities */
259 oldminactivity = minactivities[rowpos];
260 oldmaxactivity = maxactivities[rowpos];
261
262 if( !SCIPisInfinity(scip, -oldminactivity) )
263 {
264 newminactivity = oldminactivity + delta * colvals[r];
265 minactivities[rowpos] = newminactivity;
266 }
267 else
268 newminactivity = -SCIPinfinity(scip);
269 if( !SCIPisInfinity(scip, oldmaxactivity) )
270 {
271 newmaxactivity = oldmaxactivity + delta * colvals[r];
272 maxactivities[rowpos] = newmaxactivity;
273 }
274 else
275 newmaxactivity = SCIPinfinity(scip);
276
277 /* update row violation arrays */
278 updateViolations(scip, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldminactivity, oldmaxactivity,
279 newminactivity, newmaxactivity);
280 }
281 }
282
283 return SCIP_OKAY;
284}
285
286/** returns an integer variable, that pushes activity of the row in the given direction with minimal negative impact on
287 * other rows;
288 * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
289 * prefer fractional integers over other variables in order to become integral during the process;
290 * shifting in a direction is forbidden, if this forces the objective value over the upper bound, or if the variable
291 * was already shifted in the opposite direction
292 */
293static
295 SCIP* scip, /**< SCIP data structure */
296 SCIP_SOL* sol, /**< primal solution */
297 SCIP_ROW* row, /**< LP row */
298 SCIP_Real rowactivity, /**< activity of LP row */
299 int direction, /**< should the activity be increased (+1) or decreased (-1)? */
300 SCIP_Real* nincreases, /**< array with weighted number of increasings per variables */
301 SCIP_Real* ndecreases, /**< array with weighted number of decreasings per variables */
302 SCIP_Real increaseweight, /**< current weight of increase/decrease updates */
303 SCIP_VAR** shiftvar, /**< pointer to store the shifting variable, returns NULL if impossible */
304 SCIP_Real* oldsolval, /**< pointer to store old solution value of shifting variable */
305 SCIP_Real* newsolval /**< pointer to store new (shifted) solution value of shifting variable */
306 )
307{
308 SCIP_COL** rowcols;
309 SCIP_Real* rowvals;
310 int nrowcols;
311 SCIP_Real activitydelta;
312 SCIP_Real bestshiftscore;
313 SCIP_Real bestdeltaobj;
314 int c;
315
316 assert(direction == +1 || direction == -1);
319 assert(shiftvar != NULL);
320 assert(oldsolval != NULL);
321 assert(newsolval != NULL);
322
323 /* get row entries */
324 rowcols = SCIProwGetCols(row);
325 rowvals = SCIProwGetVals(row);
326 nrowcols = SCIProwGetNLPNonz(row);
327
328 /* calculate how much the activity must be shifted in order to become feasible */
329 activitydelta = (direction == +1 ? SCIProwGetLhs(row) - rowactivity : SCIProwGetRhs(row) - rowactivity);
330 assert((direction == +1 && SCIPisPositive(scip, activitydelta))
331 || (direction == -1 && SCIPisNegative(scip, activitydelta)));
332
333 /* select shifting variable */
334 bestshiftscore = SCIP_REAL_MAX;
335 bestdeltaobj = SCIPinfinity(scip);
336 *shiftvar = NULL;
337 *newsolval = 0.0;
338 *oldsolval = 0.0;
339 for( c = 0; c < nrowcols; ++c )
340 {
341 SCIP_COL* col;
342 SCIP_VAR* var;
343 SCIP_Real val;
344 SCIP_Real solval;
345 SCIP_Real shiftval;
346 SCIP_Real shiftscore;
347 SCIP_Bool isfrac;
348 SCIP_Bool increase;
349 int probindex;
350
351 col = rowcols[c];
352 var = SCIPcolGetVar(col);
353 val = rowvals[c];
354 assert(!SCIPisZero(scip, val));
355 solval = SCIPgetSolVal(scip, sol, var);
356
357 /* only accept integer variables */
359 continue;
360
361 isfrac = !SCIPisFeasIntegral(scip, solval);
362 increase = (direction * val > 0.0);
363 probindex = SCIPvarGetProbindex(var);
364
365 /* calculate the score of the shifting (prefer smaller values) */
366 if( isfrac )
367 shiftscore = increase ? -1.0 / (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) + 1.0) :
369 else
370 {
371 if( increase )
372 shiftscore = ndecreases[probindex]/increaseweight;
373 else
374 shiftscore = nincreases[probindex]/increaseweight;
375 shiftscore += 1.0;
376 }
377
378 if( shiftscore <= bestshiftscore )
379 {
380 SCIP_Real deltaobj;
381
382 if( !increase )
383 {
384 /* shifting down */
385 assert(direction * val < 0.0);
386 if( isfrac )
387 shiftval = SCIPfeasFloor(scip, solval);
388 else
389 {
390 SCIP_Real lb;
391
392 assert(activitydelta/val < 0.0);
393 shiftval = solval + activitydelta/val;
394 assert(shiftval <= solval); /* may be equal due to numerical digit erasement in the subtraction */
395 shiftval = SCIPfeasFloor(scip, shiftval);
397 shiftval = MAX(shiftval, lb);
398 }
399 }
400 else
401 {
402 /* shifting up */
403 assert(direction * val > 0.0);
404 if( isfrac )
405 shiftval = SCIPfeasCeil(scip, solval);
406 else
407 {
408 SCIP_Real ub;
409
410 assert(activitydelta/val > 0.0);
411 shiftval = solval + activitydelta/val;
412 assert(shiftval >= solval); /* may be equal due to numerical digit erasement in the subtraction */
413 shiftval = SCIPfeasCeil(scip, shiftval);
415 shiftval = MIN(shiftval, ub);
416 }
417 }
418
419 if( SCIPisEQ(scip, shiftval, solval) )
420 continue;
421
422 deltaobj = SCIPvarGetObj(var) * (shiftval - solval);
423 if( (shiftscore < bestshiftscore || deltaobj < bestdeltaobj)
424 && !SCIPisHugeValue(scip, REALABS(shiftval)) ) /* ignore candidates for which shiftval is too large */
425 {
426 bestshiftscore = shiftscore;
427 bestdeltaobj = deltaobj;
428 *shiftvar = var;
429 *oldsolval = solval;
430 *newsolval = shiftval;
431 }
432 }
433 }
434
435 return SCIP_OKAY;
436}
437
438/** returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to
439 * fix in the other direction;
440 * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
441 * shifting in a direction is forbidden, if this forces the objective value over the upper bound
442 */
443static
445 SCIP* scip, /**< SCIP data structure */
446 SCIP_SOL* sol, /**< primal solution */
447 SCIP_Real minobj, /**< minimal objective value possible after shifting remaining fractional vars */
448 SCIP_VAR** lpcands, /**< fractional variables in LP */
449 int nlpcands, /**< number of fractional variables in LP */
450 SCIP_VAR** shiftvar, /**< pointer to store the shifting variable, returns NULL if impossible */
451 SCIP_Real* oldsolval, /**< old (fractional) solution value of shifting variable */
452 SCIP_Real* newsolval /**< new (shifted) solution value of shifting variable */
453 )
454{
455 SCIP_VAR* var;
456 SCIP_Real solval;
457 SCIP_Real shiftval;
459 SCIP_Real deltaobj;
460 SCIP_Real bestdeltaobj;
461 int maxnlocks;
462 int nlocks;
463 int v;
464
465 assert(shiftvar != NULL);
466 assert(oldsolval != NULL);
467 assert(newsolval != NULL);
468
469 /* select shifting variable */
470 maxnlocks = -1;
471 bestdeltaobj = SCIPinfinity(scip);
472 *shiftvar = NULL;
473 for( v = 0; v < nlpcands; ++v )
474 {
475 var = lpcands[v];
477
478 solval = SCIPgetSolVal(scip, sol, var);
479 if( !SCIPisFeasIntegral(scip, solval) )
480 {
482
483 /* shifting down */
485 if( nlocks >= maxnlocks )
486 {
487 shiftval = SCIPfeasFloor(scip, solval);
488 deltaobj = obj * (shiftval - solval);
489 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
490 {
491 maxnlocks = nlocks;
492 bestdeltaobj = deltaobj;
493 *shiftvar = var;
494 *oldsolval = solval;
495 *newsolval = shiftval;
496 }
497 }
498
499 /* shifting up */
501 if( nlocks >= maxnlocks )
502 {
503 shiftval = SCIPfeasCeil(scip, solval);
504 deltaobj = obj * (shiftval - solval);
505 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
506 {
507 maxnlocks = nlocks;
508 bestdeltaobj = deltaobj;
509 *shiftvar = var;
510 *oldsolval = solval;
511 *newsolval = shiftval;
512 }
513 }
514 }
515 }
516
517 return SCIP_OKAY;
518}
519
520/** adds a given value to the fractionality counters of the rows in which the given variable appears */
521static
523 int* nfracsinrow, /**< array to store number of fractional variables per row */
524 SCIP_ROW** violrows, /**< array with currently violated rows */
525 int* violrowpos, /**< position of LP rows in violrows array */
526 int* nviolfracrows, /**< pointer to store the number of violated rows with fractional variables */
527 int nviolrows, /**< the number of currently violated rows (stays unchanged in this method) */
528 int nlprows, /**< number of rows in LP */
529 SCIP_VAR* var, /**< variable for which the counting should be updated */
530 int incval /**< value that should be added to the corresponding array entries */
531 )
532{
533 SCIP_COL* col;
534 SCIP_ROW** rows;
535 int nrows;
536 int r;
537
538 assert(incval != 0);
540
541 col = SCIPvarGetCol(var);
542 rows = SCIPcolGetRows(col);
543 nrows = SCIPcolGetNLPNonz(col);
544 for( r = 0; r < nrows; ++r )
545 {
546 int rowlppos;
547 int theviolrowpos;
548 SCIP_ROW* row;
549
550 row = rows[r];
551 assert(NULL != row);
552 rowlppos = SCIProwGetLPPos(row);
553 assert(0 <= rowlppos && rowlppos < nlprows);
554 assert(!SCIProwIsLocal(row) || violrowpos[rowlppos] == -1);
555
556 if( SCIProwIsLocal(row) )
557 continue;
558
559 nfracsinrow[rowlppos] += incval;
560 assert(nfracsinrow[rowlppos] >= 0);
561
562 theviolrowpos = violrowpos[rowlppos];
563
564 /* swap positions in violrows array if fractionality has changed to 0 */
565 if( theviolrowpos >= 0 )
566 {
567 /* first case: the number of fractional variables has become zero: swap row in violrows array to the
568 * second part, containing only violated rows without fractional variables
569 */
570 if( nfracsinrow[rowlppos] == 0 )
571 {
572 assert(theviolrowpos <= *nviolfracrows - 1);
573
574 /* nothing to do if row is already at the end of the first part, otherwise, swap it to the last position
575 * and decrease the counter */
576 if( theviolrowpos < *nviolfracrows - 1 )
577 {
578 violrows[theviolrowpos] = violrows[*nviolfracrows - 1];
579 violrows[*nviolfracrows - 1] = row;
580
581 violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos;
582 violrowpos[rowlppos] = *nviolfracrows - 1;
583 }
584 (*nviolfracrows)--;
585 }
586 /* second interesting case: the number of fractional variables was zero before, swap it with the first
587 * violated row without fractional variables
588 */
589 else if( nfracsinrow[rowlppos] == incval )
590 {
591 assert(theviolrowpos >= *nviolfracrows);
592
593 /* nothing to do if the row is exactly located at index *nviolfracrows */
594 if( theviolrowpos > *nviolfracrows )
595 {
596 violrows[theviolrowpos] = violrows[*nviolfracrows];
597 violrows[*nviolfracrows] = row;
598
599 violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos;
600 violrowpos[rowlppos] = *nviolfracrows;
601 }
602 (*nviolfracrows)++;
603 }
604 }
605 }
606}
607
608
609/*
610 * Callback methods
611 */
612
613/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
614static
615SCIP_DECL_HEURCOPY(heurCopyIntshifting)
616{ /*lint --e{715}*/
617 assert(scip != NULL);
618 assert(heur != NULL);
619 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
620
621 /* call inclusion method of primal heuristic */
623
624 return SCIP_OKAY;
625}
626
627
628/** initialization method of primal heuristic (called after problem was transformed) */
629static
630SCIP_DECL_HEURINIT(heurInitIntshifting) /*lint --e{715}*/
631{ /*lint --e{715}*/
633
634 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
636
637 /* create heuristic data */
640 heurdata->lastlp = -1;
642
643 /* create random number generator */
646
647 return SCIP_OKAY;
648}
649
650/** deinitialization method of primal heuristic (called before transformed problem is freed) */
651static
652SCIP_DECL_HEUREXIT(heurExitIntshifting) /*lint --e{715}*/
653{ /*lint --e{715}*/
655
656 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
657
658 /* free heuristic data */
662
663 /* free random number generator */
665
668
669 return SCIP_OKAY;
670}
671
672/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
673static
674SCIP_DECL_HEURINITSOL(heurInitsolIntshifting)
675{
677
678 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
679
681 assert(heurdata != NULL);
682 heurdata->lastlp = -1;
683
684 return SCIP_OKAY;
685}
686
687
688/** execution method of primal heuristic */
689static
690SCIP_DECL_HEUREXEC(heurExecIntshifting) /*lint --e{715}*/
691{ /*lint --e{715}*/
710 int nvars;
711 int nfrac;
717 int c;
718 int r;
723
724 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
728
730
731 /* do not call heuristic of node was already detected to be infeasible */
732 if( nodeinfeasible )
733 return SCIP_OKAY;
734
735 /* don't call heuristic, if no continuous variables are present
736 * -> in this case, it is equivalent to shifting heuristic
737 */
738 if( SCIPgetNContVars(scip) == 0 )
739 return SCIP_OKAY;
740
741 /* only call heuristic, if an optimal LP solution is at hand */
743 return SCIP_OKAY;
744
745 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
747 return SCIP_OKAY;
748
749 /* get heuristic data */
751 assert(heurdata != NULL);
752
753 /* don't call heuristic, if we have already processed the current LP solution */
755 if( nlps == heurdata->lastlp )
756 return SCIP_OKAY;
757 heurdata->lastlp = nlps;
758
759 /* don't call heuristic, if it was not successful enough in the past */
763 if( nnodes % (ncalls/(nsolsfound+1)+1) != 0 ) /*?????????? ncalls/100 */
764 return SCIP_OKAY;
765
766 /* get fractional variables, that should be integral */
767 /* todo check if heuristic should include implicit integer variables for its calculations */
769 nfrac = nlpcands;
770
771 /* only call heuristic, if LP solution is fractional */
772 if( nfrac == 0 )
773 return SCIP_OKAY;
774
776
777 /* get LP rows */
779
780 SCIPdebugMsg(scip, "executing intshifting heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
781
782 /* get memory for activities, violated rows, and row violation positions */
794
795 /* get the minimal and maximal activity for all globally valid rows for continuous variables in their full range;
796 * these are the values of a*x' with x' being the LP solution for integer variables and the lower or upper bound
797 * for the continuous variables
798 */
799 nviolrows = 0;
800 for( r = 0; r < nlprows; ++r )
801 {
802 SCIP_ROW* row;
803
804 row = lprows[r];
805 assert(SCIProwGetLPPos(row) == r);
806
807 if( !SCIProwIsLocal(row) )
808 {
809 SCIP_COL** cols;
810 SCIP_Real* vals;
811 int nnonz;
812 SCIP_Bool mininf;
813 SCIP_Bool maxinf;
814
815 mininf = FALSE;
816 maxinf = FALSE;
817 minactivities[r] = 0.0;
818 maxactivities[r] = 0.0;
819 cols = SCIProwGetCols(row);
820 vals = SCIProwGetVals(row);
821 nnonz = SCIProwGetNNonz(row);
822 for( c = 0; c < nnonz && !(mininf && maxinf); ++c )
823 {
824 SCIP_VAR* var;
825
826 var = SCIPcolGetVar(cols[c]);
828 {
829 SCIP_Real act;
830
831 act = vals[c] * SCIPcolGetPrimsol(cols[c]);
832 minactivities[r] += act;
833 maxactivities[r] += act;
834 }
835 else if( vals[c] > 0.0 )
836 {
837 SCIP_Real lb;
838 SCIP_Real ub;
839
842 if( SCIPisInfinity(scip, -lb) )
843 mininf = TRUE;
844 else
845 minactivities[r] += vals[c] * lb;
846 if( SCIPisInfinity(scip, ub) )
847 maxinf = TRUE;
848 else
849 maxactivities[r] += vals[c] * ub;
850 }
851 else if( vals[c] < 0.0 )
852 {
853 SCIP_Real lb;
854 SCIP_Real ub;
855
858 if( SCIPisInfinity(scip, ub) )
859 mininf = TRUE;
860 else
861 minactivities[r] += vals[c] * ub;
862 if( SCIPisInfinity(scip, -lb) )
863 maxinf = TRUE;
864 else
865 maxactivities[r] += vals[c] * lb;
866 }
867
868 if( mininf )
870 if( maxinf )
872 }
873
876 {
877 violrows[nviolrows] = row;
879 nviolrows++;
880 }
881 else
882 violrowpos[r] = -1;
883 }
884 else
885 /* if row is a local row */
886 violrowpos[r] = -1;
887 }
888
889 nviolfracrows = 0;
890 /* calc the current number of fractional variables in rows */
891 for( c = 0; c < nlpcands; ++c )
893
894 /* get the working solution from heuristic's local data */
895 sol = heurdata->sol;
897
898 /* copy the current LP solution to the working solution */
900
901 /* calculate the minimal objective value possible after rounding fractional variables */
904 for( c = 0; c < nlpcands; ++c )
905 {
909 }
910
911 /* try to shift remaining variables in order to become/stay feasible */
913 minnviolrows = INT_MAX;
914 increaseweight = 1.0;
916 {
917 SCIP_VAR* shiftvar;
918 SCIP_Real oldsolval;
919 SCIP_Real newsolval;
920 SCIP_Bool oldsolvalisfrac;
921 int probindex;
922
923 SCIPdebugMsg(scip, "intshifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n",
926
928
929 /* choose next variable to process:
930 * - if a violated row exists, shift a variable decreasing the violation, that has least impact on other rows
931 * - otherwise, shift a variable, that has strongest devastating impact on rows in opposite direction
932 */
933 shiftvar = NULL;
934 oldsolval = 0.0;
935 newsolval = 0.0;
936 if( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts < MAXSHIFTINGS-1) )
937 {
938 SCIP_ROW* row;
939 int rowidx;
940 int rowpos;
941 int direction;
942
943 assert(nviolfracrows == 0 || nfrac > 0);
944 /* violated rows containing fractional variables are preferred; if such a row exists, choose the last one from the list
945 * (at position nviolfracrows - 1) because removing this row will cause one swapping operation less than other rows
946 */
947 if( nviolfracrows > 0 )
948 rowidx = nviolfracrows - 1;
949 else
950 rowidx = SCIPrandomGetInt(heurdata->randnumgen, 0, nviolrows-1);
951
952 assert(0 <= rowidx && rowidx < nviolrows);
953 row = violrows[rowidx];
954 rowpos = SCIProwGetLPPos(row);
955 assert(0 <= rowpos && rowpos < nlprows);
956 assert(violrowpos[rowpos] == rowidx);
957 assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1);
958
959 SCIPdebugMsg(scip, "intshifting heuristic: try to fix violated row <%s>: %g <= [%g,%g] <= %g\n",
960 SCIProwGetName(row), SCIProwGetLhs(row), minactivities[rowpos], maxactivities[rowpos], SCIProwGetRhs(row));
962
963 /* get direction in which activity must be shifted */
965 || SCIPisFeasGT(scip, minactivities[rowpos], SCIProwGetRhs(row)));
966 direction = SCIPisFeasLT(scip, maxactivities[rowpos], SCIProwGetLhs(row)) ? +1 : -1;
967
968 /* search an integer variable that can shift the activity in the necessary direction */
969 SCIP_CALL( selectShifting(scip, sol, row, direction == +1 ? maxactivities[rowpos] : minactivities[rowpos],
970 direction, nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) );
971 }
972
973 if( shiftvar == NULL && nfrac > 0 )
974 {
975 SCIPdebugMsg(scip, "intshifting heuristic: search rounding variable and try to stay feasible\n");
976 SCIP_CALL( selectEssentialRounding(scip, sol, minobj, lpcands, nlpcands, &shiftvar, &oldsolval, &newsolval) );
977 }
978
979 /* check, whether shifting was possible */
980 if( shiftvar == NULL || SCIPisEQ(scip, oldsolval, newsolval) )
981 {
982 SCIPdebugMsg(scip, "intshifting heuristic: -> didn't find a shifting variable\n");
983 break;
984 }
985
987
988 SCIPdebugMsg(scip, "intshifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n",
989 SCIPvarGetName(shiftvar), SCIPvarGetLbGlobal(shiftvar), SCIPvarGetUbGlobal(shiftvar), SCIPvarGetType(shiftvar),
990 oldsolval, newsolval, SCIPvarGetObj(shiftvar));
991
992 /* update row activities of globally valid rows */
994 nfracsinrow, nlprows, shiftvar, oldsolval, newsolval) );
995
996 if( nviolrows >= nprevviolrows )
998 else if( nviolrows < minnviolrows )
999 {
1002 }
1003
1004 /* store new solution value and decrease fractionality counter */
1005 SCIP_CALL( SCIPsetSolVal(scip, sol, shiftvar, newsolval) );
1006
1007 /* update fractionality counter and minimal objective value possible after shifting remaining variables */
1008 oldsolvalisfrac = !SCIPisFeasIntegral(scip, oldsolval);
1009 obj = SCIPvarGetObj(shiftvar);
1010 if( oldsolvalisfrac )
1011 {
1012 assert(SCIPisFeasIntegral(scip, newsolval));
1013 nfrac--;
1015 minnviolrows = INT_MAX;
1017
1018 /* the rounding was already calculated into the minobj -> update only if rounding in "wrong" direction */
1019 if( obj > 0.0 && newsolval > oldsolval )
1020 minobj += obj;
1021 else if( obj < 0.0 && newsolval < oldsolval )
1022 minobj -= obj;
1023 }
1024 else
1025 {
1026 /* update minimal possible objective value */
1027 minobj += obj * (newsolval - oldsolval);
1028 }
1029
1030 /* update increase/decrease arrays */
1031 if( !oldsolvalisfrac )
1032 {
1033 probindex = SCIPvarGetProbindex(shiftvar);
1034 assert(0 <= probindex && probindex < nvars);
1036 if( newsolval < oldsolval )
1037 ndecreases[probindex] += increaseweight;
1038 else
1039 nincreases[probindex] += increaseweight;
1040 if( increaseweight >= 1e+09 )
1041 {
1042 int i;
1043
1044 for( i = 0; i < nvars; ++i )
1045 {
1048 }
1049 increaseweight = 1.0;
1050 }
1051 }
1052
1053 SCIPdebugMsg(scip, "intshifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
1055 }
1056
1057 /* check, if the new solution is potentially feasible and solve the LP to calculate values for the continuous
1058 * variables
1059 */
1060 if( nfrac == 0 && nviolrows == 0 )
1061 {
1062 SCIP_VAR** vars;
1064 int nintvars;
1065 int v;
1066#ifdef NDEBUG
1067 SCIP_RETCODE retstat;
1068#endif
1069
1070 SCIPdebugMsg(scip, "shifted solution is potentially feasible -> solve LP to fix continuous variables\n");
1071
1072 /* start diving to calculate the LP relaxation */
1074
1075 /* set the bounds of the variables: fixed for integers, global bounds for continuous */
1078 for( v = 0; v < nvars; ++v )
1079 {
1081 {
1084 }
1085 }
1086 for( v = 0; v < nintvars; ++v ) /* apply this after global bounds to not cause an error with intermediate empty domains */
1087 {
1089 {
1090 SCIP_Real solval;
1091 solval = SCIPgetSolVal(scip, sol, vars[v]);
1092 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) );
1093 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) );
1094 }
1095 }
1096
1097 /* solve LP */
1098 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1099
1100 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1101 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1102 */
1103#ifdef NDEBUG
1104 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
1105 if( retstat != SCIP_OKAY )
1106 {
1107 SCIPwarningMessage(scip, "Error while solving LP in Intshifting heuristic; LP solve terminated with code <%d>\n",retstat);
1108 }
1109#else
1111#endif
1112
1113 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1114 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
1115
1116 /* check if this is a feasible solution */
1118 {
1119 SCIP_Bool stored;
1120
1121 /* copy the current LP solution to the working solution */
1123
1124 /* check solution for feasibility, and add it to solution store if possible
1125 * neither integrality nor feasibility of LP rows has to be checked, because this is already
1126 * done in the intshifting heuristic itself and due to the LP resolve
1127 */
1128 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
1129
1130 if( stored )
1131 {
1132 SCIPdebugMsg(scip, "found feasible shifted solution:\n");
1135 }
1136 }
1137
1138 /* terminate the diving */
1140 }
1141
1142 /* free memory buffers */
1150
1151 return SCIP_OKAY;
1152}
1153
1154
1155/*
1156 * heuristic specific interface methods
1157 */
1158
1159/** creates the intshifting heuristic with infeasibility recovering and includes it in SCIP */
1161 SCIP* scip /**< SCIP data structure */
1162 )
1163{
1164 SCIP_HEUR* heur;
1165
1166 /* include primal heuristic */
1169 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntshifting, NULL) );
1170
1171 assert(heur != NULL);
1172
1173 /* set non-NULL pointers to callback methods */
1174 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntshifting) );
1175 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntshifting) );
1176 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntshifting) );
1177 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolIntshifting) );
1178
1179 return SCIP_OKAY;
1180}
#define DEFAULT_RANDSEED
#define NULL
Definition def.h:266
#define SCIP_Longint
Definition def.h:157
#define SCIP_REAL_MAX
Definition def.h:173
#define SCIP_Bool
Definition def.h:91
#define MIN(x, y)
Definition def.h:242
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:238
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define REALABS(x)
Definition def.h:196
#define SCIP_CALL(x)
Definition def.h:373
#define nnodes
Definition gastrans.c:74
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNContVars(SCIP *scip)
Definition scip_prob.c:2172
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
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPincludeHeurIntshifting(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
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition lp.c:16996
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition lp.c:17140
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_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition heur.c:1589
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
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:1453
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_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
int SCIProwGetNNonz(SCIP_ROW *row)
Definition lp.c:17213
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
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 * 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:1627
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_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1296
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
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1428
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(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 SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17809
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17558
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17946
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17604
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18108
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17788
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17439
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18098
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10111
#define HEUR_TIMING
return SCIP_OKAY
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
SCIP_Longint nsolsfound
SCIP_Bool lperror
SCIP_Longint ncalls
int c
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
static SCIP_RETCODE selectEssentialRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
SCIP_Real * nincreases
int nlprows
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldminactivity, SCIP_Real oldmaxactivity, SCIP_Real newminactivity, SCIP_Real newmaxactivity)
static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)
SCIP_Real * maxactivities
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *minactivities, SCIP_Real *maxactivities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
heurdata lastlp
int nfrac
int nviolrows
SCIP_ROW ** lprows
static SCIP_SOL * sol
SCIP_Real * lpcandssol
SCIPfreeSol(scip, &heurdata->sol))
int * nfracsinrow
SCIP_Real bestshiftval
int * violrowpos
int nlpcands
SCIP_Longint nlps
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIP_Real * minactivities
int minnviolrows
int r
SCIP_Real minobj
SCIP_Real obj
SCIPheurSetData(heur, heurdata)
static SCIP_RETCODE selectShifting(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *row, SCIP_Real rowactivity, int direction, SCIP_Real *nincreases, SCIP_Real *ndecreases, SCIP_Real increaseweight, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
SCIP_VAR ** lpcands
assert(minobj< SCIPgetCutoffbound(scip))
int nprevviolrows
SCIP_ROW ** violrows
int nvars
SCIP_Real increaseweight
SCIP_Real * ndecreases
#define WEIGHTFACTOR
int nviolfracrows
SCIPcreateSol(scip, &heurdata->sol, heur))
int nnonimprovingshifts
#define MAXSHIFTINGS
SCIPlinkLPSol(scip, sol))
LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variabl...
SCIP_VAR * var
SCIPendDive(scip))
static SCIP_VAR ** vars
int nintvars
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
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
public methods for problem variables
public methods for branching rule plugins and branching
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 global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:132
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
struct SCIP_Heur SCIP_HEUR
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:121
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
struct SCIP_Row SCIP_ROW
Definition type_lp.h:104
struct SCIP_Col SCIP_COL
Definition type_lp.h:98
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
struct SCIP_RandNumGen SCIP_RANDNUMGEN
Definition type_misc.h:126
@ 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
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
struct SCIP_Var SCIP_VAR
Definition type_var.h:119
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97