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