Scippy

SCIP

Solving Constraint Integer Programs

sepa_flowcover.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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_flowcover.c
17  * @brief flow cover cuts separator
18  * @author Kati Wolter
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/sepa_flowcover.h"
28 #include "scip/cons_knapsack.h"
29 #include "scip/pub_misc.h"
30 
31 
32 #define SEPA_NAME "flowcover"
33 #define SEPA_DESC "flow cover cuts separator (c-MIR approach)"
34 #define SEPA_PRIORITY -4000
35 #define SEPA_FREQ 0
36 #define SEPA_MAXBOUNDDIST 0.0
37 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
38 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
39 
40 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
41 #define DEFAULT_MAXROUNDSROOT 15 /**< maximal number of separation rounds in the root node (-1: unlimited) */
42 #define DEFAULT_MAXTRIES 100 /**< maximal number of rows to separate flow cover cuts for per separation round
43  * (-1: unlimited) */
44 #define DEFAULT_MAXTRIESROOT -1 /**< maximal number of rows to separate flow cover cuts for per separation round
45  * in the root (-1: unlimited) */
46 #define DEFAULT_MAXFAILS 50 /**< maximal number of consecutive fails to generate a cut per separation round
47  * (-1: unlimited) */
48 #define DEFAULT_MAXFAILSROOT 100 /**< maximal number of consecutive fails to generate a cut per separation round
49  * in the root (-1: unlimited) */
50 #define DEFAULT_MAXSEPACUTS 100 /**< maximal number of flow cover cuts separated per separation round */
51 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of flow cover cuts separated per separation round in the root */
52 #define DEFAULT_MAXSLACK SCIP_REAL_MAX /**< maximal slack of rows to separate flow cover cuts for */
53 #define DEFAULT_MAXSLACKROOT SCIP_REAL_MAX /**< maximal slack of rows to separate flow cover cuts for in the root */
54 #define DEFAULT_SLACKSCORE 1e-03 /**< weight of slack in the scoring of the rows */
55 #define DEFAULT_MAXROWDENSITY 1.0 /**< maximal density of rows to separate flow cover cuts for */
56 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
57 #define DEFAULT_MAXTESTDELTA 10 /**< cut generation heuristic: maximal number of different deltas to try */
58 #define DEFAULT_MULTBYMINUSONE TRUE /**< should flow cover cuts be separated for 0-1 single node flow set with reversed arcs in addition? */
59 
60 #define BOUNDSWITCH 0.5
61 #define ALLOWLOCAL TRUE
62 #define DENSSCORE 1e-04
63 /*#define MAKECONTINTEGRAL FALSE*/
64 #define MINFRAC 0.01
65 #define MAXFRAC 0.95
66 #define FIXINTEGRALRHS FALSE
67 #define MAXDNOM 1000LL
68 #define MINDELTA 1e-03
69 #define MAXDELTA 1e-09
70 #define MAXSCALE 1000.0
71 #define MAXDYNPROGSPACE 1000000
72 
73 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) /**< maximal length of base inequality */
74 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for snf relaxation */
75 #define MAXBOUND 1e+10 /**< maximal value of normal bounds used for snf relaxation */
76 
77 
78 /*
79  * Data structures
80  */
81 
82 /** separator data */
83 struct SCIP_SepaData
84 {
85  int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
86  int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
87  int maxtries; /**< maximal number of rows to separate flow cover cuts for per separation round
88  * (-1: unlimited) */
89  int maxtriesroot; /**< maximal number of rows to separate flow cover cuts for per separation round
90  * in the root (-1: unlimited) */
91  int maxfails; /**< maximal number of consecutive fails to generate a cut per separation round
92  * (-1: unlimited) */
93  int maxfailsroot; /**< maximal number of consecutive fails to generate a cut per separation round
94  * in the root (-1: unlimited) */
95  int maxsepacuts; /**< maximal number of flow cover cuts separated per separation round */
96  int maxsepacutsroot; /**< maximal number of flow cover cuts separated per separation round in the root */
97  SCIP_Real maxslack; /**< maximal slack of rows to separate flow cover cuts for */
98  SCIP_Real maxslackroot; /**< maximal slack of rows to separate flow cover cuts for in the root */
99  SCIP_Real slackscore; /**< weight of slack in the scoring of the rows */
100  SCIP_Real maxrowdensity; /**< maximal density of rows to separate flow cover cuts for */
101  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
102  SCIP_Bool multbyminusone; /**< should flow cover cuts be separated for 0-1 single node flow set with reversed arcs in addition? */
103  int maxtestdelta; /**< cut generation heuristic: maximal number of different deltas to try */
104 };
105 
106 
107 /*
108  * Local methods
109  */
110 
111 /** get LP solution value and index of variable lower bound (with binary variable) which is closest to the current LP
112  * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
113  * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
114  * given variable
115  */
116 static
117 SCIP_RETCODE getClosestVlb(
118  SCIP* scip, /**< SCIP data structure */
119  SCIP_VAR* var, /**< given active problem variable */
120  SCIP_Real bestsub, /**< closest simple upper bound of given variable */
121  SCIP_Real rowcoef, /**< coefficient of given variable in current row */
122  SCIP_Real* rowcoefsbinary, /**< coefficient of all binary problem variables in current row */
123  SCIP_Real* varsolvals, /**< LP solution value of all active problem variables */
124  int* assoctransvars, /**< associated var in relaxed set for all vars of row; construction is not finished yet */
125  SCIP_Real* closestvlb, /**< pointer to store the LP sol value of the closest variable lower bound */
126  int* closestvlbidx /**< pointer to store the index of the closest vlb; -1 if no vlb was found */
127  )
128 {
129  int nvlbs;
130 
131  assert(scip != NULL);
132  assert(var != NULL);
133  assert(bestsub == SCIPvarGetUbGlobal(var) || bestsub == SCIPvarGetUbLocal(var)); /*lint !e777*/
134  assert(!SCIPisInfinity(scip, bestsub));
135  assert(!SCIPisZero(scip, rowcoef));
136  assert(rowcoefsbinary != NULL);
137  assert(varsolvals != NULL);
138  assert(assoctransvars != NULL);
139  assert(closestvlb != NULL);
140  assert(closestvlbidx != NULL);
141 
142  nvlbs = SCIPvarGetNVlbs(var);
143 
144  *closestvlbidx = -1;
145  *closestvlb = -SCIPinfinity(scip);
146  if( nvlbs > 0 )
147  {
148  SCIP_VAR** vlbvars;
149  SCIP_Real* vlbcoefs;
150  SCIP_Real* vlbconsts;
151  int i;
152 
153  vlbvars = SCIPvarGetVlbVars(var);
154  vlbcoefs = SCIPvarGetVlbCoefs(var);
155  vlbconsts = SCIPvarGetVlbConstants(var);
156 
157  for( i = 0; i < nvlbs; i++ )
158  {
159  SCIP_Real rowcoefbinvar;
160  SCIP_Real val1;
161  SCIP_Real val2;
162  SCIP_Real vlbsol;
163  SCIP_Bool meetscriteria;
164  int probidxbinvar;
165 
166  /* use only variable lower bounds l~_i * x_i + d_i with x_i binary which are active */
167  if( !SCIPvarIsBinary(vlbvars[i]) || !SCIPvarIsActive(vlbvars[i]) )
168  continue;
169 
170  /* check if current variable lower bound l~_i * x_i + d_i imposed on y_j meets the following criteria:
171  * (let a_j = coefficient of y_j in current row,
172  * u_j = closest simple upper bound imposed on y_j,
173  * c_i = coefficient of x_i in current row)
174  * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k yet
175  * if a_j > 0:
176  * 1. u_j <= d_i
177  * 2. a_j ( u_j - d_i ) + c_i <= 0
178  * 3. a_j l~_i + c_i <= 0
179  * if a_j < 0:
180  * 1. u_j <= d_i
181  * 2. a_j ( u_j - d_i ) + c_i >= 0
182  * 3. a_j l~_i + c_i >= 0
183  */
184  probidxbinvar = SCIPvarGetProbindex(vlbvars[i]);
185  rowcoefbinvar = rowcoefsbinary[probidxbinvar];
186 
187  val1 = ( rowcoef * ( bestsub - vlbconsts[i] ) ) + rowcoefbinvar;
188  val2 = ( rowcoef * vlbcoefs[i] ) + rowcoefbinvar;
189 
190  meetscriteria = FALSE;
191  if( SCIPisPositive(scip, rowcoef) )
192  {
193  if( assoctransvars[probidxbinvar] == -1 && SCIPisFeasLE(scip, bestsub, vlbconsts[i])
194  && SCIPisFeasLE(scip, val1, 0.0) && SCIPisFeasLE(scip, val2, 0.0) )
195  meetscriteria = TRUE;
196  }
197  else
198  {
199  assert(SCIPisNegative(scip, rowcoef));
200  if( assoctransvars[probidxbinvar] == -1 && SCIPisFeasLE(scip, bestsub, vlbconsts[i])
201  && SCIPisFeasGE(scip, val1, 0.0) && SCIPisFeasGE(scip, val2, 0.0) )
202  meetscriteria = TRUE;
203  }
204 
205  /* variable lower bound does not meet criteria */
206  if( !meetscriteria )
207  continue;
208 
209  /* for numerical reasons, ignore variable bounds with large absolute coefficient and
210  * those which lead to an infinite variable bound coefficient (val2) in snf relaxation
211  */
212  if( REALABS(vlbcoefs[i]) > MAXABSVBCOEF || SCIPisInfinity(scip, REALABS(val2)) )
213  continue;
214 
215  vlbsol = (vlbcoefs[i] * varsolvals[probidxbinvar]) + vlbconsts[i];
216  if( SCIPisGT(scip, vlbsol, *closestvlb) )
217  {
218  *closestvlb = vlbsol;
219  *closestvlbidx = i;
220  }
221  assert(*closestvlbidx >= 0);
222 
223  }
224  }
225 
226  return SCIP_OKAY;
227 }
228 
229 /** get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP
230  * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
231  * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
232  * given variable
233  */
234 static
235 SCIP_RETCODE getClosestVub(
236  SCIP* scip, /**< SCIP data structure */
237  SCIP_VAR* var, /**< given active problem variable */
238  SCIP_Real bestslb, /**< closest simple lower bound of given variable */
239  SCIP_Real rowcoef, /**< coefficient of given variable in current row */
240  SCIP_Real* rowcoefsbinary, /**< coefficient of all binary problem variables in current row */
241  SCIP_Real* varsolvals, /**< LP solution value of all active problem variables */
242  int* assoctransvars, /**< associated var in relaxed set for all vars of row; construction is not finished yet */
243  SCIP_Real* closestvub, /**< pointer to store the LP sol value of the closest variable upper bound */
244  int* closestvubidx /**< pointer to store the index of the closest vub; -1 if no vub was found */
245  )
246 {
247  int nvubs;
248 
249  assert(scip != NULL);
250  assert(var != NULL);
251  assert(bestslb == SCIPvarGetLbGlobal(var) || bestslb == SCIPvarGetLbLocal(var)); /*lint !e777*/
252  assert(!SCIPisInfinity(scip, - bestslb));
253  assert(!SCIPisZero(scip, rowcoef));
254  assert(rowcoefsbinary != NULL);
255  assert(varsolvals != NULL);
256  assert(assoctransvars != NULL);
257  assert(closestvub != NULL);
258  assert(closestvubidx != NULL);
259 
260  nvubs = SCIPvarGetNVubs(var);
261 
262  *closestvubidx = -1;
263  *closestvub = SCIPinfinity(scip);
264  if( nvubs > 0 )
265  {
266  SCIP_VAR** vubvars;
267  SCIP_Real* vubcoefs;
268  SCIP_Real* vubconsts;
269  int i;
270 
271  vubvars = SCIPvarGetVubVars(var);
272  vubcoefs = SCIPvarGetVubCoefs(var);
273  vubconsts = SCIPvarGetVubConstants(var);
274 
275  for( i = 0; i < nvubs; i++ )
276  {
277  SCIP_Real rowcoefbinvar;
278  SCIP_Real val1;
279  SCIP_Real val2;
280  SCIP_Real vubsol;
281  SCIP_Bool meetscriteria;
282  int probidxbinvar;
283 
284  /* use only variable upper bound u~_i * x_i + d_i with x_i binary and which are active */
285  if( !SCIPvarIsBinary(vubvars[i]) || !SCIPvarIsActive(vubvars[i]))
286  continue;
287 
288  /* checks if current variable upper bound u~_i * x_i + d_i meets the following criteria
289  * (let a_j = coefficient of y_j in current row,
290  * l_j = closest simple lower bound imposed on y_j,
291  * c_i = coefficient of x_i in current row)
292  * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k
293  * if a > 0:
294  * 1. l_j >= d_i
295  * 2. a_j ( l_i - d_i ) + c_i >= 0
296  * 3. a_j u~_i + c_i >= 0
297  * if a < 0:
298  * 1. l_j >= d_i
299  * 2. a_j ( l_j - d_i ) + c_i <= 0
300  * 3. a_j u~_i + c_i <= 0
301  */
302  probidxbinvar = SCIPvarGetProbindex(vubvars[i]);
303  rowcoefbinvar = rowcoefsbinary[probidxbinvar];
304 
305  val1 = ( rowcoef * ( bestslb - vubconsts[i] ) ) + rowcoefbinvar;
306  val2 = ( rowcoef * vubcoefs[i] ) + rowcoefbinvar;
307 
308  meetscriteria = FALSE;
309  if( SCIPisPositive(scip, rowcoef) )
310  {
311  if( assoctransvars[probidxbinvar] == -1 && SCIPisFeasGE(scip, bestslb, vubconsts[i])
312  && SCIPisFeasGE(scip, val1, 0.0) && SCIPisFeasGE(scip, val2, 0.0) )
313  meetscriteria = TRUE;
314  }
315  else
316  {
317  assert(SCIPisNegative(scip, rowcoef));
318  if( assoctransvars[probidxbinvar] == -1 && SCIPisFeasGE(scip, bestslb, vubconsts[i])
319  && SCIPisFeasLE(scip, val1, 0.0) && SCIPisFeasLE(scip, val2, 0.0) )
320  meetscriteria = TRUE;
321  }
322 
323  /* variable upper bound does not meet criteria */
324  if( !meetscriteria )
325  continue;
326 
327  /* for numerical reasons, ignore variable bounds with large absolute coefficient and
328  * those which lead to an infinite variable bound coefficient (val2) in snf relaxation
329  */
330  if( REALABS(vubcoefs[i]) > MAXABSVBCOEF || SCIPisInfinity(scip, REALABS(val2)) )
331  continue;
332 
333  vubsol = vubcoefs[i] * varsolvals[probidxbinvar] + vubconsts[i];
334  if( SCIPisLT(scip, vubsol, *closestvub) )
335  {
336  *closestvub = vubsol;
337  *closestvubidx = i;
338  }
339  assert(*closestvubidx >= 0);
340  }
341  }
342 
343  return SCIP_OKAY;
344 }
345 
346 /** return global or local lower bound of given variable whichever is closer to the variables current LP solution value */
347 static
348 void getClosestLb(
349  SCIP* scip, /**< SCIP data structure */
350  SCIP_VAR* var, /**< active problem variable */
351  SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
352  SCIP_Real* closestlb, /**< pointer to store the value of the closest variable lower bound */
353  int* closestlbtype /**< pointer to store type of closest bound; -1 if global lb, -2 otherwise */
354  )
355 {
356  assert(closestlb != NULL);
357  assert(closestlbtype != NULL);
358 
359  *closestlb = SCIPvarGetLbGlobal(var);
360  *closestlbtype = -1;
361  if( allowlocal )
362  {
363  SCIP_Real loclb;
364  loclb = SCIPvarGetLbLocal(var);
365  if( SCIPisGT(scip, loclb, *closestlb) )
366  {
367  *closestlb = loclb;
368  *closestlbtype = -2;
369  }
370  }
371 
372  /* due to numerical reasons, huge bounds are relaxed to infinite bounds; this way the bounds are not used for
373  * the construction of the 0-1 single node flow relaxation
374  */
375  if( *closestlb <= -MAXBOUND )
376  *closestlb = -SCIPinfinity(scip);
377 }
378 
379 /** return global or local upper bound of given variable whichever is closer to the variables current LP solution value */
380 static
381 void getClosestUb(
382  SCIP* scip, /**< SCIP data structure */
383  SCIP_VAR* var, /**< active problem variable */
384  SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
385  SCIP_Real* closestub, /**< pointer to store the value of the closest upper bound */
386  int* closestubtype /**< pointer to store type of closest bound; -1 if global ub, -2 otherwise */
387  )
388 {
389  assert(closestub != NULL);
390  assert(closestubtype != NULL);
391 
392  *closestub = SCIPvarGetUbGlobal(var);
393  *closestubtype = -1;
394  if( allowlocal )
395  {
396  SCIP_Real locub;
397  locub = SCIPvarGetUbLocal(var);
398  if( SCIPisLT(scip, locub, *closestub) )
399  {
400  *closestub = locub;
401  *closestubtype = -2;
402  }
403  }
404 
405  /* due to numerical reasons, huge bounds are relaxed to infinite bounds; this way the bounds are not used for
406  * the construction of the 0-1 single node flow relaxation
407  */
408  if( *closestub >= MAXBOUND )
409  *closestub = SCIPinfinity(scip);
410 }
411 
412 /** construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set
413  * corresponding to the given row lhs <= a * x + const <= rhs; depending on the given values rowweight and scale
414  * the mixed integer set which should be used is defined by the mixed integer constraint
415  * a * (x,y) <= rhs - const if (rowweight = 1, scale = 1) or (rowweight = -1, scale = -1, rhs < infinity)
416  * - a * (x,y) <= - (lhs - const) if (rowweight = -1, scale = 1) or (rowweight = 1, scale = -1, lhs > -infinity)
417  * - a * (x,y) - s <= - (rhs - const) if (rowweight = 1, scale = -1, lhs = -infinity)
418  * a * (x,y) - s <= (lhs - const) if (rowweight = -1, scale = -1, rhs = infinity)
419  */
420 static
421 SCIP_RETCODE constructSNFRelaxation(
422  SCIP* scip, /**< SCIP data structure */
423  SCIP_VAR** vars, /**< active problem variables */
424  int nvars, /**< number of active problem variables */
425  SCIP_Real* varsolvals, /**< solution values of active problem variables */
426  SCIP_ROW* row, /**< given row */
427  SCIP_Real rowweight, /**< weight of given row; can be +1 or -1 */
428  SCIP_Real scale, /**< additional scaling factor for given row */
429  int* boundsfortrans, /**< pointer to store bound used for all non-binary vars of row */
430  SCIP_BOUNDTYPE* boundtypesfortrans, /**< pointer to store type of bound used for all non-binary vars of row */
431  int* assoctransvars, /**< pointer to store associated var in relaxed set for all vars of row */
432  int* transvarcoefs, /**< pointer to store coefficient of all vars in relaxed set */
433  SCIP_Real* transbinvarsolvals, /**< pointer to store sol val of bin var in vub of all vars in relaxed set */
434  SCIP_Real* transcontvarsolvals,/**< pointer to store sol val of all real vars in relaxed set */
435  SCIP_Real* transvarvubcoefs, /**< pointer to store coefficient in vub of all vars in relaxed set */
436  int* ntransvars, /**< pointer to store number of vars in relaxed set */
437  SCIP_Real* transrhs, /**< pointer to store rhs in relaxed set */
438  SCIP_Bool* success /**< pointer to store whether a relaxation was constructed */
439  )
440 {
441  SCIP_COL** nonzcols;
442  SCIP_Real* nonzcoefs;
443  SCIP_Real* rowcoefsbinary;
444  int* nonzcolsbinary;
445  int* nonzcolsnonbinary;
446  int nnonzcols;
447  int nnonzcolsbinary;
448  int nnonzcolsnonbinary;
449  int c;
450 
451  assert(scip != NULL);
452  assert(vars!= NULL);
453  assert(nvars > 0);
454  assert(varsolvals != NULL);
455  assert(row != NULL);
456  assert(rowweight == 1.0 || rowweight == -1.0);
457  assert(( rowweight == 1.0 && !SCIPisInfinity(scip, SCIProwGetRhs(row)) )
458  || ( rowweight == -1.0 && !SCIPisInfinity(scip, -SCIProwGetLhs(row)) ));
459  assert(scale == 1.0 || scale == -1.0);
460  assert(boundsfortrans != NULL);
461  assert(boundtypesfortrans != NULL);
462  assert(assoctransvars != NULL);
463  assert(transvarcoefs != NULL);
464  assert(transbinvarsolvals != NULL);
465  assert(transcontvarsolvals != NULL);
466  assert(transvarvubcoefs != NULL);
467  assert(ntransvars != NULL);
468  assert(transrhs != NULL);
469  assert(success != NULL);
470 
471  *success = FALSE;
472 
473  SCIPdebugMsg(scip, "--------------------- construction of SNF relaxation ------------------------------------\n");
474 
475  /* get nonzero columns and coefficients of row */
476  nonzcols = SCIProwGetCols(row);
477  nnonzcols = SCIProwGetNLPNonz(row);
478  nonzcoefs = SCIProwGetVals(row);
479  SCIPdebugMsg(scip, "nnonzcols = %d\n",nnonzcols);
480 
481  /* get data structures */
482  SCIP_CALL( SCIPallocBufferArray(scip, &nonzcolsbinary, nnonzcols) );
483  SCIP_CALL( SCIPallocBufferArray(scip, &nonzcolsnonbinary, nnonzcols) );
484  SCIP_CALL( SCIPallocBufferArray(scip, &rowcoefsbinary, nvars) );
485 
486  /* store nonzero columns representing binary and non-binary variables, and get active binary problem variables the
487  * coefficient in the row
488  */
489  nnonzcolsbinary = 0;
490  nnonzcolsnonbinary = 0;
491  BMSclearMemoryArray(rowcoefsbinary, nvars);
492  for( c = 0; c < nnonzcols; c++ )
493  {
494  SCIP_COL* col;
495  SCIP_VAR* var;
496 
497  col = nonzcols[c];
498  var = SCIPcolGetVar(col);
499 
500  assert(!SCIPisZero(scip, nonzcoefs[c]));
501 
502  if( SCIPvarIsBinary(var) )
503  {
504  /* saves column for binary variable */
505  nonzcolsbinary[nnonzcolsbinary] = c;
506  nnonzcolsbinary++;
507 
508  /* saves row coefficient of binary variable */
509  assert(SCIPvarGetProbindex(var) > -1 && SCIPvarGetProbindex(var) < nvars);
510  rowcoefsbinary[SCIPvarGetProbindex(var)] = rowweight * scale * nonzcoefs[c];
511  }
512  else
513  {
514  /* saves column for non-binary variable */
515  nonzcolsnonbinary[nnonzcolsnonbinary] = c;
516  nnonzcolsnonbinary++;
517  }
518  }
519  assert(nnonzcolsbinary + nnonzcolsnonbinary == nnonzcols);
520 
521  /* initialize data structures */
522  for( c = 0; c < nvars; c++ )
523  {
524  assoctransvars[c] = -1;
525  boundsfortrans[c] = -3;
526  }
527  *ntransvars = 0;
528 
529  /* initialize right hand side of constraint in 0-1 single node flow relaxation */
530  if( rowweight * scale == 1.0 && !SCIPisInfinity(scip, SCIProwGetRhs(row)) )
531  *transrhs = SCIProwGetRhs(row) - SCIProwGetConstant(row);
532  else if( rowweight * scale == 1.0 && SCIPisInfinity(scip, SCIProwGetRhs(row)) )
533  {
534  assert(rowweight == -1.0 && scale == -1.0);
535  *transrhs = SCIProwGetLhs(row) - SCIProwGetConstant(row);
536  }
537  else if( rowweight * scale == -1.0 && !SCIPisInfinity(scip, -SCIProwGetLhs(row)) )
538  *transrhs = - SCIProwGetLhs(row) + SCIProwGetConstant(row);
539  else
540  {
541  assert(rowweight == 1.0 && scale == -1.0 && SCIPisInfinity(scip, -SCIProwGetLhs(row)));
542  *transrhs = - SCIProwGetRhs(row) + SCIProwGetConstant(row);
543  }
544 
545  /* for each non-binary variable y_j in the row with nonzero row coefficient perform
546  * 1. get closest simple or variable lower bound and closest simple or variable upper bound
547  * 2. decide which bound is used to define the real variable y'_j in the 0-1 single node flow relaxation
548  * 3. construct y'_j with 0 <= y'_j <= u'_j x_j
549  * 4. store for y_j and x_j (if x_j is a binary variable in the row) that y'_j is the associated real variable
550  * in the 0-1 single node flow relaxation and for y_j the bound used to define y'_j.
551  *
552  * for each binary variable x_j in the row which has not been handled with a non-binary variable perform
553  * 1. construct y'_j with 0 <= y'_j <= u'_j x_j
554  * 2. store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation.
555  *
556  * start with non-binary variables because a binary variable x_j which is involved in a used variable bound
557  * imposed on a non-binary variable y_j has to be handled together with the non-binary variable y_j.
558  */
559  SCIPdebugMsg(scip, "transformation for NONBINARY variables (nnonbinvars=%d):\n", nnonzcolsnonbinary);
560 
561  /* non-binary variables and binary variables contained in used variable bounds */
562  for( c = 0; c < nnonzcolsnonbinary; c++ )
563  {
564  SCIP_VAR* var;
565  SCIP_Real bestlb;
566  SCIP_Real bestub;
567  SCIP_Real bestslb;
568  SCIP_Real bestsub;
569  SCIP_Real rowcoef;
570  SCIP_Bool uselb;
571  int bestlbtype;
572  int bestubtype;
573  int bestslbtype;
574  int bestsubtype;
575  int probidx;
576 
577  bestlb = -SCIPinfinity(scip);
578  bestub = SCIPinfinity(scip);
579  bestlbtype = -3;
580  bestubtype = -3;
581 
582  var = SCIPcolGetVar(nonzcols[nonzcolsnonbinary[c]]);
583  probidx = SCIPvarGetProbindex(var);
584  rowcoef = rowweight * scale * nonzcoefs[nonzcolsnonbinary[c]];
585 
586  assert(assoctransvars[probidx] == -1);
587  assert(boundsfortrans[probidx] == -3);
588  assert(!SCIPisZero(scip, rowcoef));
589 
590  /* get closest simple lower bound and closest simple upper bound */
591  getClosestLb(scip, var, ALLOWLOCAL, &bestslb, &bestslbtype);
592  getClosestUb(scip, var, ALLOWLOCAL, &bestsub, &bestsubtype);
593 
594  SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", c, rowcoef, SCIPvarGetName(var), probidx,
595  varsolvals[probidx], bestslb, bestslbtype, bestsub, bestsubtype);
596 
597  /* mixed integer set cannot be relaxed to 0-1 single node flow set because both simple bounds are -infinity
598  * and infinity, respectively
599  */
600  if( SCIPisInfinity(scip, -bestslb) && SCIPisInfinity(scip, bestsub) )
601  {
602  assert(!(*success));
603  goto TERMINATE;
604  }
605 
606  /* get closest lower bound that can be used to define the real variable y'_j in the 0-1 single node flow
607  * relaxation
608  */
609  if( !SCIPisInfinity(scip, bestsub) )
610  {
611  bestlb = bestslb;
612  bestlbtype = bestslbtype;
613 
614  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
615  {
616  SCIP_Real bestvlb;
617  int bestvlbidx;
618 
619  SCIP_CALL( getClosestVlb(scip, var, bestsub, rowcoef, rowcoefsbinary, varsolvals, assoctransvars, &bestvlb, &bestvlbidx) );
620  if( SCIPisGT(scip, bestvlb, bestlb) )
621  {
622  bestlb = bestvlb;
623  bestlbtype = bestvlbidx;
624  }
625  }
626  }
627  /* get closest upper bound that can be used to define the real variable y'_j in the 0-1 single node flow
628  * relaxation
629  */
630  if( !SCIPisInfinity(scip, -bestslb) )
631  {
632  bestub = bestsub;
633  bestubtype = bestsubtype;
634 
635  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
636  {
637  SCIP_Real bestvub;
638  int bestvubidx;
639 
640  SCIP_CALL( getClosestVub(scip, var, bestslb, rowcoef, rowcoefsbinary, varsolvals, assoctransvars, &bestvub, &bestvubidx) );
641  if( SCIPisLT(scip, bestvub, bestub) )
642  {
643  bestub = bestvub;
644  bestubtype = bestvubidx;
645  }
646  }
647  }
648  SCIPdebugMsg(scip, " bestlb=%g(%d), bestub=%g(%d)\n", bestlb, bestlbtype, bestub, bestubtype);
649 
650  /* mixed integer set cannot be relaxed to 0-1 single node flow set because there are no suitable bounds
651  * to define the transformed variable y'_j
652  */
653  if( SCIPisInfinity(scip, -bestlb) && SCIPisInfinity(scip, bestub) )
654  {
655  assert(!(*success));
656  goto TERMINATE;
657  }
658 
659  /* select best upper bound if it is closer to the LP value of y_j and best lower bound otherwise and use this bound
660  * to define the real variable y'_j with 0 <= y'_j <= u'_j x_j in the 0-1 single node flow relaxation;
661  * prefer variable bounds
662  */
663  if( SCIPisEQ(scip, varsolvals[probidx], (1.0 - BOUNDSWITCH) * bestlb + BOUNDSWITCH * bestub) && bestlbtype >= 0 )
664  uselb = TRUE;
665  else if( SCIPisEQ(scip, varsolvals[probidx], (1.0 - BOUNDSWITCH) * bestlb + BOUNDSWITCH * bestub)
666  && bestubtype >= 0 )
667  uselb = FALSE;
668  else if( SCIPisLE(scip, varsolvals[probidx], (1.0 - BOUNDSWITCH) * bestlb + BOUNDSWITCH * bestub) )
669  uselb = TRUE;
670  else
671  {
672  assert(SCIPisGT(scip, varsolvals[probidx], (1.0 - BOUNDSWITCH) * bestlb + BOUNDSWITCH * bestub));
673  uselb = FALSE;
674  }
675  if( uselb )
676  {
677  /* use bestlb to define y'_j */
678 
679  assert(!SCIPisInfinity(scip, bestsub));
680  assert(!SCIPisInfinity(scip, - bestlb));
681  assert(bestsubtype == -1 || bestsubtype == -2);
682  assert(bestlbtype > -3 && bestlbtype < SCIPvarGetNVlbs(var));
683 
684  /* store for y_j that bestlb is the bound used to define y'_j and that y'_j is the associated real variable
685  * in the relaxed set
686  */
687  boundsfortrans[probidx] = bestlbtype;
688  boundtypesfortrans[probidx] = SCIP_BOUNDTYPE_LOWER;
689  assoctransvars[probidx] = *ntransvars;
690 
691  if( bestlbtype < 0 )
692  {
693  SCIP_Real val;
694  SCIP_Real contsolval;
695 
696  /* use simple lower bound in bestlb = l_j <= y_j <= u_j = bestsub to define
697  * y'_j = - a_j ( y_j - u_j ) with 0 <= y'_j <= a_j ( u_j - l_j ) x_j and x_j = 1 if a_j > 0
698  * y'_j = a_j ( y_j - u_j ) with 0 <= y'_j <= - a_j ( u_j - l_j ) x_j and x_j = 1 if a_j < 0,
699  * put j into the set
700  * N2 if a_j > 0
701  * N1 if a_j < 0
702  * and update the right hand side of the constraint in the relaxation
703  * rhs = rhs - a_j u_j
704  */
705  val = rowcoef * ( bestsub - bestlb );
706  contsolval = rowcoef * ( varsolvals[probidx] - bestsub );
707  if( SCIPisPositive(scip, rowcoef) )
708  {
709  transvarcoefs[*ntransvars] = - 1;
710  transvarvubcoefs[*ntransvars] = val;
711  transbinvarsolvals[*ntransvars] = 1.0;
712  transcontvarsolvals[*ntransvars] = - contsolval;
713  }
714  else
715  {
716  assert(SCIPisNegative(scip, rowcoef));
717  transvarcoefs[*ntransvars] = 1;
718  transvarvubcoefs[*ntransvars] = - val;
719  transbinvarsolvals[*ntransvars] = 1.0;
720  transcontvarsolvals[*ntransvars] = contsolval;
721  }
722  (*transrhs) -= (rowcoef * bestsub);
723 
724  SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
725  transvarcoefs[*ntransvars] == 1 ? "+" : "-", *ntransvars, *ntransvars, transvarvubcoefs[*ntransvars],
726  *ntransvars, *transrhs + (rowcoef * bestsub), rowcoef, bestsub, *transrhs);
727  }
728  else
729  {
730  SCIP_Real rowcoefbinary;
731  SCIP_Real varsolvalbinary;
732  SCIP_Real val;
733  SCIP_Real contsolval;
734  SCIP_VAR** vlbvars = SCIPvarGetVlbVars(var);
735  SCIP_Real* vlbconsts = SCIPvarGetVlbConstants(var);
736  SCIP_Real* vlbcoefs = SCIPvarGetVlbCoefs(var);
737 
738  /* use variable lower bound in bestlb = l~_j x_j + d_j <= y_j <= u_j = bestsub to define
739  * y'_j = - ( a_j ( y_j - d_j ) + c_j x_j ) with 0 <= y'_j <= - ( a_j l~_j + c_j ) x_j if a_j > 0
740  * y'_j = a_j ( y_j - d_j ) + c_j x_j with 0 <= y'_j <= ( a_j l~_j + c_j ) x_j if a_j < 0,
741  * where c_j is the coefficient of x_j in the row, put j into the set
742  * N2 if a_j > 0
743  * N1 if a_j < 0
744  * and update the right hand side of the constraint in the relaxation
745  * rhs = rhs - a_j d_j
746  */
747  assert(SCIPvarIsBinary(vlbvars[bestlbtype]));
748 
749  rowcoefbinary = rowcoefsbinary[SCIPvarGetProbindex(vlbvars[bestlbtype])];
750  varsolvalbinary = varsolvals[SCIPvarGetProbindex(vlbvars[bestlbtype])];
751 
752  val = (rowcoef * vlbcoefs[bestlbtype]) + rowcoefbinary;
753  contsolval = (rowcoef * (varsolvals[probidx] - vlbconsts[bestlbtype])) + (rowcoefbinary * varsolvalbinary);
754 
755  if( SCIPisPositive(scip, rowcoef) )
756  {
757  transvarcoefs[*ntransvars] = - 1;
758  transvarvubcoefs[*ntransvars] = - val;
759  transbinvarsolvals[*ntransvars] = varsolvalbinary;
760  transcontvarsolvals[*ntransvars] = - contsolval;
761  }
762  else
763  {
764  assert(SCIPisNegative(scip, rowcoef));
765  transvarcoefs[*ntransvars] = 1;
766  transvarvubcoefs[*ntransvars] = val;
767  transbinvarsolvals[*ntransvars] = varsolvalbinary;
768  transcontvarsolvals[*ntransvars] = contsolval;
769  }
770  (*transrhs) -= (rowcoef * vlbconsts[bestlbtype]);
771 
772  /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
773  assoctransvars[SCIPvarGetProbindex(vlbvars[bestlbtype])] = *ntransvars;
774 
775  SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
776  transvarcoefs[*ntransvars] == 1 ? "+" : "-", *ntransvars, *ntransvars, transvarvubcoefs[*ntransvars],
777  *ntransvars, SCIPvarGetName(vlbvars[bestlbtype]), *transrhs + (rowcoef * vlbconsts[bestlbtype]), rowcoef,
778  vlbconsts[bestlbtype], *transrhs );
779  }
780  }
781  else
782  {
783  /* use bestub to define y'_j */
784 
785  assert(!SCIPisInfinity(scip, bestub));
786  assert(!SCIPisInfinity(scip, - bestslb));
787  assert(bestslbtype == -1 || bestslbtype == -2);
788  assert(bestubtype > -3 && bestubtype < SCIPvarGetNVubs(var));
789 
790  /* store for y_j that bestub is the bound used to define y'_j and that y'_j is the associated real variable
791  * in the relaxed set
792  */
793  boundsfortrans[probidx] = bestubtype;
794  boundtypesfortrans[probidx] = SCIP_BOUNDTYPE_UPPER;
795  assoctransvars[probidx] = *ntransvars;
796 
797  if( bestubtype < 0 )
798  {
799  SCIP_Real val;
800  SCIP_Real contsolval;
801 
802  /* use simple upper bound in bestslb = l_j <= y_j <= u_j = bestub to define
803  * y'_j = a_j ( y_j - l_j ) with 0 <= y'_j <= a_j ( u_j - l_j ) x_j and x_j = 1 if a_j > 0
804  * y'_j = - a_j ( y_j - l_j ) with 0 <= y'_j <= - a_j ( u_j - l_j ) x_j and x_j = 1 if a_j < 0,
805  * put j into the set
806  * N1 if a_j > 0
807  * N2 if a_j < 0
808  * and update the right hand side of the constraint in the relaxation
809  * rhs = rhs - a_j l_j
810  */
811  val = rowcoef * ( bestub - bestslb );
812  contsolval = rowcoef * ( varsolvals[probidx] - bestslb );
813  if( SCIPisPositive(scip, rowcoef) )
814  {
815  transvarcoefs[*ntransvars] = 1;
816  transvarvubcoefs[*ntransvars] = val;
817  transbinvarsolvals[*ntransvars] = 1.0;
818  transcontvarsolvals[*ntransvars] = contsolval;
819  }
820  else
821  {
822  assert(SCIPisNegative(scip, rowcoef));
823  transvarcoefs[*ntransvars] = - 1;
824  transvarvubcoefs[*ntransvars] = - val;
825  transbinvarsolvals[*ntransvars] = 1.0;
826  transcontvarsolvals[*ntransvars] = - contsolval;
827  }
828  (*transrhs) -= (rowcoef * bestslb);
829 
830  SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
831  transvarcoefs[*ntransvars] == 1 ? "+" : "-", *ntransvars, *ntransvars, transvarvubcoefs[*ntransvars],
832  *ntransvars, *transrhs + (rowcoef * bestslb), rowcoef, bestslb, *transrhs);
833  }
834  else
835  {
836  SCIP_Real rowcoefbinary;
837  SCIP_Real varsolvalbinary;
838  SCIP_Real val;
839  SCIP_Real contsolval;
840 
841  SCIP_VAR** vubvars = SCIPvarGetVubVars(var);
842  SCIP_Real* vubconsts = SCIPvarGetVubConstants(var);
843  SCIP_Real* vubcoefs = SCIPvarGetVubCoefs(var);
844 
845  /* use variable upper bound in bestslb = l_j <= y_j <= u~_j x_j + d_j = bestub to define
846  * y'_j = a_j ( y_j - d_j ) + c_j x_j with 0 <= y'_j <= ( a_j u~_j + c_j ) x_j if a_j > 0
847  * y'_j = - ( a_j ( y_j - d_j ) + c_j x_j ) with 0 <= y'_j <= - ( a_j u~_j + c_j ) x_j if a_j < 0,
848  * where c_j is the coefficient of x_j in the row, put j into the set
849  * N1 if a_j > 0
850  * N2 if a_j < 0
851  * and update the right hand side of the constraint in the relaxation
852  * rhs = rhs - a_j d_j
853  */
854  assert(SCIPvarIsBinary(vubvars[bestubtype]));
855 
856  rowcoefbinary = rowcoefsbinary[SCIPvarGetProbindex(vubvars[bestubtype])];
857  varsolvalbinary = varsolvals[SCIPvarGetProbindex(vubvars[bestubtype])];
858 
859  val = ( rowcoef * vubcoefs[bestubtype] ) + rowcoefbinary;
860  contsolval = (rowcoef * (varsolvals[probidx] - vubconsts[bestubtype])) + (rowcoefbinary * varsolvalbinary);
861 
862  if( SCIPisPositive(scip, rowcoef) )
863  {
864  transvarcoefs[*ntransvars] = 1;
865  transvarvubcoefs[*ntransvars] = val;
866  transbinvarsolvals[*ntransvars] = varsolvalbinary;
867  transcontvarsolvals[*ntransvars] = contsolval;
868  }
869  else
870  {
871  assert(SCIPisNegative(scip, rowcoef));
872  transvarcoefs[*ntransvars] = - 1;
873  transvarvubcoefs[*ntransvars] = - val;
874  transbinvarsolvals[*ntransvars] = varsolvalbinary;
875  transcontvarsolvals[*ntransvars] = - contsolval;
876  }
877  (*transrhs) -= (rowcoef * vubconsts[bestubtype]);
878 
879  /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
880  assoctransvars[SCIPvarGetProbindex(vubvars[bestubtype])] = *ntransvars;
881 
882  SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
883  transvarcoefs[*ntransvars] == 1 ? "+" : "-", *ntransvars, *ntransvars, transvarvubcoefs[*ntransvars],
884  *ntransvars, SCIPvarGetName(vubvars[bestubtype]), *transrhs + (rowcoef * vubconsts[bestubtype]), rowcoef,
885  vubconsts[bestubtype], *transrhs);
886  }
887  }
888 
889  /* relaxing the mixed integer set to a 0-1 single node flow set was not successful because coefficient of y_j and
890  * the bounds selected for the transformation together result in an infinite variable upper bound in the 0-1 single
891  * node flow set; this can be caused by huge but finite values for the bounds or the coefficient
892  */
893  if( SCIPisInfinity(scip, transvarvubcoefs[*ntransvars]) )
894  {
895  assert(!(*success));
896  goto TERMINATE;
897  }
898 
899  assert(boundsfortrans[probidx] > -3);
900  assert(assoctransvars[probidx] >= 0 && assoctransvars[probidx] == (*ntransvars));
901  assert(transvarcoefs[*ntransvars] == 1 || transvarcoefs[*ntransvars] == - 1 );
902  assert(SCIPisFeasGE(scip, transbinvarsolvals[*ntransvars], 0.0)
903  && SCIPisFeasLE(scip, transbinvarsolvals[*ntransvars], 1.0));
904  assert(SCIPisFeasGE(scip, transvarvubcoefs[*ntransvars], 0.0)
905  && !SCIPisInfinity(scip, transvarvubcoefs[*ntransvars]));
906 
907  /* updates number of variables in transformed problem */
908  (*ntransvars)++;
909  }
910  assert(*ntransvars == nnonzcolsnonbinary);
911 
912  SCIPdebugMsg(scip, "transformation for BINARY variables (nbinvars=%d):\n", nnonzcolsbinary);
913 
914  /* binary variables not involved in used variable bounds imposed on non-binary variable */
915  for( c = 0; c < nnonzcolsbinary; c++ )
916  {
917  SCIP_VAR* var;
918  SCIP_Real rowcoef;
919  int probidx;
920  SCIP_Real val;
921  SCIP_Real contsolval;
922 
923  var = SCIPcolGetVar(nonzcols[nonzcolsbinary[c]]);
924  probidx = SCIPvarGetProbindex(var);
925  rowcoef = rowweight * scale * nonzcoefs[nonzcolsbinary[c]];
926 
927  assert(rowcoefsbinary[probidx] == rowcoef); /*lint !e777*/
928  assert(!SCIPisZero(scip, rowcoef));
929 
930  SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n", c, rowcoef, SCIPvarGetName(var), probidx, varsolvals[probidx],
931  SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
932 
933  /* x_j has already been handled in connection with a non-binary variable */
934  if( assoctransvars[probidx] > -1 )
935  {
936  assert(assoctransvars[probidx] >= 0 && assoctransvars[probidx] <= nnonzcolsnonbinary);
937  assert(boundsfortrans[probidx] == -3);
938  SCIPdebugMsg(scip, " --> already handled\n");
939  continue;
940  }
941 
942  assert(assoctransvars[probidx] == -1);
943  assert(boundsfortrans[probidx] == -3);
944 
945  /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
946  assoctransvars[probidx] = *ntransvars;
947 
948  /* define
949  * y'_j = c_j x_j with 0 <= y'_j <= c_j x_j if c_j > 0
950  * y'_j = - c_j x_j with 0 <= y'_j <= - c_j x_j if c_j < 0,
951  * where c_j is the coefficient of x_j in the row and put j into the set
952  * N1 if c_j > 0
953  * N2 if c_j < 0.
954  */
955  val = rowcoef;
956  contsolval = rowcoef * varsolvals[probidx];
957  if( SCIPisPositive(scip, rowcoef) )
958  {
959  transvarcoefs[*ntransvars] = 1;
960  transvarvubcoefs[*ntransvars] = val;
961  transbinvarsolvals[*ntransvars] = varsolvals[probidx];
962  transcontvarsolvals[*ntransvars] = contsolval;
963  }
964  else
965  {
966  assert(SCIPisNegative(scip, rowcoef));
967  transvarcoefs[*ntransvars] = - 1;
968  transvarvubcoefs[*ntransvars] = - val;
969  transbinvarsolvals[*ntransvars] = varsolvals[probidx];
970  transcontvarsolvals[*ntransvars] = - contsolval;
971  }
972  assert(assoctransvars[probidx] >= 0 && assoctransvars[probidx] == (*ntransvars));
973  assert(transvarcoefs[*ntransvars] == 1 || transvarcoefs[*ntransvars] == - 1 );
974  assert(SCIPisFeasGE(scip, transbinvarsolvals[*ntransvars], 0.0)
975  && SCIPisFeasLE(scip, transbinvarsolvals[*ntransvars], 1.0));
976  assert(SCIPisFeasGE(scip, transvarvubcoefs[*ntransvars], 0.0)
977  && !SCIPisInfinity(scip, transvarvubcoefs[*ntransvars]));
978 
979  SCIPdebugMsg(scip, " --> ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s))\n", transvarcoefs[*ntransvars] == 1 ? "+" : "-", *ntransvars, *ntransvars,
980  transvarvubcoefs[*ntransvars], *ntransvars, SCIPvarGetName(var) );
981 
982  /* updates number of variables in transformed problem */
983  (*ntransvars)++;
984  }
985  assert(*ntransvars >= nnonzcolsnonbinary && *ntransvars <= nnonzcols);
986 
987  /* construction was successful */
988  *success = TRUE;
989 
990 #ifdef SCIP_DEBUG
991  SCIPdebugMsg(scip, "constraint in constructed 0-1 single node flow relaxation: ");
992  for( c = 0; c < *ntransvars; c++ )
993  {
994  SCIPdebugMsgPrint(scip, "%s y'_%d ", transvarcoefs[c] == 1 ? "+" : "-", c);
995  }
996  SCIPdebugMsgPrint(scip, "<= %g\n", *transrhs);
997 #endif
998 
999  TERMINATE:
1000  /* free data structures */
1001  SCIPfreeBufferArray(scip, &rowcoefsbinary);
1002  SCIPfreeBufferArray(scip, &nonzcolsnonbinary);
1003  SCIPfreeBufferArray(scip, &nonzcolsbinary);
1004 
1005  return SCIP_OKAY;
1006 }
1007 
1008 /** solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide
1009  * arrays to store all selected items and all not selected items
1010  */
1011 static
1012 SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT(
1013  SCIP* scip, /**< SCIP data structure */
1014  int nitems, /**< number of available items */
1015  SCIP_Real* weights, /**< item weights */
1016  SCIP_Real* profits, /**< item profits */
1017  SCIP_Real capacity, /**< capacity of knapsack */
1018  int* items, /**< item numbers */
1019  int* solitems, /**< array to store items in solution, or NULL */
1020  int* nonsolitems, /**< array to store items not in solution, or NULL */
1021  int* nsolitems, /**< pointer to store number of items in solution, or NULL */
1022  int* nnonsolitems, /**< pointer to store number of items not in solution, or NULL */
1023  SCIP_Real* solval /**< pointer to store optimal solution value, or NULL */
1024  )
1025 {
1026  SCIP_Real* tempsort;
1027  SCIP_Real solitemsweight;
1028  SCIP_Real mediancapacity;
1029  int j;
1030  int i;
1031  int criticalitem;
1032 
1033  assert(weights != NULL);
1034  assert(profits != NULL);
1035  assert(SCIPisFeasGE(scip, capacity, 0.0));
1036  assert(!SCIPisInfinity(scip, capacity));
1037  assert(items != NULL);
1038  assert(nitems >= 0);
1039 
1040  if( solitems != NULL )
1041  {
1042  *nsolitems = 0;
1043  *nnonsolitems = 0;
1044  }
1045  if( solval != NULL )
1046  *solval = 0.0;
1047 
1048  /* allocate memory for temporary array used for sorting; array should contain profits divided by corresponding weights (p_1 / w_1 ... p_n / w_n )*/
1049  SCIP_CALL( SCIPallocBufferArray(scip, &tempsort, nitems) );
1050 
1051  /* initialize temporary array */
1052  for( i = nitems - 1; i >= 0; --i )
1053  tempsort[i] = profits[i] / weights[i];
1054 
1055  /* decrease capacity slightly to make it tighter than the original capacity */
1056  mediancapacity = capacity * (1 - SCIPfeastol(scip));
1057 
1058  /* rearrange items around */
1059  SCIPselectWeightedDownRealRealInt(tempsort, profits, items, weights, mediancapacity, nitems, &criticalitem);
1060 
1061  /* free temporary array */
1062  SCIPfreeBufferArray(scip, &tempsort);
1063 
1064  /* select items as long as they fit into the knapsack */
1065  solitemsweight = 0.0;
1066  for( j = 0; j < nitems && SCIPisFeasLT(scip, solitemsweight + weights[j], capacity); j++ )
1067  {
1068  if( solitems != NULL )
1069  {
1070  solitems[*nsolitems] = items[j];
1071  (*nsolitems)++;
1072  }
1073  if( solval != NULL )
1074  (*solval) += profits[j];
1075  solitemsweight += weights[j];
1076  }
1077 
1078 
1079  /* continue to put items into the knapsack if they entirely fit */
1080  for( ; j < nitems; j++ )
1081  {
1082  if( SCIPisFeasLT(scip, solitemsweight + weights[j], capacity) )
1083  {
1084  if( solitems != NULL )
1085  {
1086  solitems[*nsolitems] = items[j];
1087  (*nsolitems)++;
1088  }
1089  if( solval != NULL )
1090  (*solval) += profits[j];
1091  solitemsweight += weights[j];
1092  }
1093  else if( solitems != NULL )
1094  {
1095  nonsolitems[*nnonsolitems] = items[j];
1096  (*nnonsolitems)++;
1097  }
1098  }
1099 
1100  return SCIP_OKAY;
1101 }
1102 
1103 /** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
1104 static
1105 SCIP_Bool isIntegralScalar(
1106  SCIP_Real val, /**< value that should be scaled to an integral value */
1107  SCIP_Real scalar, /**< scalar that should be tried */
1108  SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
1109  SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
1110  )
1111 {
1112  SCIP_Real sval;
1113  SCIP_Real downval;
1114  SCIP_Real upval;
1115 
1116  assert(mindelta <= 0.0);
1117  assert(maxdelta >= 0.0);
1118 
1119  sval = val * scalar;
1120  downval = floor(sval);
1121  upval = ceil(sval);
1122 
1123  return (SCIPrelDiff(sval, downval) <= maxdelta || SCIPrelDiff(sval, upval) >= mindelta);
1124 }
1125 
1126 /** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
1127  * should be used in connection with isIntegralScalar()
1128  */
1129 static
1130 SCIP_Longint getIntegralVal(
1131  SCIP_Real val, /**< value that should be scaled to an integral value */
1132  SCIP_Real scalar, /**< scalar that should be tried */
1133  SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
1134  SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
1135  )
1136 {
1137  SCIP_Real sval;
1138  SCIP_Real upval;
1139  SCIP_Longint intval;
1140 
1141  assert(mindelta <= 0.0);
1142  assert(maxdelta >= 0.0);
1143 
1144  sval = val * scalar;
1145  upval = ceil(sval);
1146 
1147  if( SCIPrelDiff(sval, upval) >= mindelta )
1148  intval = (SCIP_Longint) upval;
1149  else
1150  intval = (SCIP_Longint) (floor(sval));
1151 
1152  return intval;
1153 }
1154 
1155 /** build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished
1156  * flow cover contains variables which have been fixed in advance
1157  */
1158 static
1159 void buildFlowCover(
1160  SCIP* scip, /**< SCIP data structure */
1161  int* coefs, /**< coefficient of all real variables in N1&N2 */
1162  SCIP_Real* vubcoefs, /**< coefficient in vub of all real variables in N1&N2 */
1163  SCIP_Real rhs, /**< right hand side of 0-1 single node flow constraint */
1164  int* solitems, /**< items in knapsack */
1165  int* nonsolitems, /**< items not in knapsack */
1166  int nsolitems, /**< number of items in knapsack */
1167  int nnonsolitems, /**< number of items not in knapsack */
1168  int* nflowcovervars, /**< pointer to store number of variables in flow cover */
1169  int* nnonflowcovervars, /**< pointer to store number of variables not in flow cover */
1170  int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
1171  SCIP_Real* flowcoverweight, /**< pointer to store weight of flow cover */
1172  SCIP_Real* lambda /**< pointer to store lambda */
1173  )
1174 {
1175  int j;
1176 
1177  assert(scip != NULL);
1178  assert(coefs != NULL);
1179  assert(vubcoefs != NULL);
1180  assert(solitems != NULL);
1181  assert(nonsolitems != NULL);
1182  assert(nsolitems >= 0);
1183  assert(nnonsolitems >= 0);
1184  assert(nflowcovervars != NULL && *nflowcovervars >= 0);
1185  assert(nnonflowcovervars != NULL && *nnonflowcovervars >= 0);
1186  assert(flowcoverstatus != NULL);
1187  assert(flowcoverweight != NULL);
1188  assert(lambda != NULL);
1189 
1190  /* get flowcover status for each item */
1191  for( j = 0; j < nsolitems; j++ )
1192  {
1193  /* j in N1 with z°_j = 1 => j in N1\C1 */
1194  if( coefs[solitems[j]] == 1 )
1195  {
1196  flowcoverstatus[solitems[j]] = -1;
1197  (*nnonflowcovervars)++;
1198  }
1199  /* j in N2 with z_j = 1 => j in C2 */
1200  else
1201  {
1202  assert(coefs[solitems[j]] == -1);
1203  flowcoverstatus[solitems[j]] = 1;
1204  (*nflowcovervars)++;
1205  (*flowcoverweight) -= vubcoefs[solitems[j]];
1206  }
1207  }
1208  for( j = 0; j < nnonsolitems; j++ )
1209  {
1210  /* j in N1 with z°_j = 0 => j in C1 */
1211  if( coefs[nonsolitems[j]] == 1 )
1212  {
1213  flowcoverstatus[nonsolitems[j]] = 1;
1214  (*nflowcovervars)++;
1215  (*flowcoverweight) += vubcoefs[nonsolitems[j]];
1216  }
1217  /* j in N2 with z_j = 0 => j in N2\C2 */
1218  else
1219  {
1220  assert(coefs[nonsolitems[j]] == -1);
1221  flowcoverstatus[nonsolitems[j]] = -1;
1222  (*nnonflowcovervars)++;
1223  }
1224  }
1225 
1226  /* get lambda = sum_{j in C1} u_j - sum_{j in C2} u_j - rhs */
1227  *lambda = (*flowcoverweight) - rhs;
1228 }
1229 
1230 /** get a flow cover (C1, C2) for a given 0-1 single node flow set
1231  * {(x,y) in {0,1}^n x R^n : sum_{j in N1} y_j - sum_{j in N2} y_j <= b, 0 <= y_j <= u_j x_j},
1232  * i.e., get sets C1 subset N1 and C2 subset N2 with sum_{j in C1} u_j - sum_{j in C2} u_j = b + lambda and lambda > 0
1233  */
1234 static
1235 SCIP_RETCODE getFlowCover(
1236  SCIP* scip, /**< SCIP data structure */
1237  int* coefs, /**< coefficient of all real variables in N1&N2 */
1238  SCIP_Real* solvals, /**< LP solution value of binary variable in vub of all real vars in N1&N2 */
1239  SCIP_Real* vubcoefs, /**< coefficient in vub of all real variables in N1&N2 */
1240  int nvars, /**< number of real variables in N1&N2 */
1241  SCIP_Real rhs, /**< right hand side of 0-1 single node flow constraint */
1242  int* nflowcovervars, /**< pointer to store number of variables in flow cover */
1243  int* nnonflowcovervars, /**< pointer to store number of variables not in flow cover */
1244  int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
1245  SCIP_Real* lambda, /**< pointer to store lambda */
1246  SCIP_Bool* found /**< pointer to store whether a cover was found */
1247  )
1248 {
1249  SCIP_Real* transprofitsint;
1250  SCIP_Real* transprofitsreal;
1251  SCIP_Real* transweightsreal;
1252  SCIP_Longint* transweightsint;
1253  int* items;
1254  int* itemsint;
1255  int* nonsolitems;
1256  int* solitems;
1257  SCIP_Real flowcoverweight;
1258  SCIP_Real flowcoverweightafterfix;
1259  SCIP_Real n1itemsweight;
1260  SCIP_Real n2itemsminweight;
1261  SCIP_Real scalar;
1262  SCIP_Real transcapacityreal;
1263 #if !defined(NDEBUG) || defined(SCIP_DEBUG)
1264  SCIP_Bool kpexact;
1265 #endif
1266  SCIP_Bool scalesuccess;
1267  SCIP_Bool transweightsrealintegral;
1268  SCIP_Longint transcapacityint;
1269  int nflowcovervarsafterfix;
1270  int nitems;
1271  int nn1items;
1272  int nnonflowcovervarsafterfix;
1273  int nnonsolitems;
1274  int nsolitems;
1275  int j;
1276 
1277  assert(scip != NULL);
1278  assert(coefs != NULL);
1279  assert(solvals != NULL);
1280  assert(vubcoefs != NULL);
1281  assert(nvars > 0);
1282  assert(nflowcovervars != NULL);
1283  assert(nnonflowcovervars != NULL);
1284  assert(flowcoverstatus != NULL);
1285  assert(lambda != NULL);
1286  assert(found != NULL);
1287 
1288  SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
1289 
1290  /* get data structures */
1291  SCIP_CALL( SCIPallocBufferArray(scip, &items, nvars) );
1292  SCIP_CALL( SCIPallocBufferArray(scip, &itemsint, nvars) );
1293  SCIP_CALL( SCIPallocBufferArray(scip, &transprofitsreal, nvars) );
1294  SCIP_CALL( SCIPallocBufferArray(scip, &transprofitsint, nvars) );
1295  SCIP_CALL( SCIPallocBufferArray(scip, &transweightsreal, nvars) );
1296  SCIP_CALL( SCIPallocBufferArray(scip, &transweightsint, nvars) );
1297  SCIP_CALL( SCIPallocBufferArray(scip, &solitems, nvars) );
1298  SCIP_CALL( SCIPallocBufferArray(scip, &nonsolitems, nvars) );
1299 
1300  BMSclearMemoryArray(flowcoverstatus, nvars);
1301  *found = FALSE;
1302  *nflowcovervars = 0;
1303  *nnonflowcovervars = 0;
1304  flowcoverweight = 0.0;
1305  nflowcovervarsafterfix = 0;
1306  nnonflowcovervarsafterfix = 0;
1307  flowcoverweightafterfix = 0.0;
1308 #if !defined(NDEBUG) || defined(SCIP_DEBUG)
1309  kpexact = FALSE;
1310 #endif
1311 
1312  /* fix some variables in advance according to the following fixing strategy
1313  * put j into N1\C1, if j in N1 and x*_j = 0,
1314  * put j into C1, if j in N1 and x*_j = 1,
1315  * put j into C2, if j in N2 and x*_j = 1,
1316  * put j into N2\C2, if j in N2 and x*_j = 0
1317  * and get the set of the remaining variables
1318  */
1319  SCIPdebugMsg(scip, "0. Fix some variables in advance:\n");
1320  nitems = 0;
1321  nn1items = 0;
1322  n1itemsweight = 0.0;
1323  n2itemsminweight = SCIP_REAL_MAX;
1324  for( j = 0; j < nvars; j++ )
1325  {
1326  assert(coefs[j] == 1 || coefs[j] == -1);
1327  assert(SCIPisFeasGE(scip, solvals[j], 0.0) && SCIPisFeasLE(scip, solvals[j], 1.0));
1328  assert(SCIPisFeasGE(scip, vubcoefs[j], 0.0));
1329 
1330  /* if u_j = 0, put j into N1\C1 and N2\C2, respectively */
1331  if( SCIPisFeasZero(scip, vubcoefs[j]) )
1332  {
1333  flowcoverstatus[j] = -1;
1334  (*nnonflowcovervars)++;
1335  continue;
1336  }
1337 
1338  /* x*_j is fractional */
1339  if( !SCIPisFeasIntegral(scip, solvals[j]) )
1340  {
1341  items[nitems] = j;
1342  nitems++;
1343  if( coefs[j] == 1 )
1344  {
1345  n1itemsweight += vubcoefs[j];
1346  nn1items++;
1347  }
1348  else
1349  n2itemsminweight = MIN(n2itemsminweight, vubcoefs[j]);
1350  }
1351  /* j is in N1 and x*_j = 0 */
1352  else if( coefs[j] == 1 && solvals[j] < 0.5 )
1353  {
1354  flowcoverstatus[j] = -1;
1355  (*nnonflowcovervars)++;
1356  SCIPdebugMsg(scip, " <%d>: in N1-C1\n", j);
1357  }
1358  /* j is in N1 and x*_j = 1 */
1359  else if( coefs[j] == 1 && solvals[j] > 0.5 )
1360  {
1361  flowcoverstatus[j] = 1;
1362  (*nflowcovervars)++;
1363  flowcoverweight += vubcoefs[j];
1364  SCIPdebugMsg(scip, " <%d>: in C1\n", j);
1365  }
1366  /* j is in N2 and x*_j = 1 */
1367  else if( coefs[j] == -1 && solvals[j] > 0.5 )
1368  {
1369  flowcoverstatus[j] = 1;
1370  (*nflowcovervars)++;
1371  flowcoverweight -= vubcoefs[j];
1372  SCIPdebugMsg(scip, " <%d>: in C2\n", j);
1373  }
1374  /* j is in N2 and x*_j = 0 */
1375  else
1376  {
1377  assert(coefs[j] == -1 && solvals[j] < 0.5);
1378  flowcoverstatus[j] = -1;
1379  (*nnonflowcovervars)++;
1380  SCIPdebugMsg(scip, " <%d>: in N2-C2\n", j);
1381  }
1382  }
1383  assert((*nflowcovervars) + (*nnonflowcovervars) + nitems == nvars);
1384  assert(nn1items >= 0);
1385 
1386  /* to find a flow cover, transform the following knapsack problem
1387  *
1388  * (KP^SNF) max sum_{j in N1} ( x*_j - 1 ) z_j + sum_{j in N2} x*_j z_j
1389  * sum_{j in N1} u_j z_j - sum_{j in N2} u_j z_j > b
1390  * z_j in {0,1} for all j in N1 & N2
1391  *
1392  * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
1393  * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
1394  *
1395  * (KP^SNF_rat) max sum_{j in N1} ( 1 - x*_j ) z°_j + sum_{j in N2} x*_j z_j
1396  * sum_{j in N1} u_j z°_j + sum_{j in N2} u_j z_j < - b + sum_{j in N1} u_j
1397  * z°_j in {0,1} for all j in N1
1398  * z_j in {0,1} for all j in N2,
1399  * and solve it approximately under consideration of the fixing,
1400  * or
1401  * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
1402  * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
1403  * and multiplying the constraint by a suitable scalar C
1404  *
1405  * (KP^SNF_int) max sum_{j in N1} ( 1 - x*_j ) z°_j + sum_{j in N2} x*_j z_j
1406  * sum_{j in N1} C u_j z°_j + sum_{j in N2} C u_j z_j <= c
1407  * z°_j in {0,1} for all j in N1
1408  * z_j in {0,1} for all j in N2,
1409  * where
1410  * c = floor[ C (- b + sum_{j in N1} u_j ) ] if frac[ C (- b + sum_{j in N1} u_j ) ] > 0
1411  * c = C (- b + sum_{j in N1} u_j ) - 1 if frac[ C (- b + sum_{j in N1} u_j ) ] = 0
1412  * and solve it exactly under consideration of the fixing.
1413  */
1414  SCIPdebugMsg(scip, "1. Transform KP^SNF to KP^SNF_rat:\n");
1415 
1416  /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
1417  transweightsrealintegral = TRUE;
1418  for( j = 0; j < nitems; j++ )
1419  {
1420  transweightsreal[j] = vubcoefs[items[j]];
1421 
1422  if( !isIntegralScalar(transweightsreal[j], 1.0, -MINDELTA, MAXDELTA) )
1423  transweightsrealintegral = FALSE;
1424 
1425  if( coefs[items[j]] == 1 )
1426  {
1427  transprofitsreal[j] = 1.0 - solvals[items[j]];
1428  SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
1429  items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
1430  }
1431  else
1432  {
1433  transprofitsreal[j] = solvals[items[j]];
1434  SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
1435  items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
1436  }
1437  }
1438  /* get capacity of knapsack constraint in KP^SNF_rat */
1439  transcapacityreal = - rhs + flowcoverweight + n1itemsweight;
1440  SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
1441  rhs, flowcoverweight, n1itemsweight, transcapacityreal);
1442 
1443  /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
1444  * is less than or equal to zero
1445  */
1446  if( SCIPisFeasLE(scip, transcapacityreal/10, 0.0) )
1447  {
1448  assert(!(*found));
1449  goto TERMINATE;
1450  }
1451 
1452  /* KP^SNF_rat has been solved by fixing some variables in advance */
1453  assert(nitems >= 0);
1454  if( nitems == 0)
1455  {
1456  /* get lambda = sum_{j in C1} u_j - sum_{j in C2} u_j - rhs */
1457  *lambda = flowcoverweight - rhs;
1458  *found = TRUE;
1459  goto TERMINATE;
1460  }
1461 
1462  /* Use the following strategy
1463  * solve KP^SNF_int exactly, if a suitable factor C is found and (nitems*capacity) <= MAXDYNPROGSPACE,
1464  * solve KP^SNF_rat approximately, otherwise
1465  */
1466 
1467  /* find a scaling factor C */
1468  if( transweightsrealintegral )
1469  {
1470  /* weights are already integral */
1471  scalar = 1.0;
1472  scalesuccess = TRUE;
1473  }
1474  else
1475  {
1476  scalesuccess = FALSE;
1477  SCIP_CALL( SCIPcalcIntegralScalar(transweightsreal, nitems, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE, &scalar,
1478  &scalesuccess) );
1479  }
1480 
1481  /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
1482  nsolitems = -1;
1483  nnonsolitems = -1;
1484 
1485  /* suitable factor C was found*/
1486  if( scalesuccess )
1487  {
1488  SCIP_Real tmp1;
1489  SCIP_Real tmp2;
1490 
1491  /* transform KP^SNF to KP^SNF_int */
1492  for( j = 0; j < nitems; ++j )
1493  {
1494  transweightsint[j] = getIntegralVal(transweightsreal[j], scalar, -MINDELTA, MAXDELTA);
1495  transprofitsint[j] = transprofitsreal[j];
1496  itemsint[j] = items[j];
1497  }
1498  if( isIntegralScalar(transcapacityreal, scalar, -MINDELTA, MAXDELTA) )
1499  {
1500  transcapacityint = getIntegralVal(transcapacityreal, scalar, -MINDELTA, MAXDELTA);
1501  transcapacityint -= 1;
1502  }
1503  else
1504  transcapacityint = (SCIP_Longint) (transcapacityreal * scalar);
1505  nflowcovervarsafterfix = *nflowcovervars;
1506  nnonflowcovervarsafterfix = *nnonflowcovervars;
1507  flowcoverweightafterfix = flowcoverweight;
1508 
1509  tmp1 = (SCIP_Real) (nitems + 1);
1510  tmp2 = (SCIP_Real) ((transcapacityint) + 1);
1511  if( transcapacityint * nitems <= MAXDYNPROGSPACE && tmp1 * tmp2 <= INT_MAX / 8.0)
1512  {
1513  SCIP_Bool success;
1514 
1515  /* solve KP^SNF_int by dynamic programming */
1516  SCIP_CALL(SCIPsolveKnapsackExactly(scip, nitems, transweightsint, transprofitsint, transcapacityint,
1517  itemsint, solitems, nonsolitems, &nsolitems, &nnonsolitems, NULL, &success));
1518 
1519  if( !success )
1520  {
1521  /* solve KP^SNF_rat approximately */
1522  SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal,
1523  transcapacityreal, items, solitems, nonsolitems, &nsolitems, &nnonsolitems, NULL));
1524  }
1525 #if !defined(NDEBUG) || defined(SCIP_DEBUG)
1526  else
1527  kpexact = TRUE;
1528 #endif
1529  }
1530  else
1531  {
1532  /* solve KP^SNF_rat approximately */
1533  SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
1534  items, solitems, nonsolitems, &nsolitems, &nnonsolitems, NULL));
1535  assert(!kpexact);
1536  }
1537  }
1538  else
1539  {
1540  /* solve KP^SNF_rat approximately */
1541  SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
1542  items, solitems, nonsolitems, &nsolitems, &nnonsolitems, NULL));
1543  assert(!kpexact);
1544  }
1545 
1546  assert(nsolitems != -1);
1547  assert(nnonsolitems != -1);
1548 
1549  /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
1550  assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == nvars);
1551  buildFlowCover(scip, coefs, vubcoefs, rhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
1552  nnonflowcovervars, flowcoverstatus, &flowcoverweight, lambda);
1553  assert(*nflowcovervars + *nnonflowcovervars == nvars);
1554 
1555  /* if the found structure is not a flow cover, because of scaling, solve KP^SNF_rat approximately */
1556  if( SCIPisFeasLE(scip, *lambda, 0.0) )
1557  {
1558  assert(kpexact);
1559 
1560  /* solve KP^SNF_rat approximately */
1561  SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
1562  items, solitems, nonsolitems, &nsolitems, &nnonsolitems, NULL));
1563 #ifdef SCIP_DEBUG /* this time only for SCIP_DEBUG, because only then, the variable is used again */
1564  kpexact = FALSE;
1565 #endif
1566 
1567  /* build the flow cover from the solution of KP^SNF_rat and the fixing */
1568  *nflowcovervars = nflowcovervarsafterfix;
1569  *nnonflowcovervars = nnonflowcovervarsafterfix;
1570  flowcoverweight = flowcoverweightafterfix;
1571 
1572  assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == nvars);
1573  buildFlowCover(scip, coefs, vubcoefs, rhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
1574  nnonflowcovervars, flowcoverstatus, &flowcoverweight, lambda);
1575  assert(*nflowcovervars + *nnonflowcovervars == nvars);
1576  }
1577  *found = TRUE;
1578 
1579  TERMINATE:
1580  assert((!*found) || SCIPisFeasGT(scip, *lambda, 0.0));
1581 #ifdef SCIP_DEBUG
1582  if( *found )
1583  {
1584  SCIPdebugMsg(scip, "2. %s solution:\n", kpexact ? "exact" : "approximate");
1585  for( j = 0; j < nvars; j++ )
1586  {
1587  if( coefs[j] == 1 && flowcoverstatus[j] == 1 )
1588  {
1589  SCIPdebugMsg(scip, " C1: + y_%d [u_%d = %g]\n", j, j, vubcoefs[j]);
1590  }
1591  else if( coefs[j] == -1 && flowcoverstatus[j] == 1 )
1592  {
1593  SCIPdebugMsg(scip, " C2: - y_%d [u_%d = %g]\n", j, j, vubcoefs[j]);
1594  }
1595  }
1596  SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", flowcoverweight, rhs, *lambda);
1597  }
1598 #endif
1599 
1600  /* free data structures */
1601  SCIPfreeBufferArray(scip, &nonsolitems);
1602  SCIPfreeBufferArray(scip, &solitems);
1603  SCIPfreeBufferArray(scip, &transweightsint);
1604  SCIPfreeBufferArray(scip, &transweightsreal);
1605  SCIPfreeBufferArray(scip, &transprofitsint);
1606  SCIPfreeBufferArray(scip, &transprofitsreal);
1607  SCIPfreeBufferArray(scip, &itemsint);
1608  SCIPfreeBufferArray(scip, &items);
1609 
1610  return SCIP_OKAY;
1611 }
1612 
1613 /** for a given flow cover and a given value of delta, choose L1 subset N1 \ C1 and L2 subset N2 \ C2 by comparison such that
1614  * the violation of the resulting c-MIRFCI is maximized.
1615  */
1616 static
1617 void getL1L2(
1618  SCIP* scip, /**< SCIP data structure */
1619  int ntransvars, /**< number of continuous variables in N1 & N2 */
1620  int* transvarcoefs, /**< coefficient of all continuous variables in N1 & N2 */
1621  SCIP_Real* transbinvarsolvals, /**< LP solution value of bin var in vub of all continuous vars in N1 & N2 */
1622  SCIP_Real* transcontvarsolvals,/**< LP solution value of all continuous vars in N1 & N2 */
1623  SCIP_Real* transvarvubcoefs, /**< coefficient of vub of all continuous variables in N1 & N2 */
1624  int* transvarflowcoverstatus,/**< pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) */
1625  SCIP_Real delta, /**< delta */
1626  SCIP_Real lambda /**< lambda */
1627  )
1628 {
1629  SCIP_Real fbeta;
1630  SCIP_Real onedivoneminusfbeta;
1631  int j;
1632 
1633  assert(scip != NULL);
1634  assert(ntransvars >= 0);
1635  assert(transvarcoefs != NULL);
1636  assert(transbinvarsolvals != NULL);
1637  assert(transcontvarsolvals != NULL);
1638  assert(transvarvubcoefs != NULL);
1639  assert(transvarflowcoverstatus != NULL);
1640  assert(SCIPisGT(scip, delta, lambda));
1641  assert(SCIPisFeasGT(scip, lambda, 0.0));
1642 
1643  /* for beta = - lambda / delta with delta > lambda,
1644  * f_beta = beta - floor[beta] = 1 - ( lambda / delta )
1645  * 1 / ( 1 - f_beta ) = delta / lambda
1646  */
1647  fbeta = 1.0 - (lambda / delta);
1648  onedivoneminusfbeta = delta / lambda;
1649 
1650  SCIPdebugMsg(scip, " --------------------- get L1 and L2 -----------------------------------------------------\n");
1651  SCIPdebugMsg(scip, " L1 = { j in N1-C1 : y*_j >= ( u_j - lambda F_{f_beta}( u_j/delta) ) x*_j }\n");
1652  SCIPdebugMsg(scip, " L2 = { j in N2-C2 : y*_j >= - lambda F_{f_beta}(- u_j/delta) x*_j }\n");
1653 
1654  /* set flowcover status of continuous variable x_j to 2, i.e., put j intp L1 and L2, respectively
1655  * if j is in N1\C1 and y*_j >= ( u_j - lambda F_{f_beta}( u_j/delta) ) x*_j
1656  * if j is in N2\C2 and y*_j >= - lambda F_{f_beta}(- u_j/delta) x*_j
1657  */
1658  for( j = 0; j < ntransvars; j++ )
1659  {
1660  SCIP_Real d;
1661  SCIP_Real downd;
1662  SCIP_Real fd;
1663  SCIP_Real mirval;
1664 
1665  assert(transvarcoefs[j] == 1 || transvarcoefs[j] == -1);
1666  assert(SCIPisGE(scip, transvarvubcoefs[j], 0.0));
1667  assert(SCIPisFeasGE(scip, transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, transbinvarsolvals[j], 1.0));
1668 
1669  /* j in N1\C1 */
1670  if( transvarcoefs[j] == 1 && transvarflowcoverstatus[j] == -1 )
1671  {
1672  /* Let d = u_j/delta and alpha = f_beta, than the MIR function is defined as
1673  * F_{alpha}(d) = down(d) , if f_d <= alpha
1674  * F_{alpha}(d) = down(d) + (f_d - alpha)/(1 - alpha), if f_d > alpha
1675  */
1676  d = transvarvubcoefs[j] / delta;
1677  downd = SCIPfloor(scip, d);
1678  fd = d - downd;
1679  if( SCIPisSumLE(scip, fd, fbeta) )
1680  mirval = downd;
1681  else
1682  mirval = downd + ((fd - fbeta) * onedivoneminusfbeta);
1683 
1684  /* y*_j >= ( u_j - lambda F_{f_beta}(u_j/delta) ) x*_j */
1685  if( SCIPisFeasGE(scip, transcontvarsolvals[j], ( transvarvubcoefs[j] - ( lambda * mirval ) ) * transbinvarsolvals[j]) )
1686  transvarflowcoverstatus[j] = 2;
1687 
1688  SCIPdebugMsg(scip, " <%d>: in N1-C1: %g ?>=? ( %g - %g F_{f_beta}(%g)(%g) ) %g = %g ---> fcstatus = %d\n",
1689  j, transcontvarsolvals[j], transvarvubcoefs[j], lambda, d, mirval, transbinvarsolvals[j],
1690  ( transvarvubcoefs[j] - ( lambda * mirval ) ) * transbinvarsolvals[j], transvarflowcoverstatus[j]);
1691  }
1692 
1693  /* j in N2\C2 */
1694  if( transvarcoefs[j] == -1 && transvarflowcoverstatus[j] == -1 )
1695  {
1696  /* Let d = - u_j/delta and alpha = f_beta, than the MIR function is defined as
1697  * F_{alpha}(d) = down(d) , if f_d <= alpha
1698  * F_{alpha}(d) = down(d) + (f_d - alpha)/(1 - alpha), if f_d > alpha
1699  */
1700  d = - transvarvubcoefs[j] / delta;
1701  downd = SCIPfloor(scip, d);
1702  fd = d - downd;
1703  if( SCIPisSumLE(scip, fd, fbeta) )
1704  mirval = downd;
1705  else
1706  mirval = downd + ((fd - fbeta) * onedivoneminusfbeta);
1707 
1708  /* j in N2\C2 and y*_j >= - lambda F_{f_beta}(- u_j/delta) x*_j */
1709  if( SCIPisFeasGE(scip, transcontvarsolvals[j], - ( lambda * mirval ) * transbinvarsolvals[j]) )
1710  transvarflowcoverstatus[j] = 2;
1711 
1712  SCIPdebugMsg(scip, " <%d>: in N2-C2: %g ?>=? - %g F_{f_beta}(-%g)(%g) %g = %g ---> fcstatus = %d\n",
1713  j, transcontvarsolvals[j], lambda, d, mirval, transbinvarsolvals[j],
1714  - ( lambda * mirval ) * transbinvarsolvals[j], transvarflowcoverstatus[j]);
1715  }
1716  }
1717 }
1718 
1719 /** get for all problem variables with nonzero coefficient in current row the bound which should be used for the
1720  * substitution routine in the c-MIR routine; this bound depends on the bound used for each variable to get associated
1721  * variable in transformed problem
1722  */
1723 static
1724 SCIP_RETCODE getBoundsForSubstitution(
1725  SCIP* scip, /**< SCIP data structure */
1726  SCIP_VAR** vars, /**< active problem variables */
1727  int nvars, /**< number of active problem variables */
1728  int* boundsfortrans, /**< bound used for transformation for all non-binary vars of current row */
1729  SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bound used for transform. for all non-binary vars of current row */
1730  int* assoctransvars, /**< associated var in transformed problem for all vars of current row */
1731  int* transvarcoefs, /**< coefficient of all vars in transformed problem */
1732  int* flowcoverstatus, /**< flow cover status of all non-binary vars in transformed problem;
1733  * 1 if in C1 & C2, 2 if in L2, -1 N1 \ C1 & N2 \ (C2&L2) */
1734  int ntransvars, /**< number of vars in transformed problem */
1735  int* boundsforsubst, /**< pointer to store bounds that should be used for substitution in c-mir for vars */
1736  SCIP_BOUNDTYPE* boundtypesforsubst /**< pointer to store types of bounds that should be used for substitution in c-mir */
1737  )
1738 {
1739  int j;
1740 
1741  assert(scip != NULL);
1742  assert(vars != NULL);
1743  assert(nvars >= 0);
1744  assert(boundsfortrans != NULL);
1745  assert(boundtypesfortrans != NULL);
1746  assert(assoctransvars != NULL);
1747  assert(transvarcoefs != NULL);
1748  assert(flowcoverstatus != NULL);
1749  assert(ntransvars >= 0 && ntransvars <= nvars);
1750  assert(boundsforsubst != NULL);
1751  assert(boundtypesforsubst != NULL);
1752 
1753  for( j = 0; j < nvars; j++ )
1754  {
1755  assert(SCIPvarGetProbindex(vars[j]) == j);
1756  assert(assoctransvars[j] == -1 || ( flowcoverstatus[assoctransvars[j]] == -1
1757  || flowcoverstatus[assoctransvars[j]] == 1 || flowcoverstatus[assoctransvars[j]] == 2 ));
1758 
1759  /* variable has no associated variable in transformed problem */
1760  if( assoctransvars[j] == -1 )
1761  {
1762  assert(boundsfortrans[j] == -3);
1763  boundsforsubst[j] = -3;
1764  continue;
1765  }
1766 
1767  /* binary variable */
1768  if( SCIPvarIsBinary(vars[j]) )
1769  {
1770  /* j in C1 & C2 */
1771  if( flowcoverstatus[assoctransvars[j]] == 1 )
1772  {
1773  boundsforsubst[j] = -1;
1774  boundtypesforsubst[j] = SCIP_BOUNDTYPE_UPPER;
1775  }
1776  /* j in N1\C1 & N2\C2 */
1777  else
1778  {
1779  boundsforsubst[j] = -1;
1780  boundtypesforsubst[j] = SCIP_BOUNDTYPE_LOWER;
1781  }
1782  }
1783  /* non-binary variables */
1784  else
1785  {
1786  /* j in C1 & C2 & L1 & L2 */
1787  if( flowcoverstatus[assoctransvars[j]] >= 1 )
1788  {
1789  boundsforsubst[j] = boundsfortrans[j];
1790  boundtypesforsubst[j] = boundtypesfortrans[j];
1791  }
1792  /* j in N1\C1 & N2\(C2 & L2) */
1793  else
1794  {
1795  if( boundtypesfortrans[j] == SCIP_BOUNDTYPE_UPPER )
1796  {
1797  SCIP_Real closestlb;
1798  int closestlbtype;
1799 
1800  getClosestLb(scip, vars[j], ALLOWLOCAL, &closestlb, &closestlbtype);
1801  assert(!SCIPisInfinity(scip, -closestlb));
1802  assert(closestlbtype == -1 || closestlbtype == -2);
1803 
1804  boundsforsubst[j] = closestlbtype;
1805  boundtypesforsubst[j] = SCIP_BOUNDTYPE_LOWER;
1806  }
1807  else
1808  {
1809  SCIP_Real closestub;
1810  int closestubtype;
1811 
1812  getClosestUb(scip, vars[j], ALLOWLOCAL, &closestub, &closestubtype);
1813  assert(!SCIPisInfinity(scip, closestub));
1814  assert(closestubtype == -1 || closestubtype == -2);
1815 
1816  boundsforsubst[j] = closestubtype;
1817  boundtypesforsubst[j] = SCIP_BOUNDTYPE_UPPER;
1818  }
1819  }
1820  }
1821  }
1822 
1823  return SCIP_OKAY;
1824 }
1825 
1826 /** stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm */
1827 static
1828 SCIP_RETCODE storeCutInArrays(
1829  SCIP* scip, /**< SCIP data structure */
1830  int nvars, /**< number of problem variables */
1831  SCIP_VAR** vars, /**< problem variables */
1832  SCIP_Real* cutcoefs, /**< dense coefficient vector */
1833  SCIP_Real* varsolvals, /**< dense variable LP solution vector */
1834  char normtype, /**< type of norm to use for efficacy norm calculation */
1835  SCIP_VAR** cutvars, /**< array to store variables of sparse cut vector */
1836  SCIP_Real* cutvals, /**< array to store coefficients of sparse cut vector */
1837  int* cutlen, /**< pointer to store number of nonzero entries in cut */
1838  SCIP_Real* cutact, /**< pointer to store activity of cut */
1839  SCIP_Real* cutnorm /**< pointer to store norm of cut vector */
1840  )
1841 {
1842  SCIP_Real val;
1843  SCIP_Real absval;
1844  SCIP_Real cutsqrnorm;
1845  SCIP_Real act;
1846  SCIP_Real norm;
1847  int len;
1848  int v;
1849 
1850  assert(nvars == 0 || cutcoefs != NULL);
1851  assert(nvars == 0 || varsolvals != NULL);
1852  assert(cutvars != NULL);
1853  assert(cutvals != NULL);
1854  assert(cutlen != NULL);
1855  assert(cutact != NULL);
1856  assert(cutnorm != NULL);
1857 
1858  len = 0;
1859  act = 0.0;
1860  norm = 0.0;
1861  switch( normtype )
1862  {
1863  case 'e':
1864  cutsqrnorm = 0.0;
1865  for( v = 0; v < nvars; ++v )
1866  {
1867  val = cutcoefs[v];
1868  if( !SCIPisZero(scip, val) )
1869  {
1870  act += val * varsolvals[v];
1871  cutsqrnorm += SQR(val);
1872  cutvars[len] = vars[v];
1873  cutvals[len] = val;
1874  len++;
1875  }
1876  }
1877  norm = SQRT(cutsqrnorm);
1878  break;
1879  case 'm':
1880  for( v = 0; v < nvars; ++v )
1881  {
1882  val = cutcoefs[v];
1883  if( !SCIPisZero(scip, val) )
1884  {
1885  act += val * varsolvals[v];
1886  absval = REALABS(val);
1887  norm = MAX(norm, absval);
1888  cutvars[len] = vars[v];
1889  cutvals[len] = val;
1890  len++;
1891  }
1892  }
1893  break;
1894  case 's':
1895  for( v = 0; v < nvars; ++v )
1896  {
1897  val = cutcoefs[v];
1898  if( !SCIPisZero(scip, val) )
1899  {
1900  act += val * varsolvals[v];
1901  norm += REALABS(val);
1902  cutvars[len] = vars[v];
1903  cutvals[len] = val;
1904  len++;
1905  }
1906  }
1907  break;
1908  case 'd':
1909  for( v = 0; v < nvars; ++v )
1910  {
1911  val = cutcoefs[v];
1912  if( !SCIPisZero(scip, val) )
1913  {
1914  act += val * varsolvals[v];
1915  norm = 1.0;
1916  cutvars[len] = vars[v];
1917  cutvals[len] = val;
1918  len++;
1919  }
1920  }
1921  break;
1922  default:
1923  SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", normtype);
1924  return SCIP_INVALIDDATA;
1925  }
1926 
1927  *cutlen = len;
1928  *cutact = act;
1929  *cutnorm = norm;
1930 
1931  return SCIP_OKAY;
1932 }
1933 
1934 /** adds given cut to LP if violated */
1935 static
1936 SCIP_RETCODE addCut(
1937  SCIP* scip, /**< SCIP data structure */
1938  SCIP_SEPA* sepa, /**< separator */
1939  SCIP_SEPADATA* sepadata, /**< separator data */
1940  SCIP_VAR** vars, /**< problem variables */
1941  int nvars, /**< number of problem variables */
1942  SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
1943  SCIP_Real* varsolvals, /**< solution values of active variables */
1944  SCIP_Real* cutcoefs, /**< coefficients of active variables in cut */
1945  SCIP_Real cutrhs, /**< right hand side of cut */
1946  SCIP_Bool cutislocal, /**< is the cut only locally valid? */
1947  int cutrank, /**< rank of the cut */
1948  char normtype, /**< type of norm to use for efficacy norm calculation */
1949  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
1950  int* ncuts /**< pointer to count the number of added cuts */
1951  )
1952 {
1953  SCIP_VAR** cutvars;
1954  SCIP_Real* cutvals;
1955  SCIP_Real cutact;
1956  SCIP_Real cutnorm;
1957  int cutlen;
1958  SCIP_Bool success;
1959 
1960  assert(scip != NULL);
1961  assert(varsolvals != NULL);
1962  assert(cutcoefs != NULL);
1963  assert(ncuts != NULL);
1964  assert(cutoff != NULL);
1965  assert(nvars == 0 || vars != NULL);
1966 
1967  *cutoff = FALSE;
1968 
1969  SCIPdebugMsg(scip, "--------------------- found cut ---------------------------------------------------------\n");
1970 
1971  /* gets temporary memory for storing the cut as sparse row */
1972  SCIP_CALL( SCIPallocBufferArray(scip, &cutvars, nvars) );
1973  SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) );
1974 
1975  /* stores the cut as sparse row, calculates activity and norm of cut */
1976  SCIP_CALL( storeCutInArrays(scip, nvars, vars, cutcoefs, varsolvals, normtype,
1977  cutvars, cutvals, &cutlen, &cutact, &cutnorm) );
1978 
1979  if( SCIPisPositive(scip, cutnorm) && SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm) )
1980  {
1981  SCIP_ROW* cut;
1982  char cutname[SCIP_MAXSTRLEN];
1983 
1984  /* creates the cut */
1985  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "flowcover%d_%d", SCIPgetNLPs(scip), *ncuts);
1986  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
1987  cutislocal, FALSE, sepadata->dynamiccuts) );
1988  SCIP_CALL( SCIPaddVarsToRow(scip, cut, cutlen, cutvars, cutvals) );
1989 
1990  /* set cut rank */
1991  SCIProwChgRank(cut, cutrank);
1992 
1993  SCIPdebugMsg(scip, " -> found potential flowcover cut <%s>: activity=%f, rhs=%f, norm=%f, eff=%f\n",
1994  cutname, cutact, cutrhs, cutnorm, SCIPgetCutEfficacy(scip, sol, cut));
1995  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );
1996 
1997 #if 0 /* tries to scale the cut to integral values */
1998  SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
1999  10, 100.0, MAKECONTINTEGRAL, &success) );
2000  if( success && !SCIPisCutEfficacious(scip, sol, cut) )
2001  {
2002  SCIPdebugMsg(scip, " -> flowcover cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
2003  cutname, cutact, cutrhs, cutnorm, SCIPgetCutEfficacy(scip, sol, cut));
2004  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );
2005  success = FALSE;
2006  }
2007 #else
2008  success = TRUE;
2009 #endif
2010 
2011  /* if scaling was successful, adds the cut */
2012  if( success ) /*lint !e774*/ /* Boolean within 'if' always evaluates to True */
2013  {
2014  SCIPdebugMsg(scip, " -> found flowcover cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%g)\n",
2015  cutname, cutact, cutrhs, cutnorm, SCIPgetCutEfficacy(scip, sol, cut), SCIProwGetRank(cut),
2016  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
2017  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
2018  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );
2019  SCIP_CALL( SCIPaddCut(scip, sol, cut, FALSE, cutoff) );
2020  if( !(*cutoff) && !cutislocal )
2021  {
2022  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
2023  }
2024  (*ncuts)++;
2025  }
2026 
2027  /* releases the row */
2028  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2029  }
2030 
2031  /* frees temporary memory */
2032  SCIPfreeBufferArray(scip, &cutvals);
2033  SCIPfreeBufferArray(scip, &cutvars);
2034 
2035  return SCIP_OKAY;
2036 }
2037 
2038 /** calculates efficacy of the given cut */
2039 static
2040 SCIP_Real calcEfficacy(
2041  int nvars, /**< number of variables in the problem */
2042  SCIP_Real* cutcoefs, /**< dense vector of cut coefficients */
2043  SCIP_Real cutrhs, /**< right hand side of cut */
2044  SCIP_Real cutact /**< activity of cut */
2045  )
2046 {
2047  SCIP_Real sqrnorm;
2048  int i;
2049 
2050  assert(cutcoefs != NULL);
2051 
2052  sqrnorm = 0;
2053  for( i = 0; i < nvars; ++i )
2054  sqrnorm += SQR(cutcoefs[i]);
2055  sqrnorm = MAX(sqrnorm, 1e-06);
2056  return (cutact - cutrhs)/SQRT(sqrnorm);
2057 }
2058 
2059 /* generate c-MIRFCI for different sets L1 and L2 and different values of delta */
2060 static
2061 SCIP_RETCODE cutGenerationHeuristic(
2062  SCIP* scip, /**< SCIP data structure */
2063  SCIP_SEPA* sepa, /**< separator */
2064  SCIP_SEPADATA* sepadata, /**< separator data */
2065  SCIP_VAR** vars, /**< active problem variables */
2066  int nvars, /**< number of active problem variables */
2067  SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
2068  SCIP_Real* varsolvals, /**< solution values of active variables */
2069  SCIP_Real* rowweights, /**< weight of rows in aggregated row */
2070  SCIP_Real scalar, /**< additional scaling factor of rows in aggregation */
2071  int* boundsfortrans, /**< bound used for all non-bin vars of row */
2072  SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bound used for all non-binary vars of row */
2073  int* assoctransvars, /**< associated var in relaxed set for all vars of row */
2074  int ntransvars, /**< number of real variables in N1&N2 */
2075  int* transvarcoefs, /**< coefficient of all continuous variables in N1 & N2 */
2076  SCIP_Real* transbinvarsolvals, /**< LP solution value of binary variable in vub of all real vars in N1&N2 */
2077  SCIP_Real* transcontvarsolvals,/**< LP solution value of all real vars in N1&N2 */
2078  SCIP_Real* transvarvubcoefs, /**< coefficient of vub of all continuous variables in N1 & N2 */
2079  int* transvarflowcoverstatus, /**< pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) */
2080  SCIP_Real lambda, /**< lambda */
2081  char normtype, /**< type of norm to use for efficacy norm calculation */
2082  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
2083  int* ncuts /**< pointer to count the number of generated cuts */
2084  )
2085 {
2086  SCIP_BOUNDTYPE* boundtypesforsubst;
2087  SCIP_Real* candsetdelta;
2088  SCIP_Real* cutcoefs;
2089  SCIP_Real* testeddeltas;
2090  int* boundsforsubst;
2091  int* transvarflowcoverstatustmp;
2092  SCIP_Real bestdelta;
2093  SCIP_Real bestefficacy;
2094  SCIP_Real c1vubcoefsmax;
2095  SCIP_Real cutrhs;
2096  SCIP_Real cutact;
2097  SCIP_Real l2tmpvubcoefsmax;
2098  SCIP_Real nvubcoefsmax;
2099  SCIP_Bool cutislocal;
2100  SCIP_Bool success;
2101  int cutrank;
2102  int ncandsetdelta;
2103  int ntesteddeltas;
2104  int startidx;
2105  int j;
2106 
2107  assert(scip != NULL);
2108  assert(sepadata != NULL);
2109  assert(vars != NULL);
2110  assert(varsolvals != NULL);
2111  assert(rowweights != NULL);
2112  assert(boundsfortrans != NULL);
2113  assert(boundtypesfortrans != NULL);
2114  assert(assoctransvars != NULL);
2115  assert(ntransvars >=0);
2116  assert(transvarcoefs != NULL);
2117  assert(transbinvarsolvals != NULL);
2118  assert(transcontvarsolvals != NULL);
2119  assert(transvarvubcoefs != NULL);
2120  assert(transvarflowcoverstatus != NULL);
2121  assert(SCIPisFeasGT(scip, lambda, 0.0));
2122  assert(ncuts != NULL);
2123 
2124  SCIPdebugMsg(scip, "--------------------- cut generation heuristic ------------------------------------------\n");
2125 
2126  /* get data structures */
2127  SCIP_CALL( SCIPallocBufferArray(scip, &testeddeltas, ntransvars + 4) );
2128  SCIP_CALL( SCIPallocBufferArray(scip, &candsetdelta, ntransvars + 4) );
2129  SCIP_CALL( SCIPallocBufferArray(scip, &transvarflowcoverstatustmp, ntransvars) );
2130  SCIP_CALL( SCIPallocBufferArray(scip, &boundsforsubst, nvars) );
2131  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesforsubst, nvars) );
2132  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
2133 
2134  SCIPdebugMsg(scip, "1. get candidate set for the value of delta:\n");
2135 
2136  /* get candidate set for the value of delta
2137  * N* = { u_j : j in N and u_j > lambda} & { max{ u_j : j in N and u_j >= lambda } + 1, lambda + 1 };
2138  * store the following values which will be tested in any case at the beginning of the array
2139  * max{ u_j : j in N and u_j >= lambda } + 1,
2140  * lambda + 1,
2141  * max{ u_j : j in C1 and u_j > lambda },
2142  * max{ u_j : j in L~2 and u_j > lambda }
2143  */
2144  ncandsetdelta = 0;
2145  startidx = 4;
2146 
2147  /* get max{ u_j : j in C1 and u_j > lambda }, max{ u_j : j in L~2 and u_j > lambda }, and
2148  * max{ u_j : j in N and u_j >= lambda } and store { u_j : j in N and u_j > lambda }
2149  */
2150  c1vubcoefsmax = SCIP_REAL_MIN;
2151  l2tmpvubcoefsmax = SCIP_REAL_MIN;
2152  nvubcoefsmax = SCIP_REAL_MIN;
2153  for( j = 0; j < ntransvars; j++ )
2154  {
2155  SCIP_Real val;
2156 
2157  /* j is in C1 and u_j > lambda */
2158  if( transvarcoefs[j] == 1 && transvarflowcoverstatus[j] == 1
2159  && SCIPisFeasGT(scip, transvarvubcoefs[j], lambda) )
2160  c1vubcoefsmax = MAX(c1vubcoefsmax, transvarvubcoefs[j]);
2161 
2162  /* j is in L~2 and u_j > lambda */
2163  val = MIN(transvarvubcoefs[j], lambda) * transbinvarsolvals[j];
2164  if( transvarcoefs[j] == -1 && transvarflowcoverstatus[j] == -1 && SCIPisFeasLE(scip, val, transcontvarsolvals[j])
2165  && SCIPisFeasGT(scip, transvarvubcoefs[j], lambda) )
2166  l2tmpvubcoefsmax = MAX(l2tmpvubcoefsmax, transvarvubcoefs[j]);
2167 
2168  /* u_j + 1 > lambda */
2169  if( SCIPisFeasGT(scip, transvarvubcoefs[j] + 1.0, lambda) )
2170  nvubcoefsmax = MAX(nvubcoefsmax, transvarvubcoefs[j]);
2171 
2172  /* u_j > lambda */
2173  if( SCIPisFeasGT(scip, transvarvubcoefs[j], lambda) )
2174  {
2175  candsetdelta[startidx + ncandsetdelta] = transvarvubcoefs[j];
2176  ncandsetdelta++;
2177  SCIPdebugMsg(scip, " u_j = %g\n", transvarvubcoefs[j]);
2178  }
2179  }
2180 
2181  /* store max { u_j : j in N and u_j >= lambda } + 1 */
2182  if( !SCIPisInfinity(scip, -nvubcoefsmax) )
2183  {
2184  assert(SCIPisFeasGT(scip, nvubcoefsmax + 1.0, lambda));
2185  startidx--;
2186  candsetdelta[startidx] = nvubcoefsmax + 1.0;
2187  ncandsetdelta++;
2188  SCIPdebugMsg(scip, " max u_j+1 = %g\n", nvubcoefsmax + 1.0);
2189  }
2190 
2191  /* store lambda + 1 */
2192  startidx--;
2193  candsetdelta[startidx] = lambda + 1.0;
2194  ncandsetdelta++;
2195  SCIPdebugMsg(scip, " lambda + 1 = %g\n", lambda + 1.0);
2196 
2197  /* store max{ u_j : j in C1 and u_j > lambda } and max{ u_j : j in C1 & L~2 and u_j > lambda } */
2198  if( !SCIPisInfinity(scip, -l2tmpvubcoefsmax) && SCIPisFeasGT(scip, l2tmpvubcoefsmax, c1vubcoefsmax) )
2199  {
2200  assert(SCIPisFeasGT(scip, l2tmpvubcoefsmax, lambda));
2201  startidx--;
2202  candsetdelta[startidx] = l2tmpvubcoefsmax;
2203  ncandsetdelta++;
2204  SCIPdebugMsg(scip, " l2tmpvubcoefsmax = %g\n", l2tmpvubcoefsmax);
2205  }
2206  if( !SCIPisInfinity(scip, -c1vubcoefsmax) )
2207  {
2208  assert(SCIPisFeasGT(scip, c1vubcoefsmax, lambda));
2209  startidx--;
2210  candsetdelta[startidx] = c1vubcoefsmax;
2211  ncandsetdelta++;
2212  SCIPdebugMsg(scip, " c1vubcoefsmax = %g\n", c1vubcoefsmax);
2213  }
2214 
2215  assert(startidx >= 0 && startidx <= 3);
2216  assert(startidx + ncandsetdelta >= 4);
2217  assert(ncandsetdelta >= 1 && ncandsetdelta <= ntransvars + 4);
2218 
2219  SCIPdebugMsg(scip, "2. generate c-MIRFCIs for different values of delta:\n");
2220 
2221  /* for each value of delta choose L1 subset N1\C1 and L2 subset N2\C2 by comparison, generate the
2222  * c-MIRFCI for delta, (C1, C2) and (L1, L2) and select the most efficient c-MIRFCI
2223  */
2224  ntesteddeltas = 0;
2225  bestdelta = 0.0;
2226  bestefficacy = 0.0;
2227  for( j = startidx; j < startidx + ncandsetdelta && ntesteddeltas < sepadata->maxtestdelta; j++ )
2228  {
2229  SCIP_Real delta;
2230  SCIP_Real onedivdelta;
2231  SCIP_Bool tested;
2232  int i;
2233 
2234  /* get current delta and corresponding scalar for c-MIR routine */
2235  delta = candsetdelta[j];
2236  onedivdelta = 1.0 / delta;
2237 
2238  /* do not use scaling factors (1/delta) which are too small, since this max cause numerical problems;
2239  * besides for relatively small lambda and large scaling factors (delta), we get f_beta = 1 - lambda/delta > MINFRAC
2240  */
2241  if( SCIPisZero(scip, scalar * onedivdelta) )
2242  continue;
2243 
2244  /* check, if delta was already tested */
2245  tested = FALSE;
2246  for( i = 0; i < ntesteddeltas && !tested; i++ )
2247  tested = SCIPisEQ(scip, testeddeltas[i], delta);
2248  if( tested )
2249  continue;
2250  testeddeltas[ntesteddeltas] = delta;
2251  ntesteddeltas++;
2252 
2253  SCIPdebugMsg(scip, " delta = %g:\n", delta);
2254 
2255  /* work on copy of transvarflowcoverstatus because current choice of sets L1 and L2 will change
2256  * transvarflowcoverstatus
2257  */
2258  BMScopyMemoryArray(transvarflowcoverstatustmp, transvarflowcoverstatus, ntransvars);
2259 
2260  /* get L1 subset of N1\C1 and L2 subset of N2\C2 by comparison */
2261  getL1L2(scip, ntransvars, transvarcoefs, transbinvarsolvals, transcontvarsolvals, transvarvubcoefs,
2262  transvarflowcoverstatustmp, delta, lambda);
2263 
2264  /* get bounds for substitution in c-MIR routine for original mixed integer set;
2265  * note that the scalar has already been considered in the constructed 0-1 single node flow relaxation
2266  */
2267  SCIP_CALL( getBoundsForSubstitution(scip, vars, nvars, boundsfortrans, boundtypesfortrans, assoctransvars,
2268  transvarcoefs, transvarflowcoverstatustmp, ntransvars, boundsforsubst, boundtypesforsubst ) );
2269 
2270  /* generate c-MIRFCI for flow cover (C1,C2), L1 subset N1\C1 and L2 subset N2\C2 and delta */
2271  SCIP_CALL( SCIPcalcMIR(scip, sol, BOUNDSWITCH, TRUE, ALLOWLOCAL, FIXINTEGRALRHS, boundsforsubst,
2272  boundtypesforsubst, (int) MAXAGGRLEN(nvars), 1.0, MINFRAC, MAXFRAC, rowweights, -1.0, NULL, -1, -1, NULL,
2273  scalar * onedivdelta, NULL, NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, NULL) );
2274  assert(ALLOWLOCAL || !cutislocal);
2275 
2276  /* delta leads to c-MIRFCI which is more violated */
2277  if( success )
2278  {
2279  SCIP_Real efficacy;
2280 
2281  for(i = 0; i < nvars; i++)
2282  cutcoefs[i] = lambda * cutcoefs[i];
2283  cutrhs = lambda * cutrhs;
2284  cutact = lambda * cutact;
2285 
2286  efficacy = calcEfficacy(nvars, cutcoefs, cutrhs, cutact);
2287 
2288  SCIPdebugMsg(scip, " ---> act = %g rhs = %g eff = %g (old besteff = %g, old bestdelta=%g)\n", cutact, cutrhs, efficacy, bestefficacy, bestdelta);
2289 
2290  if( efficacy > bestefficacy )
2291  {
2292  bestdelta = delta;
2293  bestefficacy = efficacy;
2294  }
2295  }
2296  }
2297 
2298  /* delta found */
2299  if( SCIPisEfficacious(scip, bestefficacy) )
2300  {
2301  SCIP_Real onedivbestdelta;
2302  int i;
2303 
2304  assert(bestdelta != 0.0);
2305  onedivbestdelta = 1.0 / bestdelta;
2306 
2307  /* for best value of delta: get L1 subset of N1\C1 and L2 subset of N2\C2 by comparison */
2308  getL1L2(scip, ntransvars, transvarcoefs, transbinvarsolvals, transcontvarsolvals, transvarvubcoefs,
2309  transvarflowcoverstatus, bestdelta, lambda);
2310 
2311  /* for best value of delta: get bounds for substitution in c-MIR routine for original mixed integer set
2312  * note that the scalar has already been considered in the constructed 0-1 single node flow relaxation
2313  */
2314  SCIP_CALL( getBoundsForSubstitution(scip, vars, nvars, boundsfortrans, boundtypesfortrans, assoctransvars,
2315  transvarcoefs, transvarflowcoverstatus, ntransvars, boundsforsubst, boundtypesforsubst ) );
2316 
2317  /* generate c-MIRFCI for flow cover (C1,C2), L1 subset N1\C1 and L2 subset N2\C2 and bestdelta */
2318  SCIP_CALL( SCIPcalcMIR(scip, sol, BOUNDSWITCH, TRUE, ALLOWLOCAL, FIXINTEGRALRHS, boundsforsubst,
2319  boundtypesforsubst, (int) MAXAGGRLEN(nvars), 1.0, MINFRAC, MAXFRAC, rowweights, -1.0, NULL, -1, -1, NULL,
2320  scalar * onedivbestdelta, NULL, NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
2321  assert(ALLOWLOCAL || !cutislocal);
2322  assert(success);
2323 
2324  for(i = 0; i < nvars; i++)
2325  cutcoefs[i] = lambda * cutcoefs[i];
2326  cutrhs = lambda * cutrhs;
2327  cutact = lambda * cutact;
2328 
2329  assert(SCIPisFeasEQ(scip, bestefficacy, calcEfficacy(nvars, cutcoefs, cutrhs, cutact)));
2330  SCIP_CALL( addCut(scip, sepa, sepadata, vars, nvars, sol, varsolvals, cutcoefs, cutrhs, cutislocal, cutrank, normtype, cutoff, ncuts) );
2331  }
2332 
2333  /* free data structures */
2334  SCIPfreeBufferArray(scip, &cutcoefs);
2335  SCIPfreeBufferArray(scip, &boundtypesforsubst);
2336  SCIPfreeBufferArray(scip, &boundsforsubst);
2337  SCIPfreeBufferArray(scip, &transvarflowcoverstatustmp);
2338  SCIPfreeBufferArray(scip, &candsetdelta);
2339  SCIPfreeBufferArray(scip, &testeddeltas);
2340 
2341  return SCIP_OKAY;
2342 }
2343 
2344 /** comparison method for scores of lp rows */
2345 static
2346 SCIP_DECL_SORTINDCOMP(rowScoreComp)
2347 { /*lint --e{715}*/
2348  SCIP_Real* rowscores = (SCIP_Real*)dataptr;
2349  SCIP_Real tmp;
2350 
2351  assert(rowscores != NULL);
2352  assert(0 <= ind1 && 0 <= ind2);
2353 
2354  tmp = rowscores[ind1] - rowscores[ind2];
2355 
2356  if( tmp < 0 )
2357  return 1;
2358  else if( tmp > 0 )
2359  return -1;
2360  else
2361  return 0;
2362 }
2363 
2364 /** search and add flowcover cuts that separate the given primal solution */
2365 static
2366 SCIP_RETCODE separateCuts(
2367  SCIP* scip, /**< SCIP data structure */
2368  SCIP_SEPA* sepa, /**< the flowcover separator */
2369  SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
2370  SCIP_RESULT* result /**< pointer to store the result */
2371  )
2372 {
2373  SCIP_ROW** rows;
2374  SCIP_VAR** vars;
2375  SCIP_BOUNDTYPE* boundtypesfortrans;
2376  SCIP_SEPADATA* sepadata;
2377  SCIP_Real* rowlhsscores;
2378  SCIP_Real* rowrhsscores;
2379  SCIP_Real* rowscores;
2380  SCIP_Real* rowweights;
2381  SCIP_Real* transbinvarsolvals;
2382  SCIP_Real* transcontvarsolvals;
2383  SCIP_Real* transvarvubcoefs;
2384  SCIP_Real* varsolvals;
2385  int* assoctransvars;
2386  int* boundsfortrans;
2387  int* covervars;
2388  int* noncovervars;
2389  int* roworder;
2390  int* transvarcoefs;
2391  int* transvarflowcoverstatus;
2392  SCIP_Real lambda;
2393  SCIP_Real maxslack;
2394  SCIP_Real objnorm;
2395  SCIP_Real transcapacity;
2396  SCIP_Bool transsuccess;
2397  SCIP_Bool flowcoverfound;
2398  SCIP_Bool cutoff = FALSE;
2399  char normtype;
2400  int depth;
2401  int maxfails;
2402  int maxsepacuts;
2403  int maxtries;
2404  int ncalls;
2405  int ncovervars;
2406  int nfails;
2407  int nnoncovervars;
2408  int nrows;
2409  int ntransvars;
2410  int ntries;
2411  int nvars;
2412  int ncuts;
2413  int r;
2414 
2415  assert(scip != NULL);
2416  assert(sepa != NULL);
2417  assert(result != NULL);
2418  assert(*result == SCIP_DIDNOTRUN);
2419 
2420  sepadata = SCIPsepaGetData(sepa);
2421  assert(sepadata != NULL);
2422 
2423  depth = SCIPgetDepth(scip);
2424  ncalls = SCIPsepaGetNCallsAtNode(sepa);
2425 
2426  /* only call the flow cover cuts separator a given number of times at each node */
2427  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
2428  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
2429  return SCIP_OKAY;
2430 
2431  /* get all rows and number of rows */
2432  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2433  assert(nrows == 0 || rows != NULL);
2434 
2435  /* nothing to do, if LP is empty */
2436  if( nrows == 0 )
2437  return SCIP_OKAY;
2438 
2439  /* get active problem variables */
2440  vars = SCIPgetVars(scip);
2441  nvars = SCIPgetNVars(scip);
2442  assert(nvars == 0 || vars != NULL);
2443 
2444  /* nothing to do, if problem has no variables */
2445  if( nvars == 0 )
2446  return SCIP_OKAY;
2447 
2448  /* check whether SCIP was stopped in the meantime */
2449  if( SCIPisStopped(scip) )
2450  return SCIP_OKAY;
2451 
2452  *result = SCIP_DIDNOTFIND;
2453 
2454  /* get the type of norm to use for efficacy calculations */
2455  SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &normtype) );
2456 
2457  /* get data structures */
2458  SCIP_CALL( SCIPallocBufferArray(scip, &rowlhsscores, nrows) );
2459  SCIP_CALL( SCIPallocBufferArray(scip, &rowrhsscores, nrows) );
2460  SCIP_CALL( SCIPallocBufferArray(scip, &rowscores, nrows) );
2461  SCIP_CALL( SCIPallocBufferArray(scip, &roworder, nrows) );
2462  SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
2463  SCIP_CALL( SCIPallocBufferArray(scip, &assoctransvars, nvars) );
2464  SCIP_CALL( SCIPallocBufferArray(scip, &transvarcoefs, nvars) );
2465  SCIP_CALL( SCIPallocBufferArray(scip, &transvarvubcoefs, nvars) );
2466  SCIP_CALL( SCIPallocBufferArray(scip, &transbinvarsolvals, nvars) );
2467  SCIP_CALL( SCIPallocBufferArray(scip, &transcontvarsolvals, nvars) );
2468  SCIP_CALL( SCIPallocBufferArray(scip, &transvarflowcoverstatus, nvars) );
2469  SCIP_CALL( SCIPallocBufferArray(scip, &boundsfortrans, nvars) );
2470  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesfortrans, nvars) );
2471  SCIP_CALL( SCIPallocBufferArray(scip, &covervars, nvars) );
2472  SCIP_CALL( SCIPallocBufferArray(scip, &noncovervars, nvars) );
2473  SCIP_CALL( SCIPallocBufferArray(scip, &rowweights, nrows) );
2474 
2475  /* get the solution values for all active variables */
2476  SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, varsolvals) );
2477 
2478  /* get the maximal number of cuts allowed in a separation round */
2479  if( depth == 0 )
2480  {
2481  maxtries = sepadata->maxtriesroot;
2482  maxfails = sepadata->maxfailsroot;
2483  maxsepacuts = sepadata->maxsepacutsroot;
2484  maxslack = sepadata->maxslackroot;
2485  }
2486  else
2487  {
2488  maxtries = sepadata->maxtries;
2489  maxfails = sepadata->maxfails;
2490  maxsepacuts = sepadata->maxsepacuts;
2491  maxslack = sepadata->maxslack;
2492  }
2493 
2494  /* calculate row scores for both sides of all rows, and sort rows by nonincreasing maximal score */
2495  objnorm = SCIPgetObjNorm(scip);
2496  objnorm = MAX(objnorm, 1.0);
2497  for( r = 0; r < nrows; r++ )
2498  {
2499  int nnonz;
2500 
2501  assert(SCIProwGetLPPos(rows[r]) == r);
2502 
2503  nnonz = SCIProwGetNLPNonz(rows[r]);
2504  if( nnonz == 0 )
2505  {
2506  /* ignore empty rows */
2507  rowlhsscores[r] = 0.0;
2508  rowrhsscores[r] = 0.0;
2509  }
2510  else
2511  {
2512  SCIP_Real activity;
2513  SCIP_Real lhs;
2514  SCIP_Real rhs;
2515  SCIP_Real dualsol;
2516  SCIP_Real dualscore;
2517  SCIP_Real rowdensity;
2518  SCIP_Real rownorm;
2519  SCIP_Real slack;
2520 
2521  dualsol = (sol == NULL ? SCIProwGetDualsol(rows[r]) : 1.0);
2522  activity = SCIPgetRowSolActivity(scip, rows[r], sol);
2523  lhs = SCIProwGetLhs(rows[r]);
2524  rhs = SCIProwGetRhs(rows[r]);
2525  rownorm = SCIProwGetNorm(rows[r]);
2526  rownorm = MAX(rownorm, 0.1);
2527  rowdensity = (SCIP_Real)nnonz/(SCIP_Real)nvars;
2528  assert(SCIPisPositive(scip, rownorm));
2529 
2530  slack = (activity - lhs)/rownorm;
2531  dualscore = MAX(dualsol/objnorm, 0.0001);
2532  if( !SCIPisInfinity(scip, -lhs) && SCIPisLE(scip, slack, maxslack)
2533  && (ALLOWLOCAL || !SCIProwIsLocal(rows[r])) /*lint !e506 !e774*/
2534  && rowdensity <= sepadata->maxrowdensity )
2535  {
2536  rowlhsscores[r] = dualscore + DENSSCORE * rowdensity + sepadata->slackscore * MAX(1.0 - slack, 0.0);
2537  assert(rowlhsscores[r] > 0.0);
2538  }
2539  else
2540  rowlhsscores[r] = 0.0;
2541 
2542  slack = (rhs - activity)/rownorm;
2543  dualscore = MAX(-dualsol/objnorm, 0.0001);
2544  if( !SCIPisInfinity(scip, rhs) && SCIPisLE(scip, slack, maxslack)
2545  && (ALLOWLOCAL || !SCIProwIsLocal(rows[r])) /*lint !e506 !e774*/
2546  && rowdensity <= sepadata->maxrowdensity )
2547  {
2548  rowrhsscores[r] = dualscore + DENSSCORE * rowdensity + sepadata->slackscore * MAX(1.0 - slack, 0.0);
2549  assert(rowrhsscores[r] > 0.0);
2550  }
2551  else
2552  rowrhsscores[r] = 0.0;
2553  }
2554  rowscores[r] = MAX(rowlhsscores[r], rowrhsscores[r]);
2555 
2556  roworder[r] = r;
2557  }
2558 
2559  SCIPsortInd(roworder, rowScoreComp, (void*) rowscores, nrows);
2560 #ifndef NDEBUG
2561  for( r = nrows - 1; r > 0; --r )
2562  assert(rowscores[roworder[r]] <= rowscores[roworder[r - 1]]);
2563 #endif
2564 
2565  /* initialize weights of rows for aggregation for c-mir routine */
2566  BMSclearMemoryArray(rowweights, nrows);
2567 
2568  /* try to generate a flow cover cut for each row in the LP */
2569  ncuts = 0;
2570  if( maxtries < 0 )
2571  maxtries = INT_MAX;
2572  if( maxfails < 0 )
2573  maxfails = INT_MAX;
2574  else if( depth == 0 && 2*SCIPgetNSepaRounds(scip) < maxfails )
2575  maxfails += maxfails - 2*SCIPgetNSepaRounds(scip); /* allow up to double as many fails in early separounds of root node */
2576  ntries = 0;
2577  nfails = 0;
2578  for( r = 0; r < nrows && ntries < maxtries && ncuts < maxsepacuts && rowscores[roworder[r]] > 0.0
2579  && !SCIPisStopped(scip); r++ )
2580  {
2581  SCIP_Bool wastried;
2582  int oldncuts;
2583  SCIP_Real rowact;
2584  SCIP_Real mult;
2585 
2586  oldncuts = ncuts;
2587  wastried = FALSE;
2588 
2589  /* update weight of rows for aggregation in c-MIR routine; all rows but current one have weight 0.0 */
2590  if( r > 0 )
2591  {
2592  assert(rowweights[roworder[r-1]] == 1.0 || rowweights[roworder[r-1]] == -1.0 || rowweights[roworder[r-1]] == 0.0);
2593  rowweights[roworder[r-1]] = 0.0;
2594  }
2595 
2596  /* decide which side of the row should be used */
2597  rowact = SCIPgetRowSolActivity(scip, rows[roworder[r]], sol);
2598  if( !SCIPisInfinity(scip, -SCIProwGetLhs(rows[roworder[r]]))
2599  && rowact < 0.5 * SCIProwGetLhs(rows[roworder[r]]) + 0.5 * SCIProwGetRhs(rows[roworder[r]]) )
2600  rowweights[roworder[r]] = -1.0;
2601  else if( !SCIPisInfinity(scip, SCIProwGetRhs(rows[roworder[r]])) )
2602  rowweights[roworder[r]] = 1.0;
2603  else
2604  {
2605  SCIPdebugMsg(scip, "skipping unconstrained row\n");
2606  rowweights[roworder[r]] = 0.0;
2607  continue;
2608  }
2609 
2610  SCIPdebugMsg(scip, "===================== flow cover separation for row <%s> (%d of %d) ===================== \n",
2611  SCIProwGetName(rows[roworder[r]]), r, nrows);
2612  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, rows[roworder[r]], NULL) ) );
2613  SCIPdebugMsg(scip, "rowact=%g is closer to %s --> rowweight=%g\n", rowact, rowweights[roworder[r]] == 1 ? "rhs" : "lhs", rowweights[roworder[r]]);
2614 
2615  mult = 1.0;
2616  do
2617  {
2618  assert(mult == 1.0 || (mult == -1.0 && sepadata->multbyminusone));
2619 
2620  /* construct 0-1 single node flow relaxation (with some additional simple constraints) of the mixed integer set
2621  * corresponding to the current row
2622  * sum_{j in N} a_j x_j + sum_{j in M} c_j y_j + s = rhs + const or
2623  * - ( sum_{j in N} a_j x_j + sum_{j in M} c_j y_j ) + s = - ( lhs - const )
2624  * multiplied by mult in { +1, -1 }
2625  */
2626  SCIP_CALL( constructSNFRelaxation(scip, vars, nvars, varsolvals, rows[roworder[r]], rowweights[roworder[r]],
2627  mult, boundsfortrans, boundtypesfortrans, assoctransvars, transvarcoefs, transbinvarsolvals,
2628  transcontvarsolvals, transvarvubcoefs, &ntransvars, &transcapacity, &transsuccess) );
2629  if( !transsuccess )
2630  {
2631  /* transformation will fail for mult = -1, too */
2632  SCIPdebugMsg(scip, "mult=%g: no 0-1 single node flow relaxation found\n", mult);
2633  break;
2634  }
2635 
2636  flowcoverfound = FALSE;
2637 
2638  /* get a flow cover (C1, C2) for the constructed 0-1 single node flow set */
2639  SCIP_CALL( getFlowCover(scip, transvarcoefs, transbinvarsolvals, transvarvubcoefs, ntransvars, transcapacity,
2640  &ncovervars, &nnoncovervars, transvarflowcoverstatus, &lambda, &flowcoverfound) );
2641  if( !flowcoverfound )
2642  {
2643  SCIPdebugMsg(scip, "mult=%g: no flow cover found\n", mult);
2644  mult *= -1.0;
2645  continue;
2646  }
2647  assert(SCIPisFeasGT(scip, lambda, 0.0));
2648 
2649  /* generate most violated c-MIRFCI for different sets L1 and L2 and different values of delta and add it to the LP */
2650  SCIP_CALL( cutGenerationHeuristic(scip, sepa, sepadata, vars, nvars, sol, varsolvals, rowweights, mult, boundsfortrans,
2651  boundtypesfortrans, assoctransvars, ntransvars, transvarcoefs, transbinvarsolvals, transcontvarsolvals,
2652  transvarvubcoefs, transvarflowcoverstatus, lambda, normtype, &cutoff, &ncuts) );
2653 
2654  wastried = TRUE;
2655  mult *= -1.0;
2656 
2657  if ( cutoff )
2658  break;
2659  }
2660  while( sepadata->multbyminusone && mult < 0.0 );
2661 
2662  if ( cutoff )
2663  break;
2664 
2665  if( !wastried )
2666  continue;
2667 
2668  ntries++;
2669  if( ncuts == oldncuts )
2670  {
2671  nfails++;
2672  if( nfails >= maxfails )
2673  break;
2674  }
2675  else
2676  nfails = 0;
2677  }
2678 
2679  /* free data structures */
2680  SCIPfreeBufferArray(scip, &rowweights);
2681  SCIPfreeBufferArray(scip, &noncovervars);
2682  SCIPfreeBufferArray(scip, &covervars);
2683  SCIPfreeBufferArray(scip, &boundtypesfortrans);
2684  SCIPfreeBufferArray(scip, &boundsfortrans);
2685  SCIPfreeBufferArray(scip, &transvarflowcoverstatus);
2686  SCIPfreeBufferArray(scip, &transcontvarsolvals);
2687  SCIPfreeBufferArray(scip, &transbinvarsolvals);
2688  SCIPfreeBufferArray(scip, &transvarvubcoefs);
2689  SCIPfreeBufferArray(scip, &transvarcoefs);
2690  SCIPfreeBufferArray(scip, &assoctransvars);
2691  SCIPfreeBufferArray(scip, &varsolvals);
2692  SCIPfreeBufferArray(scip, &roworder);
2693  SCIPfreeBufferArray(scip, &rowscores);
2694  SCIPfreeBufferArray(scip, &rowrhsscores);
2695  SCIPfreeBufferArray(scip, &rowlhsscores);
2696 
2697  if ( cutoff )
2698  *result = SCIP_CUTOFF;
2699  else if ( ncuts > 0 )
2700  *result = SCIP_SEPARATED;
2701 
2702  return SCIP_OKAY;
2703 }
2704 
2705 
2706 /*
2707  * Callback methods of separator
2708  */
2709 
2710 /** copy method for separator plugins (called when SCIP copies plugins) */
2711 static
2712 SCIP_DECL_SEPACOPY(sepaCopyFlowcover)
2713 { /*lint --e{715}*/
2714  assert(scip != NULL);
2715  assert(sepa != NULL);
2716  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2717 
2718  /* call inclusion method of constraint handler */
2719  SCIP_CALL( SCIPincludeSepaFlowcover(scip) );
2720 
2721  return SCIP_OKAY;
2722 }
2723 
2724 /** destructor of separator to free user data (called when SCIP is exiting) */
2725 static
2726 SCIP_DECL_SEPAFREE(sepaFreeFlowcover)
2727 { /*lint --e{715}*/
2728  SCIP_SEPADATA* sepadata;
2729 
2730  /* free separator data */
2731  sepadata = SCIPsepaGetData(sepa);
2732  assert(sepadata != NULL);
2733 
2734  SCIPfreeBlockMemory(scip, &sepadata);
2735 
2736  SCIPsepaSetData(sepa, NULL);
2737 
2738  return SCIP_OKAY;
2739 }
2740 
2741 
2742 /** LP solution separation method of separator */
2743 static
2744 SCIP_DECL_SEPAEXECLP(sepaExeclpFlowcover)
2745 { /*lint --e{715}*/
2746 
2747  *result = SCIP_DIDNOTRUN;
2748 
2749  /* only call separator, if we are not close to terminating */
2750  if( SCIPisStopped(scip) )
2751  return SCIP_OKAY;
2752 
2753  /* only call separator, if an optimal LP solution is at hand */
2754  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2755  return SCIP_OKAY;
2756 
2757  /* only call separator, if there are fractional variables */
2758  if( SCIPgetNLPBranchCands(scip) == 0 )
2759  return SCIP_OKAY;
2760 
2761  SCIP_CALL( separateCuts(scip, sepa, NULL, result) );
2762 
2763  return SCIP_OKAY;
2764 }
2765 
2766 
2767 /** arbitrary primal solution separation method of separator */
2768 static
2769 SCIP_DECL_SEPAEXECSOL(sepaExecsolFlowcover)
2770 { /*lint --e{715}*/
2771 
2772  *result = SCIP_DIDNOTRUN;
2773 
2774  SCIP_CALL( separateCuts(scip, sepa, sol, result) );
2775 
2776  return SCIP_OKAY;
2777 }
2778 
2779 
2780 /*
2781  * separator specific interface methods
2782  */
2783 
2784 /** creates the flowcover separator and includes it in SCIP */
2785 SCIP_RETCODE SCIPincludeSepaFlowcover(
2786  SCIP* scip /**< SCIP data structure */
2787  )
2788 {
2789  SCIP_SEPADATA* sepadata;
2790  SCIP_SEPA* sepa;
2791 
2792  /* create flowcover separator data */
2793  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
2794 
2795  /* include separator */
2796  SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
2797  SEPA_USESSUBSCIP, SEPA_DELAY,
2798  sepaExeclpFlowcover, sepaExecsolFlowcover,
2799  sepadata) );
2800 
2801  assert(sepa != NULL);
2802 
2803  /* set non-NULL pointers to callback methods */
2804  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyFlowcover) );
2805  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeFlowcover) );
2806 
2807  /* add flow cover cuts separator parameters */
2808  SCIP_CALL( SCIPaddIntParam(scip,
2809  "separating/flowcover/maxrounds",
2810  "maximal number of separation rounds per node (-1: unlimited)",
2811  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
2812  SCIP_CALL( SCIPaddIntParam(scip,
2813  "separating/flowcover/maxroundsroot",
2814  "maximal number of separation rounds in the root node (-1: unlimited)",
2815  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
2816  SCIP_CALL( SCIPaddIntParam(scip,
2817  "separating/flowcover/maxtries",
2818  "maximal number of rows to separate flow cover cuts for per separation round (-1: unlimited)",
2819  &sepadata->maxtries, TRUE, DEFAULT_MAXTRIES, -1, INT_MAX, NULL, NULL) );
2820  SCIP_CALL( SCIPaddIntParam(scip,
2821  "separating/flowcover/maxtriesroot",
2822  "maximal number of rows to separate flow cover cuts for per separation round in the root (-1: unlimited)",
2823  &sepadata->maxtriesroot, TRUE, DEFAULT_MAXTRIESROOT, -1, INT_MAX, NULL, NULL) );
2824  SCIP_CALL( SCIPaddIntParam(scip,
2825  "separating/flowcover/maxfails",
2826  "maximal number of consecutive fails to generate a cut per separation round (-1: unlimited)",
2827  &sepadata->maxfails, TRUE, DEFAULT_MAXFAILS, -1, INT_MAX, NULL, NULL) );
2828  SCIP_CALL( SCIPaddIntParam(scip,
2829  "separating/flowcover/maxfailsroot",
2830  "maximal number of consecutive fails to generate a cut per separation round in the root (-1: unlimited)",
2831  &sepadata->maxfailsroot, TRUE, DEFAULT_MAXFAILSROOT, -1, INT_MAX, NULL, NULL) );
2832  SCIP_CALL( SCIPaddIntParam(scip,
2833  "separating/flowcover/maxsepacuts",
2834  "maximal number of flow cover cuts separated per separation round",
2835  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
2836  SCIP_CALL( SCIPaddIntParam(scip,
2837  "separating/flowcover/maxsepacutsroot",
2838  "maximal number of flow cover cuts separated per separation round in the root",
2839  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
2840  SCIP_CALL( SCIPaddRealParam(scip,
2841  "separating/flowcover/maxslack",
2842  "maximal slack of rows to separate flow cover cuts for",
2843  &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2844  SCIP_CALL( SCIPaddRealParam(scip,
2845  "separating/flowcover/maxslackroot",
2846  "maximal slack of rows to separate flow cover cuts for in the root",
2847  &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2848  SCIP_CALL( SCIPaddRealParam(scip,
2849  "separating/flowcover/slackscore",
2850  "weight of slack in the scoring of the rows",
2851  &sepadata->slackscore, TRUE, DEFAULT_SLACKSCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2852  SCIP_CALL( SCIPaddRealParam(scip,
2853  "separating/flowcover/maxrowdensity",
2854  "maximal density of row to separate flow cover cuts for",
2855  &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) );
2856  SCIP_CALL( SCIPaddBoolParam(scip,
2857  "separating/flowcover/dynamiccuts",
2858  "should generated cuts be removed from the LP if they are no longer tight?",
2859  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
2860  SCIP_CALL( SCIPaddBoolParam(scip,
2861  "separating/flowcover/multbyminusone",
2862  "should flow cover cuts be separated for 0-1 single node flow set with reversed arcs in addition?",
2863  &sepadata->multbyminusone, TRUE, DEFAULT_MULTBYMINUSONE, NULL, NULL) );
2864  SCIP_CALL( SCIPaddIntParam(scip,
2865  "separating/flowcover/maxtestdelta",
2866  "cut generation heuristic: maximal number of different deltas to try",
2867  &sepadata->maxtestdelta, TRUE, DEFAULT_MAXTESTDELTA, 0, INT_MAX, NULL, NULL) );
2868  return SCIP_OKAY;
2869 }
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
DEFAULT_MAXROWDENSITY
#define DEFAULT_MAXROWDENSITY
Definition: sepa_flowcover.c:59
isIntegralScalar
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
Definition: sepa_flowcover.c:1109
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
SCIPgetCharParam
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip.c:4445
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIPvarGetVlbCoefs
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:17380
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45274
SEPA_DESC
#define SEPA_DESC
Definition: sepa_flowcover.c:33
SCIPsolveKnapsackExactly
SCIP_RETCODE SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success)
Definition: cons_knapsack.c:994
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
addCut
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Real *varsolvals, SCIP_Real *cutcoefs, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, char normtype, SCIP_Bool *cutoff, int *ncuts)
Definition: sepa_flowcover.c:1940
DEFAULT_MAXTRIES
#define DEFAULT_MAXTRIES
Definition: sepa_flowcover.c:42
SEPA_DELAY
#define SEPA_DELAY
Definition: sepa_flowcover.c:38
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46099
SCIPsortInd
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
SCIPvarGetNVlbs
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:17358
ALLOWLOCAL
#define ALLOWLOCAL
Definition: sepa_flowcover.c:65
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
MAXDELTA
#define MAXDELTA
Definition: sepa_flowcover.c:73
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
SEPA_NAME
#define SEPA_NAME
Definition: sepa_flowcover.c:32
MINDELTA
#define MINDELTA
Definition: sepa_flowcover.c:72
SCIProwGetName
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16370
SCIP_Var
Definition: struct_var.h:197
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
MAXDYNPROGSPACE
#define MAXDYNPROGSPACE
Definition: sepa_flowcover.c:75
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:16246
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16311
FALSE
#define FALSE
Definition: def.h:64
SCIPrelDiff
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:9618
getClosestVlb
static SCIP_RETCODE getClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_Real bestsub, SCIP_Real rowcoef, SCIP_Real *rowcoefsbinary, SCIP_Real *varsolvals, int *assoctransvars, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: sepa_flowcover.c:121
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:45888
DEFAULT_DYNAMICCUTS
#define DEFAULT_DYNAMICCUTS
Definition: sepa_flowcover.c:60
TRUE
#define TRUE
Definition: def.h:63
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:632
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPvarGetNVubs
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:17400
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16859
SCIPcalcMIR
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
Definition: scip.c:29473
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIPvarGetVlbVars
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:17370
SCIP_SEPARATED
Definition: type_result.h:40
sepa_flowcover.h
flowcover separator
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
SCIP_Sepa
Definition: struct_sepa.h:37
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36161
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7367
SCIProwGetDualsol
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16331
SCIPdebugMsgPrint
#define SCIPdebugMsgPrint
Definition: scip.h:452
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:451
SCIPaddIntParam
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.c:4202
SCIPincludeSepaFlowcover
SCIP_RETCODE SCIPincludeSepaFlowcover(SCIP *scip)
Definition: sepa_flowcover.c:2789
SCIPgetObjNorm
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition: scip.c:11284
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:45246
SCIPgetRowMaxCoef
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30491
SCIPsepaGetData
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:543
SCIP_Col
Definition: struct_lp.h:124
SCIP_Sol
Definition: struct_sol.h:51
DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS
Definition: sepa_flowcover.c:40
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
MAXFRAC
#define MAXFRAC
Definition: sepa_flowcover.c:69
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_flowcover.c:35
DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_flowcover.c:41
SCIPisCutEfficacious
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33761
cons_knapsack.h
Constraint handler for knapsack constraints of the form , x binary and .
getClosestVub
static SCIP_RETCODE getClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_Real bestslb, SCIP_Real rowcoef, SCIP_Real *rowcoefsbinary, SCIP_Real *varsolvals, int *assoctransvars, SCIP_Real *closestvub, int *closestvubidx)
Definition: sepa_flowcover.c:239
BOUNDSWITCH
#define BOUNDSWITCH
Definition: sepa_flowcover.c:64
calcEfficacy
static SCIP_Real calcEfficacy(int nvars, SCIP_Real *cutcoefs, SCIP_Real cutrhs, SCIP_Real cutact)
Definition: sepa_flowcover.c:2044
DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS
Definition: sepa_flowcover.c:54
SCIPgetRowMinCoef
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30473
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpFlowcover)
Definition: sepa_flowcover.c:2748
DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_flowcover.c:55
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
MAKECONTINTEGRAL
#define MAKECONTINTEGRAL
Definition: sepa_cgmip.c:138
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38044
DEFAULT_MULTBYMINUSONE
#define DEFAULT_MULTBYMINUSONE
Definition: sepa_flowcover.c:62
SCIProwIsLocal
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16420
SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:47
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:759
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:33779
getBoundsForSubstitution
static SCIP_RETCODE getBoundsForSubstitution(SCIP *scip, SCIP_VAR **vars, int nvars, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *assoctransvars, int *transvarcoefs, int *flowcoverstatus, int ntransvars, int *boundsforsubst, SCIP_BOUNDTYPE *boundtypesforsubst)
Definition: sepa_flowcover.c:1728
MINFRAC
#define MINFRAC
Definition: sepa_flowcover.c:68
MAXDNOM
#define MAXDNOM
Definition: sepa_flowcover.c:71
SCIP_DECL_SEPAEXECSOL
static SCIP_DECL_SEPAEXECSOL(sepaExecsolFlowcover)
Definition: sepa_flowcover.c:2773
storeCutInArrays
static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
Definition: sepa_flowcover.c:1832
SCIPvarGetVubConstants
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17432
cutGenerationHeuristic
static SCIP_RETCODE cutGenerationHeuristic(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Real *varsolvals, SCIP_Real *rowweights, SCIP_Real scalar, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *assoctransvars, int ntransvars, int *transvarcoefs, SCIP_Real *transbinvarsolvals, SCIP_Real *transcontvarsolvals, SCIP_Real *transvarvubcoefs, int *transvarflowcoverstatus, SCIP_Real lambda, char normtype, SCIP_Bool *cutoff, int *ncuts)
Definition: sepa_flowcover.c:2065
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
getClosestLb
static void getClosestLb(SCIP *scip, SCIP_VAR *var, SCIP_Bool allowlocal, SCIP_Real *closestlb, int *closestlbtype)
Definition: sepa_flowcover.c:352
SCIPsepaSetData
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:553
NULL
#define NULL
Definition: lpi_spx1.cpp:137
buildFlowCover
static void buildFlowCover(SCIP *scip, int *coefs, SCIP_Real *vubcoefs, SCIP_Real rhs, int *solitems, int *nonsolitems, int nsolitems, int nnonsolitems, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *flowcoverweight, SCIP_Real *lambda)
Definition: sepa_flowcover.c:1163
REALABS
#define REALABS(x)
Definition: def.h:159
SCIP_OKAY
Definition: type_retcode.h:33
getIntegralVal
static SCIP_Longint getIntegralVal(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
Definition: sepa_flowcover.c:1134
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:306
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIPvarGetVlbConstants
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17390
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIPvarGetVubCoefs
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:17422
MAXABSVBCOEF
#define MAXABSVBCOEF
Definition: sepa_flowcover.c:78
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition: sepa_flowcover.c:34
SCIPaddCut
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33869
SCIP_DECL_SEPAFREE
static SCIP_DECL_SEPAFREE(sepaFreeFlowcover)
Definition: sepa_flowcover.c:2730
getFlowCover
static SCIP_RETCODE getFlowCover(SCIP *scip, int *coefs, SCIP_Real *solvals, SCIP_Real *vubcoefs, int nvars, SCIP_Real rhs, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
Definition: sepa_flowcover.c:1239
getClosestUb
static void getClosestUb(SCIP *scip, SCIP_VAR *var, SCIP_Bool allowlocal, SCIP_Real *closestub, int *closestubtype)
Definition: sepa_flowcover.c:385
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16257
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
SCIPincludeSepaBasic
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip.c:7325
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16267
pub_misc.h
public data structures and miscellaneous methods
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyFlowcover)
Definition: sepa_flowcover.c:2716
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
getL1L2
static void getL1L2(SCIP *scip, int ntransvars, int *transvarcoefs, SCIP_Real *transbinvarsolvals, SCIP_Real *transcontvarsolvals, SCIP_Real *transvarvubcoefs, int *transvarflowcoverstatus, SCIP_Real delta, SCIP_Real lambda)
Definition: sepa_flowcover.c:1621
SCIPisSumLE
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
DEFAULT_MAXSLACKROOT
#define DEFAULT_MAXSLACKROOT
Definition: sepa_flowcover.c:57
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_Row
Definition: struct_lp.h:190
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:33964
SCIPcreateEmptyRowSepa
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30051
SCIPgetCutEfficacy
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33738
MAXSCALE
#define MAXSCALE
Definition: sepa_flowcover.c:74
separateCuts
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_flowcover.c:2370
BMScopyMemoryArray
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:89
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIPgetRowSolActivity
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip.c:30713
SCIP_DECL_SORTINDCOMP
static SCIP_DECL_SORTINDCOMP(rowScoreComp)
Definition: sepa_flowcover.c:2350
SCIProwGetRank
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16400
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:136
SCIP_REAL_MIN
#define SCIP_REAL_MIN
Definition: def.h:137
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16277
DENSSCORE
#define DENSSCORE
Definition: sepa_flowcover.c:66
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30160
SCIPsetSepaFree
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7383
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:45900
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition: sepa_flowcover.c:36
SCIPselectWeightedDownRealRealInt
void SCIPselectWeightedDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16081
FIXINTEGRALRHS
#define FIXINTEGRALRHS
Definition: sepa_flowcover.c:70
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16533
constructSNFRelaxation
static SCIP_RETCODE constructSNFRelaxation(SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_Real *varsolvals, SCIP_ROW *row, SCIP_Real rowweight, SCIP_Real scale, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *assoctransvars, int *transvarcoefs, SCIP_Real *transbinvarsolvals, SCIP_Real *transcontvarsolvals, SCIP_Real *transvarvubcoefs, int *ntransvars, SCIP_Real *transrhs, SCIP_Bool *success)
Definition: sepa_flowcover.c:425
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:48
SCIPgetVars
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
SCIPsolveKnapsackApproximatelyLT
static SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT(SCIP *scip, int nitems, SCIP_Real *weights, SCIP_Real *profits, SCIP_Real capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
Definition: sepa_flowcover.c:1016
SCIProwGetLPPos
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:16500
SCIP_Real
#define SCIP_Real
Definition: def.h:135
SCIPaddVarsToRow
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:30314
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
MIN
#define MIN(x, y)
Definition: memory.c:75
DEFAULT_MAXTESTDELTA
#define DEFAULT_MAXTESTDELTA
Definition: sepa_flowcover.c:61
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30762
SCIPvarGetVubVars
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:17412
SCIP_Longint
#define SCIP_Longint
Definition: def.h:120
SCIPcalcIntegralScalar
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
Definition: misc.c:8237
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
SCIPgetLPRowsData
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29165
SCIP_INVALIDDATA
Definition: type_retcode.h:43
DEFAULT_MAXSLACK
#define DEFAULT_MAXSLACK
Definition: sepa_flowcover.c:56
SCIPgetNLPs
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41363
DEFAULT_MAXTRIESROOT
#define DEFAULT_MAXTRIESROOT
Definition: sepa_flowcover.c:45
MAXAGGRLEN
#define MAXAGGRLEN(nvars)
Definition: sepa_flowcover.c:77
SCIPmakeRowIntegral
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition: scip.c:30431
SCIProwGetNorm
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16287
SCIPaddRealParam
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.c:4258
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
SCIP_CUTOFF
Definition: type_result.h:39
SCIP_SEPADATA
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition: sepa_flowcover.c:37
SCIPaddBoolParam
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.c:4176
SCIPgetNSepaRounds
int SCIPgetNSepaRounds(SCIP *scip)
Definition: scip.c:41933
SCIPvarIsActive
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839
DEFAULT_MAXFAILSROOT
#define DEFAULT_MAXFAILSROOT
Definition: sepa_flowcover.c:51
DEFAULT_SLACKSCORE
#define DEFAULT_SLACKSCORE
Definition: sepa_flowcover.c:58
DEFAULT_MAXFAILS
#define DEFAULT_MAXFAILS
Definition: sepa_flowcover.c:48
MAXBOUND
#define MAXBOUND
Definition: sepa_flowcover.c:79
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58