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-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file heur_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. */
112 {
114 }
115 else
116 {
119 }
120
121 /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */
124 {
126 }
127 else
128 {
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 */
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 {
153
154 /* replace with last violated row containing fractional variables */
155 if( violpos != *nviolfracrows - 1 )
156 {
159 violpos = *nviolfracrows - 1;
160 }
161 (*nviolfracrows)--;
162 }
163
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 {
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;
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;
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;
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);
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 */
261
263 {
266 }
267 else
270 {
273 }
274 else
276
277 /* update row violation arrays */
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{
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);
322
323 /* get row entries */
324 rowcols = SCIProwGetCols(row);
325 rowvals = SCIProwGetVals(row);
327
328 /* calculate how much the activity must be shifted in order to become feasible */
332
333 /* select shifting variable */
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 )
369 else
370 {
371 if( increase )
373 else
375 shiftscore += 1.0;
376 }
377
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 */
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 */
415 shiftval = MIN(shiftval, ub);
416 }
417 }
418
419 if( SCIPisEQ(scip, shiftval, solval) )
420 continue;
421
422 deltaobj = SCIPvarGetObj(var) * (shiftval - solval);
424 && !SCIPisHugeValue(scip, REALABS(shiftval)) ) /* ignore candidates for which shiftval is too large */
425 {
428 *shiftvar = var;
429 *oldsolval = solval;
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);
468
469 /* select shifting variable */
470 maxnlocks = -1;
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;
493 *shiftvar = var;
494 *oldsolval = solval;
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;
509 *shiftvar = var;
510 *oldsolval = solval;
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);
553 assert(0 <= rowlppos && rowlppos < nlprows);
554 assert(!SCIProwIsLocal(row) || violrowpos[rowlppos] == -1);
555
556 if( SCIProwIsLocal(row) )
557 continue;
558
561
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 {
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 {
579 violrows[*nviolfracrows - 1] = row;
580
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 {
592
593 /* nothing to do if the row is exactly located at index *nviolfracrows */
595 {
597 violrows[*nviolfracrows] = row;
598
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
616{ /*lint --e{715}*/
617 assert(scip != NULL);
618 assert(heur != NULL);
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
631{ /*lint --e{715}*/
633
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
653{ /*lint --e{715}*/
655
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
675{
677
679
681 assert(heurdata != NULL);
682 heurdata->lastlp = -1;
683
684 return SCIP_OKAY;
685}
686
687
688/** execution method of primal heuristic */
689static
691{ /*lint --e{715}*/
695 SCIP_Real* lpcandssol;
697 SCIP_Real* minactivities;
698 SCIP_Real* maxactivities;
700 SCIP_Real* nincreases;
701 SCIP_Real* ndecreases;
704 SCIP_Real increaseweight;
705 SCIP_Real obj;
706 SCIP_Real bestshiftval;
707 SCIP_Real minobj;
710 int nvars;
711 int nfrac;
717 int c;
718 int r;
719 SCIP_Longint nlps;
720 SCIP_Longint ncalls;
721 SCIP_Longint nsolsfound;
722 SCIP_Longint nnodes;
723
728
730
731 /* do not call heuristic of node was already detected to be infeasible */
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 */
914 increaseweight = 1.0;
916 {
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",
962
963 /* get direction in which activity must be shifted */
967
968 /* search an integer variable that can shift the activity in the necessary direction */
971 }
972
973 if( shiftvar == NULL && nfrac > 0 )
974 {
975 SCIPdebugMsg(scip, "intshifting heuristic: search rounding variable and try to stay feasible\n");
977 }
978
979 /* check, whether shifting was possible */
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",
991
992 /* update row activities of globally valid rows */
995
996 if( nviolrows >= nprevviolrows )
998 else if( nviolrows < minnviolrows )
999 {
1002 }
1003
1004 /* store new solution value and decrease fractionality counter */
1006
1007 /* update fractionality counter and minimal objective value possible after shifting remaining variables */
1010 if( oldsolvalisfrac )
1011 {
1013 nfrac--;
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;
1063 SCIP_Bool lperror;
1064 int nintvars;
1065 int v;
1066#ifdef NDEBUG
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
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 */
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 */
1170
1171 assert(heur != NULL);
1172
1173 /* set non-NULL pointers to callback methods */
1178
1179 return SCIP_OKAY;
1180}
#define SCIP_REAL_MAX
Definition def.h:187
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
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:1361
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition scip_heur.c:117
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition heur.c:1586
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1596
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1576
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
SCIP_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:1775
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition scip_sol.c:3098
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1444
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1491
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1576
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_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:17611
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10019
SCIP_Bool lperror
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
* result
SCIP_Longint nsolsfound
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
SCIP_Longint ncalls
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)
SCIP_Real * maxactivities
return SCIP_OKAY
#define HEUR_FREQOFS
int c
#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)
heurdata lastlp
int nfrac
int nviolrows
SCIP_ROW ** lprows
static SCIP_SOL * sol
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
SCIP_Real * lpcandssol
SCIPfreeSol(scip, &heurdata->sol))
int * nfracsinrow
#define HEUR_NAME
SCIP_Real bestshiftval
int * violrowpos
int nlpcands
SCIP_Longint nlps
SCIPfreeRandom(scip, &heurdata->randnumgen)
#define DEFAULT_RANDSEED
SCIP_Real * minactivities
int minnviolrows
int r
#define HEUR_FREQ
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)
#define HEUR_USESSUBSCIP
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))
SCIP_Longint nnodes
LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variabl...
SCIP_VAR * var
SCIPendDive(scip))
static SCIP_VAR ** vars
int nintvars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
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 MAX(x, y)
Definition tclique_def.h:92
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:131
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:112
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:120
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Retcode SCIP_RETCODE
@ 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