Scippy

SCIP

Solving Constraint Integer Programs

cons_knapsack.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-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_knapsack.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief Constraint handler for knapsack constraints of the form \f$a^T x \le b\f$, x binary and \f$a \ge 0\f$.
19  * @author Tobias Achterberg
20  * @author Xin Liu
21  * @author Kati Wolter
22  * @author Michael Winkler
23  * @author Tobias Fischer
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include "blockmemshell/memory.h"
29 #include "scip/cons_knapsack.h"
30 #include "scip/cons_linear.h"
31 #include "scip/cons_logicor.h"
32 #include "scip/cons_setppc.h"
33 #include "scip/pub_cons.h"
34 #include "scip/pub_event.h"
35 #include "scip/pub_implics.h"
36 #include "scip/pub_lp.h"
37 #include "scip/pub_message.h"
38 #include "scip/pub_misc.h"
39 #include "scip/pub_misc_select.h"
40 #include "scip/pub_misc_sort.h"
41 #include "scip/pub_sepa.h"
42 #include "scip/pub_var.h"
43 #include "scip/scip_branch.h"
44 #include "scip/scip_conflict.h"
45 #include "scip/scip_cons.h"
46 #include "scip/scip_copy.h"
47 #include "scip/scip_cut.h"
48 #include "scip/scip_event.h"
49 #include "scip/scip_general.h"
50 #include "scip/scip_lp.h"
51 #include "scip/scip_mem.h"
52 #include "scip/scip_message.h"
53 #include "scip/scip_nlp.h"
54 #include "scip/scip_numerics.h"
55 #include "scip/scip_param.h"
56 #include "scip/scip_prob.h"
57 #include "scip/scip_probing.h"
58 #include "scip/scip_sol.h"
59 #include "scip/scip_solvingstats.h"
60 #include "scip/scip_tree.h"
61 #include "scip/scip_var.h"
62 #include <ctype.h>
63 #include <string.h>
64 
65 #ifdef WITH_CARDINALITY_UPGRADE
66 #include "scip/cons_cardinality.h"
67 #endif
68 
69 /* constraint handler properties */
70 #define CONSHDLR_NAME "knapsack"
71 #define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"
72 #define CONSHDLR_SEPAPRIORITY +600000 /**< priority of the constraint handler for separation */
73 #define CONSHDLR_ENFOPRIORITY -600000 /**< priority of the constraint handler for constraint enforcing */
74 #define CONSHDLR_CHECKPRIORITY -600000 /**< priority of the constraint handler for checking feasibility */
75 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
76 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
77 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
78  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
79 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
80 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
81 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
82 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
83 
84 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
85 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
86 
87 #define EVENTHDLR_NAME "knapsack"
88 #define EVENTHDLR_DESC "bound change event handler for knapsack constraints"
89 #define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \
90  | SCIP_EVENTTYPE_UBTIGHTENED \
91  | SCIP_EVENTTYPE_VARFIXED \
92  | SCIP_EVENTTYPE_VARDELETED \
93  | SCIP_EVENTTYPE_IMPLADDED /**< variable events that should be caught by the event handler */
94 
95 #define LINCONSUPGD_PRIORITY +100000 /**< priority of the constraint handler for upgrading of linear constraints */
96 
97 #define MAX_USECLIQUES_SIZE 1000 /**< maximal number of items in knapsack where clique information is used */
98 #define MAX_ZEROITEMS_SIZE 10000 /**< maximal number of items to store in the zero list in preprocessing */
99 
100 #define KNAPSACKRELAX_MAXDELTA 0.1 /**< maximal allowed rounding distance for scaling in knapsack relaxation */
101 #define KNAPSACKRELAX_MAXDNOM 1000LL /**< maximal allowed denominator in knapsack rational relaxation */
102 #define KNAPSACKRELAX_MAXSCALE 1000.0 /**< maximal allowed scaling factor in knapsack rational relaxation */
104 #define DEFAULT_SEPACARDFREQ 1 /**< multiplier on separation frequency, how often knapsack cuts are separated */
105 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
106 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
107 #define DEFAULT_MAXSEPACUTS 50 /**< maximal number of cuts separated per separation round */
108 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in the root node */
109 #define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
110  * to best node's dual bound for separating knapsack cuts */
111 #define DEFAULT_DISAGGREGATION TRUE /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
112 #define DEFAULT_SIMPLIFYINEQUALITIES TRUE/**< should presolving try to simplify knapsacks */
113 #define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in solving process */
115 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for knapsack relaxation */
116 #define USESUPADDLIFT FALSE /**< should lifted minimal cover inequalities using superadditive up-lifting be separated in addition */
118 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
119 #define HASHSIZE_KNAPSACKCONS 500 /**< minimal size of hash table in linear constraint tables */
121 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
122 #define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
123 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
124  * comparison round */
125 #define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving steps be performed? */
126 #define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
127  * function defining an upper bound and prevent these constraints from
128  * entering the LP */
129 #define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
130  * function defining a lower bound and prevent these constraints from
131  * entering the LP */
132 #define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 /**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
133 #define MAXCOVERSIZEITERLEWI 1000 /**< maximal size for which LEWI are iteratively separated by reducing the feasible set */
135 #define DEFAULT_USEGUBS FALSE /**< should GUB information be used for separation? */
136 #define GUBCONSGROWVALUE 6 /**< memory growing value for GUB constraint array */
137 #define GUBSPLITGNC1GUBS FALSE /**< should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss? */
138 #define DEFAULT_CLQPARTUPDATEFAC 1.5 /**< factor on the growth of global cliques to decide when to update a previous
139  * (negated) clique partition (used only if updatecliquepartitions is set to TRUE) */
140 #define DEFAULT_UPDATECLIQUEPARTITIONS FALSE /**< should clique partition information be updated when old partition seems outdated? */
141 #define MAXNCLIQUEVARSCOMP 1000000 /**< limit on number of pairwise comparisons in clique partitioning algorithm */
142 #ifdef WITH_CARDINALITY_UPGRADE
143 #define DEFAULT_UPGDCARDINALITY FALSE /**< if TRUE then try to update knapsack constraints to cardinality constraints */
144 #endif
146 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
147 
148 /*
149  * Data structures
150  */
151 
152 /** constraint handler data */
153 struct SCIP_ConshdlrData
154 {
155  int* ints1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
156  * you have to clear it at the end, exists only in presolving stage */
157  int* ints2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
158  * you have to clear it at the end, exists only in presolving stage */
159  SCIP_Longint* longints1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
160  * you have to clear it at the end, exists only in presolving stage */
161  SCIP_Longint* longints2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
162  * you have to clear it at the end, exists only in presolving stage */
163  SCIP_Bool* bools1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
164  * you have to clear it at the end, exists only in presolving stage */
165  SCIP_Bool* bools2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
166  * you have to clear it at the end, exists only in presolving stage */
167  SCIP_Bool* bools3; /**< cleared memory array, all entries are set to zero in initpre, if you use this
168  * you have to clear it at the end, exists only in presolving stage */
169  SCIP_Bool* bools4; /**< cleared memory array, all entries are set to zero in initpre, if you use this
170  * you have to clear it at the end, exists only in presolving stage */
171  SCIP_Real* reals1; /**< cleared memory array, all entries are set to zero in consinit, if you use this
172  * you have to clear it at the end */
173  int ints1size; /**< size of ints1 array */
174  int ints2size; /**< size of ints2 array */
175  int longints1size; /**< size of longints1 array */
176  int longints2size; /**< size of longints2 array */
177  int bools1size; /**< size of bools1 array */
178  int bools2size; /**< size of bools2 array */
179  int bools3size; /**< size of bools3 array */
180  int bools4size; /**< size of bools4 array */
181  int reals1size; /**< size of reals1 array */
182  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
183  SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared
184  * to best node's dual bound for separating knapsack cuts */
185  int sepacardfreq; /**< multiplier on separation frequency, how often knapsack cuts are separated */
186  int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
187  int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
188  int maxsepacuts; /**< maximal number of cuts separated per separation round */
189  int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */
190  SCIP_Bool disaggregation; /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
191  SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
192  SCIP_Bool negatedclique; /**< should negated clique information be used in solving process */
193  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
194  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
195  SCIP_Bool dualpresolving; /**< should dual presolving steps be performed? */
196  SCIP_Bool usegubs; /**< should GUB information be used for separation? */
197  SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective
198  * function defining an upper bound and prevent these constraints from
199  * entering the LP */
200  SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective
201  * function defining a lower bound and prevent these constraints from
202  * entering the LP */
203  SCIP_Bool updatecliquepartitions; /**< should clique partition information be updated when old partition seems outdated? */
204  SCIP_Real cliqueextractfactor;/**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
205  SCIP_Real clqpartupdatefac; /**< factor on the growth of global cliques to decide when to update a previous
206  * (negated) clique partition (used only if updatecliquepartitions is set to TRUE) */
207 #ifdef WITH_CARDINALITY_UPGRADE
208  SCIP_Bool upgdcardinality; /**< if TRUE then try to update knapsack constraints to cardinality constraints */
209  SCIP_Bool upgradedcard; /**< whether we have already upgraded knapsack constraints to cardinality constraints */
210 #endif
211 };
212 
213 
214 /** constraint data for knapsack constraints */
215 struct SCIP_ConsData
216 {
217  SCIP_VAR** vars; /**< variables in knapsack constraint */
218  SCIP_Longint* weights; /**< weights of variables in knapsack constraint */
219  SCIP_EVENTDATA** eventdata; /**< event data for bound change events of the variables */
220  int* cliquepartition; /**< clique indices of the clique partition */
221  int* negcliquepartition; /**< clique indices of the negated clique partition */
222  SCIP_ROW* row; /**< corresponding LP row */
223  SCIP_NLROW* nlrow; /**< corresponding NLP row */
224  int nvars; /**< number of variables in knapsack constraint */
225  int varssize; /**< size of vars, weights, and eventdata arrays */
226  int ncliques; /**< number of cliques in the clique partition */
227  int nnegcliques; /**< number of cliques in the negated clique partition */
228  int ncliqueslastnegpart;/**< number of global cliques the last time a negated clique partition was computed */
229  int ncliqueslastpart; /**< number of global cliques the last time a clique partition was computed */
230  SCIP_Longint capacity; /**< capacity of knapsack */
231  SCIP_Longint weightsum; /**< sum of all weights */
232  SCIP_Longint onesweightsum; /**< sum of weights of variables fixed to one */
233  unsigned int presolvedtiming:5; /**< max level in which the knapsack constraint is already presolved */
234  unsigned int sorted:1; /**< are the knapsack items sorted by weight? */
235  unsigned int cliquepartitioned:1;/**< is the clique partition valid? */
236  unsigned int negcliquepartitioned:1;/**< is the negated clique partition valid? */
237  unsigned int merged:1; /**< are the constraint's equal variables already merged? */
238  unsigned int cliquesadded:1; /**< were the cliques of the knapsack already added to clique table? */
239  unsigned int varsdeleted:1; /**< were variables deleted after last cleanup? */
240  unsigned int existmultaggr:1; /**< does this constraint contain multi-aggregations */
241 };
242 
243 /** event data for bound changes events */
244 struct SCIP_EventData
245 {
246  SCIP_CONS* cons; /**< knapsack constraint to process the bound change for */
247  SCIP_Longint weight; /**< weight of variable */
248  int filterpos; /**< position of event in variable's event filter */
249 };
250 
251 
252 /** data structure to combine two sorting key values */
253 struct sortkeypair
254 {
255  SCIP_Real key1; /**< first sort key value */
256  SCIP_Real key2; /**< second sort key value */
257 };
258 typedef struct sortkeypair SORTKEYPAIR;
259 
260 /** status of GUB constraint */
261 enum GUBVarstatus
262 {
263  GUBVARSTATUS_UNINITIAL = -1, /** unintitialized variable status */
264  GUBVARSTATUS_CAPACITYEXCEEDED = 0, /** variable with weight exceeding the knapsack capacity */
265  GUBVARSTATUS_BELONGSTOSET_R = 1, /** variable in noncovervars R */
266  GUBVARSTATUS_BELONGSTOSET_F = 2, /** variable in noncovervars F */
267  GUBVARSTATUS_BELONGSTOSET_C2 = 3, /** variable in covervars C2 */
268  GUBVARSTATUS_BELONGSTOSET_C1 = 4 /** variable in covervars C1 */
269 };
270 typedef enum GUBVarstatus GUBVARSTATUS;
272 /** status of variable in GUB constraint */
274 {
275  GUBCONSSTATUS_UNINITIAL = -1, /** unintitialized GUB constraint status */
276  GUBCONSSTATUS_BELONGSTOSET_GR = 0, /** all GUB variables are in noncovervars R */
277  GUBCONSSTATUS_BELONGSTOSET_GF = 1, /** all GUB variables are in noncovervars F (and noncovervars R) */
278  GUBCONSSTATUS_BELONGSTOSET_GC2 = 2, /** all GUB variables are in covervars C2 */
279  GUBCONSSTATUS_BELONGSTOSET_GNC1 = 3, /** some GUB variables are in covervars C1, others in noncovervars R or F */
280  GUBCONSSTATUS_BELONGSTOSET_GOC1 = 4 /** all GUB variables are in covervars C1 */
281 };
282 typedef enum GUBConsstatus GUBCONSSTATUS;
284 /** data structure of GUB constraints */
286 {
287  int* gubvars; /**< indices of GUB variables in knapsack constraint */
288  GUBVARSTATUS* gubvarsstatus; /**< status of GUB variables */
289  int ngubvars; /**< number of GUB variables */
290  int gubvarssize; /**< size of gubvars array */
291 };
292 typedef struct SCIP_GUBCons SCIP_GUBCONS;
294 /** data structure of a set of GUB constraints */
296 {
297  SCIP_GUBCONS** gubconss; /**< GUB constraints in GUB set */
298  GUBCONSSTATUS* gubconsstatus; /**< status of GUB constraints */
299  int ngubconss; /**< number of GUB constraints */
300  int nvars; /**< number of variables in knapsack constraint */
301  int* gubconssidx; /**< index of GUB constraint (in gubconss array) of each knapsack variable */
302  int* gubvarsidx; /**< index in GUB constraint (in gubvars array) of each knapsack variable */
303 };
304 typedef struct SCIP_GUBSet SCIP_GUBSET;
306 /*
307  * Local methods
308  */
310 /** comparison method for two sorting key pairs */
311 static
312 SCIP_DECL_SORTPTRCOMP(compSortkeypairs)
313 {
314  SORTKEYPAIR* sortkeypair1 = (SORTKEYPAIR*)elem1;
315  SORTKEYPAIR* sortkeypair2 = (SORTKEYPAIR*)elem2;
316 
317  if( sortkeypair1->key1 < sortkeypair2->key1 )
318  return -1;
319  else if( sortkeypair1->key1 > sortkeypair2->key1 )
320  return +1;
321  else if( sortkeypair1->key2 < sortkeypair2->key2 )
322  return -1;
323  else if( sortkeypair1->key2 > sortkeypair2->key2 )
324  return +1;
325  else
326  return 0;
327 }
328 
329 /** creates event data */
330 static
332  SCIP* scip, /**< SCIP data structure */
333  SCIP_EVENTDATA** eventdata, /**< pointer to store event data */
334  SCIP_CONS* cons, /**< constraint */
335  SCIP_Longint weight /**< weight of variable */
336  )
337 {
338  assert(eventdata != NULL);
340  SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) );
341  (*eventdata)->cons = cons;
342  (*eventdata)->weight = weight;
343 
344  return SCIP_OKAY;
345 }
346 
347 /** frees event data */
348 static
350  SCIP* scip, /**< SCIP data structure */
351  SCIP_EVENTDATA** eventdata /**< pointer to event data */
352  )
353 {
354  assert(eventdata != NULL);
355 
356  SCIPfreeBlockMemory(scip, eventdata);
358  return SCIP_OKAY;
359 }
360 
361 /** sorts items in knapsack with nonincreasing weights */
362 static
363 void sortItems(
364  SCIP_CONSDATA* consdata /**< constraint data */
365  )
366 {
367  assert(consdata != NULL);
368  assert(consdata->nvars == 0 || consdata->vars != NULL);
369  assert(consdata->nvars == 0 || consdata->weights != NULL);
370  assert(consdata->nvars == 0 || consdata->eventdata != NULL);
371  assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
372 
373  if( !consdata->sorted )
374  {
375  int pos;
376  int lastcliquenum;
377  int v;
378 
379  /* sort of five joint arrays of Long/pointer/pointer/ints/ints,
380  * sorted by first array in non-increasing order via sort template */
382  consdata->weights,
383  (void**)consdata->vars,
384  (void**)consdata->eventdata,
385  consdata->cliquepartition,
386  consdata->negcliquepartition,
387  consdata->nvars);
388 
389  v = consdata->nvars - 1;
390  /* sort all items with same weight according to their variable index, used for hash value for fast pairwise comparison of all constraints */
391  while( v >= 0 )
392  {
393  int w = v - 1;
394 
395  while( w >= 0 && consdata->weights[v] == consdata->weights[w] )
396  --w;
397 
398  if( v - w > 1 )
399  {
400  /* sort all corresponding parts of arrays for which the weights are equal by using the variable index */
402  (void**)(&(consdata->vars[w+1])),
403  (void**)(&(consdata->eventdata[w+1])),
404  &(consdata->cliquepartition[w+1]),
405  &(consdata->negcliquepartition[w+1]),
406  SCIPvarComp,
407  v - w);
408  }
409  v = w;
410  }
411 
412  /* we need to make sure that our clique numbers of our normal clique will be in increasing order without gaps */
413  if( consdata->cliquepartitioned )
414  {
415  lastcliquenum = 0;
416 
417  for( pos = 0; pos < consdata->nvars; ++pos )
418  {
419  /* if the clique number in the normal clique at position pos is greater than the last found clique number the
420  * partition is invalid */
421  if( consdata->cliquepartition[pos] > lastcliquenum )
422  {
423  consdata->cliquepartitioned = FALSE;
424  break;
425  }
426  else if( consdata->cliquepartition[pos] == lastcliquenum )
427  ++lastcliquenum;
428  }
429  }
430  /* we need to make sure that our clique numbers of our negated clique will be in increasing order without gaps */
431  if( consdata->negcliquepartitioned )
432  {
433  lastcliquenum = 0;
434 
435  for( pos = 0; pos < consdata->nvars; ++pos )
436  {
437  /* if the clique number in the negated clique at position pos is greater than the last found clique number the
438  * partition is invalid */
439  if( consdata->negcliquepartition[pos] > lastcliquenum )
440  {
441  consdata->negcliquepartitioned = FALSE;
442  break;
443  }
444  else if( consdata->negcliquepartition[pos] == lastcliquenum )
445  ++lastcliquenum;
446  }
447  }
448 
449  consdata->sorted = TRUE;
450  }
451 #ifndef NDEBUG
452  {
453  /* check if the weight array is sorted in a non-increasing way */
454  int i;
455  for( i = 0; i < consdata->nvars-1; ++i )
456  assert(consdata->weights[i] >= consdata->weights[i+1]);
457  }
458 #endif
459 }
460 
461 /** calculates a partition of the variables into cliques */
462 static
464  SCIP* scip, /**< SCIP data structure */
465  SCIP_CONSHDLRDATA* conshdlrdata, /**< knapsack constraint handler data */
466  SCIP_CONSDATA* consdata, /**< constraint data */
467  SCIP_Bool normalclique, /**< Should normal cliquepartition be created? */
468  SCIP_Bool negatedclique /**< Should negated cliquepartition be created? */
469  )
470 {
471  SCIP_Bool ispartitionoutdated;
472  SCIP_Bool isnegpartitionoutdated;
473  assert(consdata != NULL);
474  assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
475 
476  /* rerun eventually if number of global cliques increased considerably since last partition */
477  ispartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->ncliques > 1
478  && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
479 
480  if( normalclique && ( !consdata->cliquepartitioned || ispartitionoutdated ) )
481  {
482  SCIP_CALL( SCIPcalcCliquePartition(scip, consdata->vars, consdata->nvars, consdata->cliquepartition, &consdata->ncliques) );
483  consdata->cliquepartitioned = TRUE;
484  consdata->ncliqueslastpart = SCIPgetNCliques(scip);
485  }
486 
487  /* rerun eventually if number of global cliques increased considerably since last negated partition */
488  isnegpartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->nnegcliques > 1
489  && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
490 
491  if( negatedclique && (!consdata->negcliquepartitioned || isnegpartitionoutdated) )
492  {
493  SCIP_CALL( SCIPcalcNegatedCliquePartition(scip, consdata->vars, consdata->nvars, consdata->negcliquepartition, &consdata->nnegcliques) );
494  consdata->negcliquepartitioned = TRUE;
495  consdata->ncliqueslastnegpart = SCIPgetNCliques(scip);
496  }
497  assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
498  assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
499 
500  return SCIP_OKAY;
501 }
502 
503 /** installs rounding locks for the given variable in the given knapsack constraint */
504 static
506  SCIP* scip, /**< SCIP data structure */
507  SCIP_CONS* cons, /**< knapsack constraint */
508  SCIP_VAR* var /**< variable of constraint entry */
509  )
510 {
511  SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) );
512 
513  return SCIP_OKAY;
514 }
515 
516 /** removes rounding locks for the given variable in the given knapsack constraint */
517 static
519  SCIP* scip, /**< SCIP data structure */
520  SCIP_CONS* cons, /**< knapsack constraint */
521  SCIP_VAR* var /**< variable of constraint entry */
522  )
523 {
524  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, FALSE, TRUE) );
525 
526  return SCIP_OKAY;
527 }
528 
529 /** catches bound change events for variables in knapsack */
530 static
532  SCIP* scip, /**< SCIP data structure */
533  SCIP_CONS* cons, /**< constraint */
534  SCIP_CONSDATA* consdata, /**< constraint data */
535  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
536  )
537 {
538  int i;
540  assert(cons != NULL);
541  assert(consdata != NULL);
542  assert(consdata->nvars == 0 || consdata->vars != NULL);
543  assert(consdata->nvars == 0 || consdata->weights != NULL);
544  assert(consdata->nvars == 0 || consdata->eventdata != NULL);
545 
546  for( i = 0; i < consdata->nvars; i++)
547  {
548  SCIP_CALL( eventdataCreate(scip, &consdata->eventdata[i], cons, consdata->weights[i]) );
549  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[i], EVENTTYPE_KNAPSACK,
550  eventhdlr, consdata->eventdata[i], &consdata->eventdata[i]->filterpos) );
551  }
552 
553  return SCIP_OKAY;
554 }
555 
556 /** drops bound change events for variables in knapsack */
557 static
559  SCIP* scip, /**< SCIP data structure */
560  SCIP_CONSDATA* consdata, /**< constraint data */
561  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
562  )
563 {
564  int i;
565 
566  assert(consdata != NULL);
567  assert(consdata->nvars == 0 || consdata->vars != NULL);
568  assert(consdata->nvars == 0 || consdata->weights != NULL);
569  assert(consdata->nvars == 0 || consdata->eventdata != NULL);
570 
571  for( i = 0; i < consdata->nvars; i++)
572  {
573  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[i], EVENTTYPE_KNAPSACK,
574  eventhdlr, consdata->eventdata[i], consdata->eventdata[i]->filterpos) );
575  SCIP_CALL( eventdataFree(scip, &consdata->eventdata[i]) );
576  }
577 
578  return SCIP_OKAY;
579 }
580 
581 /** ensures, that vars and vals arrays can store at least num entries */
582 static
584  SCIP* scip, /**< SCIP data structure */
585  SCIP_CONSDATA* consdata, /**< knapsack constraint data */
586  int num, /**< minimum number of entries to store */
587  SCIP_Bool transformed /**< is constraint from transformed problem? */
588  )
589 {
590  assert(consdata != NULL);
591  assert(consdata->nvars <= consdata->varssize);
592 
593  if( num > consdata->varssize )
594  {
595  int newsize;
596 
597  newsize = SCIPcalcMemGrowSize(scip, num);
598  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
599  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->varssize, newsize) );
600  if( transformed )
601  {
602  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
603  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->cliquepartition, consdata->varssize, newsize) );
604  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->negcliquepartition, consdata->varssize, newsize) );
605  }
606  else
607  {
608  assert(consdata->eventdata == NULL);
609  assert(consdata->cliquepartition == NULL);
610  assert(consdata->negcliquepartition == NULL);
611  }
612  consdata->varssize = newsize;
613  }
614  assert(num <= consdata->varssize);
615 
616  return SCIP_OKAY;
617 }
618 
619 /** updates all weight sums for fixed and unfixed variables */
620 static
621 void updateWeightSums(
622  SCIP_CONSDATA* consdata, /**< knapsack constraint data */
623  SCIP_VAR* var, /**< variable for this weight */
624  SCIP_Longint weightdelta /**< difference between the old and the new weight of the variable */
625  )
626 {
627  assert(consdata != NULL);
628  assert(var != NULL);
630  consdata->weightsum += weightdelta;
631 
632  if( SCIPvarGetLbLocal(var) > 0.5 )
633  consdata->onesweightsum += weightdelta;
634 
635  assert(consdata->weightsum >= 0);
636  assert(consdata->onesweightsum >= 0);
637 }
638 
639 /** creates knapsack constraint data */
640 static
642  SCIP* scip, /**< SCIP data structure */
643  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
644  int nvars, /**< number of variables in knapsack */
645  SCIP_VAR** vars, /**< variables of knapsack */
646  SCIP_Longint* weights, /**< weights of knapsack items */
647  SCIP_Longint capacity /**< capacity of knapsack */
648  )
649 {
650  int v;
651  SCIP_Longint constant;
652 
653  assert(consdata != NULL);
654 
655  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
656 
657  constant = 0L;
658  (*consdata)->vars = NULL;
659  (*consdata)->weights = NULL;
660  (*consdata)->nvars = 0;
661  if( nvars > 0 )
662  {
663  SCIP_VAR** varsbuffer;
664  SCIP_Longint* weightsbuffer;
665  int k;
666 
667  SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
668  SCIP_CALL( SCIPallocBufferArray(scip, &weightsbuffer, nvars) );
669 
670  k = 0;
671  for( v = 0; v < nvars; ++v )
672  {
673  assert(vars[v] != NULL);
674  assert(SCIPvarIsBinary(vars[v]));
675 
676  /* all weight have to be non negative */
677  assert( weights[v] >= 0 );
678 
679  if( weights[v] > 0 )
680  {
681  /* treat fixed variables as constants if problem compression is enabled */
682  if( SCIPisConsCompressionEnabled(scip) && SCIPvarGetLbGlobal(vars[v]) > SCIPvarGetUbGlobal(vars[v]) - 0.5 )
683  {
684  /* only if the variable is fixed to 1, we add its weight to the constant */
685  if( SCIPvarGetUbGlobal(vars[v]) > 0.5 )
686  constant += weights[v];
687  }
688  else
689  {
690  varsbuffer[k] = vars[v];
691  weightsbuffer[k] = weights[v];
692  ++k;
693  }
694  }
695  }
696  assert(k >= 0);
697  assert(constant >= 0);
698 
699  (*consdata)->nvars = k;
700 
701  /* copy the active variables and weights into the constraint data structure */
702  if( k > 0 )
703  {
704  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
705  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->weights, weightsbuffer, k) );
706  }
707 
708  /* free buffer storage */
709  SCIPfreeBufferArray(scip, &weightsbuffer);
710  SCIPfreeBufferArray(scip, &varsbuffer);
711  }
712 
713  (*consdata)->varssize = (*consdata)->nvars;
714  (*consdata)->capacity = capacity - constant;
715  (*consdata)->eventdata = NULL;
716  (*consdata)->cliquepartition = NULL;
717  (*consdata)->negcliquepartition = NULL;
718  (*consdata)->row = NULL;
719  (*consdata)->nlrow = NULL;
720  (*consdata)->weightsum = 0;
721  (*consdata)->onesweightsum = 0;
722  (*consdata)->ncliques = 0;
723  (*consdata)->nnegcliques = 0;
724  (*consdata)->presolvedtiming = 0;
725  (*consdata)->sorted = FALSE;
726  (*consdata)->cliquepartitioned = FALSE;
727  (*consdata)->negcliquepartitioned = FALSE;
728  (*consdata)->ncliqueslastpart = -1;
729  (*consdata)->ncliqueslastnegpart = -1;
730  (*consdata)->merged = FALSE;
731  (*consdata)->cliquesadded = FALSE;
732  (*consdata)->varsdeleted = FALSE;
733  (*consdata)->existmultaggr = FALSE;
734 
735  /* get transformed variables, if we are in the transformed problem */
736  if( SCIPisTransformed(scip) )
737  {
738  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
739 
740  for( v = 0; v < (*consdata)->nvars; v++ )
741  {
742  SCIP_VAR* var = SCIPvarGetProbvar((*consdata)->vars[v]);
743  assert(var != NULL);
744  (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
745  }
746 
747  /* allocate memory for additional data structures */
748  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->eventdata, (*consdata)->nvars) );
749  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cliquepartition, (*consdata)->nvars) );
750  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->negcliquepartition, (*consdata)->nvars) );
751  }
752 
753  /* calculate sum of weights and capture variables */
754  for( v = 0; v < (*consdata)->nvars; ++v )
755  {
756  /* calculate sum of weights */
757  updateWeightSums(*consdata, (*consdata)->vars[v], (*consdata)->weights[v]);
758 
759  /* capture variables */
760  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
761  }
762  return SCIP_OKAY;
763 }
764 
765 /** frees knapsack constraint data */
766 static
768  SCIP* scip, /**< SCIP data structure */
769  SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
770  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
771  )
772 {
773  assert(consdata != NULL);
774  assert(*consdata != NULL);
776  if( (*consdata)->row != NULL )
777  {
778  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
779  }
780  if( (*consdata)->nlrow != NULL )
781  {
782  SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
783  }
784  if( (*consdata)->eventdata != NULL )
785  {
786  SCIP_CALL( dropEvents(scip, *consdata, eventhdlr) );
787  SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventdata, (*consdata)->varssize);
788  }
789  if( (*consdata)->negcliquepartition != NULL )
790  {
791  SCIPfreeBlockMemoryArray(scip, &(*consdata)->negcliquepartition, (*consdata)->varssize);
792  }
793  if( (*consdata)->cliquepartition != NULL )
794  {
795  SCIPfreeBlockMemoryArray(scip, &(*consdata)->cliquepartition, (*consdata)->varssize);
796  }
797  if( (*consdata)->vars != NULL )
798  {
799  int v;
800 
801  /* release variables */
802  for( v = 0; v < (*consdata)->nvars; v++ )
803  {
804  assert((*consdata)->vars[v] != NULL);
805  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
806  }
807 
808  assert( (*consdata)->weights != NULL );
809  assert( (*consdata)->varssize > 0 );
810  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
811  SCIPfreeBlockMemoryArray(scip, &(*consdata)->weights, (*consdata)->varssize);
812  }
813 
814  SCIPfreeBlockMemory(scip, consdata);
815 
816  return SCIP_OKAY;
817 }
818 
819 /** changes a single weight in knapsack constraint data */
820 static
821 void consdataChgWeight(
822  SCIP_CONSDATA* consdata, /**< knapsack constraint data */
823  int item, /**< item number */
824  SCIP_Longint newweight /**< new weight of item */
825  )
826 {
827  SCIP_Longint oldweight;
828  SCIP_Longint weightdiff;
830  assert(consdata != NULL);
831  assert(0 <= item && item < consdata->nvars);
832 
833  oldweight = consdata->weights[item];
834  weightdiff = newweight - oldweight;
835  consdata->weights[item] = newweight;
836 
837  /* update weight sums for all and fixed variables */
838  updateWeightSums(consdata, consdata->vars[item], weightdiff);
839 
840  if( consdata->eventdata != NULL )
841  {
842  assert(consdata->eventdata[item] != NULL);
843  assert(consdata->eventdata[item]->weight == oldweight);
844  consdata->eventdata[item]->weight = newweight;
845  }
846 
847  consdata->presolvedtiming = 0;
848  consdata->sorted = FALSE;
849 
850  /* recalculate cliques extraction after a weight was increased */
851  if( oldweight < newweight )
852  {
853  consdata->cliquesadded = FALSE;
854  }
855 }
856 
857 /** creates LP row corresponding to knapsack constraint */
858 static
860  SCIP* scip, /**< SCIP data structure */
861  SCIP_CONS* cons /**< knapsack constraint */
862  )
863 {
864  SCIP_CONSDATA* consdata;
865  int i;
866 
867  consdata = SCIPconsGetData(cons);
868  assert(consdata != NULL);
869  assert(consdata->row == NULL);
870 
871  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, cons, SCIPconsGetName(cons),
872  -SCIPinfinity(scip), (SCIP_Real)consdata->capacity,
874 
875  SCIP_CALL( SCIPcacheRowExtensions(scip, consdata->row) );
876  for( i = 0; i < consdata->nvars; ++i )
877  {
878  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vars[i], (SCIP_Real)consdata->weights[i]) );
879  }
880  SCIP_CALL( SCIPflushRowExtensions(scip, consdata->row) );
881 
882  return SCIP_OKAY;
883 }
884 
885 /** adds linear relaxation of knapsack constraint to the LP */
886 static
888  SCIP* scip, /**< SCIP data structure */
889  SCIP_CONS* cons, /**< knapsack constraint */
890  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
891  )
892 {
893  SCIP_CONSDATA* consdata;
894 
895  assert( cutoff != NULL );
896  *cutoff = FALSE;
897 
898  consdata = SCIPconsGetData(cons);
899  assert(consdata != NULL);
900 
901  if( consdata->row == NULL )
902  {
903  SCIP_CALL( createRelaxation(scip, cons) );
904  }
905  assert(consdata->row != NULL);
906 
907  /* insert LP row as cut */
908  if( !SCIProwIsInLP(consdata->row) )
909  {
910  SCIPdebugMsg(scip, "adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT "): ",
911  SCIPconsGetName(cons), consdata->capacity);
912  SCIPdebug( SCIP_CALL(SCIPprintRow(scip, consdata->row, NULL)) );
913  SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, cutoff) );
914  }
915 
916  return SCIP_OKAY;
917 }
918 
919 /** adds knapsack constraint as row to the NLP, if not added yet */
920 static
922  SCIP* scip, /**< SCIP data structure */
923  SCIP_CONS* cons /**< knapsack constraint */
924  )
925 {
926  SCIP_CONSDATA* consdata;
927 
928  assert(SCIPisNLPConstructed(scip));
930  /* skip deactivated, redundant, or local linear constraints (the NLP does not allow for local rows at the moment) */
931  if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
932  return SCIP_OKAY;
933 
934  consdata = SCIPconsGetData(cons);
935  assert(consdata != NULL);
936 
937  if( consdata->nlrow == NULL )
938  {
939  SCIP_Real* coefs;
940  int i;
941 
942  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nvars) );
943  for( i = 0; i < consdata->nvars; ++i )
944  coefs[i] = (SCIP_Real)consdata->weights[i]; /*lint !e613*/
945 
946  SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow, SCIPconsGetName(cons), 0.0,
947  consdata->nvars, consdata->vars, coefs, NULL,
948  -SCIPinfinity(scip), (SCIP_Real)consdata->capacity, SCIP_EXPRCURV_LINEAR) );
949 
950  assert(consdata->nlrow != NULL);
951 
952  SCIPfreeBufferArray(scip, &coefs);
953  }
954 
955  if( !SCIPnlrowIsInNLP(consdata->nlrow) )
956  {
957  SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow) );
958  }
959 
960  return SCIP_OKAY;
961 }
962 
963 /** checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
964 static
966  SCIP* scip, /**< SCIP data structure */
967  SCIP_CONS* cons, /**< constraint to check */
968  SCIP_SOL* sol, /**< solution to check, NULL for current solution */
969  SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
970  SCIP_Bool printreason, /**< Should the reason for the violation be printed? */
971  SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
972  )
973 {
974  SCIP_CONSDATA* consdata;
975 
976  assert(violated != NULL);
977 
978  consdata = SCIPconsGetData(cons);
979  assert(consdata != NULL);
980 
981  SCIPdebugMsg(scip, "checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
982  SCIPconsGetName(cons), (void*)sol, checklprows);
983 
984  *violated = FALSE;
985 
986  if( checklprows || consdata->row == NULL || !SCIProwIsInLP(consdata->row) )
987  {
988  SCIP_Real sum;
989  SCIP_Longint integralsum;
990  SCIP_Bool ishuge;
991  SCIP_Real absviol;
992  SCIP_Real relviol;
993  int v;
994 
995  /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
996  * enforcement
997  */
998  if( sol == NULL )
999  {
1000  SCIP_CALL( SCIPincConsAge(scip, cons) );
1001  }
1002 
1003  sum = 0.0;
1004  integralsum = 0;
1005  /* we perform a more exact comparison if the capacity does not exceed the huge value */
1006  if( SCIPisHugeValue(scip, (SCIP_Real) consdata->capacity) )
1007  {
1008  ishuge = TRUE;
1009 
1010  /* sum over all weight times the corresponding solution value */
1011  for( v = consdata->nvars - 1; v >= 0; --v )
1012  {
1013  assert(SCIPvarIsBinary(consdata->vars[v]));
1014  sum += consdata->weights[v] * SCIPgetSolVal(scip, sol, consdata->vars[v]);
1015  }
1016  }
1017  else
1018  {
1019  ishuge = FALSE;
1020 
1021  /* sum over all weight for which the variable has a solution value of 1 in feastol */
1022  for( v = consdata->nvars - 1; v >= 0; --v )
1023  {
1024  assert(SCIPvarIsBinary(consdata->vars[v]));
1025 
1026  if( SCIPgetSolVal(scip, sol, consdata->vars[v]) > 0.5 )
1027  integralsum += consdata->weights[v];
1028  }
1029  }
1030 
1031  /* calculate constraint violation and update it in solution */
1032  absviol = ishuge ? sum : (SCIP_Real)integralsum;
1033  absviol -= consdata->capacity;
1034  relviol = SCIPrelDiff(absviol + consdata->capacity, (SCIP_Real)consdata->capacity);
1035  if( sol != NULL )
1036  SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);
1037 
1038  if( SCIPisFeasPositive(scip, absviol) )
1039  {
1040  *violated = TRUE;
1041 
1042  /* only reset constraint age if we are in enforcement */
1043  if( sol == NULL )
1044  {
1045  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1046  }
1047 
1048  if( printreason )
1049  {
1050  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
1051 
1052  SCIPinfoMessage(scip, NULL, ";\n");
1053  SCIPinfoMessage(scip, NULL, "violation: the capacity is violated by %.15g\n", absviol);
1054  }
1055  }
1056  }
1057 
1058  return SCIP_OKAY;
1059 }
1060 
1061 /* IDX computes the integer index for the optimal solution array */
1062 #define IDX(j,d) ((j)*(intcap)+(d))
1063 
1064 /** solves knapsack problem in maximization form exactly using dynamic programming;
1065  * if needed, one can provide arrays to store all selected items and all not selected items
1066  *
1067  * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part, as well
1068  *
1069  * @note the algorithm will first compute a greedy solution and terminate
1070  * if the greedy solution is proven to be optimal.
1071  * The dynamic programming algorithm runs with a time and space complexity
1072  * of O(nitems * capacity).
1073  *
1074  * @todo If only the objective is relevant, it is easy to change the code to use only one slice with O(capacity) space.
1075  * There are recursive methods (see the book by Kellerer et al.) that require O(capacity) space, but it remains
1076  * to be checked whether they are faster and whether they can reconstruct the solution.
1077  * Dembo and Hammer (see Kellerer et al. Section 5.1.3, page 126) found a method that relies on a fast probing method.
1078  * This fixes additional elements to 0 or 1 similar to a reduced cost fixing.
1079  * This could be implemented, however, it would be technically a bit cumbersome,
1080  * since one needs the greedy solution and the LP-value for this.
1081  * This is currently only available after the redundant items have already been sorted out.
1082  */
1084  SCIP* scip, /**< SCIP data structure */
1085  int nitems, /**< number of available items */
1086  SCIP_Longint* weights, /**< item weights */
1087  SCIP_Real* profits, /**< item profits */
1088  SCIP_Longint capacity, /**< capacity of knapsack */
1089  int* items, /**< item numbers */
1090  int* solitems, /**< array to store items in solution, or NULL */
1091  int* nonsolitems, /**< array to store items not in solution, or NULL */
1092  int* nsolitems, /**< pointer to store number of items in solution, or NULL */
1093  int* nnonsolitems, /**< pointer to store number of items not in solution, or NULL */
1094  SCIP_Real* solval, /**< pointer to store optimal solution value, or NULL */
1095  SCIP_Bool* success /**< pointer to store if an error occured during solving
1096  * (normally a memory problem) */
1097  )
1098 {
1099  SCIP_RETCODE retcode;
1100  SCIP_Real* tempsort;
1101  SCIP_Real* optvalues;
1102  int intcap;
1103  int d;
1104  int j;
1105  int greedymedianpos;
1106  SCIP_Longint weightsum;
1107  int* myitems;
1108  SCIP_Longint* myweights;
1109  SCIP_Real* realweights;
1110  int* allcurrminweight;
1111  SCIP_Real* myprofits;
1112  int nmyitems;
1113  SCIP_Longint gcd;
1114  SCIP_Longint minweight;
1115  SCIP_Longint maxweight;
1116  int currminweight;
1117  SCIP_Longint greedysolweight;
1118  SCIP_Real greedysolvalue;
1119  SCIP_Real greedyupperbound;
1120  SCIP_Bool eqweights;
1121  SCIP_Bool intprofits;
1122 
1123  assert(weights != NULL);
1124  assert(profits != NULL);
1125  assert(capacity >= 0);
1126  assert(items != NULL);
1127  assert(nitems >= 0);
1128  assert(success != NULL);
1129 
1130  *success = TRUE;
1131 
1132 #ifndef NDEBUG
1133  for( j = nitems - 1; j >= 0; --j )
1134  assert(weights[j] >= 0);
1135 #endif
1136 
1137  SCIPdebugMsg(scip, "Solving knapsack exactly.\n");
1138 
1139  /* initializing solution value */
1140  if( solval != NULL )
1141  *solval = 0.0;
1142 
1143  /* init solution information */
1144  if( solitems != NULL )
1145  {
1146  assert(items != NULL);
1147  assert(nsolitems != NULL);
1148  assert(nonsolitems != NULL);
1149  assert(nnonsolitems != NULL);
1150 
1151  *nnonsolitems = 0;
1152  *nsolitems = 0;
1153  }
1154 
1155  /* allocate temporary memory */
1156  SCIP_CALL( SCIPallocBufferArray(scip, &myweights, nitems) );
1157  SCIP_CALL( SCIPallocBufferArray(scip, &myprofits, nitems) );
1158  SCIP_CALL( SCIPallocBufferArray(scip, &myitems, nitems) );
1159  nmyitems = 0;
1160  weightsum = 0;
1161  minweight = SCIP_LONGINT_MAX;
1162  maxweight = 0;
1163 
1164  /* remove unnecessary items */
1165  for( j = 0; j < nitems; ++j )
1166  {
1167  assert(0 <= weights[j] && weights[j] < SCIP_LONGINT_MAX);
1168 
1169  /* item does not fit */
1170  if( weights[j] > capacity )
1171  {
1172  if( solitems != NULL )
1173  nonsolitems[(*nnonsolitems)++] = items[j]; /*lint !e413*/
1174  }
1175  /* item is not profitable */
1176  else if( profits[j] <= 0.0 )
1177  {
1178  if( solitems != NULL )
1179  nonsolitems[(*nnonsolitems)++] = items[j]; /*lint !e413*/
1180  }
1181  /* item always fits */
1182  else if( weights[j] == 0 )
1183  {
1184  if( solitems != NULL )
1185  solitems[(*nsolitems)++] = items[j]; /*lint !e413*/
1186 
1187  if( solval != NULL )
1188  *solval += profits[j];
1189  }
1190  /* all important items */
1191  else
1192  {
1193  myweights[nmyitems] = weights[j];
1194  myprofits[nmyitems] = profits[j];
1195  myitems[nmyitems] = items[j];
1196 
1197  /* remember smallest item */
1198  if( myweights[nmyitems] < minweight )
1199  minweight = myweights[nmyitems];
1200 
1201  /* remember bigest item */
1202  if( myweights[nmyitems] > maxweight )
1203  maxweight = myweights[nmyitems];
1204 
1205  weightsum += myweights[nmyitems];
1206  ++nmyitems;
1207  }
1208  }
1209 
1210  intprofits = TRUE;
1211  /* check if all profits are integer to strengthen the upper bound on the greedy solution */
1212  for( j = 0; j < nmyitems && intprofits; ++j )
1213  intprofits = intprofits && SCIPisIntegral(scip, myprofits[j]);
1214 
1215  /* if no item is left then goto end */
1216  if( nmyitems == 0 )
1217  {
1218  SCIPdebugMsg(scip, "After preprocessing no items are left.\n");
1219 
1220  goto TERMINATE;
1221  }
1222 
1223  /* if all items fit, we also do not need to do the expensive stuff later on */
1224  if( weightsum > 0 && weightsum <= capacity )
1225  {
1226  SCIPdebugMsg(scip, "After preprocessing all items fit into knapsack.\n");
1227 
1228  for( j = nmyitems - 1; j >= 0; --j )
1229  {
1230  if( solitems != NULL )
1231  solitems[(*nsolitems)++] = myitems[j]; /*lint !e413*/
1232 
1233  if( solval != NULL )
1234  *solval += myprofits[j];
1235  }
1236 
1237  goto TERMINATE;
1238  }
1239 
1240  assert(0 < minweight && minweight <= capacity );
1241  assert(0 < maxweight && maxweight <= capacity);
1242 
1243  /* make weights relatively prime */
1244  eqweights = TRUE;
1245  if( maxweight > 1 )
1246  {
1247  /* determine greatest common divisor */
1248  gcd = myweights[nmyitems - 1];
1249  for( j = nmyitems - 2; j >= 0 && gcd >= 2; --j )
1250  gcd = SCIPcalcGreComDiv(gcd, myweights[j]);
1251 
1252  SCIPdebugMsg(scip, "Gcd is %" SCIP_LONGINT_FORMAT ".\n", gcd);
1253 
1254  /* divide by greatest common divisor */
1255  if( gcd > 1 )
1256  {
1257  for( j = nmyitems - 1; j >= 0; --j )
1258  {
1259  myweights[j] /= gcd;
1260  eqweights = eqweights && (myweights[j] == 1);
1261  }
1262  capacity /= gcd;
1263  minweight /= gcd;
1264  }
1265  else
1266  eqweights = FALSE;
1267  }
1268  assert(minweight <= capacity);
1269 
1270  /* if only one item fits, then take the best */
1271  if( minweight > capacity / 2 )
1272  {
1273  int p;
1274 
1275  SCIPdebugMsg(scip, "Only one item fits into knapsack, so take the best.\n");
1276 
1277  p = nmyitems - 1;
1278 
1279  /* find best item */
1280  for( j = nmyitems - 2; j >= 0; --j )
1281  {
1282  if( myprofits[j] > myprofits[p] )
1283  p = j;
1284  }
1285 
1286  /* update solution information */
1287  if( solitems != NULL )
1288  {
1289  assert(nsolitems != NULL && nonsolitems != NULL && nnonsolitems != NULL);
1290 
1291  solitems[(*nsolitems)++] = myitems[p];
1292  for( j = nmyitems - 1; j >= 0; --j )
1293  {
1294  if( j != p )
1295  nonsolitems[(*nnonsolitems)++] = myitems[j];
1296  }
1297  }
1298  /* update solution value */
1299  if( solval != NULL )
1300  *solval += myprofits[p];
1301 
1302  goto TERMINATE;
1303  }
1304 
1305  /* if all items have the same weight, then take the best */
1306  if( eqweights )
1307  {
1308  SCIP_Real addval = 0.0;
1309 
1310  SCIPdebugMsg(scip, "All weights are equal, so take the best.\n");
1311 
1312  SCIPsortDownRealIntLong(myprofits, myitems, myweights, nmyitems);
1313 
1314  /* update solution information */
1315  if( solitems != NULL || solval != NULL )
1316  {
1317  SCIP_Longint i;
1318 
1319  /* if all items would fit we had handled this case before */
1320  assert((SCIP_Longint) nmyitems > capacity);
1321  assert(nsolitems != NULL && nonsolitems != NULL && nnonsolitems != NULL);
1322 
1323  /* take the first best items into the solution */
1324  for( i = capacity - 1; i >= 0; --i )
1325  {
1326  if( solitems != NULL )
1327  solitems[(*nsolitems)++] = myitems[i];
1328  addval += myprofits[i];
1329  }
1330 
1331  if( solitems != NULL )
1332  {
1333  /* the rest are not in the solution */
1334  for( i = nmyitems - 1; i >= capacity; --i )
1335  nonsolitems[(*nnonsolitems)++] = myitems[i];
1336  }
1337  }
1338  /* update solution value */
1339  if( solval != NULL )
1340  {
1341  assert(addval > 0.0);
1342  *solval += addval;
1343  }
1344 
1345  goto TERMINATE;
1346  }
1347 
1348  SCIPdebugMsg(scip, "Determine greedy solution.\n");
1349 
1350  /* sort myitems (plus corresponding arrays myweights and myprofits) such that
1351  * p_1/w_1 >= p_2/w_2 >= ... >= p_n/w_n, this is only used for the greedy solution
1352  */
1353  SCIP_CALL( SCIPallocBufferArray(scip, &tempsort, nmyitems) );
1354  SCIP_CALL( SCIPallocBufferArray(scip, &realweights, nmyitems) );
1355 
1356  for( j = 0; j < nmyitems; ++j )
1357  {
1358  tempsort[j] = myprofits[j]/((SCIP_Real) myweights[j]);
1359  realweights[j] = (SCIP_Real)myweights[j];
1360  }
1361 
1362  SCIPselectWeightedDownRealLongRealInt(tempsort, myweights, myprofits, myitems, realweights,
1363  (SCIP_Real)capacity, nmyitems, &greedymedianpos);
1364 
1365  SCIPfreeBufferArray(scip, &realweights);
1366  SCIPfreeBufferArray(scip, &tempsort);
1367 
1368  /* initialize values for greedy solution information */
1369  greedysolweight = 0;
1370  greedysolvalue = 0.0;
1371 
1372  /* determine greedy solution */
1373  for( j = 0; j < greedymedianpos; ++j )
1374  {
1375  assert(myweights[j] <= capacity);
1376 
1377  /* update greedy solution weight and value */
1378  greedysolweight += myweights[j];
1379  greedysolvalue += myprofits[j];
1380  }
1381 
1382  assert(0 < greedysolweight && greedysolweight <= capacity);
1383  assert(greedysolvalue > 0.0);
1384 
1385  /* If the greedy solution is optimal by comparing to the LP solution, we take this solution. This happens if:
1386  * - the greedy solution reaches the capacity, because then the LP solution is integral;
1387  * - the greedy solution has an objective that is at least the LP value rounded down in case that all profits are integer, too. */
1388  greedyupperbound = greedysolvalue + myprofits[j] * (SCIP_Real) (capacity - greedysolweight)/((SCIP_Real) myweights[j]);
1389  if( intprofits )
1390  greedyupperbound = SCIPfloor(scip, greedyupperbound);
1391  if( greedysolweight == capacity || SCIPisGE(scip, greedysolvalue, greedyupperbound) )
1392  {
1393  SCIPdebugMsg(scip, "Greedy solution is optimal.\n");
1394 
1395  /* update solution information */
1396  if( solitems != NULL )
1397  {
1398  int l;
1399 
1400  assert(nsolitems != NULL && nonsolitems != NULL && nnonsolitems != NULL);
1401 
1402  /* collect items */
1403  for( l = 0; l < j; ++l )
1404  solitems[(*nsolitems)++] = myitems[l];
1405  for ( ; l < nmyitems; ++l )
1406  nonsolitems[(*nnonsolitems)++] = myitems[l];
1407  }
1408  /* update solution value */
1409  if( solval != NULL )
1410  {
1411  assert(greedysolvalue > 0.0);
1412  *solval += greedysolvalue;
1413  }
1414 
1415  goto TERMINATE;
1416  }
1417 
1418  /* in the following table we do not need the first minweight columns */
1419  capacity -= (minweight - 1);
1420 
1421  /* we can only handle integers */
1422  if( capacity >= INT_MAX )
1423  {
1424  SCIPdebugMsg(scip, "Capacity is to big, so we cannot handle it here.\n");
1425 
1426  *success = FALSE;
1427  goto TERMINATE;
1428  }
1429  assert(capacity < INT_MAX);
1430 
1431  intcap = (int)capacity;
1432  assert(intcap >= 0);
1433  assert(nmyitems > 0);
1434  assert(sizeof(size_t) >= sizeof(int)); /*lint !e506*/ /* no following conversion should be messed up */
1435 
1436  /* this condition checks whether we will try to allocate a correct number of bytes and do not have an overflow, while
1437  * computing the size for the allocation
1438  */
1439  if( intcap < 0 || (intcap > 0 && (((size_t)nmyitems) > (SIZE_MAX / (size_t)intcap / sizeof(*optvalues)) || ((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues) > ((size_t)INT_MAX) )) ) /*lint !e571*/
1440  {
1441  SCIPdebugMsg(scip, "Too much memory (%lu) would be consumed.\n", (unsigned long) (((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues))); /*lint !e571*/
1442 
1443  *success = FALSE;
1444  goto TERMINATE;
1445  }
1446 
1447  /* allocate temporary memory and check for memory exceedance */
1448  retcode = SCIPallocBufferArray(scip, &optvalues, nmyitems * intcap);
1449  if( retcode == SCIP_NOMEMORY )
1450  {
1451  SCIPdebugMsg(scip, "Did not get enough memory.\n");
1452 
1453  *success = FALSE;
1454  goto TERMINATE;
1455  }
1456  else
1457  {
1458  SCIP_CALL( retcode );
1459  }
1460 
1461  SCIPdebugMsg(scip, "Start real exact algorithm.\n");
1462 
1463  /* we memorize at each step the current minimal weight to later on know which value in our optvalues matrix is valid;
1464  * each value entries of the j-th row of optvalues is valid if the index is >= allcurrminweight[j], otherwise it is
1465  * invalid; a second possibility would be to clear the whole optvalues, which should be more expensive than storing
1466  * 'nmyitem' values
1467  */
1468  SCIP_CALL( SCIPallocBufferArray(scip, &allcurrminweight, nmyitems) );
1469  assert(myweights[0] - minweight < INT_MAX);
1470  currminweight = (int) (myweights[0] - minweight);
1471  allcurrminweight[0] = currminweight;
1472 
1473  /* fills first row of dynamic programming table with optimal values */
1474  for( d = currminweight; d < intcap; ++d )
1475  optvalues[d] = myprofits[0];
1476 
1477  /* fills dynamic programming table with optimal values */
1478  for( j = 1; j < nmyitems; ++j )
1479  {
1480  int intweight;
1481 
1482  /* compute important part of weight, which will be represented in the table */
1483  intweight = (int)(myweights[j] - minweight);
1484  assert(0 <= intweight && intweight < intcap);
1485 
1486  /* copy all nonzeros from row above */
1487  for( d = currminweight; d < intweight && d < intcap; ++d )
1488  optvalues[IDX(j,d)] = optvalues[IDX(j-1,d)];
1489 
1490  /* update corresponding row */
1491  for( d = intweight; d < intcap; ++d )
1492  {
1493  /* if index d < current minweight then optvalues[IDX(j-1,d)] is not initialized, i.e. should be 0 */
1494  if( d < currminweight )
1495  optvalues[IDX(j,d)] = myprofits[j];
1496  else
1497  {
1498  SCIP_Real sumprofit;
1499 
1500  if( d - myweights[j] < currminweight )
1501  sumprofit = myprofits[j];
1502  else
1503  sumprofit = optvalues[IDX(j-1,(int)(d-myweights[j]))] + myprofits[j];
1504 
1505  optvalues[IDX(j,d)] = MAX(sumprofit, optvalues[IDX(j-1,d)]);
1506  }
1507  }
1508 
1509  /* update currminweight */
1510  if( intweight < currminweight )
1511  currminweight = intweight;
1512 
1513  allcurrminweight[j] = currminweight;
1514  }
1515 
1516  /* update optimal solution by following the table */
1517  if( solitems != NULL )
1518  {
1519  assert(nsolitems != NULL && nonsolitems != NULL && nnonsolitems != NULL);
1520  d = intcap - 1;
1521 
1522  SCIPdebugMsg(scip, "Fill the solution vector after solving exactly.\n");
1523 
1524  /* insert all items in (non-) solution vector */
1525  for( j = nmyitems - 1; j > 0; --j )
1526  {
1527  /* if the following condition holds this means all remaining items does not fit anymore */
1528  if( d < allcurrminweight[j] )
1529  {
1530  /* we cannot have exceeded our capacity */
1531  assert((SCIP_Longint) d >= -minweight);
1532  break;
1533  }
1534 
1535  /* collect solution items; the first condition means that no further item can fit anymore, but this does */
1536  if( d < allcurrminweight[j-1] || optvalues[IDX(j,d)] > optvalues[IDX(j-1,d)] )
1537  {
1538  solitems[(*nsolitems)++] = myitems[j];
1539 
1540  /* check that we do not have an underflow */
1541  assert(myweights[j] <= (INT_MAX + (SCIP_Longint) d));
1542  d = (int)(d - myweights[j]);
1543  }
1544  /* collect non-solution items */
1545  else
1546  nonsolitems[(*nnonsolitems)++] = myitems[j];
1547  }
1548 
1549  /* insert remaining items */
1550  if( d >= allcurrminweight[j] )
1551  {
1552  assert(j == 0);
1553  solitems[(*nsolitems)++] = myitems[j];
1554  }
1555  else
1556  {
1557  assert(j >= 0);
1558  assert(d < allcurrminweight[j]);
1559 
1560  for( ; j >= 0; --j )
1561  nonsolitems[(*nnonsolitems)++] = myitems[j];
1562  }
1563 
1564  assert(*nsolitems + *nnonsolitems == nitems);
1565  }
1566 
1567  /* update solution value */
1568  if( solval != NULL )
1569  *solval += optvalues[IDX(nmyitems-1,intcap-1)];
1570  SCIPfreeBufferArray(scip, &allcurrminweight);
1571 
1572  /* free all temporary memory */
1573  SCIPfreeBufferArray(scip, &optvalues);
1574 
1575  TERMINATE:
1576  SCIPfreeBufferArray(scip, &myitems);
1577  SCIPfreeBufferArray(scip, &myprofits);
1578  SCIPfreeBufferArray(scip, &myweights);
1579 
1580  return SCIP_OKAY;
1581 }
1582 
1583 /** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's
1584  * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not
1585  * selected items
1586  */
1588  SCIP* scip, /**< SCIP data structure */
1589  int nitems, /**< number of available items */
1590  SCIP_Longint* weights, /**< item weights */
1591  SCIP_Real* profits, /**< item profits */
1592  SCIP_Longint capacity, /**< capacity of knapsack */
1593  int* items, /**< item numbers */
1594  int* solitems, /**< array to store items in solution, or NULL */
1595  int* nonsolitems, /**< array to store items not in solution, or NULL */
1596  int* nsolitems, /**< pointer to store number of items in solution, or NULL */
1597  int* nnonsolitems, /**< pointer to store number of items not in solution, or NULL */
1598  SCIP_Real* solval /**< pointer to store optimal solution value, or NULL */
1599  )
1600 {
1601  SCIP_Real* tempsort;
1602  SCIP_Longint solitemsweight;
1603  SCIP_Real* realweights;
1604  int j;
1605  int criticalindex;
1606 
1607  assert(weights != NULL);
1608  assert(profits != NULL);
1609  assert(capacity >= 0);
1610  assert(items != NULL);
1611  assert(nitems >= 0);
1612 
1613  if( solitems != NULL )
1614  {
1615  *nsolitems = 0;
1616  *nnonsolitems = 0;
1617  }
1618  if( solval != NULL )
1619  *solval = 0.0;
1620 
1621  /* initialize data for median search */
1622  SCIP_CALL( SCIPallocBufferArray(scip, &tempsort, nitems) );
1623  SCIP_CALL( SCIPallocBufferArray(scip, &realweights, nitems) );
1624  for( j = nitems - 1; j >= 0; --j )
1625  {
1626  tempsort[j] = profits[j]/((SCIP_Real) weights[j]);
1627  realweights[j] = (SCIP_Real)weights[j];
1628  }
1629 
1630  /* partially sort indices such that all elements that are larger than the break item appear first */
1631  SCIPselectWeightedDownRealLongRealInt(tempsort, weights, profits, items, realweights, (SCIP_Real)capacity, nitems, &criticalindex);
1632 
1633  /* selects items as long as they fit into the knapsack */
1634  solitemsweight = 0;
1635  for( j = 0; j < nitems && solitemsweight + weights[j] <= capacity; ++j )
1636  {
1637  if( solitems != NULL )
1638  solitems[(*nsolitems)++] = items[j];
1639 
1640  if( solval != NULL )
1641  (*solval) += profits[j];
1642  solitemsweight += weights[j];
1643  }
1644  if ( solitems != NULL )
1645  {
1646  for( ; j < nitems; j++ )
1647  nonsolitems[(*nnonsolitems)++] = items[j];
1648  }
1649 
1650  SCIPfreeBufferArray(scip, &realweights);
1651  SCIPfreeBufferArray(scip, &tempsort);
1652 
1653  return SCIP_OKAY;
1654 }
1655 
1656 #ifdef SCIP_DEBUG
1657 /** prints all nontrivial GUB constraints and their LP solution values */
1658 static
1659 void GUBsetPrint(
1660  SCIP* scip, /**< SCIP data structure */
1661  SCIP_GUBSET* gubset, /**< GUB set data structure */
1662  SCIP_VAR** vars, /**< variables in knapsack constraint */
1663  SCIP_Real* solvals /**< solution values of variables in knapsack constraint; or NULL */
1664  )
1665 {
1666  int nnontrivialgubconss;
1667  int c;
1668 
1669  nnontrivialgubconss = 0;
1670 
1671  SCIPdebugMsg(scip, " Nontrivial GUBs of current GUB set:\n");
1672 
1673  /* print out all nontrivial GUB constraints, i.e., with more than one variable */
1674  for( c = 0; c < gubset->ngubconss; c++ )
1675  {
1676  SCIP_Real gubsolval;
1677 
1678  assert(gubset->gubconss[c]->ngubvars >= 0);
1679 
1680  /* nontrivial GUB */
1681  if( gubset->gubconss[c]->ngubvars > 1 )
1682  {
1683  int v;
1684 
1685  gubsolval = 0.0;
1686  SCIPdebugMsg(scip, " GUB<%d>:\n", c);
1687 
1688  /* print GUB var */
1689  for( v = 0; v < gubset->gubconss[c]->ngubvars; v++ )
1690  {
1691  int currentvar;
1692 
1693  currentvar = gubset->gubconss[c]->gubvars[v];
1694  if( solvals != NULL )
1695  {
1696  gubsolval += solvals[currentvar];
1697  SCIPdebugMsg(scip, " +<%s>(%4.2f)\n", SCIPvarGetName(vars[currentvar]), solvals[currentvar]);
1698  }
1699  else
1700  {
1701  SCIPdebugMsg(scip, " +<%s>\n", SCIPvarGetName(vars[currentvar]));
1702  }
1703  }
1704 
1705  /* check whether LP solution satisfies the GUB constraint */
1706  if( solvals != NULL )
1707  {
1708  SCIPdebugMsg(scip, " =%4.2f <= 1 %s\n", gubsolval,
1709  SCIPisFeasGT(scip, gubsolval, 1.0) ? "--> violated" : "");
1710  }
1711  else
1712  {
1713  SCIPdebugMsg(scip, " <= 1 %s\n", SCIPisFeasGT(scip, gubsolval, 1.0) ? "--> violated" : "");
1714  }
1715  nnontrivialgubconss++;
1716  }
1717  }
1718 
1719  SCIPdebugMsg(scip, " --> %d/%d nontrivial GUBs\n", nnontrivialgubconss, gubset->ngubconss);
1720 }
1721 #endif
1722 
1723 /** creates an empty GUB constraint */
1724 static
1726  SCIP* scip, /**< SCIP data structure */
1727  SCIP_GUBCONS** gubcons /**< pointer to store GUB constraint data */
1728  )
1729 {
1730  assert(scip != NULL);
1731  assert(gubcons != NULL);
1732 
1733  /* allocate memory for GUB constraint data structures */
1734  SCIP_CALL( SCIPallocBuffer(scip, gubcons) );
1735  (*gubcons)->gubvarssize = GUBCONSGROWVALUE;
1736  SCIP_CALL( SCIPallocBufferArray(scip, &(*gubcons)->gubvars, (*gubcons)->gubvarssize) );
1737  SCIP_CALL( SCIPallocBufferArray(scip, &(*gubcons)->gubvarsstatus, (*gubcons)->gubvarssize) );
1738 
1739  (*gubcons)->ngubvars = 0;
1740 
1741  return SCIP_OKAY;
1742 }
1743 
1744 /** frees GUB constraint */
1745 static
1746 void GUBconsFree(
1747  SCIP* scip, /**< SCIP data structure */
1748  SCIP_GUBCONS** gubcons /**< pointer to GUB constraint data structure */
1749  )
1750 {
1751  assert(scip != NULL);
1752  assert(gubcons != NULL);
1753  assert((*gubcons)->gubvars != NULL);
1754  assert((*gubcons)->gubvarsstatus != NULL);
1755 
1756  /* free allocated memory */
1757  SCIPfreeBufferArray(scip, &(*gubcons)->gubvarsstatus);
1758  SCIPfreeBufferArray(scip, &(*gubcons)->gubvars);
1759  SCIPfreeBuffer(scip, gubcons);
1760 }
1761 
1762 /** adds variable to given GUB constraint */
1763 static
1765  SCIP* scip, /**< SCIP data structure */
1766  SCIP_GUBCONS* gubcons, /**< GUB constraint data */
1767  int var /**< index of given variable in knapsack constraint */
1768  )
1769 {
1770  assert(scip != NULL);
1771  assert(gubcons != NULL);
1772  assert(gubcons->ngubvars >= 0 && gubcons->ngubvars < gubcons->gubvarssize);
1773  assert(gubcons->gubvars != NULL);
1774  assert(gubcons->gubvarsstatus != NULL);
1775  assert(var >= 0);
1776 
1777  /* add variable to GUB constraint */
1778  gubcons->gubvars[gubcons->ngubvars] = var;
1779  gubcons->gubvarsstatus[gubcons->ngubvars] = GUBVARSTATUS_UNINITIAL;
1780  gubcons->ngubvars++;
1781 
1782  /* increase space allocated to GUB constraint if the number of variables reaches the size */
1783  if( gubcons->ngubvars == gubcons->gubvarssize )
1784  {
1785  int newlen;
1786 
1787  newlen = gubcons->gubvarssize + GUBCONSGROWVALUE;
1788  SCIP_CALL( SCIPreallocBufferArray(scip, &gubcons->gubvars, newlen) );
1789  SCIP_CALL( SCIPreallocBufferArray(scip, &gubcons->gubvarsstatus, newlen) );
1790 
1791  gubcons->gubvarssize = newlen;
1792  }
1793 
1794  return SCIP_OKAY;
1795 }
1796 
1797 /** deletes variable from its current GUB constraint */
1798 static
1800  SCIP* scip, /**< SCIP data structure */
1801  SCIP_GUBCONS* gubcons, /**< GUB constraint data */
1802  int var, /**< index of given variable in knapsack constraint */
1803  int gubvarsidx /**< index of the variable in its current GUB constraint */
1804  )
1805 {
1806  assert(scip != NULL);
1807  assert(gubcons != NULL);
1808  assert(var >= 0);
1809  assert(gubvarsidx >= 0 && gubvarsidx < gubcons->ngubvars);
1810  assert(gubcons->ngubvars >= gubvarsidx+1);
1811  assert(gubcons->gubvars[gubvarsidx] == var);
1812 
1813  /* delete variable from GUB by swapping it replacing in by the last variable in the GUB constraint */
1814  gubcons->gubvars[gubvarsidx] = gubcons->gubvars[gubcons->ngubvars-1];
1815  gubcons->gubvarsstatus[gubvarsidx] = gubcons->gubvarsstatus[gubcons->ngubvars-1];
1816  gubcons->ngubvars--;
1817 
1818  /* decrease space allocated for the GUB constraint, if the last GUBCONSGROWVALUE+1 array entries are now empty */
1819  if( gubcons->ngubvars < gubcons->gubvarssize - GUBCONSGROWVALUE && gubcons->ngubvars > 0 )
1820  {
1821  int newlen;
1822 
1823  newlen = gubcons->gubvarssize - GUBCONSGROWVALUE;
1824 
1825  SCIP_CALL( SCIPreallocBufferArray(scip, &gubcons->gubvars, newlen) );
1826  SCIP_CALL( SCIPreallocBufferArray(scip, &gubcons->gubvarsstatus, newlen) );
1827 
1828  gubcons->gubvarssize = newlen;
1829  }
1830 
1831  return SCIP_OKAY;
1832 }
1833 
1834 /** moves variable from current GUB constraint to a different existing (nonempty) GUB constraint */
1835 static
1837  SCIP* scip, /**< SCIP data structure */
1838  SCIP_GUBSET* gubset, /**< GUB set data structure */
1839  SCIP_VAR** vars, /**< variables in knapsack constraint */
1840  int var, /**< index of given variable in knapsack constraint */
1841  int oldgubcons, /**< index of old GUB constraint of given variable */
1842  int newgubcons /**< index of new GUB constraint of given variable */
1843  )
1845  int oldgubvaridx;
1846  int replacevar;
1847  int j;
1848 
1849  assert(scip != NULL);
1850  assert(gubset != NULL);
1851  assert(var >= 0);
1852  assert(oldgubcons >= 0 && oldgubcons < gubset->ngubconss);
1853  assert(newgubcons >= 0 && newgubcons < gubset->ngubconss);
1854  assert(oldgubcons != newgubcons);
1855  assert(gubset->gubconssidx[var] == oldgubcons);
1856  assert(gubset->gubconss[oldgubcons]->ngubvars > 0);
1857  assert(gubset->gubconss[newgubcons]->ngubvars >= 0);
1858 
1859  SCIPdebugMsg(scip, " moving variable<%s> from GUB<%d> to GUB<%d>\n", SCIPvarGetName(vars[var]), oldgubcons, newgubcons);
1860 
1861  oldgubvaridx = gubset->gubvarsidx[var];
1862 
1863  /* delete variable from old GUB constraint by replacing it by the last variable of the GUB constraint */
1864  SCIP_CALL( GUBconsDelVar(scip, gubset->gubconss[oldgubcons], var, oldgubvaridx) );
1865 
1866  /* in GUB set, update stored index of variable in old GUB constraint for the variable used for replacement;
1867  * replacement variable is given by old position of the deleted variable
1868  */
1869  replacevar = gubset->gubconss[oldgubcons]->gubvars[oldgubvaridx];
1870  assert(gubset->gubvarsidx[replacevar] == gubset->gubconss[oldgubcons]->ngubvars);
1871  gubset->gubvarsidx[replacevar] = oldgubvaridx;
1872 
1873  /* add variable to the end of new GUB constraint */
1874  SCIP_CALL( GUBconsAddVar(scip, gubset->gubconss[newgubcons], var) );
1875  assert(gubset->gubconss[newgubcons]->gubvars[gubset->gubconss[newgubcons]->ngubvars-1] == var);
1876 
1877  /* in GUB set, update stored index of GUB of moved variable and stored index of variable in this GUB constraint */
1878  gubset->gubconssidx[var] = newgubcons;
1879  gubset->gubvarsidx[var] = gubset->gubconss[newgubcons]->ngubvars-1;
1880 
1881  /* delete old GUB constraint if it became empty */
1882  if( gubset->gubconss[oldgubcons]->ngubvars == 0 )
1883  {
1884  SCIPdebugMsg(scip, "deleting empty GUB cons<%d> from current GUB set\n", oldgubcons);
1885 #ifdef SCIP_DEBUG
1886  GUBsetPrint(scip, gubset, vars, NULL);
1887 #endif
1888 
1889  /* free old GUB constraint */
1890  GUBconsFree(scip, &gubset->gubconss[oldgubcons]);
1891 
1892  /* if empty GUB was not the last one in GUB set data structure, replace it by last GUB constraint */
1893  if( oldgubcons != gubset->ngubconss-1 )
1894  {
1895  gubset->gubconss[oldgubcons] = gubset->gubconss[gubset->ngubconss-1];
1896  gubset->gubconsstatus[oldgubcons] = gubset->gubconsstatus[gubset->ngubconss-1];
1897 
1898  /* in GUB set, update stored index of GUB constraint for all variable of the GUB constraint used for replacement;
1899  * replacement GUB is given by old position of the deleted GUB
1900  */
1901  for( j = 0; j < gubset->gubconss[oldgubcons]->ngubvars; j++ )
1902  {
1903  assert(gubset->gubconssidx[gubset->gubconss[oldgubcons]->gubvars[j]] == gubset->ngubconss-1);
1904  gubset->gubconssidx[gubset->gubconss[oldgubcons]->gubvars[j]] = oldgubcons;
1905  }
1906  }
1907 
1908  /* update number of GUB constraints */
1909  gubset->ngubconss--;
1910 
1911  /* variable should be at given new position, unless new GUB constraint replaced empty old GUB constraint
1912  * (because it was at the end of the GUB constraint array)
1913  */
1914  assert(gubset->gubconssidx[var] == newgubcons
1915  || (newgubcons == gubset->ngubconss && gubset->gubconssidx[var] == oldgubcons));
1916  }
1917 #ifndef NDEBUG
1918  else
1919  assert(gubset->gubconssidx[var] == newgubcons);
1920 #endif
1921 
1922  return SCIP_OKAY;
1923 }
1924 
1925 /** swaps two variables in the same GUB constraint */
1926 static
1927 void GUBsetSwapVars(
1928  SCIP* scip, /**< SCIP data structure */
1929  SCIP_GUBSET* gubset, /**< GUB set data structure */
1930  int var1, /**< first variable to be swapped */
1931  int var2 /**< second variable to be swapped */
1932  )
1933 {
1934  int gubcons;
1935  int var1idx;
1936  GUBVARSTATUS var1status;
1937  int var2idx;
1938  GUBVARSTATUS var2status;
1939 
1940  assert(scip != NULL);
1941  assert(gubset != NULL);
1942 
1943  gubcons = gubset->gubconssidx[var1];
1944  assert(gubcons == gubset->gubconssidx[var2]);
1945 
1946  /* nothing to be done if both variables are the same */
1947  if( var1 == var2 )
1948  return;
1949 
1950  /* swap index and status of variables in GUB constraint */
1951  var1idx = gubset->gubvarsidx[var1];
1952  var1status = gubset->gubconss[gubcons]->gubvarsstatus[var1idx];
1953  var2idx = gubset->gubvarsidx[var2];
1954  var2status = gubset->gubconss[gubcons]->gubvarsstatus[var2idx];
1955 
1956  gubset->gubvarsidx[var1] = var2idx;
1957  gubset->gubconss[gubcons]->gubvars[var1idx] = var2;
1958  gubset->gubconss[gubcons]->gubvarsstatus[var1idx] = var2status;
1959 
1960  gubset->gubvarsidx[var2] = var1idx;
1961  gubset->gubconss[gubcons]->gubvars[var2idx] = var1;
1962  gubset->gubconss[gubcons]->gubvarsstatus[var2idx] = var1status;
1963 }
1964 
1965 /** initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable) */
1966 static
1968  SCIP* scip, /**< SCIP data structure */
1969  SCIP_GUBSET** gubset, /**< pointer to store GUB set data structure */
1970  int nvars, /**< number of variables in the knapsack constraint */
1971  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
1972  SCIP_Longint capacity /**< capacity of knapsack */
1973  )
1974 {
1975  int i;
1976 
1977  assert(scip != NULL);
1978  assert(gubset != NULL);
1979  assert(nvars > 0);
1980  assert(weights != NULL);
1981  assert(capacity >= 0);
1982 
1983  /* allocate memory for GUB set data structures */
1984  SCIP_CALL( SCIPallocBuffer(scip, gubset) );
1985  SCIP_CALL( SCIPallocBufferArray(scip, &(*gubset)->gubconss, nvars) );
1986  SCIP_CALL( SCIPallocBufferArray(scip, &(*gubset)->gubconsstatus, nvars) );
1987  SCIP_CALL( SCIPallocBufferArray(scip, &(*gubset)->gubconssidx, nvars) );
1988  SCIP_CALL( SCIPallocBufferArray(scip, &(*gubset)->gubvarsidx, nvars) );
1989  (*gubset)->ngubconss = nvars;
1990  (*gubset)->nvars = nvars;
1991 
1992  /* initialize the set of GUB constraints */
1993  for( i = 0; i < nvars; i++ )
1994  {
1995  /* assign each variable to a new (trivial) GUB constraint */
1996  SCIP_CALL( GUBconsCreate(scip, &(*gubset)->gubconss[i]) );
1997  SCIP_CALL( GUBconsAddVar(scip, (*gubset)->gubconss[i], i) );
1998 
1999  /* set status of GUB constraint to initial */
2000  (*gubset)->gubconsstatus[i] = GUBCONSSTATUS_UNINITIAL;
2001 
2002  (*gubset)->gubconssidx[i] = i;
2003  (*gubset)->gubvarsidx[i] = 0;
2004  assert((*gubset)->gubconss[i]->ngubvars == 1);
2005 
2006  /* already updated status of variable in GUB constraint if it exceeds the capacity of the knapsack */
2007  if( weights[i] > capacity )
2008  (*gubset)->gubconss[(*gubset)->gubconssidx[i]]->gubvarsstatus[(*gubset)->gubvarsidx[i]] = GUBVARSTATUS_CAPACITYEXCEEDED;
2009  }
2010 
2011  return SCIP_OKAY;
2012 }
2013 
2014 /** frees GUB set data structure */
2015 static
2016 void GUBsetFree(
2017  SCIP* scip, /**< SCIP data structure */
2018  SCIP_GUBSET** gubset /**< pointer to GUB set data structure */
2019  )
2020 {
2021  int i;
2022 
2023  assert(scip != NULL);
2024  assert(gubset != NULL);
2025  assert((*gubset)->gubconss != NULL);
2026  assert((*gubset)->gubconsstatus != NULL);
2027  assert((*gubset)->gubconssidx != NULL);
2028  assert((*gubset)->gubvarsidx != NULL);
2029 
2030  /* free all GUB constraints */
2031  for( i = (*gubset)->ngubconss-1; i >= 0; --i )
2032  {
2033  assert((*gubset)->gubconss[i] != NULL);
2034  GUBconsFree(scip, &(*gubset)->gubconss[i]);
2035  }
2036 
2037  /* free allocated memory */
2038  SCIPfreeBufferArray( scip, &(*gubset)->gubvarsidx );
2039  SCIPfreeBufferArray( scip, &(*gubset)->gubconssidx );
2040  SCIPfreeBufferArray( scip, &(*gubset)->gubconsstatus );
2041  SCIPfreeBufferArray( scip, &(*gubset)->gubconss );
2042  SCIPfreeBuffer(scip, gubset);
2043 }
2044 
2045 #ifndef NDEBUG
2046 /** checks whether GUB set data structure is consistent */
2047 static
2049  SCIP* scip, /**< SCIP data structure */
2050  SCIP_GUBSET* gubset, /**< GUB set data structure */
2051  SCIP_VAR** vars /**< variables in the knapsack constraint */
2052  )
2053 {
2054  int i;
2055  int gubconsidx;
2056  int gubvaridx;
2057  SCIP_VAR* var1;
2058  SCIP_VAR* var2;
2059  SCIP_Bool var1negated;
2060  SCIP_Bool var2negated;
2061 
2062  assert(scip != NULL);
2063  assert(gubset != NULL);
2064 
2065  SCIPdebugMsg(scip, " GUB set consistency check:\n");
2066 
2067  /* checks for all knapsack vars consistency of stored index of associated gubcons and corresponding index in gubvars */
2068  for( i = 0; i < gubset->nvars; i++ )
2069  {
2070  gubconsidx = gubset->gubconssidx[i];
2071  gubvaridx = gubset->gubvarsidx[i];
2072 
2073  if( gubset->gubconss[gubconsidx]->gubvars[gubvaridx] != i )
2074  {
2075  SCIPdebugMsg(scip, " var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2076  gubconsidx, gubvaridx, gubset->gubconss[gubconsidx]->gubvars[gubvaridx] );
2077  }
2078  assert(gubset->gubconss[gubconsidx]->gubvars[gubvaridx] == i);
2079  }
2080 
2081  /* checks for each GUB whether all pairs of its variables have a common clique */
2082  for( i = 0; i < gubset->ngubconss; i++ )
2083  {
2084  int j;
2085 
2086  for( j = 0; j < gubset->gubconss[i]->ngubvars; j++ )
2087  {
2088  int k;
2089 
2090  /* get corresponding active problem variable */
2091  var1 = vars[gubset->gubconss[i]->gubvars[j]];
2092  var1negated = FALSE;
2093  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &var1negated) );
2094 
2095  for( k = j+1; k < gubset->gubconss[i]->ngubvars; k++ )
2096  {
2097  /* get corresponding active problem variable */
2098  var2 = vars[gubset->gubconss[i]->gubvars[k]];
2099  var2negated = FALSE;
2100  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &var2negated) );
2101 
2102  if( !SCIPvarsHaveCommonClique(var1, !var1negated, var2, !var2negated, TRUE) )
2103  {
2104  SCIPdebugMsg(scip, " GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n", i, j,
2105  SCIPvarGetName(vars[gubset->gubconss[i]->gubvars[j]]), k,
2106  SCIPvarGetName(vars[gubset->gubconss[i]->gubvars[k]]));
2107  SCIPdebugMsg(scip, " GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n", i, j,
2108  SCIPvarGetName(var1), k,
2109  SCIPvarGetName(var2));
2110  }
2111 
2112  /* @todo: in case we used also negated cliques for the GUB partition, this assert has to be changed */
2113  assert(SCIPvarsHaveCommonClique(var1, !var1negated, var2, !var2negated, TRUE));
2114  }
2115  }
2116  }
2117  SCIPdebugMsg(scip, " --> successful\n");
2118 
2119  return SCIP_OKAY;
2120 }
2121 #endif
2122 
2123 /** calculates a partition of the given set of binary variables into cliques;
2124  * afterwards the output array contains one value for each variable, such that two variables got the same value iff they
2125  * were assigned to the same clique;
2126  * the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of
2127  * the preceding variables was assigned to clique i-1;
2128  * note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one
2129  * variable) and for the remaining variables, a partition with a small number of cliques is constructed
2130  */
2131 
2132 static
2134  SCIP*const scip, /**< SCIP data structure */
2135  SCIP_VAR**const vars, /**< binary variables in the clique from which at most one can be set to 1 */
2136  int const nvars, /**< number of variables in the clique */
2137  int*const cliquepartition, /**< array of length nvars to store the clique partition */
2138  int*const ncliques, /**< pointer to store number of cliques actually contained in the partition */
2139  SCIP_Real* solvals /**< solution values of all given binary variables */
2140  )
2142  SCIP_VAR** tmpvars;
2143  SCIP_VAR** cliquevars;
2144  SCIP_Bool* cliquevalues;
2145  SCIP_Bool* tmpvalues;
2146  int* varseq;
2147  int* sortkeys;
2148  int ncliquevars;
2149  int maxncliquevarscomp;
2150  int nignorevars;
2151  int nvarsused;
2152  int i;
2153 
2154  assert(scip != NULL);
2155  assert(nvars == 0 || vars != NULL);
2156  assert(nvars == 0 || cliquepartition != NULL);
2157  assert(ncliques != NULL);
2158 
2159  if( nvars == 0 )
2160  {
2161  *ncliques = 0;
2162  return SCIP_OKAY;
2163  }
2164 
2165  /* allocate temporary memory for storing the variables of the current clique */
2166  SCIP_CALL( SCIPallocBufferArray(scip, &cliquevars, nvars) );
2167  SCIP_CALL( SCIPallocBufferArray(scip, &cliquevalues, nvars) );
2168  SCIP_CALL( SCIPallocBufferArray(scip, &tmpvalues, nvars) );
2169  SCIP_CALL( SCIPduplicateBufferArray(scip, &tmpvars, vars, nvars) );
2170  SCIP_CALL( SCIPallocBufferArray(scip, &varseq, nvars) );
2171  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeys, nvars) );
2172 
2173  /* initialize the cliquepartition array with -1 */
2174  /* initialize the tmpvalues array */
2175  for( i = nvars - 1; i >= 0; --i )
2176  {
2177  tmpvalues[i] = TRUE;
2178  cliquepartition[i] = -1;
2179  }
2180 
2181  /* get corresponding active problem variables */
2182  SCIP_CALL( SCIPvarsGetProbvarBinary(&tmpvars, &tmpvalues, nvars) );
2183 
2184  /* ignore variables with LP value 1 (will be assigned to trivial GUBs at the end) and sort remaining variables
2185  * by nondecreasing number of cliques the variables are in
2186  */
2187  nignorevars = 0;
2188  nvarsused = 0;
2189  for( i = 0; i < nvars; i++ )
2190  {
2191  if( SCIPisFeasEQ(scip, solvals[i], 1.0) )
2192  {
2193  /* variables with LP value 1 are put to the end of varseq array and will not be sorted */
2194  varseq[nvars-1-nignorevars] = i;
2195  nignorevars++;
2196  }
2197  else
2198  {
2199  /* remaining variables are put to the front of varseq array and will be sorted by their number of cliques */
2200  varseq[nvarsused] = i;
2201  sortkeys[nvarsused] = SCIPvarGetNCliques(tmpvars[i], tmpvalues[i]);
2202  nvarsused++;
2203  }
2204  }
2205  assert(nvarsused + nignorevars == nvars);
2206 
2207  /* sort variables with LP value less than 1 by nondecreasing order of the number of cliques they are in */
2208  SCIPsortIntInt(sortkeys, varseq, nvarsused);
2209 
2210  maxncliquevarscomp = MIN(nvars*nvars, MAXNCLIQUEVARSCOMP);
2211 
2212  /* calculate the clique partition */
2213  *ncliques = 0;
2214  for( i = 0; i < nvars; ++i )
2215  {
2216  if( cliquepartition[varseq[i]] == -1 )
2217  {
2218  int j;
2219 
2220  /* variable starts a new clique */
2221  cliquepartition[varseq[i]] = *ncliques;
2222  cliquevars[0] = tmpvars[varseq[i]];
2223  cliquevalues[0] = tmpvalues[varseq[i]];
2224  ncliquevars = 1;
2225 
2226  /* if variable is not active (multi-aggregated or fixed), it cannot be in any clique and
2227  * if the variable has LP value 1 we do not want it to be in nontrivial cliques
2228  */
2229  if( SCIPvarIsActive(tmpvars[varseq[i]]) && i < nvarsused )
2230  {
2231  /* greedily fill up the clique */
2232  for( j = i + 1; j < nvarsused; ++j )
2233  {
2234  /* if variable is not active (multi-aggregated or fixed), it cannot be in any clique */
2235  if( cliquepartition[varseq[j]] == -1 && SCIPvarIsActive(tmpvars[varseq[j]]) )
2236  {
2237  int k;
2238 
2239  /* check if every variable in the actual clique is in clique with the new variable */
2240  for( k = ncliquevars - 1; k >= 0; --k )
2241  {
2242  if( !SCIPvarsHaveCommonClique(tmpvars[varseq[j]], tmpvalues[varseq[j]], cliquevars[k],
2243  cliquevalues[k], TRUE) )
2244  break;
2245  }
2246 
2247  if( k == -1 )
2248  {
2249  /* put the variable into the same clique */
2250  cliquepartition[varseq[j]] = cliquepartition[varseq[i]];
2251  cliquevars[ncliquevars] = tmpvars[varseq[j]];
2252  cliquevalues[ncliquevars] = tmpvalues[varseq[j]];
2253  ++ncliquevars;
2254  }
2255  }
2256  }
2257  }
2258 
2259  /* this clique is finished */
2260  ++(*ncliques);
2261  }
2262  assert(cliquepartition[varseq[i]] >= 0 && cliquepartition[varseq[i]] < i + 1);
2263 
2264  /* break if we reached the maximal number of comparisons */
2265  if( i * nvars > maxncliquevarscomp )
2266  break;
2267  }
2268  /* if we had too many variables fill up the cliquepartition and put each variable in a separate clique */
2269  for( ; i < nvars; ++i )
2270  {
2271  if( cliquepartition[varseq[i]] == -1 )
2272  {
2273  cliquepartition[varseq[i]] = *ncliques;
2274  ++(*ncliques);
2275  }
2276  }
2277 
2278  /* free temporary memory */
2279  SCIPfreeBufferArray(scip, &sortkeys);
2280  SCIPfreeBufferArray(scip, &varseq);
2281  SCIPfreeBufferArray(scip, &tmpvars);
2282  SCIPfreeBufferArray(scip, &tmpvalues);
2283  SCIPfreeBufferArray(scip, &cliquevalues);
2284  SCIPfreeBufferArray(scip, &cliquevars);
2285 
2286  return SCIP_OKAY;
2287 }
2288 
2289 /** constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs */
2290 static
2292  SCIP* scip, /**< SCIP data structure */
2293  SCIP_GUBSET* gubset, /**< GUB set data structure */
2294  SCIP_VAR** vars, /**< variables in the knapsack constraint */
2295  SCIP_Real* solvals /**< solution values of all knapsack variables */
2296  )
2297 {
2298  int* cliquepartition;
2299  int* gubfirstvar;
2300  int ncliques;
2301  int currentgubconsidx;
2302  int newgubconsidx;
2303  int cliqueidx;
2304  int nvars;
2305  int i;
2306 
2307  assert(scip != NULL);
2308  assert(gubset != NULL);
2309  assert(vars != NULL);
2310 
2311  nvars = gubset->nvars;
2312  assert(nvars >= 0);
2313 
2314  /* allocate temporary memory for clique partition */
2315  SCIP_CALL( SCIPallocBufferArray(scip, &cliquepartition, nvars) );
2316 
2317  /* compute sophisticated clique partition */
2318  SCIP_CALL( GUBsetCalcCliquePartition(scip, vars, nvars, cliquepartition, &ncliques, solvals) );
2319 
2320  /* allocate temporary memory for GUB set data structure */
2321  SCIP_CALL( SCIPallocBufferArray(scip, &gubfirstvar, ncliques) );
2322 
2323  /* translate GUB partition into GUB set data structure */
2324  for( i = 0; i < ncliques; i++ )
2325  {
2326  /* initialize first variable for every GUB */
2327  gubfirstvar[i] = -1;
2328  }
2329  /* move every knapsack variable into GUB defined by clique partition */
2330  for( i = 0; i < nvars; i++ )
2331  {
2332  assert(cliquepartition[i] >= 0);
2333 
2334  cliqueidx = cliquepartition[i];
2335  currentgubconsidx = gubset->gubconssidx[i];
2336  assert(gubset->gubconss[currentgubconsidx]->ngubvars == 1 );
2337 
2338  /* variable is first element in GUB constraint defined by clique partition */
2339  if( gubfirstvar[cliqueidx] == -1 )
2340  {
2341  /* corresponding GUB constraint in GUB set data structure was already constructed (as initial trivial GUB);
2342  * note: no assert for gubconssidx, because it can changed due to deleting empty GUBs in GUBsetMoveVar()
2343  */
2344  assert(gubset->gubvarsidx[i] == 0);
2345  assert(gubset->gubconss[gubset->gubconssidx[i]]->gubvars[gubset->gubvarsidx[i]] == i);
2346 
2347  /* remember the first variable found for the current GUB */
2348  gubfirstvar[cliqueidx] = i;
2349  }
2350  /* variable is additional element of GUB constraint defined by clique partition */
2351  else
2352  {
2353  assert(gubfirstvar[cliqueidx] >= 0 && gubfirstvar[cliqueidx] < i);
2354 
2355  /* move variable to GUB constraint defined by clique partition; index of this GUB constraint is given by the
2356  * first variable of this GUB constraint
2357  */
2358  newgubconsidx = gubset->gubconssidx[gubfirstvar[cliqueidx]];
2359  assert(newgubconsidx != currentgubconsidx); /* because initially every variable is in a different GUB */
2360  SCIP_CALL( GUBsetMoveVar(scip, gubset, vars, i, currentgubconsidx, newgubconsidx) );
2361 
2362  assert(gubset->gubconss[gubset->gubconssidx[i]]->gubvars[gubset->gubvarsidx[i]] == i);
2363  }
2364  }
2365 
2366 #ifdef SCIP_DEBUG
2367  /* prints GUB set data structure */
2368  GUBsetPrint(scip, gubset, vars, solvals);
2369 #endif
2370 
2371 #ifndef NDEBUG
2372  /* checks consistency of GUB set data structure */
2373  SCIP_CALL( GUBsetCheck(scip, gubset, vars) );
2374 #endif
2375 
2376  /* free temporary memory */
2377  SCIPfreeBufferArray(scip, &gubfirstvar);
2378  SCIPfreeBufferArray(scip, &cliquepartition);
2379 
2380  return SCIP_OKAY;
2381 }
2382 
2383 /** gets a most violated cover C (\f$\sum_{j \in C} a_j > a_0\f$) for a given knapsack constraint \f$\sum_{j \in N} a_j x_j \leq a_0\f$
2384  * taking into consideration the following fixing: \f$j \in C\f$, if \f$j \in N_1 = \{j \in N : x^*_j = 1\}\f$ and
2385  * \f$j \in N \setminus C\f$, if \f$j \in N_0 = \{j \in N : x^*_j = 0\}\f$, if one exists.
2386  */
2387 static
2389  SCIP* scip, /**< SCIP data structure */
2390  SCIP_VAR** vars, /**< variables in knapsack constraint */
2391  int nvars, /**< number of variables in knapsack constraint */
2392  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
2393  SCIP_Longint capacity, /**< capacity of knapsack */
2394  SCIP_Real* solvals, /**< solution values of all problem variables */
2395  int* covervars, /**< pointer to store cover variables */
2396  int* noncovervars, /**< pointer to store noncover variables */
2397  int* ncovervars, /**< pointer to store number of cover variables */
2398  int* nnoncovervars, /**< pointer to store number of noncover variables */
2399  SCIP_Longint* coverweight, /**< pointer to store weight of cover */
2400  SCIP_Bool* found, /**< pointer to store whether a cover was found */
2401  SCIP_Bool modtransused, /**< should modified transformed separation problem be used to find cover */
2402  int* ntightened, /**< pointer to store number of variables with tightened upper bound */
2403  SCIP_Bool* fractional /**< pointer to store whether the LP sol for knapsack vars is fractional */
2404  )
2405 {
2406  SCIP_Longint* transweights;
2407  SCIP_Real* transprofits;
2408  SCIP_Longint transcapacity;
2409  SCIP_Longint fixedonesweight;
2410  SCIP_Longint itemsweight;
2411  SCIP_Bool infeasible;
2412  int* fixedones;
2413  int* fixedzeros;
2414  int* items;
2415  int nfixedones;
2416  int nfixedzeros;
2417  int nitems;
2418  int j;
2419 
2420  assert(scip != NULL);
2421  assert(vars != NULL);
2422  assert(nvars > 0);
2423  assert(weights != NULL);
2424  assert(capacity >= 0);
2425  assert(solvals != NULL);
2426  assert(covervars != NULL);
2427  assert(noncovervars != NULL);
2428  assert(ncovervars != NULL);
2429  assert(nnoncovervars != NULL);
2430  assert(coverweight != NULL);
2431  assert(found != NULL);
2432  assert(ntightened != NULL);
2433  assert(fractional != NULL);
2434 
2435  SCIPdebugMsg(scip, " get cover for knapsack constraint\n");
2436 
2437  /* allocates temporary memory */
2438  SCIP_CALL( SCIPallocBufferArray(scip, &transweights, nvars) );
2439  SCIP_CALL( SCIPallocBufferArray(scip, &transprofits, nvars) );
2440  SCIP_CALL( SCIPallocBufferArray(scip, &fixedones, nvars) );
2441  SCIP_CALL( SCIPallocBufferArray(scip, &fixedzeros, nvars) );
2442  SCIP_CALL( SCIPallocBufferArray(scip, &items, nvars) );
2443 
2444  *found = FALSE;
2445  *ncovervars = 0;
2446  *nnoncovervars = 0;
2447  *coverweight = 0;
2448  *fractional = TRUE;
2449 
2450  /* gets the following sets
2451  * N_1 = {j in N : x*_j = 1} (fixedones),
2452  * N_0 = {j in N : x*_j = 0} (fixedzeros) and
2453  * N\(N_0 & N_1) (items),
2454  * where x*_j is the solution value of variable x_j
2455  */
2456  nfixedones = 0;
2457  nfixedzeros = 0;
2458  nitems = 0;
2459  fixedonesweight = 0;
2460  itemsweight = 0;
2461  *ntightened = 0;
2462  for( j = 0; j < nvars; j++ )
2463  {
2464  assert(SCIPvarIsBinary(vars[j]));
2465 
2466  /* tightens upper bound of x_j if weight of x_j is greater than capacity of knapsack */
2467  if( weights[j] > capacity )
2468  {
2469  SCIP_CALL( SCIPtightenVarUb(scip, vars[j], 0.0, FALSE, &infeasible, NULL) );
2470  assert(!infeasible);
2471  (*ntightened)++;
2472  continue;
2473  }
2474 
2475  /* variable x_j has solution value one */
2476  if( SCIPisFeasEQ(scip, solvals[j], 1.0) )
2477  {
2478  fixedones[nfixedones] = j;
2479  nfixedones++;
2480  fixedonesweight += weights[j];
2481  }
2482  /* variable x_j has solution value zero */
2483  else if( SCIPisFeasEQ(scip, solvals[j], 0.0) )
2484  {
2485  fixedzeros[nfixedzeros] = j;
2486  nfixedzeros++;
2487  }
2488  /* variable x_j has fractional solution value */
2489  else
2490  {
2491  assert( SCIPisFeasGT(scip, solvals[j], 0.0) && SCIPisFeasLT(scip, solvals[j], 1.0) );
2492  items[nitems] = j;
2493  nitems++;
2494  itemsweight += weights[j];
2495  }
2496  }
2497  assert(nfixedones + nfixedzeros + nitems == nvars - (*ntightened));
2498 
2499  /* sets whether the LP solution x* for the knapsack variables is fractional; if it is not fractional we stop
2500  * the separation routine
2501  */
2502  assert(nitems >= 0);
2503  if( nitems == 0 )
2504  {
2505  *fractional = FALSE;
2506  goto TERMINATE;
2507  }
2508  assert(*fractional);
2509 
2510  /* transforms the traditional separation problem (under consideration of the following fixing:
2511  * z_j = 1 for all j in N_1, z_j = 0 for all j in N_0)
2512  *
2513  * min sum_{j in N\(N_0 & N_1)} (1 - x*_j) z_j
2514  * sum_{j in N\(N_0 & N_1)} a_j z_j >= (a_0 + 1) - sum_{j in N_1} a_j
2515  * z_j in {0,1}, j in N\(N_0 & N_1)
2516  *
2517  * to a knapsack problem in maximization form by complementing the variables
2518  *
2519  * sum_{j in N\(N_0 & N_1)} (1 - x*_j) -
2520  * max sum_{j in N\(N_0 & N_1)} (1 - x*_j) z_j
2521  * sum_{j in N\(N_0 & N_1)} a_j z_j <= sum_{j in N\N_0} a_j - (a_0 + 1)
2522  * z_j in {0,1}, j in N\(N_0 & N_1)
2523  */
2524 
2525  /* gets weight and profit of variables in transformed knapsack problem */
2526  for( j = 0; j < nitems; j++ )
2527  {
2528  transweights[j] = weights[items[j]];
2529  transprofits[j] = 1.0 - solvals[items[j]];
2530  }
2531  /* gets capacity of transformed knapsack problem */
2532  transcapacity = fixedonesweight + itemsweight - capacity - 1;
2533 
2534  /* if capacity of transformed knapsack problem is less than zero, there is no cover
2535  * (when variables fixed to zero are not used)
2536  */
2537  if( transcapacity < 0 )
2538  {
2539  assert(!(*found));
2540  goto TERMINATE;
2541  }
2542 
2543  if( modtransused )
2544  {
2545  /* transforms the modified separation problem (under consideration of the following fixing:
2546  * z_j = 1 for all j in N_1, z_j = 0 for all j in N_0)
2547  *
2548  * min sum_{j in N\(N_0 & N_1)} (1 - x*_j) a_j z_j
2549  * sum_{j in N\(N_0 & N_1)} a_j z_j >= (a_0 + 1) - sum_{j in N_1} a_j
2550  * z_j in {0,1}, j in N\(N_0 & N_1)
2551  *
2552  * to a knapsack problem in maximization form by complementing the variables
2553  *
2554  * sum_{j in N\(N_0 & N_1)} (1 - x*_j) a_j -
2555  * max sum_{j in N\(N_0 & N_1)} (1 - x*_j) a_j z_j
2556  * sum_{j in N\(N_0 & N_1)} a_j z_j <= sum_{j in N\N_0} a_j - (a_0 + 1)
2557  * z_j in {0,1}, j in N\(N_0 & N_1)
2558  */
2559 
2560  /* gets weight and profit of variables in modified transformed knapsack problem */
2561  for( j = 0; j < nitems; j++ )
2562  {
2563  transprofits[j] *= weights[items[j]];
2564  assert(SCIPisFeasPositive(scip, transprofits[j]));
2565  }
2566  }
2567 
2568  /* solves (modified) transformed knapsack problem approximately by solving the LP-relaxation of the (modified)
2569  * transformed knapsack problem using Dantzig's method and rounding down the solution.
2570  * let z* be the solution, then
2571  * j in C, if z*_j = 0 and
2572  * i in N\C, if z*_j = 1.
2573  */
2574  SCIP_CALL( SCIPsolveKnapsackApproximately(scip, nitems, transweights, transprofits, transcapacity, items,
2575  noncovervars, covervars, nnoncovervars, ncovervars, NULL) );
2576  /*assert(checkSolveKnapsack(scip, nitems, transweights, transprofits, items, weights, solvals, modtransused));*/
2577 
2578  /* constructs cover C (sum_{j in C} a_j > a_0) */
2579  for( j = 0; j < *ncovervars; j++ )
2580  {
2581  (*coverweight) += weights[covervars[j]];
2582  }
2583 
2584  /* adds all variables from N_1 to C */
2585  for( j = 0; j < nfixedones; j++ )
2586  {
2587  covervars[*ncovervars] = fixedones[j];
2588  (*ncovervars)++;
2589  (*coverweight) += weights[fixedones[j]];
2590  }
2591 
2592  /* adds all variables from N_0 to N\C */
2593  for( j = 0; j < nfixedzeros; j++ )
2594  {
2595  noncovervars[*nnoncovervars] = fixedzeros[j];
2596  (*nnoncovervars)++;
2597  }
2598  assert((*ncovervars) + (*nnoncovervars) == nvars - (*ntightened));
2599  assert((*coverweight) > capacity);
2600  *found = TRUE;
2601 
2602  TERMINATE:
2603  /* frees temporary memory */
2604  SCIPfreeBufferArray(scip, &items);
2605  SCIPfreeBufferArray(scip, &fixedzeros);
2606  SCIPfreeBufferArray(scip, &fixedones);
2607  SCIPfreeBufferArray(scip, &transprofits);
2608  SCIPfreeBufferArray(scip, &transweights);
2609 
2610  SCIPdebugMsg(scip, " get cover for knapsack constraint -- end\n");
2611 
2612  return SCIP_OKAY;
2613 }
2614 
2615 #ifndef NDEBUG
2616 /** checks if minweightidx is set correctly
2617  */
2618 static
2620  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
2621  SCIP_Longint capacity, /**< capacity of knapsack */
2622  int* covervars, /**< pointer to store cover variables */
2623  int ncovervars, /**< pointer to store number of cover variables */
2624  SCIP_Longint coverweight, /**< pointer to store weight of cover */
2625  int minweightidx, /**< index of variable in cover variables with minimum weight */
2626  int j /**< current index in cover variables */
2627  )
2628 {
2629  SCIP_Longint minweight;
2630  int i;
2631 
2632  assert(weights != NULL);
2633  assert(covervars != NULL);
2634  assert(ncovervars > 0);
2635 
2636  minweight = weights[covervars[minweightidx]];
2637 
2638  /* checks if all cover variables before index j have weight greater than minweight */
2639  for( i = 0; i < j; i++ )
2640  {
2641  assert(weights[covervars[i]] > minweight);
2642  if( weights[covervars[i]] <= minweight )
2643  return FALSE;
2644  }
2645 
2646  /* checks if all variables before index j cannot be removed, i.e. i cannot be the next minweightidx */
2647  for( i = 0; i < j; i++ )
2648  {
2649  assert(coverweight - weights[covervars[i]] <= capacity);
2650  if( coverweight - weights[covervars[i]] > capacity )
2651  return FALSE;
2652  }
2653  return TRUE;
2654 }
2655 #endif
2656 
2657 
2658 /** gets partition \f$(C_1,C_2)\f$ of minimal cover \f$C\f$, i.e. \f$C_1 \cup C_2 = C\f$ and \f$C_1 \cap C_2 = \emptyset\f$,
2659  * with \f$C_1\f$ not empty; chooses partition as follows \f$C_2 = \{ j \in C : x^*_j = 1 \}\f$ and \f$C_1 = C \setminus C_2\f$
2660  */
2661 static
2663  SCIP* scip, /**< SCIP data structure */
2664  SCIP_Real* solvals, /**< solution values of all problem variables */
2665  int* covervars, /**< cover variables */
2666  int ncovervars, /**< number of cover variables */
2667  int* varsC1, /**< pointer to store variables in C1 */
2668  int* varsC2, /**< pointer to store variables in C2 */
2669  int* nvarsC1, /**< pointer to store number of variables in C1 */
2670  int* nvarsC2 /**< pointer to store number of variables in C2 */
2671  )
2672 {
2673  int j;
2674 
2675  assert(scip != NULL);
2676  assert(ncovervars >= 0);
2677  assert(solvals != NULL);
2678  assert(covervars != NULL);
2679  assert(varsC1 != NULL);
2680  assert(varsC2 != NULL);
2681  assert(nvarsC1 != NULL);
2682  assert(nvarsC2 != NULL);
2683 
2684  *nvarsC1 = 0;
2685  *nvarsC2 = 0;
2686  for( j = 0; j < ncovervars; j++ )
2687  {
2688  assert(SCIPisFeasGT(scip, solvals[covervars[j]], 0.0));
2689 
2690  /* variable has solution value one */
2691  if( SCIPisGE(scip, solvals[covervars[j]], 1.0) )
2692  {
2693  varsC2[*nvarsC2] = covervars[j];
2694  (*nvarsC2)++;
2695  }
2696  /* variable has solution value less than one */
2697  else
2698  {
2699  assert(SCIPisLT(scip, solvals[covervars[j]], 1.0));
2700  varsC1[*nvarsC1] = covervars[j];
2701  (*nvarsC1)++;
2702  }
2703  }
2704  assert((*nvarsC1) + (*nvarsC2) == ncovervars);
2705 }
2706 
2707 /** changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from
2708  * C2 to C1 if |C1| = 1 and |C1| = 0, respectively.
2709  */
2710 static
2712  SCIP* scip, /**< SCIP data structure */
2713  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
2714  int* varsC1, /**< pointer to store variables in C1 */
2715  int* varsC2, /**< pointer to store variables in C2 */
2716  int* nvarsC1, /**< pointer to store number of variables in C1 */
2717  int* nvarsC2 /**< pointer to store number of variables in C2 */
2718  )
2720  SCIP_Real* sortkeysC2;
2721  int j;
2722 
2723  assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2724  assert(*nvarsC2 > 0);
2725 
2726  /* allocates temporary memory */
2727  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysC2, *nvarsC2) );
2728 
2729  /* sorts variables in C2 such that a_1 >= .... >= a_|C2| */
2730  for( j = 0; j < *nvarsC2; j++ )
2731  sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
2732  SCIPsortDownRealInt(sortkeysC2, varsC2, *nvarsC2);
2733 
2734  /* adds one or two variable from C2 with smallest weight to C1 and removes them from C2 */
2735  assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2736  while( *nvarsC1 < 2 && *nvarsC2 > 0 )
2737  {
2738  varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2739  (*nvarsC1)++;
2740  (*nvarsC2)--;
2741  }
2742 
2743  /* frees temporary memory */
2744  SCIPfreeBufferArray(scip, &sortkeysC2);
2745 
2746  return SCIP_OKAY;
2747 }
2748 
2749 /** changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1 */
2750 static
2752  SCIP* scip, /**< SCIP data structure */
2753  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
2754  int* varsC1, /**< pointer to store variables in C1 */
2755  int* varsC2, /**< pointer to store variables in C2 */
2756  int* nvarsC1, /**< pointer to store number of variables in C1 */
2757  int* nvarsC2 /**< pointer to store number of variables in C2 */
2758  )
2760  SCIP_Real* sortkeysC2;
2761  int j;
2762 
2763  assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2764  assert(*nvarsC2 > 0);
2765 
2766  /* allocates temporary memory */
2767  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysC2, *nvarsC2) );
2768 
2769  /* sorts variables in C2 such that a_1 >= .... >= a_|C2| */
2770  for( j = 0; j < *nvarsC2; j++ )
2771  sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
2772  SCIPsortDownRealInt(sortkeysC2, varsC2, *nvarsC2);
2773 
2774  /* adds variable from C2 with smallest weight to C1 and removes it from C2 */
2775  assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2776  varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2777  (*nvarsC1)++;
2778  (*nvarsC2)--;
2779 
2780  /* frees temporary memory */
2781  SCIPfreeBufferArray(scip, &sortkeysC2);
2782 
2783  return SCIP_OKAY;
2784 }
2785 
2786 
2787 /** gets partition \f$(F,R)\f$ of \f$N \setminus C\f$ where \f$C\f$ is a minimal cover, i.e. \f$F \cup R = N \setminus C\f$
2788  * and \f$F \cap R = \emptyset\f$; chooses partition as follows \f$R = \{ j \in N \setminus C : x^*_j = 0 \}\f$ and
2789  * \f$F = (N \setminus C) \setminus F\f$
2790  */
2791 static
2793  SCIP* scip, /**< SCIP data structure */
2794  SCIP_Real* solvals, /**< solution values of all problem variables */
2795  int* noncovervars, /**< noncover variables */
2796  int nnoncovervars, /**< number of noncover variables */
2797  int* varsF, /**< pointer to store variables in F */
2798  int* varsR, /**< pointer to store variables in R */
2799  int* nvarsF, /**< pointer to store number of variables in F */
2800  int* nvarsR /**< pointer to store number of variables in R */
2801  )
2802 {
2803  int j;
2804 
2805  assert(scip != NULL);
2806  assert(nnoncovervars >= 0);
2807  assert(solvals != NULL);
2808  assert(noncovervars != NULL);
2809  assert(varsF != NULL);
2810  assert(varsR != NULL);
2811  assert(nvarsF != NULL);
2812  assert(nvarsR != NULL);
2813 
2814  *nvarsF = 0;
2815  *nvarsR = 0;
2816 
2817  for( j = 0; j < nnoncovervars; j++ )
2818  {
2819  /* variable has solution value zero */
2820  if( SCIPisFeasEQ(scip, solvals[noncovervars[j]], 0.0) )
2821  {
2822  varsR[*nvarsR] = noncovervars[j];
2823  (*nvarsR)++;
2824  }
2825  /* variable has solution value greater than zero */
2826  else
2827  {
2828  assert(SCIPisFeasGT(scip, solvals[noncovervars[j]], 0.0));
2829  varsF[*nvarsF] = noncovervars[j];
2830  (*nvarsF)++;
2831  }
2832  }
2833  assert((*nvarsF) + (*nvarsR) == nnoncovervars);
2834 }
2835 
2836 /** sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential
2837  * lifting procedure
2838  */
2839 static
2841  SCIP* scip, /**< SCIP data structure */
2842  SCIP_Real* solvals, /**< solution values of all problem variables */
2843  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
2844  int* varsF, /**< pointer to store variables in F */
2845  int* varsC2, /**< pointer to store variables in C2 */
2846  int* varsR, /**< pointer to store variables in R */
2847  int nvarsF, /**< number of variables in F */
2848  int nvarsC2, /**< number of variables in C2 */
2849  int nvarsR /**< number of variables in R */
2850  )
2851 {
2852  SORTKEYPAIR** sortkeypairsF;
2853  SORTKEYPAIR* sortkeypairsFstore;
2854  SCIP_Real* sortkeysC2;
2855  SCIP_Real* sortkeysR;
2856  int j;
2857 
2858  assert(scip != NULL);
2859  assert(solvals != NULL);
2860  assert(weights != NULL);
2861  assert(varsF != NULL);
2862  assert(varsC2 != NULL);
2863  assert(varsR != NULL);
2864  assert(nvarsF >= 0);
2865  assert(nvarsC2 >= 0);
2866  assert(nvarsR >= 0);
2867 
2868  /* allocates temporary memory */
2869  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeypairsF, nvarsF) );
2870  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeypairsFstore, nvarsF) );
2871  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysC2, nvarsC2) );
2872  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysR, nvarsR) );
2873 
2874  /* gets sorting key for variables in F corresponding to the following lifting sequence
2875  * sequence 1: non-increasing absolute difference between x*_j and the value the variable is fixed to, i.e.
2876  * x*_1 >= x*_2 >= ... >= x*_|F|
2877  * in case of equality uses
2878  * sequence 4: non-increasing a_j, i.e. a_1 >= a_2 >= ... >= a_|C_2|
2879  */
2880  for( j = 0; j < nvarsF; j++ )
2881  {
2882  sortkeypairsF[j] = &(sortkeypairsFstore[j]);
2883  sortkeypairsF[j]->key1 = solvals[varsF[j]];
2884  sortkeypairsF[j]->key2 = (SCIP_Real) weights[varsF[j]];
2885  }
2886 
2887  /* gets sorting key for variables in C_2 corresponding to the following lifting sequence
2888  * sequence 4: non-increasing a_j, i.e. a_1 >= a_2 >= ... >= a_|C_2|
2889  */
2890  for( j = 0; j < nvarsC2; j++ )
2891  sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
2892 
2893  /* gets sorting key for variables in R corresponding to the following lifting sequence
2894  * sequence 4: non-increasing a_j, i.e. a_1 >= a_2 >= ... >= a_|R|
2895  */
2896  for( j = 0; j < nvarsR; j++ )
2897  sortkeysR[j] = (SCIP_Real) weights[varsR[j]];
2898 
2899  /* sorts F, C2 and R */
2900  if( nvarsF > 0 )
2901  {
2902  SCIPsortDownPtrInt((void**)sortkeypairsF, varsF, compSortkeypairs, nvarsF);
2903  }
2904  if( nvarsC2 > 0 )
2905  {
2906  SCIPsortDownRealInt(sortkeysC2, varsC2, nvarsC2);
2907  }
2908  if( nvarsR > 0)
2909  {
2910  SCIPsortDownRealInt(sortkeysR, varsR, nvarsR);
2911  }
2912 
2913  /* frees temporary memory */
2914  SCIPfreeBufferArray(scip, &sortkeysR);
2915  SCIPfreeBufferArray(scip, &sortkeysC2);
2916  SCIPfreeBufferArray(scip, &sortkeypairsFstore);
2917  SCIPfreeBufferArray(scip, &sortkeypairsF);
2918 
2919  return SCIP_OKAY;
2920 }
2921 
2922 /** categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs
2923  * for the sequential GUB wise lifting procedure
2924  */
2925 static
2927  SCIP* scip, /**< SCIP data structure */
2928  SCIP_GUBSET* gubset, /**< GUB set data structure */
2929  SCIP_Real* solvals, /**< solution values of variables in knapsack constraint */
2930  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
2931  int* varsC1, /**< variables in C1 */
2932  int* varsC2, /**< variables in C2 */
2933  int* varsF, /**< variables in F */
2934  int* varsR, /**< variables in R */
2935  int nvarsC1, /**< number of variables in C1 */
2936  int nvarsC2, /**< number of variables in C2 */
2937  int nvarsF, /**< number of variables in F */
2938  int nvarsR, /**< number of variables in R */
2939  int* gubconsGC1, /**< pointer to store GUBs in GC1(GNC1+GOC1) */
2940  int* gubconsGC2, /**< pointer to store GUBs in GC2 */
2941  int* gubconsGFC1, /**< pointer to store GUBs in GFC1(GNC1+GF) */
2942  int* gubconsGR, /**< pointer to store GUBs in GR */
2943  int* ngubconsGC1, /**< pointer to store number of GUBs in GC1(GNC1+GOC1) */
2944  int* ngubconsGC2, /**< pointer to store number of GUBs in GC2 */
2945  int* ngubconsGFC1, /**< pointer to store number of GUBs in GFC1(GNC1+GF) */
2946  int* ngubconsGR, /**< pointer to store number of GUBs in GR */
2947  int* ngubconscapexceed, /**< pointer to store number of GUBs with only capacity exceeding variables */
2948  int* maxgubvarssize /**< pointer to store the maximal size of GUB constraints */
2949  )
2950 {
2951  SORTKEYPAIR** sortkeypairsGFC1;
2952  SORTKEYPAIR* sortkeypairsGFC1store;
2953  SCIP_Real* sortkeysC1;
2954  SCIP_Real* sortkeysC2;
2955  SCIP_Real* sortkeysR;
2956  int* nC1varsingubcons;
2957  int var;
2958  int gubconsidx;
2959  int varidx;
2960  int ngubconss;
2961  int ngubconsGOC1;
2962  int targetvar;
2963  int nvarsprocessed;
2964  int i;
2965  int j;
2966 
2967 #if GUBSPLITGNC1GUBS
2968  SCIP_Bool gubconswithF;
2969  int origngubconss;
2970  origngubconss = gubset->ngubconss;
2971 #endif
2972 
2973  assert(scip != NULL);
2974  assert(gubset != NULL);
2975  assert(solvals != NULL);
2976  assert(weights != NULL);
2977  assert(varsC1 != NULL);
2978  assert(varsC2 != NULL);
2979  assert(varsF != NULL);
2980  assert(varsR != NULL);
2981  assert(nvarsC1 > 0);
2982  assert(nvarsC2 >= 0);
2983  assert(nvarsF >= 0);
2984  assert(nvarsR >= 0);
2985  assert(gubconsGC1 != NULL);
2986  assert(gubconsGC2 != NULL);
2987  assert(gubconsGFC1 != NULL);
2988  assert(gubconsGR != NULL);
2989  assert(ngubconsGC1 != NULL);
2990  assert(ngubconsGC2 != NULL);
2991  assert(ngubconsGFC1 != NULL);
2992  assert(ngubconsGR != NULL);
2993  assert(maxgubvarssize != NULL);
2994 
2995  ngubconss = gubset->ngubconss;
2996  nvarsprocessed = 0;
2997  ngubconsGOC1 = 0;
2998 
2999  /* GUBs are categorized into different types according to the variables in volved
3000  * - GOC1: involves variables in C1 only -- no C2, R, F
3001  * - GNC1: involves variables in C1 and F (and R) -- no C2
3002  * - GF: involves variables in F (and R) only -- no C1, C2
3003  * - GC2: involves variables in C2 only -- no C1, R, F
3004  * - GR: involves variables in R only -- no C1, C2, F
3005  * which requires splitting GUBs in case they include variable in F and R.
3006  *
3007  * afterwards all GUBs (except GOC1 GUBs, which we do not need to lift) are sorted by a two level lifting sequence.
3008  * - first ordering level is: GFC1 (GNC1+GF), GC2, and GR.
3009  * - second ordering level is
3010  * GFC1: non-increasing number of variables in F and non-increasing max{x*_k : k in GFC1_j} in case of equality
3011  * GC2: non-increasing max{ a_k : k in GC2_j}; note that |GFC2_j| = 1
3012  * GR: non-increasing max{ a_k : k in GR_j}
3013  *
3014  * in additon, another GUB union, which is helpful for the lifting procedure, is formed
3015  * - GC1: GUBs of category GOC1 and GNC1
3016  * with second ordering level non-decreasing min{ a_k : k in GC1_j };
3017  * note that min{ a_k : k in GC1_j } always comes from the first variable in the GUB
3018  */
3019 
3020  /* allocates temporary memory */
3021  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysC1, nvarsC1) );
3022  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysC2, nvarsC2) );
3023  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeysR, nvarsR) );
3024 
3025  /* to get the GUB lifting sequence, we first sort all variables in F, C2, and R
3026  * - F: non-increasing x*_j and non-increasing a_j in case of equality
3027  * - C2: non-increasing a_j
3028  * - R: non-increasing a_j
3029  * furthermore, sort C1 variables as needed for initializing the minweight table (non-increasing a_j).
3030  */
3031 
3032  /* gets sorting key for variables in C1 corresponding to the following ordering
3033  * non-decreasing a_j, i.e. a_1 <= a_2 <= ... <= a_|C_1|
3034  */
3035  for( j = 0; j < nvarsC1; j++ )
3036  {
3037  /* gets sortkeys */
3038  sortkeysC1[j] = (SCIP_Real) weights[varsC1[j]];
3039 
3040  /* update status of variable in its gub constraint */
3041  gubconsidx = gubset->gubconssidx[varsC1[j]];
3042  varidx = gubset->gubvarsidx[varsC1[j]];
3043  gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] = GUBVARSTATUS_BELONGSTOSET_C1;
3044  }
3045 
3046  /* gets sorting key for variables in F corresponding to the following ordering
3047  * non-increasing x*_j, i.e., x*_1 >= x*_2 >= ... >= x*_|F|, and
3048  * non-increasing a_j, i.e., a_1 >= a_2 >= ... >= a_|F| in case of equality
3049  * and updates status of each variable in F in GUB set data structure
3050  */
3051  for( j = 0; j < nvarsF; j++ )
3052  {
3053  /* update status of variable in its gub constraint */
3054  gubconsidx = gubset->gubconssidx[varsF[j]];
3055  varidx = gubset->gubvarsidx[varsF[j]];
3056  gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] = GUBVARSTATUS_BELONGSTOSET_F;
3057  }
3058 
3059  /* gets sorting key for variables in C2 corresponding to the following ordering
3060  * non-increasing a_j, i.e., a_1 >= a_2 >= ... >= a_|C2|
3061  * and updates status of each variable in F in GUB set data structure
3062  */
3063  for( j = 0; j < nvarsC2; j++ )
3064  {
3065  /* gets sortkeys */
3066  sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
3067 
3068  /* update status of variable in its gub constraint */
3069  gubconsidx = gubset->gubconssidx[varsC2[j]];
3070  varidx = gubset->gubvarsidx[varsC2[j]];
3071  gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] = GUBVARSTATUS_BELONGSTOSET_C2;
3072  }
3073 
3074  /* gets sorting key for variables in R corresponding to the following ordering
3075  * non-increasing a_j, i.e., a_1 >= a_2 >= ... >= a_|R|
3076  * and updates status of each variable in F in GUB set data structure
3077  */
3078  for( j = 0; j < nvarsR; j++ )
3079  {
3080  /* gets sortkeys */
3081  sortkeysR[j] = (SCIP_Real) weights[varsR[j]];
3082 
3083  /* update status of variable in its gub constraint */
3084  gubconsidx = gubset->gubconssidx[varsR[j]];
3085  varidx = gubset->gubvarsidx[varsR[j]];
3086  gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] = GUBVARSTATUS_BELONGSTOSET_R;
3087  }
3088 
3089  /* sorts C1, F, C2 and R */
3090  assert(nvarsC1 > 0);
3091  SCIPsortRealInt(sortkeysC1, varsC1, nvarsC1);
3092 
3093  if( nvarsC2 > 0 )
3094  {
3095  SCIPsortDownRealInt(sortkeysC2, varsC2, nvarsC2);
3096  }
3097  if( nvarsR > 0)
3098  {
3099  SCIPsortDownRealInt(sortkeysR, varsR, nvarsR);
3100  }
3101 
3102  /* frees temporary memory */
3103  SCIPfreeBufferArray(scip, &sortkeysR);
3104  SCIPfreeBufferArray(scip, &sortkeysC2);
3105  SCIPfreeBufferArray(scip, &sortkeysC1);
3106 
3107  /* allocate and initialize temporary memory for sorting GUB constraints */
3108  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeypairsGFC1, ngubconss) );
3109  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeypairsGFC1store, ngubconss) );
3110  SCIP_CALL( SCIPallocBufferArray(scip, &nC1varsingubcons, ngubconss) );
3111  BMSclearMemoryArray(nC1varsingubcons, ngubconss);
3112  for( i = 0; i < ngubconss; i++)
3113  {
3114  sortkeypairsGFC1[i] = &(sortkeypairsGFC1store[i]);
3115  sortkeypairsGFC1[i]->key1 = 0.0;
3116  sortkeypairsGFC1[i]->key2 = 0.0;
3117  }
3118  *ngubconsGC1 = 0;
3119  *ngubconsGC2 = 0;
3120  *ngubconsGFC1 = 0;
3121  *ngubconsGR = 0;
3122  *ngubconscapexceed = 0;
3123  *maxgubvarssize = 0;
3124 
3125 #ifndef NDEBUG
3126  for( i = 0; i < gubset->ngubconss; i++ )
3127  assert(gubset->gubconsstatus[i] == GUBCONSSTATUS_UNINITIAL);
3128 #endif
3129 
3130  /* stores GUBs of group GC1 (GOC1+GNC1) and part of the GUBs of group GFC1 (GNC1 GUBs) and sorts variables in these GUBs
3131  * s.t. C1 variables come first (will automatically be sorted by non-decreasing weight).
3132  * gets sorting keys for GUBs of type GFC1 corresponding to the following ordering
3133  * non-increasing number of variables in F, and
3134  * non-increasing max{x*_k : k in GFC1_j} in case of equality
3135  */
3136  for( i = 0; i < nvarsC1; i++ )
3137  {
3138  int nvarsC1capexceed;
3139 
3140  nvarsC1capexceed = 0;
3141 
3142  var = varsC1[i];
3143  gubconsidx = gubset->gubconssidx[var];
3144  varidx = gubset->gubvarsidx[var];
3145 
3146  assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3147  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] == GUBVARSTATUS_BELONGSTOSET_C1);
3148 
3149  /* current C1 variable is put to the front of its GUB where C1 part is stored by non-decreasing weigth;
3150  * note that variables in C1 are already sorted by non-decreasing weigth
3151  */
3152  targetvar = gubset->gubconss[gubconsidx]->gubvars[nC1varsingubcons[gubconsidx]];
3153  GUBsetSwapVars(scip, gubset, var, targetvar);
3154  nC1varsingubcons[gubconsidx]++;
3155 
3156  /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3157  if( gubset->gubconsstatus[gubconsidx] != GUBCONSSTATUS_UNINITIAL )
3158  {
3159  assert(gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GOC1
3160  || gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
3161  continue;
3162  }
3163 
3164  /* determine the status of the current GUB constraint, GOC1 or GNC1; GUBs involving R variables are split into
3165  * GOC1/GNC1 and GF, if wanted. also update sorting key if GUB is of type GFC1 (GNC1)
3166  */
3167 #if GUBSPLITGNC1GUBS
3168  gubconswithF = FALSE;
3169 #endif
3170  for( j = 0; j < gubset->gubconss[gubconsidx]->ngubvars; j++ )
3171  {
3172  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[j] != GUBVARSTATUS_BELONGSTOSET_C2);
3173 
3174  /* C1-variable: update number of C1/capacity exceeding variables */
3175  if( gubset->gubconss[gubconsidx]->gubvarsstatus[j] == GUBVARSTATUS_BELONGSTOSET_C1 )
3176  {
3177  nvarsC1capexceed++;
3178  nvarsprocessed++;
3179  }
3180  /* F-variable: update sort key (number of F variables in GUB) of corresponding GFC1-GUB */
3181  else if( gubset->gubconss[gubconsidx]->gubvarsstatus[j] == GUBVARSTATUS_BELONGSTOSET_F )
3182  {
3183 #if GUBSPLITGNC1GUBS
3184  gubconswithF = TRUE;
3185 #endif
3186  sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3187 
3188  if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3189  sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->gubconss[gubconsidx]->gubvars[j]];
3190  }
3191  else if( gubset->gubconss[gubconsidx]->gubvarsstatus[j] == GUBVARSTATUS_CAPACITYEXCEEDED )
3192  {
3193  nvarsC1capexceed++;
3194  }
3195  else
3196  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[j] == GUBVARSTATUS_BELONGSTOSET_R);
3197  }
3198 
3199  /* update set of GC1 GUBs */
3200  gubconsGC1[*ngubconsGC1] = gubconsidx;
3201  (*ngubconsGC1)++;
3202 
3203  /* update maximum size of all GUB constraints */
3204  if( gubset->gubconss[gubconsidx]->gubvarssize > *maxgubvarssize )
3205  *maxgubvarssize = gubset->gubconss[gubconsidx]->gubvarssize;
3206 
3207  /* set status of GC1-GUB (GOC1 or GNC1) and update set of GFC1 GUBs */
3208  if( nvarsC1capexceed == gubset->gubconss[gubconsidx]->ngubvars )
3209  {
3210  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GOC1;
3211  ngubconsGOC1++;
3212  }
3213  else
3214  {
3215 #if GUBSPLITGNC1GUBS
3216  /* only variables in C1 and R -- no in F: GUB will be split into GR and GOC1 GUBs */
3217  if( !gubconswithF )
3218  {
3219  GUBVARSTATUS movevarstatus;
3220 
3221  assert(gubset->ngubconss < gubset->nvars);
3222 
3223  /* create a new GUB for GR part of splitting */
3224  SCIP_CALL( GUBconsCreate(scip, &gubset->gubconss[gubset->ngubconss]) );
3225  gubset->ngubconss++;
3226  ngubconss = gubset->ngubconss;
3227 
3228  /* fill GR with R variables in current GUB */
3229  for( j = gubset->gubconss[gubconsidx]->ngubvars-1; j >= 0; j-- )
3230  {
3231  movevarstatus = gubset->gubconss[gubconsidx]->gubvarsstatus[j];
3232  if( movevarstatus != GUBVARSTATUS_BELONGSTOSET_C1 )
3233  {
3234  assert(movevarstatus == GUBVARSTATUS_BELONGSTOSET_R || movevarstatus == GUBVARSTATUS_CAPACITYEXCEEDED);
3235  SCIP_CALL( GUBsetMoveVar(scip, gubset, vars, gubset->gubconss[gubconsidx]->gubvars[j],
3236  gubconsidx, ngubconss-1) );
3237  gubset->gubconss[ngubconss-1]->gubvarsstatus[gubset->gubconss[ngubconss-1]->ngubvars-1] =
3238  movevarstatus;
3239  }
3240  }
3241 
3242  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GOC1;
3243  ngubconsGOC1++;
3244 
3245  gubset->gubconsstatus[ngubconss-1] = GUBCONSSTATUS_BELONGSTOSET_GR;
3246  gubconsGR[*ngubconsGR] = ngubconss-1;
3247  (*ngubconsGR)++;
3248  }
3249  /* variables in C1, F, and maybe R: GNC1 GUB */
3250  else
3251  {
3252  assert(gubconswithF);
3253 
3254  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GNC1;
3255  gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3256  (*ngubconsGFC1)++;
3257  }
3258 #else
3259  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GNC1;
3260  gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3261  (*ngubconsGFC1)++;
3262 #endif
3263  }
3264  }
3265 
3266  /* stores GUBs of group GC2 (only trivial GUBs); sorting is not required because the C2 variables (which we loop over)
3267  * are already sorted correctly
3268  */
3269  for( i = 0; i < nvarsC2; i++ )
3270  {
3271  var = varsC2[i];
3272  gubconsidx = gubset->gubconssidx[var];
3273  varidx = gubset->gubvarsidx[var];
3274 
3275  assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3276  assert(gubset->gubconss[gubconsidx]->ngubvars == 1);
3277  assert(varidx == 0);
3278  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] == GUBVARSTATUS_BELONGSTOSET_C2);
3279  assert(gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_UNINITIAL);
3280 
3281  /* set status of GC2 GUB */
3282  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GC2;
3283 
3284  /* update group of GC2 GUBs */
3285  gubconsGC2[*ngubconsGC2] = gubconsidx;
3286  (*ngubconsGC2)++;
3287 
3288  /* update maximum size of all GUB constraints */
3289  if( gubset->gubconss[gubconsidx]->gubvarssize > *maxgubvarssize )
3290  *maxgubvarssize = gubset->gubconss[gubconsidx]->gubvarssize;
3291 
3292  nvarsprocessed++;
3293  }
3294 
3295  /* stores remaining part of the GUBs of group GFC1 (GF GUBs) and gets GUB sorting keys corresp. to following ordering
3296  * non-increasing number of variables in F, and
3297  * non-increasing max{x*_k : k in GFC1_j} in case of equality
3298  */
3299  for( i = 0; i < nvarsF; i++ )
3300  {
3301  var = varsF[i];
3302  gubconsidx = gubset->gubconssidx[var];
3303  varidx = gubset->gubvarsidx[var];
3304 
3305  assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3306  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] == GUBVARSTATUS_BELONGSTOSET_F);
3307 
3308  nvarsprocessed++;
3309 
3310  /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3311  if( gubset->gubconsstatus[gubconsidx] != GUBCONSSTATUS_UNINITIAL )
3312  {
3313  assert(gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GF
3314  || gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
3315  continue;
3316  }
3317 
3318  /* set status of GF GUB */
3319  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GF;
3320 
3321  /* update sorting key of corresponding GFC1 GUB */
3322  for( j = 0; j < gubset->gubconss[gubconsidx]->ngubvars; j++ )
3323  {
3324  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[j] != GUBVARSTATUS_BELONGSTOSET_C2
3325  && gubset->gubconss[gubconsidx]->gubvarsstatus[j] != GUBVARSTATUS_BELONGSTOSET_C1);
3326 
3327  /* F-variable: update sort key (number of F variables in GUB) of corresponding GFC1-GUB */
3328  if( gubset->gubconss[gubconsidx]->gubvarsstatus[j] == GUBVARSTATUS_BELONGSTOSET_F )
3329  {
3330  sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3331 
3332  if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3333  sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->gubconss[gubconsidx]->gubvars[j]];
3334  }
3335  }
3336 
3337  /* update set of GFC1 GUBs */
3338  gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3339  (*ngubconsGFC1)++;
3340 
3341  /* update maximum size of all GUB constraints */
3342  if( gubset->gubconss[gubconsidx]->gubvarssize > *maxgubvarssize )
3343  *maxgubvarssize = gubset->gubconss[gubconsidx]->gubvarssize;
3344  }
3345 
3346  /* stores GUBs of group GR; sorting is not required because the R variables (which we loop over) are already sorted
3347  * correctly
3348  */
3349  for( i = 0; i < nvarsR; i++ )
3350  {
3351  var = varsR[i];
3352  gubconsidx = gubset->gubconssidx[var];
3353  varidx = gubset->gubvarsidx[var];
3354 
3355  assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3356  assert(gubset->gubconss[gubconsidx]->gubvarsstatus[varidx] == GUBVARSTATUS_BELONGSTOSET_R);
3357 
3358  nvarsprocessed++;
3359 
3360  /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3361  if( gubset->gubconsstatus[gubconsidx] != GUBCONSSTATUS_UNINITIAL )
3362  {
3363  assert(gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GR
3364  || gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GF
3365  || gubset->gubconsstatus[gubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
3366  continue;
3367  }
3368 
3369  /* set status of GR GUB */
3370  gubset->gubconsstatus[gubconsidx] = GUBCONSSTATUS_BELONGSTOSET_GR;
3371 
3372  /* update set of GR GUBs */
3373  gubconsGR[*ngubconsGR] = gubconsidx;
3374  (*ngubconsGR)++;
3375 
3376  /* update maximum size of all GUB constraints */
3377  if( gubset->gubconss[gubconsidx]->gubvarssize > *maxgubvarssize )
3378  *maxgubvarssize = gubset->gubconss[gubconsidx]->gubvarssize;
3379  }
3380  assert(nvarsprocessed == nvarsC1 + nvarsC2 + nvarsF + nvarsR);
3381 
3382  /* update number of GUBs with only capacity exceeding variables (will not be used for lifting) */
3383  (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3384  assert(*ngubconscapexceed >= 0);
3385 #ifndef NDEBUG
3386  {
3387  int check;
3388 
3389  check = 0;
3390 
3391  /* remaining not handled GUBs should only contain capacity exceeding variables */
3392  for( i = 0; i < ngubconss; i++ )
3393  {
3394  if( gubset->gubconsstatus[i] == GUBCONSSTATUS_UNINITIAL )
3395  check++;
3396  }
3397  assert(check == *ngubconscapexceed);
3398  }
3399 #endif
3400 
3401  /* sort GFCI GUBs according to computed sorting keys */
3402  if( (*ngubconsGFC1) > 0 )
3403  {
3404  SCIPsortDownPtrInt((void**)sortkeypairsGFC1, gubconsGFC1, compSortkeypairs, (*ngubconsGFC1));
3405  }
3406 
3407  /* free temporary memory */
3408 #if GUBSPLITGNC1GUBS
3409  ngubconss = origngubconss;
3410 #endif
3411  SCIPfreeBufferArray(scip, &nC1varsingubcons);
3412  SCIPfreeBufferArray(scip, &sortkeypairsGFC1store);
3413  SCIPfreeBufferArray(scip, &sortkeypairsGFC1);
3414 
3415  return SCIP_OKAY;
3416 }
3417 
3418 /** enlarges minweight table to at least the given length */
3419 static
3421  SCIP* scip, /**< SCIP data structure */
3422  SCIP_Longint** minweightsptr, /**< pointer to minweights table */
3423  int* minweightslen, /**< pointer to store number of entries in minweights table (incl. z=0) */
3424  int* minweightssize, /**< pointer to current size of minweights table */
3425  int newlen /**< new length of minweights table */
3426  )
3427 {
3428  int j;
3429 
3430  assert(minweightsptr != NULL);
3431  assert(*minweightsptr != NULL);
3432  assert(minweightslen != NULL);
3433  assert(*minweightslen >= 0);
3434  assert(minweightssize != NULL);
3435  assert(*minweightssize >= 0);
3436 
3437  if( newlen > *minweightssize )
3438  {
3439  int newsize;
3440 
3441  /* reallocate table memory */
3442  newsize = SCIPcalcMemGrowSize(scip, newlen);
3443  SCIP_CALL( SCIPreallocBufferArray(scip, minweightsptr, newsize) );
3444  *minweightssize = newsize;
3445  }
3446  assert(newlen <= *minweightssize);
3447 
3448  /* initialize new elements */
3449  for( j = *minweightslen; j < newlen; ++j )
3450  (*minweightsptr)[j] = SCIP_LONGINT_MAX;
3451  *minweightslen = newlen;
3452 
3453  return SCIP_OKAY;
3454 }
3455 
3456 /** lifts given inequality
3457  * sum_{j in M_1} x_j <= alpha_0
3458  * valid for
3459  * S^0 = { x in {0,1}^|M_1| : sum_{j in M_1} a_j x_j <= a_0 - sum_{j in M_2} a_j }
3460  * to a valid inequality
3461  * sum_{j in M_1} x_j + sum_{j in F} alpha_j x_j + sum_{j in M_2} alpha_j x_j + sum_{j in R} alpha_j x_j
3462  * <= alpha_0 + sum_{j in M_2} alpha_j
3463  * for
3464  * S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0 };
3465  * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and
3466  * sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and
3467  * extended weight inequalities.
3468  */
3469 static
3471  SCIP* scip, /**< SCIP data structure */
3472  SCIP_VAR** vars, /**< variables in knapsack constraint */
3473  int nvars, /**< number of variables in knapsack constraint */
3474  int ntightened, /**< number of variables with tightened upper bound */
3475  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
3476  SCIP_Longint capacity, /**< capacity of knapsack */
3477  SCIP_Real* solvals, /**< solution values of all problem variables */
3478  int* varsM1, /**< variables in M_1 */
3479  int* varsM2, /**< variables in M_2 */
3480  int* varsF, /**< variables in F */
3481  int* varsR, /**< variables in R */
3482  int nvarsM1, /**< number of variables in M_1 */
3483  int nvarsM2, /**< number of variables in M_2 */
3484  int nvarsF, /**< number of variables in F */
3485  int nvarsR, /**< number of variables in R */
3486  int alpha0, /**< rights hand side of given valid inequality */
3487  int* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
3488  SCIP_Real* cutact, /**< pointer to store activity of lifted valid inequality */
3489  int* liftrhs /**< pointer to store right hand side of the lifted valid inequality */
3490  )
3491 {
3492  SCIP_Longint* minweights;
3493  SCIP_Real* sortkeys;
3494  SCIP_Longint fixedonesweight;
3495  int minweightssize;
3496  int minweightslen;
3497  int j;
3498  int w;
3499 
3500  assert(scip != NULL);
3501  assert(vars != NULL);
3502  assert(nvars >= 0);
3503  assert(weights != NULL);
3504  assert(capacity >= 0);
3505  assert(solvals != NULL);
3506  assert(varsM1 != NULL);
3507  assert(varsM2 != NULL);
3508  assert(varsF != NULL);
3509  assert(varsR != NULL);
3510  assert(nvarsM1 >= 0 && nvarsM1 <= nvars - ntightened);
3511  assert(nvarsM2 >= 0 && nvarsM2 <= nvars - ntightened);
3512  assert(nvarsF >= 0 && nvarsF <= nvars - ntightened);
3513  assert(nvarsR >= 0 && nvarsR <= nvars - ntightened);
3514  assert(nvarsM1 + nvarsM2 + nvarsF + nvarsR == nvars - ntightened);
3515  assert(alpha0 >= 0);
3516  assert(liftcoefs != NULL);
3517  assert(cutact != NULL);
3518  assert(liftrhs != NULL);
3519 
3520  /* allocates temporary memory */
3521  minweightssize = nvarsM1 + 1;
3522  SCIP_CALL( SCIPallocBufferArray(scip, &minweights, minweightssize) );
3523  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeys, nvarsM1) );
3524 
3525  /* initializes data structures */
3526  BMSclearMemoryArray(liftcoefs, nvars);
3527  *cutact = 0.0;
3528 
3529  /* sets lifting coefficient of variables in M1, sorts variables in M1 such that a_1 <= a_2 <= ... <= a_|M1|
3530  * and calculates activity of the current valid inequality
3531  */
3532  for( j = 0; j < nvarsM1; j++ )
3533  {
3534  assert(liftcoefs[varsM1[j]] == 0);
3535  liftcoefs[varsM1[j]] = 1;
3536  sortkeys[j] = (SCIP_Real) (weights[varsM1[j]]);
3537  (*cutact) += solvals[varsM1[j]];
3538  }
3539 
3540  SCIPsortRealInt(sortkeys, varsM1, nvarsM1);
3541 
3542  /* initializes (i = 1) the minweight table, defined as: minweights_i[w] =
3543  * min sum_{j in M_1} a_j x_j + sum_{k=1}^{i-1} a_{j_k} x_{j_k}
3544  * s.t. sum_{j in M_1} x_j + sum_{k=1}^{i-1} alpha_{j_k} x_{j_k} >= w
3545  * x_j in {0,1} for j in M_1 & {j_i,...,j_i-1},
3546  * for i = 1,...,t with t = |N\M1| and w = 0,...,|M1| + sum_{k=1}^{i-1} alpha_{j_k};
3547  */
3548  minweights[0] = 0;
3549  for( w = 1; w <= nvarsM1; w++ )
3550  minweights[w] = minweights[w-1] + weights[varsM1[w-1]];
3551  minweightslen = nvarsM1 + 1;
3552 
3553  /* gets sum of weights of variables fixed to one, i.e. sum of weights of variables in M_2 */
3554  fixedonesweight = 0;
3555  for( j = 0; j < nvarsM2; j++ )
3556  fixedonesweight += weights[varsM2[j]];
3557  assert(fixedonesweight >= 0);
3558 
3559  /* initializes right hand side of lifted valid inequality */
3560  *liftrhs = alpha0;
3561 
3562  /* sequentially up-lifts all variables in F: */
3563  for( j = 0; j < nvarsF; j++ )
3564  {
3565  SCIP_Longint weight;
3566  int liftvar;
3567  int liftcoef;
3568  int z;
3569 
3570  liftvar = varsF[j];
3571  weight = weights[liftvar];
3572  assert(liftvar >= 0 && liftvar < nvars);
3573  assert(SCIPisFeasGT(scip, solvals[liftvar], 0.0));
3574  assert(weight > 0);
3575 
3576  /* knapsack problem is infeasible:
3577  * sets z = 0
3578  */
3579  if( capacity - fixedonesweight - weight < 0 )
3580  {
3581  z = 0;
3582  }
3583  /* knapsack problem is feasible:
3584  * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
3585  * if minweights_i[liftrhs] <= a_0 - fixedonesweight - a_{j_i}
3586  */
3587  else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
3588  {
3589  z = *liftrhs;
3590  }
3591  /* knapsack problem is feasible:
3592  * uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} }
3593  */
3594  else
3595  {
3596  int left;
3597  int right;
3598  int middle;
3599 
3600  assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3601  left = 0;
3602  right = (*liftrhs) + 1;
3603  while( left < right - 1 )
3604  {
3605  middle = (left + right) / 2;
3606  assert(0 <= middle && middle < minweightslen);
3607  if( minweights[middle] <= capacity - fixedonesweight - weight )
3608  left = middle;
3609  else
3610  right = middle;
3611  }
3612  assert(left == right - 1);
3613  assert(0 <= left && left < minweightslen);
3614  assert(minweights[left] <= capacity - fixedonesweight - weight );
3615  assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
3616 
3617  /* now z = left */
3618  z = left;
3619  assert(z <= *liftrhs);
3620  }
3621 
3622  /* calculates lifting coefficients alpha_{j_i} = liftrhs - z */
3623  liftcoef = (*liftrhs) - z;
3624  liftcoefs[liftvar] = liftcoef;
3625  assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
3626 
3627  /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3628  if( liftcoef == 0 )
3629  continue;
3630 
3631  /* updates activity of current valid inequality */
3632  (*cutact) += liftcoef * solvals[liftvar];
3633 
3634  /* enlarges current minweight table:
3635  * from minweightlen = |M1| + sum_{k=1}^{i-1} alpha_{j_k} + 1 entries
3636  * to |M1| + sum_{k=1}^{i } alpha_{j_k} + 1 entries
3637  * and sets minweights_i[w] = infinity for
3638  * w = |M1| + sum_{k=1}^{i-1} alpha_{j_k} + 1 , ... , |M1| + sum_{k=1}^{i} alpha_{j_k}
3639  */
3640  SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3641 
3642  /* updates minweight table: minweight_i+1[w] =
3643  * min{ minweights_i[w], a_{j_i}}, if w < alpha_j_i
3644  * min{ minweights_i[w], minweights_i[w - alpha_j_i] + a_j_i}, if w >= alpha_j_i
3645  */
3646  for( w = minweightslen - 1; w >= 0; w-- )
3647  {
3648  SCIP_Longint min;
3649  if( w < liftcoef )
3650  {
3651  min = MIN(minweights[w], weight);
3652  minweights[w] = min;
3653  }
3654  else
3655  {
3656  assert(w >= liftcoef);
3657  min = MIN(minweights[w], minweights[w - liftcoef] + weight);
3658  minweights[w] = min;
3659  }
3660  }
3661  }
3662  assert(minweights[0] == 0);
3663 
3664  /* sequentially down-lifts all variables in M_2: */
3665  for( j = 0; j < nvarsM2; j++ )
3666  {
3667  SCIP_Longint weight;
3668  int liftvar;
3669  int liftcoef;
3670  int left;
3671  int right;
3672  int middle;
3673  int z;
3674 
3675  liftvar = varsM2[j];
3676  weight = weights[liftvar];
3677  assert(SCIPisFeasEQ(scip, solvals[liftvar], 1.0));
3678  assert(liftvar >= 0 && liftvar < nvars);
3679  assert(weight > 0);
3680 
3681  /* uses binary search to find
3682  * z = max { w : 0 <= w <= |M_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
3683  */
3684  left = 0;
3685  right = minweightslen;
3686  while( left < right - 1 )
3687  {
3688  middle = (left + right) / 2;
3689  assert(0 <= middle && middle < minweightslen);
3690  if( minweights[middle] <= capacity - fixedonesweight + weight )
3691  left = middle;
3692  else
3693  right = middle;
3694  }
3695  assert(left == right - 1);
3696  assert(0 <= left && left < minweightslen);
3697  assert(minweights[left] <= capacity - fixedonesweight + weight );
3698  assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight + weight);
3699 
3700  /* now z = left */
3701  z = left;
3702  assert(z >= *liftrhs);
3703 
3704  /* calculates lifting coefficients alpha_{j_i} = z - liftrhs */
3705  liftcoef = z - (*liftrhs);
3706  liftcoefs[liftvar] = liftcoef;
3707  assert(liftcoef >= 0);
3708 
3709  /* updates sum of weights of variables fixed to one */
3710  fixedonesweight -= weight;
3711 
3712  /* updates right-hand side of current valid inequality */
3713  (*liftrhs) += liftcoef;
3714  assert(*liftrhs >= alpha0);
3715 
3716  /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3717  if( liftcoef == 0 )
3718  continue;
3719 
3720  /* updates activity of current valid inequality */
3721  (*cutact) += liftcoef * solvals[liftvar];
3722 
3723  /* enlarges current minweight table:
3724  * from minweightlen = |M1| + sum_{k=1}^{i-1} alpha_{j_k} + 1 entries
3725  * to |M1| + sum_{k=1}^{i } alpha_{j_k} + 1 entries
3726  * and sets minweights_i[w] = infinity for
3727  * w = |M1| + sum_{k=1}^{i-1} alpha_{j_k} + 1 , ... , |M1| + sum_{k=1}^{i} alpha_{j_k}
3728  */
3729  SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3730 
3731  /* updates minweight table: minweight_i+1[w] =
3732  * min{ minweights_i[w], a_{j_i}}, if w < alpha_j_i
3733  * min{ minweights_i[w], minweights_i[w - alpha_j_i] + a_j_i}, if w >= alpha_j_i
3734  */
3735  for( w = minweightslen - 1; w >= 0; w-- )
3736  {
3737  SCIP_Longint min;
3738  if( w < liftcoef )
3739  {
3740  min = MIN(minweights[w], weight);
3741  minweights[w] = min;
3742  }
3743  else
3744  {
3745  assert(w >= liftcoef);
3746  min = MIN(minweights[w], minweights[w - liftcoef] + weight);
3747  minweights[w] = min;
3748  }
3749  }
3750  }
3751  assert(fixedonesweight == 0);
3752  assert(*liftrhs >= alpha0);
3753 
3754  /* sequentially up-lifts all variables in R: */
3755  for( j = 0; j < nvarsR; j++ )
3756  {
3757  SCIP_Longint weight;
3758  int liftvar;
3759  int liftcoef;
3760  int z;
3761 
3762  liftvar = varsR[j];
3763  weight = weights[liftvar];
3764  assert(liftvar >= 0 && liftvar < nvars);
3765  assert(SCIPisFeasEQ(scip, solvals[liftvar], 0.0));
3766  assert(weight > 0);
3767  assert(capacity - weight >= 0);
3768  assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
3769 
3770  /* sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} } = liftrhs,
3771  * if minweights_i[liftrhs] <= a_0 - a_{j_i}
3772  */
3773  if( minweights[*liftrhs] <= capacity - weight )
3774  {
3775  z = *liftrhs;
3776  }
3777  /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
3778  */
3779  else
3780  {
3781  int left;
3782  int right;
3783  int middle;
3784 
3785  left = 0;
3786  right = (*liftrhs) + 1;
3787  while( left < right - 1)
3788  {
3789  middle = (left + right) / 2;
3790  assert(0 <= middle && middle < minweightslen);
3791  if( minweights[middle] <= capacity - weight )
3792  left = middle;
3793  else
3794  right = middle;
3795  }
3796  assert(left == right - 1);
3797  assert(0 <= left && left < minweightslen);
3798  assert(minweights[left] <= capacity - weight );
3799  assert(left == minweightslen - 1 || minweights[left+1] > capacity - weight);
3800 
3801  /* now z = left */
3802  z = left;
3803  assert(z <= *liftrhs);
3804  }
3805 
3806  /* calculates lifting coefficients alpha_{j_i} = liftrhs - z */
3807  liftcoef = (*liftrhs) - z;
3808  liftcoefs[liftvar] = liftcoef;
3809  assert(liftcoef >= 0 && liftcoef <= *liftrhs);
3810 
3811  /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3812  if( liftcoef == 0 )
3813  continue;
3814 
3815  /* updates activity of current valid inequality */
3816  (*cutact) += liftcoef * solvals[liftvar];
3817 
3818  /* updates minweight table: minweight_i+1[w] =
3819  * min{ minweight_i[w], a_{j_i}}, if w < alpha_j_i
3820  * min{ minweight_i[w], minweight_i[w - alpha_j_i] + a_j_i}, if w >= alpha_j_i
3821  */
3822  for( w = *liftrhs; w >= 0; w-- )
3823  {
3824  SCIP_Longint min;
3825  if( w < liftcoef )
3826  {
3827  min = MIN(minweights[w], weight);
3828  minweights[w] = min;
3829  }
3830  else
3831  {
3832  assert(w >= liftcoef);
3833  min = MIN(minweights[w], minweights[w - liftcoef] + weight);
3834  minweights[w] = min;
3835  }
3836  }
3837  }
3838 
3839  /* frees temporary memory */
3840  SCIPfreeBufferArray(scip, &sortkeys);
3841  SCIPfreeBufferArray(scip, &minweights);
3842 
3843  return SCIP_OKAY;
3844 }
3845 
3846 /** adds two minweight values in a safe way, i.e,, ensures no overflow */
3847 static
3849  SCIP_Longint val1, /**< first value to add */
3850  SCIP_Longint val2 /**< second value to add */
3851  )
3852 {
3853  assert(val1 >= 0);
3854  assert(val2 >= 0);
3855 
3856  if( val1 >= SCIP_LONGINT_MAX || val2 >= SCIP_LONGINT_MAX )
3857  return SCIP_LONGINT_MAX;
3858  else
3859  {
3860  assert(val1 <= SCIP_LONGINT_MAX - val2);
3861  return (val1 + val2);
3862  }
3863 }
3864 
3865 /** computes minweights table for lifting with GUBs by combining unfished and fished tables */
3866 static
3868  SCIP_Longint* minweights, /**< minweight table to compute */
3869  SCIP_Longint* finished, /**< given finished table */
3870  SCIP_Longint* unfinished, /**< given unfinished table */
3871  int minweightslen /**< length of minweight, finished, and unfinished tables */
3872  )
3873 {
3874  int w1;
3875  int w2;
3876 
3877  /* minweights_i[w] = min{finished_i[w1] + unfinished_i[w2] : w1>=0, w2>=0, w1+w2=w};
3878  * note that finished and unfished arrays sorted by non-decreasing weight
3879  */
3880 
3881  /* initialize minweight with w2 = 0 */
3882  w2 = 0;
3883  assert(unfinished[w2] == 0);
3884  for( w1 = 0; w1 < minweightslen; w1++ )
3885  minweights[w1] = finished[w1];
3886 
3887  /* consider w2 = 1, ..., minweightslen-1 */
3888  for( w2 = 1; w2 < minweightslen; w2++ )
3889  {
3890  if( unfinished[w2] >= SCIP_LONGINT_MAX )
3891  break;
3892 
3893  for( w1 = 0; w1 < minweightslen - w2; w1++ )
3894  {
3895  SCIP_Longint temp;
3896 
3897  temp = safeAddMinweightsGUB(finished[w1], unfinished[w2]);
3898  if( temp <= minweights[w1+w2] )
3899  minweights[w1+w2] = temp;
3900  }
3901  }
3902 }
3903 
3904 /** lifts given inequality
3905  * sum_{j in C_1} x_j <= alpha_0
3906  * valid for
3907  * S^0 = { x in {0,1}^|C_1| : sum_{j in C_1} a_j x_j <= a_0 - sum_{j in C_2} a_j;
3908  * sum_{j in Q_i} x_j <= 1, forall i in I }
3909  * to a valid inequality
3910  * sum_{j in C_1} x_j + sum_{j in F} alpha_j x_j + sum_{j in C_2} alpha_j x_j + sum_{j in R} alpha_j x_j
3911  * <= alpha_0 + sum_{j in C_2} alpha_j
3912  * for
3913  * S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0; sum_{j in Q_i} x_j <= 1, forall i in I };
3914  * uses sequential up-lifting for the variables in GUB constraints in gubconsGFC1,
3915  * sequential down-lifting for the variables in GUB constraints in gubconsGC2, and
3916  * sequential up-lifting for the variabels in GUB constraints in gubconsGR.
3917  */
3918 static
3920  SCIP* scip, /**< SCIP data structure */
3921  SCIP_GUBSET* gubset, /**< GUB set data structure */
3922  SCIP_VAR** vars, /**< variables in knapsack constraint */
3923  int ngubconscapexceed, /**< number of GUBs with only capacity exceeding variables */
3924  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
3925  SCIP_Longint capacity, /**< capacity of knapsack */
3926  SCIP_Real* solvals, /**< solution values of all knapsack variables */
3927  int* gubconsGC1, /**< GUBs in GC1(GNC1+GOC1) */
3928  int* gubconsGC2, /**< GUBs in GC2 */
3929  int* gubconsGFC1, /**< GUBs in GFC1(GNC1+GF) */
3930  int* gubconsGR, /**< GUBs in GR */
3931  int ngubconsGC1, /**< number of GUBs in GC1(GNC1+GOC1) */
3932  int ngubconsGC2, /**< number of GUBs in GC2 */
3933  int ngubconsGFC1, /**< number of GUBs in GFC1(GNC1+GF) */
3934  int ngubconsGR, /**< number of GUBs in GR */
3935  int alpha0, /**< rights hand side of given valid inequality */
3936  int* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
3937  SCIP_Real* cutact, /**< pointer to store activity of lifted valid inequality */
3938  int* liftrhs, /**< pointer to store right hand side of the lifted valid inequality */
3939  int maxgubvarssize /**< maximal size of GUB constraints */
3940  )
3941 {
3942  SCIP_Longint* minweights;
3943  SCIP_Longint* finished;
3944  SCIP_Longint* unfinished;
3945  int* gubconsGOC1;
3946  int* gubconsGNC1;
3947  int* liftgubvars;
3948  SCIP_Longint fixedonesweight;
3949  SCIP_Longint weight;
3950  SCIP_Longint weightdiff1;
3951  SCIP_Longint weightdiff2;
3952  SCIP_Longint min;
3953  int minweightssize;
3954  int minweightslen;
3955  int nvars;
3956  int varidx;
3957  int liftgubconsidx;
3958  int liftvar;
3959  int sumliftcoef;
3960  int liftcoef;
3961  int ngubconsGOC1;
3962  int ngubconsGNC1;
3963  int left;
3964  int right;
3965  int middle;
3966  int nliftgubvars;
3967  int tmplen;
3968  int tmpsize;
3969  int j;
3970  int k;
3971  int w;
3972  int z;
3973 #ifndef NDEBUG
3974  int ngubconss;
3975  int nliftgubC1;
3976 
3977  assert(gubset != NULL);
3978  ngubconss = gubset->ngubconss;
3979 #else
3980  assert(gubset != NULL);
3981 #endif
3982 
3983  nvars = gubset->nvars;
3984 
3985  assert(scip != NULL);
3986  assert(vars != NULL);
3987  assert(nvars >= 0);
3988  assert(weights != NULL);
3989  assert(capacity >= 0);
3990  assert(solvals != NULL);
3991  assert(gubconsGC1 != NULL);
3992  assert(gubconsGC2 != NULL);
3993  assert(gubconsGFC1 != NULL);
3994  assert(gubconsGR != NULL);
3995  assert(ngubconsGC1 >= 0 && ngubconsGC1 <= ngubconss - ngubconscapexceed);
3996  assert(ngubconsGC2 >= 0 && ngubconsGC2 <= ngubconss - ngubconscapexceed);
3997  assert(ngubconsGFC1 >= 0 && ngubconsGFC1 <= ngubconss - ngubconscapexceed);
3998  assert(ngubconsGR >= 0 && ngubconsGR <= ngubconss - ngubconscapexceed);
3999  assert(alpha0 >= 0);
4000  assert(liftcoefs != NULL);
4001  assert(cutact != NULL);
4002  assert(liftrhs != NULL);
4003 
4004  minweightssize = ngubconsGC1+1;
4005 
4006  /* allocates temporary memory */
4007  SCIP_CALL( SCIPallocBufferArray(scip, &liftgubvars, maxgubvarssize) );
4008  SCIP_CALL( SCIPallocBufferArray(scip, &gubconsGOC1, ngubconsGC1) );
4009  SCIP_CALL( SCIPallocBufferArray(scip, &gubconsGNC1, ngubconsGC1) );
4010  SCIP_CALL( SCIPallocBufferArray(scip, &minweights, minweightssize) );
4011  SCIP_CALL( SCIPallocBufferArray(scip, &finished, minweightssize) );
4012  SCIP_CALL( SCIPallocBufferArray(scip, &unfinished, minweightssize) );
4013 
4014  /* initializes data structures */
4015  BMSclearMemoryArray(liftcoefs, nvars);
4016  *cutact = 0.0;
4017 
4018  /* gets GOC1 and GNC1 GUBs, sets lifting coefficient of variables in C1 and calculates activity of the current
4019  * valid inequality
4020  */
4021  ngubconsGOC1 = 0;
4022  ngubconsGNC1 = 0;
4023  for( j = 0; j < ngubconsGC1; j++ )
4024  {
4025  if( gubset->gubconsstatus[gubconsGC1[j]] == GUBCONSSTATUS_BELONGSTOSET_GOC1 )
4026  {
4027  gubconsGOC1[ngubconsGOC1] = gubconsGC1[j];
4028  ngubconsGOC1++;
4029  }
4030  else
4031  {
4032  assert(gubset->gubconsstatus[gubconsGC1[j]] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
4033  gubconsGNC1[ngubconsGNC1] = gubconsGC1[j];
4034  ngubconsGNC1++;
4035  }
4036  for( k = 0; k < gubset->gubconss[gubconsGC1[j]]->ngubvars
4037  && gubset->gubconss[gubconsGC1[j]]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_C1; k++ )
4038  {
4039  varidx = gubset->gubconss[gubconsGC1[j]]->gubvars[k];
4040  assert(varidx >= 0 && varidx < nvars);
4041  assert(liftcoefs[varidx] == 0);
4042 
4043  liftcoefs[varidx] = 1;
4044  (*cutact) += solvals[varidx];
4045  }
4046  assert(k >= 1);
4047  }
4048  assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4049  assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4050 
4051  /* initialize the minweight tables, defined as: for i = 1,...,m with m = |I| and w = 0,...,|gubconsGC1|;
4052  * - finished_i[w] =
4053  * min sum_{k = 1,2,...,i-1} sum_{j in Q_k} a_j x_j
4054  * s.t. sum_{k = 1,2,...,i-1} sum_{j in Q_k} alpha_j x_j >= w
4055  * sum_{j in Q_k} x_j <= 1
4056  * x_j in {0,1} forall j in Q_k forall k = 1,2,...,i-1,
4057  * - unfinished_i[w] =
4058  * min sum_{k = i+1,...,m} sum_{j in Q_k && j in C1} a_j x_j
4059  * s.t. sum_{k = i+1,...,m} sum_{j in Q_k && j in C1} x_j >= w
4060  * sum_{j in Q_k} x_j <= 1
4061  * x_j in {0,1} forall j in Q_k forall k = 1,2,...,i-1,
4062  * - minweights_i[w] = min{finished_i[w1] + unfinished_i[w2] : w1>=0, w2>=0, w1+w2=w};
4063  */
4064 
4065  /* initialize finished table; note that variables in GOC1 GUBs (includes C1 and capacity exceeding variables)
4066  * are sorted s.t. C1 variables come first and are sorted by non-decreasing weight.
4067  * GUBs in the group GCI are sorted by non-decreasing min{ a_k : k in GC1_j } where min{ a_k : k in GC1_j } always
4068  * comes from the first variable in the GUB
4069  */
4070  assert(ngubconsGOC1 <= ngubconsGC1);
4071  finished[0] = 0;
4072  for( w = 1; w <= ngubconsGOC1; w++ )
4073  {
4074  liftgubconsidx = gubconsGOC1[w-1];
4075 
4076  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GOC1);
4077  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[0] == GUBVARSTATUS_BELONGSTOSET_C1);
4078 
4079  varidx = gubset->gubconss[liftgubconsidx]->gubvars[0];
4080 
4081  assert(varidx >= 0 && varidx < nvars);
4082  assert(liftcoefs[varidx] == 1);
4083 
4084  min = weights[varidx];
4085  finished[w] = finished[w-1] + min;
4086 
4087 #ifndef NDEBUG
4088  for( k = 1; k < gubset->gubconss[liftgubconsidx]->ngubvars
4089  && gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_C1; k++ )
4090  {
4091  varidx = gubset->gubconss[liftgubconsidx]->gubvars[k];
4092  assert(varidx >= 0 && varidx < nvars);
4093  assert(liftcoefs[varidx] == 1);
4094  assert(weights[varidx] >= min);
4095  }
4096 #endif
4097  }
4098  for( w = ngubconsGOC1+1; w <= ngubconsGC1; w++ )
4099  finished[w] = SCIP_LONGINT_MAX;
4100 
4101  /* initialize unfinished table; note that variables in GNC1 GUBs
4102  * are sorted s.t. C1 variables come first and are sorted by non-decreasing weight.
4103  * GUBs in the group GCI are sorted by non-decreasing min{ a_k : k in GC1_j } where min{ a_k : k in GC1_j } always
4104  * comes from the first variable in the GUB
4105  */
4106  assert(ngubconsGNC1 <= ngubconsGC1);
4107  unfinished[0] = 0;
4108  for( w = 1; w <= ngubconsGNC1; w++ )
4109  {
4110  liftgubconsidx = gubconsGNC1[w-1];
4111 
4112  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
4113  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[0] == GUBVARSTATUS_BELONGSTOSET_C1);
4114 
4115  varidx = gubset->gubconss[liftgubconsidx]->gubvars[0];
4116 
4117  assert(varidx >= 0 && varidx < nvars);
4118  assert(liftcoefs[varidx] == 1);
4119 
4120  min = weights[varidx];
4121  unfinished[w] = unfinished[w-1] + min;
4122 
4123 #ifndef NDEBUG
4124  for( k = 1; k < gubset->gubconss[liftgubconsidx]->ngubvars
4125  && gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_C1; k++ )
4126  {
4127  varidx = gubset->gubconss[liftgubconsidx]->gubvars[k];
4128  assert(varidx >= 0 && varidx < nvars);
4129  assert(liftcoefs[varidx] == 1);
4130  assert(weights[varidx] >= min );
4131  }
4132 #endif
4133  }
4134  for( w = ngubconsGNC1 + 1; w <= ngubconsGC1; w++ )
4135  unfinished[w] = SCIP_LONGINT_MAX;
4136 
4137  /* initialize minweights table; note that variables in GC1 GUBs
4138  * are sorted s.t. C1 variables come first and are sorted by non-decreasing weight.
4139  * we can directly initialize minweights instead of computing it from finished and unfinished (which would be more time
4140  * consuming) because is it has to be build using weights from C1 only.
4141  */
4142  assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4143  minweights[0] = 0;
4144  for( w = 1; w <= ngubconsGC1; w++ )
4145  {
4146  liftgubconsidx = gubconsGC1[w-1];
4147 
4148  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GOC1
4149  || gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
4150  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[0] == GUBVARSTATUS_BELONGSTOSET_C1);
4151 
4152  varidx = gubset->gubconss[liftgubconsidx]->gubvars[0];
4153 
4154  assert(varidx >= 0 && varidx < nvars);
4155  assert(liftcoefs[varidx] == 1);
4156 
4157  min = weights[varidx];
4158  minweights[w] = minweights[w-1] + min;
4159 
4160 #ifndef NDEBUG
4161  for( k = 1; k < gubset->gubconss[liftgubconsidx]->ngubvars
4162  && gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_C1; k++ )
4163  {
4164  varidx = gubset->gubconss[liftgubconsidx]->gubvars[k];
4165  assert(varidx >= 0 && varidx < nvars);
4166  assert(liftcoefs[varidx] == 1);
4167  assert(weights[varidx] >= min);
4168  }
4169 #endif
4170  }
4171  minweightslen = ngubconsGC1 + 1;
4172 
4173  /* gets sum of weights of variables fixed to one, i.e. sum of weights of C2 variables GC2 GUBs */
4174  fixedonesweight = 0;
4175  for( j = 0; j < ngubconsGC2; j++ )
4176  {
4177  varidx = gubset->gubconss[gubconsGC2[j]]->gubvars[0];
4178 
4179  assert(gubset->gubconss[gubconsGC2[j]]->ngubvars == 1);
4180  assert(varidx >= 0 && varidx < nvars);
4181  assert(gubset->gubconss[gubconsGC2[j]]->gubvarsstatus[0] == GUBVARSTATUS_BELONGSTOSET_C2);
4182 
4183  fixedonesweight += weights[varidx];
4184  }
4185  assert(fixedonesweight >= 0);
4186 
4187  /* initializes right hand side of lifted valid inequality */
4188  *liftrhs = alpha0;
4189 
4190  /* sequentially up-lifts all variables in GFC1 GUBs */
4191  for( j = 0; j < ngubconsGFC1; j++ )
4192  {
4193  liftgubconsidx = gubconsGFC1[j];
4194  assert(liftgubconsidx >= 0 && liftgubconsidx < ngubconss);
4195 
4196  /* GNC1 GUB: update unfinished table (remove current GUB, i.e., remove min weight of C1 vars in GUB) and
4197  * compute minweight table via updated unfinished table and aleady upto date finished table;
4198  */
4199  k = 0;
4200  if( gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1 )
4201  {
4202  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1);
4203  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[0] == GUBVARSTATUS_BELONGSTOSET_C1);
4204  assert(ngubconsGNC1 > 0);
4205 
4206  /* get number of C1 variables of current GNC1 GUB and put them into array of variables in GUB that
4207  * are considered for the lifting, i.e., not capacity exceeding
4208  */
4209  for( ; k < gubset->gubconss[liftgubconsidx]->ngubvars
4210  && gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_C1; k++ )
4211  liftgubvars[k] = gubset->gubconss[liftgubconsidx]->gubvars[k];
4212  assert(k >= 1);
4213 
4214  /* update unfinished table by removing current GNC1 GUB, i.e, remove C1 variable with minimal weight
4215  * unfinished[w] = MAX{unfinished[w], unfinished[w+1] - weight}, "weight" is the minimal weight of current GUB
4216  */
4217  weight = weights[liftgubvars[0]];
4218 
4219  weightdiff2 = unfinished[ngubconsGNC1] - weight;
4220  unfinished[ngubconsGNC1] = SCIP_LONGINT_MAX;
4221  for( w = ngubconsGNC1-1; w >= 1; w-- )
4222  {
4223  weightdiff1 = weightdiff2;
4224  weightdiff2 = unfinished[w] - weight;
4225 
4226  if( unfinished[w] < weightdiff1 )
4227  unfinished[w] = weightdiff1;
4228  else
4229  break;
4230  }
4231  ngubconsGNC1--;
4232 
4233  /* computes minweights table by combining unfished and fished tables */
4234  computeMinweightsGUB(minweights, finished, unfinished, minweightslen);
4235  assert(minweights[0] == 0);
4236  }
4237  /* GF GUB: no update of unfinished table (and minweight table) required because GF GUBs have no C1 variables and
4238  * are therefore not in the unfinished table
4239  */
4240  else
4241  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GF);
4242 
4243 #ifndef NDEBUG
4244  nliftgubC1 = k;
4245 #endif
4246  nliftgubvars = k;
4247  sumliftcoef = 0;
4248 
4249  /* compute lifting coefficient of F and R variables in GNC1 and GF GUBs (C1 vars have already liftcoef 1) */
4250  for( ; k < gubset->gubconss[liftgubconsidx]->ngubvars; k++ )
4251  {
4252  if( gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_F
4253  || gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_R )
4254  {
4255  liftvar = gubset->gubconss[liftgubconsidx]->gubvars[k];
4256  weight = weights[liftvar];
4257  assert(weight > 0);
4258  assert(liftvar >= 0 && liftvar < nvars);
4259  assert(capacity - weight >= 0);
4260 
4261  /* put variable into array of variables in GUB that are considered for the lifting,
4262  * i.e., not capacity exceeding
4263  */
4264  liftgubvars[nliftgubvars] = liftvar;
4265  nliftgubvars++;
4266 
4267  /* knapsack problem is infeasible:
4268  * sets z = 0
4269  */
4270  if( capacity - fixedonesweight - weight < 0 )
4271  {
4272  z = 0;
4273  }
4274  /* knapsack problem is feasible:
4275  * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
4276  * if minweights_i[liftrhs] <= a_0 - fixedonesweight - a_{j_i}
4277  */
4278  else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
4279  {
4280  z = *liftrhs;
4281  }
4282  /* knapsack problem is feasible:
4283  * binary search to find z = max {w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i}}
4284  */
4285  else
4286  {
4287  assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4288  left = 0;
4289  right = (*liftrhs) + 1;
4290  while( left < right - 1 )
4291  {
4292  middle = (left + right) / 2;
4293  assert(0 <= middle && middle < minweightslen);
4294  if( minweights[middle] <= capacity - fixedonesweight - weight )
4295  left = middle;
4296  else
4297  right = middle;
4298  }
4299  assert(left == right - 1);
4300  assert(0 <= left && left < minweightslen);
4301  assert(minweights[left] <= capacity - fixedonesweight - weight);
4302  assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
4303 
4304  /* now z = left */
4305  z = left;
4306  assert(z <= *liftrhs);
4307  }
4308 
4309  /* calculates lifting coefficients alpha_{j_i} = liftrhs - z */
4310  liftcoef = (*liftrhs) - z;
4311  liftcoefs[liftvar] = liftcoef;
4312  assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4313 
4314  /* updates activity of current valid inequality */
4315  (*cutact) += liftcoef * solvals[liftvar];
4316 
4317  /* updates sum of all lifting coefficients in GUB */
4318  sumliftcoef += liftcoefs[liftvar];
4319  }
4320  else
4321  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_CAPACITYEXCEEDED);
4322  }
4323  /* at least one variable is in F or R (j = number of C1 variables in current GUB) */
4324  assert(nliftgubvars > nliftgubC1);
4325 
4326  /* activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0
4327  * and finished and minweight table can be updated easily as only C1 variables need to be considered;
4328  * not needed for GF GUBs
4329  */
4330  if( sumliftcoef == 0 )
4331  {
4332  if( gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GNC1 )
4333  {
4334  weight = weights[liftgubvars[0]];
4335  /* update finished table and minweights table by applying special case of
4336  * finished[w] = MIN{finished[w], finished[w-1] + weight}, "weight" is the minimal weight of current GUB
4337  * minweights[w] = MIN{minweights[w], minweights[w-1] + weight}, "weight" is the minimal weight of current GUB
4338  */
4339  for( w = minweightslen-1; w >= 1; w-- )
4340  {
4341  SCIP_Longint tmpval;
4342 
4343  tmpval = safeAddMinweightsGUB(finished[w-1], weight);
4344  finished[w] = MIN(finished[w], tmpval);
4345 
4346  tmpval = safeAddMinweightsGUB(minweights[w-1], weight);
4347  minweights[w] = MIN(minweights[w], tmpval);
4348  }
4349  }
4350  else
4351  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GF);
4352 
4353  continue;
4354  }
4355 
4356  /* enlarges current minweights tables(finished, unfinished, minweights):
4357  * from minweightlen = |gubconsGC1| + sum_{k=1,2,...,i-1}sum_{j in Q_k} alpha_j + 1 entries
4358  * to |gubconsGC1| + sum_{k=1,2,...,i }sum_{j in Q_k} alpha_j + 1 entries
4359  * and sets minweights_i[w] = infinity for
4360  * w = |gubconsGC1| + sum_{k=1,2,..,i-1}sum_{j in Q_k} alpha_j+1,..,|C1| + sum_{k=1,2,..,i}sum_{j in Q_k} alpha_j
4361  */
4362  tmplen = minweightslen; /* will be updated in enlargeMinweights() */
4363  tmpsize = minweightssize;
4364  SCIP_CALL( enlargeMinweights(scip, &unfinished, &tmplen, &tmpsize, tmplen + sumliftcoef) );
4365  tmplen = minweightslen;
4366  tmpsize = minweightssize;
4367  SCIP_CALL( enlargeMinweights(scip, &finished, &tmplen, &tmpsize, tmplen + sumliftcoef) );
4368  SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + sumliftcoef) );
4369 
4370  /* update finished table and minweight table;
4371  * note that instead of computing minweight table from updated finished and updated unfinished table again
4372  * (for the lifting coefficient, we had to update unfinished table and compute minweight table), we here
4373  * only need to update the minweight table and the updated finished in the same way (i.e., computing for minweight
4374  * not needed because only finished table changed at this point and the change was "adding" one weight)
4375  *
4376  * update formular for minweight table is: minweight_i+1[w] =
4377  * min{ minweights_i[w], min{ minweights_i[w - alpha_k]^{+} + a_k : k in GUB_j_i } }
4378  * formular for finished table has the same pattern.
4379  */
4380  for( w = minweightslen-1; w >= 0; w-- )
4381  {
4382  SCIP_Longint minminweight;
4383  SCIP_Longint minfinished;
4384 
4385  for( k = 0; k < nliftgubvars; k++ )
4386  {
4387  liftcoef = liftcoefs[liftgubvars[k]];
4388  weight = weights[liftgubvars[k]];
4389 
4390  if( w < liftcoef )
4391  {
4392  minfinished = MIN(finished[w], weight);
4393  minminweight = MIN(minweights[w], weight);
4394 
4395  finished[w] = minfinished;
4396  minweights[w] = minminweight;
4397  }
4398  else
4399  {
4400  SCIP_Longint tmpval;
4401 
4402  assert(w >= liftcoef);
4403 
4404  tmpval = safeAddMinweightsGUB(finished[w-liftcoef], weight);
4405  minfinished = MIN(finished[w], tmpval);
4406 
4407  tmpval = safeAddMinweightsGUB(minweights[w-liftcoef], weight);
4408  minminweight = MIN(minweights[w], tmpval);
4409 
4410  finished[w] = minfinished;
4411  minweights[w] = minminweight;
4412  }
4413  }
4414  }
4415  assert(minweights[0] == 0);
4416  }
4417  assert(ngubconsGNC1 == 0);
4418 
4419  /* note: now the unfinished table no longer exists, i.e., it is "0, MAX, MAX, ..." and minweight equals to finished;
4420  * therefore, only work with minweight table from here on
4421  */
4422 
4423  /* sequentially down-lifts C2 variables contained in trivial GC2 GUBs */
4424  for( j = 0; j < ngubconsGC2; j++ )
4425  {
4426  liftgubconsidx = gubconsGC2[j];
4427 
4428  assert(liftgubconsidx >=0 && liftgubconsidx < ngubconss);
4429  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GC2);
4430  assert(gubset->gubconss[liftgubconsidx]->ngubvars == 1);
4431  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[0] == GUBVARSTATUS_BELONGSTOSET_C2);
4432 
4433  liftvar = gubset->gubconss[liftgubconsidx]->gubvars[0]; /* C2 GUBs contain only one variable */
4434  weight = weights[liftvar];
4435 
4436  assert(liftvar >= 0 && liftvar < nvars);
4437  assert(SCIPisFeasEQ(scip, solvals[liftvar], 1.0));
4438  assert(weight > 0);
4439 
4440  /* uses binary search to find
4441  * z = max { w : 0 <= w <= |C_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
4442  */
4443  left = 0;
4444  right = minweightslen;
4445  while( left < right - 1 )
4446  {
4447  middle = (left + right) / 2;
4448  assert(0 <= middle && middle < minweightslen);
4449  if( minweights[middle] <= capacity - fixedonesweight + weight )
4450  left = middle;
4451  else
4452  right = middle;
4453  }
4454  assert(left == right - 1);
4455  assert(0 <= left && left < minweightslen);
4456  assert(minweights[left] <= capacity - fixedonesweight + weight);
4457  assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4458 
4459  /* now z = left */
4460  z = left;
4461  assert(z >= *liftrhs);
4462 
4463  /* calculates lifting coefficients alpha_{j_i} = z - liftrhs */
4464  liftcoef = z - (*liftrhs);
4465  liftcoefs[liftvar] = liftcoef;
4466  assert(liftcoef >= 0);
4467 
4468  /* updates sum of weights of variables fixed to one */
4469  fixedonesweight -= weight;
4470 
4471  /* updates right-hand side of current valid inequality */
4472  (*liftrhs) += liftcoef;
4473  assert(*liftrhs >= alpha0);
4474 
4475  /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
4476  if( liftcoef == 0 )
4477  continue;
4478 
4479  /* updates activity of current valid inequality */
4480  (*cutact) += liftcoef * solvals[liftvar];
4481 
4482  /* enlarges current minweight table:
4483  * from minweightlen = |gubconsGC1| + sum_{k=1,2,...,i-1}sum_{j in Q_k} alpha_j + 1 entries
4484  * to |gubconsGC1| + sum_{k=1,2,...,i }sum_{j in Q_k} alpha_j + 1 entries
4485  * and sets minweights_i[w] = infinity for
4486  * w = |C1| + sum_{k=1,2,...,i-1}sum_{j in Q_k} alpha_j + 1 , ... , |C1| + sum_{k=1,2,...,i}sum_{j in Q_k} alpha_j
4487  */
4488  SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
4489 
4490  /* updates minweight table: minweight_i+1[w] =
4491  * min{ minweights_i[w], a_{j_i}}, if w < alpha_j_i
4492  * min{ minweights_i[w], minweights_i[w - alpha_j_i] + a_j_i}, if w >= alpha_j_i
4493  */
4494  for( w = minweightslen - 1; w >= 0; w-- )
4495  {
4496  if( w < liftcoef )
4497  {
4498  min = MIN(minweights[w], weight);
4499  minweights[w] = min;
4500  }
4501  else
4502  {
4503  SCIP_Longint tmpval;
4504 
4505  assert(w >= liftcoef);
4506 
4507  tmpval = safeAddMinweightsGUB(minweights[w-liftcoef], weight);
4508  min = MIN(minweights[w], tmpval);
4509  minweights[w] = min;
4510  }
4511  }
4512  }
4513  assert(fixedonesweight == 0);
4514  assert(*liftrhs >= alpha0);
4515 
4516  /* sequentially up-lifts variables in GUB constraints in GR GUBs */
4517  for( j = 0; j < ngubconsGR; j++ )
4518  {
4519  liftgubconsidx = gubconsGR[j];
4520 
4521  assert(liftgubconsidx >=0 && liftgubconsidx < ngubconss);
4522  assert(gubset->gubconsstatus[liftgubconsidx] == GUBCONSSTATUS_BELONGSTOSET_GR);
4523 
4524  sumliftcoef = 0;
4525  nliftgubvars = 0;
4526  for( k = 0; k < gubset->gubconss[liftgubconsidx]->ngubvars; k++ )
4527  {
4528  if(gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_BELONGSTOSET_R )
4529  {
4530  liftvar = gubset->gubconss[liftgubconsidx]->gubvars[k];
4531  weight = weights[liftvar];
4532  assert(weight > 0);
4533  assert(liftvar >= 0 && liftvar < nvars);
4534  assert(capacity - weight >= 0);
4535  assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
4536 
4537  /* put variable into array of variables in GUB that are considered for the lifting,
4538  * i.e., not capacity exceeding
4539  */
4540  liftgubvars[nliftgubvars] = liftvar;
4541  nliftgubvars++;
4542 
4543  /* sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} } = liftrhs,
4544  * if minweights_i[liftrhs] <= a_0 - a_{j_i}
4545  */
4546  if( minweights[*liftrhs] <= capacity - weight )
4547  {
4548  z = *liftrhs;
4549  }
4550  /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
4551  */
4552  else
4553  {
4554  left = 0;
4555  right = (*liftrhs) + 1;
4556  while( left < right - 1 )
4557  {
4558  middle = (left + right) / 2;
4559  assert(0 <= middle && middle < minweightslen);
4560  if( minweights[middle] <= capacity - weight )
4561  left = middle;
4562  else
4563  right = middle;
4564  }
4565  assert(left == right - 1);
4566  assert(0 <= left && left < minweightslen);
4567  assert(minweights[left] <= capacity - weight);
4568  assert(left == minweightslen - 1 || minweights[left + 1] > capacity - weight);
4569 
4570  /* now z = left */
4571  z = left;
4572  assert(z <= *liftrhs);
4573  }
4574  /* calculates lifting coefficients alpha_{j_i} = liftrhs - z */
4575  liftcoef = (*liftrhs) - z;
4576  liftcoefs[liftvar] = liftcoef;
4577  assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4578 
4579  /* updates activity of current valid inequality */
4580  (*cutact) += liftcoef * solvals[liftvar];
4581 
4582  /* updates sum of all lifting coefficients in GUB */
4583  sumliftcoef += liftcoefs[liftvar];
4584  }
4585  else
4586  assert(gubset->gubconss[liftgubconsidx]->gubvarsstatus[k] == GUBVARSTATUS_CAPACITYEXCEEDED);
4587  }
4588  assert(nliftgubvars >= 1); /* at least one variable is in R */
4589 
4590  /* minweight table and activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0 */
4591  if( sumliftcoef == 0 )
4592  continue;
4593 
4594  /* updates minweight table: minweight_i+1[w] =
4595  * min{ minweights_i[w], min{ minweights_i[w - alpha_k]^{+} + a_k : k in GUB_j_i } }
4596  */
4597  for( w = *liftrhs; w >= 0; w-- )
4598  {
4599  for( k = 0; k < nliftgubvars; k++ )
4600  {
4601  liftcoef = liftcoefs[liftgubvars[k]];
4602  weight = weights[liftgubvars[k]];
4603 
4604  if( w < liftcoef )
4605  {
4606  min = MIN(minweights[w], weight);
4607  minweights[w] = min;
4608  }
4609  else
4610  {
4611  SCIP_Longint tmpval;
4612 
4613  assert(w >= liftcoef);
4614 
4615  tmpval = safeAddMinweightsGUB(minweights[w-liftcoef], weight);
4616  min = MIN(minweights[w], tmpval);
4617  minweights[w] = min;
4618  }
4619  }
4620  }
4621  assert(minweights[0] == 0);
4622  }
4623 
4624  /* frees temporary memory */
4625  SCIPfreeBufferArray(scip, &minweights);
4626  SCIPfreeBufferArray(scip, &finished);
4627  SCIPfreeBufferArray(scip, &unfinished);
4628  SCIPfreeBufferArray(scip, &liftgubvars);
4629  SCIPfreeBufferArray(scip, &gubconsGOC1 );
4630  SCIPfreeBufferArray(scip, &gubconsGNC1);
4631 
4632  return SCIP_OKAY;
4633 }
4634 
4635 /** lifts given minimal cover inequality
4636  * \f[
4637  * \sum_{j \in C} x_j \leq |C| - 1
4638  * \f]
4639  * valid for
4640  * \f[
4641  * S^0 = \{ x \in {0,1}^{|C|} : \sum_{j \in C} a_j x_j \leq a_0 \}
4642  * \f]
4643  * to a valid inequality
4644  * \f[
4645  * \sum_{j \in C} x_j + \sum_{j \in N \setminus C} \alpha_j x_j \leq |C| - 1
4646  * \f]
4647  * for
4648  * \f[
4649  * S = \{ x \in {0,1}^{|N|} : \sum_{j \in N} a_j x_j \leq a_0 \};
4650  * \f]
4651  * uses superadditive up-lifting for the variables in \f$N \setminus C\f$.
4652  */
4653 static
4655  SCIP* scip, /**< SCIP data structure */
4656  SCIP_VAR** vars, /**< variables in knapsack constraint */
4657  int nvars, /**< number of variables in knapsack constraint */
4658  int ntightened, /**< number of variables with tightened upper bound */
4659  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
4660  SCIP_Longint capacity, /**< capacity of knapsack */
4661  SCIP_Real* solvals, /**< solution values of all problem variables */
4662  int* covervars, /**< cover variables */
4663  int* noncovervars, /**< noncover variables */
4664  int ncovervars, /**< number of cover variables */
4665  int nnoncovervars, /**< number of noncover variables */
4666  SCIP_Longint coverweight, /**< weight of cover */
4667  SCIP_Real* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
4668  SCIP_Real* cutact /**< pointer to store activity of lifted valid inequality */
4669  )
4670 {
4671  SCIP_Longint* maxweightsums;
4672  SCIP_Longint* intervalends;
4673  SCIP_Longint* rhos;
4674  SCIP_Real* sortkeys;
4675  SCIP_Longint lambda;
4676  int j;
4677  int h;
4678 
4679  assert(scip != NULL);
4680  assert(vars != NULL);
4681  assert(nvars >= 0);
4682  assert(weights != NULL);
4683  assert(capacity >= 0);
4684  assert(solvals != NULL);
4685  assert(covervars != NULL);
4686  assert(noncovervars != NULL);
4687  assert(ncovervars > 0 && ncovervars <= nvars);
4688  assert(nnoncovervars >= 0 && nnoncovervars <= nvars - ntightened);
4689  assert(ncovervars + nnoncovervars == nvars - ntightened);
4690  assert(liftcoefs != NULL);
4691  assert(cutact != NULL);
4692 
4693  /* allocates temporary memory */
4694  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeys, ncovervars) );
4695  SCIP_CALL( SCIPallocBufferArray(scip, &maxweightsums, ncovervars + 1) );
4696  SCIP_CALL( SCIPallocBufferArray(scip, &intervalends, ncovervars) );
4697  SCIP_CALL( SCIPallocBufferArray(scip, &rhos, ncovervars) );
4698 
4699  /* initializes data structures */
4700  BMSclearMemoryArray(liftcoefs, nvars);
4701  *cutact = 0.0;
4702 
4703  /* sets lifting coefficient of variables in C, sorts variables in C such that a_1 >= a_2 >= ... >= a_|C|
4704  * and calculates activity of current valid inequality
4705  */
4706  for( j = 0; j < ncovervars; j++ )
4707  {
4708  assert(liftcoefs[covervars[j]] == 0.0);
4709  liftcoefs[covervars[j]] = 1.0;
4710  sortkeys[j] = (SCIP_Real) weights[covervars[j]];
4711  (*cutact) += solvals[covervars[j]];
4712  }
4713  SCIPsortDownRealInt(sortkeys, covervars, ncovervars);
4714 
4715  /* calculates weight excess of cover C */
4716  lambda = coverweight - capacity;
4717  assert(lambda > 0);
4718 
4719  /* calculates A_h for h = 0,...,|C|, I_h for h = 1,...,|C| and rho_h for h = 1,...,|C| */
4720  maxweightsums[0] = 0;
4721  for( h = 1; h <= ncovervars; h++ )
4722  {
4723  maxweightsums[h] = maxweightsums[h-1] + weights[covervars[h-1]];
4724  intervalends[h-1] = maxweightsums[h] - lambda;
4725  rhos[h-1] = MAX(0, weights[covervars[h-1]] - weights[covervars[0]] + lambda);
4726  }
4727 
4728  /* sorts variables in N\C such that a_{j_1} <= a_{j_2} <= ... <= a_{j_t} */
4729  for( j = 0; j < nnoncovervars; j++ )
4730  sortkeys[j] = (SCIP_Real) (weights[noncovervars[j]]);
4731  SCIPsortRealInt(sortkeys, noncovervars, nnoncovervars);
4732 
4733  /* calculates lifting coefficient for all variables in N\C */
4734  h = 0;
4735  for( j = 0; j < nnoncovervars; j++ )
4736  {
4737  int liftvar;
4738  SCIP_Longint weight;
4739  SCIP_Real liftcoef;
4740 
4741  liftvar = noncovervars[j];
4742  weight = weights[liftvar];
4743 
4744  while( intervalends[h] < weight )
4745  h++;
4746 
4747  if( h == 0 )
4748  liftcoef = h;
4749  else
4750  {
4751  if( weight <= intervalends[h-1] + rhos[h] )
4752  {
4753  SCIP_Real tmp1;
4754  SCIP_Real tmp2;
4755  tmp1 = (SCIP_Real) (intervalends[h-1] + rhos[h] - weight);
4756  tmp2 = (SCIP_Real) rhos[1];
4757  liftcoef = h - ( tmp1 / tmp2 );
4758  }
4759  else
4760  liftcoef = h;
4761  }
4762 
4763  /* sets lifting coefficient */
4764  assert(liftcoefs[liftvar] == 0.0);
4765  liftcoefs[liftvar] = liftcoef;
4766 
4767  /* updates activity of current valid inequality */
4768  (*cutact) += liftcoef * solvals[liftvar];
4769  }
4770 
4771  /* frees temporary memory */
4772  SCIPfreeBufferArray(scip, &rhos);
4773  SCIPfreeBufferArray(scip, &intervalends);
4774  SCIPfreeBufferArray(scip, &maxweightsums);
4775  SCIPfreeBufferArray(scip, &sortkeys);
4776 
4777  return SCIP_OKAY;
4778 }
4779 
4780 
4781 /** separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for
4782  * given knapsack problem
4783 */
4784 static
4786  SCIP* scip, /**< SCIP data structure */
4787  SCIP_CONS* cons, /**< originating constraint of the knapsack problem, or NULL */
4788  SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */
4789  SCIP_VAR** vars, /**< variables in knapsack constraint */
4790  int nvars, /**< number of variables in knapsack constraint */
4791  int ntightened, /**< number of variables with tightened upper bound */
4792  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
4793  SCIP_Longint capacity, /**< capacity of knapsack */
4794  SCIP_Real* solvals, /**< solution values of all problem variables */
4795  int* mincovervars, /**< mincover variables */
4796  int* nonmincovervars, /**< nonmincover variables */
4797  int nmincovervars, /**< number of mincover variables */
4798  int nnonmincovervars, /**< number of nonmincover variables */
4799  SCIP_SOL* sol, /**< primal SCIP solution to separate, NULL for current LP solution */
4800  SCIP_GUBSET* gubset, /**< GUB set data structure, NULL if no GUB information should be used */
4801  SCIP_Bool* cutoff, /**< pointer to store whether a cutoff has been detected */
4802  int* ncuts /**< pointer to add up the number of found cuts */
4803  )
4804 {
4805  int* varsC1;
4806  int* varsC2;
4807  int* varsF;
4808  int* varsR;
4809  int nvarsC1;
4810  int nvarsC2;
4811  int nvarsF;
4812  int nvarsR;
4813  SCIP_Real cutact;
4814  int* liftcoefs;
4815  int liftrhs;
4816 
4817  assert( cutoff != NULL );
4818  *cutoff = FALSE;
4819 
4820  /* allocates temporary memory */
4821  SCIP_CALL( SCIPallocBufferArray(scip, &varsC1, nvars) );
4822  SCIP_CALL( SCIPallocBufferArray(scip, &varsC2, nvars) );
4823  SCIP_CALL( SCIPallocBufferArray(scip, &varsF, nvars) );
4824  SCIP_CALL( SCIPallocBufferArray(scip, &varsR, nvars) );
4825  SCIP_CALL( SCIPallocBufferArray(scip, &liftcoefs, nvars) );
4826 
4827  /* gets partition (C_1,C_2) of C, i.e. C_1 & C_2 = C and C_1 cap C_2 = emptyset, with C_1 not empty; chooses partition
4828  * as follows
4829  * C_2 = { j in C : x*_j = 1 } and
4830  * C_1 = C\C_2
4831  */
4832  getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4833  assert(nvarsC1 + nvarsC2 == nmincovervars);
4834  assert(nmincovervars > 0);
4835  assert(nvarsC1 >= 0); /* nvarsC1 > 0 does not always hold, because relaxed knapsack conss may already be violated */
4836 
4837  /* changes partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one variable from C2 to C1 */
4838  if( nvarsC1 < 2 && nvarsC2 > 0)
4839  {
4840  SCIP_CALL( changePartitionCovervars(scip, weights, varsC1, varsC2, &nvarsC1, &nvarsC2) );
4841  assert(nvarsC1 >= 1);
4842  }
4843  assert(nvarsC2 == 0 || nvarsC1 >= 1);
4844 
4845  /* gets partition (F,R) of N\C, i.e. F & R = N\C and F cap R = emptyset; chooses partition as follows
4846  * R = { j in N\C : x*_j = 0 } and
4847  * F = (N\C)\F
4848  */
4849  getPartitionNoncovervars(scip, solvals, nonmincovervars, nnonmincovervars, varsF, varsR, &nvarsF, &nvarsR);
4850  assert(nvarsF + nvarsR == nnonmincovervars);
4851  assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR == nvars - ntightened);
4852 
4853  /* lift cuts without GUB information */
4854  if( gubset == NULL )
4855  {
4856  /* sorts variables in F, C_2, R according to the second level lifting sequence that will be used in the sequential
4857  * lifting procedure
4858  */
4859  SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsC2, varsR, nvarsF, nvarsC2, nvarsR) );
4860 
4861  /* lifts minimal cover inequality sum_{j in C_1} x_j <= |C_1| - 1 valid for
4862  *
4863  * S^0 = { x in {0,1}^|C_1| : sum_{j in C_1} a_j x_j <= a_0 - sum_{j in C_2} a_j }
4864  *
4865  * to a valid inequality sum_{j in C_1} x_j + sum_{j in N\C_1} alpha_j x_j <= |C_1| - 1 + sum_{j in C_2} alpha_j for
4866  *
4867  * S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0 },
4868  *
4869  * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in C_2 and sequential
4870  * up-lifting for the variables in R according to the second level lifting sequence
4871  */
4872  SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsC1, varsC2,
4873  varsF, varsR, nvarsC1, nvarsC2, nvarsF, nvarsR, nvarsC1 - 1, liftcoefs, &cutact, &liftrhs) );
4874  }
4875  /* lift cuts with GUB information */
4876  else
4877  {
4878  int* gubconsGC1;
4879  int* gubconsGC2;
4880  int* gubconsGFC1;
4881  int* gubconsGR;
4882  int ngubconsGC1;
4883  int ngubconsGC2;
4884  int ngubconsGFC1;
4885  int ngubconsGR;
4886  int ngubconss;
4887  int nconstightened;
4888  int maxgubvarssize;
4889 
4890  assert(nvars == gubset->nvars);
4891 
4892  ngubconsGC1 = 0;
4893  ngubconsGC2 = 0;
4894  ngubconsGFC1 = 0;
4895  ngubconsGR = 0;
4896  ngubconss = gubset->ngubconss;
4897  nconstightened = 0;
4898  maxgubvarssize = 0;
4899 
4900  /* allocates temporary memory */
4901  SCIP_CALL( SCIPallocBufferArray(scip, &gubconsGC1, ngubconss) );
4902  SCIP_CALL( SCIPallocBufferArray(scip, &gubconsGC2, ngubconss) );
4903  SCIP_CALL( SCIPallocBufferArray(scip, &gubconsGFC1, ngubconss) );
4904  SCIP_CALL( SCIPallocBufferArray(scip, &gubconsGR, ngubconss) );
4905 
4906  /* categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of
4907  * the GUBs for the sequential GUB wise lifting procedure
4908  */
4909  SCIP_CALL( getLiftingSequenceGUB(scip, gubset, solvals, weights, varsC1, varsC2, varsF, varsR, nvarsC1,
4910  nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4911  &ngubconsGFC1, &ngubconsGR, &nconstightened, &maxgubvarssize) );
4912 
4913  /* lifts minimal cover inequality sum_{j in C_1} x_j <= |C_1| - 1 valid for
4914  *
4915  * S^0 = { x in {0,1}^|C_1| : sum_{j in C_1} a_j x_j <= a_0 - sum_{j in C_2} a_j,
4916  * sum_{j in Q_i} x_j <= 1, forall i in I }
4917  *
4918  * to a valid inequality sum_{j in C_1} x_j + sum_{j in N\C_1} alpha_j x_j <= |C_1| - 1 + sum_{j in C_2} alpha_j for
4919  *
4920  * S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0, sum_{j in Q_i} x_j <= 1, forall i in I },
4921  *
4922  * uses sequential up-lifting for the variables in GUB constraints in gubconsGFC1,
4923  * sequential down-lifting for the variables in GUB constraints in gubconsGC2, and
4924  * sequential up-lifting for the variabels in GUB constraints in gubconsGR.
4925  */
4926  SCIP_CALL( sequentialUpAndDownLiftingGUB(scip, gubset, vars, nconstightened, weights, capacity, solvals, gubconsGC1,
4927  gubconsGC2, gubconsGFC1, gubconsGR, ngubconsGC1, ngubconsGC2, ngubconsGFC1, ngubconsGR,
4928  MIN(nvarsC1 - 1, ngubconsGC1), liftcoefs, &cutact, &liftrhs, maxgubvarssize) );
4929 
4930  /* frees temporary memory */
4931  SCIPfreeBufferArray(scip, &gubconsGR);
4932  SCIPfreeBufferArray(scip, &gubconsGFC1);
4933  SCIPfreeBufferArray(scip, &gubconsGC2);
4934  SCIPfreeBufferArray(scip, &gubconsGC1);
4935  }
4936 
4937  /* checks, if lifting yielded a violated cut */
4938  if( SCIPisEfficacious(scip, (cutact - liftrhs)/sqrt((SCIP_Real)MAX(liftrhs, 1))) )
4939  {
4940  SCIP_ROW* row;
4941  char name[SCIP_MAXSTRLEN];
4942  int j;
4943 
4944  /* creates LP row */
4945  assert( cons == NULL || sepa == NULL );
4946  if ( cons != NULL )
4947  {
4948  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
4949  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
4950  cons != NULL ? SCIPconsIsLocal(cons) : FALSE, FALSE,
4951  cons != NULL ? SCIPconsIsRemovable(cons) : TRUE) );
4952  }
4953  else if ( sepa != NULL )
4954  {
4955  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
4956  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4957  }
4958  else
4959  {
4960  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "nn_mcseq_%d", *ncuts);
4961  SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4962  }
4963 
4964  /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
4965  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
4966  assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR == nvars - ntightened);
4967  for( j = 0; j < nvarsC1; j++ )
4968  {
4969  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsC1[j]], 1.0) );
4970  }
4971  for( j = 0; j < nvarsC2; j++ )
4972  {
4973  if( liftcoefs[varsC2[j]] > 0 )
4974  {
4975  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsC2[j]], (SCIP_Real)liftcoefs[varsC2[j]]) );
4976  }
4977  }
4978  for( j = 0; j < nvarsF; j++ )
4979  {
4980  if( liftcoefs[varsF[j]] > 0 )
4981  {
4982  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsF[j]], (SCIP_Real)liftcoefs[varsF[j]]) );
4983  }
4984  }
4985  for( j = 0; j < nvarsR; j++ )
4986  {
4987  if( liftcoefs[varsR[j]] > 0 )
4988  {
4989  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsR[j]], (SCIP_Real)liftcoefs[varsR[j]]) );
4990  }
4991  }
4992  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
4993 
4994  /* checks, if cut is violated enough */
4995  if( SCIPisCutEfficacious(scip, sol, row) )
4996  {
4997  if( cons != NULL )
4998  {
4999  SCIP_CALL( SCIPresetConsAge(scip, cons) );
5000  }
5001  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
5002  (*ncuts)++;
5003  }
5004  SCIP_CALL( SCIPreleaseRow(scip, &row) );
5005  }
5006 
5007  /* frees temporary memory */
5008  SCIPfreeBufferArray(scip, &liftcoefs);
5009  SCIPfreeBufferArray(scip, &varsR);
5010  SCIPfreeBufferArray(scip, &varsF);
5011  SCIPfreeBufferArray(scip, &varsC2);
5012  SCIPfreeBufferArray(scip, &varsC1);
5013 
5014  return SCIP_OKAY;
5015 }
5016 
5017 /** separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem */
5018 static
5020  SCIP* scip, /**< SCIP data structure */
5021  SCIP_CONS* cons, /**< constraint that originates the knapsack problem, or NULL */
5022  SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */
5023  SCIP_VAR** vars, /**< variables in knapsack constraint */
5024  int nvars, /**< number of variables in knapsack constraint */
5025  int ntightened, /**< number of variables with tightened upper bound */
5026  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
5027  SCIP_Longint capacity, /**< capacity of knapsack */
5028  SCIP_Real* solvals, /**< solution values of all problem variables */
5029  int* feassetvars, /**< variables in feasible set */
5030  int* nonfeassetvars, /**< variables not in feasible set */
5031  int nfeassetvars, /**< number of variables in feasible set */
5032  int nnonfeassetvars, /**< number of variables not in feasible set */
5033  SCIP_SOL* sol, /**< primal SCIP solution to separate, NULL for current LP solution */
5034  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
5035  int* ncuts /**< pointer to add up the number of found cuts */
5036  )
5037 {
5038  int* varsT1;
5039  int* varsT2;
5040  int* varsF;
5041  int* varsR;
5042  int* liftcoefs;
5043  SCIP_Real cutact;
5044  int nvarsT1;
5045  int nvarsT2;
5046  int nvarsF;
5047  int nvarsR;
5048  int liftrhs;
5049  int j;
5050 
5051  assert( cutoff != NULL );
5052  *cutoff = FALSE;
5053 
5054  /* allocates temporary memory */
5055  SCIP_CALL( SCIPallocBufferArray(scip, &varsT1, nvars) );
5056  SCIP_CALL( SCIPallocBufferArray(scip, &varsT2, nvars) );
5057  SCIP_CALL( SCIPallocBufferArray(scip, &varsF, nvars) );
5058  SCIP_CALL( SCIPallocBufferArray(scip, &varsR, nvars) );
5059  SCIP_CALL( SCIPallocBufferArray(scip, &liftcoefs, nvars) );
5060 
5061  /* gets partition (T_1,T_2) of T, i.e. T_1 & T_2 = T and T_1 cap T_2 = emptyset, with T_1 not empty; chooses partition
5062  * as follows
5063  * T_2 = { j in T : x*_j = 1 } and
5064  * T_1 = T\T_2
5065  */
5066  getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5067  assert(nvarsT1 + nvarsT2 == nfeassetvars);
5068 
5069  /* changes partition (T_1,T_2) of feasible set T, if |T1| = 0, by moving one variable from T2 to T1 */
5070  if( nvarsT1 == 0 && nvarsT2 > 0)
5071  {
5072  SCIP_CALL( changePartitionFeasiblesetvars(scip, weights, varsT1, varsT2, &nvarsT1, &nvarsT2) );
5073  assert(nvarsT1 == 1);
5074  }
5075  assert(nvarsT2 == 0 || nvarsT1 > 0);
5076 
5077  /* gets partition (F,R) of N\T, i.e. F & R = N\T and F cap R = emptyset; chooses partition as follows
5078  * R = { j in N\T : x*_j = 0 } and
5079  * F = (N\T)\F
5080  */
5081  getPartitionNoncovervars(scip, solvals, nonfeassetvars, nnonfeassetvars, varsF, varsR, &nvarsF, &nvarsR);
5082  assert(nvarsF + nvarsR == nnonfeassetvars);
5083  assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR == nvars - ntightened);
5084 
5085  /* sorts variables in F, T_2, and R according to the second level lifting sequence that will be used in the sequential
5086  * lifting procedure (the variable removed last from the initial cover does not have to be lifted first, therefore it
5087  * is included in the sorting routine)
5088  */
5089  SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsT2, varsR, nvarsF, nvarsT2, nvarsR) );
5090 
5091  /* lifts extended weight inequality sum_{j in T_1} x_j <= |T_1| valid for
5092  *
5093  * S^0 = { x in {0,1}^|T_1| : sum_{j in T_1} a_j x_j <= a_0 - sum_{j in T_2} a_j }
5094  *
5095  * to a valid inequality sum_{j in T_1} x_j + sum_{j in N\T_1} alpha_j x_j <= |T_1| + sum_{j in T_2} alpha_j for
5096  *
5097  * S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0 },
5098  *
5099  * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in T_2 and sequential
5100  * up-lifting for the variabels in R according to the second level lifting sequence
5101  */
5102  SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5103  nvarsT1, nvarsT2, nvarsF, nvarsR, nvarsT1, liftcoefs, &cutact, &liftrhs) );
5104 
5105  /* checks, if lifting yielded a violated cut */
5106  if( SCIPisEfficacious(scip, (cutact - liftrhs)/sqrt((SCIP_Real)MAX(liftrhs, 1))) )
5107  {
5108  SCIP_ROW* row;
5109  char name[SCIP_MAXSTRLEN];
5110 
5111  /* creates LP row */
5112  assert( cons == NULL || sepa == NULL );
5113  if( cons != NULL )
5114  {
5115  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5116  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5117  cons != NULL ? SCIPconsIsLocal(cons) : FALSE, FALSE,
5118  cons != NULL ? SCIPconsIsRemovable(cons) : TRUE) );
5119  }
5120  else if ( sepa != NULL )
5121  {
5122  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5123  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5124  }
5125  else
5126  {
5127  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "nn_ewseq_%d", *ncuts);
5128  SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5129  }
5130 
5131  /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5132  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
5133  assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR == nvars - ntightened);
5134  for( j = 0; j < nvarsT1; j++ )
5135  {
5136  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsT1[j]], 1.0) );
5137  }
5138  for( j = 0; j < nvarsT2; j++ )
5139  {
5140  if( liftcoefs[varsT2[j]] > 0 )
5141  {
5142  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsT2[j]], (SCIP_Real)liftcoefs[varsT2[j]]) );
5143  }
5144  }
5145  for( j = 0; j < nvarsF; j++ )
5146  {
5147  if( liftcoefs[varsF[j]] > 0 )
5148  {
5149  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsF[j]], (SCIP_Real)liftcoefs[varsF[j]]) );
5150  }
5151  }
5152  for( j = 0; j < nvarsR; j++ )
5153  {
5154  if( liftcoefs[varsR[j]] > 0 )
5155  {
5156  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[varsR[j]], (SCIP_Real)liftcoefs[varsR[j]]) );
5157  }
5158  }
5159  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
5160 
5161  /* checks, if cut is violated enough */
5162  if( SCIPisCutEfficacious(scip, sol, row) )
5163  {
5164  if( cons != NULL )
5165  {
5166  SCIP_CALL( SCIPresetConsAge(scip, cons) );
5167  }
5168  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
5169  (*ncuts)++;
5170  }
5171  SCIP_CALL( SCIPreleaseRow(scip, &row) );
5172  }
5173 
5174  /* frees temporary memory */
5175  SCIPfreeBufferArray(scip, &liftcoefs);
5176  SCIPfreeBufferArray(scip, &varsR);
5177  SCIPfreeBufferArray(scip, &varsF);
5178  SCIPfreeBufferArray(scip, &varsT2);
5179  SCIPfreeBufferArray(scip, &varsT1);
5180 
5181  return SCIP_OKAY;
5182 }
5183 
5184 /** separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem */
5185 static
5187  SCIP* scip, /**< SCIP data structure */
5188  SCIP_CONS* cons, /**< constraint that originates the knapsack problem, or NULL */
5189  SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */
5190  SCIP_VAR** vars, /**< variables in knapsack constraint */
5191  int nvars, /**< number of variables in knapsack constraint */
5192  int ntightened, /**< number of variables with tightened upper bound */
5193  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
5194  SCIP_Longint capacity, /**< capacity of knapsack */
5195  SCIP_Real* solvals, /**< solution values of all problem variables */
5196  int* mincovervars, /**< mincover variables */
5197  int* nonmincovervars, /**< nonmincover variables */
5198  int nmincovervars, /**< number of mincover variables */
5199  int nnonmincovervars, /**< number of nonmincover variables */
5200  SCIP_Longint mincoverweight, /**< weight of minimal cover */
5201  SCIP_SOL* sol, /**< primal SCIP solution to separate, NULL for current LP solution */
5202  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
5203  int* ncuts /**< pointer to add up the number of found cuts */
5204  )
5205 {
5206  SCIP_Real* realliftcoefs;
5207  SCIP_Real cutact;
5208  int liftrhs;
5209 
5210  assert( cutoff != NULL );
5211  *cutoff = FALSE;
5212  cutact = 0.0;
5213 
5214  /* allocates temporary memory */
5215  SCIP_CALL( SCIPallocBufferArray(scip, &realliftcoefs, nvars) );
5216 
5217  /* lifts minimal cover inequality sum_{j in C} x_j <= |C| - 1 valid for
5218  *
5219  * S^0 = { x in {0,1}^|C| : sum_{j in C} a_j x_j <= a_0 }
5220  *
5221  * to a valid inequality sum_{j in C} x_j + sum_{j in N\C} alpha_j x_j <= |C| - 1 for
5222  *
5223  * S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0 },
5224  *
5225  * uses superadditive up-lifting for the variables in N\C.
5226  */
5227  SCIP_CALL( superadditiveUpLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, mincovervars,
5228  nonmincovervars, nmincovervars, nnonmincovervars, mincoverweight, realliftcoefs, &cutact) );
5229  liftrhs = nmincovervars - 1;
5230 
5231  /* checks, if lifting yielded a violated cut */
5232  if( SCIPisEfficacious(scip, (cutact - liftrhs)/sqrt((SCIP_Real)MAX(liftrhs, 1))) )
5233  {
5234  SCIP_ROW* row;
5235  char name[SCIP_MAXSTRLEN];
5236  int j;
5237 
5238  /* creates LP row */
5239  assert( cons == NULL || sepa == NULL );
5240  if ( cons != NULL )
5241  {
5242  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5243  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5244  cons != NULL ? SCIPconsIsLocal(cons) : FALSE, FALSE,
5245  cons != NULL ? SCIPconsIsRemovable(cons) : TRUE) );
5246  }
5247  else if ( sepa != NULL )
5248  {
5249  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5250  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5251  }
5252  else
5253  {
5254  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "nn_mcsup_%d", *ncuts);
5255  SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5256  }
5257 
5258  /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5259  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
5260  assert(nmincovervars + nnonmincovervars == nvars - ntightened);
5261  for( j = 0; j < nmincovervars; j++ )
5262  {
5263  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[mincovervars[j]], 1.0) );
5264  }
5265  for( j = 0; j < nnonmincovervars; j++ )
5266  {
5267  assert(SCIPisFeasGE(scip, realliftcoefs[nonmincovervars[j]], 0.0));
5268  if( SCIPisFeasGT(scip, realliftcoefs[nonmincovervars[j]], 0.0) )
5269  {
5270  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[nonmincovervars[j]], realliftcoefs[nonmincovervars[j]]) );
5271  }
5272  }
5273  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
5274 
5275  /* checks, if cut is violated enough */
5276  if( SCIPisCutEfficacious(scip, sol, row) )
5277  {
5278  if( cons != NULL )
5279  {
5280  SCIP_CALL( SCIPresetConsAge(scip, cons) );
5281  }
5282  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
5283  (*ncuts)++;
5284  }
5285  SCIP_CALL( SCIPreleaseRow(scip, &row) );
5286  }
5287 
5288  /* frees temporary memory */
5289  SCIPfreeBufferArray(scip, &realliftcoefs);
5290 
5291  return SCIP_OKAY;
5292 }
5293 
5294 /** converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen
5295  * to be in C, i.e. in the order of non-increasing (1 - x*_j)/a_j, if the transformed separation problem was used to find
5296  * C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C;
5297  * note that all variables with x*_j = 1 will be removed last
5298  */
5299 static
5301  SCIP* scip, /**< SCIP data structure */
5302  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
5303  SCIP_Longint capacity, /**< capacity of knapsack */
5304  SCIP_Real* solvals, /**< solution values of all problem variables */
5305  int* covervars, /**< pointer to store cover variables */
5306  int* noncovervars, /**< pointer to store noncover variables */
5307  int* ncovervars, /**< pointer to store number of cover variables */
5308  int* nnoncovervars, /**< pointer to store number of noncover variables */
5309  SCIP_Longint* coverweight, /**< pointer to store weight of cover */
5310  SCIP_Bool modtransused /**< TRUE if mod trans sepa prob was used to find cover */
5311  )
5312 {
5313  SORTKEYPAIR** sortkeypairs;
5314  SORTKEYPAIR** sortkeypairssorted;
5315  SCIP_Longint minweight;
5316  int nsortkeypairs;
5317  int minweightidx;
5318  int j;
5319  int k;
5320 
5321  assert(scip != NULL);
5322  assert(covervars != NULL);
5323  assert(noncovervars != NULL);
5324  assert(ncovervars != NULL);
5325  assert(*ncovervars > 0);
5326  assert(nnoncovervars != NULL);
5327  assert(*nnoncovervars >= 0);
5328  assert(coverweight != NULL);
5329  assert(*coverweight > 0);
5330  assert(*coverweight > capacity);
5331 
5332  /* allocates temporary memory; we need two arrays for the keypairs in order to be able to free them in the correct
5333  * order */
5334  nsortkeypairs = *ncovervars;
5335  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeypairs, nsortkeypairs) );
5336  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeypairssorted, nsortkeypairs) );
5337 
5338  /* sorts C in the reverse order in which the variables were chosen to be in the cover, i.e.
5339  * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5340  * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5341  * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5342  */
5343  assert(*ncovervars == nsortkeypairs);
5344  if( modtransused )
5345  {
5346  for( j = 0; j < *ncovervars; j++ )
5347  {
5348  SCIP_CALL( SCIPallocBuffer(scip, &(sortkeypairs[j])) ); /*lint !e866 */
5349  sortkeypairssorted[j] = sortkeypairs[j];
5350 
5351  sortkeypairs[j]->key1 = solvals[covervars[j]];
5352  sortkeypairs[j]->key2 = (SCIP_Real) weights[covervars[j]];
5353  }
5354  }
5355  else
5356  {
5357  for( j = 0; j < *ncovervars; j++ )
5358  {
5359  SCIP_CALL( SCIPallocBuffer(scip, &(sortkeypairs[j])) ); /*lint !e866 */
5360  sortkeypairssorted[j] = sortkeypairs[j];
5361 
5362  sortkeypairs[j]->key1 = (solvals[covervars[j]] - 1.0) / ((SCIP_Real) weights[covervars[j]]);
5363  sortkeypairs[j]->key2 = (SCIP_Real) (-weights[covervars[j]]);
5364  }
5365  }
5366  SCIPsortPtrInt((void**)sortkeypairssorted, covervars, compSortkeypairs, *ncovervars);
5367 
5368  /* gets j' with a_j' = min{ a_j : j in C } */
5369  minweightidx = 0;
5370  minweight = weights[covervars[minweightidx]];
5371  for( j = 1; j < *ncovervars; j++ )
5372  {
5373  if( weights[covervars[j]] <= minweight )
5374  {
5375  minweightidx = j;
5376  minweight = weights[covervars[minweightidx]];
5377  }
5378  }
5379  assert(minweightidx >= 0 && minweightidx < *ncovervars);
5380  assert(minweight > 0 && minweight <= *coverweight);
5381 
5382  j = 0;
5383  /* removes variables from C until the remaining variables form a minimal cover */
5384  while( j < *ncovervars && ((*coverweight) - minweight > capacity) )
5385  {
5386  assert(minweightidx >= j);
5387  assert(checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j));
5388 
5389  /* if sum_{i in C} a_i - a_j <= a_0, j cannot be removed from C */
5390  if( (*coverweight) - weights[covervars[j]] <= capacity )
5391  {
5392  ++j;
5393  continue;
5394  }
5395 
5396  /* adds j to N\C */
5397  noncovervars[*nnoncovervars] = covervars[j];
5398  (*nnoncovervars)++;
5399 
5400  /* removes j from C */
5401  (*coverweight) -= weights[covervars[j]];
5402  for( k = j; k < (*ncovervars) - 1; k++ )
5403  covervars[k] = covervars[k+1];
5404  (*ncovervars)--;
5405 
5406  /* updates j' with a_j' = min{ a_j : j in C } */
5407  if( j == minweightidx )
5408  {
5409  minweightidx = 0;
5410  minweight = weights[covervars[minweightidx]];
5411  for( k = 1; k < *ncovervars; k++ )
5412  {
5413  if( weights[covervars[k]] <= minweight )
5414  {
5415  minweightidx = k;
5416  minweight = weights[covervars[minweightidx]];
5417  }
5418  }
5419  assert(minweight > 0 && minweight <= *coverweight);
5420  assert(minweightidx >= 0 && minweightidx < *ncovervars);
5421  }
5422  else
5423  {
5424  assert(minweightidx > j);
5425  minweightidx--;
5426  }
5427  /* j needs to stay the same */
5428  }
5429  assert((*coverweight) > capacity);
5430  assert((*coverweight) - minweight <= capacity);
5431 
5432  /* frees temporary memory */
5433  for( j = nsortkeypairs-1; j >= 0; j-- )
5434  SCIPfreeBuffer(scip, &(sortkeypairs[j])); /*lint !e866 */
5435  SCIPfreeBufferArray(scip, &sortkeypairssorted);
5436  SCIPfreeBufferArray(scip, &sortkeypairs);
5437 
5438  return SCIP_OKAY;
5439 }
5440 
5441 /** converts given initial cover C_init to a feasible set by removing variables in the reverse order in which
5442  * they were chosen to be in C_init:
5443  * non-increasing (1 - x*_j)/a_j, if transformed separation problem was used to find C_init
5444  * non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init.
5445  * separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set
5446  * and all subsequent feasible sets.
5447  */
5448 static
5450  SCIP* scip, /**< SCIP data structure */
5451  SCIP_CONS* cons, /**< constraint that originates the knapsack problem */
5452  SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */
5453  SCIP_VAR** vars, /**< variables in knapsack constraint */
5454  int nvars, /**< number of variables in knapsack constraint */
5455  int ntightened, /**< number of variables with tightened upper bound */
5456  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
5457  SCIP_Longint capacity, /**< capacity of knapsack */
5458  SCIP_Real* solvals, /**< solution values of all problem variables */
5459  int* covervars, /**< pointer to store cover variables */
5460  int* noncovervars, /**< pointer to store noncover variables */
5461  int* ncovervars, /**< pointer to store number of cover variables */
5462  int* nnoncovervars, /**< pointer to store number of noncover variables */
5463  SCIP_Longint* coverweight, /**< pointer to store weight of cover */
5464  SCIP_Bool modtransused, /**< TRUE if mod trans sepa prob was used to find cover */
5465  SCIP_SOL* sol, /**< primal SCIP solution to separate, NULL for current LP solution */
5466  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
5467  int* ncuts /**< pointer to add up the number of found cuts */
5468  )
5469 {
5470  SCIP_Real* sortkeys;
5471  int j;
5472  int k;
5473 
5474  assert(scip != NULL);
5475  assert(covervars != NULL);
5476  assert(noncovervars != NULL);
5477  assert(ncovervars != NULL);
5478  assert(*ncovervars > 0);
5479  assert(nnoncovervars != NULL);
5480  assert(*nnoncovervars >= 0);
5481  assert(coverweight != NULL);
5482  assert(*coverweight > 0);
5483  assert(*coverweight > capacity);
5484  assert(*ncovervars + *nnoncovervars == nvars - ntightened);
5485  assert(cutoff != NULL);
5486 
5487  *cutoff = FALSE;
5488 
5489  /* allocates temporary memory */
5490  SCIP_CALL( SCIPallocBufferArray(scip, &sortkeys, *ncovervars) );
5491 
5492  /* sorts C in the reverse order in which the variables were chosen to be in the cover, i.e.
5493  * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5494  * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5495  * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5496  */
5497  if( modtransused )
5498  {
5499  for( j = 0; j < *ncovervars; j++ )
5500  {
5501  sortkeys[j] = solvals[covervars[j]];
5502  assert(SCIPisFeasGE(scip, sortkeys[j], 0.0));
5503  }
5504  }
5505  else
5506  {
5507  for( j = 0; j < *ncovervars; j++ )
5508  {
5509  sortkeys[j] = (solvals[covervars[j]] - 1.0) / ((SCIP_Real) weights[covervars[j]]);
5510  assert(SCIPisFeasLE(scip, sortkeys[j], 0.0));
5511  }
5512  }
5513  SCIPsortRealInt(sortkeys, covervars, *ncovervars);
5514 
5515  /* removes variables from C_init and separates lifted extended weight inequalities using sequential up- and down-lifting;
5516  * in addition to an extended weight inequality this gives cardinality inequalities */
5517  while( *ncovervars >= 2 )
5518  {
5519  /* adds first element of C_init to N\C_init */
5520  noncovervars[*nnoncovervars] = covervars[0];
5521  (*nnoncovervars)++;
5522 
5523  /* removes first element from C_init */
5524  (*coverweight) -= weights[covervars[0]];
5525  for( k = 0; k < (*ncovervars) - 1; k++ )
5526  covervars[k] = covervars[k+1];
5527  (*ncovervars)--;
5528 
5529  assert(*ncovervars + *nnoncovervars == nvars - ntightened);
5530  if( (*coverweight) <= capacity )
5531  {
5532  SCIP_CALL( separateSequLiftedExtendedWeightInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals,
5533  covervars, noncovervars, *ncovervars, *nnoncovervars, sol, cutoff, ncuts) );
5534  }
5535 
5536  /* stop if cover is too large */
5537  if ( *ncovervars >= MAXCOVERSIZEITERLEWI )
5538  break;
5539  }
5540 
5541  /* frees temporary memory */
5542  SCIPfreeBufferArray(scip, &sortkeys);
5543 
5544  return SCIP_OKAY;
5545 }
5546 
5547 /** separates different classes of valid inequalities for the 0-1 knapsack problem */
5549  SCIP* scip, /**< SCIP data structure */
5550  SCIP_CONS* cons, /**< originating constraint of the knapsack problem, or NULL */
5551  SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */
5552  SCIP_VAR** vars, /**< variables in knapsack constraint */
5553  int nvars, /**< number of variables in knapsack constraint */
5554  SCIP_Longint* weights, /**< weights of variables in knapsack constraint */
5555  SCIP_Longint capacity, /**< capacity of knapsack */
5556  SCIP_SOL* sol, /**< primal SCIP solution to separate, NULL for current LP solution */
5557  SCIP_Bool usegubs, /**< should GUB information be used for separation? */
5558  SCIP_Bool* cutoff, /**< pointer to store whether a cutoff has been detected */
5559  int* ncuts /**< pointer to add up the number of found cuts */
5560  )
5561 {
5562  SCIP_Real* solvals;
5563  int* covervars;
5564  int* noncovervars;
5565  SCIP_Bool coverfound;
5566  SCIP_Bool fractional;
5567  SCIP_Bool modtransused;
5568  SCIP_Longint coverweight;
5569  int ncovervars;
5570  int nnoncovervars;
5571  int ntightened;
5572 
5573  assert(scip != NULL);
5574  assert(capacity >= 0);
5575  assert(cutoff != NULL);
5576  assert(ncuts != NULL);
5577 
5578  *cutoff = FALSE;
5579 
5580  if( nvars == 0 )
5581  return SCIP_OKAY;
5582 
5583  assert(vars != NULL);
5584  assert(nvars > 0);
5585  assert(weights != NULL);
5586 
5587  /* increase age of constraint (age is reset to zero, if a cut was found) */
5588  if( cons != NULL )
5589  {
5590  SCIP_CALL( SCIPincConsAge(scip, cons) );
5591  }
5592 
5593  /* allocates temporary memory */
5594  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) );
5595  SCIP_CALL( SCIPallocBufferArray(scip, &covervars, nvars) );
5596  SCIP_CALL( SCIPallocBufferArray(scip, &noncovervars, nvars) );
5597 
5598  /* gets solution values of all problem variables */
5599  SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, solvals) );
5600 
5601 #ifdef SCIP_DEBUG
5602  {
5603  int i;
5604 
5605  SCIPdebugMsg(scip, "separate cuts for knapsack constraint originated by cons <%s>:\n",
5606  cons == NULL ? "-" : SCIPconsGetName(cons));
5607  for( i = 0; i < nvars; ++i )
5608  {
5609  SCIPdebugMsgPrint(scip, "%+" SCIP_LONGINT_FORMAT "<%s>(%g)", weights[i], SCIPvarGetName(vars[i]), solvals[i]);
5610  }
5611  SCIPdebugMsgPrint(scip, " <= %" SCIP_LONGINT_FORMAT "\n", capacity);
5612  }
5613 #endif
5614 
5615  /* LMCI1 (lifted minimal cover inequalities using sequential up- and down-lifting) using GUB information
5616  */
5617  if( usegubs )
5618  {
5619  SCIP_GUBSET* gubset;
5620 
5621  SCIPdebugMsg(scip, "separate LMCI1-GUB cuts:\n");
5622 
5623  /* initializes partion of knapsack variables into nonoverlapping GUB constraints */
5624  SCIP_CALL( GUBsetCreate(scip, &gubset, nvars, weights, capacity) );
5625 
5626  /* constructs sophisticated partition of knapsack variables into nonoverlapping GUBs */
5627  SCIP_CALL( GUBsetGetCliquePartition(scip, gubset, vars, solvals) );
5628  assert(gubset->ngubconss <= nvars);
5629 
5630  /* gets a most violated initial cover C_init ( sum_{j in C_init} a_j > a_0 ) by using the
5631  * MODIFIED transformed separation problem and taking into account the following fixing:
5632  * j in C_init, if j in N_1 = {j in N : x*_j = 1} and
5633  * j in N\C_init, if j in N_0 = {j in N : x*_j = 0},
5634  * if one exists
5635  */
5636  modtransused = TRUE;
5637  SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5638  &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5639 
5640  assert(!coverfound || !fractional || ncovervars + nnoncovervars == nvars - ntightened);
5641 
5642  /* if x* is not fractional we stop the separation routine */
5643  if( !fractional )
5644  {
5645  SCIPdebugMsg(scip, " LMCI1-GUB terminated by no variable with fractional LP value.\n");
5646 
5647  /* frees memory for GUB set data structure */
5648  GUBsetFree(scip, &gubset);
5649 
5650  goto TERMINATE;
5651  }
5652 
5653  /* if no cover was found we stop the separation routine for lifted minimal cover inequality */
5654  if( coverfound )
5655  {
5656  /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5657  * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5658  */
5659  SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5660  &nnoncovervars, &coverweight, modtransused) );
5661 
5662  /* only separate with GUB information if we have at least one nontrivial GUB (with more than one variable) */
5663  if( gubset->ngubconss < nvars )
5664  {
5665  /* separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information */
5666  SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5667  solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, gubset, cutoff, ncuts) );
5668  }
5669  else
5670  {
5671  /* separates lifted minimal cover inequalities using sequential up- and down-lifting, but do not use trivial
5672  * GUB information
5673  */
5674  SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5675  solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, NULL, cutoff, ncuts) );
5676  }
5677  }
5678 
5679  /* frees memory for GUB set data structure */
5680  GUBsetFree(scip, &gubset);
5681  }
5682  else
5683  {
5684  /* LMCI1 (lifted minimal cover inequalities using sequential up- and down-lifting)
5685  * (and LMCI2 (lifted minimal cover inequalities using superadditive up-lifting))
5686  */
5687 
5688  /* gets a most violated initial cover C_init ( sum_{j in C_init} a_j > a_0 ) by using the
5689  * MODIFIED transformed separation problem and taking into account the following fixing:
5690  * j in C_init, if j in N_1 = {j in N : x*_j = 1} and
5691  * j in N\C_init, if j in N_0 = {j in N : x*_j = 0},
5692  * if one exists
5693  */
5694  SCIPdebugMsg(scip, "separate LMCI1 cuts:\n");
5695  modtransused = TRUE;
5696  SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5697  &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5698  assert(!coverfound || !fractional || ncovervars + nnoncovervars == nvars - ntightened);
5699 
5700  /* if x* is not fractional we stop the separation routine */
5701  if( !fractional )
5702  goto TERMINATE;
5703 
5704  /* if no cover was found we stop the separation routine for lifted minimal cover inequality */
5705  if( coverfound )
5706  {
5707  /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5708  * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5709  */
5710  SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5711  &nnoncovervars, &coverweight, modtransused) );
5712 
5713  /* separates lifted minimal cover inequalities using sequential up- and down-lifting */
5714  SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5715  solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, NULL, cutoff, ncuts) );
5716 
5717  if( USESUPADDLIFT ) /*lint !e506 !e774*/
5718  {
5719  SCIPdebugMsg(scip, "separate LMCI2 cuts:\n");
5720  /* separates lifted minimal cover inequalities using superadditive up-lifting */
5721  SCIP_CALL( separateSupLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5722  solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) );
5723  }
5724  }
5725  }
5726 
5727  /* LEWI (lifted extended weight inequalities using sequential up- and down-lifting) */
5728  if ( ! (*cutoff) )
5729  {
5730  /* gets a most violated initial cover C_init ( sum_{j in C_init} a_j > a_0 ) by using the
5731  * transformed separation problem and taking into account the following fixing:
5732  * j in C_init, if j in N_1 = {j in N : x*_j = 1} and
5733  * j in N\C_init, if j in N_0 = {j in N : x*_j = 0},
5734  * if one exists
5735  */
5736  SCIPdebugMsg(scip, "separate LEWI cuts:\n");
5737  modtransused = FALSE;
5738  SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5739  &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5740  assert(fractional);
5741  assert(!coverfound || ncovervars + nnoncovervars == nvars - ntightened);
5742 
5743  /* if no cover was found we stop the separation routine */
5744  if( coverfound )
5745  {
5746  /* converts initial cover C_init to a feasible set by removing variables in the reverse order in which
5747  * they were chosen to be in C_init and separates lifted extended weight inequalities using sequential
5748  * up- and down-lifting for this feasible set and all subsequent feasible sets.
5749  */
5750  SCIP_CALL( getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5751  &ncovervars, &nnoncovervars, &coverweight, modtransused, sol, cutoff, ncuts) );
5752  }
5753  }
5754 
5755  TERMINATE:
5756  /* frees temporary memory */
5757  SCIPfreeBufferArray(scip, &noncovervars);
5758  SCIPfreeBufferArray(scip, &covervars);
5759  SCIPfreeBufferArray(scip, &solvals);
5760 
5761  return SCIP_OKAY;
5762 }
5763 
5764 /* relaxes given general linear constraint into a knapsack constraint and separates lifted knapsack cover inequalities */
5766  SCIP* scip, /**< SCIP data structure */
5767  SCIP_CONS* cons, /**< originating constraint of the knapsack problem, or NULL */
5768  SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */
5769  int nknapvars, /**< number of variables in the continuous knapsack constraint */
5770  SCIP_VAR** knapvars, /**< variables in the continuous knapsack constraint */
5771  SCIP_Real* knapvals, /**< coefficients of the variables in the continuous knapsack constraint */
5772  SCIP_Real valscale, /**< -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise */
5773  SCIP_Real rhs, /**< right hand side of the continuous knapsack constraint */
5774  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
5775  SCIP_Bool* cutoff, /**< pointer to store whether a cutoff was found */
5776  int* ncuts /**< pointer to add up the number of found cuts */
5777  )
5778 {
5779  SCIP_VAR** binvars;
5780  SCIP_VAR** consvars;
5781  SCIP_Real* binvals;
5782  SCIP_Longint* consvals;
5783  SCIP_Longint minact;
5784  SCIP_Longint maxact;
5785  SCIP_Real intscalar;
5786  SCIP_Bool success;
5787  int nbinvars;
5788  int nconsvars;
5789  int i;
5790 
5791  int* tmpindices;
5792  int tmp;
5793  SCIP_CONSHDLR* conshdlr;
5794  SCIP_CONSHDLRDATA* conshdlrdata;
5795  SCIP_Bool noknapsackconshdlr;
5796  SCIP_Bool usegubs;
5797 
5798  assert(nknapvars > 0);
5799  assert(knapvars != NULL);
5800  assert(cutoff != NULL);
5801 
5802  tmpindices = NULL;
5803 
5804  SCIPdebugMsg(scip, "separate linear constraint <%s> relaxed to knapsack\n", cons != NULL ? SCIPconsGetName(cons) : "-");
5805  SCIPdebug( if( cons != NULL ) { SCIPdebugPrintCons(scip, cons, NULL); } );
5806 
5807  binvars = SCIPgetVars(scip);
5808 
5809  /* all variables which are of integral type can be potentially of binary type; this can be checked via the method SCIPvarIsBinary(var) */
5810  nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
5811 
5812  *cutoff = FALSE;
5813 
5814  if( nbinvars == 0 )
5815  return SCIP_OKAY;
5816 
5817  /* set up data structures */
5818  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) );
5819  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) );
5820 
5821  /* get conshdlrdata to use cleared memory */
5822  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5823  if( conshdlr == NULL )
5824  {
5825  noknapsackconshdlr = TRUE;
5826  usegubs = DEFAULT_USEGUBS;
5827 
5828  SCIP_CALL( SCIPallocBufferArray(scip, &binvals, nbinvars) );
5829  BMSclearMemoryArray(binvals, nbinvars);
5830  }
5831  else
5832  {
5833  noknapsackconshdlr = FALSE;
5834  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5835  assert(conshdlrdata != NULL);
5836  usegubs = conshdlrdata->usegubs;
5837 
5838  SCIP_CALL( SCIPallocBufferArray(scip, &tmpindices, nknapvars) );
5839 
5840  /* increase array size to avoid an endless loop in the next block; this might happen if continuous variables
5841  * change their types to SCIP_VARTYPE_BINARY during presolving
5842  */
5843  if( conshdlrdata->reals1size == 0 )
5844  {
5845  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, conshdlrdata->reals1size, 1) );
5846  conshdlrdata->reals1size = 1;
5847  conshdlrdata->reals1[0] = 0.0;
5848  }
5849 
5850  assert(conshdlrdata->reals1size > 0);
5851 
5852  /* next if condition should normally not be true, because it means that presolving has created more binary
5853  * variables than binary + integer variables existed at the constraint initialization method, but for example if you would
5854  * transform all integers into their binary representation then it maybe happens
5855  */
5856  if( conshdlrdata->reals1size < nbinvars )
5857  {
5858  int oldsize = conshdlrdata->reals1size;
5859 
5860  conshdlrdata->reals1size = nbinvars;
5861  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, oldsize, conshdlrdata->reals1size) );
5862  BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize); /*lint !e866 */
5863  }
5864  binvals = conshdlrdata->reals1;
5865 
5866  /* check for cleared array, all entries have to be zero */
5867 #ifndef NDEBUG
5868  for( tmp = nbinvars - 1; tmp >= 0; --tmp )
5869  {
5870  assert(binvals[tmp] == 0);
5871  }
5872 #endif
5873  }
5874 
5875  tmp = 0;
5876 
5877  /* relax continuous knapsack constraint:
5878  * 1. make all variables binary:
5879  * if x_j is continuous or integer variable substitute:
5880  * - a_j < 0: x_j = lb or x_j = b*z + d with variable lower bound b*z + d with binary variable z
5881  * - a_j > 0: x_j = ub or x_j = b*z + d with variable upper bound b*z + d with binary variable z
5882  * 2. convert coefficients of all variables to positive integers:
5883  * - scale all coefficients a_j to a~_j integral
5884  * - substitute x~_j = 1 - x_j if a~_j < 0
5885  */
5886 
5887  /* replace integer and continuous variables with binary variables */
5888  for( i = 0; i < nknapvars; i++ )
5889  {
5890  SCIP_VAR* var;
5891 
5892  var = knapvars[i];
5893 
5894  if( SCIPvarIsBinary(var) && SCIPvarIsActive(var) )
5895  {
5896  SCIP_Real solval;
5897  assert(0 <= SCIPvarGetProbindex(var) && SCIPvarGetProbindex(var) < nbinvars);
5898 
5899  solval = SCIPgetSolVal(scip, sol, var);
5900 
5901  /* knapsack relaxation assumes solution values between 0.0 and 1.0 for binary variables */
5902  if( SCIPisFeasLT(scip, solval, 0.0 )
5903  || SCIPisFeasGT(scip, solval, 1.0) )
5904  {
5905  SCIPdebugMsg(scip, "Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5906  solval, SCIPvarGetName(var));
5907  goto TERMINATE;
5908  }
5909 
5910  binvals[SCIPvarGetProbindex(var)] += valscale * knapvals[i];
5911  if( !noknapsackconshdlr )
5912  {
5913  assert(tmpindices != NULL);
5914 
5915  tmpindices[tmp] = SCIPvarGetProbindex(var);
5916  ++tmp;
5917  }
5918  SCIPdebugMsg(scip, " -> binary variable %+.15g<%s>(%.15g)\n", valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var));
5919  }
5920  else if( valscale * knapvals[i] > 0.0 )
5921  {
5922  SCIP_VAR** zvlb;
5923  SCIP_Real* bvlb;
5924  SCIP_Real* dvlb;
5925  SCIP_Real bestlbsol;
5926  int bestlbtype;
5927  int nvlb;
5928  int j;
5929 
5930  /* a_j > 0: substitution with lb or vlb */
5931  nvlb = SCIPvarGetNVlbs(var);
5932  zvlb = SCIPvarGetVlbVars(var);
5933  bvlb = SCIPvarGetVlbCoefs(var);
5934  dvlb = SCIPvarGetVlbConstants(var);
5935 
5936  /* search for lb or vlb with maximal bound value */
5937  bestlbsol = SCIPvarGetLbGlobal(var);
5938  bestlbtype = -1;
5939  for( j = 0; j < nvlb; j++ )
5940  {
5941  /* use only numerical stable vlb with binary variable z */
5942  if( SCIPvarIsBinary(zvlb[j]) && SCIPvarIsActive(zvlb[j]) && REALABS(bvlb[j]) <= MAXABSVBCOEF )
5943  {
5944  SCIP_Real vlbsol;
5945 
5946  if( (bvlb[j] >= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetLbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) ||
5947  (bvlb[j] <= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetUbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) )
5948  {
5949  *cutoff = TRUE;
5950  SCIPdebugMsg(scip, "variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5952  bvlb[j], SCIPvarGetName(zvlb[j]), SCIPvarGetLbLocal(zvlb[j]), SCIPvarGetUbLocal(zvlb[j]), dvlb[j]);
5953  goto TERMINATE;
5954  }
5955 
5956  assert(0 <= SCIPvarGetProbindex(zvlb[j]) && SCIPvarGetProbindex(zvlb[j]) < nbinvars);
5957  vlbsol = bvlb[j] * SCIPgetSolVal(scip, sol, zvlb[j]) + dvlb[j];
5958  if( SCIPisGE(scip, vlbsol, bestlbsol) )
5959  {
5960  bestlbsol = vlbsol;
5961  bestlbtype = j;
5962  }
5963  }
5964  }
5965 
5966  /* if no lb or vlb with binary variable was found, we have to abort */
5967  if( SCIPisInfinity(scip, -bestlbsol) )
5968  goto TERMINATE;
5969 
5970  if( bestlbtype == -1 )
5971  {
5972  rhs -= valscale * knapvals[i] * bestlbsol;
5973  SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5974  valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbGlobal(var), rhs);
5975  }
5976  else
5977  {
5978  assert(0 <= SCIPvarGetProbindex(zvlb[bestlbtype]) && SCIPvarGetProbindex(zvlb[bestlbtype]) < nbinvars);
5979  rhs -= valscale * knapvals[i] * dvlb[bestlbtype];
5980  binvals[SCIPvarGetProbindex(zvlb[bestlbtype])] += valscale * knapvals[i] * bvlb[bestlbtype];
5981 
5982  if( SCIPisInfinity(scip, REALABS(binvals[SCIPvarGetProbindex(zvlb[bestlbtype])])) )
5983  goto TERMINATE;
5984 
5985  if( !noknapsackconshdlr )
5986  {
5987  assert(tmpindices != NULL);
5988 
5989  tmpindices[tmp] = SCIPvarGetProbindex(zvlb[bestlbtype]);
5990  ++tmp;
5991  }
5992  SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
5993  valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var),
5994  bvlb[bestlbtype], SCIPvarGetName(zvlb[bestlbtype]),
5995  SCIPgetSolVal(scip, sol, zvlb[bestlbtype]), dvlb[bestlbtype], rhs);
5996  }
5997  }
5998  else
5999  {
6000  SCIP_VAR** zvub;
6001  SCIP_Real* bvub;
6002  SCIP_Real* dvub;
6003  SCIP_Real bestubsol;
6004  int bestubtype;
6005  int nvub;
6006  int j;
6007 
6008  assert(valscale * knapvals[i] < 0.0);
6009 
6010  /* a_j < 0: substitution with ub or vub */
6011  nvub = SCIPvarGetNVubs(var);