Scippy

SCIP

Solving Constraint Integer Programs

heur_zirounding.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_zirounding.c
17  * @brief zirounding primal heuristic
18  * @author Gregor Hendel
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "blockmemshell/memory.h"
24 #include "scip/heur_zirounding.h"
25 #include "scip/pub_heur.h"
26 #include "scip/pub_lp.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_var.h"
29 #include "scip/scip_branch.h"
30 #include "scip/scip_heur.h"
31 #include "scip/scip_lp.h"
32 #include "scip/scip_mem.h"
33 #include "scip/scip_message.h"
34 #include "scip/scip_numerics.h"
35 #include "scip/scip_param.h"
36 #include "scip/scip_sol.h"
37 #include "scip/scip_solvingstats.h"
38 #include <string.h>
39 
40 #define HEUR_NAME "zirounding"
41 #define HEUR_DESC "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"
42 #define HEUR_DISPCHAR 'z'
43 #define HEUR_PRIORITY -500
44 #define HEUR_FREQ 1
45 #define HEUR_FREQOFS 0
46 #define HEUR_MAXDEPTH -1
47 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
48 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
49 
50 #define DEFAULT_MAXROUNDINGLOOPS 2 /**< delimits the number of main loops, can be set to -1 for no limit */
51 #define DEFAULT_STOPZIROUND TRUE /**< deactivation check is enabled by default */
52 #define DEFAULT_STOPPERCENTAGE 0.02 /**< the tolerance percentage after which zirounding will not be executed anymore */
53 #define DEFAULT_MINSTOPNCALLS 1000 /**< number of heuristic calls before deactivation check */
54 
55 #define MINSHIFT 1e-4 /**< minimum shift value for every single step */
56 
57 /*
58  * Data structures
59  */
60 
61 /** primal heuristic data */
62 struct SCIP_HeurData
63 {
64  SCIP_SOL* sol; /**< working solution */
65  SCIP_Longint lastlp; /**< the number of the last LP for which ZIRounding was called */
66  int maxroundingloops; /**< limits rounding loops in execution */
67  SCIP_Bool stopziround; /**< sets deactivation check */
68  SCIP_Real stoppercentage; /**< threshold for deactivation check */
69  int minstopncalls; /**< number of heuristic calls before deactivation check */
70 };
71 
73 {
76 };
77 typedef enum Direction DIRECTION;
78 
79 /*
80  * Local methods
81  */
82 
83 /** returns the fractionality of a value x, which is calculated as zivalue(x) = min(x-floor(x), ceil(x)-x) */
84 static
86  SCIP* scip, /**< pointer to current SCIP data structure */
87  SCIP_Real val /**< the value for which the fractionality should be computed */
88  )
89 {
90  SCIP_Real upgap; /* the gap between val and ceil(val) */
91  SCIP_Real downgap; /* the gap between val and floor(val) */
92 
93  assert(scip != NULL);
94 
95  upgap = SCIPfeasCeil(scip, val) - val;
96  downgap = val - SCIPfeasFloor(scip, val);
97 
98  return MIN(upgap, downgap);
99 }
100 
101 /** determines shifting bounds for variable */
102 static
104  SCIP* scip, /**< pointer to current SCIP data structure */
105  SCIP_VAR* var, /**< the variable for which lb and ub have to be calculated */
106  SCIP_Real currentvalue, /**< the current value of var in the working solution */
107  SCIP_Real* upperbound, /**< pointer to store the calculated upper bound on the variable shift */
108  SCIP_Real* lowerbound, /**< pointer to store the calculated lower bound on the variable shift */
109  SCIP_Real* upslacks, /**< array that contains the slacks between row activities and the right hand sides of the rows */
110  SCIP_Real* downslacks, /**< array that contains lhs slacks */
111  int nslacks, /**< current number of slacks */
112  SCIP_Bool* numericalerror /**< flag to determine whether a numerical error occurred */
113  )
114 {
115  SCIP_COL* col;
116  SCIP_ROW** colrows;
117  SCIP_Real* colvals;
118  int ncolvals;
119  int i;
120 
121  assert(scip != NULL);
122  assert(var != NULL);
123  assert(upslacks != NULL);
124  assert(downslacks != NULL);
125  assert(upperbound != NULL);
126  assert(lowerbound != NULL);
127 
128  /* get the column associated to the variable, the nonzero rows and the nonzero coefficients */
129  col = SCIPvarGetCol(var);
130  colrows = SCIPcolGetRows(col);
131  colvals = SCIPcolGetVals(col);
132  ncolvals = SCIPcolGetNLPNonz(col);
133 
134  /* only proceed, when variable has nonzero coefficients */
135  if( ncolvals == 0 )
136  return;
137 
138  assert(colvals != NULL);
139  assert(colrows != NULL);
140 
141  /* initialize the bounds on the shift to be the gap of the current solution value to the bounds of the variable */
142  if( SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) )
143  *upperbound = SCIPinfinity(scip);
144  else
145  *upperbound = SCIPvarGetUbGlobal(var) - currentvalue;
146 
147  if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) )
148  *lowerbound = SCIPinfinity(scip);
149  else
150  *lowerbound = currentvalue - SCIPvarGetLbGlobal(var);
151 
152  /* go through every nonzero row coefficient corresponding to var to determine bounds for shifting
153  * in such a way that shifting maintains feasibility in every LP row.
154  * a lower or upper bound as it is calculated in zirounding always has to be >= 0.0.
155  * if one of these values is significantly < 0.0, this will cause the abort of execution of the heuristic so that
156  * infeasible solutions are avoided
157  */
158  for( i = 0; i < ncolvals && MAX(*lowerbound, *upperbound) >= MINSHIFT; ++i )
159  {
160  SCIP_ROW* row;
161  int rowpos;
162 
163  row = colrows[i];
164  rowpos = SCIProwGetLPPos(row);
165 
166  /* the row might currently not be in the LP, ignore it! */
167  if( rowpos == -1 )
168  continue;
169 
170  assert(0 <= rowpos && rowpos < nslacks);
171 
172  /* all bounds and slacks as they are calculated in zirounding always have to be greater equal zero.
173  * It might however be due to numerical issues, e.g. with scaling, that they are not. Better abort in this case.
174  */
175  if( SCIPisFeasLT(scip, *lowerbound, 0.0) || SCIPisFeasLT(scip, *upperbound, 0.0)
176  || SCIPisFeasLT(scip, upslacks[rowpos], 0.0) || SCIPisFeasLT(scip, downslacks[rowpos] , 0.0) )
177  {
178  *numericalerror = TRUE;
179  return;
180  }
181 
182  SCIPdebugMsg(scip, "colval: %15.8g, downslack: %15.8g, upslack: %5.2g, lb: %5.2g, ub: %5.2g\n", colvals[i], downslacks[rowpos], upslacks[rowpos],
183  *lowerbound, *upperbound);
184 
185  /* if coefficient > 0, rounding up might violate up slack and rounding down might violate down slack
186  * thus search for the minimum so that no constraint is violated; vice versa for coefficient < 0
187  */
188  if( colvals[i] > 0 )
189  {
190  if( !SCIPisInfinity(scip, upslacks[rowpos]) )
191  {
192  SCIP_Real upslack;
193  upslack = MAX(upslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
194  *upperbound = MIN(*upperbound, upslack/colvals[i]);
195  }
196 
197  if( !SCIPisInfinity(scip, downslacks[rowpos]) )
198  {
199  SCIP_Real downslack;
200  downslack = MAX(downslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
201  *lowerbound = MIN(*lowerbound, downslack/colvals[i]);
202  }
203  }
204  else
205  {
206  assert(colvals[i] != 0.0);
207 
208  if( !SCIPisInfinity(scip, upslacks[rowpos]) )
209  {
210  SCIP_Real upslack;
211  upslack = MAX(upslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
212  *lowerbound = MIN(*lowerbound, -upslack/colvals[i]);
213  }
214 
215  if( !SCIPisInfinity(scip, downslacks[rowpos]) )
216  {
217  SCIP_Real downslack;
218  downslack = MAX(downslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
219  *upperbound = MIN(*upperbound, -downslack/colvals[i]);
220  }
221  }
222  }
223 }
224 
225 /** when a variable is shifted, the activities and slacks of all rows it appears in have to be updated */
226 static
228  SCIP* scip, /**< pointer to current SCIP data structure */
229  SCIP_SOL* sol, /**< working solution */
230  SCIP_VAR* var, /**< pointer to variable to be modified */
231  SCIP_Real shiftvalue, /**< the value by which the variable is shifted */
232  SCIP_Real* upslacks, /**< upslacks of all rows the variable appears in */
233  SCIP_Real* downslacks, /**< downslacks of all rows the variable appears in */
234  SCIP_Real* activities, /**< activities of the LP rows */
235  SCIP_VAR** slackvars, /**< the slack variables for equality rows */
236  SCIP_Real* slackcoeffs, /**< the slack variable coefficients */
237  int nslacks /**< size of the arrays */
238  )
239 {
240  SCIP_COL* col; /* the corresponding column of variable var */
241  SCIP_ROW** rows; /* pointer to the nonzero coefficient rows for variable var */
242  int nrows; /* the number of nonzeros */
243  SCIP_Real* colvals; /* array to store the nonzero coefficients */
244  int i;
245 
246  assert(scip != NULL);
247  assert(sol != NULL);
248  assert(var != NULL);
249  assert(upslacks != NULL);
250  assert(downslacks != NULL);
251  assert(activities != NULL);
252  assert(nslacks >= 0);
253 
254  col = SCIPvarGetCol(var);
255  assert(col != NULL);
256 
257  rows = SCIPcolGetRows(col);
258  nrows = SCIPcolGetNLPNonz(col);
259  colvals = SCIPcolGetVals(col);
260  assert(nrows == 0 || (rows != NULL && colvals != NULL));
261 
262  /* go through all rows the shifted variable appears in */
263  for( i = 0; i < nrows; ++i )
264  {
265  int rowpos;
266 
267  rowpos = SCIProwGetLPPos(rows[i]);
268  assert(-1 <= rowpos && rowpos < nslacks);
269 
270  /* if the row is in the LP, update its activity, up and down slack */
271  if( rowpos >= 0 )
272  {
273  SCIP_Real val;
274  SCIP_Real lhs;
275  SCIP_Real rhs;
276  SCIP_ROW* row;
277 
278  val = colvals[i] * shiftvalue;
279  row = rows[i];
280  lhs = SCIProwGetLhs(row);
281  rhs = SCIProwGetRhs(row);
282 
283  /* if the row is an equation, we update its slack variable instead of its activities */
284  if( SCIPisFeasEQ(scip, lhs, rhs) )
285  {
286  SCIP_Real slackvarshiftval;
287  SCIP_Real slackvarsolval;
288 
289  assert(slackvars[rowpos] != NULL);
290  assert(!SCIPisZero(scip, slackcoeffs[rowpos]));
291 
292  slackvarsolval = SCIPgetSolVal(scip, sol, slackvars[rowpos]);
293  slackvarshiftval = -val / slackcoeffs[rowpos];
294 
295  assert(SCIPisFeasGE(scip, slackvarsolval + slackvarshiftval, SCIPvarGetLbGlobal(slackvars[rowpos])));
296  assert(SCIPisFeasLE(scip, slackvarsolval + slackvarshiftval, SCIPvarGetUbGlobal(slackvars[rowpos])));
297 
298  SCIP_CALL( SCIPsetSolVal(scip, sol, slackvars[rowpos], slackvarsolval + slackvarshiftval) );
299  }
300  else if( !SCIPisInfinity(scip, REALABS(activities[rowpos])) )
301  activities[rowpos] += val;
302 
303  /* the slacks of the row now can be updated independently of its type */
304  if( !SCIPisInfinity(scip, upslacks[rowpos]) )
305  upslacks[rowpos] -= val;
306  if( !SCIPisInfinity(scip, -downslacks[rowpos]) )
307  downslacks[rowpos] += val;
308 
309  assert(SCIPisInfinity(scip, -lhs) || SCIPisFeasGE(scip, activities[rowpos], lhs));
310  assert(SCIPisInfinity(scip, rhs) || SCIPisFeasLE(scip, activities[rowpos], rhs));
311  }
312  }
313  return SCIP_OKAY;
314 }
315 
316 /** finds a continuous slack variable for an equation row, NULL if none exists */
317 static
319  SCIP* scip, /**< pointer to current SCIP data structure */
320  SCIP_ROW* row, /**< the row for which a slack variable is searched */
321  SCIP_VAR** varpointer, /**< pointer to store the slack variable */
322  SCIP_Real* coeffpointer /**< pointer to store the coefficient of the slack variable */
323  )
324 {
325  int v;
326  SCIP_COL** rowcols;
327  SCIP_Real* rowvals;
328  int nrowvals;
329 
330  assert(row != NULL);
331  assert(varpointer != NULL);
332  assert(coeffpointer != NULL);
333 
334  rowcols = SCIProwGetCols(row);
335  rowvals = SCIProwGetVals(row);
336  nrowvals = SCIProwGetNNonz(row);
337 
338  assert(nrowvals == 0 || rowvals != NULL);
339  assert(nrowvals == 0 || rowcols != NULL);
340 
341  /* iterate over the row variables. Stop after the first unfixed continuous variable was found. */
342  for( v = nrowvals - 1; v >= 0; --v )
343  {
344  SCIP_VAR* colvar;
345 
346  assert(rowcols[v] != NULL);
347  if( SCIPcolGetLPPos(rowcols[v]) == -1 )
348  continue;
349 
350  colvar = SCIPcolGetVar(rowcols[v]);
351 
353  && !SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(colvar), SCIPvarGetUbGlobal(colvar))
354  && SCIPcolGetNLPNonz(rowcols[v]) == 1 )
355  {
356  SCIPdebugMsg(scip, " slack variable for row %s found: %s\n", SCIProwGetName(row), SCIPvarGetName(colvar));
357 
358  *coeffpointer = rowvals[v];
359  *varpointer = colvar;
360 
361  return;
362  }
363  }
364 
365  *varpointer = NULL;
366  *coeffpointer = 0.0;
367 
368  SCIPdebugMsg(scip, "No slack variable for row %s found. \n", SCIProwGetName(row));
369 }
370 
371 /*
372  * Callback methods of primal heuristic
373  */
374 
375 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
376 static
377 SCIP_DECL_HEURCOPY(heurCopyZirounding)
378 { /*lint --e{715}*/
379  assert(scip != NULL);
380  assert(heur != NULL);
381  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
382 
383  /* call inclusion method of primal heuristic */
385 
386  return SCIP_OKAY;
387 }
388 
389 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
390 static
391 SCIP_DECL_HEURFREE(heurFreeZirounding)
392 { /*lint --e{715}*/
393  SCIP_HEURDATA* heurdata;
394 
395  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
396 
397  heurdata = SCIPheurGetData(heur);
398  assert(heurdata != NULL);
399 
400  /* free heuristic data */
401  SCIPfreeBlockMemory(scip, &heurdata);
402  SCIPheurSetData(heur, NULL);
403 
404  return SCIP_OKAY;
405 }
406 
407 /** initialization method of primal heuristic (called after problem was transformed) */
408 static
409 SCIP_DECL_HEURINIT(heurInitZirounding)
410 { /*lint --e{715}*/
411  SCIP_HEURDATA* heurdata;
412 
413  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
414 
415  heurdata = SCIPheurGetData(heur);
416  assert(heurdata != NULL);
417 
418  /* create working solution */
419  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
420 
421  return SCIP_OKAY;
422 }
423 
424 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
425 static
426 SCIP_DECL_HEUREXIT(heurExitZirounding) /*lint --e{715}*/
427 { /*lint --e{715}*/
428  SCIP_HEURDATA* heurdata;
429 
430  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
431 
432  heurdata = SCIPheurGetData(heur);
433  assert(heurdata != NULL);
434 
435  /* free working solution */
436  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
437 
438  return SCIP_OKAY;
439 }
440 
441 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
442 static
443 SCIP_DECL_HEURINITSOL(heurInitsolZirounding)
444 { /*lint --e{715}*/
445  SCIP_HEURDATA* heurdata;
446 
447  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
448 
449  heurdata = SCIPheurGetData(heur);
450  assert(heurdata != NULL);
451 
452  heurdata->lastlp = -1;
453 
454  return SCIP_OKAY;
455 }
456 
457 
458 /** execution method of primal heuristic */
459 static
460 SCIP_DECL_HEUREXEC(heurExecZirounding)
461 { /*lint --e{715}*/
462  SCIP_HEURDATA* heurdata;
463  SCIP_SOL* sol;
464  SCIP_VAR** lpcands;
465  SCIP_VAR** zilpcands;
466 
467  SCIP_VAR** slackvars;
468  SCIP_Real* upslacks;
469  SCIP_Real* downslacks;
470  SCIP_Real* activities;
471  SCIP_Real* slackvarcoeffs;
472  SCIP_Bool* rowneedsslackvar;
473 
474  SCIP_ROW** rows;
475  SCIP_Real* lpcandssol;
476  SCIP_Real* solarray;
477 
478  SCIP_Longint nlps;
479  int currentlpcands;
480  int nlpcands;
481  int nimplfracs;
482  int i;
483  int c;
484  int nslacks;
485  int nroundings;
486 
487  SCIP_Bool improvementfound;
488  SCIP_Bool numericalerror;
489 
490  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
491  assert(result != NULL);
492  assert(SCIPhasCurrentNodeLP(scip));
493 
494  *result = SCIP_DIDNOTRUN;
495 
496  /* do not call heuristic of node was already detected to be infeasible */
497  if( nodeinfeasible )
498  return SCIP_OKAY;
499 
500  /* only call heuristic if an optimal LP-solution is at hand */
502  return SCIP_OKAY;
503 
504  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
506  return SCIP_OKAY;
507 
508  /* get heuristic data */
509  heurdata = SCIPheurGetData(heur);
510  assert(heurdata != NULL);
511 
512  /* Do not call heuristic if deactivation check is enabled and percentage of found solutions in relation
513  * to number of calls falls below heurdata->stoppercentage */
514  if( heurdata->stopziround && SCIPheurGetNCalls(heur) >= heurdata->minstopncalls
515  && SCIPheurGetNSolsFound(heur)/(SCIP_Real)SCIPheurGetNCalls(heur) < heurdata->stoppercentage )
516  return SCIP_OKAY;
517 
518  /* assure that heuristic has not already been called after the last LP had been solved */
519  nlps = SCIPgetNLPs(scip);
520  if( nlps == heurdata->lastlp )
521  return SCIP_OKAY;
522 
523  heurdata->lastlp = nlps;
524 
525  /* get fractional variables */
526  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, &nimplfracs) );
527  nlpcands = nlpcands + nimplfracs;
528  /* make sure that there is at least one fractional variable that should be integral */
529  if( nlpcands == 0 )
530  return SCIP_OKAY;
531 
532  assert(nlpcands > 0);
533  assert(lpcands != NULL);
534  assert(lpcandssol != NULL);
535 
536  /* get LP rows data */
537  rows = SCIPgetLPRows(scip);
538  nslacks = SCIPgetNLPRows(scip);
539 
540  /* cannot do anything if LP is empty */
541  if( nslacks == 0 )
542  return SCIP_OKAY;
543 
544  assert(rows != NULL);
545  assert(nslacks > 0);
546 
547  /* get the working solution from heuristic's local data */
548  sol = heurdata->sol;
549  assert(sol != NULL);
550 
551  *result = SCIP_DIDNOTFIND;
552 
553  solarray = NULL;
554  zilpcands = NULL;
555 
556  /* copy the current LP solution to the working solution and allocate memory for local data */
557  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
558  SCIP_CALL( SCIPallocBufferArray(scip, &solarray, nlpcands) );
559  SCIP_CALL( SCIPallocBufferArray(scip, &zilpcands, nlpcands) );
560 
561  /* copy necessary data to local arrays */
562  BMScopyMemoryArray(solarray, lpcandssol, nlpcands);
563  BMScopyMemoryArray(zilpcands, lpcands, nlpcands);
564 
565  /* allocate buffer data arrays */
566  SCIP_CALL( SCIPallocBufferArray(scip, &slackvars, nslacks) );
567  SCIP_CALL( SCIPallocBufferArray(scip, &upslacks, nslacks) );
568  SCIP_CALL( SCIPallocBufferArray(scip, &downslacks, nslacks) );
569  SCIP_CALL( SCIPallocBufferArray(scip, &slackvarcoeffs, nslacks) );
570  SCIP_CALL( SCIPallocBufferArray(scip, &rowneedsslackvar, nslacks) );
571  SCIP_CALL( SCIPallocBufferArray(scip, &activities, nslacks) );
572 
573  BMSclearMemoryArray(slackvars, nslacks);
574  BMSclearMemoryArray(slackvarcoeffs, nslacks);
575  BMSclearMemoryArray(rowneedsslackvar, nslacks);
576 
577  numericalerror = FALSE;
578  nroundings = 0;
579 
580  /* loop over fractional variables and involved LP rows to find all rows which require a slack variable */
581  for( c = 0; c < nlpcands; ++c )
582  {
583  SCIP_VAR* cand;
584  SCIP_ROW** candrows;
585  int r;
586  int ncandrows;
587 
588  cand = zilpcands[c];
589  assert(cand != NULL);
590  assert(SCIPcolGetLPPos(SCIPvarGetCol(cand)) >= 0);
591 
592  candrows = SCIPcolGetRows(SCIPvarGetCol(cand));
593  ncandrows = SCIPcolGetNLPNonz(SCIPvarGetCol(cand));
594 
595  assert(candrows == NULL || ncandrows > 0);
596 
597  for( r = 0; r < ncandrows; ++r )
598  {
599  int rowpos;
600 
601  assert(candrows != NULL); /* to please flexelint */
602  assert(candrows[r] != NULL);
603  rowpos = SCIProwGetLPPos(candrows[r]);
604 
605  if( rowpos >= 0 && SCIPisFeasEQ(scip, SCIProwGetLhs(candrows[r]), SCIProwGetRhs(candrows[r])) )
606  {
607  rowneedsslackvar[rowpos] = TRUE;
608  SCIPdebugMsg(scip, " Row %s needs slack variable for variable %s\n", SCIProwGetName(candrows[r]), SCIPvarGetName(cand));
609  }
610  }
611  }
612 
613  /* calculate row slacks for every every row that belongs to the current LP and ensure, that the current solution
614  * has no violated constraint -- if any constraint is violated, i.e. a slack is significantly smaller than zero,
615  * this will cause the termination of the heuristic because Zirounding does not provide feasibility recovering
616  */
617  for( i = 0; i < nslacks; ++i )
618  {
619  SCIP_ROW* row;
620  SCIP_Real lhs;
621  SCIP_Real rhs;
622 
623  row = rows[i];
624 
625  assert(row != NULL);
626 
627  lhs = SCIProwGetLhs(row);
628  rhs = SCIProwGetRhs(row);
629 
630  /* get row activity */
631  activities[i] = SCIPgetRowActivity(scip, row);
632  assert(SCIPisFeasLE(scip, lhs, activities[i]) && SCIPisFeasLE(scip, activities[i], rhs));
633 
634  /* in special case if LHS or RHS is (-)infinity slacks have to be initialized as infinity */
635  if( SCIPisInfinity(scip, -lhs) )
636  downslacks[i] = SCIPinfinity(scip);
637  else
638  downslacks[i] = activities[i] - lhs;
639 
640  if( SCIPisInfinity(scip, rhs) )
641  upslacks[i] = SCIPinfinity(scip);
642  else
643  upslacks[i] = rhs - activities[i];
644 
645  SCIPdebugMsg(scip, "lhs:%5.2f <= act:%5.2g <= rhs:%5.2g --> down: %5.2g, up:%5.2g\n", lhs, activities[i], rhs, downslacks[i], upslacks[i]);
646 
647  /* row is an equation. Try to find a slack variable in the row, i.e.,
648  * a continuous variable which occurs only in this row. If no such variable exists,
649  * there is no hope for an IP-feasible solution in this round
650  */
651  if( SCIPisFeasEQ(scip, lhs, rhs) && rowneedsslackvar[i] )
652  {
653  /* @todo: This is only necessary for rows containing fractional variables. */
654  rowFindSlackVar(scip, row, &(slackvars[i]), &(slackvarcoeffs[i]));
655 
656  if( slackvars[i] == NULL )
657  {
658  SCIPdebugMsg(scip, "No slack variable found for equation %s, terminating ZI Round heuristic\n", SCIProwGetName(row));
659  goto TERMINATE;
660  }
661  else
662  {
663  SCIP_Real ubslackvar;
664  SCIP_Real lbslackvar;
665  SCIP_Real solvalslackvar;
666  SCIP_Real coeffslackvar;
667  SCIP_Real ubgap;
668  SCIP_Real lbgap;
669 
670  assert(SCIPvarGetType(slackvars[i]) == SCIP_VARTYPE_CONTINUOUS);
671  solvalslackvar = SCIPgetSolVal(scip, sol, slackvars[i]);
672  ubslackvar = SCIPvarGetUbGlobal(slackvars[i]);
673  lbslackvar = SCIPvarGetLbGlobal(slackvars[i]);
674 
675  coeffslackvar = slackvarcoeffs[i];
676  assert(!SCIPisZero(scip, coeffslackvar));
677 
678  ubgap = MAX(0.0, ubslackvar - solvalslackvar);
679  lbgap = MAX(0.0, solvalslackvar - lbslackvar);
680 
681  if( SCIPisPositive(scip, coeffslackvar) )
682  {
683  if( !SCIPisInfinity(scip, lbslackvar) )
684  upslacks[i] += coeffslackvar * lbgap;
685  else
686  upslacks[i] = SCIPinfinity(scip);
687  if( !SCIPisInfinity(scip, ubslackvar) )
688  downslacks[i] += coeffslackvar * ubgap;
689  else
690  downslacks[i] = SCIPinfinity(scip);
691  }
692  else
693  {
694  if( !SCIPisInfinity(scip, ubslackvar) )
695  upslacks[i] -= coeffslackvar * ubgap;
696  else
697  upslacks[i] = SCIPinfinity(scip);
698  if( !SCIPisInfinity(scip, lbslackvar) )
699  downslacks[i] -= coeffslackvar * lbgap;
700  else
701  downslacks[i] = SCIPinfinity(scip);
702  }
703  SCIPdebugMsg(scip, " Slack variable for row %s at pos %d: %g <= %s = %g <= %g; Coeff %g, upslack = %g, downslack = %g \n",
704  SCIProwGetName(row), SCIProwGetLPPos(row), lbslackvar, SCIPvarGetName(slackvars[i]), solvalslackvar, ubslackvar, coeffslackvar,
705  upslacks[i], downslacks[i]);
706  }
707  }
708  /* due to numerical inaccuracies, the rows might be feasible, even if the slacks are
709  * significantly smaller than zero -> terminate
710  */
711  if( SCIPisFeasLT(scip, upslacks[i], 0.0) || SCIPisFeasLT(scip, downslacks[i], 0.0) )
712  goto TERMINATE;
713  }
714 
715  assert(nslacks == 0 || (upslacks != NULL && downslacks != NULL && activities != NULL));
716 
717  /* initialize number of remaining variables and flag to enter the main loop */
718  currentlpcands = nlpcands;
719  improvementfound = TRUE;
720 
721  /* iterate over variables as long as there are fractional variables left */
722  while( currentlpcands > 0 && improvementfound && (heurdata->maxroundingloops == -1 || nroundings < heurdata->maxroundingloops) )
723  { /*lint --e{850}*/
724  improvementfound = FALSE;
725  nroundings++;
726  SCIPdebugMsg(scip, "zirounding enters while loop for %d time with %d candidates left. \n", nroundings, currentlpcands);
727 
728  /* check for every remaining fractional variable if a shifting decreases ZI-value of the variable */
729  for( c = 0; c < currentlpcands; ++c )
730  {
731  SCIP_VAR* var;
732  SCIP_Real oldsolval;
733  SCIP_Real upperbound;
734  SCIP_Real lowerbound;
735  SCIP_Real up;
736  SCIP_Real down;
737  SCIP_Real ziup;
738  SCIP_Real zidown;
739  SCIP_Real zicurrent;
740  SCIP_Real shiftval;
741 
742  DIRECTION direction;
743 
744  /* get values from local data */
745  oldsolval = solarray[c];
746  var = zilpcands[c];
747 
748  assert(!SCIPisFeasIntegral(scip, oldsolval));
749  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
750 
751  /* calculate bounds for variable and make sure that there are no numerical inconsistencies */
752  upperbound = SCIPinfinity(scip);
753  lowerbound = SCIPinfinity(scip);
754  calculateBounds(scip, var, oldsolval, &upperbound, &lowerbound, upslacks, downslacks, nslacks, &numericalerror);
755 
756  if( numericalerror )
757  goto TERMINATE;
758 
759  /* continue if only marginal shifts are possible */
760  if( MAX(upperbound, lowerbound) < MINSHIFT )
761  {
762  /* stop immediately if a variable has not been rounded during the last round */
763  if( nroundings == heurdata->maxroundingloops )
764  break;
765  else
766  continue;
767  }
768 
769  /* calculate the possible values after shifting */
770  up = oldsolval + upperbound;
771  down = oldsolval - lowerbound;
772 
773  /* if the variable is integer or implicit binary, do not shift further than the nearest integer */
775  {
776  SCIP_Real ceilx;
777  SCIP_Real floorx;
778 
779  ceilx = SCIPfeasCeil(scip, oldsolval);
780  floorx = SCIPfeasFloor(scip, oldsolval);
781  up = MIN(up, ceilx);
782  down = MAX(down, floorx);
783  }
784 
785  /* calculate necessary values */
786  ziup = getZiValue(scip, up);
787  zidown = getZiValue(scip, down);
788  zicurrent = getZiValue(scip, oldsolval);
789 
790  /* calculate the shifting direction that reduces ZI-value the most,
791  * if both directions improve ZI-value equally, take the direction which improves the objective
792  */
793  if( SCIPisFeasLT(scip, zidown, zicurrent) || SCIPisFeasLT(scip, ziup, zicurrent) )
794  {
795  if( SCIPisFeasEQ(scip,ziup, zidown) )
796  direction = SCIPisFeasGE(scip, SCIPvarGetObj(var), 0.0) ? DIRECTION_DOWN : DIRECTION_UP;
797  else if( SCIPisFeasLT(scip, zidown, ziup) )
798  direction = DIRECTION_DOWN;
799  else
800  direction = DIRECTION_UP;
801 
802  /* once a possible shifting direction and value have been found, variable value is updated */
803  shiftval = (direction == DIRECTION_UP ? up - oldsolval : down - oldsolval);
804 
805  /* this improves numerical stability in some cases */
806  if( direction == DIRECTION_UP )
807  shiftval = MIN(shiftval, upperbound);
808  else
809  shiftval = MIN(shiftval, lowerbound);
810  /* update the solution */
811  solarray[c] = direction == DIRECTION_UP ? up : down;
812  SCIP_CALL( SCIPsetSolVal(scip, sol, var, solarray[c]) );
813 
814  /* update the rows activities and slacks */
815  SCIP_CALL( updateSlacks(scip, sol, var, shiftval, upslacks,
816  downslacks, activities, slackvars, slackvarcoeffs, nslacks) );
817 
818  SCIPdebugMsg(scip, "zirounding update step : %d var index, oldsolval=%g, shiftval=%g\n",
819  SCIPvarGetIndex(var), oldsolval, shiftval);
820  /* since at least one improvement has been found, heuristic will enter main loop for another time because the improvement
821  * might affect many LP rows and their current slacks and thus make further rounding steps possible */
822  improvementfound = TRUE;
823  }
824 
825  /* if solution value of variable has become feasibly integral due to rounding step,
826  * variable is put at the end of remaining candidates array so as not to be considered in future loops
827  */
828  if( SCIPisFeasIntegral(scip, solarray[c]) )
829  {
830  zilpcands[c] = zilpcands[currentlpcands - 1];
831  solarray[c] = solarray[currentlpcands - 1];
832  currentlpcands--;
833 
834  /* counter is decreased if end of candidates array has not been reached yet */
835  if( c < currentlpcands )
836  c--;
837  }
838  else if( nroundings == heurdata->maxroundingloops )
839  goto TERMINATE;
840  }
841  }
842 
843  /* in case that no candidate is left for rounding after the final main loop
844  * the found solution has to be checked for feasibility in the original problem
845  */
846  if( currentlpcands == 0 )
847  {
848  SCIP_Bool stored;
849  SCIP_CALL(SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, TRUE, FALSE, &stored));
850  if( stored )
851  {
852 #ifdef SCIP_DEBUG
853  SCIPdebugMsg(scip, "found feasible rounded solution:\n");
854  SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
855 #endif
856  SCIPstatisticMessage(" ZI Round solution value: %g \n", SCIPgetSolOrigObj(scip, sol));
857 
858  *result = SCIP_FOUNDSOL;
859  }
860  }
861 
862  /* free memory for all locally allocated data */
863  TERMINATE:
864  SCIPfreeBufferArrayNull(scip, &activities);
865  SCIPfreeBufferArrayNull(scip, &rowneedsslackvar);
866  SCIPfreeBufferArrayNull(scip, &slackvarcoeffs);
867  SCIPfreeBufferArrayNull(scip, &downslacks);
868  SCIPfreeBufferArrayNull(scip, &upslacks);
869  SCIPfreeBufferArrayNull(scip, &slackvars);
870  SCIPfreeBufferArrayNull(scip, &zilpcands);
871  SCIPfreeBufferArrayNull(scip, &solarray);
872 
873  return SCIP_OKAY;
874 }
875 
876 /*
877  * primal heuristic specific interface methods
878  */
879 
880 /** creates the zirounding primal heuristic and includes it in SCIP */
882  SCIP* scip /**< SCIP data structure */
883  )
884 {
885  SCIP_HEURDATA* heurdata;
886  SCIP_HEUR* heur;
887 
888  /* create zirounding primal heuristic data */
889  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
890 
891  /* include primal heuristic */
892  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
894  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZirounding, heurdata) );
895 
896  assert(heur != NULL);
897 
898  /* set non-NULL pointers to callback methods */
899  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZirounding) );
900  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZirounding) );
901  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZirounding) );
902  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitZirounding) );
903  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolZirounding) );
904 
905  /* add zirounding primal heuristic parameters */
906  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/zirounding/maxroundingloops",
907  "determines maximum number of rounding loops",
908  &heurdata->maxroundingloops, TRUE, DEFAULT_MAXROUNDINGLOOPS, -1, INT_MAX, NULL, NULL) );
909  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/zirounding/stopziround",
910  "flag to determine if Zirounding is deactivated after a certain percentage of unsuccessful calls",
911  &heurdata->stopziround, TRUE, DEFAULT_STOPZIROUND, NULL, NULL) );
912  SCIP_CALL( SCIPaddRealParam(scip,"heuristics/zirounding/stoppercentage",
913  "if percentage of found solutions falls below this parameter, Zirounding will be deactivated",
914  &heurdata->stoppercentage, TRUE, DEFAULT_STOPPERCENTAGE, 0.0, 1.0, NULL, NULL) );
915  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/zirounding/minstopncalls",
916  "determines the minimum number of calls before percentage-based deactivation of Zirounding is applied",
917  &heurdata->minstopncalls, TRUE, DEFAULT_MINSTOPNCALLS, 1, INT_MAX, NULL, NULL) );
918 
919  return SCIP_OKAY;
920 }
static void calculateBounds(SCIP *scip, SCIP_VAR *var, SCIP_Real currentvalue, SCIP_Real *upperbound, SCIP_Real *lowerbound, SCIP_Real *upslacks, SCIP_Real *downslacks, int nslacks, SCIP_Bool *numericalerror)
static SCIP_Real getZiValue(SCIP *scip, SCIP_Real val)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define NULL
Definition: def.h:253
enum Direction DIRECTION
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1390
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
#define HEUR_DESC
public methods for SCIP parameter handling
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:561
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
#define HEUR_FREQ
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16845
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16887
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
#define DEFAULT_MAXROUNDINGLOOPS
#define FALSE
Definition: def.h:73
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16835
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
#define HEUR_NAME
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16903
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1017
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
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:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16857
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17155
#define HEUR_FREQOFS
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:184
#define HEUR_DISPCHAR
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:3124
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:158
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:73
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:540
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
Direction
Definition: heur_twoopt.c:127
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for querying solving statistics
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:107
static SCIP_DECL_HEUREXIT(heurExitZirounding)
#define DEFAULT_STOPZIROUND
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16912
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16922
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:16824
static SCIP_DECL_HEURCOPY(heurCopyZirounding)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define REALABS(x)
Definition: def.h:188
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:237
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPincludeHeurZirounding(SCIP *scip)
#define HEUR_TIMING
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17066
#define DEFAULT_MINSTOPNCALLS
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:200
#define HEUR_USESSUBSCIP
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16966
#define MIN(x, y)
Definition: def.h:223
public methods for LP management
enum Direction DIRECTION
Definition: heur_twoopt.c:133
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:129
ZI Round primal heuristic.
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16736
public methods for the LP relaxation, rows and columns
SCIP_Real * r
Definition: circlepacking.c:50
public methods for branching rule plugins and branching
#define DEFAULT_STOPPERCENTAGE
#define MAX(x, y)
Definition: def.h:222
static SCIP_DECL_HEUREXEC(heurExecZirounding)
static SCIP_DECL_HEURINITSOL(heurInitsolZirounding)
public methods for solutions
static SCIP_RETCODE updateSlacks(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real shiftvalue, SCIP_Real *upslacks, SCIP_Real *downslacks, SCIP_Real *activities, SCIP_VAR **slackvars, SCIP_Real *slackcoeffs, int nslacks)
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:152
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message output
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:73
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766
#define SCIP_Real
Definition: def.h:164
static SCIP_DECL_HEURFREE(heurFreeZirounding)
#define MINSHIFT
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17025
public methods for message handling
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:384
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:216
#define SCIP_Longint
Definition: def.h:149
#define HEUR_PRIORITY
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:168
static void rowFindSlackVar(SCIP *scip, SCIP_ROW *row, SCIP_VAR **varpointer, SCIP_Real *coeffpointer)
static SCIP_DECL_HEURINIT(heurInitZirounding)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16976
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
public methods for primal heuristics
#define HEUR_MAXDEPTH
SCIP_EXPORT int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17035
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16777
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1942
memory allocation routines