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