Scippy

SCIP

Solving Constraint Integer Programs

heur_shiftandpropagate.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-2014 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_shiftandpropagate.c
17  * @brief shiftandpropagate primal heuristic
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_shiftandpropagate.h"
27 
28 #define HEUR_NAME "shiftandpropagate"
29 #define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"
30 #define HEUR_DISPCHAR 'T'
31 #define HEUR_PRIORITY 1000
32 #define HEUR_FREQ 0
33 #define HEUR_FREQOFS 0
34 #define HEUR_MAXDEPTH -1
35 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
36 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
37 
38 #define DEFAULT_WEIGHT_INEQUALITY 1 /**< the heuristic row weight for inequalities */
39 #define DEFAULT_WEIGHT_EQUALITY 3 /**< the heuristic row weight for equations */
40 #define DEFAULT_RELAX TRUE /**< Should continuous variables be relaxed from the problem? */
41 #define DEFAULT_PROBING TRUE /**< Is propagation of solution values enabled? */
42 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */
43 #define DEFAULT_NPROPROUNDS 10 /**< The default number of propagation rounds for each propagation used */
44 #define DEFAULT_PROPBREAKER 65000 /**< fixed maximum number of propagations */
45 #define DEFAULT_CUTOFFBREAKER 15 /**< fixed maximum number of allowed cutoffs before the heuristic stops */
46 #define DEFAULT_RANDSEED 3141598 /**< the default random seed for random number generation */
47 #define DEFAULT_SORTKEY 'v' /**< the default key for variable sorting */
48 #define DEFAULT_SORTVARS TRUE /**< should variables be processed in sorted order? */
49 #define DEFAULT_COLLECTSTATS TRUE /**< should variable statistics be collected during probing? */
50 #define DEFAULT_STOPAFTERFEASIBLE TRUE /**< Should the heuristic stop calculating optimal shift values when no more rows are violated? */
51 #define DEFAULT_PREFERBINARIES TRUE /**< Should binary variables be shifted first? */
52 #define SORTKEYS "nrtuv"/**< options sorting key: (n)orms down, norms (u)p, (v)iolated rows decreasing,
53  * viola(t)ed rows increasing, or (r)andom */
54 #define DEFAULT_NOZEROFIXING FALSE /**< should variables with a zero shifting value be delayed instead of being fixed? */
55 #define DEFAULT_FIXBINLOCKS TRUE /**< should binary variables with no locks in one direction be fixed to that direction? */
56 #define DEFAULT_NORMALIZE TRUE /**< should coefficients and left/right hand sides be normalized by max row coeff? */
57 #define DEFAULT_UPDATEWEIGHTS FALSE /**< should row weight be increased every time the row is violated? */
58 #define DEFAULT_IMPLISCONTINUOUS TRUE /**< should implicit integer variables be treated as continuous variables? */
59 
60 #define EVENTHDLR_NAME "eventhdlrshiftandpropagate"
61 #define EVENTHDLR_DESC "event handler to catch bound changes"
62 
63 /*
64  * Data structures
65  */
66 
67 /** primal heuristic data */
68 struct SCIP_HeurData
69 {
70  SCIP_COL** lpcols; /**< stores lp columns with discrete variables before cont. variables */
71  int* rowweights; /**< row weight storage */
72  SCIP_Bool relax; /**< should continuous variables be relaxed from the problem */
73  SCIP_Bool probing; /**< should probing be executed? */
74  SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */
75  int nlpcols; /**< the number of lp columns */
76  int nproprounds; /**< The default number of propagation rounds for each propagation used */
77  int cutoffbreaker; /**< the number of cutoffs before heuristic execution is stopped, or -1 for no
78  * limit */
79  SCIP_EVENTHDLR* eventhdlr; /**< event handler to register and process variable bound changes */
80 
81  unsigned int randseed; /**< seed for random number generation */
82  char sortkey; /**< the key by which variables are sorted */
83  SCIP_Bool sortvars; /**< should variables be processed in sorted order? */
84  SCIP_Bool collectstats; /**< should variable statistics be collected during probing? */
85  SCIP_Bool stopafterfeasible; /**< Should the heuristic stop calculating optimal shift values when no
86  * more rows are violated? */
87  SCIP_Bool preferbinaries; /**< Should binary variables be shifted first? */
88  SCIP_Bool nozerofixing; /**< should variables with a zero shifting value be delayed instead of being fixed? */
89  SCIP_Bool fixbinlocks; /**< should binary variables with no locks in one direction be fixed to that direction? */
90  SCIP_Bool normalize; /**< should coefficients and left/right hand sides be normalized by max row coeff? */
91  SCIP_Bool updateweights; /**< should row weight be increased every time the row is violated? */
92  SCIP_Bool impliscontinuous; /**< should implicit integer variables be treated as continuous variables? */
93  SCIPstatistic(
94  SCIP_LPSOLSTAT lpsolstat; /**< the probing status after probing */
95  SCIP_Longint ntotaldomredsfound; /**< the total number of domain reductions during heuristic */
96  SCIP_Longint nlpiters; /**< number of LP iterations which the heuristic needed */
97  int nremainingviols; /**< the number of remaining violations */
98  int nprobings; /**< how many probings has the heuristic executed? */
99  int ncutoffs; /**< has the probing node been cutoff? */
100  int nredundantrows; /**< how many rows were redundant after relaxation? */
101  )
102 };
103 
104 /** status of a variable in heuristic transformation */
105 enum TransformStatus
106 {
107  TRANSFORMSTATUS_NONE = 0, /**< variable has not been transformed yet */
108  TRANSFORMSTATUS_LB = 1, /**< variable has been shifted by using lower bound (x-lb) */
109  TRANSFORMSTATUS_NEG = 2, /**< variable has been negated by using upper bound (ub-x) */
110  TRANSFORMSTATUS_FREE = 3 /**< variable does not have to be shifted */
111 };
112 typedef enum TransformStatus TRANSFORMSTATUS;
113 
114 /** information about the matrix after its heuristic transformation */
115 struct ConstraintMatrix
116 {
117  SCIP_Real* rowmatvals; /**< matrix coefficients row by row */
118  int* rowmatind; /**< the indices of the corresponding variables */
119  int* rowmatbegin; /**< the starting indices of each row */
120  SCIP_Real* colmatvals; /**< matrix coefficients column by column */
121  int* colmatind; /**< the indices of the corresponding rows for each coefficient */
122  int* colmatbegin; /**< the starting indices of each column */
123  TRANSFORMSTATUS* transformstatus; /**< information about transform status of every discrete variable */
124  SCIP_Real* lhs; /**< left hand side vector after normalization */
125  SCIP_Real* rhs; /**< right hand side vector after normalization */
126  SCIP_Real* colnorms; /**< vector norms of all discrete problem variables after normalization */
127  SCIP_Real* upperbounds; /**< the upper bounds of every non-continuous variable after transformation*/
128  SCIP_Real* transformshiftvals; /**< values by which original discrete variable bounds were shifted */
129  int nnonzs; /**< number of nonzero column entries */
130  int nrows; /**< number of rows of matrix */
131  int ncols; /**< the number of columns in matrix (including continuous vars) */
132  int ndiscvars; /**< number of discrete problem variables */
133  SCIP_Bool normalized; /**< indicates if the matrix data has already been normalized */
134 };
135 typedef struct ConstraintMatrix CONSTRAINTMATRIX;
136 
137 struct SCIP_EventhdlrData
138 {
139  CONSTRAINTMATRIX* matrix; /**< the constraint matrix of the heuristic */
140  SCIP_HEURDATA* heurdata; /**< heuristic data */
141  int* violatedrows; /**< all currently violated LP rows */
142  int* violatedrowpos; /**< position in violatedrows array for every row */
143  int* nviolatedrows; /**< pointer to the total number of currently violated rows */
144 };
145 
146 struct SCIP_EventData
147 {
148  int colpos; /**< column position of the event-related variable */
149 };
150 /*
151  * Local methods
152  */
153 
154 /** returns whether a given variable is counted as discrete, depending on the parameter impliscontinuous */
155 static
156 SCIP_Bool varIsDiscrete(
157  SCIP_VAR* var, /**< variable to check for discreteness */
158  SCIP_Bool impliscontinuous /**< should implicit integer variables be counted as continuous? */
159  )
160 {
161  return SCIPvarIsIntegral(var) && (SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT || !impliscontinuous);
162 }
163 
164 /** returns whether a given column is counted as discrete, depending on the parameter impliscontinuous */
165 static
166 SCIP_Bool colIsDiscrete(
167  SCIP_COL* col, /**< column to check for discreteness */
168  SCIP_Bool impliscontinuous /**< should implicit integer variables be counted as continuous? */
169  )
170 {
171  return SCIPcolIsIntegral(col) && (!impliscontinuous || SCIPvarGetType(SCIPcolGetVar(col)) != SCIP_VARTYPE_IMPLINT);
172 }
173 
174 /** returns nonzero values and corresponding columns of given row */
175 static
176 void getRowData(
177  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
178  int rowindex, /**< index of the desired row */
179  SCIP_Real** valpointer, /**< pointer to store the nonzero coefficients of the row */
180  SCIP_Real* lhs, /**< lhs of the row */
181  SCIP_Real* rhs, /**< rhs of the row */
182  int** indexpointer, /**< pointer to store column indices which belong to the nonzeros */
183  int* nrowvals /**< pointer to store number of nonzeros in the desired row */
184  )
185 {
186  int arrayposition;
187 
188  assert(matrix != NULL);
189  assert(0 <= rowindex && rowindex < matrix->nrows);
190 
191  arrayposition = matrix->rowmatbegin[rowindex];
192 
193  if( nrowvals != NULL && rowindex == matrix->nrows - 1 )
194  *nrowvals = matrix->nnonzs - arrayposition;
195  else if( nrowvals != NULL )
196  *nrowvals = matrix->rowmatbegin[rowindex + 1] - arrayposition;
197 
198  if( valpointer != NULL )
199  *valpointer = &(matrix->rowmatvals[arrayposition]);
200  if( indexpointer != NULL )
201  *indexpointer = &(matrix->rowmatind[arrayposition]);
202 
203  if( lhs != NULL )
204  *lhs = matrix->lhs[rowindex];
205 
206  if( rhs != NULL )
207  *rhs = matrix->rhs[rowindex];
208 }
209 
210 /** returns nonzero values and corresponding rows of given column */
211 static
212 void getColumnData(
213  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
214  int colindex, /**< the index of the desired column */
215  SCIP_Real** valpointer, /**< pointer to store the nonzero coefficients of the column */
216  int** indexpointer, /**< pointer to store row indices which belong to the nonzeros */
217  int* ncolvals /**< pointer to store number of nonzeros in the desired column */
218  )
219 {
220  int arrayposition;
221 
222  assert(matrix != NULL);
223  assert(0 <= colindex && colindex < matrix->ncols);
224 
225  arrayposition = matrix->colmatbegin[colindex];
226 
227  if( ncolvals != NULL )
228  {
229  if( colindex == matrix->ncols - 1 )
230  *ncolvals = matrix->nnonzs - arrayposition;
231  else
232  *ncolvals = matrix->colmatbegin[colindex + 1] - arrayposition;
233  }
234  if( valpointer != NULL )
235  *valpointer = &(matrix->colmatvals[arrayposition]);
236 
237  if( indexpointer != NULL )
238  *indexpointer = &(matrix->colmatind[arrayposition]);
239 }
240 
241 /** relaxes a continuous variable from all its rows, which has influence
242  * on both the left and right hand side of the constraint.
243  */
244 static
245 void relaxVar(
246  SCIP* scip, /**< current scip instance */
247  SCIP_VAR* var, /**< variable which is relaxed from the problem */
248  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
249  SCIP_Bool normalize /**< should coefficients and be normalized by rows maximum norms? */
250  )
251 {
252  SCIP_ROW** colrows;
253  SCIP_COL* varcol;
254  SCIP_Real* colvals;
255  SCIP_Real ub;
256  SCIP_Real lb;
257  int ncolvals;
258  int r;
259 
260  assert(var != NULL);
261  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
262 
263  varcol = SCIPvarGetCol(var);
264  assert(varcol != NULL);
265 
266  /* get nonzero values and corresponding rows of variable */
267  colvals = SCIPcolGetVals(varcol);
268  ncolvals = SCIPcolGetNLPNonz(varcol);
269  colrows = SCIPcolGetRows(varcol);
270 
271  ub = SCIPvarGetUbGlobal(var);
272  lb = SCIPvarGetLbGlobal(var);
273 
274  assert(colvals != NULL || ncolvals == 0);
275 
276  SCIPdebugMessage("Relaxing variable <%s> with lb <%g> and ub <%g>\n",
277  SCIPvarGetName(var), lb, ub);
278 
279  assert(matrix->normalized);
280  /* relax variable from all its constraints */
281  for( r = 0; r < ncolvals; ++r )
282  {
283  SCIP_ROW* colrow;
284  SCIP_Real lhs;
285  SCIP_Real rhs;
286  SCIP_Real lhsvarbound;
287  SCIP_Real rhsvarbound;
288  SCIP_Real rowabs;
289  SCIP_Real colval;
290  int rowindex;
291 
292  colrow = colrows[r];
293  rowindex = SCIProwGetLPPos(colrow);
294 
295  if( rowindex == -1 )
296  break;
297 
298  rowabs = SCIPgetRowMaxCoef(scip, colrow);
299  assert(colvals != NULL); /* to please flexelint */
300  colval = colvals[r];
301  if( normalize && SCIPisFeasGT(scip, rowabs, 0.0) )
302  colval /= rowabs;
303 
304  assert(0 <= rowindex && rowindex < matrix->nrows);
305  getRowData(matrix, rowindex, NULL, &lhs, &rhs, NULL, NULL);
306  /* variables bound influence the lhs and rhs of current row depending on the sign
307  * of the variables coefficient.
308  */
309  if( SCIPisFeasPositive(scip, colval) )
310  {
311  lhsvarbound = ub;
312  rhsvarbound = lb;
313  }
314  else if( SCIPisFeasNegative(scip, colval) )
315  {
316  lhsvarbound = lb;
317  rhsvarbound = ub;
318  }
319  else
320  continue;
321 
322  /* relax variable from the current row */
323  if( !SCIPisInfinity(scip, -matrix->lhs[rowindex]) && !SCIPisInfinity(scip, ABS(lhsvarbound)) )
324  matrix->lhs[rowindex] -= colval * lhsvarbound;
325  else
326  matrix->lhs[rowindex] = -SCIPinfinity(scip);
327 
328  if( !SCIPisInfinity(scip, matrix->rhs[rowindex]) && !SCIPisInfinity(scip, ABS(rhsvarbound)) )
329  matrix->rhs[rowindex] -= colval * rhsvarbound;
330  else
331  matrix->rhs[rowindex] = SCIPinfinity(scip);
332 
333  SCIPdebugMessage("Row <%s> changed:Coefficient <%g>, LHS <%g> --> <%g>, RHS <%g> --> <%g>\n",
334  SCIProwGetName(colrow), colval, lhs, matrix->lhs[rowindex], rhs, matrix->rhs[rowindex]);
335  }
336 }
337 
338 /** transforms bounds of a given variable s.t. its lower bound equals zero afterwards.
339  * If the variable already has lower bound zero, the variable is not transformed,
340  * if not, the variable's bounds are changed w.r.t. the smaller absolute value of its
341  * bounds in order to avoid numerical inaccuracies. If both lower and upper bound
342  * of the variable differ from infinity, there are two cases. If |lb| <= |ub|,
343  * the bounds are shifted by -lb, else a new variable ub - x replaces x.
344  * The transformation is memorized by the transform status of the variable s.t.
345  * retransformation is possible.
346  */
347 static
348 void transformVariable(
349  SCIP* scip, /**< current scip instance */
350  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
351  SCIP_HEURDATA* heurdata, /**< heuristic data */
352  int colpos /**< position of variable column in matrix */
353  )
354 {
355  SCIP_COL* col;
356  SCIP_VAR* var;
357  SCIP_Real lb;
358  SCIP_Real ub;
359 
360  SCIP_Bool negatecoeffs; /* do the row coefficients need to be negated? */
361  SCIP_Real deltashift; /* difference from previous transformation */
362 
363  assert(matrix != NULL);
364  assert(0 <= colpos && colpos < heurdata->nlpcols);
365  col = heurdata->lpcols[colpos];
366  assert(col != NULL);
367  assert(SCIPcolIsInLP(col));
368 
369  var = SCIPcolGetVar(col);
370  assert(var != NULL);
371  assert(SCIPvarIsIntegral(var));
372  lb = SCIPvarGetLbLocal(var);
373  ub = SCIPvarGetUbLocal(var);
374 
375  deltashift = 0.0;
376  negatecoeffs = FALSE;
377  /* if both lower and upper bound are -infinity and infinity, resp., this is reflected by a free transform status.
378  * If the lower bound is already zero, this is reflected by identity transform status. In both cases, none of the
379  * corresponding rows needs to be modified.
380  */
381  if( SCIPisInfinity(scip, -lb) && SCIPisInfinity(scip, ub) )
382  {
383  if( matrix->transformstatus[colpos] == TRANSFORMSTATUS_NEG )
384  negatecoeffs = TRUE;
385 
386  deltashift = matrix->transformshiftvals[colpos];
387  matrix->transformshiftvals[colpos] = 0.0;
388  matrix->transformstatus[colpos] = TRANSFORMSTATUS_FREE;
389  }
390  else if( SCIPisFeasLE(scip, ABS(lb), ABS(ub)) )
391  {
392  assert(!SCIPisInfinity(scip, lb));
393  matrix->transformstatus[colpos] = TRANSFORMSTATUS_LB;
394  deltashift = lb;
395  matrix->transformshiftvals[colpos] = lb;
396  }
397  else
398  {
399  assert(!SCIPisInfinity(scip, ub));
400  if( matrix->transformstatus[colpos] != TRANSFORMSTATUS_NEG )
401  negatecoeffs = TRUE;
402  matrix->transformstatus[colpos] = TRANSFORMSTATUS_NEG;
403  deltashift = ub;
404  matrix->transformshiftvals[colpos] = ub;
405  }
406 
407  /* determine the upper bound for this variable in heuristic transformation (lower bound is implicit; always 0) */
408  if( !SCIPisInfinity(scip, ub) && !SCIPisInfinity(scip, lb) )
409  matrix->upperbounds[colpos] = ub - lb;
410  else
411  matrix->upperbounds[colpos] = SCIPinfinity(scip);
412 
413  /* a real transformation is necessary. The variable x is either shifted by -lb or
414  * replaced by ub - x, depending on the smaller absolute of lb and ub.
415  */
416  if( !SCIPisFeasZero(scip, deltashift) || negatecoeffs )
417  {
418  SCIP_Real* vals;
419  int* rows;
420 
421  int nrows;
422  int i;
423 
424  assert(!SCIPisInfinity(scip, deltashift));
425 
426  /* get nonzero values and corresponding rows of column */
427  getColumnData(matrix, colpos, &vals, &rows, &nrows);
428  assert(nrows == 0 ||(vals != NULL && rows != NULL));
429 
430  /* go through rows and modify its lhs, rhs and the variable coefficient, if necessary */
431  for( i = 0; i < nrows; ++i )
432  {
433  assert(rows[i] >= 0);
434  assert(rows[i] < matrix->nrows);
435 
436  if( !SCIPisInfinity(scip, -(matrix->lhs[rows[i]])) )
437  matrix->lhs[rows[i]] -= (vals[i]) * deltashift;
438 
439  if( !SCIPisInfinity(scip, matrix->rhs[rows[i]]) )
440  matrix->rhs[rows[i]] -= (vals[i]) * deltashift;
441 
442  if( negatecoeffs )
443  (vals[i]) = -(vals[i]);
444 
445  assert(SCIPisFeasLE(scip, matrix->lhs[rows[i]], matrix->rhs[rows[i]]));
446  }
447  }
448  SCIPdebugMessage("Variable <%s> at colpos %d transformed. LB <%g> --> <%g>, UB <%g> --> <%g>\n",
449  SCIPvarGetName(var), colpos, lb, 0.0, ub, matrix->upperbounds[colpos]);
450 }
451 
452 /** initializes copy of the original coefficient matrix and applies heuristic specific adjustments: normalizing row
453  * vectors, transforming variable domains such that lower bound is zero, and relaxing continuous variables.
454  */
455 static
456 SCIP_RETCODE initMatrix(
457  SCIP* scip, /**< current scip instance */
458  CONSTRAINTMATRIX* matrix, /**< constraint matrix object to be initialized */
459  SCIP_HEURDATA* heurdata, /**< heuristic data */
460  SCIP_Bool normalize, /**< should coefficients and be normalized by rows maximum norms? */
461  int* nmaxrows, /**< maximum number of rows a variable appears in */
462  SCIP_Bool relax, /**< should continuous variables be relaxed from the problem? */
463  SCIP_Bool* initialized, /**< was the initialization successful? */
464  SCIP_Bool* infeasible /**< is the problem infeasible? */
465  )
466 {
467  SCIP_ROW** lprows;
468  SCIP_COL** lpcols;
469  SCIP_Bool impliscontinuous;
470  int i;
471  int j;
472  int currentpointer;
473 
474  int nrows;
475  int ncols;
476 
477  assert(scip != NULL);
478  assert(matrix != NULL);
479  assert(initialized!= NULL);
480  assert(infeasible != NULL);
481  assert(nmaxrows != NULL);
482 
483  SCIPdebugMessage("entering Matrix Initialization method of SHIFTANDPROPAGATE heuristic!\n");
484 
485  /* get LP row data; column data is already initialized in heurdata */
486  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nrows) );
487  lpcols = heurdata->lpcols;
488  ncols = heurdata->nlpcols;
489 
490  matrix->nrows = nrows;
491  matrix->nnonzs = 0;
492  matrix->normalized = FALSE;
493  matrix->ndiscvars = 0;
494  *nmaxrows = 0;
495  impliscontinuous = heurdata->impliscontinuous;
496 
497  /* count the number of nonzeros of the LP constraint matrix */
498  for( j = 0; j < ncols; ++j )
499  {
500  assert(lpcols[j] != NULL);
501  assert(SCIPcolGetLPPos(lpcols[j]) >= 0);
502 
503  if( colIsDiscrete(lpcols[j], impliscontinuous) )
504  {
505  matrix->nnonzs += SCIPcolGetNLPNonz(lpcols[j]);
506  ++matrix->ndiscvars;
507  }
508  }
509 
510  matrix->ncols = matrix->ndiscvars;
511 
512  if( matrix->nnonzs == 0 )
513  {
514  SCIPdebugMessage("No matrix entries - Terminating initialization of matrix.\n");
515 
516  *initialized = FALSE;
517 
518  return SCIP_OKAY;
519  }
520 
521  /* allocate memory for the members of heuristic matrix */
522  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->rowmatvals, matrix->nnonzs) );
523  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->rowmatind, matrix->nnonzs) );
524  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->colmatvals, matrix->nnonzs) );
525  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->colmatind, matrix->nnonzs) );
526  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->rowmatbegin, nrows) );
527  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->colmatbegin, matrix->ncols) );
528  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->lhs, matrix->nrows) );
529  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->rhs, matrix->nrows) );
530  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->colnorms, matrix->ncols) );
531  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->transformstatus, matrix->ndiscvars) );
532  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->upperbounds, matrix->ndiscvars) );
533  SCIP_CALL( SCIPallocMemoryArray(scip, &matrix->transformshiftvals, matrix->ndiscvars) );
534 
535  /* set transform status of variables */
536  for( j = 0; j < matrix->ndiscvars; ++j )
537  matrix->transformstatus[j] = TRANSFORMSTATUS_NONE;
538 
539  currentpointer = 0;
540  *infeasible = FALSE;
541 
542  /* initialize the rows vector of the heuristic matrix together with its corresponding
543  * lhs, rhs.
544  */
545  for( i = 0; i < nrows; ++i )
546  {
547  SCIP_COL** cols;
548  SCIP_ROW* row;
549  SCIP_Real* rowvals;
550  SCIP_Real constant;
551  SCIP_Real maxval;
552  int nrowlpnonz;
553 
554  /* get LP row information */
555  row = lprows[i];
556  rowvals = SCIProwGetVals(row);
557  nrowlpnonz = SCIProwGetNLPNonz(row);
558  maxval = SCIPgetRowMaxCoef(scip, row);
559  cols = SCIProwGetCols(row);
560  constant = SCIProwGetConstant(row);
561 
562  SCIPdebugMessage(" %s : lhs=%g, rhs=%g, maxval=%g \n", SCIProwGetName(row), matrix->lhs[i], matrix->rhs[i], maxval);
563  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
564  assert(!SCIPisInfinity(scip, constant));
565 
566  matrix->rowmatbegin[i] = currentpointer;
567 
568  /* modify the lhs and rhs w.r.t to the rows constant and normalize by 1-norm, i.e divide the lhs and rhs by the
569  * maximum absolute value of the row
570  */
571  if( !SCIPisInfinity(scip, -SCIProwGetLhs(row)) )
572  matrix->lhs[i] = (SCIProwGetLhs(row) - constant);
573  else
574  matrix->lhs[i] = -SCIPinfinity(scip);
575 
576  if( !SCIPisInfinity(scip, SCIProwGetRhs(row)) )
577  matrix->rhs[i] = (SCIProwGetRhs(row) - constant);
578  else
579  matrix->rhs[i] = SCIPinfinity(scip);
580 
581  /* make sure that maxval is larger than zero before normalization.
582  * Maxval may be zero if the constraint contains no variables but is modifiable, hence not redundant
583  */
584  if( normalize && !SCIPisFeasZero(scip, maxval) )
585  {
586  if( !SCIPisInfinity(scip, -matrix->lhs[i]) )
587  matrix->lhs[i] /= maxval;
588  if( !SCIPisInfinity(scip, matrix->rhs[i]) )
589  matrix->rhs[i] /= maxval;
590  }
591 
592 
593  /* in case of empty rows with a 0 < lhs <= 0.0 or 0.0 <= rhs < 0 we deduce the infeasibility of the problem */
594  if( nrowlpnonz == 0 && (SCIPisFeasPositive(scip, matrix->lhs[i]) || SCIPisFeasNegative(scip, matrix->rhs[i])) )
595  {
596  *infeasible = TRUE;
597  SCIPdebugMessage(" Matrix initialization stopped because of row infeasibility! \n");
598  break;
599  }
600 
601  /* row coefficients are normalized and copied to heuristic matrix */
602  for( j = 0; j < nrowlpnonz; ++j )
603  {
604  if( !colIsDiscrete(cols[j], impliscontinuous) )
605  continue;
606  assert(SCIPcolGetLPPos(cols[j]) >= 0);
607  assert(currentpointer < matrix->nnonzs);
608 
609  matrix->rowmatvals[currentpointer] = rowvals[j];
610  if( normalize && SCIPisFeasGT(scip, maxval, 0.0) )
611  matrix->rowmatvals[currentpointer] /= maxval;
612 
613  matrix->rowmatind[currentpointer] = SCIPcolGetLPPos(cols[j]);
614 
615  ++currentpointer;
616  }
617  }
618 
619  matrix->normalized = TRUE;
620 
621  if( *infeasible )
622  return SCIP_OKAY;
623 
624  assert(currentpointer == matrix->nnonzs);
625 
626  currentpointer = 0;
627 
628  /* copy the nonzero coefficient data column by column to heuristic matrix */
629  for( j = 0; j < matrix->ncols; ++j )
630  {
631  SCIP_COL* currentcol;
632  SCIP_ROW** rows;
633  SCIP_Real* colvals;
634  int ncolnonz;
635 
636 
637  assert(SCIPcolGetLPPos(lpcols[j]) >= 0);
638 
639  currentcol = lpcols[j];
640  assert(colIsDiscrete(currentcol, impliscontinuous));
641 
642  colvals = SCIPcolGetVals(currentcol);
643  rows = SCIPcolGetRows(currentcol);
644  ncolnonz = SCIPcolGetNLPNonz(currentcol);
645  matrix->colnorms[j] = ncolnonz;
646 
647  *nmaxrows = MAX(*nmaxrows, ncolnonz);
648 
649  /* loop over all rows with nonzero coefficients in the column, transform them and add them to the heuristic matrix */
650  matrix->colmatbegin[j] = currentpointer;
651 
652  for( i = 0; i < ncolnonz; ++i )
653  {
654  SCIP_Real maxval;
655 
656  assert(rows[i] != NULL);
657  assert(0 <= SCIProwGetLPPos(rows[i]));
658  assert(SCIProwGetLPPos(rows[i]) < nrows);
659  assert(currentpointer < matrix->nnonzs);
660 
661  /* rows are normalized by maximum norm */
662  maxval = SCIPgetRowMaxCoef(scip, rows[i]);
663 
664  assert(maxval > 0);
665 
666  matrix->colmatvals[currentpointer] = colvals[i];
667  if( normalize && SCIPisFeasGT(scip, maxval, 0.0) )
668  matrix->colmatvals[currentpointer] /= maxval;
669 
670  matrix->colmatind[currentpointer] = SCIProwGetLPPos(rows[i]);
671 
672  /* update the column norm */
673  matrix->colnorms[j] += ABS(matrix->colmatvals[currentpointer]);
674 
675  ++currentpointer;
676  }
677  }
678  assert(currentpointer == matrix->nnonzs);
679 
680  /* each variable is either transformed, if it supposed to be integral, or relaxed */
681  for( j = 0; j < (relax ? ncols : matrix->ndiscvars); ++j )
682  {
683  SCIP_COL* col;
684 
685  col = lpcols[j];
686  if( colIsDiscrete(col, impliscontinuous) )
687  {
688  matrix->transformshiftvals[j] = 0.0;
689  transformVariable(scip, matrix, heurdata, j);
690  }
691  else
692  {
693  SCIP_VAR* var;
694  var = SCIPcolGetVar(col);
695  assert(!varIsDiscrete(var, impliscontinuous));
696  relaxVar(scip, var, matrix, normalize);
697  }
698  }
699  *initialized = TRUE;
700 
701  SCIPdebugMessage("Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n",
702  matrix->ndiscvars, matrix->ncols, matrix->nrows, matrix->nnonzs);
703  return SCIP_OKAY;
704 }
705 
706 /** frees all members of the heuristic matrix */
707 static
708 void freeMatrix(
709  SCIP* scip, /**< current SCIP instance */
710  CONSTRAINTMATRIX** matrix /**< constraint matrix object */
711  )
712 {
713  assert(scip != NULL);
714  assert(matrix != NULL);
715 
716  /* all fields are only allocated, if problem is not empty */
717  if( (*matrix)->nnonzs > 0 )
718  {
719  assert((*matrix) != NULL);
720  assert((*matrix)->rowmatbegin != NULL);
721  assert((*matrix)->rowmatvals != NULL);
722  assert((*matrix)->rowmatind != NULL);
723  assert((*matrix)->colmatbegin != NULL);
724  assert((*matrix)->colmatvals!= NULL);
725  assert((*matrix)->colmatind != NULL);
726  assert((*matrix)->lhs != NULL);
727  assert((*matrix)->rhs != NULL);
728  assert((*matrix)->transformstatus != NULL);
729  assert((*matrix)->transformshiftvals != NULL);
730 
731  /* free all fields */
732  SCIPfreeMemoryArray(scip, &((*matrix)->rowmatbegin));
733  SCIPfreeMemoryArray(scip, &((*matrix)->rowmatvals));
734  SCIPfreeMemoryArray(scip, &((*matrix)->rowmatind));
735  SCIPfreeMemoryArray(scip, &((*matrix)->colmatvals));
736  SCIPfreeMemoryArray(scip, &((*matrix)->colmatind));
737  SCIPfreeMemoryArray(scip, &((*matrix)->colmatbegin));
738  SCIPfreeMemoryArray(scip, &((*matrix)->lhs));
739  SCIPfreeMemoryArray(scip, &((*matrix)->rhs));
740  SCIPfreeMemoryArray(scip, &((*matrix)->colnorms));
741  SCIPfreeMemoryArray(scip, &((*matrix)->transformstatus));
742  SCIPfreeMemoryArray(scip, &((*matrix)->upperbounds));
743  SCIPfreeMemoryArray(scip, &((*matrix)->transformshiftvals));
744 
745  (*matrix)->nrows = 0;
746  (*matrix)->ncols = 0;
747  }
748 
749  /* free matrix */
750  SCIPfreeBuffer(scip, matrix);
751 }
752 
753 /** collects the necessary information about row violations for the zero-solution. That is,
754  * all solution values in heuristic transformation are zero.
755  */
756 static
757 void checkViolations(
758  SCIP* scip, /**< current scip instance */
759  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
760  int* violatedrows, /**< violated rows */
761  int* violatedrowpos, /**< row positions of violated rows */
762  int* nviolatedrows, /**< pointer to store the number of violated rows */
763  int* nredundantrows, /**< pointer to store the number of redundant rows */
764  int* violatedvarrows /**< reference to number of violated rows for every variable, or NULL */
765  )
766 {
767  SCIP_Real* rhs;
768  SCIP_Real* lhs;
769  int nrows;
770  int i;
771 
772  assert(matrix != NULL);
773  assert(violatedrows != NULL);
774  assert(violatedrowpos != NULL);
775  assert(nviolatedrows != NULL);
776 
777  /* get RHS, LHS and number of the problem rows */
778  rhs = matrix->rhs;
779  lhs = matrix->lhs;
780  nrows = matrix->nrows;
781 
782  SCIPdebugMessage("Entering violation check for %d rows! \n", nrows);
783  *nviolatedrows = 0;
784  if( nredundantrows != NULL )
785  *nredundantrows = 0;
786 
787  /* loop over rows and check if it is violated */
788  for( i = 0; i < nrows; ++i )
789  {
790  /* check, if zero solution violates this row */
791  if( SCIPisFeasLT(scip, rhs[i], 0.0) || SCIPisFeasGT(scip, lhs[i], 0.0) )
792  {
793  violatedrows[*nviolatedrows] = i;
794  (violatedrowpos)[i] = *nviolatedrows;
795  ++(*nviolatedrows);
796 
797  /* if needed, increase the counter for violated rows for every variable column of this row */
798  if( violatedvarrows != NULL )
799  {
800  int* rowcols;
801  int nrowcols;
802  int j;
803 
804  rowcols = NULL;
805  nrowcols = 0;
806  getRowData(matrix, i, NULL, NULL, NULL, &rowcols, &nrowcols);
807  assert(nrowcols == 0 || rowcols != NULL);
808 
809  for( j = 0; j < nrowcols; ++j )
810  {
811  assert(0 <= rowcols[j] && rowcols[j] < matrix->ndiscvars);
812  ++violatedvarrows[rowcols[j]];
813  }
814  }
815  }
816  else
817  violatedrowpos[i] = -1;
818 
819  assert((violatedrowpos[i] == -1 && SCIPisFeasGE(scip, rhs[i], 0.0) && SCIPisFeasGE(scip, -lhs[i], 0.0))
820  || (violatedrowpos[i] >= 0 &&(SCIPisFeasLT(scip, rhs[i], 0.0) || SCIPisFeasLT(scip, -lhs[i], 0.0))));
821 
822  if( SCIPisInfinity(scip, rhs[i]) && SCIPisInfinity(scip, -lhs[i]) && nredundantrows != NULL)
823  ++(*nredundantrows);
824  }
825 }
826 
827 /** retransforms solution values of variables according to their transformation status */
828 static
829 SCIP_Real retransformVariable(
830  SCIP* scip, /**< current scip instance */
831  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
832  SCIP_VAR* var, /**< variable whose solution value has to be retransformed */
833  int varindex, /**< permutation of variable indices according to sorting */
834  SCIP_Real solvalue /**< solution value of the variable */
835  )
836 {
837  TRANSFORMSTATUS status;
838 
839  assert(matrix != NULL);
840  assert(var != NULL);
841 
842  status = matrix->transformstatus[varindex];
843  assert(status != TRANSFORMSTATUS_NONE);
844 
845  /* check if original variable has different bounds and transform solution value correspondingly */
846  if( status == TRANSFORMSTATUS_LB )
847  {
848  assert(!SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
849 
850  return solvalue + matrix->transformshiftvals[varindex];
851  }
852  else if( status == TRANSFORMSTATUS_NEG )
853  {
854  assert(!SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
855  return matrix->transformshiftvals[varindex] - solvalue;
856  }
857  return solvalue;
858 }
859 
860 /** determines the best shifting value of a variable
861  * @todo if there is already an incumbent solution, try considering the objective cutoff as additional constraint */
862 static
863 SCIP_RETCODE getOptimalShiftingValue(
864  SCIP* scip, /**< current scip instance */
865  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
866  int varindex, /**< index of variable which should be shifted */
867  int direction, /**< the direction for this variable */
868  int* rowweights, /**< weighting of rows for best shift calculation */
869  SCIP_Real* steps, /**< buffer array to store the individual steps for individual rows */
870  int* violationchange, /**< buffer array to store the individual change of feasibility of row */
871  SCIP_Real* beststep, /**< pointer to store optimal shifting step */
872  int* rowviolations /**< pointer to store new weighted sum of row violations, i.e, v - f */
873  )
874 {
875  SCIP_Real* vals;
876  int* rows;
877 
878  SCIP_Real slacksurplus;
879  SCIP_Real upperbound;
880 
881  int nrows;
882  int sum;
883  int i;
884 
885  SCIP_Bool allzero;
886 
887  assert(beststep != NULL);
888  assert(rowviolations != NULL);
889  assert(rowweights != NULL);
890  assert(steps != NULL);
891  assert(violationchange != NULL);
892  assert(direction == 1 || direction == -1);
893 
894  upperbound = matrix->upperbounds[varindex];
895 
896  /* get nonzero values and corresponding rows of variable */
897  getColumnData(matrix, varindex, &vals, &rows, &nrows);
898 
899  /* loop over rows and calculate, which is the minimum shift to make this row feasible
900  * or the minimum shift to violate this row
901  */
902  allzero = TRUE;
903  slacksurplus = 0.0;
904  for( i = 0; i < nrows; ++i )
905  {
906  SCIP_Real lhs;
907  SCIP_Real rhs;
908  SCIP_Real val;
909  int rowpos;
910  SCIP_Bool rowisviolated;
911  int rowweight;
912 
913  /* get the row data */
914  rowpos = rows[i];
915  assert(rowpos >= 0);
916  lhs = matrix->lhs[rowpos];
917  rhs = matrix->rhs[rowpos];
918  rowweight = rowweights[rowpos];
919  val = direction * vals[i];
920 
921  /* determine if current row is violated or not */
922  rowisviolated =(SCIPisFeasLT(scip, rhs, 0.0) || SCIPisFeasLT(scip, -lhs, 0.0));
923 
924  /* for a feasible row, determine the minimum integer value within the bounds of the variable by which it has to be
925  * shifted to make row infeasible.
926  */
927  if( !rowisviolated )
928  {
929  SCIP_Real maxfeasshift;
930 
931  maxfeasshift = SCIPinfinity(scip);
932 
933  /* feasibility can only be violated if the variable has a lock in the corresponding direction,
934  * i.e. a positive coefficient for a "<="-constraint, a negative coefficient for a ">="-constraint.
935  */
936  if( SCIPisFeasGT(scip, val, 0.0) && !SCIPisInfinity(scip, rhs) )
937  maxfeasshift = SCIPfeasFloor(scip, rhs/val);
938  else if( SCIPisFeasLT(scip, val, 0.0) && !SCIPisInfinity(scip, -lhs) )
939  maxfeasshift = SCIPfeasFloor(scip, lhs/val);
940 
941  /* if the variable has no lock in the current row, it can still help to increase the slack of this row;
942  * we measure slack increase for shifting by one
943  */
944  if( SCIPisFeasGT(scip, val, 0.0) && SCIPisInfinity(scip, rhs) )
945  slacksurplus += val;
946  if( SCIPisFeasLT(scip, val, 0.0) && SCIPisInfinity(scip, -lhs) )
947  slacksurplus -= val;
948 
949  /* check if the least violating shift lies within variable bounds and set corresponding array values */
950  if( SCIPisFeasLE(scip, maxfeasshift + 1.0, upperbound) )
951  {
952  steps[i] = maxfeasshift + 1.0;
953  violationchange[i] = rowweight;
954  allzero = FALSE;
955  }
956  else
957  {
958  steps[i] = upperbound;
959  violationchange[i] = 0;
960  }
961  }
962  /* for a violated row, determine the minimum integral value within the bounds of the variable by which it has to be
963  * shifted to make row feasible.
964  */
965  else
966  {
967  SCIP_Real minfeasshift;
968 
969  minfeasshift = SCIPinfinity(scip);
970 
971  /* if coefficient has the right sign to make row feasible, determine the minimum integer to shift variable
972  * to obtain feasibility
973  */
974  if( SCIPisFeasLT(scip, -lhs, 0.0) && SCIPisFeasGT(scip, val, 0.0) )
975  minfeasshift = SCIPfeasCeil(scip, lhs/val);
976  else if( SCIPisFeasLT(scip, rhs,0.0) && SCIPisFeasLT(scip, val, 0.0) )
977  minfeasshift = SCIPfeasCeil(scip, rhs/val);
978 
979  /* check if the minimum feasibility recovery shift lies within variable bounds and set corresponding array
980  * values
981  */
982  if( !SCIPisInfinity(scip, minfeasshift) && SCIPisFeasLE(scip, minfeasshift, upperbound) )
983  {
984  steps[i] = minfeasshift;
985  violationchange[i] = -rowweight;
986  allzero = FALSE;
987  }
988  else
989  {
990  steps[i] = upperbound;
991  violationchange[i] = 0;
992  }
993  }
994  }
995 
996  /* in case that the variable cannot affect the feasibility of any row, in particular it cannot violate
997  * a single row, but we can add slack to already feasible rows, we will do this
998  */
999  if( allzero )
1000  {
1001  *beststep = SCIPisFeasGT(scip, slacksurplus, 0.0) ? direction * upperbound : 0.0;
1002  return SCIP_OKAY;
1003  }
1004 
1005  /* sorts rows by increasing value of steps */
1006  SCIPsortRealInt(steps, violationchange, nrows);
1007 
1008  *beststep = 0.0;
1009  *rowviolations = 0;
1010  sum = 0;
1011 
1012  /* best shifting step is calculated by summing up the violation changes for each relevant step and
1013  * taking the one which leads to the minimum sum. This sum measures the balance of feasibility recovering and
1014  * violating changes which will be obtained by shifting the variable by this step
1015  * note, the sums for smaller steps have to be taken into account for all bigger steps, i.e., the sums can be
1016  * computed iteratively
1017  */
1018  for( i = 0; i < nrows && !SCIPisInfinity(scip, steps[i]); ++i )
1019  {
1020  sum += violationchange[i];
1021 
1022  /* if we reached the last entry for the current step value, we have finished computing its sum and
1023  * update the step defining the minimum sum
1024  */
1025  if( (i == nrows-1 || steps[i+1] > steps[i]) && sum < *rowviolations )
1026  {
1027  *rowviolations = sum;
1028  *beststep = direction * steps[i];
1029  }
1030  }
1031  assert(*rowviolations <= 0);
1032  assert(!SCIPisInfinity(scip, *beststep));
1033 
1034  return SCIP_OKAY;
1035 }
1036 
1037 /** updates the information about a row whenever violation status changes */
1038 static
1039 void updateViolations(
1040  SCIP* scip, /**< current SCIP instance */
1041  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
1042  int rowindex, /**< index of the row */
1043  int* violatedrows, /**< contains all violated rows */
1044  int* violatedrowpos, /**< positions of rows in the violatedrows array */
1045  int* nviolatedrows, /**< pointer to update total number of violated rows */
1046  int* rowweights, /**< row weight storage */
1047  SCIP_Bool updateweights /**< should row weight be increased every time the row is violated? */
1048  )
1049 {
1050  assert(matrix != NULL);
1051  assert(violatedrows != NULL);
1052  assert(violatedrowpos != NULL);
1053  assert(nviolatedrows != NULL);
1054 
1055  /* row is now violated. Enqueue it in the set of violated rows. */
1056  if( SCIPisFeasLT(scip, -(matrix->lhs[rowindex]), 0.0) || SCIPisFeasLT(scip, matrix->rhs[rowindex], 0.0) )
1057  {
1058  assert(violatedrowpos[rowindex] == -1);
1059  assert(*nviolatedrows < matrix->nrows);
1060 
1061  violatedrows[*nviolatedrows] = rowindex;
1062  violatedrowpos[rowindex] = *nviolatedrows;
1063  ++(*nviolatedrows);
1064  if( updateweights )
1065  ++rowweights[rowindex];
1066  }
1067  /* row is now feasible. Remove it from the set of violated rows. */
1068  else
1069  {
1070  assert(violatedrowpos[rowindex] > -1);
1071 
1072  /* swap the row with last violated row */
1073  if( violatedrowpos[rowindex] != *nviolatedrows - 1 )
1074  {
1075  assert(*nviolatedrows - 1 >= 0);
1076  violatedrows[violatedrowpos[rowindex]] = violatedrows[*nviolatedrows - 1];
1077  violatedrowpos[violatedrows[*nviolatedrows - 1]] = violatedrowpos[rowindex];
1078  }
1079 
1080  /* unlink the row from its position in the array and decrease number of violated rows */
1081  violatedrowpos[rowindex] = -1;
1082  --(*nviolatedrows);
1083  }
1084 }
1085 
1086 /** updates transformation of a given variable by taking into account current local bounds. if the bounds have changed
1087  * since last update, updating the heuristic specific upper bound of the variable, its current transformed solution value
1088  * and all affected rows is necessary.
1089  */
1090 static
1091 void updateTransformation(
1092  SCIP* scip, /**< current scip */
1093  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
1094  SCIP_HEURDATA* heurdata, /**< heuristic data */
1095  int varindex, /**< index of variable in matrix */
1096  SCIP_Real* transformshiftval, /**< value, by which the variable has been shifted during transformation */
1097  SCIP_Real lb, /**< local lower bound of the variable */
1098  SCIP_Real ub, /**< local upper bound of the variable */
1099  int* violatedrows, /**< violated rows */
1100  int* violatedrowpos, /**< violated row positions */
1101  int* nviolatedrows /**< pointer to store number of violated rows */
1102  )
1103 {
1104  TRANSFORMSTATUS status;
1105  SCIP_Real deltashift;
1106 
1107  assert(scip != NULL);
1108  assert(matrix != NULL);
1109  assert(0 <= varindex && varindex < matrix->ndiscvars);
1110 
1111  /* deltashift is the difference between the old and new transformation value. */
1112  deltashift = 0.0;
1113  status = matrix->transformstatus[varindex];
1114 
1115  SCIPdebugMessage(" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1116  matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1117 
1118  /* depending on the variable status, deltashift is calculated differently. */
1119  if( status == TRANSFORMSTATUS_LB )
1120  {
1121  if( SCIPisInfinity(scip, -lb) )
1122  transformVariable(scip, matrix, heurdata, varindex);
1123  else
1124  {
1125  deltashift = lb - (*transformshiftval);
1126  *transformshiftval = lb;
1127  if( !SCIPisInfinity(scip, ub) )
1128  matrix->upperbounds[varindex] = ub - lb;
1129  else
1130  matrix->upperbounds[varindex] = SCIPinfinity(scip);
1131  }
1132  }
1133 
1134  if( status == TRANSFORMSTATUS_NEG )
1135  {
1136 
1137  if( SCIPisInfinity(scip, ub) )
1138  transformVariable(scip, matrix, heurdata, varindex);
1139  else
1140  {
1141  deltashift = (*transformshiftval) - ub;
1142  *transformshiftval = ub;
1143 
1144  if( !SCIPisInfinity(scip, -lb) )
1145  matrix->upperbounds[varindex] = ub - lb;
1146  }
1147  }
1148 
1149  if( status == TRANSFORMSTATUS_FREE )
1150  {
1151  /* in case of a free transform status, if one of the bounds has become finite, we want
1152  * to transform this variable to a variable with a lowerbound or a negated transform status */
1153  if( !SCIPisInfinity(scip, -lb) || !SCIPisInfinity(scip, ub) )
1154  {
1155  transformVariable(scip, matrix, heurdata, varindex);
1156 
1157  /* violations have to be rechecked for all rows
1158  * @todo : change this and only update violations of rows in which this variable
1159  * appears
1160  */
1161  checkViolations(scip, matrix, violatedrows, violatedrowpos, nviolatedrows, NULL, NULL);
1162 
1163  assert(matrix->transformstatus[varindex] == TRANSFORMSTATUS_LB || TRANSFORMSTATUS_NEG);
1164  assert(SCIPisFeasLE(scip, ABS(lb), ABS(ub)) || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1165  }
1166  }
1167 
1168  /* if the bound, by which the variable was shifted, has changed, deltashift is different from zero, which requires
1169  * an update of all affected rows
1170  */
1171  if( !SCIPisFeasZero(scip, deltashift) )
1172  {
1173  int i;
1174  int* rows;
1175  SCIP_Real* vals;
1176  int nrows;
1177 
1178  /* get nonzero values and corresponding rows of variable */
1179  getColumnData(matrix, varindex, &vals, &rows, &nrows);
1180 
1181  /* go through rows, update the rows w.r.t. the influence of the changed transformation of the variable */
1182  for( i = 0; i < nrows; ++i )
1183  {
1184  SCIP_Bool updaterow;
1185  SCIP_Bool leftviolation;
1186  SCIP_Bool rightviolation;
1187 
1188  SCIPdebugMessage(" update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n",
1189  rows[i], vals[i], matrix->lhs[rows[i]], matrix->rhs[rows[i]]);
1190 
1191  /* the row has to be updated if either lhs or rhs changes its sign. */
1192  leftviolation = SCIPisFeasLT(scip, -(matrix->lhs[rows[i]]), 0.0);
1193 
1194  if( !SCIPisInfinity(scip, -(matrix->lhs[rows[i]])) )
1195  matrix->lhs[rows[i]] -= (vals[i]) * deltashift;
1196 
1197  updaterow = leftviolation != SCIPisFeasLT(scip, -(matrix->lhs[rows[i]]), 0.0);
1198 
1199  rightviolation = SCIPisFeasLT(scip,(matrix->rhs[rows[i]]), 0.0);
1200  if( !SCIPisInfinity(scip, matrix->rhs[rows[i]]) )
1201  matrix->rhs[rows[i]] -= (vals[i]) * deltashift;
1202 
1203  updaterow = updaterow != (rightviolation != SCIPisFeasLT(scip,(matrix->rhs[rows[i]]), 0.0));
1204 
1205  /* update the row violation */
1206  if( updaterow )
1207  updateViolations(scip, matrix, rows[i], violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1208 
1209  SCIPdebugMessage(" --> %g <= 0 <= %g %s\n",
1210  matrix->lhs[rows[i]], matrix->rhs[rows[i]], updaterow ? ": row violation updated " : "");
1211  }
1212  }
1213  SCIPdebugMessage(" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1214  matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1215 }
1216 
1217 /** comparison method for columns; binary < integer < implicit < continuous variables */
1218 static
1219 SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
1220 {
1221  SCIP_COL* col1;
1222  SCIP_COL* col2;
1223  SCIP_VAR* var1;
1224  SCIP_VAR* var2;
1225  SCIP_VARTYPE vartype1;
1226  SCIP_VARTYPE vartype2;
1227  int key1;
1228  int key2;
1229 
1230  col1 = (SCIP_COL*)elem1;
1231  col2 = (SCIP_COL*)elem2;
1232  var1 = SCIPcolGetVar(col1);
1233  var2 = SCIPcolGetVar(col2);
1234  assert(var1 != NULL && var2 != NULL);
1235 
1236  vartype1 = SCIPvarGetType(var1);
1237  vartype2 = SCIPvarGetType(var2);
1238 
1239  switch (vartype1)
1240  {
1241  case SCIP_VARTYPE_BINARY:
1242  key1 = 1;
1243  break;
1244  case SCIP_VARTYPE_INTEGER:
1245  key1 = 2;
1246  break;
1247  case SCIP_VARTYPE_IMPLINT:
1248  key1 = 3;
1249  break;
1250  case SCIP_VARTYPE_CONTINUOUS:
1251  key1 = 4;
1252  break;
1253  default:
1254  key1 = -1;
1255  SCIPerrorMessage("unknown variable type\n");
1256  SCIPABORT();
1257  break;
1258  }
1259  switch (vartype2)
1260  {
1261  case SCIP_VARTYPE_BINARY:
1262  key2 = 1;
1263  break;
1264  case SCIP_VARTYPE_INTEGER:
1265  key2 = 2;
1266  break;
1267  case SCIP_VARTYPE_IMPLINT:
1268  key2 = 3;
1269  break;
1270  case SCIP_VARTYPE_CONTINUOUS:
1271  key2 = 4;
1272  break;
1273  default:
1274  key2 = -1;
1275  SCIPerrorMessage("unknown variable type\n");
1276  SCIPABORT();
1277  break;
1278  }
1279  return key1 - key2;
1280 }
1281 
1282 /*
1283  * Callback methods of primal heuristic
1284  */
1285 
1286 /** deinitialization method of primal heuristic(called before transformed problem is freed) */
1287 static
1288 SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
1289 { /*lint --e{715}*/
1290  /* if statistic mode is enabled, statistics are printed to console */
1291  SCIPstatistic(
1292  SCIP_HEURDATA* heurdata;
1293 
1294  heurdata = SCIPheurGetData(heur);
1295 
1296  assert(heurdata != NULL);
1297 
1298  SCIPstatisticMessage(
1299  " DETAILS : %d violations left, %d probing status, %d redundant rows\n",
1300  heurdata->nremainingviols,
1301  heurdata->lpsolstat,
1302  heurdata->nredundantrows);
1303  SCIPstatisticMessage(
1304  " SHIFTANDPROPAGATE PROBING : %d probings, %lld domain reductions, ncutoffs: %d , LP iterations: %lld \n ",
1305  heurdata->nprobings,
1306  heurdata->ntotaldomredsfound,
1307  heurdata->ncutoffs,
1308  heurdata->nlpiters);
1309  );
1310 
1311  return SCIP_OKAY;
1312 }
1313 
1314 /** initialization method of primal heuristic(called after problem was transformed). We only need this method for
1315  * statistic mode of heuristic.
1316  */
1317 static
1318 SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
1319 { /*lint --e{715}*/
1320 
1321  SCIP_HEURDATA* heurdata;
1322 
1323  heurdata = SCIPheurGetData(heur);
1324 
1325  assert(heurdata != NULL);
1326 
1327  heurdata->randseed = DEFAULT_RANDSEED;
1328 
1329  SCIPstatistic(
1330  heurdata->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
1331  heurdata->nremainingviols = 0;
1332  heurdata->nprobings = 0;
1333  heurdata->ntotaldomredsfound = 0;
1334  heurdata->ncutoffs = 0;
1335  heurdata->nlpiters = 0;
1336  heurdata->nredundantrows = 0;
1337  )
1338  return SCIP_OKAY;
1339 }
1340 
1341 /** destructor of primal heuristic to free user data(called when SCIP is exiting) */
1342 static
1343 SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
1344 { /*lint --e{715}*/
1345  SCIP_HEURDATA* heurdata;
1346  SCIP_EVENTHDLR* eventhdlr;
1347  SCIP_EVENTHDLRDATA* eventhdlrdata;
1348 
1349  heurdata = SCIPheurGetData(heur);
1350  eventhdlr = heurdata->eventhdlr;
1351  assert(eventhdlr != NULL);
1352  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1353 
1354  SCIPfreeMemory(scip, &eventhdlrdata);
1355 
1356  /* free heuristic data */
1357  if( heurdata != NULL )
1358  SCIPfreeMemory(scip, &heurdata);
1359 
1360  SCIPheurSetData(heur, NULL);
1361 
1362  return SCIP_OKAY;
1363 }
1364 
1365 
1366 /** copy method for primal heuristic plugins(called when SCIP copies plugins) */
1367 static
1368 SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
1369 { /*lint --e{715}*/
1370  assert(scip != NULL);
1371  assert(heur != NULL);
1372  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1373 
1374  /* call inclusion method of primal heuristic */
1375  SCIP_CALL( SCIPincludeHeurShiftandpropagate(scip) );
1376 
1377  return SCIP_OKAY;
1378 }
1379 
1380 /** execution method of primal heuristic */
1381 static
1382 SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
1383 { /*lint --e{715}*/
1384  SCIP_HEURDATA* heurdata; /* heuristic data */
1385  SCIP_EVENTHDLR* eventhdlr; /* shiftandpropagate event handler */
1386  SCIP_EVENTHDLRDATA* eventhdlrdata; /* event handler data */
1387  SCIP_EVENTDATA** eventdatas; /* event data for every variable */
1388 
1389  CONSTRAINTMATRIX* matrix; /* constraint matrix object */
1390  SCIP_COL** lpcols; /* lp columns */
1391  SCIP_SOL* sol; /* solution pointer */
1392  SCIP_Real* colnorms; /* contains Euclidean norms of column vectors */
1393 
1394  SCIP_Real* steps; /* buffer arrays for best shift selection in main loop */
1395  int* violationchange;
1396 
1397  int* violatedrows; /* the violated rows */
1398  int* violatedrowpos; /* the array position of a violated row, or -1 */
1399  int* permutation; /* reflects the position of the variables after sorting */
1400  int* violatedvarrows; /* number of violated rows for each variable */
1401  int nlpcols; /* number of lp columns */
1402  int nviolatedrows; /* number of violated rows */
1403  int ndiscvars; /* number of non-continuous variables of the problem */
1404  int lastindexofsusp; /* last variable which has been swapped due to a cutoff */
1405  int nbinvars; /* number of binary variables */
1406  int nintvars; /* number of integer variables */
1407  int i;
1408  int r;
1409  int v;
1410  int c;
1411  int ncutoffs; /* counts the number of cutoffs for this execution */
1412  int nprobings; /* counts the number of probings */
1413  int nredundantrows; /* the number of redundant rows */
1414  int nlprows; /* the number LP rows */
1415  int nmaxrows; /* maximum number of LP rows of a variable */
1416 
1417  SCIP_Bool initialized; /* has the matrix been initialized? */
1418  SCIP_Bool cutoff; /* has current probing node been cutoff? */
1419  SCIP_Bool probing; /* should probing be applied or not? */
1420  SCIP_Bool infeasible; /* FALSE as long as currently infeasible rows have variables left */
1421  SCIP_Bool impliscontinuous;
1422 
1423  heurdata = SCIPheurGetData(heur);
1424  assert(heurdata != NULL);
1425 
1426  eventhdlr = heurdata->eventhdlr;
1427  assert(eventhdlr != NULL);
1428 
1429  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1430  assert(eventhdlrdata != NULL);
1431 
1432  *result = SCIP_DIDNOTRUN;
1433  SCIPdebugMessage("entering execution method of shift and propagate heuristic\n");
1434 
1435  /* heuristic is obsolete if there are only continuous variables */
1436  if( SCIPgetNVars(scip) - SCIPgetNContVars(scip) == 0 )
1437  return SCIP_OKAY;
1438 
1439  /* stop execution method if there is already a primarily feasible solution at hand */
1440  if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
1441  return SCIP_OKAY;
1442 
1443  /* stop if there is no LP available */
1444  if ( ! SCIPhasCurrentNodeLP(scip) )
1445  return SCIP_OKAY;
1446 
1447  if( !SCIPisLPConstructed(scip) )
1448  {
1449  SCIP_Bool nodecutoff;
1450 
1451  nodecutoff = FALSE;
1452  /* @note this call can have the side effect that variables are created */
1453  SCIP_CALL( SCIPconstructLP(scip, &nodecutoff) );
1454  SCIP_CALL( SCIPflushLP(scip) );
1455  }
1456 
1457  SCIPstatistic( heurdata->nlpiters = SCIPgetNLPIterations(scip) );
1458 
1459  nlprows = SCIPgetNLPRows(scip);
1460 
1461  SCIP_CALL( SCIPgetLPColsData(scip, &lpcols, &nlpcols) );
1462  assert(nlpcols == 0 || lpcols != NULL);
1463 
1464  /* we need an LP */
1465  if( nlprows == 0 || nlpcols == 0 )
1466  return SCIP_OKAY;
1467 
1468 
1469  *result = SCIP_DIDNOTFIND;
1470  initialized = FALSE;
1471 
1472  /* allocate lp column array */
1473  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->lpcols, nlpcols) );
1474  heurdata->nlpcols = nlpcols;
1475 
1476  impliscontinuous = heurdata->impliscontinuous;
1477 
1478 #ifndef NDEBUG
1479  BMSclearMemoryArray(heurdata->lpcols, nlpcols);
1480 #endif
1481 
1482  BMScopyMemoryArray(heurdata->lpcols, lpcols, nlpcols);
1483 
1484  SCIPsortPtr((void**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);
1485 
1486  /* we have to collect the number of different variable types before we start probing since during probing variable
1487  * can be created (e.g., cons_xor.c)
1488  */
1489  ndiscvars = 0;
1490  nbinvars = 0;
1491  nintvars = 0;
1492  for( c = 0; c < nlpcols; ++c )
1493  {
1494  SCIP_COL* col;
1495  SCIP_VAR* colvar;
1496 
1497  col = heurdata->lpcols[c];
1498  assert(col != NULL);
1499  colvar = SCIPcolGetVar(col);
1500  assert(colvar != NULL);
1501 
1502  if( varIsDiscrete(colvar, impliscontinuous) )
1503  ++ndiscvars;
1504  if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY )
1505  ++nbinvars;
1506  else if( SCIPvarGetType(colvar) == SCIP_VARTYPE_INTEGER )
1507  ++nintvars;
1508  }
1509  assert(nbinvars + nintvars <= ndiscvars);
1510 
1511  /* start probing mode */
1512  SCIP_CALL( SCIPstartProbing(scip) );
1513 
1514  /* enables collection of variable statistics during probing */
1515  if( heurdata->collectstats )
1516  SCIPenableVarHistory(scip);
1517  else
1518  SCIPdisableVarHistory(scip);
1519 
1520  SCIP_CALL( SCIPnewProbingNode(scip) );
1521  ncutoffs = 0;
1522  nprobings = 0;
1523  nmaxrows = 0;
1524  infeasible = FALSE;
1525 
1526  /* initialize heuristic matrix and working solution */
1527  SCIP_CALL( SCIPallocBuffer(scip, &matrix) );
1528  SCIP_CALL( initMatrix(scip, matrix, heurdata, heurdata->normalize, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1529 
1530  /* could not initialize matrix */
1531  if( !initialized || infeasible )
1532  {
1533  SCIPdebugMessage(" MATRIX not initialized -> Execution of heuristic stopped! \n");
1534  goto TERMINATE;
1535  }
1536 
1537  /* the number of discrete LP column variables can be less than the actual number of variables, if, e.g., there
1538  * are nonlinearities in the problem. The heuristic execution can be terminated in that case.
1539  */
1540  if( matrix->ndiscvars < ndiscvars )
1541  {
1542  SCIPdebugMessage(" Not all discrete variables are in the current LP. Shiftandpropagate execution terminated\n");
1543  goto TERMINATE;
1544  }
1545 
1546  assert(nmaxrows > 0);
1547 
1548  eventhdlrdata->matrix = matrix;
1549  eventhdlrdata->heurdata = heurdata;
1550 
1551  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1552  SCIPsolSetHeur(sol, heur);
1553 
1554  /* allocate arrays for execution method */
1555  SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ndiscvars) );
1556  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowweights, matrix->nrows) );
1557 
1558  /* allocate necessary memory for best shift search */
1559  SCIP_CALL( SCIPallocBufferArray(scip, &steps, nmaxrows) );
1560  SCIP_CALL( SCIPallocBufferArray(scip, &violationchange, nmaxrows) );
1561 
1562  /* allocate arrays to store information about infeasible rows */
1563  SCIP_CALL( SCIPallocBufferArray(scip, &violatedrows, matrix->nrows) );
1564  SCIP_CALL( SCIPallocBufferArray(scip, &violatedrowpos, matrix->nrows) );
1565 
1566  eventhdlrdata->violatedrows = violatedrows;
1567  eventhdlrdata->violatedrowpos = violatedrowpos;
1568  eventhdlrdata->nviolatedrows = &nviolatedrows;
1569 
1570 
1571 
1572  /* initialize arrays. Before sorting, permutation is the identity permutation */
1573  for( i = 0; i < ndiscvars; ++i )
1574  permutation[i] = i;
1575 
1576  /* initialize row weights */
1577  for( r = 0; r < matrix->nrows; ++r )
1578  {
1579  if( !SCIPisInfinity(scip, -(matrix->lhs[r])) && !SCIPisInfinity(scip, matrix->rhs[r]) )
1580  heurdata->rowweights[r] = DEFAULT_WEIGHT_EQUALITY;
1581  else
1582  heurdata->rowweights[r] = DEFAULT_WEIGHT_INEQUALITY;
1583 
1584  }
1585  colnorms = matrix->colnorms;
1586 
1587  assert(nbinvars >= 0);
1588  assert(nintvars >= 0);
1589 
1590  /* allocate memory for violatedvarrows array only if variable ordering relies on it */
1591  if( heurdata->sortvars && (heurdata->sortkey == 't' || heurdata->sortkey == 'v') )
1592  {
1593  SCIP_CALL( SCIPallocBufferArray(scip, &violatedvarrows, ndiscvars) );
1594  BMSclearMemoryArray(violatedvarrows, ndiscvars);
1595  }
1596  else
1597  violatedvarrows = NULL;
1598 
1599  /* check rows for infeasibility */
1600  nredundantrows = 0;
1601  checkViolations(scip, matrix, violatedrows, violatedrowpos, &nviolatedrows, &nredundantrows, violatedvarrows);
1602 
1603 
1604  /* sort variables w.r.t. the sorting key parameter. Sorting is indirect, all matrix column data
1605  * stays in place, but permutation array gives access to the sorted order of variables
1606  */
1607  if( heurdata->sortvars )
1608  {
1609  switch (heurdata->sortkey)
1610  {
1611  case 'n':
1612  /* variable ordering w.r.t. column norms nonincreasing */
1613  if( heurdata->preferbinaries )
1614  {
1615  if( nbinvars > 0 )
1616  SCIPsortDownRealInt(colnorms, permutation, nbinvars);
1617  if( nbinvars < ndiscvars )
1618  SCIPsortDownRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1619  }
1620  else
1621  {
1622  SCIPsortDownRealInt(colnorms, permutation, ndiscvars);
1623  }
1624  SCIPdebugMessage("Variables sorted down w.r.t their normalized columns!\n");
1625  break;
1626  case 'u':
1627  /* variable ordering w.r.t. column norms nondecreasing */
1628  if( heurdata->preferbinaries )
1629  {
1630  if( nbinvars > 0 )
1631  SCIPsortRealInt(colnorms, permutation, nbinvars);
1632  if( nbinvars < ndiscvars )
1633  SCIPsortRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1634  }
1635  else
1636  {
1637  SCIPsortRealInt(colnorms, permutation, ndiscvars);
1638  }
1639  SCIPdebugMessage("Variables sorted w.r.t their normalized columns!\n");
1640  break;
1641  case 'v':
1642  /* variable ordering w.r.t. nonincreasing number of violated rows */
1643  assert(violatedvarrows != NULL);
1644  if( heurdata->preferbinaries )
1645  {
1646  if( nbinvars > 0 )
1647  SCIPsortDownIntInt(violatedvarrows, permutation, nbinvars);
1648  if( nbinvars < ndiscvars )
1649  SCIPsortDownIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1650  }
1651  else
1652  {
1653  SCIPsortDownIntInt(violatedvarrows, permutation, ndiscvars);
1654  }
1655 
1656  SCIPdebugMessage("Variables sorted down w.r.t their number of currently infeasible rows!\n");
1657  break;
1658  case 't':
1659  /* variable ordering w.r.t. nondecreasing number of violated rows */
1660  assert(violatedvarrows != NULL);
1661  if( heurdata->preferbinaries )
1662  {
1663  if( nbinvars > 0 )
1664  SCIPsortIntInt(violatedvarrows, permutation, nbinvars);
1665  if( nbinvars < ndiscvars )
1666  SCIPsortIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1667  }
1668  else
1669  {
1670  SCIPsortIntInt(violatedvarrows, permutation, ndiscvars);
1671  }
1672 
1673  SCIPdebugMessage("Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1674  break;
1675  case 'r':
1676  /* random sorting */
1677  if( heurdata->preferbinaries )
1678  {
1679  if( nbinvars > 0 )
1680  SCIPpermuteIntArray(permutation, 0, nbinvars - 1, &heurdata->randseed);
1681  if( nbinvars < ndiscvars )
1682  SCIPpermuteIntArray(&permutation[nbinvars], nbinvars - 1, ndiscvars - nbinvars - 1, &heurdata->randseed);
1683  }
1684  else
1685  {
1686  SCIPpermuteIntArray(permutation, 0, ndiscvars - 1, &heurdata->randseed);
1687  }
1688  SCIPdebugMessage("Variables permuted randomly!\n");
1689  break;
1690  default:
1691  SCIPdebugMessage("No variable permutation applied\n");
1692  break;
1693  }
1694  }
1695 
1696  SCIP_CALL( SCIPallocBufferArray(scip, &eventdatas, matrix->ndiscvars) );
1697  BMSclearMemoryArray(eventdatas, matrix->ndiscvars);
1698 
1699  /* initialize variable events to catch bound changes during propagation */
1700  for( c = 0; c < matrix->ndiscvars; ++c )
1701  {
1702  SCIP_VAR* var;
1703 
1704  var = SCIPcolGetVar(heurdata->lpcols[c]);
1705  assert(var != NULL);
1706  assert(SCIPvarIsIntegral(var));
1707  assert(eventdatas[c] == NULL);
1708 
1709  SCIP_CALL( SCIPallocBuffer(scip, &(eventdatas[c])) ); /*lint !e866*/
1710 
1711  eventdatas[c]->colpos = c;
1712 
1713  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, eventdatas[c], NULL) );
1714  }
1715 
1716  cutoff = FALSE;
1717  lastindexofsusp = -1;
1718  probing = heurdata->probing;
1719  infeasible = FALSE;
1720 
1721  SCIPdebugMessage("SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1722  nviolatedrows, ndiscvars);
1723 
1724  assert(matrix->ndiscvars == ndiscvars);
1725 
1726  /* loop over variables, shift them according to shifting criteria and try to reduce the global infeasibility */
1727  for( c = 0; c < ndiscvars; ++c )
1728  {
1729  SCIP_VAR* var;
1730  SCIP_Longint ndomredsfound;
1731  SCIP_Real optimalshiftvalue;
1732  SCIP_Real origsolval;
1733  SCIP_Real lb;
1734  SCIP_Real ub;
1735  TRANSFORMSTATUS status;
1736  int nviolations;
1737  int permutedvarindex;
1738  SCIP_Bool marksuspicious;
1739 
1740  permutedvarindex = permutation[c];
1741  optimalshiftvalue = 0.0;
1742  nviolations = 0;
1743  var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
1744  lb = SCIPvarGetLbLocal(var);
1745  ub = SCIPvarGetUbLocal(var);
1746  assert(SCIPcolGetLPPos(SCIPvarGetCol(var)) >= 0);
1747  assert(SCIPvarIsIntegral(var));
1748 
1749  /* check whether we hit some limit, e.g. the time limit, in between
1750  * since the check itself consumes some time, we only do it every tenth iteration
1751  */
1752  if( c % 10 == 0 && SCIPisStopped(scip) )
1753  goto TERMINATE2;
1754 
1755  /* if propagation is enabled, check if propagation has changed the variables bounds
1756  * and update the transformed upper bound correspondingly
1757  */
1758  if( heurdata->probing )
1759  updateTransformation(scip, matrix, heurdata, permutedvarindex, &(matrix->transformshiftvals[permutedvarindex]),
1760  lb, ub, violatedrows, violatedrowpos, &nviolatedrows);
1761 
1762  status = matrix->transformstatus[permutedvarindex];
1763 
1764  SCIPdebugMessage("Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1765  SCIPvarGetName(var), lb, ub, status, matrix->upperbounds[permutedvarindex]);
1766 
1767  /* ignore variable if propagation fixed it(lb and ub will be zero) */
1768  if( SCIPisFeasZero(scip, matrix->upperbounds[permutedvarindex]) )
1769  {
1770  assert(!SCIPisInfinity(scip, ub));
1771  assert(SCIPisFeasEQ(scip, lb, ub));
1772 
1773  SCIP_CALL( SCIPsetSolVal(scip, sol, var, ub) );
1774 
1775  continue;
1776  }
1777 
1778  marksuspicious = FALSE;
1779 
1780  /* check whether the variable is binary and has no locks in one direction, so that we want to fix it to the
1781  * respective bound (only enabled by parameter)
1782  */
1783  if( heurdata->fixbinlocks && SCIPvarIsBinary(var) && (SCIPvarGetNLocksUp(var) == 0 || SCIPvarGetNLocksDown(var) == 0) )
1784  {
1785  if( SCIPvarGetNLocksUp(var) == 0 )
1786  origsolval = SCIPvarGetUbLocal(var);
1787  else
1788  {
1789  assert(SCIPvarGetNLocksDown(var) == 0);
1790  origsolval = SCIPvarGetLbLocal(var);
1791  }
1792  }
1793  else
1794  {
1795  /* only apply the computationally expensive best shift selection, if there is a violated row left */
1796  if( !heurdata->stopafterfeasible || nviolatedrows > 0 )
1797  {
1798  /* compute optimal shift value for variable */
1799  SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, 1, heurdata->rowweights, steps, violationchange,
1800  &optimalshiftvalue, &nviolations) );
1801  assert(SCIPisFeasGE(scip, optimalshiftvalue, 0.0));
1802 
1803  /* Variables with FREE transform have to be dealt with twice */
1804  if( matrix->transformstatus[permutedvarindex] == TRANSFORMSTATUS_FREE )
1805  {
1806  SCIP_Real downshiftvalue;
1807  int ndownviolations;
1808 
1809  downshiftvalue = 0.0;
1810  ndownviolations = 0;
1811  SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, -1, heurdata->rowweights, steps, violationchange,
1812  &downshiftvalue, &ndownviolations) );
1813 
1814  assert(SCIPisLE(scip, downshiftvalue, 0.0));
1815 
1816  /* compare to positive direction and select the direction which makes more rows feasible */
1817  if( ndownviolations < nviolations )
1818  {
1819  optimalshiftvalue = downshiftvalue;
1820  }
1821  }
1822  }
1823  else
1824  optimalshiftvalue = 0.0;
1825 
1826  /* if zero optimal shift values are forbidden by the user parameter, delay the variable by marking it suspicious */
1827  if( heurdata->nozerofixing && nviolations > 0 && SCIPisFeasZero(scip, optimalshiftvalue) )
1828  marksuspicious = TRUE;
1829 
1830  /* retransform the solution value from the heuristic transformation space */
1831  assert(varIsDiscrete(var, impliscontinuous));
1832  origsolval = retransformVariable(scip, matrix, var, permutedvarindex, optimalshiftvalue);
1833  }
1834  assert(SCIPisFeasGE(scip, origsolval, lb) && SCIPisFeasLE(scip, origsolval, ub));
1835 
1836  /* check if propagation should still be performed */
1837  if( nprobings > DEFAULT_PROPBREAKER )
1838  probing = FALSE;
1839 
1840  /* if propagation is enabled, fix the variable to the new solution value and propagate the fixation
1841  * (to fix other variables and to find out early whether solution is already infeasible)
1842  */
1843  if( !marksuspicious && probing )
1844  {
1845  SCIP_CALL( SCIPnewProbingNode(scip) );
1846  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
1847  ndomredsfound = 0;
1848 
1849  SCIPdebugMessage(" Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
1850  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
1851 
1852  ++nprobings;
1853  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
1854  SCIPdebugMessage("Propagation finished! <%lld> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ? "CUTOFF" : "",
1855  SCIPgetProbingDepth(scip));
1856  }
1857  assert(!cutoff || probing);
1858 
1859  /* propagation led to an empty domain, hence we backtrack and postpone the variable */
1860  if( cutoff )
1861  {
1862  assert(probing);
1863 
1864  ++ncutoffs;
1865 
1866  /* only continue heuristic if number of cutoffs occured so far is reasonably small */
1867  if( heurdata->cutoffbreaker >= 0 && ncutoffs >= heurdata->cutoffbreaker )
1868  break;
1869 
1870  cutoff = FALSE;
1871 
1872  /* backtrack to the parent of the current node */
1873  assert(SCIPgetProbingDepth(scip) >= 1);
1874  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) );
1875  marksuspicious = TRUE;
1876 
1877  /* if the variable were to be set to one of its bounds, repropagate by tightening this bound by 1.0
1878  * into the direction of the other bound, if possible */
1879  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
1880  {
1881  assert(SCIPisFeasGE(scip, SCIPvarGetUbLocal(var), origsolval + 1.0));
1882 
1883  ndomredsfound = 0;
1884  SCIP_CALL( SCIPnewProbingNode(scip) );
1885  SCIP_CALL( SCIPchgVarLbProbing(scip, var, origsolval + 1.0) );
1886  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
1887 
1888  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
1889 
1890  /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
1891  * can be stopped */
1892  if( cutoff )
1893  break;
1894  }
1895  else if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) )
1896  {
1897  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), origsolval - 1.0));
1898 
1899  ndomredsfound = 0;
1900 
1901  SCIP_CALL( SCIPnewProbingNode(scip) );
1902  SCIP_CALL( SCIPchgVarUbProbing(scip, var, origsolval - 1.0) );
1903  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
1904 
1905  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
1906 
1907  /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
1908  * can be stopped */
1909  if( cutoff )
1910  break;
1911  }
1912  }
1913 
1914  if( marksuspicious )
1915  {
1916  /* mark the variable as suspicious */
1917  assert(permutedvarindex == permutation[c]);
1918 
1919  ++lastindexofsusp;
1920  assert(lastindexofsusp >= 0 && lastindexofsusp <= c);
1921 
1922  permutation[c] = permutation[lastindexofsusp];
1923  permutation[lastindexofsusp] = permutedvarindex;
1924 
1925  SCIPdebugMessage(" Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
1926  }
1927  else
1928  {
1929  SCIPdebugMessage("Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
1930  SCIPvarGetName(var), optimalshiftvalue);
1931 
1932  /* update solution */
1933  SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
1934 
1935  /* only to ensure that some assertions can be made later on */
1936  if( !probing )
1937  {
1938  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
1939  }
1940  }
1941  }
1942  SCIPdebugMessage("Heuristic finished with %d remaining violations and %d remaining variables!\n",
1943  nviolatedrows, lastindexofsusp + 1);
1944 
1945  /* if constructed solution might be feasible, go through the queue of suspicious variables and set the solution
1946  * values
1947  */
1948  if( nviolatedrows == 0 && !cutoff )
1949  {
1950  SCIP_Bool stored;
1951 
1952  for( v = 0; v <= lastindexofsusp; ++v )
1953  {
1954  SCIP_VAR* var;
1955  SCIP_Real origsolval;
1956  int permutedvarindex;
1957 
1958  /* get the column position of the variable */
1959  permutedvarindex = permutation[v];
1960  var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
1961  assert(varIsDiscrete(var, impliscontinuous));
1962 
1963  /* update the transformation of the variable, since the bound might have changed after the last update. */
1964  if( heurdata->probing )
1965  updateTransformation(scip, matrix, heurdata, permutedvarindex, &(matrix->transformshiftvals[permutedvarindex]),
1966  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), violatedrows, violatedrowpos, &nviolatedrows);
1967 
1968  /* retransform the solution value from the heuristic transformed space, set the solution value accordingly */
1969  assert(varIsDiscrete(var, impliscontinuous));
1970  origsolval = retransformVariable(scip, matrix, var, permutedvarindex, 0.0);
1971  assert(SCIPisFeasGE(scip, origsolval, SCIPvarGetLbLocal(var))
1972  && SCIPisFeasLE(scip, origsolval, SCIPvarGetUbLocal(var)));
1973  SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
1974  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) ); /* only to ensure that some assertions can be made later */
1975 
1976  SCIPdebugMessage(" Remaining variable <%s> set to <%g>; %d Violations\n", SCIPvarGetName(var), origsolval,
1977  nviolatedrows);
1978  }
1979  /* Fixing of remaining variables led to infeasibility */
1980  if( nviolatedrows > 0 )
1981  goto TERMINATE2;
1982 
1983  stored = TRUE;
1984  /* if the constructed solution might still be extendable to a feasible solution, try this by
1985  * solving the remaining LP
1986  */
1987  if( nlpcols != matrix->ndiscvars )
1988  {
1989  /* case that remaining LP has to be solved */
1990  SCIP_Bool lperror;
1991 
1992 #ifndef NDEBUG
1993  {
1994  SCIP_VAR** vars;
1995 
1996  vars = SCIPgetVars(scip);
1997  assert(vars != NULL);
1998  /* ensure that all discrete variables in the remaining LP are fixed */
1999  for( v = 0; v < ndiscvars; ++v )
2000  {
2001  if( SCIPvarIsInLP(vars[v]) )
2002  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])));
2003 
2004  }
2005  }
2006 #endif
2007 
2008  SCIPdebugMessage(" -> old LP iterations: %"SCIP_LONGINT_FORMAT"\n", SCIPgetNLPIterations(scip));
2009 
2010  /* solve LP;
2011  * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
2012  * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2013  */
2014 #ifdef NDEBUG
2015  {
2016  SCIP_RETCODE retstat;
2017  retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
2018  if( retstat != SCIP_OKAY )
2019  {
2020  SCIPwarningMessage(scip, "Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2021  retstat);
2022  }
2023  }
2024 #else
2025  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
2026 #endif
2027 
2028  SCIPdebugMessage(" -> new LP iterations: %"SCIP_LONGINT_FORMAT"\n", SCIPgetNLPIterations(scip));
2029  SCIPdebugMessage(" -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
2030 
2031  /* check if this is a feasible solution */
2032  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2033  {
2034  /* copy the current LP solution to the working solution */
2035  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
2036  }
2037  else
2038  stored = FALSE;
2039 
2040  SCIPstatistic( heurdata->lpsolstat = SCIPgetLPSolstat(scip) );
2041  }
2042  /* check solution for feasibility, and add it to solution store if possible.
2043  * Neither integrality nor feasibility of LP rows have to be checked, because they
2044  * are guaranteed by the heuristic at this stage.
2045  */
2046  if( stored )
2047  {
2048 #ifndef NDEBUG
2049  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, TRUE, TRUE, TRUE, &stored) );
2050 #else
2051  /* @todo: maybe bounds don't need to be checked, in this case put an assert concerning stored ?????????? */
2052  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, TRUE, FALSE, FALSE, &stored) );
2053 #endif
2054  if( stored )
2055  {
2056  SCIPdebugMessage("found feasible shifted solution:\n");
2057  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
2058  *result = SCIP_FOUNDSOL;
2059  SCIPstatisticMessage(" Shiftandpropagate solution value: %16.9g \n", SCIPgetSolOrigObj(scip, sol));
2060  }
2061  }
2062  }
2063  else
2064  {
2065  SCIPdebugMessage("Solution constructed by heuristic is already known to be infeasible\n");
2066  }
2067 
2068  SCIPstatistic(
2069  heurdata->nremainingviols = nviolatedrows;
2070  heurdata->nredundantrows = nredundantrows;
2071  );
2072 
2073  TERMINATE2:
2074  /* free allocated memory in reverse order of allocation */
2075  for( c = matrix->ndiscvars - 1; c >= 0; --c )
2076  {
2077  SCIP_VAR* var;
2078 
2079  var = SCIPcolGetVar(heurdata->lpcols[c]);
2080  assert(var != NULL);
2081  assert(eventdatas[c] != NULL);
2082 
2083  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, eventdatas[c], -1) );
2084  SCIPfreeBuffer(scip, &(eventdatas[c]));
2085  }
2086  SCIPfreeBufferArray(scip, &eventdatas);
2087 
2088  if( violatedvarrows != NULL )
2089  {
2090  assert(heurdata->sortkey == 'v' || heurdata->sortkey == 't');
2091  SCIPfreeBufferArray(scip, &violatedvarrows);
2092  }
2093  /* free all allocated memory */
2094  SCIPfreeBufferArray(scip, &violatedrowpos);
2095  SCIPfreeBufferArray(scip, &violatedrows);
2096  SCIPfreeBufferArray(scip, &violationchange);
2097  SCIPfreeBufferArray(scip, &steps);
2098  SCIPfreeBufferArray(scip, &heurdata->rowweights);
2099  SCIPfreeBufferArray(scip, &permutation);
2100  SCIP_CALL( SCIPfreeSol(scip, &sol) );
2101 
2102  eventhdlrdata->nviolatedrows = NULL;
2103  eventhdlrdata->violatedrowpos = NULL;
2104  eventhdlrdata->violatedrows = NULL;
2105 
2106  TERMINATE:
2107  /* terminate probing mode and free the remaining memory */
2108  SCIPstatistic(
2109  heurdata->ncutoffs += ncutoffs;
2110  heurdata->nprobings += nprobings;
2111  heurdata->nlpiters = SCIPgetNLPIterations(scip) - heurdata->nlpiters;
2112  );
2113 
2114  SCIP_CALL( SCIPendProbing(scip) );
2115  SCIPfreeBufferArray(scip, &heurdata->lpcols);
2116  freeMatrix(scip, &matrix);
2117  eventhdlrdata->matrix = NULL;
2118 
2119  return SCIP_OKAY;
2120 }
2121 
2122 /** event handler execution method for the heuristic which catches all
2123  * events in which a lower or upper bound were tightened */
2124 static
2125 SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
2126 { /*lint --e{715}*/
2127  SCIP_EVENTHDLRDATA* eventhdlrdata;
2128  SCIP_VAR* var;
2129  SCIP_COL* col;
2130  SCIP_Real lb;
2131  SCIP_Real ub;
2132  int colpos;
2133  CONSTRAINTMATRIX* matrix;
2134  SCIP_HEURDATA* heurdata;
2135 
2136  assert(scip != NULL);
2137  assert(eventhdlr != NULL);
2138  assert(strcmp(EVENTHDLR_NAME, SCIPeventhdlrGetName(eventhdlr)) == 0);
2139 
2140  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2141  assert(eventhdlrdata != NULL);
2142 
2143  matrix = eventhdlrdata->matrix;
2144 
2145  heurdata = eventhdlrdata->heurdata;
2146  assert(heurdata != NULL && heurdata->lpcols != NULL);
2147 
2148  colpos = eventdata->colpos;
2149 
2150  assert(0 <= colpos && colpos < matrix->ndiscvars);
2151 
2152  col = heurdata->lpcols[colpos];
2153  var = SCIPcolGetVar(col);
2154 
2155  lb = SCIPvarGetLbLocal(var);
2156  ub = SCIPvarGetUbLocal(var);
2157 
2158  updateTransformation(scip, matrix, eventhdlrdata->heurdata, colpos, &(matrix->transformshiftvals[colpos]),
2159  lb, ub, eventhdlrdata->violatedrows, eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows);
2160 
2161  return SCIP_OKAY;
2162 }
2163 
2164 /*
2165  * primal heuristic specific interface methods
2166  */
2167 
2168 /** creates the shiftandpropagate primal heuristic and includes it in SCIP */
2169 SCIP_RETCODE SCIPincludeHeurShiftandpropagate(
2170  SCIP* scip /**< SCIP data structure */
2171  )
2172 {
2173  SCIP_HEURDATA* heurdata;
2174  SCIP_HEUR* heur;
2175  SCIP_EVENTHDLRDATA* eventhandlerdata;
2176  SCIP_EVENTHDLR* eventhdlr;
2177 
2178 
2179  SCIP_CALL( SCIPallocMemory(scip, &eventhandlerdata) );
2180  eventhandlerdata->matrix = NULL;
2181 
2182  eventhdlr = NULL;
2183  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2184  eventExecShiftandpropagate, eventhandlerdata) );
2185  assert(eventhdlr != NULL);
2186 
2187  /* create Shiftandpropagate primal heuristic data */
2188  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
2189  heurdata->rowweights = NULL;
2190  heurdata->nlpcols = 0;
2191  heurdata->eventhdlr = eventhdlr;
2192 
2193  /* include primal heuristic */
2194  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2195  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2196  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecShiftandpropagate, heurdata) );
2197 
2198  assert(heur != NULL);
2199 
2200  /* set non-NULL pointers to callback methods */
2201  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyShiftandpropagate) );
2202  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeShiftandpropagate) );
2203  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitShiftandpropagate) );
2204  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitShiftandpropagate) );
2205 
2206 
2207  /* add shiftandpropagate primal heuristic parameters */
2208  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nproprounds", "The number of propagation rounds used for each propagation",
2209  &heurdata->nproprounds, TRUE, DEFAULT_NPROPROUNDS, -1, 1000, NULL, NULL) );
2210  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/relax", "Should continuous variables be relaxed?",
2211  &heurdata->relax, TRUE, DEFAULT_RELAX, NULL, NULL) );
2212  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/probing", "Should domains be reduced by probing?",
2213  &heurdata->probing, TRUE, DEFAULT_PROBING, NULL, NULL) );
2214  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/onlywithoutsol", "Should heuristic only be executed if no primal solution was found, yet?",
2215  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
2216  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/cutoffbreaker", "The number of cutoffs before heuristic stops",
2217  &heurdata->cutoffbreaker, TRUE, DEFAULT_CUTOFFBREAKER, -1, 1000000, NULL, NULL) );
2218  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/"HEUR_NAME"/sortkey", "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2219  &heurdata->sortkey, TRUE, DEFAULT_SORTKEY, SORTKEYS, NULL, NULL) );
2220  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/sortvars", "Should variables be sorted for the heuristic?",
2221  &heurdata->sortvars, TRUE, DEFAULT_SORTVARS, NULL, NULL));
2222  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/collectstats", "should variable statistics be collected during probing?",
2223  &heurdata->collectstats, TRUE, DEFAULT_COLLECTSTATS, NULL, NULL) );
2224  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/stopafterfeasible", "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2225  &heurdata->stopafterfeasible, TRUE, DEFAULT_STOPAFTERFEASIBLE, NULL, NULL) );
2226  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/preferbinaries", "Should binary variables be shifted first?",
2227  &heurdata->preferbinaries, TRUE, DEFAULT_PREFERBINARIES, NULL, NULL) );
2228  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/nozerofixing", "should variables with a zero shifting value be delayed instead of being fixed?",
2229  &heurdata->nozerofixing, TRUE, DEFAULT_NOZEROFIXING, NULL, NULL) );
2230  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/fixbinlocks", "should binary variables with no locks in one direction be fixed to that direction?",
2231  &heurdata->fixbinlocks, TRUE, DEFAULT_FIXBINLOCKS, NULL, NULL) );
2232  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/normalize", "should coefficients and left/right hand sides be normalized by max row coeff?",
2233  &heurdata->normalize, TRUE, DEFAULT_NORMALIZE, NULL, NULL) );
2234  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/updateweights", "should row weight be increased every time the row is violated?",
2235  &heurdata->updateweights, TRUE, DEFAULT_UPDATEWEIGHTS, NULL, NULL) );
2236  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/impliscontinuous", "should implicit integer variables be treated as continuous variables?",
2237  &heurdata->impliscontinuous, TRUE, DEFAULT_IMPLISCONTINUOUS, NULL, NULL) );
2238  return SCIP_OKAY;
2239 }
2240