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