Scippy

SCIP

Solving Constraint Integer Programs

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-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_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);
103 assert(violrowpos != NULL);
104 assert(nviolrows != 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 {
189 assert(nfracsinrow[SCIProwGetLPPos(violrows[*nviolfracrows])] == 0);
190
191 violrows[*nviolrows - 1] = violrows[*nviolfracrows];
192 violrowpos[SCIProwGetLPPos(violrows[*nviolrows - 1])] = *nviolrows - 1;
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
227 assert(minactivities != NULL);
228 assert(maxactivities != NULL);
229 assert(nviolrows != NULL);
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);
317 assert(nincreases != NULL);
318 assert(ndecreases != NULL);
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);
396 lb = SCIPvarGetLbGlobal(var);
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);
414 ub = SCIPvarGetUbGlobal(var);
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;
458 SCIP_Real obj;
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 {
481 obj = SCIPvarGetObj(var);
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);
539 assert(nviolrows >= *nviolfracrows);
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}*/
632 SCIP_HEURDATA* heurdata;
633
634 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
635 assert(SCIPheurGetData(heur) == NULL);
636
637 /* create heuristic data */
638 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
639 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
640 heurdata->lastlp = -1;
641 SCIPheurSetData(heur, heurdata);
642
643 /* create random number generator */
644 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
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}*/
654 SCIP_HEURDATA* heurdata;
655
656 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
657
658 /* free heuristic data */
659 heurdata = SCIPheurGetData(heur);
660 assert(heurdata != NULL);
661 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
662
663 /* free random number generator */
664 SCIPfreeRandom(scip, &heurdata->randnumgen);
665
666 SCIPfreeBlockMemory(scip, &heurdata);
667 SCIPheurSetData(heur, NULL);
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{
676 SCIP_HEURDATA* heurdata;
677
678 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
679
680 heurdata = SCIPheurGetData(heur);
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}*/
692 SCIP_HEURDATA* heurdata;
693 SCIP_SOL* sol;
694 SCIP_VAR** lpcands;
695 SCIP_Real* lpcandssol;
696 SCIP_ROW** lprows;
697 SCIP_Real* minactivities;
698 SCIP_Real* maxactivities;
699 SCIP_ROW** violrows;
700 SCIP_Real* nincreases;
701 SCIP_Real* ndecreases;
702 int* violrowpos;
703 int* nfracsinrow;
704 SCIP_Real increaseweight;
705 SCIP_Real obj;
706 SCIP_Real bestshiftval;
707 SCIP_Real minobj;
708 int nlpcands;
709 int nlprows;
710 int nvars;
711 int nfrac;
712 int nviolrows;
713 int nviolfracrows;
714 int nprevviolrows;
715 int minnviolrows;
716 int nnonimprovingshifts;
717 int c;
718 int r;
719 SCIP_Longint nlps;
720 SCIP_Longint ncalls;
721 SCIP_Longint nsolsfound;
723
724 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
725 assert(scip != NULL);
726 assert(result != NULL);
727 assert(SCIPhasCurrentNodeLP(scip));
728
729 *result = SCIP_DIDNOTRUN;
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 */
750 heurdata = SCIPheurGetData(heur);
751 assert(heurdata != NULL);
752
753 /* don't call heuristic, if we have already processed the current LP solution */
754 nlps = SCIPgetNLPs(scip);
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 */
760 ncalls = SCIPheurGetNCalls(heur);
761 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + SCIPheurGetNSolsFound(heur);
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 */
768 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
769 nfrac = nlpcands;
770
771 /* only call heuristic, if LP solution is fractional */
772 if( nfrac == 0 )
773 return SCIP_OKAY;
774
775 *result = SCIP_DIDNOTFIND;
776
777 /* get LP rows */
778 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
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 */
783 nvars = SCIPgetNVars(scip);
784 SCIP_CALL( SCIPallocBufferArray(scip, &minactivities, nlprows) );
785 SCIP_CALL( SCIPallocBufferArray(scip, &maxactivities, nlprows) );
786 SCIP_CALL( SCIPallocBufferArray(scip, &violrows, nlprows) );
787 SCIP_CALL( SCIPallocBufferArray(scip, &violrowpos, nlprows) );
788 SCIP_CALL( SCIPallocBufferArray(scip, &nfracsinrow, nlprows) );
789 SCIP_CALL( SCIPallocBufferArray(scip, &nincreases, nvars) );
790 SCIP_CALL( SCIPallocBufferArray(scip, &ndecreases, nvars) );
791 BMSclearMemoryArray(nfracsinrow, nlprows);
792 BMSclearMemoryArray(nincreases, nvars);
793 BMSclearMemoryArray(ndecreases, nvars);
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
840 lb = SCIPvarGetLbGlobal(var);
841 ub = SCIPvarGetUbGlobal(var);
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
856 lb = SCIPvarGetLbGlobal(var);
857 ub = SCIPvarGetUbGlobal(var);
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 )
869 minactivities[r] = -SCIPinfinity(scip);
870 if( maxinf )
871 maxactivities[r] = SCIPinfinity(scip);
872 }
873
874 if( SCIPisFeasLT(scip, maxactivities[r], SCIProwGetLhs(row))
875 || SCIPisFeasGT(scip, minactivities[r], SCIProwGetRhs(row)) )
876 {
877 violrows[nviolrows] = row;
878 violrowpos[r] = nviolrows;
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 )
892 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1);
893
894 /* get the working solution from heuristic's local data */
895 sol = heurdata->sol;
896 assert(sol != NULL);
897
898 /* copy the current LP solution to the working solution */
900
901 /* calculate the minimal objective value possible after rounding fractional variables */
902 minobj = SCIPgetSolTransObj(scip, sol);
903 assert(minobj < SCIPgetCutoffbound(scip));
904 for( c = 0; c < nlpcands; ++c )
905 {
906 obj = SCIPvarGetObj(lpcands[c]);
907 bestshiftval = obj > 0.0 ? SCIPfeasFloor(scip, lpcandssol[c]) : SCIPfeasCeil(scip, lpcandssol[c]);
908 minobj += obj * (bestshiftval - lpcandssol[c]);
909 }
910
911 /* try to shift remaining variables in order to become/stay feasible */
912 nnonimprovingshifts = 0;
913 minnviolrows = INT_MAX;
914 increaseweight = 1.0;
915 while( (nfrac > 0 || nviolrows > 0) && nnonimprovingshifts < MAXSHIFTINGS && !SCIPisStopped(scip) )
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",
924 nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj),
926
927 nprevviolrows = nviolrows;
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 */
964 assert(SCIPisFeasLT(scip, maxactivities[rowpos], SCIProwGetLhs(row))
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
986 assert(SCIPvarGetType(shiftvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(shiftvar) == SCIP_VARTYPE_INTEGER);
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 */
993 SCIP_CALL( updateActivities(scip, minactivities, maxactivities, violrows, violrowpos, &nviolrows, &nviolfracrows,
994 nfracsinrow, nlprows, shiftvar, oldsolval, newsolval) );
995
996 if( nviolrows >= nprevviolrows )
997 nnonimprovingshifts++;
998 else if( nviolrows < minnviolrows )
999 {
1000 minnviolrows = nviolrows;
1001 nnonimprovingshifts = 0;
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--;
1014 nnonimprovingshifts = 0;
1015 minnviolrows = INT_MAX;
1016 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1);
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);
1035 increaseweight *= WEIGHTFACTOR;
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 {
1046 nincreases[i] /= increaseweight;
1047 ndecreases[i] /= increaseweight;
1048 }
1049 increaseweight = 1.0;
1050 }
1051 }
1052
1053 SCIPdebugMsg(scip, "intshifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
1054 nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj));
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;
1063 SCIP_Bool lperror;
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 */
1076 vars = SCIPgetVars(scip);
1078 for( v = 0; v < nvars; ++v )
1079 {
1080 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
1081 {
1082 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) );
1083 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) );
1084 }
1085 }
1086 for( v = 0; v < nintvars; ++v ) /* apply this after global bounds to not cause an error with intermediate empty domains */
1087 {
1088 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
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
1110 SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
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 */
1117 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
1118 {
1119 SCIP_Bool stored;
1120
1121 /* copy the current LP solution to the working solution */
1122 SCIP_CALL( SCIPlinkLPSol(scip, sol) );
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");
1134 *result = SCIP_FOUNDSOL;
1135 }
1136 }
1137
1138 /* terminate the diving */
1140 }
1141
1142 /* free memory buffers */
1143 SCIPfreeBufferArray(scip, &ndecreases);
1144 SCIPfreeBufferArray(scip, &nincreases);
1145 SCIPfreeBufferArray(scip, &nfracsinrow);
1146 SCIPfreeBufferArray(scip, &violrowpos);
1147 SCIPfreeBufferArray(scip, &violrows);
1148 SCIPfreeBufferArray(scip, &maxactivities);
1149 SCIPfreeBufferArray(scip, &minactivities);
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}
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
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
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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)
Definition: scip_branch.c:395
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_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_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1589
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
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_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 SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
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 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 SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
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:17789
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
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
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
static SCIP_DECL_HEUREXIT(heurExitIntshifting)
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)
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)
#define HEUR_TIMING
static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)
#define HEUR_FREQOFS
#define HEUR_DESC
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)
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
static SCIP_DECL_HEUREXEC(heurExecIntshifting)
#define HEUR_NAME
static SCIP_DECL_HEURINIT(heurInitIntshifting)
#define DEFAULT_RANDSEED
static SCIP_DECL_HEURINITSOL(heurInitsolIntshifting)
#define HEUR_FREQ
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)
static SCIP_DECL_HEURCOPY(heurCopyIntshifting)
#define HEUR_USESSUBSCIP
#define WEIGHTFACTOR
#define MAXSHIFTINGS
LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variabl...
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
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ 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
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ 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