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