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 2002-2022 Zuse Institute Berlin */
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  int nintvars; /* number of integer variables */
1460  int i;
1461  int r;
1462  int v;
1463  int c;
1464  int ncutoffs; /* counts the number of cutoffs for this execution */
1465  int nprobings; /* counts the number of probings */
1466  int nlprows; /* the number LP rows */
1467  int nmaxrows; /* maximum number of LP rows of a variable */
1468 
1469  SCIP_Bool initialized; /* has the matrix been initialized? */
1470  SCIP_Bool cutoff; /* has current probing node been cutoff? */
1471  SCIP_Bool probing; /* should probing be applied or not? */
1472  SCIP_Bool infeasible; /* FALSE as long as currently infeasible rows have variables left */
1473  SCIP_Bool impliscontinuous;
1474 
1475  heurdata = SCIPheurGetData(heur);
1476  assert(heurdata != NULL);
1477 
1478  eventhdlr = heurdata->eventhdlr;
1479  assert(eventhdlr != NULL);
1480 
1481  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1482  assert(eventhdlrdata != NULL);
1483 
1484  *result = SCIP_DIDNOTRUN;
1485  SCIPdebugMsg(scip, "entering execution method of shift and propagate heuristic\n");
1486 
1487  /* heuristic is obsolete if there are only continuous variables */
1488  if( SCIPgetNVars(scip) - SCIPgetNContVars(scip) == 0 )
1489  return SCIP_OKAY;
1490 
1491  /* stop execution method if there is already a primarily feasible solution at hand */
1492  if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
1493  return SCIP_OKAY;
1494 
1495  /* stop if there is no LP available */
1496  if ( ! SCIPhasCurrentNodeLP(scip) )
1497  return SCIP_OKAY;
1498 
1499  if( !SCIPisLPConstructed(scip) )
1500  {
1501  /* @note this call can have the side effect that variables are created */
1502  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1503 
1504  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1505  if( cutoff )
1506  {
1508  return SCIP_OKAY;
1509  }
1510 
1511  SCIP_CALL( SCIPflushLP(scip) );
1512  }
1513 
1514  SCIPstatistic( heurdata->nlpiters = SCIPgetNLPIterations(scip) );
1515 
1516  nlprows = SCIPgetNLPRows(scip);
1517 
1518  SCIP_CALL( SCIPgetLPColsData(scip, &lpcols, &nlpcols) );
1519  assert(nlpcols == 0 || lpcols != NULL);
1520 
1521  /* we need an LP */
1522  if( nlprows == 0 || nlpcols == 0 )
1523  return SCIP_OKAY;
1524 
1525  *result = SCIP_DIDNOTFIND;
1526  initialized = FALSE;
1527 
1528  /* allocate lp column array */
1529  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->lpcols, nlpcols) );
1530  heurdata->nlpcols = nlpcols;
1531 
1532  impliscontinuous = heurdata->impliscontinuous;
1533 
1534 #ifndef NDEBUG
1535  BMSclearMemoryArray(heurdata->lpcols, nlpcols);
1536 #endif
1537 
1538  /* copy and sort the columns by their variable types (binary before integer before implicit integer before continuous) */
1539  BMScopyMemoryArray(heurdata->lpcols, lpcols, nlpcols);
1540 
1541  SCIPsortPtr((void**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);
1542 
1543  SCIP_CALL( SCIPallocBufferArray(scip, &colposs, nlpcols) );
1544 
1545  /* we have to collect the number of different variable types before we start probing since during probing variable
1546  * can be created (e.g., cons_xor.c)
1547  */
1548  ndiscvars = 0;
1549  nbinvars = 0;
1550  nintvars = 0;
1551  for( c = 0; c < nlpcols; ++c )
1552  {
1553  SCIP_COL* col;
1554  SCIP_VAR* colvar;
1555 
1556  col = heurdata->lpcols[c];
1557  assert(col != NULL);
1558  colvar = SCIPcolGetVar(col);
1559  assert(colvar != NULL);
1560 
1561  if( varIsDiscrete(colvar, impliscontinuous) )
1562  ++ndiscvars;
1563  if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY )
1564  ++nbinvars;
1565  else if( SCIPvarGetType(colvar) == SCIP_VARTYPE_INTEGER )
1566  ++nintvars;
1567 
1568  /* save the position of this column in the array such that it can be accessed as the "true" column position */
1569  assert(SCIPcolGetLPPos(col) >= 0);
1570  colposs[SCIPcolGetLPPos(col)] = c;
1571  }
1572  assert(nbinvars + nintvars <= ndiscvars);
1573 
1574  /* start probing mode */
1575  SCIP_CALL( SCIPstartProbing(scip) );
1576 
1577  /* enables collection of variable statistics during probing */
1578  if( heurdata->collectstats )
1579  SCIPenableVarHistory(scip);
1580  else
1581  SCIPdisableVarHistory(scip);
1582 
1583  /* this should always be fulfilled because we perform shift and propagate only at the root node */
1584  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
1585 
1586  /* @todo check if this node is necessary (I don't think so) */
1587  SCIP_CALL( SCIPnewProbingNode(scip) );
1588  ncutoffs = 0;
1589  nprobings = 0;
1590  nmaxrows = 0;
1591  infeasible = FALSE;
1592 
1593  /* initialize heuristic matrix and working solution */
1594  SCIP_CALL( SCIPallocBuffer(scip, &matrix) );
1595  SCIP_CALL( initMatrix(scip, matrix, heurdata, colposs, heurdata->normalize, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1596 
1597  /* could not initialize matrix */
1598  if( !initialized || infeasible )
1599  {
1600  SCIPdebugMsg(scip, " MATRIX not initialized -> Execution of heuristic stopped! \n");
1601  goto TERMINATE;
1602  }
1603 
1604  /* the number of discrete LP column variables can be less than the actual number of variables, if, e.g., there
1605  * are nonlinearities in the problem. The heuristic execution can be terminated in that case.
1606  */
1607  if( matrix->ndiscvars < ndiscvars )
1608  {
1609  SCIPdebugMsg(scip, "Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1610  goto TERMINATE;
1611  }
1612 
1613  assert(nmaxrows > 0);
1614 
1615  eventhdlrdata->matrix = matrix;
1616  eventhdlrdata->heurdata = heurdata;
1617 
1618  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1619  SCIPsolSetHeur(sol, heur);
1620 
1621  /* allocate arrays for execution method */
1622  SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ndiscvars) );
1623  SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rowweights, matrix->nrows) );
1624 
1625  /* allocate necessary memory for best shift search */
1626  SCIP_CALL( SCIPallocBufferArray(scip, &steps, nmaxrows) );
1627  SCIP_CALL( SCIPallocBufferArray(scip, &violationchange, nmaxrows) );
1628 
1629  /* allocate arrays to store information about infeasible rows */
1630  SCIP_CALL( SCIPallocBufferArray(scip, &violatedrows, matrix->nrows) );
1631  SCIP_CALL( SCIPallocBufferArray(scip, &violatedrowpos, matrix->nrows) );
1632 
1633  eventhdlrdata->violatedrows = violatedrows;
1634  eventhdlrdata->violatedrowpos = violatedrowpos;
1635  eventhdlrdata->nviolatedrows = &nviolatedrows;
1636 
1637  /* initialize arrays. Before sorting, permutation is the identity permutation */
1638  for( i = 0; i < ndiscvars; ++i )
1639  permutation[i] = i;
1640 
1641  /* initialize row weights */
1642  for( r = 0; r < matrix->nrows; ++r )
1643  {
1644  if( !SCIPisInfinity(scip, -(matrix->lhs[r])) && !SCIPisInfinity(scip, matrix->rhs[r]) )
1645  heurdata->rowweights[r] = DEFAULT_WEIGHT_EQUALITY;
1646  else
1647  heurdata->rowweights[r] = DEFAULT_WEIGHT_INEQUALITY;
1648  }
1649  colnorms = matrix->colnorms;
1650 
1651  assert(nbinvars >= 0);
1652  assert(nintvars >= 0);
1653 
1654  /* check rows for infeasibility */
1655  checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1656 
1657  /* allocate memory for violatedvarrows array only if variable ordering relies on it */
1658  if( heurdata->sortvars && (heurdata->sortkey == 't' || heurdata->sortkey == 'v') )
1659  {
1660  SCIP_CALL( SCIPallocBufferArray(scip, &violatedvarrows, ndiscvars) );
1661  BMScopyMemoryArray(violatedvarrows, matrix->violrows, ndiscvars);
1662  }
1663  else
1664  violatedvarrows = NULL;
1665 
1666  /* sort variables w.r.t. the sorting key parameter. Sorting is indirect, all matrix column data
1667  * stays in place, but permutation array gives access to the sorted order of variables
1668  */
1669  if( heurdata->sortvars )
1670  {
1671  switch (heurdata->sortkey)
1672  {
1673  case 'n':
1674  /* variable ordering w.r.t. column norms nonincreasing */
1675  if( heurdata->preferbinaries )
1676  {
1677  if( nbinvars > 0 )
1678  SCIPsortDownRealInt(colnorms, permutation, nbinvars);
1679  if( nbinvars < ndiscvars )
1680  SCIPsortDownRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1681  }
1682  else
1683  {
1684  SCIPsortDownRealInt(colnorms, permutation, ndiscvars);
1685  }
1686  SCIPdebugMsg(scip, "Variables sorted down w.r.t their normalized columns!\n");
1687  break;
1688  case 'u':
1689  /* variable ordering w.r.t. column norms nondecreasing */
1690  if( heurdata->preferbinaries )
1691  {
1692  if( nbinvars > 0 )
1693  SCIPsortRealInt(colnorms, permutation, nbinvars);
1694  if( nbinvars < ndiscvars )
1695  SCIPsortRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1696  }
1697  else
1698  {
1699  SCIPsortRealInt(colnorms, permutation, ndiscvars);
1700  }
1701  SCIPdebugMsg(scip, "Variables sorted w.r.t their normalized columns!\n");
1702  break;
1703  case 'v':
1704  /* variable ordering w.r.t. nonincreasing number of violated rows */
1705  assert(violatedvarrows != NULL);
1706  if( heurdata->preferbinaries )
1707  {
1708  if( nbinvars > 0 )
1709  SCIPsortDownIntInt(violatedvarrows, permutation, nbinvars);
1710  if( nbinvars < ndiscvars )
1711  SCIPsortDownIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1712  }
1713  else
1714  {
1715  SCIPsortDownIntInt(violatedvarrows, permutation, ndiscvars);
1716  }
1717 
1718  SCIPdebugMsg(scip, "Variables sorted down w.r.t their number of currently infeasible rows!\n");
1719  break;
1720  case 't':
1721  /* variable ordering w.r.t. nondecreasing number of violated rows */
1722  assert(violatedvarrows != NULL);
1723  if( heurdata->preferbinaries )
1724  {
1725  if( nbinvars > 0 )
1726  SCIPsortIntInt(violatedvarrows, permutation, nbinvars);
1727  if( nbinvars < ndiscvars )
1728  SCIPsortIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1729  }
1730  else
1731  {
1732  SCIPsortIntInt(violatedvarrows, permutation, ndiscvars);
1733  }
1734 
1735  SCIPdebugMsg(scip, "Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1736  break;
1737  case 'r':
1738  /* random sorting */
1739  if( heurdata->preferbinaries )
1740  {
1741  if( nbinvars > 0 )
1742  SCIPrandomPermuteIntArray(heurdata->randnumgen, permutation, 0, nbinvars - 1);
1743  if( nbinvars < ndiscvars )
1744  SCIPrandomPermuteIntArray(heurdata->randnumgen, &permutation[nbinvars], nbinvars - 1,
1745  ndiscvars - nbinvars - 1);
1746  }
1747  else
1748  {
1749  SCIPrandomPermuteIntArray(heurdata->randnumgen, permutation, 0, ndiscvars - 1);
1750  }
1751  SCIPdebugMsg(scip, "Variables permuted randomly!\n");
1752  break;
1753  default:
1754  SCIPdebugMsg(scip, "No variable permutation applied\n");
1755  break;
1756  }
1757  }
1758 
1759  /* should binary variables without locks be treated first? */
1760  if( heurdata->binlocksfirst )
1761  {
1762  SCIP_VAR* var;
1763  int nbinwithoutlocks = 0;
1764 
1765  /* count number of binaries without locks */
1766  if( heurdata->preferbinaries )
1767  {
1768  for( c = 0; c < nbinvars; ++c )
1769  {
1770  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1773  ++nbinwithoutlocks;
1774  }
1775  }
1776  else
1777  {
1778  for( c = 0; c < ndiscvars; ++c )
1779  {
1780  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1781  if( SCIPvarIsBinary(var) )
1782  {
1785  ++nbinwithoutlocks;
1786  }
1787  }
1788  }
1789 
1790  if( nbinwithoutlocks > 0 )
1791  {
1792  SCIP_VAR* binvar;
1793  int b = 1;
1794  int tmp;
1795  c = 0;
1796 
1797  /* if c reaches nbinwithoutlocks, then all binary variables without locks were sorted to the beginning of the array */
1798  while( c < nbinwithoutlocks && b < ndiscvars )
1799  {
1800  assert(c < b);
1801  assert(c < ndiscvars);
1802  assert(b < ndiscvars);
1803  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1804  binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1805 
1806  /* search for next variable which is not a binary variable without locks */
1809  {
1810  ++c;
1811  if( c >= nbinwithoutlocks )
1812  break;
1813  var = SCIPcolGetVar(heurdata->lpcols[permutation[c]]);
1814  }
1815  if( c >= nbinwithoutlocks )
1816  break;
1817 
1818  /* search for next binary variable without locks (with position > c) */
1819  if( b <= c )
1820  {
1821  b = c + 1;
1822  binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1823  }
1824  while( !SCIPvarIsBinary(binvar) || (SCIPvarGetNLocksUpType(binvar, SCIP_LOCKTYPE_MODEL) > 0
1826  {
1827  ++b;
1828  assert(b < ndiscvars);
1829  binvar = SCIPcolGetVar(heurdata->lpcols[permutation[b]]);
1830  }
1831 
1832  /* swap the two variables */
1833  tmp = permutation[b];
1834  permutation[b] = permutation[c];
1835  permutation[c] = tmp;
1836 
1837  /* increase counters */
1838  ++c;
1839  ++b;
1840  }
1841  }
1842 
1843 #ifndef NDEBUG
1844  for( c = 0; c < ndiscvars; ++c )
1845  {
1846  assert((c < nbinwithoutlocks) == (SCIPvarIsBinary(SCIPcolGetVar(heurdata->lpcols[permutation[c]]))
1847  && (SCIPvarGetNLocksUpType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0
1848  || SCIPvarGetNLocksDownType(SCIPcolGetVar(heurdata->lpcols[permutation[c]]), SCIP_LOCKTYPE_MODEL) == 0)));
1849  }
1850 #endif
1851  }
1852 
1853  SCIP_CALL( SCIPallocBufferArray(scip, &eventdatas, matrix->ndiscvars) );
1854  BMSclearMemoryArray(eventdatas, matrix->ndiscvars);
1855 
1856  /* initialize variable events to catch bound changes during propagation */
1857  for( c = 0; c < matrix->ndiscvars; ++c )
1858  {
1859  SCIP_VAR* var;
1860 
1861  var = SCIPcolGetVar(heurdata->lpcols[c]);
1862  assert(var != NULL);
1863  assert(SCIPvarIsIntegral(var));
1864  assert(eventdatas[c] == NULL);
1865 
1866  SCIP_CALL( SCIPallocBuffer(scip, &(eventdatas[c])) ); /*lint !e866*/
1867 
1868  eventdatas[c]->colpos = c;
1869 
1870  SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], NULL) );
1871  }
1872 
1873  cutoff = FALSE;
1874 
1875  lastindexofsusp = -1;
1876  probing = heurdata->probing;
1877  infeasible = FALSE;
1878 
1879  SCIPdebugMsg(scip, "SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1880  nviolatedrows, ndiscvars);
1881 
1882  assert(matrix->ndiscvars == ndiscvars);
1883 
1884  /* loop over variables, shift them according to shifting criteria and try to reduce the global infeasibility */
1885  for( c = 0; c < ndiscvars; ++c )
1886  {
1887  SCIP_VAR* var;
1888  SCIP_Longint ndomredsfound;
1889  SCIP_Real optimalshiftvalue;
1890  SCIP_Real origsolval;
1891  SCIP_Real lb;
1892  SCIP_Real ub;
1893  int nviolations;
1894  int permutedvarindex;
1895  int j;
1896  SCIP_Bool marksuspicious;
1897 
1898  if( heurdata->selectbest )
1899  { /* search for best candidate */
1900  j = c + 1;
1901  while( j < ndiscvars )
1902  {
1903  /* run through remaining variables and search for best candidate */
1904  if( matrix->violrows[permutation[c]] < matrix->violrows[permutation[j]] )
1905  {
1906  int tmp;
1907  tmp = permutation[c];
1908  permutation[c] = permutation[j];
1909  permutation[j] = tmp;
1910  }
1911  ++j;
1912  }
1913  }
1914  permutedvarindex = permutation[c];
1915  optimalshiftvalue = 0.0;
1916  nviolations = 0;
1917  var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
1918  lb = SCIPvarGetLbLocal(var);
1919  ub = SCIPvarGetUbLocal(var);
1920  assert(SCIPcolGetLPPos(SCIPvarGetCol(var)) >= 0);
1921  assert(SCIPvarIsIntegral(var));
1922 
1923  /* check whether we hit some limit, e.g. the time limit, in between
1924  * since the check itself consumes some time, we only do it every tenth iteration
1925  */
1926  if( c % 10 == 0 && SCIPisStopped(scip) )
1927  goto TERMINATE2;
1928 
1929  /* if propagation is enabled, check if propagation has changed the variables bounds
1930  * and update the transformed upper bound correspondingly
1931  * @todo this should not be necessary
1932  */
1933  if( heurdata->probing )
1934  {
1935  SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex,lb, ub, violatedrows, violatedrowpos,
1936  &nviolatedrows) );
1937  }
1938 
1939  SCIPdebugMsg(scip, "Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1940  SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1941 
1942  /* ignore variable if propagation fixed it (lb and ub will be zero) */
1943  if( SCIPisFeasZero(scip, matrix->upperbounds[permutedvarindex]) )
1944  {
1945  assert(!SCIPisInfinity(scip, ub));
1946  assert(SCIPisFeasEQ(scip, lb, ub));
1947 
1948  SCIP_CALL( SCIPsetSolVal(scip, sol, var, ub) );
1949 
1950  continue;
1951  }
1952 
1953  marksuspicious = FALSE;
1954 
1955  /* check whether the variable is binary and has no locks in one direction, so that we want to fix it to the
1956  * respective bound (only enabled by parameter)
1957  */
1958  if( heurdata->fixbinlocks && SCIPvarIsBinary(var)
1961  {
1963  origsolval = SCIPvarGetUbLocal(var);
1964  else
1965  {
1966  assert(SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 0);
1967  origsolval = SCIPvarGetLbLocal(var);
1968  }
1969  }
1970  else
1971  {
1972  /* only apply the computationally expensive best shift selection, if there is a violated row left */
1973  if( !heurdata->stopafterfeasible || nviolatedrows > 0 )
1974  {
1975  /* compute optimal shift value for variable */
1976  SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, 1, heurdata->rowweights, steps, violationchange,
1977  &optimalshiftvalue, &nviolations) );
1978  assert(SCIPisFeasGE(scip, optimalshiftvalue, 0.0));
1979 
1980  /* Variables with FREE transform have to be dealt with twice */
1981  if( matrix->transformstatus[permutedvarindex] == TRANSFORMSTATUS_FREE )
1982  {
1983  SCIP_Real downshiftvalue;
1984  int ndownviolations;
1985 
1986  downshiftvalue = 0.0;
1987  ndownviolations = 0;
1988  SCIP_CALL( getOptimalShiftingValue(scip, matrix, permutedvarindex, -1, heurdata->rowweights, steps, violationchange,
1989  &downshiftvalue, &ndownviolations) );
1990 
1991  assert(SCIPisLE(scip, downshiftvalue, 0.0));
1992 
1993  /* compare to positive direction and select the direction which makes more rows feasible */
1994  if( ndownviolations < nviolations )
1995  {
1996  optimalshiftvalue = downshiftvalue;
1997  }
1998  }
1999  }
2000  else
2001  optimalshiftvalue = 0.0;
2002 
2003  /* if zero optimal shift values are forbidden by the user parameter, delay the variable by marking it suspicious */
2004  if( heurdata->nozerofixing && nviolations > 0 && SCIPisFeasZero(scip, optimalshiftvalue) )
2005  marksuspicious = TRUE;
2006 
2007  /* retransform the solution value from the heuristic transformation space */
2008  assert(varIsDiscrete(var, impliscontinuous));
2009  origsolval = retransformVariable(scip, matrix, var, permutedvarindex, optimalshiftvalue);
2010  }
2011  assert(SCIPisFeasGE(scip, origsolval, lb) && SCIPisFeasLE(scip, origsolval, ub));
2012 
2013  /* check if propagation should still be performed
2014  * @todo do we need the hard coded value? we could use SCIP_MAXTREEDEPTH
2015  */
2016  if( nprobings > DEFAULT_PROPBREAKER )
2017  probing = FALSE;
2018 
2019  /* if propagation is enabled, fix the variable to the new solution value and propagate the fixation
2020  * (to fix other variables and to find out early whether solution is already infeasible)
2021  */
2022  if( !marksuspicious && probing )
2023  {
2024  /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2025  * perform probing if nprobings is less than DEFAULT_PROPBREAKER (currently: 65000)
2026  */
2027  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2028 
2029  SCIP_CALL( SCIPnewProbingNode(scip) );
2030  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
2031  ndomredsfound = 0;
2032 
2033  SCIPdebugMsg(scip, " Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2034  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2035 
2036  ++nprobings;
2037  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2038  SCIPdebugMsg(scip, "Propagation finished! <%" SCIP_LONGINT_FORMAT "> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ? "CUTOFF" : "",
2039  SCIPgetProbingDepth(scip));
2040  }
2041  assert(!cutoff || probing);
2042 
2043  /* propagation led to an empty domain, hence we backtrack and postpone the variable */
2044  if( cutoff )
2045  {
2046  assert(probing);
2047 
2048  ++ncutoffs;
2049 
2050  /* only continue heuristic if number of cutoffs occured so far is reasonably small */
2051  if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot * SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2052  break;
2053 
2054  cutoff = FALSE;
2055 
2056  /* backtrack to the parent of the current node */
2057  assert(SCIPgetProbingDepth(scip) >= 1);
2059 
2060  /* this assert should be always fulfilled because we run this heuristic at the root node only and do not
2061  * perform probing if nprobings is less than DEFAULT_PROPBREAKER (currently: 65000)
2062  */
2063  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2064 
2065  /* if the variable upper and lower bound are equal to the solution value to which we tried to fix the variable,
2066  * we are trapped at an infeasible node and break; this can only happen due to an intermediate global bound change of the variable,
2067  * I guess
2068  */
2069  if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) )
2070  {
2071  cutoff = TRUE;
2072  break;
2073  }
2074  else if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2075  {
2076  /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2077  * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2078  */
2079  assert(SCIPisFeasGE(scip, SCIPvarGetUbLocal(var), origsolval + 1.0));
2080 
2081  ndomredsfound = 0;
2082  SCIP_CALL( SCIPnewProbingNode(scip) );
2083  SCIP_CALL( SCIPchgVarLbProbing(scip, var, origsolval + 1.0) );
2084  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2085 
2086  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2087  }
2088  else if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), origsolval) && REALABS( origsolval ) < 1.0 / SCIPepsilon(scip) )
2089  {
2090  /* if the variable was set to one of its bounds, repropagate by tightening this bound by 1.0 into the
2091  * direction of the other bound, if possible; if the bound is too large (in abs value) do not even bother
2092  */
2093  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), origsolval - 1.0));
2094 
2095  ndomredsfound = 0;
2096 
2097  SCIP_CALL( SCIPnewProbingNode(scip) );
2098  SCIP_CALL( SCIPchgVarUbProbing(scip, var, origsolval - 1.0) );
2099  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->nproprounds, &cutoff, &ndomredsfound) );
2100 
2101  SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2102  }
2103 
2104  /* if the tightened bound again leads to a cutoff, both subproblems are proven infeasible and the heuristic
2105  * can be stopped */
2106  if( cutoff )
2107  {
2108  break;
2109  }
2110  else
2111  {
2112  /* since repropagation was successful, we indicate that this variable led to a cutoff in one direction */
2113  marksuspicious = TRUE;
2114  }
2115  }
2116 
2117  if( marksuspicious )
2118  {
2119  /* mark the variable as suspicious */
2120  assert(permutedvarindex == permutation[c]);
2121 
2122  ++lastindexofsusp;
2123  assert(lastindexofsusp >= 0 && lastindexofsusp <= c);
2124 
2125  permutation[c] = permutation[lastindexofsusp];
2126  permutation[lastindexofsusp] = permutedvarindex;
2127 
2128  SCIPdebugMsg(scip, " Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2129  }
2130  else
2131  {
2132  SCIPdebugMsg(scip, "Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2133  SCIPvarGetName(var), optimalshiftvalue);
2134 
2135  /* update solution */
2136  SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
2137 
2138  /* only to ensure that some assertions can be made later on */
2139  if( !probing )
2140  {
2141  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) );
2142  }
2143  }
2144  }
2145  SCIPdebugMsg(scip, "Heuristic finished with %d remaining violations and %d remaining variables!\n",
2146  nviolatedrows, lastindexofsusp + 1);
2147 
2148  /* if constructed solution might be feasible, go through the queue of suspicious variables and set the solution
2149  * values
2150  */
2151  if( nviolatedrows == 0 && !cutoff )
2152  {
2153  SCIP_Bool stored;
2154  SCIP_Bool trysol;
2155  SCIP_Bool solvelp;
2156 
2157  for( v = 0; v <= lastindexofsusp; ++v )
2158  {
2159  SCIP_VAR* var;
2160  SCIP_Real origsolval;
2161  int permutedvarindex;
2162 
2163  /* get the column position of the variable */
2164  permutedvarindex = permutation[v];
2165  var = SCIPcolGetVar(heurdata->lpcols[permutedvarindex]);
2166  assert(varIsDiscrete(var, impliscontinuous));
2167 
2168  /* update the transformation of the variable, since the bound might have changed after the last update. */
2169  if( heurdata->probing )
2170  SCIP_CALL( updateTransformation(scip, matrix, heurdata, permutedvarindex, SCIPvarGetLbLocal(var),
2171  SCIPvarGetUbLocal(var), violatedrows, violatedrowpos, &nviolatedrows) );
2172 
2173  /* retransform the solution value from the heuristic transformed space, set the solution value accordingly */
2174  assert(varIsDiscrete(var, impliscontinuous));
2175  origsolval = retransformVariable(scip, matrix, var, permutedvarindex, 0.0);
2176  assert(SCIPisFeasGE(scip, origsolval, SCIPvarGetLbLocal(var))
2177  && SCIPisFeasLE(scip, origsolval, SCIPvarGetUbLocal(var)));
2178  SCIP_CALL( SCIPsetSolVal(scip, sol, var, origsolval) );
2179  SCIP_CALL( SCIPfixVarProbing(scip, var, origsolval) ); /* only to ensure that some assertions can be made later */
2180 
2181  SCIPdebugMsg(scip, " Remaining variable <%s> set to <%g>; %d Violations\n", SCIPvarGetName(var), origsolval,
2182  nviolatedrows);
2183  }
2184 
2185  /* Fixing of remaining variables led to infeasibility */
2186  if( nviolatedrows > 0 )
2187  goto TERMINATE2;
2188 
2189  trysol = TRUE;
2190 
2191  /* check if enough variables have been fixed (including continuous) to solve the remaining LP */
2192  if( nlpcols != matrix->ndiscvars )
2193  {
2194  SCIP_VAR** vars;
2195  int nvars = SCIPgetNVars(scip);
2196  int nminfixings = (int)(SCIPceil(scip, heurdata->minfixingratelp * nvars));
2197  int nfixedvars = ndiscvars;
2198 
2199  vars = SCIPgetVars(scip);
2200 
2201  /* count fixed variables */
2202  for( v = ndiscvars; v < nvars && nfixedvars < nminfixings; ++v )
2203  {
2204  if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
2205  ++nfixedvars;
2206  }
2207 
2208  solvelp = (nfixedvars >= nminfixings);
2209  trysol = solvelp;
2210  SCIPdebugMsg(scip, "Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
2211  nfixedvars, nvars, (100.0 * nfixedvars / (SCIP_Real)nvars),
2212  solvelp ? "continue and solve LP for remaining variables" : "terminate without LP");
2213  }
2214  else /* no need to solve an LP */
2215  solvelp = FALSE;
2216 
2217  /* if the constructed solution might still be extendable to a feasible solution, try this by
2218  * solving the remaining LP
2219  */
2220  if( solvelp )
2221  {
2222  char strbuf[SCIP_MAXSTRLEN];
2223  /* case that remaining LP has to be solved */
2224  SCIP_Bool lperror;
2225  int ncols;
2226 
2227 #ifndef NDEBUG
2228  {
2229  SCIP_VAR** vars;
2230 
2231  vars = SCIPgetVars(scip);
2232  assert(vars != NULL);
2233  /* ensure that all discrete variables in the remaining LP are fixed */
2234  for( v = 0; v < ndiscvars; ++v )
2235  {
2236  if( SCIPvarIsInLP(vars[v]) )
2237  {
2238  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])));
2239  }
2240  }
2241  }
2242 #endif
2243 
2244  /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
2245  * which the user sees no output; more detailed probing stats only in debug mode */
2246  ncols = SCIPgetNLPCols(scip);
2247  if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
2248  {
2249  int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
2250 
2251  if( nunfixedcols > 0.5 * ncols )
2252  {
2254  "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
2255  100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
2256  }
2257  }
2258  SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
2259  SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN));
2260  SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2261 
2262 #ifdef SCIP_DEBUG
2263  SCIP_CALL( SCIPwriteLP(scip, "shiftandpropagatelp.mps") );
2264 #endif
2265  /* solve LP;
2266  * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
2267  * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2268  */
2269 #ifdef NDEBUG
2270  {
2271  SCIP_RETCODE retstat;
2272  retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
2273  if( retstat != SCIP_OKAY )
2274  {
2275  SCIPwarningMessage(scip, "Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2276  retstat);
2277  }
2278  }
2279 #else
2280  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
2281 #endif
2282 
2283  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
2284  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
2285 
2286  /* check if this is a feasible solution */
2287  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2288  {
2289  /* copy the current LP solution to the working solution */
2290  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
2291  }
2292  else
2293  trysol = FALSE;
2294 
2295  SCIPstatistic( heurdata->lpsolstat = SCIPgetLPSolstat(scip) );
2296  }
2297 
2298  /* check solution for feasibility, and add it to solution store if possible.
2299  * None of integrality, feasibility of LP rows, variable bounds have to be checked, because they
2300  * are guaranteed by the heuristic at this stage.
2301  */
2302  if( trysol )
2303  {
2304  SCIP_Bool printreason;
2305  SCIP_Bool completely;
2306 #ifdef SCIP_DEBUG
2307  printreason = TRUE;
2308 #else
2309  printreason = FALSE;
2310 #endif
2311 #ifndef NDEBUG
2312  completely = TRUE; /*lint !e838*/
2313 #else
2314  completely = FALSE;
2315 #endif
2316 
2317  /* we once also checked the variable bounds which should not be necessary */
2318  SCIP_CALL( SCIPtrySol(scip, sol, printreason, completely, FALSE, FALSE, FALSE, &stored) );
2319 
2320  if( stored )
2321  {
2322  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
2323  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
2324  *result = SCIP_FOUNDSOL;
2325 
2326  SCIPstatisticMessage(" Shiftandpropagate solution value: %16.9g \n", SCIPgetSolOrigObj(scip, sol));
2327  }
2328  }
2329  }
2330  else
2331  {
2332  SCIPdebugMsg(scip, "Solution constructed by heuristic is already known to be infeasible\n");
2333  }
2334 
2335  SCIPstatistic( heurdata->nremainingviols = nviolatedrows; );
2336 
2337  TERMINATE2:
2338  /* free allocated memory in reverse order of allocation */
2339  for( c = matrix->ndiscvars - 1; c >= 0; --c )
2340  {
2341  SCIP_VAR* var;
2342 
2343  var = SCIPcolGetVar(heurdata->lpcols[c]);
2344  assert(var != NULL);
2345  assert(eventdatas[c] != NULL);
2346 
2347  SCIP_CALL( SCIPdropVarEvent(scip, var, EVENTTYPE_SHIFTANDPROPAGATE, eventhdlr, eventdatas[c], -1) );
2348  SCIPfreeBuffer(scip, &(eventdatas[c]));
2349  }
2350  SCIPfreeBufferArray(scip, &eventdatas);
2351 
2352  if( violatedvarrows != NULL )
2353  {
2354  assert(heurdata->sortkey == 'v' || heurdata->sortkey == 't');
2355  SCIPfreeBufferArray(scip, &violatedvarrows);
2356  }
2357  /* free all allocated memory */
2358  SCIPfreeBufferArray(scip, &violatedrowpos);
2359  SCIPfreeBufferArray(scip, &violatedrows);
2360  SCIPfreeBufferArray(scip, &violationchange);
2361  SCIPfreeBufferArray(scip, &steps);
2362  SCIPfreeBufferArray(scip, &heurdata->rowweights);
2363  SCIPfreeBufferArray(scip, &permutation);
2364  SCIP_CALL( SCIPfreeSol(scip, &sol) );
2365 
2366  eventhdlrdata->nviolatedrows = NULL;
2367  eventhdlrdata->violatedrowpos = NULL;
2368  eventhdlrdata->violatedrows = NULL;
2369 
2370  TERMINATE:
2371  /* terminate probing mode and free the remaining memory */
2372  SCIPstatistic(
2373  heurdata->ncutoffs += ncutoffs;
2374  heurdata->nprobings += nprobings;
2375  heurdata->nlpiters = SCIPgetNLPIterations(scip) - heurdata->nlpiters;
2376  );
2377 
2378  SCIP_CALL( SCIPendProbing(scip) );
2379  freeMatrix(scip, &matrix);
2380  SCIPfreeBufferArray(scip, &colposs);
2381  SCIPfreeBufferArray(scip, &heurdata->lpcols);
2382  eventhdlrdata->matrix = NULL;
2383 
2384  return SCIP_OKAY;
2385 }
2386 
2387 /** event handler execution method for the heuristic which catches all
2388  * events in which a lower or upper bound were tightened */
2389 static
2390 SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
2391 { /*lint --e{715}*/
2392  SCIP_EVENTHDLRDATA* eventhdlrdata;
2393  SCIP_VAR* var;
2394  SCIP_COL* col;
2395  SCIP_Real lb;
2396  SCIP_Real ub;
2397  int colpos;
2398  CONSTRAINTMATRIX* matrix;
2399  SCIP_HEURDATA* heurdata;
2400 
2401  assert(scip != NULL);
2402  assert(eventhdlr != NULL);
2403  assert(strcmp(EVENTHDLR_NAME, SCIPeventhdlrGetName(eventhdlr)) == 0);
2404 
2405  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2406  assert(eventhdlrdata != NULL);
2407 
2408  matrix = eventhdlrdata->matrix;
2409 
2410  heurdata = eventhdlrdata->heurdata;
2411  assert(heurdata != NULL && heurdata->lpcols != NULL);
2412 
2413  colpos = eventdata->colpos;
2414 
2415  assert(0 <= colpos && colpos < matrix->ndiscvars);
2416 
2417  col = heurdata->lpcols[colpos];
2418  var = SCIPcolGetVar(col);
2419 
2420  lb = SCIPvarGetLbLocal(var);
2421  ub = SCIPvarGetUbLocal(var);
2422 
2423  SCIP_CALL( updateTransformation(scip, matrix, eventhdlrdata->heurdata, colpos, lb, ub, eventhdlrdata->violatedrows,
2424  eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );
2425 
2426  return SCIP_OKAY;
2427 }
2428 
2429 /*
2430  * primal heuristic specific interface methods
2431  */
2432 
2433 /** creates the shiftandpropagate primal heuristic and includes it in SCIP */
2435  SCIP* scip /**< SCIP data structure */
2436  )
2437 {
2438  SCIP_HEURDATA* heurdata;
2439  SCIP_HEUR* heur;
2440  SCIP_EVENTHDLRDATA* eventhandlerdata;
2441  SCIP_EVENTHDLR* eventhdlr;
2442 
2443  SCIP_CALL( SCIPallocBlockMemory(scip, &eventhandlerdata) );
2444  eventhandlerdata->matrix = NULL;
2445 
2446  eventhdlr = NULL;
2448  eventExecShiftandpropagate, eventhandlerdata) );
2449  assert(eventhdlr != NULL);
2450 
2451  /* create Shiftandpropagate primal heuristic data */
2452  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2453  heurdata->rowweights = NULL;
2454  heurdata->nlpcols = 0;
2455  heurdata->eventhdlr = eventhdlr;
2456 
2457  /* include primal heuristic */
2458  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2460  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecShiftandpropagate, heurdata) );
2461 
2462  assert(heur != NULL);
2463 
2464  /* set non-NULL pointers to callback methods */
2465  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyShiftandpropagate) );
2466  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeShiftandpropagate) );
2467  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitShiftandpropagate) );
2468  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitShiftandpropagate) );
2469 
2470  /* add shiftandpropagate primal heuristic parameters */
2471  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nproprounds",
2472  "The number of propagation rounds used for each propagation",
2473  &heurdata->nproprounds, TRUE, DEFAULT_NPROPROUNDS, -1, 1000, NULL, NULL) );
2474  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/relax", "Should continuous variables be relaxed?",
2475  &heurdata->relax, TRUE, DEFAULT_RELAX, NULL, NULL) );
2476  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/probing", "Should domains be reduced by probing?",
2477  &heurdata->probing, TRUE, DEFAULT_PROBING, NULL, NULL) );
2478  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/onlywithoutsol",
2479  "Should heuristic only be executed if no primal solution was found, yet?",
2480  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
2481  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/cutoffbreaker", "The number of cutoffs before heuristic stops",
2482  &heurdata->cutoffbreaker, TRUE, DEFAULT_CUTOFFBREAKER, -1, 1000000, NULL, NULL) );
2483  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/sortkey",
2484  "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2485  &heurdata->sortkey, TRUE, DEFAULT_SORTKEY, SORTKEYS, NULL, NULL) );
2486  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/sortvars", "Should variables be sorted for the heuristic?",
2487  &heurdata->sortvars, TRUE, DEFAULT_SORTVARS, NULL, NULL));
2488  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/collectstats", "should variable statistics be collected during probing?",
2489  &heurdata->collectstats, TRUE, DEFAULT_COLLECTSTATS, NULL, NULL) );
2490  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/stopafterfeasible",
2491  "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2492  &heurdata->stopafterfeasible, TRUE, DEFAULT_STOPAFTERFEASIBLE, NULL, NULL) );
2493  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/preferbinaries",
2494  "Should binary variables be shifted first?",
2495  &heurdata->preferbinaries, TRUE, DEFAULT_PREFERBINARIES, NULL, NULL) );
2496  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/nozerofixing",
2497  "should variables with a zero shifting value be delayed instead of being fixed?",
2498  &heurdata->nozerofixing, TRUE, DEFAULT_NOZEROFIXING, NULL, NULL) );
2499  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/fixbinlocks",
2500  "should binary variables with no locks in one direction be fixed to that direction?",
2501  &heurdata->fixbinlocks, TRUE, DEFAULT_FIXBINLOCKS, NULL, NULL) );
2502  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/binlocksfirst",
2503  "should binary variables with no locks be preferred in the ordering?",
2504  &heurdata->binlocksfirst, TRUE, DEFAULT_BINLOCKSFIRST, NULL, NULL) );
2505  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/normalize",
2506  "should coefficients and left/right hand sides be normalized by max row coeff?",
2507  &heurdata->normalize, TRUE, DEFAULT_NORMALIZE, NULL, NULL) );
2508  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/updateweights",
2509  "should row weight be increased every time the row is violated?",
2510  &heurdata->updateweights, TRUE, DEFAULT_UPDATEWEIGHTS, NULL, NULL) );
2511  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/impliscontinuous",
2512  "should implicit integer variables be treated as continuous variables?",
2513  &heurdata->impliscontinuous, TRUE, DEFAULT_IMPLISCONTINUOUS, NULL, NULL) );
2514  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/shiftandpropagate/selectbest",
2515  "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
2516  &heurdata->selectbest, TRUE, DEFAULT_SELECTBEST, NULL, NULL) );
2517  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcutoffquot",
2518  "maximum percentage of allowed cutoffs before stopping the heuristic",
2519  &heurdata->maxcutoffquot, TRUE, DEFAULT_MAXCUTOFFQUOT, 0.0, 2.0, NULL, NULL) );
2520  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingratelp",
2521  "minimum fixing rate over all variables (including continuous) to solve LP",
2522  &heurdata->minfixingratelp, TRUE, DEFAULT_MINFIXINGRATELP, 0.0, 1.0, NULL, NULL) );
2523 
2524  return SCIP_OKAY;
2525 }
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:1026
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:3298
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:17919
#define SCIP_MAXSTRLEN
Definition: def.h:302
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3356
static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17153
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:17975
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:17343
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17440
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:17219
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17284
#define FALSE
Definition: def.h:96
#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:17064
#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:95
#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:76
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:1371
#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:2180
SCIP_Real SCIPepsilon(SCIP *scip)
#define DEFAULT_ONLYWITHOUTSOL
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1916
#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:17929
#define DEFAULT_NORMALIZE
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1450
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:17143
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:17260
#define DEFAULT_PREFERBINARIES
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
#define NULL
Definition: lpi_spx1.cpp:164
#define REALABS(x)
Definition: def.h:210
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:393
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:819
#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:17294
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:17230
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:1221
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17240
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:93
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:17641
#define DEFAULT_NPROPROUNDS
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2658
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10053
#define MAX(x, y)
Definition: tclique_def.h:92
enum TransformStatus TRANSFORMSTATUS
public methods for LP management
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:985
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8747
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:136
#define DEFAULT_WEIGHT_EQUALITY
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17630
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1444
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:3134
#define SCIP_MAXTREEDEPTH
Definition: def.h:329
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:2000
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
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17250
SCIP_VAR ** b
Definition: circlepacking.c:65
public methods for managing events
general public methods
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:134
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:2313
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:17034
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:1955
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17379
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17493
#define SCIPstatistic(x)
Definition: pub_message.h:120
#define SCIP_Real
Definition: def.h:186
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:703
static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2206
#define SCIP_Longint
Definition: def.h:171
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17425
#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:69
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:17985
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:132
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:1361
#define SCIPABORT()
Definition: def.h:365
public methods for global and local (sub)problems
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:17132
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:17085
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17451
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:8766
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:17107
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:328
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1775