Scippy

SCIP

Solving Constraint Integer Programs

heur_twoopt.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_twoopt.c
17  * @brief primal heuristic to improve incumbent solution by flipping pairs of variables
18  * @author Timo Berthold
19  * @author Gregor Hendel
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 #include "scip/heur_twoopt.h"
27 #include "scip/pub_misc.h"
28 
29 #define HEUR_NAME "twoopt"
30 #define HEUR_DESC "primal heuristic to improve incumbent solution by flipping pairs of variables"
31 #define HEUR_DISPCHAR 'B'
32 #define HEUR_PRIORITY -20100
33 #define HEUR_FREQ -1
34 #define HEUR_FREQOFS 0
35 #define HEUR_MAXDEPTH -1
36 
37 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
38 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
39 
40 /* default parameter values */
41 #define DEFAULT_INTOPT FALSE /**< optional integer optimization is applied by default */
42 #define DEFAULT_WAITINGNODES 0 /**< default number of nodes to wait after current best solution before calling heuristic */
43 #define DEFAULT_MATCHINGRATE 0.5 /**< default percentage by which two variables have to match in their LP-row set to be
44  * associated as pair by heuristic */
45 #define DEFAULT_MAXNSLAVES 199 /**< default number of slave candidates for a master variable */
46 #define DEFAULT_ARRAYSIZE 10 /**< the default array size for temporary arrays */
47 #define DEFAULT_RANDSEED 37 /**< initial random seed */
48 
49 /*
50  * Data structures
51  */
52 
53 /** primal heuristic data */
54 struct SCIP_HeurData
55 {
56  int lastsolindex; /**< index of last solution for which heuristic was performed */
57  SCIP_Real matchingrate; /**< percentage by which two variables have have to match in their LP-row
58  * set to be associated as pair by heuristic */
59  SCIP_VAR** binvars; /**< Array of binary variables which are sorted with respect to their occurrence
60  * in the LP-rows */
61  int nbinvars; /**< number of binary variables stored in heuristic array */
62  int waitingnodes; /**< user parameter to determine number of nodes to wait after last best solution
63  * before calling heuristic */
64  SCIP_Bool presolved; /**< flag to indicate whether presolving has already been executed */
65  int* binblockstart; /**< array to store the start indices of each binary block */
66  int* binblockend; /**< array to store the end indices of each binary block */
67  int nbinblocks; /**< number of blocks */
68 
69  /* integer variable twoopt data */
70  SCIP_Bool intopt; /**< parameter to determine if integer 2-opt should be applied */
71  SCIP_VAR** intvars; /**< array to store the integer variables in non-decreasing order
72  * with respect to their objective coefficient */
73  int nintvars; /**< the number of integer variables stored in array intvars */
74  int* intblockstart; /**< array to store the start indices of each binary block */
75  int* intblockend; /**< array to store the end indices of each binary block */
76  int nintblocks; /**< number of blocks */
77 
78  SCIP_Bool execute; /**< has presolveTwoOpt detected necessary structure for execution of heuristic? */
79  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
80  int maxnslaves; /**< delimits the maximum number of slave candidates for a master variable */
81 
82 #ifdef SCIP_STATISTIC
83  /* statistics */
84  int ntotalbinvars; /**< total number of binary variables over all runs */
85  int ntotalintvars; /**< total number of Integer variables over all runs */
86  int nruns; /**< counts the number of runs, i.e. the number of initialized
87  * branch and bound processes */
88  int maxbinblocksize; /**< maximum size of a binary block */
89  int maxintblocksize; /**< maximum size of an integer block */
90  int binnblockvars; /**< number of binary variables that appear in blocks */
91  int binnblocks; /**< number of blocks with at least two variables */
92  int intnblockvars; /**< number of Integer variables that appear in blocks */
93  int intnblocks; /**< number of blocks with at least two variables */
94  int binnexchanges; /**< number of executed changes of binary solution values leading to
95  * improvement in objective function */
96  int intnexchanges; /**< number of executed changes of Integer solution values leading to improvement in
97  * objective function */
98 #endif
99 };
100 
101 /** indicator for optimizing for binaries or integer variables */
102 enum Opttype
103 {
104  OPTTYPE_BINARY = 1,
106 };
107 typedef enum Opttype OPTTYPE;
109 /** indicator for direction of shifting variables */
110 enum Direction
111 {
112  DIRECTION_UP = 1,
115 };
116 typedef enum Direction DIRECTION;
118 /*
119  * Local methods
120  */
121 
122 /** Tries to switch the values of two binary or integer variables and checks feasibility with respect to the LP.
123  *
124  * @todo Adapt method not to copy entire activities array, but only the relevant region.
125  */
126 static
128  SCIP* scip, /**< scip instance */
129  SCIP_VAR* master, /**< first variable of variable pair */
130  SCIP_VAR* slave, /**< second variable of pair */
131  SCIP_Real mastersolval, /**< current value of variable1 in solution */
132  DIRECTION masterdir, /**< the direction into which the master variable has to be shifted */
133  SCIP_Real slavesolval, /**< current value of variable2 in solution */
134  DIRECTION slavedir, /**< the direction into which the slave variable has to be shifted */
135  SCIP_Real shiftval, /**< the value that variables should be shifted by */
136  SCIP_Real* activities, /**< the LP-row activities */
137  int nrows, /**< size of activities array */
138  SCIP_Bool* feasible /**< set to true if method has successfully switched the variable values */
139  )
140 { /*lint --e{715}*/
141  SCIP_COL* col;
142  SCIP_ROW** masterrows;
143  SCIP_ROW** slaverows;
144  SCIP_Real* mastercolvals;
145  SCIP_Real* slavecolvals;
146  int ncolmasterrows;
147  int ncolslaverows;
148  int i;
149  int j;
150 
151  assert(scip != NULL);
152  assert(master != NULL);
153  assert(slave != NULL);
154  assert(activities != NULL);
155  assert(SCIPisFeasGT(scip, shiftval, 0.0));
156 
157  assert(SCIPisFeasGE(scip, mastersolval + (int)masterdir * shiftval, SCIPvarGetLbGlobal(master)));
158  assert(SCIPisFeasLE(scip, mastersolval + (int)masterdir * shiftval, SCIPvarGetUbGlobal(master)));
159 
160  assert(SCIPisFeasGE(scip, slavesolval + (int)slavedir * shiftval, SCIPvarGetLbGlobal(slave)));
161  assert(SCIPisFeasLE(scip, slavesolval + (int)slavedir * shiftval, SCIPvarGetUbGlobal(slave)));
162 
163  /* get variable specific rows and coefficients for both master and slave. */
164  col = SCIPvarGetCol(master);
165  masterrows = SCIPcolGetRows(col);
166  mastercolvals = SCIPcolGetVals(col);
167  ncolmasterrows = SCIPcolGetNNonz(col);
168  assert(ncolmasterrows == 0 || masterrows != NULL);
169 
170  col = SCIPvarGetCol(slave);
171  slaverows = SCIPcolGetRows(col);
172  slavecolvals = SCIPcolGetVals(col);
173  ncolslaverows = SCIPcolGetNNonz(col);
174  assert(ncolslaverows == 0 || slaverows != NULL);
175 
176  /* update the activities of the LP rows of the master variable */
177  for( i = 0; i < ncolmasterrows && SCIProwGetLPPos(masterrows[i]) >= 0; ++i )
178  {
179  int rowpos;
180 
181  rowpos = SCIProwGetLPPos(masterrows[i]);
182  assert(rowpos < nrows);
183 
184  /* skip local rows */
185  if( rowpos >= 0 && ! SCIProwIsLocal(masterrows[i]) )
186  activities[rowpos] += mastercolvals[i] * (int)masterdir * shiftval;
187  }
188 
189  /* update the activities of the LP rows of the slave variable */
190  for( j = 0; j < ncolslaverows && SCIProwGetLPPos(slaverows[j]) >= 0; ++j )
191  {
192  int rowpos;
193 
194  rowpos = SCIProwGetLPPos(slaverows[j]);
195  assert(rowpos < nrows);
196 
197  /* skip local rows */
198  if( rowpos >= 0 && ! SCIProwIsLocal(slaverows[j]) )
199  {
200  activities[rowpos] += slavecolvals[j] * (int)slavedir * shiftval;
201  assert(SCIPisFeasGE(scip, activities[rowpos], SCIProwGetLhs(slaverows[j])));
202  assert(SCIPisFeasLE(scip, activities[rowpos], SCIProwGetRhs(slaverows[j])));
203  }
204  }
205 
206  /* in debug mode, the master rows are checked for feasibility which should be granted by the
207  * decision for a shift value */
208 #ifndef NDEBUG
209  for( i = 0; i < ncolmasterrows && SCIProwGetLPPos(masterrows[i]) >= 0; ++i )
210  {
211  /* local rows can be skipped */
212  if( SCIProwIsLocal(masterrows[i]) )
213  continue;
214 
215  assert(SCIPisFeasGE(scip, activities[SCIProwGetLPPos(masterrows[i])], SCIProwGetLhs(masterrows[i])));
216  assert(SCIPisFeasLE(scip, activities[SCIProwGetLPPos(masterrows[i])], SCIProwGetRhs(masterrows[i])));
217  }
218 #endif
219 
220  *feasible = TRUE;
221 
222  return SCIP_OKAY;
223 }
224 
225 /** Compare two variables with respect to their columns.
226  *
227  * Columns are treated as {0,1} vector, where every nonzero entry is treated as '1', and compared to each other
228  * lexicographically. I.e. var1 is < var2 if the corresponding column of var2 has the smaller single nonzero index of
229  * the two columns. This comparison costs O(constraints) in the worst case
230  */
231 static
232 int varColCompare(
233  SCIP_VAR* var1, /**< left argument of comparison */
234  SCIP_VAR* var2 /**< right argument of comparison */
235  )
236 {
237  SCIP_COL* col1;
238  SCIP_COL* col2;
239  SCIP_ROW** rows1;
240  SCIP_ROW** rows2;
241  int nnonzeros1;
242  int nnonzeros2;
243  int i;
244 
245  assert(var1 != NULL);
246  assert(var2 != NULL);
247 
248  /* get the necessary row and column data */
249  col1 = SCIPvarGetCol(var1);
250  col2 = SCIPvarGetCol(var2);
251  rows1 = SCIPcolGetRows(col1);
252  rows2 = SCIPcolGetRows(col2);
253  nnonzeros1 = SCIPcolGetNNonz(col1);
254  nnonzeros2 = SCIPcolGetNNonz(col2);
255 
256  assert(nnonzeros1 == 0 || rows1 != NULL);
257  assert(nnonzeros2 == 0 || rows2 != NULL);
258 
259  /* loop over the rows, stopped as soon as they differ in one index,
260  * or if counter reaches the end of a variables row set */
261  for( i = 0; i < nnonzeros1 && i < nnonzeros2; ++i )
262  {
263  if( SCIProwGetIndex(rows1[i]) != SCIProwGetIndex(rows2[i]) )
264  return SCIProwGetIndex(rows1[i]) - SCIProwGetIndex(rows2[i]);
265  }
266 
267  /* loop is finished, without differing in one of common row indices, due to loop invariant
268  * variable i reached either nnonzeros1 or nnonzeros2 or both.
269  * one can easily check that the difference of these two numbers always has the desired sign for comparison. */
270  return nnonzeros2 - nnonzeros1 ;
271 }
272 
273 /** implements a comparator to compare two variables with respect to their column entries */
274 static
275 SCIP_DECL_SORTPTRCOMP(SCIPvarcolComp)
276 {
277  return varColCompare((SCIP_VAR*) elem1, (SCIP_VAR*) elem2);
278 }
279 
280 /** checks if two given variables are contained in common LP rows,
281  * returns true if variables share the necessary percentage (matchingrate) of rows.
282  */
283 static
285  SCIP* scip, /**< current SCIP instance */
286  SCIP_VAR* var1, /**< first variable */
287  SCIP_VAR* var2, /**< second variable */
288  SCIP_Real matchingrate /**< determines the ratio of shared LP rows compared to the total number of
289  * LP-rows each variable appears in */
290  )
291 {
292  SCIP_COL* col1;
293  SCIP_COL* col2;
294  SCIP_ROW** rows1;
295  SCIP_ROW** rows2;
296  int nnonzeros1;
297  int nnonzeros2;
298  int i;
299  int j;
300  int nrows1not2; /* the number of LP-rows of variable 1 which variable 2 doesn't appear in */
301  int nrows2not1; /* vice versa */
302  int nrowmaximum;
303  int nrowabs;
304 
305  assert(var1 != NULL);
306  assert(var2 != NULL);
307 
308  /* get the necessary row and column data */
309  col1 = SCIPvarGetCol(var1);
310  col2 = SCIPvarGetCol(var2);
311  rows1 = SCIPcolGetRows(col1);
312  rows2 = SCIPcolGetRows(col2);
313  nnonzeros1 = SCIPcolGetNNonz(col1);
314  nnonzeros2 = SCIPcolGetNNonz(col2);
315 
316  assert(nnonzeros1 == 0 || rows1 != NULL);
317  assert(nnonzeros2 == 0 || rows2 != NULL);
318 
319  if( nnonzeros1 == 0 && nnonzeros2 == 0 )
320  return TRUE;
321 
322  /* initialize the counters for the number of rows not shared. */
323  nrowmaximum = MAX(nnonzeros1, nnonzeros2);
324 
325  nrowabs = ABS(nnonzeros1 - nnonzeros2);
326  nrows1not2 = nrowmaximum - nnonzeros2;
327  nrows2not1 = nrowmaximum - nnonzeros1;
328 
329  /* if the numbers of nonzero rows differs too much, w.r.t.matching ratio, the more expensive check over the rows
330  * doesn't have to be applied anymore because the counters for not shared rows can only increase.
331  */
332  assert(nrowmaximum > 0);
333 
334  if( (nrowmaximum - nrowabs) / (SCIP_Real) nrowmaximum < matchingrate )
335  return FALSE;
336 
337  i = 0;
338  j = 0;
339 
340  /* loop over all rows and determine number of non-shared rows */
341  while( i < nnonzeros1 && j < nnonzeros2 )
342  {
343  /* variables share a common row */
344  if( SCIProwGetIndex(rows1[i]) == SCIProwGetIndex(rows2[j]) )
345  {
346  ++i;
347  ++j;
348  }
349  /* variable 1 appears in rows1[i], variable 2 doesn't */
350  else if( SCIProwGetIndex(rows1[i]) < SCIProwGetIndex(rows2[j]) )
351  {
352  ++i;
353  ++nrows1not2;
354  }
355  /* variable 2 appears in rows2[j], variable 1 doesn't */
356  else
357  {
358  ++j;
359  ++nrows2not1;
360  }
361  }
362 
363  /* now apply the ratio based comparison, that is if the ratio of shared rows is greater or equal the matching rate
364  * for each variable */
365  return ( SCIPisFeasLE(scip, matchingrate, (nnonzeros1 - nrows1not2) / (SCIP_Real)(nnonzeros1)) ||
366  SCIPisFeasLE(scip, matchingrate, (nnonzeros2 - nrows2not1) / (SCIP_Real)(nnonzeros2)) ); /*lint !e795 */
367 }
368 
369 /** Determines a bound by which the absolute solution value of two integer variables can be shifted at most.
370  *
371  * The criterion is the maintenance of feasibility of any global LP row.
372  * The first implementation only considers shifting proportion 1:1, i.e. if master value is shifted by a certain
373  * integer value k downwards, the value of slave is simultaneously shifted by k upwards.
374  */
375 static
377  SCIP* scip, /**< current scip instance */
378  SCIP_SOL* sol, /**< current incumbent */
379  SCIP_VAR* master, /**< current master variable */
380  DIRECTION masterdirection, /**< the shifting direction of the master variable */
381  SCIP_VAR* slave, /**< slave variable with same LP_row set as master variable */
382  DIRECTION slavedirection, /**< the shifting direction of the slave variable */
383  SCIP_Real* activities, /**< array of LP row activities */
384  int nrows /**< the number of rows in LP and the size of the activities array */
385  )
386 { /*lint --e{715}*/
387  SCIP_Real masterbound;
388  SCIP_Real slavebound;
390 
391  SCIP_COL* col;
392  SCIP_ROW** slaverows;
393  SCIP_ROW** masterrows;
394  SCIP_Real* mastercolvals;
395  SCIP_Real* slavecolvals;
396  int nslaverows;
397  int nmasterrows;
398  int i;
399  int j;
400 
401  assert(scip != NULL);
402  assert(sol != NULL);
403  assert(master != NULL);
404  assert(slave != NULL);
405  assert(SCIPvarIsIntegral(master) && SCIPvarIsIntegral(slave));
406  assert(masterdirection == DIRECTION_UP || masterdirection == DIRECTION_DOWN);
407  assert(slavedirection == DIRECTION_UP || slavedirection == DIRECTION_DOWN);
408 
409  /* determine the trivial variable bounds for shift */
410  if( masterdirection == DIRECTION_UP )
411  masterbound = SCIPvarGetUbGlobal(master) - SCIPgetSolVal(scip, sol, master);
412  else
413  masterbound = SCIPgetSolVal(scip, sol, master) - SCIPvarGetLbGlobal(master);
414 
415  if( slavedirection == DIRECTION_UP )
416  slavebound = SCIPvarGetUbGlobal(slave) - SCIPgetSolVal(scip, sol, slave);
417  else
418  slavebound = SCIPgetSolVal(scip, sol, slave) - SCIPvarGetLbGlobal(slave);
419 
420  bound = MIN(slavebound, masterbound);
421  assert(!SCIPisInfinity(scip,bound));
422  if( SCIPisFeasZero(scip, bound) )
423  return 0.0;
424 
425  /* get the necessary row and and column data for each variable */
426  col = SCIPvarGetCol(slave);
427  slaverows = SCIPcolGetRows(col);
428  slavecolvals = SCIPcolGetVals(col);
429  nslaverows = SCIPcolGetNNonz(col);
430 
431  col = SCIPvarGetCol(master);
432  mastercolvals = SCIPcolGetVals(col);
433  masterrows = SCIPcolGetRows(col);
434  nmasterrows = SCIPcolGetNNonz(col);
435 
436  assert(nslaverows == 0 || slavecolvals != NULL);
437  assert(nmasterrows == 0 || mastercolvals != NULL);
438 
439  SCIPdebugMsg(scip, " Master: %s with direction %d and %d rows, Slave: %s with direction %d and %d rows \n", SCIPvarGetName(master),
440  (int)masterdirection, nmasterrows, SCIPvarGetName(slave), (int)slavedirection, nslaverows);
441 
442  /* loop over all LP rows and determine the maximum integer bound by which both variables
443  * can be shifted without loss of feasibility
444  */
445  i = 0;
446  j = 0;
447  while( (i < nslaverows || j < nmasterrows) && SCIPisPositive(scip, bound) )
448  {
449  SCIP_ROW* row;
450  SCIP_Real effect;
451  SCIP_Real rhs;
452  SCIP_Real lhs;
453  SCIP_Real activity;
454  int rowpos;
455  int masterindex;
456  int slaveindex;
457  SCIP_Bool slaveincrement;
458  SCIP_Bool masterincrement;
459 
460  /* check if one pointer already reached the end of the respective array */
461  if( i < nslaverows && SCIProwGetLPPos(slaverows[i]) == -1 )
462  {
463  SCIPdebugMsg(scip, " Slaverow %s is not in LP (i=%d, j=%d)\n", SCIProwGetName(slaverows[i]), i, j);
464  i = nslaverows;
465  continue;
466  }
467  if( j < nmasterrows && SCIProwGetLPPos(masterrows[j]) == -1 )
468  {
469  SCIPdebugMsg(scip, " Masterrow %s is not in LP (i=%d, j=%d) \n", SCIProwGetName(masterrows[j]), i, j);
470  j = nmasterrows;
471  continue;
472  }
473 
474  slaveincrement = FALSE;
475  /* If one counter has already reached its limit, assign a huge number to the corresponding
476  * row index to simulate an always greater row position. */
477  if( i < nslaverows )
478  slaveindex = SCIProwGetIndex(slaverows[i]);
479  else
480  slaveindex = INT_MAX;
481 
482  if( j < nmasterrows )
483  masterindex = SCIProwGetIndex(masterrows[j]);
484  else
485  masterindex = INT_MAX;
486 
487  assert(0 <= slaveindex && 0 <= masterindex);
488 
489  assert(slaveindex < INT_MAX || masterindex < INT_MAX);
490 
491  /* the current row is the one with the smaller index */
492  if( slaveindex <= masterindex )
493  {
494  rowpos = SCIProwGetLPPos(slaverows[i]);
495  row = slaverows[i];
496  slaveincrement = TRUE;
497  masterincrement = (slaveindex == masterindex);
498  }
499  else
500  {
501  assert(j < nmasterrows);
502 
503  rowpos = SCIProwGetLPPos(masterrows[j]);
504  row = masterrows[j];
505  masterincrement = TRUE;
506  }
507  assert(row != NULL);
508 
509  /* local rows can be skipped */
510  if( !SCIProwIsLocal(row) )
511  {
512  /* effect is the effect on the row activity by shifting the variables by 1 in the respective directions */
513  effect = 0.0;
514  if( slaveindex <= masterindex )
515  effect += (slavecolvals[i] * (int)slavedirection);
516  if( masterindex <= slaveindex )
517  effect += (mastercolvals[j] * (int)masterdirection);
518 
519  /* get information about the current row */
520  if( rowpos >= 0 && !SCIPisFeasZero(scip, effect) )
521  {
522  /* effect does not equal zero, the bound is determined as minimum positive integer such that
523  * feasibility of this constraint is maintained.
524  * if constraint is an equality constraint, activity and lhs/rhs should be feasibly equal, which
525  * will cause the method to return zero.
526  */
527  assert(rowpos < nrows);
528 
529  activity = activities[rowpos];
530  rhs = SCIProwGetRhs(row);
531  lhs = SCIProwGetLhs(row);
532 
533  /* if the row is an equation, abort because of effect being nonzero */
534  if( SCIPisFeasEQ(scip, lhs, rhs) )
535  return 0.0;
536 
537  assert(SCIPisFeasLE(scip, lhs, activity) && SCIPisFeasLE(scip, activity, rhs));
538 
539  SCIPdebugMsg(scip, " %g <= %g <= %g, bound = %g, effect = %g (%g * %d + %g * %d) (i=%d,j=%d)\n", lhs, activity, rhs, bound, effect,
540  slaveindex <= masterindex ? slavecolvals[i] : 0.0, (int)slavedirection, masterindex <= slaveindex ? mastercolvals[j] : 0.0,
541  (int)masterdirection, i, j);
542 
543  /* if the row has a left hand side, ensure that shifting preserves feasibility of this ">="-constraint */
544  if( !SCIPisInfinity(scip, -lhs) && SCIPisFeasLT(scip, activity + (effect * bound), lhs) )
545  {
546  SCIP_Real newval;
547 
548  assert(SCIPisNegative(scip, effect));
549 
550  newval = SCIPfeasFloor(scip, (lhs - activity)/effect); /*lint !e414*/
551  bound = MIN(bound - 1.0, newval);
552  }
553 
554  /* if the row has an upper bound, ensure that shifting preserves feasibility of this "<="-constraint */
555  if( !SCIPisInfinity(scip, rhs) && SCIPisFeasGT(scip, activity + (effect * bound), rhs) )
556  {
557  SCIP_Real newval;
558 
559  assert(SCIPisPositive(scip, effect));
560 
561  newval = SCIPfeasFloor(scip, (rhs - activity)/effect); /*lint !e414*/
562  bound = MIN(bound - 1.0, newval);
563  }
564 
565  assert(SCIPisFeasLE(scip, lhs, activity + effect * bound) && SCIPisFeasGE(scip, rhs, activity + effect * bound));
566  assert(SCIPisFeasIntegral(scip, bound));
567  }
568  else
569  {
570  SCIPdebugMsg(scip, " Zero effect on row %s, effect %g, master coeff: %g slave coeff: %g (i=%d, j=%d)\n",
571  SCIProwGetName(row), effect, mastercolvals[j], slavecolvals[i], i, j);
572  }
573  }
574  else
575  {
576  SCIPdebugMsg(scip, " Row %s is local.\n", SCIProwGetName(row));
577  }
578 
579  /* increase the counters which belong to the corresponding row. Both counters are increased by
580  * 1 iff rowpos1 <= rowpos2 <= rowpos1 */
581  if( slaveincrement )
582  ++i;
583  if( masterincrement )
584  ++j;
585  }
586 
587  /* due to numerical reasons, bound can be negative. A variable shift by a negative bound is not desired by
588  * by the heuristic -> Change the return value to zero */
589  if( !SCIPisPositive(scip, bound) )
590  bound = 0.0;
591 
592  return bound;
593 }
594 
595 /** Disposes variable with no heuristic relevancy, e.g., due to a fixed solution value, from its neighborhood block.
596  *
597  * The affected neighborhood block is reduced by 1.
598  */
599 static
600 void disposeVariable(
601  SCIP_VAR** vars, /**< problem variables */
602  int* blockend, /**< contains end index of block */
603  int varindex /**< variable index */
604  )
605 {
606  assert(blockend != NULL);
607  assert(varindex <= *blockend);
608 
609  vars[varindex] = vars[*blockend];
610  --(*blockend);
611 }
612 
613 /** realizes the presolve independently from type of variables it's applied to */
614 static
616  SCIP* scip, /**< current scip */
617  SCIP_VAR** vars, /**< problem vars */
618  SCIP_VAR*** varspointer, /**< pointer to heuristic specific variable memory */
619  int nvars, /**< the number of variables */
620  int* nblocks, /**< pointer to store the number of detected blocks */
621  int* maxblocksize, /**< maximum size of a block */
622  int* nblockvars, /**< pointer to store the number of block variables */
623  int** blockstart, /**< pointer to store the array of block start indices */
624  int** blockend, /**< pointer to store the array of block end indices */
625  SCIP_HEUR* heur, /**< the heuristic */
626  SCIP_HEURDATA* heurdata /**< the heuristic data */
627  )
628 {
629  int v;
630  int startindex;
631 
632  assert(scip != NULL);
633  assert(vars != NULL);
634  assert(nvars >= 2);
635  assert(nblocks != NULL);
636  assert(nblockvars != NULL);
637  assert(blockstart != NULL);
638  assert(blockend != NULL);
639  assert(heur != NULL);
640  assert(heurdata != NULL);
641 
642  /* allocate the heuristic specific variables */
643  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, varspointer, vars, nvars));
644 
645  /* sort the variables with respect to their columns */
646  SCIPsortPtr((void**)(*varspointer), SCIPvarcolComp, nvars);
647 
648  /* start determining blocks, i.e. a set of at least two variables which share most of their row set.
649  * If there is none, heuristic does not need to be executed.
650  */
651  startindex = 0;
652  *nblocks = 0;
653  *nblockvars = 0;
654 
655  SCIP_CALL( SCIPallocBlockMemoryArray(scip, blockstart, nvars/2) );
656  SCIP_CALL( SCIPallocBlockMemoryArray(scip, blockend, nvars/2) );
657 
658  /* loop over variables and compare neighbors */
659  for( v = 1; v < nvars; ++v )
660  {
661  if( !checkConstraintMatching(scip, (*varspointer)[startindex], (*varspointer)[v], heurdata->matchingrate) )
662  {
663  /* current block has its last variable at position v-1. If v differs from startindex by at least 2,
664  * a block is detected. Update the data correspondingly */
665  if( v - startindex >= 2 )
666  {
667  assert(*nblocks < nvars/2);
668  (*nblockvars) += v - startindex;
669  (*maxblocksize) = MAX((*maxblocksize), v - startindex);
670  (*blockstart)[*nblocks] = startindex;
671  (*blockend)[*nblocks] = v - 1;
672  (*nblocks)++;
673  }
674  startindex = v;
675  }
676  else if( v == nvars - 1 && v - startindex >= 1 )
677  {
678  assert(*nblocks < nvars/2);
679  (*nblockvars) += v - startindex + 1;
680  (*maxblocksize) = MAX((*maxblocksize), v - startindex + 1);
681  (*blockstart)[*nblocks] = startindex;
682  (*blockend)[*nblocks] = v;
683  (*nblocks)++;
684  }
685  }
686 
687  /* reallocate memory with respect to the number of found blocks; if there were none, free the memory */
688  if( *nblocks > 0 )
689  {
690  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, blockstart, nvars/2, *nblocks) );
691  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, blockend, nvars/2, *nblocks) );
692  }
693  else
694  {
695  SCIPfreeBlockMemoryArray(scip, blockstart, nvars/2);
696  SCIPfreeBlockMemoryArray(scip, blockend, nvars/2);
697 
698  *blockstart = NULL;
699  *blockend = NULL;
700  }
701 
702  return SCIP_OKAY;
703 }
704 
705 /** initializes the required structures for execution of heuristic.
706  *
707  * If objective coefficient functions are not all equal, each Binary and Integer variables are sorted
708  * into heuristic-specific arrays with respect to their lexicographical column order,
709  * where every zero in a column is interpreted as zero and every nonzero as '1'.
710  * After the sorting, the variables are compared with respect to user parameter matchingrate and
711  * the heuristic specific blocks are determined.
712  */
713 static
715  SCIP* scip, /**< current scip instance */
716  SCIP_HEUR* heur, /**< heuristic */
717  SCIP_HEURDATA* heurdata /**< the heuristic data */
718  )
719 {
720  int nbinvars;
721  int nintvars;
722  int nvars;
723  SCIP_VAR** vars;
724  int nbinblockvars = 0;
725  int nintblockvars;
726  int maxbinblocksize = 0;
727  int maxintblocksize;
728 
729  assert(scip != NULL);
730  assert(heurdata != NULL);
731 
732  /* ensure that method is not executed if presolving was already applied once in current branch and bound process */
733  if( heurdata->presolved )
734  return SCIP_OKAY;
735 
736  /* get necessary variable information, i.e. number of binary and integer variables */
737  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
738 
739  /* if number of binary problem variables exceeds 2, they are subject to 2-optimization algorithm, hence heuristic
740  * calls innerPresolve method to detect necessary structures. */
741  if( nbinvars >= 2 )
742  {
743  SCIP_CALL( innerPresolve(scip, vars, &(heurdata->binvars), nbinvars, &(heurdata->nbinblocks), &maxbinblocksize,
744  &nbinblockvars, &(heurdata->binblockstart), &(heurdata->binblockend), heur, heurdata) );
745  }
746 
747  heurdata->nbinvars = nbinvars;
748  heurdata->execute = nbinvars > 1 && heurdata->nbinblocks > 0;
749 
750 #ifdef SCIP_STATISTIC
751  /* update statistics */
752  heurdata->binnblocks += (heurdata->nbinblocks);
753  heurdata->binnblockvars += nbinblockvars;
754  heurdata->ntotalbinvars += nbinvars;
755  heurdata->maxbinblocksize = MAX(maxbinblocksize, heurdata->maxbinblocksize);
756 
757  SCIPstatisticMessage(" Twoopt BINARY presolving finished with <%d> blocks, <%d> block variables \n",
758  heurdata->nbinblocks, nbinblockvars);
759 #endif
760 
761  if( heurdata->intopt && nintvars > 1 )
762  {
763  SCIP_CALL( innerPresolve(scip, &(vars[nbinvars]), &(heurdata->intvars), nintvars, &(heurdata->nintblocks), &maxintblocksize,
764  &nintblockvars, &(heurdata->intblockstart), &(heurdata->intblockend),
765  heur, heurdata) );
766 
767  heurdata->execute = heurdata->execute || heurdata->nintblocks > 0;
768 
769 #ifdef SCIP_STATISTIC
770  /* update statistics */
771  heurdata->intnblocks += heurdata->nintblocks;
772  heurdata->intnblockvars += nintblockvars;
773  heurdata->ntotalintvars += nintvars;
774  heurdata->maxintblocksize = MAX(maxintblocksize, heurdata->maxintblocksize);
775  SCIPstatisticMessage(" Twoopt Integer presolving finished with <%d> blocks, <%d> block variables \n",
776  heurdata->nintblocks, nintblockvars);
777  SCIPstatisticMessage(" INTEGER coefficients are all equal \n");
778 #endif
779  }
780  heurdata->nintvars = nintvars;
781 
782  /* presolving is finished, heuristic data is updated*/
783  heurdata->presolved = TRUE;
784  SCIPheurSetData(heur, heurdata);
785 
786  return SCIP_OKAY;
787 }
788 
789 /*
790  * Callback methods of primal heuristic
791  */
792 
793 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
794 static
795 SCIP_DECL_HEURCOPY(heurCopyTwoopt)
796 { /*lint --e{715}*/
797  assert(scip != NULL);
798  assert(heur != NULL);
799  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
800 
801  /* call inclusion method of primal heuristic */
803 
804  return SCIP_OKAY;
805 }
806 
807 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
808 static
809 SCIP_DECL_HEURFREE(heurFreeTwoopt)
810 { /*lint --e{715}*/
811  SCIP_HEURDATA* heurdata;
812 
813  assert(heur != NULL);
814  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
815  assert(scip != NULL);
816 
817  /* free heuristic data */
818  heurdata = SCIPheurGetData(heur);
819  assert(heurdata != NULL);
820 
821  SCIPfreeBlockMemory(scip, &heurdata);
822  SCIPheurSetData(heur, NULL);
823 
824  return SCIP_OKAY;
825 }
826 
827 /** initialization method of primal heuristic (called after problem was transformed) */
828 static
829 SCIP_DECL_HEURINIT(heurInitTwoopt)
830 {
831  SCIP_HEURDATA* heurdata;
832  assert(heur != NULL);
833  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
834  assert(scip != NULL);
835 
836  heurdata = SCIPheurGetData(heur);
837  assert(heurdata != NULL);
838 
839  /* heuristic has not run yet, all heuristic specific data is set to initial values */
840  heurdata->nbinvars = 0;
841  heurdata->nintvars = 0;
842  heurdata->lastsolindex = -1;
843  heurdata->presolved = FALSE;
844  heurdata->nbinblocks = 0;
845  heurdata->nintblocks = 0;
846 
847  /* create random number generator */
848  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip),
850 
851 #ifdef SCIP_STATISTIC
852  /* initialize statistics */
853  heurdata->binnexchanges = 0;
854  heurdata->intnexchanges = 0;
855  heurdata->binnblockvars = 0;
856  heurdata->intnblockvars = 0;
857  heurdata->binnblocks = 0;
858  heurdata->intnblocks = 0;
859 
860  heurdata->maxbinblocksize = 0;
861  heurdata->maxintblocksize = 0;
862 
863  heurdata->ntotalbinvars = 0;
864  heurdata->ntotalintvars = 0;
865  heurdata->nruns = 0;
866 #endif
867 
868  /* all pointers are initially set to NULL. Since presolving
869  * of the heuristic requires a lot of calculation time on some instances,
870  * but might not be needed e.g. if problem is infeasible, presolving is applied
871  * when heuristic is executed for the first time
872  */
873  heurdata->binvars = NULL;
874  heurdata->intvars = NULL;
875  heurdata->binblockstart = NULL;
876  heurdata->binblockend = NULL;
877  heurdata->intblockstart = NULL;
878  heurdata->intblockend = NULL;
879 
880  SCIPheurSetData(heur, heurdata);
881 
882  return SCIP_OKAY;
883 }
884 
885 /* Realizes the 2-optimization algorithm, which tries to improve incumbent solution
886  * by shifting pairs of variables which share a common row set.
887  */
888 static
890  SCIP* scip, /**< current SCIP instance */
891  SCIP_SOL* worksol, /**< working solution */
892  SCIP_VAR** vars, /**< binary or integer variables */
893  int* blockstart, /**< contains start indices of blocks */
894  int* blockend, /**< contains end indices of blocks */
895  int nblocks, /**< the number of blocks */
896  OPTTYPE opttype, /**< are binaries or integers optimized */
897  SCIP_Real* activities, /**< the LP-row activities */
898  int nrows, /**< the number of LP rows */
899  SCIP_Bool* improvement, /**< was there a successful shift? */
900  SCIP_Bool* varboundserr, /**< has the current incumbent already been cut off */
901  SCIP_HEURDATA* heurdata /**< the heuristic data */
902  )
903 { /*lint --e{715}*/
904  int b;
905  SCIP_Real* objchanges;
906  SCIP_VAR** bestmasters;
907  SCIP_VAR** bestslaves;
908  int* bestdirections;
909  int arraysize;
910  int npairs = 0;
911 
912  assert(scip != NULL);
913  assert(nblocks > 0);
914  assert(blockstart != NULL && blockend != NULL);
915  assert(varboundserr != NULL);
916  assert(activities != NULL);
917  assert(worksol != NULL);
918  assert(improvement != NULL);
919 
920  *varboundserr = FALSE;
921 
922  SCIP_CALL( SCIPallocBufferArray(scip, &bestmasters, DEFAULT_ARRAYSIZE) );
923  SCIP_CALL( SCIPallocBufferArray(scip, &bestslaves, DEFAULT_ARRAYSIZE) );
924  SCIP_CALL( SCIPallocBufferArray(scip, &objchanges, DEFAULT_ARRAYSIZE) );
925  SCIP_CALL( SCIPallocBufferArray(scip, &bestdirections, DEFAULT_ARRAYSIZE) );
926  arraysize = DEFAULT_ARRAYSIZE;
927 
928  /* iterate over blocks */
929  for( b = 0; b < nblocks; ++b )
930  {
931  int m;
932  int blocklen;
933 
934  blocklen = blockend[b] - blockstart[b] + 1;
935 
936  /* iterate over variables in current block */
937  for( m = 0; m < blocklen; ++m )
938  {
939  /* determine the new master variable for heuristic's optimization method */
940  SCIP_VAR* master;
941  SCIP_Real masterobj;
942  SCIP_Real mastersolval;
943  SCIP_Real bestimprovement;
944  SCIP_Real bestbound;
945  int bestslavepos;
946  int s;
947  int firstslave;
948  int nslaves;
949  int bestdirection;
950  DIRECTION bestmasterdir;
951  DIRECTION bestslavedir;
952 
953  master = vars[blockstart[b] + m]; /*lint !e679*/
954  masterobj = SCIPvarGetObj(master);
955  mastersolval = SCIPgetSolVal(scip, worksol, master);
956 
957  /* due to cuts or fixings of solution values, worksol might not be feasible w.r.t. its bounds.
958  * Exit method in that case. */
959  if( SCIPisFeasGT(scip, mastersolval, SCIPvarGetUbGlobal(master)) || SCIPisFeasLT(scip, mastersolval, SCIPvarGetLbGlobal(master)) )
960  {
961  *varboundserr = TRUE;
962  SCIPdebugMsg(scip, "Solution has violated variable bounds for var %s: %g <= %g <= %g \n",
963  SCIPvarGetName(master), SCIPvarGetLbGlobal(master), mastersolval, SCIPvarGetUbGlobal(master));
964  goto TERMINATE;
965  }
966 
967  /* if variable has fixed solution value, it is deleted from heuristic array */
968  if( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(master), SCIPvarGetLbGlobal(master)) )
969  {
970  disposeVariable(vars, &(blockend[b]), blockstart[b] + m);
971  --blocklen;
972  continue;
973  }
974  else if( SCIPvarGetStatus(master) != SCIP_VARSTATUS_COLUMN )
975  continue;
976 
977  assert(SCIPisFeasIntegral(scip, mastersolval));
978 
979  assert(opttype == OPTTYPE_INTEGER || (SCIPisFeasEQ(scip, mastersolval, 1.0) || SCIPisFeasEQ(scip, mastersolval, 0.0)));
980 
981  /* initialize the data of the best available shift */
982  bestimprovement = 0.0;
983  bestslavepos = -1;
984  bestbound = 0.0;
985  bestmasterdir = DIRECTION_NONE;
986  bestslavedir = DIRECTION_NONE;
987  bestdirection = -1;
988 
989  /* in blocks with more than heurdata->maxnslaves variables, a slave candidate region is chosen */
990  if( heurdata->maxnslaves >= 0 && blocklen > heurdata->maxnslaves )
991  firstslave = SCIPrandomGetInt(heurdata->randnumgen, blockstart[b] + m, blockend[b]);
992  else
993  firstslave = blockstart[b] + m + 1;
994 
995  nslaves = MIN((heurdata->maxnslaves == -1 ? INT_MAX : heurdata->maxnslaves), blocklen);
996 
997  /* Loop over block and determine a slave shift candidate for master variable.
998  * If more than one candidate is available, choose the shift which improves objective function
999  * the most. */
1000  for( s = 0; s < nslaves; ++s )
1001  {
1002  SCIP_VAR* slave;
1003  SCIP_Real slaveobj;
1004  SCIP_Real slavesolval;
1005  SCIP_Real changedobj;
1006  SCIP_Real diffdirbound;
1007  SCIP_Real equaldirbound;
1008  int directions;
1009  int slaveindex;
1010 
1011  slaveindex = (firstslave + s - blockstart[b]) % blocklen;
1012  slaveindex += blockstart[b];
1013 
1014  /* in case of a small block, we do not want to try possible pairings twice */
1015  if( (blocklen <= heurdata->maxnslaves || heurdata->maxnslaves == -1) && slaveindex < blockstart[b] + m )
1016  break;
1017  /* master and slave should not be the same variable */
1018  if( slaveindex == blockstart[b] + m )
1019  continue;
1020 
1021  /* get the next slave variable */
1022  slave = vars[slaveindex];
1023  slaveobj = SCIPvarGetObj(slave);
1024  slavesolval = SCIPgetSolVal(scip, worksol, slave);
1025  changedobj = 0.0;
1026 
1027  assert(SCIPvarGetType(master) == SCIPvarGetType(slave));
1028  assert(SCIPisFeasIntegral(scip, slavesolval));
1029  assert(opttype == OPTTYPE_INTEGER || (SCIPisFeasEQ(scip, slavesolval, 1.0) || SCIPisFeasEQ(scip, slavesolval, 0.0)));
1030 
1031  /* solution is not feasible w.r.t. the variable bounds, stop optimization in this case */
1032  if( SCIPisFeasGT(scip, slavesolval, SCIPvarGetUbGlobal(slave)) || SCIPisFeasLT(scip, slavesolval, SCIPvarGetLbGlobal(slave)) )
1033  {
1034  *varboundserr = TRUE;
1035  SCIPdebugMsg(scip, "Solution has violated variable bounds for var %s: %g <= %g <= %g \n",
1036  SCIPvarGetName(slave), SCIPvarGetLbGlobal(slave), slavesolval, SCIPvarGetUbGlobal(slave));
1037  goto TERMINATE;
1038  }
1039 
1040  /* if solution value of the variable is fixed, delete it from the remaining candidates in the block */
1041  if( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(slave), SCIPvarGetLbGlobal(slave) ) )
1042  {
1043  disposeVariable(vars, &(blockend[b]), slaveindex);
1044  --blocklen;
1045  continue;
1046  }
1047  else if( SCIPvarGetStatus(master) != SCIP_VARSTATUS_COLUMN )
1048  continue;
1049 
1050  /* determine the shifting direction to improve the objective function */
1051  /* assert(SCIPisFeasGT(scip, masterobj, slaveobj)); */
1052 
1053  /* The heuristic chooses the shifting direction and the corresponding maximum nonnegative
1054  * integer shift value for the two variables which preserves feasibility and improves
1055  * the objective function value. */
1056  directions = -1;
1057  diffdirbound = 0.0;
1058  equaldirbound = 0.0;
1059 
1060  if( SCIPisFeasLT(scip, masterobj - slaveobj, 0.0) )
1061  {
1062  diffdirbound = determineBound(scip, worksol, master, DIRECTION_UP, slave, DIRECTION_DOWN, activities, nrows);
1063  directions = 2;
1064  /* the improvement of objective function is calculated */
1065  changedobj = (masterobj - slaveobj) * diffdirbound;
1066  }
1067  else if( SCIPisFeasGT(scip, masterobj - slaveobj, 0.0) )
1068  {
1069  diffdirbound = determineBound(scip, worksol, master, DIRECTION_DOWN, slave, DIRECTION_UP, activities, nrows);
1070  directions = 1;
1071  changedobj = (slaveobj - masterobj) * diffdirbound;
1072  }
1073 
1074  if( SCIPisFeasLT(scip, masterobj + slaveobj, 0.0) )
1075  {
1076  equaldirbound = determineBound(scip, worksol, master, DIRECTION_UP, slave, DIRECTION_UP, activities, nrows);
1077  if( SCIPisFeasLT(scip, (slaveobj + masterobj) * equaldirbound, changedobj) )
1078  {
1079  changedobj = (slaveobj + masterobj) * equaldirbound;
1080  directions = 3;
1081  }
1082  }
1083  else if( SCIPisFeasGT(scip, masterobj + slaveobj, 0.0) )
1084  {
1085  equaldirbound = determineBound(scip, worksol, master, DIRECTION_DOWN, slave, DIRECTION_DOWN, activities, nrows);
1086  if( SCIPisFeasLT(scip, -(slaveobj + masterobj) * equaldirbound, changedobj) )
1087  {
1088  changedobj = -(slaveobj + masterobj) * equaldirbound;
1089  directions = 0;
1090  }
1091  }
1092  assert(SCIPisFeasIntegral(scip, equaldirbound));
1093  assert(SCIPisFeasIntegral(scip, diffdirbound));
1094  assert(SCIPisFeasGE(scip, equaldirbound, 0.0));
1095  assert(SCIPisFeasGE(scip, diffdirbound, 0.0));
1096 
1097  /* choose the candidate which improves the objective function the most */
1098  if( (SCIPisFeasGT(scip, equaldirbound, 0.0) || SCIPisFeasGT(scip, diffdirbound, 0.0))
1099  && SCIPisFeasLT(scip, changedobj, bestimprovement) )
1100  {
1101  bestimprovement = changedobj;
1102  bestslavepos = slaveindex;
1103  bestdirection = directions;
1104 
1105  /* the most promising shift, i.e., the one which can improve the objective
1106  * the most, is recorded by the integer 'directions'. It is recovered via the use
1107  * of a binary representation of the four different combinations for the shifting directions
1108  * of two variables */
1109  if( directions / 2 == 1 )
1110  bestmasterdir = DIRECTION_UP;
1111  else
1112  bestmasterdir = DIRECTION_DOWN;
1113 
1114  if( directions % 2 == 1 )
1115  bestslavedir = DIRECTION_UP;
1116  else
1117  bestslavedir = DIRECTION_DOWN;
1118 
1119  if( bestmasterdir == bestslavedir )
1120  bestbound = equaldirbound;
1121  else
1122  bestbound = diffdirbound;
1123  }
1124  }
1125 
1126  /* choose the most promising candidate, if one exists */
1127  if( bestslavepos >= 0 )
1128  {
1129  if( npairs == arraysize )
1130  {
1131  SCIP_CALL( SCIPreallocBufferArray(scip, &bestmasters, 2 * arraysize) );
1132  SCIP_CALL( SCIPreallocBufferArray(scip, &bestslaves, 2 * arraysize) );
1133  SCIP_CALL( SCIPreallocBufferArray(scip, &objchanges, 2 * arraysize) );
1134  SCIP_CALL( SCIPreallocBufferArray(scip, &bestdirections, 2 * arraysize) );
1135  arraysize = 2 * arraysize;
1136  }
1137  assert( npairs < arraysize );
1138 
1139  bestmasters[npairs] = master;
1140  bestslaves[npairs] = vars[bestslavepos];
1141  objchanges[npairs] = ((int)bestslavedir * SCIPvarGetObj(bestslaves[npairs]) + (int)bestmasterdir * masterobj) * bestbound;
1142  bestdirections[npairs] = bestdirection;
1143 
1144  assert(objchanges[npairs] < 0);
1145 
1146  SCIPdebugMsg(scip, " Saved candidate pair {%s=%g, %s=%g} with objectives <%g>, <%g> to be set to {%g, %g} %d\n",
1147  SCIPvarGetName(master), mastersolval, SCIPvarGetName(bestslaves[npairs]), SCIPgetSolVal(scip, worksol, bestslaves[npairs]) ,
1148  masterobj, SCIPvarGetObj(bestslaves[npairs]), mastersolval + (int)bestmasterdir * bestbound, SCIPgetSolVal(scip, worksol, bestslaves[npairs])
1149  + (int)bestslavedir * bestbound, bestdirections[npairs]);
1150 
1151  ++npairs;
1152  }
1153  }
1154  }
1155 
1156  if( npairs == 0 )
1157  goto TERMINATE;
1158 
1159  SCIPsortRealPtrPtrInt(objchanges, (void**)bestmasters, (void**)bestslaves, bestdirections, npairs);
1160 
1161  for( b = 0; b < npairs; ++b )
1162  {
1163  SCIP_VAR* master;
1164  SCIP_VAR* slave;
1165  SCIP_Real mastersolval;
1166  SCIP_Real slavesolval;
1167  SCIP_Real masterobj;
1168  SCIP_Real slaveobj;
1169  SCIP_Real bound;
1170  DIRECTION masterdir;
1171  DIRECTION slavedir;
1172 
1173  master = bestmasters[b];
1174  slave = bestslaves[b];
1175  mastersolval = SCIPgetSolVal(scip, worksol, master);
1176  slavesolval = SCIPgetSolVal(scip, worksol, slave);
1177  masterobj =SCIPvarGetObj(master);
1178  slaveobj = SCIPvarGetObj(slave);
1179 
1180  assert(0 <= bestdirections[b] && bestdirections[b] < 4);
1181 
1182  if( bestdirections[b] / 2 == 1 )
1183  masterdir = DIRECTION_UP;
1184  else
1185  masterdir = DIRECTION_DOWN;
1186 
1187  if( bestdirections[b] % 2 == 1 )
1188  slavedir = DIRECTION_UP;
1189  else
1190  slavedir = DIRECTION_DOWN;
1191 
1192  bound = determineBound(scip, worksol, master, masterdir, slave, slavedir, activities, nrows);
1193 
1194  if( !SCIPisZero(scip, bound) )
1195  {
1196  SCIP_Bool feasible;
1197 #ifndef NDEBUG
1198  SCIP_Real changedobj;
1199 #endif
1200 
1201  SCIPdebugMsg(scip, " Promising candidates {%s=%g, %s=%g} with objectives <%g>, <%g> to be set to {%g, %g}\n",
1202  SCIPvarGetName(master), mastersolval, SCIPvarGetName(slave), slavesolval,
1203  masterobj, slaveobj, mastersolval + (int)masterdir * bound, slavesolval + (int)slavedir * bound);
1204 
1205 #ifndef NDEBUG
1206  /* the improvement of objective function is calculated */
1207  changedobj = ((int)slavedir * slaveobj + (int)masterdir * masterobj) * bound;
1208  assert(SCIPisFeasLT(scip, changedobj, 0.0));
1209 #endif
1210 
1212  /* try to change the solution values of the variables */
1213  feasible = FALSE;
1214  SCIP_CALL( shiftValues(scip, master, slave, mastersolval, masterdir, slavesolval, slavedir, bound,
1215  activities, nrows, &feasible) );
1216 
1217  if( feasible )
1218  {
1219  /* The variables' solution values were successfully shifted and can hence be updated. */
1220  assert(SCIPisFeasIntegral(scip, mastersolval + ((int)masterdir * bound)));
1221  assert(SCIPisFeasIntegral(scip, slavesolval + ((int)slavedir * bound)));
1222 
1223  SCIP_CALL( SCIPsetSolVal(scip, worksol, master, mastersolval + (int)masterdir * bound) );
1224  SCIP_CALL( SCIPsetSolVal(scip, worksol, slave, slavesolval + (int)slavedir * bound) );
1225  SCIPdebugMsg(scip, " Feasible shift: <%s>[%g, %g] (obj: %f) <%f> --> <%f>\n",
1226  SCIPvarGetName(master), SCIPvarGetLbGlobal(master), SCIPvarGetUbGlobal(master), masterobj, mastersolval, SCIPgetSolVal(scip, worksol, master));
1227  SCIPdebugMsg(scip, " <%s>[%g, %g] (obj: %f) <%f> --> <%f>\n",
1228  SCIPvarGetName(slave), SCIPvarGetLbGlobal(slave), SCIPvarGetUbGlobal(slave), slaveobj, slavesolval, SCIPgetSolVal(scip, worksol, slave));
1229 
1230 #ifdef SCIP_STATISTIC
1231  /* update statistics */
1232  if( opttype == OPTTYPE_BINARY )
1233  ++(heurdata->binnexchanges);
1234  else
1235  ++(heurdata->intnexchanges);
1236 #endif
1237 
1238  *improvement = TRUE;
1239  }
1240  }
1241  }
1242  TERMINATE:
1243  SCIPfreeBufferArray(scip, &bestdirections);
1244  SCIPfreeBufferArray(scip, &objchanges);
1245  SCIPfreeBufferArray(scip, &bestslaves);
1246  SCIPfreeBufferArray(scip, &bestmasters);
1247 
1248  return SCIP_OKAY;
1249 }
1250 
1251 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1252 static
1253 SCIP_DECL_HEUREXIT(heurExitTwoopt)
1255  SCIP_HEURDATA* heurdata;
1256 
1257  heurdata = SCIPheurGetData(heur);
1258  assert(heurdata != NULL);
1259 
1260  /*ensure that initialization was successful */
1261  assert(heurdata->nbinvars <= 1 || heurdata->binvars != NULL);
1262 
1263 #ifdef SCIP_STATISTIC
1264  /* print relevant statistics to console */
1266  " Twoopt Binary Statistics : "
1267  "%6.2g %6.2g %4.2g %4.0g %6d (blocks/run, variables/run, varpercentage, avg. block size, max block size) \n",
1268  heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->binnblocks/(heurdata->nruns),
1269  heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->binnblockvars/(heurdata->nruns),
1270  heurdata->ntotalbinvars == 0 ? 0.0 : (SCIP_Real)heurdata->binnblockvars/(heurdata->ntotalbinvars) * 100.0,
1271  heurdata->binnblocks == 0 ? 0.0 : heurdata->binnblockvars/(SCIP_Real)(heurdata->binnblocks),
1272  heurdata->maxbinblocksize);
1273 
1275  " Twoopt Integer statistics : "
1276  "%6.2g %6.2g %4.2g %4.0g %6d (blocks/run, variables/run, varpercentage, avg block size, max block size) \n",
1277  heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->intnblocks/(heurdata->nruns),
1278  heurdata->nruns == 0 ? 0.0 : (SCIP_Real)heurdata->intnblockvars/(heurdata->nruns),
1279  heurdata->ntotalintvars == 0 ? 0.0 : (SCIP_Real)heurdata->intnblockvars/(heurdata->ntotalintvars) * 100.0,
1280  heurdata->intnblocks == 0 ? 0.0 : heurdata->intnblockvars/(SCIP_Real)(heurdata->intnblocks),
1281  heurdata->maxintblocksize);
1282 
1284  " Twoopt results : "
1285  "%6d %6d %4d %4.2g (runs, binary exchanges, Integer shiftings, matching rate)\n",
1286  heurdata->nruns,
1287  heurdata->binnexchanges,
1288  heurdata->intnexchanges,
1289  heurdata->matchingrate);
1290 
1291  /* set statistics to initial values*/
1292  heurdata->binnblockvars = 0;
1293  heurdata->binnblocks = 0;
1294  heurdata->intnblocks = 0;
1295  heurdata->intnblockvars = 0;
1296  heurdata->binnexchanges = 0;
1297  heurdata->intnexchanges = 0;
1298 #endif
1299 
1300  /* free the allocated memory for the binary variables */
1301  if( heurdata->binvars != NULL )
1302  {
1303  SCIPfreeBlockMemoryArray(scip, &heurdata->binvars, heurdata->nbinvars);
1304  }
1305 
1306  if( heurdata->nbinblocks > 0 )
1307  {
1308  assert(heurdata->binblockstart != NULL);
1309  assert(heurdata->binblockend != NULL);
1310 
1311  SCIPfreeBlockMemoryArray(scip, &heurdata->binblockstart, heurdata->nbinblocks);
1312  SCIPfreeBlockMemoryArray(scip, &heurdata->binblockend, heurdata->nbinblocks);
1313  }
1314  heurdata->nbinvars = 0;
1315  heurdata->nbinblocks = 0;
1316 
1317  if( heurdata->nintblocks > 0 )
1318  {
1319  assert(heurdata->intblockstart != NULL);
1320  assert(heurdata->intblockend != NULL);
1321 
1322  SCIPfreeBlockMemoryArray(scip, &heurdata->intblockstart, heurdata->nintblocks);
1323  SCIPfreeBlockMemoryArray(scip, &heurdata->intblockend, heurdata->nintblocks);
1324  }
1325 
1326  /* free the allocated memory for the integers */
1327  if( heurdata->intvars != NULL )
1328  {
1329  SCIPfreeBlockMemoryArray(scip, &heurdata->intvars, heurdata->nintvars);
1330  }
1331 
1332  heurdata->nbinblocks = 0;
1333  heurdata->nintblocks = 0;
1334  heurdata->nbinvars = 0;
1335  heurdata->nintvars = 0;
1336 
1337  assert(heurdata->binvars == NULL);
1338  assert(heurdata->intvars == NULL);
1339 
1340  /* free random number generator */
1341  SCIPrandomFree(&heurdata->randnumgen);
1342 
1343  SCIPheurSetData(heur, heurdata);
1344 
1345  return SCIP_OKAY;
1346 }
1347 
1348 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1349 static
1350 SCIP_DECL_HEURINITSOL(heurInitsolTwoopt)
1352  SCIP_HEURDATA* heurdata;
1353  assert(heur != NULL);
1354  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1355  assert(scip != NULL);
1356 
1357  /* get heuristic data */
1358  heurdata = SCIPheurGetData(heur);
1359 
1360  assert(heurdata != NULL);
1361  assert(heurdata->binvars == NULL && heurdata->intvars == NULL);
1362  assert(heurdata->binblockstart == NULL && heurdata->binblockend == NULL);
1363  assert(heurdata->intblockstart == NULL && heurdata->intblockend == NULL);
1364 
1365  /* set heuristic data to initial values, but increase the total number of runs */
1366  heurdata->nbinvars = 0;
1367  heurdata->nintvars = 0;
1368  heurdata->lastsolindex = -1;
1369  heurdata->presolved = FALSE;
1370 
1371 #ifdef SCIP_STATISTIC
1372  ++(heurdata->nruns);
1373 #endif
1374 
1375  SCIPheurSetData(heur, heurdata);
1376 
1377  return SCIP_OKAY;
1378 }
1379 
1380 
1381 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1382 static
1383 SCIP_DECL_HEUREXITSOL(heurExitsolTwoopt)
1385  SCIP_HEURDATA* heurdata;
1386  int nbinvars;
1387  int nintvars;
1388 
1389  assert(heur != NULL);
1390  assert(scip != NULL);
1391  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1392  assert(scip != NULL);
1393 
1394  /* get heuristic data */
1395  heurdata = SCIPheurGetData(heur);
1396 
1397  assert(heurdata != NULL);
1398 
1399  nbinvars = heurdata->nbinvars;
1400  nintvars = heurdata->nintvars;
1401 
1402  /* free the allocated memory for the binary variables */
1403  if( heurdata->binvars != NULL )
1404  {
1405  SCIPfreeBlockMemoryArray(scip, &heurdata->binvars, nbinvars);
1406  }
1407  if( heurdata->binblockstart != NULL )
1408  {
1409  assert(heurdata->binblockend != NULL);
1410 
1411  SCIPfreeBlockMemoryArray(scip, &heurdata->binblockstart, heurdata->nbinblocks);
1412  SCIPfreeBlockMemoryArray(scip, &heurdata->binblockend, heurdata->nbinblocks);
1413  }
1414  heurdata->nbinvars = 0;
1415  heurdata->nbinblocks = 0;
1416 
1417  if( heurdata->intblockstart != NULL )
1418  {
1419  assert(heurdata->intblockend != NULL);
1420 
1421  SCIPfreeBlockMemoryArray(scip, &heurdata->intblockstart, heurdata->nintblocks);
1422  SCIPfreeBlockMemoryArray(scip, &heurdata->intblockend, heurdata->nintblocks);
1423  }
1424  heurdata->nintblocks = 0;
1425 
1426  /* free the allocated memory for the integers */
1427  if( heurdata->intvars != NULL )
1428  {
1429  SCIPfreeBlockMemoryArray(scip, &heurdata->intvars, nintvars);
1430  }
1431 
1432  heurdata->nintvars = 0;
1433 
1434  assert(heurdata->binvars == NULL && heurdata->intvars == NULL);
1435  assert(heurdata->binblockstart == NULL && heurdata->binblockend == NULL);
1436  assert(heurdata->intblockstart == NULL && heurdata->intblockend == NULL);
1437 
1438  /* set heuristic data */
1439  SCIPheurSetData(heur, heurdata);
1440 
1441  return SCIP_OKAY;
1442 }
1443 
1444 /** execution method of primal heuristic */
1445 static
1446 SCIP_DECL_HEUREXEC(heurExecTwoopt)
1447 { /*lint --e{715}*/
1448  SCIP_HEURDATA* heurdata;
1449  SCIP_SOL* bestsol;
1450  SCIP_SOL* worksol;
1451  SCIP_ROW** lprows;
1452  SCIP_Real* activities;
1453  SCIP_COL** cols;
1454  int ncols;
1455  int nbinvars;
1456  int nintvars;
1457  int ndiscvars;
1458  int nlprows;
1459  int i;
1460  int ncolsforsorting;
1461  SCIP_Bool improvement;
1462  SCIP_Bool presolthiscall;
1463  SCIP_Bool varboundserr;
1464 
1465  assert(heur != NULL);
1466  assert(scip != NULL);
1467  assert(result != NULL);
1468 
1469  /* get heuristic data */
1470  heurdata = SCIPheurGetData(heur);
1471  assert(heurdata != NULL);
1472 
1473  *result = SCIP_DIDNOTRUN;
1474 
1475  /* we need an LP */
1476  if( SCIPgetNLPRows(scip) == 0 )
1477  return SCIP_OKAY;
1478 
1479  bestsol = SCIPgetBestSol(scip);
1480 
1481  /* ensure that heuristic has not already been processed on current incumbent */
1482  if( bestsol == NULL || heurdata->lastsolindex == SCIPsolGetIndex(bestsol) )
1483  return SCIP_OKAY;
1484 
1485  heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
1486 
1487  /* we can only work on solutions valid in the transformed space */
1488  if( SCIPsolIsOriginal(bestsol) )
1489  return SCIP_OKAY;
1490 
1491 #ifdef SCIP_DEBUG
1492  SCIP_CALL( SCIPprintSol(scip, bestsol, NULL, TRUE) );
1493 #endif
1494 
1495  /* ensure that the user defined number of nodes after last best solution has been reached, return otherwise */
1496  if( (SCIPgetNNodes(scip) - SCIPsolGetNodenum(bestsol)) < heurdata->waitingnodes )
1497  return SCIP_OKAY;
1498 
1499  presolthiscall = FALSE;
1500  SCIP_CALL( SCIPgetLPColsData(scip,&cols, &ncols) );
1501  ndiscvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1502  ncolsforsorting = MIN(ncols, ndiscvars);
1503 
1504  /* ensure that heuristic specific presolve is applied when heuristic is executed first */
1505  if( !heurdata->presolved )
1506  {
1507  SCIP_CALL( SCIPgetLPColsData(scip,&cols, &ncols) );
1508 
1509  for( i = 0; i < ncolsforsorting; ++i )
1510  SCIPcolSort(cols[i]);
1511 
1512  SCIP_CALL( presolveTwoOpt(scip, heur, heurdata) );
1513  presolthiscall = TRUE;
1514  }
1515 
1516  assert(heurdata->presolved);
1517 
1518  SCIPdebugMsg(scip, " Twoopt heuristic is %sexecuting.\n", heurdata->execute ? "" : "not ");
1519  /* ensure that presolve has detected structures in the problem to which the 2-optimization can be applied.
1520  * That is if variables exist which share a common set of LP-rows. */
1521  if( !heurdata->execute )
1522  return SCIP_OKAY;
1523 
1524  nbinvars = heurdata->nbinvars;
1525  nintvars = heurdata->nintvars;
1526  ndiscvars = nbinvars + nintvars;
1527 
1528  /* we need to be able to start diving from current node in order to resolve the LP
1529  * with continuous or implicit integer variables
1530  */
1531  if( SCIPgetNVars(scip) > ndiscvars && ( !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) )
1532  return SCIP_OKAY;
1533 
1534  /* problem satisfies all necessary conditions for 2-optimization heuristic, execute heuristic! */
1535  *result = SCIP_DIDNOTFIND;
1536 
1537  /* initialize a working solution as a copy of the current incumbent to be able to store
1538  * possible improvements obtained by 2-optimization */
1539  SCIP_CALL( SCIPcreateSolCopy(scip, &worksol, bestsol) );
1540  SCIPsolSetHeur(worksol, heur);
1541 
1542  /* get the LP row activities from current incumbent bestsol */
1543  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
1544  SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
1545 
1546  for( i = 0; i < nlprows; i++ )
1547  {
1548  SCIP_ROW* row;
1549 
1550  row = lprows[i];
1551  assert(row != NULL);
1552  assert(SCIProwGetLPPos(row) == i);
1553  SCIPdebugMsg(scip, " Row <%d> is %sin LP: \n", i, SCIProwGetLPPos(row) >= 0 ? "" : "not ");
1554  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
1555  activities[i] = SCIPgetRowSolActivity(scip, row, bestsol);
1556 
1557  /* Heuristic does not provide infeasibility recovery, thus if any constraint is violated,
1558  * execution has to be terminated.
1559  */
1560  if( !SCIProwIsLocal(row) && (SCIPisFeasLT(scip, activities[i], SCIProwGetLhs(row))
1561  || SCIPisFeasGT(scip, activities[i], SCIProwGetRhs(row))) )
1562  goto TERMINATE;
1563  }
1564 
1565  if( !presolthiscall )
1566  {
1567  for( i = 0; i < ncolsforsorting; ++i )
1568  SCIPcolSort(cols[i]);
1569  }
1570  SCIPdebugMsg(scip, " Twoopt heuristic has initialized activities and sorted rows! \n");
1571 
1572  /* start with binary optimization */
1573  improvement = FALSE;
1574  varboundserr = FALSE;
1575 
1576  if( heurdata->nbinblocks > 0 )
1577  {
1578  SCIP_CALL( optimize(scip, worksol, heurdata->binvars, heurdata->binblockstart, heurdata->binblockend, heurdata->nbinblocks,
1579  OPTTYPE_BINARY, activities, nlprows, &improvement, &varboundserr, heurdata) );
1580 
1581  SCIPdebugMsg(scip, " Binary Optimization finished!\n");
1582  }
1583 
1584  if( varboundserr )
1585  goto TERMINATE;
1586 
1587  /* ensure that their are at least two integer variables which do not have the same coefficient
1588  * in the objective function. In one of these cases, the heuristic will automatically skip the
1589  * integer variable optimization */
1590  if( heurdata->nintblocks > 0 )
1591  {
1592  assert(heurdata->intopt);
1593  SCIP_CALL( optimize(scip, worksol, heurdata->intvars, heurdata->intblockstart, heurdata->intblockend, heurdata->nintblocks,
1594  OPTTYPE_INTEGER, activities, nlprows, &improvement, &varboundserr, heurdata) );
1595 
1596  SCIPdebugMsg(scip, " Integer Optimization finished!\n");
1597  }
1598 
1599  if( ! improvement || varboundserr )
1600  goto TERMINATE;
1601 
1602  if( SCIPgetNVars(scip) == ndiscvars )
1603  {
1604  /* the problem is a pure IP, hence, no continuous or implicit variables are left for diving.
1605  * try if new working solution is feasible in original problem */
1606  SCIP_Bool success;
1607 #ifndef NDEBUG
1608  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1609 #else
1610  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
1611 #endif
1612 
1613  if( success )
1614  {
1615  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
1616  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
1617  heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
1618  *result = SCIP_FOUNDSOL;
1619 
1620 #ifdef SCIP_STATISTIC
1621  SCIPstatisticMessage("***Twoopt improved solution found by %10s . \n",
1622  SCIPsolGetHeur(bestsol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(bestsol)) :"Tree");
1623 #endif
1624  }
1625  }
1626  /* fix the integer variables and start diving to optimize continuous variables with respect to reduced domain */
1627  else
1628  {
1629  SCIP_VAR** allvars;
1630  SCIP_Bool lperror;
1631 #ifdef NDEBUG
1632  SCIP_RETCODE retstat;
1633 #endif
1634 
1635  SCIPdebugMsg(scip, "shifted solution should be feasible -> solve LP to fix continuous variables to best values\n");
1636 
1637  allvars = SCIPgetVars(scip);
1638 
1639 #ifdef SCIP_DEBUG
1640  for( i = ndiscvars; i < SCIPgetNVars(scip); ++i )
1641  {
1642  SCIPdebugMsg(scip, " Cont. variable <%s>, status %d with bounds [%g <= %g <= x <= %g <= %g]\n",
1643  SCIPvarGetName(allvars[i]), SCIPvarGetStatus(allvars[i]), SCIPvarGetLbGlobal(allvars[i]), SCIPvarGetLbLocal(allvars[i]), SCIPvarGetUbLocal(allvars[i]),
1644  SCIPvarGetUbGlobal(allvars[i]));
1645  }
1646 #endif
1647 
1648  /* start diving to calculate the LP relaxation */
1649  SCIP_CALL( SCIPstartDive(scip) );
1650 
1651  /* set the bounds of the variables: fixed for integers, global bounds for continuous */
1652  for( i = 0; i < SCIPgetNVars(scip); ++i )
1653  {
1654  if( SCIPvarGetStatus(allvars[i]) == SCIP_VARSTATUS_COLUMN )
1655  {
1656  SCIP_CALL( SCIPchgVarLbDive(scip, allvars[i], SCIPvarGetLbGlobal(allvars[i])) );
1657  SCIP_CALL( SCIPchgVarUbDive(scip, allvars[i], SCIPvarGetUbGlobal(allvars[i])) );
1658  }
1659  }
1660 
1661  /* apply this after global bounds to not cause an error with intermediate empty domains */
1662  for( i = 0; i < ndiscvars; ++i )
1663  {
1664  if( SCIPvarGetStatus(allvars[i]) == SCIP_VARSTATUS_COLUMN )
1665  {
1666  SCIP_Real solval;
1667 
1668  solval = SCIPgetSolVal(scip, worksol, allvars[i]);
1669 
1670  assert(SCIPvarGetType(allvars[i]) != SCIP_VARTYPE_CONTINUOUS && SCIPisFeasIntegral(scip, solval));
1671 
1672  SCIP_CALL( SCIPchgVarLbDive(scip, allvars[i], solval) );
1673  SCIP_CALL( SCIPchgVarUbDive(scip, allvars[i], solval) );
1674  }
1675  }
1676  for( i = 0; i < ndiscvars; ++i )
1677  {
1678  assert( SCIPisFeasEQ(scip, SCIPgetVarLbDive(scip, allvars[i]), SCIPgetVarUbDive(scip, allvars[i])) );
1679  }
1680  /* solve LP */
1681  SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1682 
1683  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1684  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
1685 #ifdef NDEBUG
1686  retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
1687  if( retstat != SCIP_OKAY )
1688  {
1689  SCIPwarningMessage(scip, "Error while solving LP in Twoopt heuristic; LP solve terminated with code <%d>\n",retstat);
1690  }
1691 #else
1692  SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
1693 #endif
1694 
1695  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1696  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
1697 
1698  /* check if this is a feasible solution */
1699  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
1700  {
1701  SCIP_Bool success;
1702 
1703  /* copy the current LP solution to the working solution */
1704  SCIP_CALL( SCIPlinkLPSol(scip, worksol) );
1705 
1706  /* check solution for feasibility */
1707 #ifndef NDEBUG
1708  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1709 #else
1710  SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
1711 #endif
1712 
1713  if( success )
1714  {
1715  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
1716  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) );
1717  heurdata->lastsolindex = SCIPsolGetIndex(bestsol);
1718  *result = SCIP_FOUNDSOL;
1719 
1720 #ifdef SCIP_STATISTIC
1721  SCIPstatisticMessage("*** Twoopt improved solution found by %10s . \n",
1722  SCIPsolGetHeur(bestsol) != NULL ? SCIPheurGetName(SCIPsolGetHeur(bestsol)) :"Tree");
1723 #endif
1724  }
1725  }
1726 
1727  /* terminate the diving */
1728  SCIP_CALL( SCIPendDive(scip) );
1729  }
1730 
1731  TERMINATE:
1732  SCIPdebugMsg(scip, "Termination of Twoopt heuristic\n");
1733  SCIPfreeBufferArray(scip, &activities);
1734  SCIP_CALL( SCIPfreeSol(scip, &worksol) );
1735 
1736  return SCIP_OKAY;
1737 }
1738 
1739 /*
1740  * primal heuristic specific interface methods
1741  */
1742 
1743 /** creates the twoopt primal heuristic and includes it in SCIP */
1745  SCIP* scip /**< SCIP data structure */
1746  )
1747 {
1748  SCIP_HEURDATA* heurdata;
1749  SCIP_HEUR* heur;
1750 
1751  /* create Twoopt primal heuristic data */
1752  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1753 
1754  /* include primal heuristic */
1755  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1757  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTwoopt, heurdata) );
1758 
1759  assert(heur != NULL);
1760 
1761  /* set non-NULL pointers to callback methods */
1762  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTwoopt) );
1763  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeTwoopt) );
1764  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitTwoopt) );
1765  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitTwoopt) );
1766  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolTwoopt) );
1767  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolTwoopt) );
1768 
1769  /* include boolean flag intopt */
1770  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/twoopt/intopt", " Should Integer-2-Optimization be applied or not?",
1771  &heurdata->intopt, TRUE, DEFAULT_INTOPT, NULL, NULL) );
1772 
1773  /* include parameter waitingnodes */
1774  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/twoopt/waitingnodes", "user parameter to determine number of "
1775  "nodes to wait after last best solution before calling heuristic",
1776  &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0, 10000, NULL, NULL));
1777 
1778  /* include parameter maxnslaves */
1779  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/twoopt/maxnslaves", "maximum number of slaves for one master variable",
1780  &heurdata->maxnslaves, TRUE, DEFAULT_MAXNSLAVES, -1, 1000000, NULL, NULL) );
1781 
1782  /* include parameter matchingrate */
1783  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/twoopt/matchingrate",
1784  "parameter to determine the percentage of rows two variables have to share before they are considered equal",
1785  &heurdata->matchingrate, TRUE, DEFAULT_MATCHINGRATE, 0.0, 1.0, NULL, NULL) );
1786 
1787  return SCIP_OKAY;
1788 }
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2299
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8159
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21975
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11770
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46385
static SCIP_RETCODE shiftValues(SCIP *scip, SCIP_VAR *master, SCIP_VAR *slave, SCIP_Real mastersolval, DIRECTION masterdir, SCIP_Real slavesolval, DIRECTION slavedir, SCIP_Real shiftval, SCIP_Real *activities, int nrows, SCIP_Bool *feasible)
Definition: heur_twoopt.c:128
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21964
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
Primal heuristic to improve incumbent solution by flipping pairs of variables.
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37847
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21958
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41609
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46333
static SCIP_DECL_HEURFREE(heurFreeTwoopt)
Definition: heur_twoopt.c:810
void SCIPsortRealPtrPtrInt(SCIP_Real *realarray, void **ptrarray1, void **ptrarray2, int *intarray, int len)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16270
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8127
static long bound
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46110
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16450
#define DEFAULT_WAITINGNODES
Definition: heur_twoopt.c:42
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46372
#define DEFAULT_MAXNSLAVES
Definition: heur_twoopt.c:46
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
#define DEFAULT_INTOPT
Definition: heur_twoopt.c:41
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16391
#define FALSE
Definition: def.h:64
static SCIP_RETCODE optimize(SCIP *scip, SCIP_SOL *worksol, SCIP_VAR **vars, int *blockstart, int *blockend, int nblocks, OPTTYPE opttype, SCIP_Real *activities, int nrows, SCIP_Bool *improvement, SCIP_Bool *varboundserr, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:890
#define HEUR_FREQ
Definition: heur_twoopt.c:33
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46122
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:34772
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
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.c:8034
#define HEUR_FREQOFS
Definition: heur_twoopt.c:34
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:8723
static SCIP_DECL_SORTPTRCOMP(SCIPvarcolComp)
Definition: heur_twoopt.c:276
#define HEUR_NAME
Definition: heur_twoopt.c:29
#define HEUR_TIMING
Definition: heur_twoopt.c:37
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29217
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
static SCIP_DECL_HEURINITSOL(heurInitsolTwoopt)
Definition: heur_twoopt.c:1351
Direction
Definition: heur_twoopt.c:111
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46445
#define DEFAULT_RANDSEED
Definition: heur_twoopt.c:48
static SCIP_DECL_HEURINIT(heurInitTwoopt)
Definition: heur_twoopt.c:830
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:21970
static SCIP_DECL_HEUREXIT(heurExitTwoopt)
Definition: heur_twoopt.c:1254
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip.c:37468
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:34998
static SCIP_RETCODE presolveTwoOpt(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:715
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8143
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35031
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16260
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16500
static SCIP_DECL_HEUREXEC(heurExecTwoopt)
Definition: heur_twoopt.c:1447
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2382
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29351
static int varColCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: heur_twoopt.c:233
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46359
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46346
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16401
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28863
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38042
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
#define DEFAULT_ARRAYSIZE
Definition: heur_twoopt.c:47
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2362
#define HEUR_DESC
Definition: heur_twoopt.c:30
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:34804
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2423
#define MAX(x, y)
Definition: tclique_def.h:75
static SCIP_RETCODE innerPresolve(SCIP *scip, SCIP_VAR **vars, SCIP_VAR ***varspointer, int nvars, int *nblocks, int *maxblocksize, int *nblockvars, int **blockstart, int **blockend, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:616
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25561
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37806
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
enum Direction DIRECTION
Definition: heur_twoopt.c:117
Opttype
Definition: heur_twoopt.c:103
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16883
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip.c:30843
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.c:39976
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11725
#define DEFAULT_MATCHINGRATE
Definition: heur_twoopt.c:43
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
enum Opttype OPTTYPE
Definition: heur_twoopt.c:108
static SCIP_DECL_HEURCOPY(heurCopyTwoopt)
Definition: heur_twoopt.c:796
SCIP_RETCODE SCIPincludeHeurTwoopt(SCIP *scip)
Definition: heur_twoopt.c:1745
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16235
#define HEUR_MAXDEPTH
Definition: heur_twoopt.c:35
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39158
static void disposeVariable(SCIP_VAR **vars, int *blockend, int varindex)
Definition: heur_twoopt.c:601
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11635
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16674
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:16580
#define SCIP_Real
Definition: def.h:145
#define HEUR_PRIORITY
Definition: heur_twoopt.c:32
#define MIN(x, y)
Definition: memory.c:75
#define HEUR_USESSUBSCIP
Definition: heur_twoopt.c:38
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30892
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:34969
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip.c:34607
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:16460
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46421
void SCIPcolSort(SCIP_COL *col)
Definition: lp.c:3304
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29295
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip.c:34650
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
#define HEUR_DISPCHAR
Definition: heur_twoopt.c:31
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
static SCIP_DECL_HEUREXITSOL(heurExitsolTwoopt)
Definition: heur_twoopt.c:1384
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16746
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38182
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2413
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
static SCIP_Bool checkConstraintMatching(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real matchingrate)
Definition: heur_twoopt.c:285
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
static SCIP_Real determineBound(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *master, DIRECTION masterdirection, SCIP_VAR *slave, DIRECTION slavedirection, SCIP_Real *activities, int nrows)
Definition: heur_twoopt.c:377
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:21995
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38601