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( !SCIPisInfinity(scip, maxfeasshift) && 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  if( ! SCIPisInfinity(scip, upperbound) && SCIPisGT(scip, slacksurplus, 0.0) )
1067  *beststep = direction * upperbound;
1068  else
1069  *beststep = 0.0;
1070 
1071  return SCIP_OKAY;
1072  }
1073 
1074  /* sorts rows by increasing value of steps */
1075  SCIPsortRealInt(steps, violationchange, nrows);
1076 
1077  *beststep = 0.0;
1078  *rowviolations = 0;
1079  sum = 0;
1080 
1081  /* best shifting step is calculated by summing up the violation changes for each relevant step and
1082  * taking the one which leads to the minimum sum. This sum measures the balance of feasibility recovering and
1083  * violating changes which will be obtained by shifting the variable by this step
1084  * note, the sums for smaller steps have to be taken into account for all bigger steps, i.e., the sums can be
1085  * computed iteratively
1086  */
1087  for( i = 0; i < nrows && !SCIPisInfinity(scip, steps[i]); ++i )
1088  {
1089  sum += violationchange[i];
1090 
1091  /* if we reached the last entry for the current step value, we have finished computing its sum and
1092  * update the step defining the minimum sum
1093  */
1094  if( (i == nrows-1 || steps[i+1] > steps[i]) && sum < *rowviolations ) /*lint !e679*/
1095  {
1096  *rowviolations = sum;
1097  *beststep = direction * steps[i];
1098  }
1099  }
1100  assert(*rowviolations <= 0);
1101  assert(!SCIPisInfinity(scip, *beststep));
1102 
1103  return SCIP_OKAY;
1104 }
1105 
1106 /** updates transformation of a given variable by taking into account current local bounds. if the bounds have changed
1107  * since last update, updating the heuristic specific upper bound of the variable, its current transformed solution value
1108  * and all affected rows is necessary.
1109  */
1110 static
1112  SCIP* scip, /**< current scip */
1113  CONSTRAINTMATRIX* matrix, /**< constraint matrix object */
1114  SCIP_HEURDATA* heurdata, /**< heuristic data */
1115  int varindex, /**< index of variable in matrix */
1116  SCIP_Real lb, /**< local lower bound of the variable */
1117  SCIP_Real ub, /**< local upper bound of the variable */
1118  int* violatedrows, /**< violated rows */
1119  int* violatedrowpos, /**< violated row positions */
1120  int* nviolatedrows /**< pointer to store number of violated rows */
1121  )
1122 {
1123  TRANSFORMSTATUS status;
1124  SCIP_Real deltashift;
1125  SCIP_Bool checkviolations;
1126 
1127  assert(scip != NULL);
1128  assert(matrix != NULL);
1129  assert(0 <= varindex && varindex < matrix->ndiscvars);
1130 
1131  /* deltashift is the difference between the old and new transformation value. */
1132  deltashift = 0.0;
1133  status = matrix->transformstatus[varindex];
1134 
1135  SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1136  matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1137 
1138  checkviolations = FALSE;
1139  /* depending on the variable status, deltashift is calculated differently. */
1140  switch( status )
1141  {
1142  case TRANSFORMSTATUS_LB:
1143  if( SCIPisInfinity(scip, -lb) )
1144  {
1145  transformVariable(scip, matrix, heurdata, varindex);
1146  checkviolations = TRUE;
1147  }
1148  else
1149  {
1150  deltashift = lb - (matrix->transformshiftvals[varindex]);
1151  matrix->transformshiftvals[varindex] = lb;
1152  if( !SCIPisInfinity(scip, ub) )
1153  matrix->upperbounds[varindex] = ub - lb;
1154  else
1155  matrix->upperbounds[varindex] = SCIPinfinity(scip);
1156  }
1157  break;
1158  case TRANSFORMSTATUS_NEG:
1159  if( SCIPisInfinity(scip, ub) )
1160  {
1161  transformVariable(scip, matrix, heurdata, varindex);
1162  checkviolations = TRUE;
1163  }
1164  else
1165  {
1166  deltashift = (matrix->transformshiftvals[varindex]) - ub;
1167  matrix->transformshiftvals[varindex] = ub;
1168 
1169  if( !SCIPisInfinity(scip, -lb) )
1170  matrix->upperbounds[varindex] = ub - lb;
1171  else
1172  matrix->upperbounds[varindex] = SCIPinfinity(scip);
1173  }
1174  break;
1175  case TRANSFORMSTATUS_FREE:
1176  /* in case of a free transform status, if one of the bounds has become finite, we want
1177  * to transform this variable to a variable with a lowerbound or a negated transform status */
1178  if( !SCIPisInfinity(scip, -lb) || !SCIPisInfinity(scip, ub) )
1179  {
1180  transformVariable(scip, matrix, heurdata, varindex);
1181 
1182  /* violations have to be rechecked for rows in which variable appears */
1183  checkviolations = TRUE;
1184 
1185  assert(matrix->transformstatus[varindex] == TRANSFORMSTATUS_LB || TRANSFORMSTATUS_NEG);
1186  assert(SCIPisFeasLE(scip, ABS(lb), ABS(ub)) || matrix->transformstatus[varindex] == TRANSFORMSTATUS_NEG);
1187  }
1188  break;
1189 
1190  case TRANSFORMSTATUS_NONE:
1191  default:
1192  SCIPerrorMessage("Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n");
1193  SCIPABORT();
1194  return SCIP_INVALIDDATA; /*lint !e527*/
1195  }
1196  /* if the bound, by which the variable was shifted, has changed, deltashift is different from zero, which requires
1197  * an update of all affected rows
1198  */
1199  if( !SCIPisFeasZero(scip, deltashift) )
1200  {
1201  int i;
1202  int* rows;
1203  SCIP_Real* vals;
1204  int nrows;
1205 
1206  /* get nonzero values and corresponding rows of variable */
1207  getColumnData(matrix, varindex, &vals, &rows, &nrows);
1208 
1209  /* go through rows, update the rows w.r.t. the influence of the changed transformation of the variable */
1210  for( i = 0; i < nrows; ++i )
1211  {
1212  SCIPdebugMsg(scip, " update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n",
1213  rows[i], vals[i], matrix->lhs[rows[i]], matrix->rhs[rows[i]]);
1214 
1215  if( !SCIPisInfinity(scip, -(matrix->lhs[rows[i]])) )
1216  matrix->lhs[rows[i]] -= (vals[i]) * deltashift;
1217 
1218  if( !SCIPisInfinity(scip, matrix->rhs[rows[i]]) )
1219  matrix->rhs[rows[i]] -= (vals[i]) * deltashift;
1220  }
1221  checkviolations = TRUE;
1222  }
1223 
1224  /* check and update information about violated rows, if necessary */
1225  if( checkviolations )
1226  checkViolations(scip, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1227 
1228  SCIPdebugMsg(scip, " Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1229  matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1230 
1231  return SCIP_OKAY;
1232 }
1233 
1234 /** comparison method for columns; binary < integer < implicit < continuous variables */
1235 static
1236 SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
1238  SCIP_COL* col1;
1239  SCIP_COL* col2;
1240  SCIP_VAR* var1;
1241  SCIP_VAR* var2;
1242  SCIP_VARTYPE vartype1;
1243  SCIP_VARTYPE vartype2;
1244  int key1;
1245  int key2;
1246 
1247  col1 = (SCIP_COL*)elem1;
1248  col2 = (SCIP_COL*)elem2;
1249  var1 = SCIPcolGetVar(col1);
1250  var2 = SCIPcolGetVar(col2);
1251  assert(var1 != NULL && var2 != NULL);
1252 
1253  vartype1 = SCIPvarGetType(var1);
1254  vartype2 = SCIPvarGetType(var2);
1255 
1256  switch (vartype1)
1257  {
1258  case SCIP_VARTYPE_BINARY:
1259  key1 = 1;
1260  break;
1261  case SCIP_VARTYPE_INTEGER:
1262  key1 = 2;
1263  break;
1264  case SCIP_VARTYPE_IMPLINT:
1265  key1 = 3;
1266  break;
1268  key1 = 4;
1269  break;
1270  default:
1271  key1 = -1;
1272  SCIPerrorMessage("unknown variable type\n");
1273  SCIPABORT();
1274  break;
1275  }
1276  switch (vartype2)
1277  {
1278  case SCIP_VARTYPE_BINARY:
1279  key2 = 1;
1280  break;
1281  case SCIP_VARTYPE_INTEGER:
1282  key2 = 2;
1283  break;
1284  case SCIP_VARTYPE_IMPLINT:
1285  key2 = 3;
1286  break;
1288  key2 = 4;
1289  break;
1290  default:
1291  key2 = -1;
1292  SCIPerrorMessage("unknown variable type\n");
1293  SCIPABORT();
1294  break;
1295  }
1296  return key1 - key2;
1297 }
1298 
1299 /*
1300  * Callback methods of primal heuristic
1301  */
1302 
1303 /** deinitialization method of primal heuristic(called before transformed problem is freed) */
1304 static
1305 SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
1306 { /*lint --e{715}*/
1307  SCIP_HEURDATA* heurdata;
1308 
1309  heurdata = SCIPheurGetData(heur);
1310  assert(heurdata != NULL);
1311 
1312  /* free random number generator */
1313  SCIPfreeRandom(scip, &heurdata->randnumgen);
1314 
1315  /* if statistic mode is enabled, statistics are printed to console */
1316  SCIPstatistic(
1318  " DETAILS : %d violations left, %d probing status\n",
1319  heurdata->nremainingviols,
1320  heurdata->lpsolstat
1321  );
1323  " SHIFTANDPROPAGATE PROBING : %d probings, %" SCIP_LONGINT_FORMAT " domain reductions, ncutoffs: %d , LP iterations: %" SCIP_LONGINT_FORMAT " \n ",
1324  heurdata->nprobings,
1325  heurdata->ntotaldomredsfound,
1326  heurdata->ncutoffs,
1327  heurdata->nlpiters);
1328  );
1329 
1330  return SCIP_OKAY;
1331 }
1332 
1333 /** initialization method of primal heuristic(called after problem was transformed). We only need this method for
1334  * statistic mode of heuristic.
1335  */
1336 static
1337 SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
1338 { /*lint --e{715}*/
1339 
1340  SCIP_HEURDATA* heurdata;
1341 
1342  heurdata = SCIPheurGetData(heur);
1343 
1344  assert(heurdata != NULL);
1345 
1346  /* create random number generator */
1347  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
1348  DEFAULT_RANDSEED) );
1349 
1350  SCIPstatistic(
1351  heurdata->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
1352  heurdata->nremainingviols = 0;
1353  heurdata->nprobings = 0;
1354  heurdata->ntotaldomredsfound = 0;
1355  heurdata->ncutoffs = 0;
1356  heurdata->nlpiters = 0;
1357  )
1358  return SCIP_OKAY;
1359 }
1360 
1361 /** destructor of primal heuristic to free user data(called when SCIP is exiting) */
1362 static
1363 SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
1364 { /*lint --e{715}*/
1365  SCIP_HEURDATA* heurdata;
1366  SCIP_EVENTHDLR* eventhdlr;
1367  SCIP_EVENTHDLRDATA* eventhdlrdata;
1368 
1369  heurdata = SCIPheurGetData(heur);
1370  assert(heurdata != NULL);
1371  eventhdlr = heurdata->eventhdlr;
1372  assert(eventhdlr != NULL);
1373  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1374 
1375  SCIPfreeBlockMemoryNull(scip, &eventhdlrdata);
1376 
1377  /* free heuristic data */
1378  SCIPfreeBlockMemory(scip, &heurdata);
1379 
1380  SCIPheurSetData(heur, NULL);
1381 
1382  return SCIP_OKAY;
1383 }
1384 
1385 
1386 /** copy method for primal heuristic plugins(called when SCIP copies plugins) */
1387 static
1388 SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
1389 { /*lint --e{715}*/
1390  assert(scip != NULL);
1391  assert(heur != NULL);
1392  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1393 
1394  /* call inclusion method of primal heuristic */
1396 
1397  return SCIP_OKAY;
1398 }
1399 
1400 /** execution method of primal heuristic */
1401 static
1402 SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
1403 { /*lint --e{715}*/
1404  SCIP_HEURDATA* heurdata; /* heuristic data */
1405  SCIP_EVENTHDLR* eventhdlr; /* shiftandpropagate event handler */
1406  SCIP_EVENTHDLRDATA* eventhdlrdata; /* event handler data */
1407  SCIP_EVENTDATA** eventdatas; /* event data for every variable */
1408 
1409  CONSTRAINTMATRIX* matrix; /* constraint matrix object */
1410  SCIP_COL** lpcols; /* lp columns */
1411  SCIP_SOL* sol; /* solution pointer */
1412  SCIP_Real* colnorms; /* contains Euclidean norms of column vectors */
1413 
1414  SCIP_Real* steps; /* buffer arrays for best shift selection in main loop */
1415  int* violationchange;
1416 
1417  int* violatedrows; /* the violated rows */
1418  int* violatedrowpos; /* the array position of a violated row, or -1 */
1419  int* permutation; /* reflects the position of the variables after sorting */
1420  int* violatedvarrows; /* number of violated rows for each variable */
1421  int* colposs; /* position of columns according to variable type sorting */
1422  int nlpcols; /* number of lp columns */
1423  int nviolatedrows; /* number of violated rows */
1424  int ndiscvars; /* number of non-continuous variables of the problem */
1425  int lastindexofsusp; /* last variable which has been swapped due to a cutoff */
1426  int nbinvars; /* number of binary variables */
1427  int nintvars; /* number of integer variables */
1428  int i;
1429  int r;
1430  int v;
1431  int c;
1432  int ncutoffs; /* counts the number of cutoffs for this execution */
1433  int nprobings; /* counts the number of probings */
1434  int nlprows; /* the number LP rows */
1435  int nmaxrows; /* maximum number of LP rows of a variable */
1436 
1437  SCIP_Bool initialized; /* has the matrix been initialized? */
1438  SCIP_Bool cutoff; /* has current probing node been cutoff? */
1439  SCIP_Bool probing; /* should probing be applied or not? */
1440  SCIP_Bool infeasible; /* FALSE as long as currently infeasible rows have variables left */
1441  SCIP_Bool impliscontinuous;
1442 
1443  heurdata = SCIPheurGetData(heur);
1444  assert(heurdata != NULL);
1445 
1446  eventhdlr = heurdata->eventhdlr;
1447  assert(eventhdlr != NULL);
1448 
1449  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1450  assert(eventhdlrdata != NULL);
1451 
1452  *result = SCIP_DIDNOTRUN;
1453  SCIPdebugMsg(scip, "entering execution method of shift and propagate heuristic\n");
1454 
1455  /* heuristic is obsolete if there are only continuous variables */
1456  if( SCIPgetNVars(scip) - SCIPgetNContVars(scip) == 0 )
1457  return SCIP_OKAY;
1458 
1459  /* stop execution method if there is already a primarily feasible solution at hand */
1460  if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
1461  return SCIP_OKAY;
1462 
1463  /* stop if there is no LP available */
1464  if ( ! SCIPhasCurrentNodeLP(scip) )
1465  return SCIP_OKAY;
1466 
1467  if( !SCIPisLPConstructed(scip) )
1468  {
1469  /* @note this call can have the side effect that variables are created */
1470  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1471 
1472  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1473  if( cutoff )
1474  {
1476  return SCIP_OKAY;
1477  }
1478 
1479  SCIP_CALL( SCIPflushLP(scip) );
1480  }
1481 
1482  SCIPstatistic( heurdata->nlpiters = SCIPgetNLPIterations(scip) );
1483 
1484  nlprows = SCIPgetNLPRows(scip);
1485 
1486  SCIP_CALL( SCIPgetLPColsData(scip, &lpcols, &nlpcols) );
1487  assert(nlpcols == 0 || lpcols != NULL);
1488 
1489  /* we need an LP */
1490  if( nlprows == 0 || nlpcols == 0 )
1491  return SCIP_OKAY;
1492 
1493 
1494  *result = SCIP_DIDNOTFIND;
1495  initialized = FALSE;
1496 
1497  /* allocate lp column array */
1498  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->lpcols, nlpcols) );
1499  heurdata->nlpcols = nlpcols;
1500 
1501  impliscontinuous = heurdata->impliscontinuous;
1502 
1503 #ifndef NDEBUG
1504  BMSclearMemoryArray(heurdata->lpcols, nlpcols);
1505 #endif
1506 
1507  /* copy and sort the columns by their variable types (binary before integer before implicit integer before continuous) */
1508  BMScopyMemoryArray(heurdata->lpcols, lpcols, nlpcols);
1509 
1510  SCIPsortPtr((void**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);
1511 
1512  SCIP_CALL( SCIPallocBufferArray(scip, &colposs, nlpcols) );
1513 
1514  /* we have to collect the number of different variable types before we start probing since during probing variable
1515  * can be created (e.g., cons_xor.c)
1516  */
1517  ndiscvars = 0;
1518  nbinvars = 0;
1519  nintvars = 0;
1520  for( c = 0; c < nlpcols; ++c )
1521  {
1522  SCIP_COL* col;
1523  SCIP_VAR* colvar;
1524 
1525  col = heurdata->lpcols[c];
1526  assert(col != NULL);
1527  colvar = SCIPcolGetVar(col);
1528  assert(colvar != NULL);
1529 
1530  if( varIsDiscrete(colvar, impliscontinuous) )
1531  ++ndiscvars;
1532  if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY )
1533  ++nbinvars;
1534  else if( SCIPvarGetType(colvar) == SCIP_VARTYPE_INTEGER )
1535  ++nintvars;
1536 
1537  /* save the position of this column in the array such that it can be accessed as the "true" column position */
1538  assert(SCIPcolGetLPPos(col) >= 0);
1539  colposs[SCIPcolGetLPPos(col)] = c;
1540  }
1541  assert(nbinvars + nintvars <= ndiscvars);
1542 
1543  /* start probing mode */
1544  SCIP_CALL( SCIPstartProbing(scip) );
1545 
1546  /* enables collection of variable statistics during probing */
1547  if( heurdata->collectstats )
1548  SCIPenableVarHistory(scip);
1549  else
1550  SCIPdisableVarHistory(scip);
1551 
1552  /* this should always be fulfilled becase we perform shift and propagate only at the root node */
1553  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
1554 
1555  /* @todo check if this node is necessary (I don't think so) */
1556  SCIP_CALL( SCIPnewProbingNode(scip) );
1557  ncutoffs = 0;
1558  nprobings = 0;
1559  nmaxrows = 0;
1560  infeasible = FALSE;
1561 
1562  /* initialize heuristic matrix and working solution */
1563  SCIP_CALL( SCIPallocBuffer(scip, &matrix) );
1564  SCIP_CALL( initMatrix(scip, matrix, heurdata, colposs, heurdata->normalize, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1565 
1566  /* the column positions are not needed anymore */
1567  SCIPfreeBufferArray(scip, &colposs);
1568 
1569  /* could not initialize matrix */
1570  if( !initialized || infeasible )
1571  {
1572  SCIPdebugMsg(scip, " MATRIX not initialized -> Execution of heuristic stopped! \n");
1573  goto TERMINATE;
1574  }
1575 
1576  /* the number of discrete LP column variables can be less than the actual number of variables, if, e.g., there
1577  * are nonlinearities in the problem. The heuristic execution can be terminated in that case.
1578  */
1579  if( matrix->ndiscvars < ndiscvars )
1580  {
1581  SCIPdebugMsg(scip, "Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1582  goto TERMINATE;
1583  }
1584 
1585  assert(nmaxrows > 0);
1586 
1587  eventhdlrdata->matrix = matrix;
1588  eventhdlrdata->heurdata = heurdata;
1589 
1590  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1591  SCIPsolSetHeur(sol, heur);
1592 
1593  /* allocate arrays for execution method */
1594  SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ndiscvars) );
1595  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowweights, matrix->nrows) );
1596 
1597  /* allocate necessary memory for best shift search */
1598  SCIP_CALL( SCIPallocBufferArray(scip, &steps, nmaxrows) );
1599  SCIP_CALL( SCIPallocBufferArray(scip, &violationchange, nmaxrows) );
1600 
1601  /* allocate arrays to store information about infeasible rows */
1602  SCIP_CALL( SCIPallocBufferArray(scip, &violatedrows, matrix->nrows) );
1603  SCIP_CALL( SCIPallocBufferArray(scip, &violatedrowpos, matrix->nrows) );
1604 
1605  eventhdlrdata->violatedrows = violatedrows;
1606  eventhdlrdata->violatedrowpos = violatedrowpos;
1607  eventhdlrdata->nviolatedrows = &nviolatedrows;
1608 
1609 
1610 
1611  /* initialize arrays. Before sorting, permutation is the identity permutation */
1612  for( i = 0; i < ndiscvars; ++i )
1613  permutation[i] = i;
1614 
1615  /* initialize row weights */
1616  for( r = 0; r < matrix->nrows; ++r )
1617  {
1618  if( !SCIPisInfinity(scip, -(matrix->lhs[r])) && !SCIPisInfinity(scip, matrix->rhs[r]) )
1619  heurdata->rowweights[r] = DEFAULT_WEIGHT_EQUALITY;
1620  else
1621  heurdata->rowweights[r] = DEFAULT_WEIGHT_INEQUALITY;
1622 
1623  }
1624  colnorms = matrix->colnorms;
1625 
1626  assert(nbinvars >= 0);
1627  assert(nintvars >= 0);
1628 
1629  /* check rows for infeasibility */
1630  checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1631 
1632  /* allocate memory for violatedvarrows array only if variable ordering relies on it */
1633  if( heurdata->sortvars && (heurdata->sortkey == 't' || heurdata->sortkey == 'v') )
1634  {
1635  SCIP_CALL( SCIPallocBufferArray(scip, &violatedvarrows, ndiscvars) );
1636  BMScopyMemoryArray(violatedvarrows, matrix->violrows, ndiscvars);
1637  }
1638  else
1639  violatedvarrows = NULL;
1640 
1641  /* sort variables w.r.t. the sorting key parameter. Sorting is indirect, all matrix column data
1642  * stays in place, but permutation array gives access to the sorted order of variables
1643  */
1644  if( heurdata->sortvars )
1645  {
1646  switch (heurdata->sortkey)
1647  {
1648  case 'n':
1649  /* variable ordering w.r.t. column norms nonincreasing */
1650  if( heurdata->preferbinaries )
1651  {
1652  if( nbinvars > 0 )
1653  SCIPsortDownRealInt(colnorms, permutation, nbinvars);
1654  if( nbinvars < ndiscvars )
1655  SCIPsortDownRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1656  }
1657  else
1658  {
1659  SCIPsortDownRealInt(colnorms, permutation, ndiscvars);
1660  }
1661  SCIPdebugMsg(scip, "Variables sorted down w.r.t their normalized columns!\n");
1662  break;
1663  case 'u':
1664  /* variable ordering w.r.t. column norms nondecreasing */
1665  if( heurdata->preferbinaries )
1666  {
1667  if( nbinvars > 0 )
1668  SCIPsortRealInt(colnorms, permutation, nbinvars);
1669  if( nbinvars < ndiscvars )
1670  SCIPsortRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1671  }
1672  else
1673  {
1674  SCIPsortRealInt(colnorms, permutation, ndiscvars);
1675  }
1676  SCIPdebugMsg(scip, "Variables sorted w.r.t their normalized columns!\n");
1677  break;
1678  case 'v':
1679  /* variable ordering w.r.t. nonincreasing number of violated rows */
1680  assert(violatedvarrows != NULL);
1681  if( heurdata->preferbinaries )
1682  {
1683  if( nbinvars > 0 )
1684  SCIPsortDownIntInt(violatedvarrows, permutation, nbinvars);
1685  if( nbinvars < ndiscvars )
1686  SCIPsortDownIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1687  }
1688  else
1689  {
1690  SCIPsortDownIntInt(violatedvarrows, permutation, ndiscvars);
1691  }
1692 
1693  SCIPdebugMsg(scip, "Variables sorted down w.r.t their number of currently infeasible rows!\n");
1694  break;
1695  case 't':
1696  /* variable ordering w.r.t. nondecreasing number of violated rows */
1697  assert(violatedvarrows != NULL);
1698  if( heurdata->preferbinaries )
1699  {
1700  if( nbinvars > 0 )
1701  SCIPsortIntInt(violatedvarrows, permutation, nbinvars);
1702  if( nbinvars < ndiscvars )
1703  SCIPsortIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1704  }
1705  else
1706  {
1707  SCIPsortIntInt(violatedvarrows, permutation, ndiscvars);
1708  }
1709 
1710  SCIPdebugMsg(scip, "Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1711  break;
1712  case 'r':
1713  /* random sorting */
1714  if( heurdata->preferbinaries )
1715  {
1716  if( nbinvars > 0 )
1717  SCIPrandomPermuteIntArray(heurdata->randnumgen, permutation, 0, nbinvars - 1);
1718  if( nbinvars < ndiscvars )
1719  SCIPrandomPermuteIntArray(heurdata->randnumgen, &permutation[nbinvars], nbinvars - 1,
1720  ndiscvars - nbinvars - 1);
1721  }
1722  else
1723  {
1724  SCIPrandomPermuteIntArray(heurdata->randnumgen, permutation, 0, ndiscvars - 1);
1725  }
1726  SCIPdebugMsg(scip, "Variables permuted randomly!\n");
1727  break;
1728  default:
1729  SCIPdebugMsg(scip, "No variable permutation applied\n");
1730  break;
1731  }
1732  }
1733 
1734  /* should binary variables without locks be treated first? */
1735  if( heurdata->binlocksfirst )
1736  {
1737  SCIP_VAR* var;
1738  int nbinwithoutlocks = 0;
1739 
1740  /* count number of binaries without locks */
1741  if( heurdata->preferbinaries )
1742  {
1743  for( c = 0; c < nbinvars; ++c )
1744  {
1745  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1746  if( SCIPvarGetNLocksUp(var) == 0 || SCIPvarGetNLocksDown(var) == 0 )
1747  ++nbinwithoutlocks;
1748  }
1749  }
1750  else
1751  {
1752  for( c = 0; c < ndiscvars; ++c )
1753  {
1754  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1755  if( SCIPvarIsBinary(var) )
1756  {
1757  if( SCIPvarGetNLocksUp(var) == 0 || SCIPvarGetNLocksDown(var) == 0 )
1758  ++nbinwithoutlocks;
1759  }
1760  }
1761  }
1762 
1763  if( nbinwithoutlocks > 0 )
1764  {
1765  SCIP_VAR* binvar;
1766  int b = 1;
1767  int tmp;
1768  c = 0;
1769 
1770  /* if c reaches nbinwithoutlocks, then all binary variables without locks were sorted to the beginning of the array */
1771  while( c < nbinwithoutlocks && b < ndiscvars )
1772  {
1773  assert(c < b);
1774  assert(c < ndiscvars);
1775  assert(b < ndiscvars);
1776  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1777  binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1778 
1779  /* search for next variable which is not a binary variable without locks */
1780  while( SCIPvarIsBinary(var) && (SCIPvarGetNLocksUp(var) == 0 || SCIPvarGetNLocksDown(var) == 0) )
1781  {
1782  ++c;
1783  if( c >= nbinwithoutlocks )
1784  break;
1785  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1786  }
1787  if( c >= nbinwithoutlocks )
1788  break;
1789 
1790  /* search for next binary variable without locks (with position > c) */
1791  if( b <= c )
1792  {
1793  b = c + 1;
1794  binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1795  }
1796  while( !SCIPvarIsBinary(binvar) || (SCIPvarGetNLocksUp(binvar) > 0 && SCIPvarGetNLocksDown(binvar) > 0) )
1797  {
1798  ++b;
1799  assert(b < ndiscvars);
1800  binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1801  }
1802 
1803  /* swap the two variables */
1804  tmp = permutation[b];
1805  permutation[b] = permutation[c];
1806  permutation[c] = tmp;
1807 
1808  /* increase counters */
1809  ++c;
1810  ++b;
1811  }
1812  }
1813 
1814 #ifndef NDEBUG
1815  for( c = 0; c < ndiscvars; ++c )
1816  {
1817  assert((c < nbinwithoutlocks) == (SCIPvarIsBinary(SCIPcolGetVar(heurdata->lpcols[permutation[c]]))
1818  && (SCIPvarGetNLocksUp(SCIPcolGetVar(heurdata->lpcols[permutation[c]])) == 0
1819  || SCIPvarGetNLocksDown(SCIPcolGetVar(heurdata->lpcols[permutation[c]])) == 0)));
1820  }
1821 #endif
1822  }
1823 
1824  SCIP_CALL( SCIPallocBufferArray(scip, &eventdatas, matrix->ndiscvars) );
1825  BMSclearMemoryArray(eventdatas, matrix->ndiscvars);
1826 
1827  /* initialize variable events to catch bound changes during propagation */
1828  for( c = 0; c < matrix->ndiscvars; ++c )
1829  {
1830  SCIP_VAR* var;
1831 
1832  var = SCIPcolGetVar(heurdata->lpcols[c]);
1833  assert(var != NULL);
1834  assert(SCIPvarIsIntegral(var));
1835  assert(eventdatas[c] == NULL);
1836 
1837  SCIP_CALL( SCIPallocBuffer(scip, &(eventdatas[c])) ); /*lint !e866*/
1838 
1839  eventdatas[c]->colpos = c;
1840 
1841  SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], NULL) );
1842  }
1843 
1844  cutoff = FALSE;
1845 
1846  lastindexofsusp = -1;
1847  probing = heurdata->probing;
1848  infeasible = FALSE;
1849 
1850  SCIPdebugMsg(scip, "SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1851  nviolatedrows, ndiscvars);
1852 
1853  assert(matrix->ndiscvars == ndiscvars);
1854 
1855  /* loop over variables, shift them according to shifting criteria and try to reduce the global infeasibility */
1856  for( c = 0; c < ndiscvars; ++c )
1857  {
1858  SCIP_VAR* var;
1859  SCIP_Longint ndomredsfound;
1860  SCIP_Real optimalshiftvalue;
1861  SCIP_Real origsolval;
1862  SCIP_Real lb;
1863  SCIP_Real ub;
1864  int nviolations;
1865  int permutedvarindex;
1866  int j;
1867  SCIP_Bool marksuspicious;
1868 
1869  if( heurdata->selectbest )
1870  { /* search for best candidate */
1871  j = c + 1;
1872  while( j < ndiscvars )
1873  {
1874  /* run through remaining variables and search for best candidate */
1875  if( matrix->violrows[permutation[c]] < matrix->violrows[permutation[j]] )
1876  {
1877  int tmp;
1878  tmp = permutation[c];
1879  permutation[c] = permutation[j];
1880  permutation[j] = tmp;
1881  }
1882  ++j;
1883  }
1884  }
1885  permutedvarindex = permutation[c];
1886  optimalshiftvalue = 0.0;
1887  nviolations = 0;
1888  var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
1889  lb = SCIPvarGetLbLocal(var);
1890  ub = SCIPvarGetUbLocal(var);
1891  assert(SCIPcolGetLPPos(SCIPvarGetCol(var)) >= 0);
1892  assert(SCIPvarIsIntegral(var));
1893 
1894  /* check whether we hit some limit, e.g. the time limit, in between
1895  * since the check itself consumes some time, we only do it every tenth iteration
1896  */
1897  if( c % 10 == 0 && SCIPisStopped(scip) )
1898  goto TERMINATE2;
1899 
1900  /* if propagation is enabled, check if propagation has changed the variables bounds
1901  * and update the transformed upper bound correspondingly
1902  * @todo this should not be necessary
1903  */
1904  if( heurdata->probing )
1905  SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex,lb, ub, violatedrows, violatedrowpos,
1906  &nviolatedrows) );
1907 
1908  SCIPdebugMsg(scip, "Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1909  SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1910 
1911  /* ignore variable if propagation fixed it (lb and ub will be zero) */
1912  if( SCIPisFeasZero(scip, matrix->upperbounds[permutedvarindex]) )
1913  {
1914  assert(!SCIPisInfinity(scip, ub));
1915  assert(SCIPisFeasEQ(scip, lb, ub));
1916 
1917  SCIP_CALL( SCIPsetSolVal(scip, sol, var, ub) );
1918 
1919  continue;
1920  }
1921 
1922  marksuspicious = FALSE;
1923 
1924  /* check whether the variable is binary and has no locks in one direction, so that we want to fix it to the
1925  * respective bound (only enabled by parameter)
1926  */
1927  if( heurdata->fixbinlocks && SCIPvarIsBinary(var) && (SCIPvarGetNLocksUp(var) == 0 || SCIPvarGetNLocksDown(var) == 0) )
1928  {
1929  if( SCIPvarGetNLocksUp(var) == 0 )
1930  origsolval = SCIPvarGetUbLocal(var);
1931  else
1932  {
1933  assert(SCIPvarGetNLocksDown(var) == 0);
1934  origsolval = SCIPvarGetLbLocal(var);
1935  }
1936  }
1937  else
1938  {
1939  /* only apply the computationally expensive best shift selection, if there is a violated row left */
1940  if( !heurdata->stopafterfeasible || nviolatedrows > 0 )
1941  {
1942  /* compute optimal shift value for variable */
1943  SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, 1, heurdata->rowweights, steps, violationchange,
1944  &optimalshiftvalue, &nviolations) );
1945  assert(SCIPisFeasGE(scip, optimalshiftvalue, 0.0));
1946 
1947  /* Variables with FREE transform have to be dealt with twice */
1948  if( matrix->transformstatus[permutedvarindex] == TRANSFORMSTATUS_FREE )
1949  {
1950  SCIP_Real downshiftvalue;
1951  int ndownviolations;
1952 
1953  downshiftvalue = 0.0;
1954  ndownviolations = 0;
1955  SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, -1, heurdata->rowweights, steps, violationchange,
1956  &downshiftvalue, &ndownviolations) );
1957 
1958  assert(SCIPisLE(scip, downshiftvalue, 0.0));
1959 
1960  /* compare to positive direction and select the direction which makes more rows feasible */
1961  if( ndownviolations < nviolations )
1962  {
1963  optimalshiftvalue = downshiftvalue;
1964  }
1965  }
1966  }
1967  else
1968  optimalshiftvalue = 0.0;
1969 
1970  /* if zero optimal shift values are forbidden by the user parameter, delay the variable by marking it suspicious */
1971  if( heurdata->nozerofixing && nviolations > 0 && SCIPisFeasZero(scip, optimalshiftvalue) )
1972  marksuspicious = TRUE;
1973 
1974  /* retransform the solution value from the heuristic transformation space */
1975  assert(varIsDiscrete(var, impliscontinuous));
1976  origsolval = retransformVariable(scip, matrix, var, permutedvarindex, optimalshiftvalue);
1977  }
1978  assert(SCIPisFeasGE(scip, origsolval, lb) && SCIPisFeasLE(scip, origsolval, ub));
1979 
1980  /* check if propagation should still be performed
1981  * @todo do we need the hard coded value? we could use SCIP_MAXTREEDEPTH
1982  */
1983  if( nprobings > DEFAULT_PROPBREAKER )
1984  probing = FALSE;
1985 
1986  /* if propagation is enabled, fix the variable to the new solution value and propagate the fixation
1987  * (to fix other variables and to find out early whether solution is already infeasible)
1988  */
1989  if( !marksuspicious && probing )
1990  {
1991  /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
1992  * perform probing if nprobings is less than DEFAULT_PROPBREAKER (currently: 65000)
1993  */
1994  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
1995 
1996  SCIP_CALL( SCIPnewProbingNode(scip) );
1997  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
1998  ndomredsfound = 0;
1999 
2000  SCIPdebugMsg(scip, " Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2001  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2002 
2003  ++nprobings;
2004  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2005  SCIPdebugMsg(scip, "Propagation finished! <%" SCIP_LONGINT_FORMAT "> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ? "CUTOFF" : "",
2006  SCIPgetProbingDepth(scip));
2007  }
2008  assert(!cutoff || probing);
2009 
2010  /* propagation led to an empty domain, hence we backtrack and postpone the variable */
2011  if( cutoff )
2012  {
2013  assert(probing);
2014 
2015  ++ncutoffs;
2016 
2017  /* only continue heuristic if number of cutoffs occured so far is reasonably small */
2018  if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot * SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2019  break;
2020 
2021  cutoff = FALSE;
2022 
2023  /* backtrack to the parent of the current node */
2024  assert(SCIPgetProbingDepth(scip) >= 1);
2026 
2027 
2028 
2029 
2030  /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2031  * perform probing if nprobings is less than DEFAULT_PROPBREAKER (currently: 65000)
2032  */
2033  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2034 
2035  /* if the variable upper and lower bound are equal to the solution value to which we tried to fix the variable,
2036  * we are trapped at an infeasible node and break; this can only happen due to an intermediate global bound change of the variable,
2037  * I guess
2038  */
2039  if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
2040  {
2041  cutoff = TRUE;
2042  break;
2043  }
2044  else if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
2045  {
2046  /* if the variable were to be set to one of its bounds, repropagate by tightening this bound by 1.0
2047  * into the direction of the other bound, if possible */
2048  assert(SCIPisFeasGE(scip, SCIPvarGetUbLocal(var), origsolval + 1.0));
2049 
2050  ndomredsfound = 0;
2051  SCIP_CALL( SCIPnewProbingNode(scip) );
2052  SCIP_CALL( SCIPchgVarLbProbing(scip, var, origsolval + 1.0) );
2053  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2054 
2055  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2056  }
2057  else if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) )
2058  {
2059  /* if the variable were to be set to one of its bounds, repropagate by tightening this bound by 1.0
2060  * into the direction of the other bound, if possible */
2061  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), origsolval - 1.0));
2062 
2063  ndomredsfound = 0;
2064 
2065  SCIP_CALL( SCIPnewProbingNode(scip) );
2066  SCIP_CALL( SCIPchgVarUbProbing(scip, var, origsolval - 1.0) );
2067  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2068 
2069  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2070 
2071  }
2072  /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
2073  * can be stopped */
2074  if( cutoff )
2075  {
2076  break;
2077  }
2078  else
2079  {
2080  /* since repropagation was successful, we indicate that this variable led to a cutoff in one direction */
2081  marksuspicious = TRUE;
2082  }
2083  }
2084 
2085  if( marksuspicious )
2086  {
2087  /* mark the variable as suspicious */
2088  assert(permutedvarindex == permutation[c]);
2089 
2090  ++lastindexofsusp;
2091  assert(lastindexofsusp >= 0 && lastindexofsusp <= c);
2092 
2093  permutation[c] = permutation[lastindexofsusp];
2094  permutation[lastindexofsusp] = permutedvarindex;
2095 
2096  SCIPdebugMsg(scip, " Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2097  }
2098  else
2099  {
2100  SCIPdebugMsg(scip, "Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2101  SCIPvarGetName(var), optimalshiftvalue);
2102 
2103  /* update solution */
2104  SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
2105 
2106  /* only to ensure that some assertions can be made later on */
2107  if( !probing )
2108  {
2109  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
2110  }
2111  }
2112  }
2113  SCIPdebugMsg(scip, "Heuristic finished with %d remaining violations and %d remaining variables!\n",
2114  nviolatedrows, lastindexofsusp + 1);
2115 
2116  /* if constructed solution might be feasible, go through the queue of suspicious variables and set the solution
2117  * values
2118  */
2119  if( nviolatedrows == 0 && !cutoff )
2120  {
2121  SCIP_Bool stored;
2122  SCIP_Bool trysol;
2123 
2124  for( v = 0; v <= lastindexofsusp; ++v )
2125  {
2126  SCIP_VAR* var;
2127  SCIP_Real origsolval;
2128  int permutedvarindex;
2129 
2130  /* get the column position of the variable */
2131  permutedvarindex = permutation[v];
2132  var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
2133  assert(varIsDiscrete(var, impliscontinuous));
2134 
2135  /* update the transformation of the variable, since the bound might have changed after the last update. */
2136  if( heurdata->probing )
2137  SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex, SCIPvarGetLbLocal(var),
2138  SCIPvarGetUbLocal(var), violatedrows, violatedrowpos, &nviolatedrows) );
2139 
2140  /* retransform the solution value from the heuristic transformed space, set the solution value accordingly */
2141  assert(varIsDiscrete(var, impliscontinuous));
2142  origsolval = retransformVariable(scip, matrix, var, permutedvarindex, 0.0);
2143  assert(SCIPisFeasGE(scip, origsolval, SCIPvarGetLbLocal(var))
2144  && SCIPisFeasLE(scip, origsolval, SCIPvarGetUbLocal(var)));
2145  SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
2146  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) ); /* only to ensure that some assertions can be made later */
2147 
2148  SCIPdebugMsg(scip, " Remaining variable <%s> set to <%g>; %d Violations\n", SCIPvarGetName(var), origsolval,
2149  nviolatedrows);
2150  }
2151 
2152  /* Fixing of remaining variables led to infeasibility */
2153  if( nviolatedrows > 0 )
2154  goto TERMINATE2;
2155 
2156  trysol = TRUE;
2157 
2158  /* if the constructed solution might still be extendable to a feasible solution, try this by
2159  * solving the remaining LP
2160  */
2161  if( nlpcols != matrix->ndiscvars )
2162  {
2163  /* case that remaining LP has to be solved */
2164  SCIP_Bool lperror;
2165 
2166 #ifndef NDEBUG
2167  {
2168  SCIP_VAR** vars;
2169 
2170  vars = SCIPgetVars(scip);
2171  assert(vars != NULL);
2172  /* ensure that all discrete variables in the remaining LP are fixed */
2173  for( v = 0; v < ndiscvars; ++v )
2174  {
2175  if( SCIPvarIsInLP(vars[v]) )
2176  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])));
2177 
2178  }
2179  }
2180 #endif
2181 
2182  SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2183 
2184 #ifdef SCIP_DEBUG
2185  SCIP_CALL( SCIPwriteLP(scip, "shiftandpropagatelp.mps") );
2186 #endif
2187  /* solve LP;
2188  * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
2189  * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2190  */
2191 #ifdef NDEBUG
2192  {
2193  SCIP_RETCODE retstat;
2194  retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
2195  if( retstat != SCIP_OKAY )
2196  {
2197  SCIPwarningMessage(scip, "Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2198  retstat);
2199  }
2200  }
2201 #else
2202  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
2203 #endif
2204 
2205  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2206  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
2207 
2208  /* check if this is a feasible solution */
2209  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2210  {
2211  /* copy the current LP solution to the working solution */
2212  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
2213  }
2214  else
2215  trysol = FALSE;
2216 
2217  SCIPstatistic( heurdata->lpsolstat = SCIPgetLPSolstat(scip) );
2218  }
2219 
2220  /* check solution for feasibility, and add it to solution store if possible.
2221  * None of integrality, feasibility of LP rows, variable bounds have to be checked, because they
2222  * are guaranteed by the heuristic at this stage.
2223  */
2224  if( trysol )
2225  {
2226  SCIP_Bool printreason;
2227  SCIP_Bool completely;
2228 #ifdef SCIP_DEBUG
2229  printreason = TRUE;
2230 #else
2231  printreason = FALSE;
2232 #endif
2233 #ifndef NDEBUG
2234  completely = TRUE; /*lint !e838*/
2235 #else
2236  completely = FALSE;
2237 #endif
2238 
2239  /* we once also checked the variable bounds which should not be necessary */
2240  SCIP_CALL( SCIPtrySol(scip, sol, printreason, completely, FALSE, FALSE, FALSE, &stored) );
2241 
2242  if( stored )
2243  {
2244  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
2245  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
2246  *result = SCIP_FOUNDSOL;
2247 
2248  SCIPstatisticMessage(" Shiftandpropagate solution value: %16.9g \n", SCIPgetSolOrigObj(scip, sol));
2249  }
2250  }
2251  }
2252  else
2253  {
2254  SCIPdebugMsg(scip, "Solution constructed by heuristic is already known to be infeasible\n");
2255  }
2256 
2257  SCIPstatistic( heurdata->nremainingviols = nviolatedrows; );
2258 
2259  TERMINATE2:
2260  /* free allocated memory in reverse order of allocation */
2261  for( c = matrix->ndiscvars - 1; c >= 0; --c )
2262  {
2263  SCIP_VAR* var;
2264 
2265  var = SCIPcolGetVar(heurdata->lpcols[c]);
2266  assert(var != NULL);
2267  assert(eventdatas[c] != NULL);
2268 
2269  SCIP_CALL( SCIPdropVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], -1) );
2270  SCIPfreeBuffer(scip, &(eventdatas[c]));
2271  }
2272  SCIPfreeBufferArray(scip, &eventdatas);
2273 
2274  if( violatedvarrows != NULL )
2275  {
2276  assert(heurdata->sortkey == 'v' || heurdata->sortkey == 't');
2277  SCIPfreeBufferArray(scip, &violatedvarrows);
2278  }
2279  /* free all allocated memory */
2280  SCIPfreeBufferArray(scip, &violatedrowpos);
2281  SCIPfreeBufferArray(scip, &violatedrows);
2282  SCIPfreeBufferArray(scip, &violationchange);
2283  SCIPfreeBufferArray(scip, &steps);
2284  SCIPfreeBufferArray(scip, &heurdata->rowweights);
2285  SCIPfreeBufferArray(scip, &permutation);
2286  SCIP_CALL( SCIPfreeSol(scip, &sol) );
2287 
2288  eventhdlrdata->nviolatedrows = NULL;
2289  eventhdlrdata->violatedrowpos = NULL;
2290  eventhdlrdata->violatedrows = NULL;
2291 
2292  TERMINATE:
2293  /* terminate probing mode and free the remaining memory */
2294  SCIPstatistic(
2295  heurdata->ncutoffs += ncutoffs;
2296  heurdata->nprobings += nprobings;
2297  heurdata->nlpiters = SCIPgetNLPIterations(scip) - heurdata->nlpiters;
2298  );
2299 
2300  SCIP_CALL( SCIPendProbing(scip) );
2301  SCIPfreeBufferArray(scip, &heurdata->lpcols);
2302  freeMatrix(scip, &matrix);
2303  eventhdlrdata->matrix = NULL;
2304 
2305  return SCIP_OKAY;
2306 }
2307 
2308 /** event handler execution method for the heuristic which catches all
2309  * events in which a lower or upper bound were tightened */
2310 static
2311 SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
2312 { /*lint --e{715}*/
2313  SCIP_EVENTHDLRDATA* eventhdlrdata;
2314  SCIP_VAR* var;
2315  SCIP_COL* col;
2316  SCIP_Real lb;
2317  SCIP_Real ub;
2318  int colpos;
2319  CONSTRAINTMATRIX* matrix;
2320  SCIP_HEURDATA* heurdata;
2321 
2322  assert(scip != NULL);
2323  assert(eventhdlr != NULL);
2324  assert(strcmp(EVENTHDLR_NAME, SCIPeventhdlrGetName(eventhdlr)) == 0);
2325 
2326  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2327  assert(eventhdlrdata != NULL);
2328 
2329  matrix = eventhdlrdata->matrix;
2330 
2331  heurdata = eventhdlrdata->heurdata;
2332  assert(heurdata != NULL && heurdata->lpcols != NULL);
2333 
2334  colpos = eventdata->colpos;
2335 
2336  assert(0 <= colpos && colpos < matrix->ndiscvars);
2337 
2338  col = heurdata->lpcols[colpos];
2339  var = SCIPcolGetVar(col);
2340 
2341  lb = SCIPvarGetLbLocal(var);
2342  ub = SCIPvarGetUbLocal(var);
2343 
2344  SCIP_CALL( updateTransformation(scip, matrix, eventhdlrdata->heurdata, colpos, lb, ub, eventhdlrdata->violatedrows,
2345  eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );
2346 
2347  return SCIP_OKAY;
2348 }
2349 
2350 /*
2351  * primal heuristic specific interface methods
2352  */
2353 
2354 /** creates the shiftandpropagate primal heuristic and includes it in SCIP */
2356  SCIP* scip /**< SCIP data structure */
2357  )
2358 {
2359  SCIP_HEURDATA* heurdata;
2360  SCIP_HEUR* heur;
2361  SCIP_EVENTHDLRDATA* eventhandlerdata;
2362  SCIP_EVENTHDLR* eventhdlr;
2363 
2364  SCIP_CALL( SCIPallocBlockMemory(scip, &eventhandlerdata) );
2365  eventhandlerdata->matrix = NULL;
2366 
2367  eventhdlr = NULL;
2369  eventExecShiftandpropagate, eventhandlerdata) );
2370  assert(eventhdlr != NULL);
2371 
2372  /* create Shiftandpropagate primal heuristic data */
2373  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2374  heurdata->rowweights = NULL;
2375  heurdata->nlpcols = 0;
2376  heurdata->eventhdlr = eventhdlr;
2377 
2378  /* include primal heuristic */
2379  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2381  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecShiftandpropagate, heurdata) );
2382 
2383  assert(heur != NULL);
2384 
2385  /* set non-NULL pointers to callback methods */
2386  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyShiftandpropagate) );
2387  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeShiftandpropagate) );
2388  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitShiftandpropagate) );
2389  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitShiftandpropagate) );
2390 
2391 
2392  /* add shiftandpropagate primal heuristic parameters */
2393  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nproprounds",
2394  "The number of propagation rounds used for each propagation",
2395  &heurdata->nproprounds, TRUE, DEFAULT_NPROPROUNDS, -1, 1000, NULL, NULL) );
2396  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/relax", "Should continuous variables be relaxed?",
2397  &heurdata->relax, TRUE, DEFAULT_RELAX, NULL, NULL) );
2398  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/probing", "Should domains be reduced by probing?",
2399  &heurdata->probing, TRUE, DEFAULT_PROBING, NULL, NULL) );
2400  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/onlywithoutsol",
2401  "Should heuristic only be executed if no primal solution was found, yet?",
2402  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
2403  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/cutoffbreaker", "The number of cutoffs before heuristic stops",
2404  &heurdata->cutoffbreaker, TRUE, DEFAULT_CUTOFFBREAKER, -1, 1000000, NULL, NULL) );
2405  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/sortkey",
2406  "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2407  &heurdata->sortkey, TRUE, DEFAULT_SORTKEY, SORTKEYS, NULL, NULL) );
2408  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/sortvars", "Should variables be sorted for the heuristic?",
2409  &heurdata->sortvars, TRUE, DEFAULT_SORTVARS, NULL, NULL));
2410  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/collectstats", "should variable statistics be collected during probing?",
2411  &heurdata->collectstats, TRUE, DEFAULT_COLLECTSTATS, NULL, NULL) );
2412  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/stopafterfeasible",
2413  "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2414  &heurdata->stopafterfeasible, TRUE, DEFAULT_STOPAFTERFEASIBLE, NULL, NULL) );
2415  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/preferbinaries",
2416  "Should binary variables be shifted first?",
2417  &heurdata->preferbinaries, TRUE, DEFAULT_PREFERBINARIES, NULL, NULL) );
2418  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/nozerofixing",
2419  "should variables with a zero shifting value be delayed instead of being fixed?",
2420  &heurdata->nozerofixing, TRUE, DEFAULT_NOZEROFIXING, NULL, NULL) );
2421  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/fixbinlocks",
2422  "should binary variables with no locks in one direction be fixed to that direction?",
2423  &heurdata->fixbinlocks, TRUE, DEFAULT_FIXBINLOCKS, NULL, NULL) );
2424  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/binlocksfirst",
2425  "should binary variables with no locks be preferred in the ordering?",
2426  &heurdata->binlocksfirst, TRUE, DEFAULT_BINLOCKSFIRST, NULL, NULL) );
2427  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/normalize",
2428  "should coefficients and left/right hand sides be normalized by max row coeff?",
2429  &heurdata->normalize, TRUE, DEFAULT_NORMALIZE, NULL, NULL) );
2430  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/updateweights",
2431  "should row weight be increased every time the row is violated?",
2432  &heurdata->updateweights, TRUE, DEFAULT_UPDATEWEIGHTS, NULL, NULL) );
2433  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/impliscontinuous",
2434  "should implicit integer variables be treated as continuous variables?",
2435  &heurdata->impliscontinuous, TRUE, DEFAULT_IMPLISCONTINUOUS, NULL, NULL) );
2436  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/selectbest",
2437  "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
2438  &heurdata->selectbest, TRUE, DEFAULT_SELECTBEST, NULL, NULL) );
2439  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcutoffquot",
2440  "maximum percentage of allowed cutoffs before stopping the heuristic",
2441  &heurdata->maxcutoffquot, TRUE, DEFAULT_MAXCUTOFFQUOT, 0.0, 2.0, NULL, NULL) );
2442 
2443  return SCIP_OKAY;
2444 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48620
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38570
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35958
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:42327
#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:47305
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:41220
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35931
SCIP_RETCODE SCIPwriteLP(SCIP *scip, const char *filename)
Definition: scip.c:29941
#define DEFAULT_SORTKEY
#define HEUR_DESC
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48602
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16360
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8177
#define HEUR_NAME
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8611
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16540
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47381
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:16416
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#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:16271
#define DEFAULT_RELAX
static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:41741
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#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:22602
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:8084
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36034
#define DEFAULT_WEIGHT_INEQUALITY
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip.c:29243
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29556
#define DEFAULT_RANDSEED
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define HEUR_TIMING
#define SCIPdebugMsg
Definition: scip.h:455
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:4265
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11986
#define DEFAULT_ONLYWITHOUTSOL
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30883
#define HEUR_PRIORITY
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47429
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47417
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip.c:29220
static SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
#define DEFAULT_NORMALIZE
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
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:8145
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16350
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:36308
static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:36151
#define SCIPallocBuffer(scip, ptr)
Definition: scip.h:22618
#define EVENTTYPE_SHIFTANDPROPAGATE
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:35993
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define DEFAULT_PREFERBINARIES
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29690
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47331
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:36544
#define DEFAULT_NOZEROFIXING
#define SCIPfreeBlockMemoryNull(scip, ptr)
Definition: scip.h:22603
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
static SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16427
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29202
#define EVENTHDLR_NAME
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38765
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16437
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
#define HEUR_MAXDEPTH
#define HEUR_FREQOFS
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17001
#define DEFAULT_NPROPROUNDS
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2589
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:9407
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define MAX(x, y)
Definition: tclique_def.h:75
enum TransformStatus TRANSFORMSTATUS
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38529
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25952
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:41266
#define DEFAULT_MAXCUTOFFQUOT
#define DEFAULT_IMPLISCONTINUOUS
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
#define DEFAULT_WEIGHT_EQUALITY
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16990
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38988
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip.c:29267
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#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:40694
#define SCIP_MAXTREEDEPTH
Definition: def.h:286
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:11806
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:16447
#define SCIPfreeBuffer(scip, ptr)
Definition: scip.h:22630
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:39876
SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
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:4349
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
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:8161
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47369
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:16670
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:31154
#define SCIP_Longint
Definition: def.h:134
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
#define EVENTHDLR_DESC
#define DEFAULT_PROBING
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
#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:8129
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35898
#define DEFAULT_COLLECTSTATS
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35852
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:288
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
#define SCIPABORT()
Definition: def.h:322
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:16339
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16292
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16853
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:36078
static SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
void SCIPdisableVarHistory(SCIP *scip)
Definition: scip.c:25971
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:4321
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:16314
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:4239
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:37872
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:39319