Scippy

SCIP

Solving Constraint Integer Programs

cons_linking.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-2022 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_linking.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for linking constraints
19  * @author Stefan Heinz
20  * @author Jens Schulz
21  *
22  * The constraints handler stores linking constraints between a linking variable (integer or continuous) and an array of binary variables. Such
23  * a linking constraint has the form:
24  *
25  * linkvar = sum_{i=1}^n {vals[i] * binvars[i]}
26  *
27  * with the additional side condition that exactly one binary variable has to be one (set partitioning condition).
28  *
29  * This constraint can be created only with the linking variable if it is an integer variable. In this case the binary variables are only created on
30  * demand. That is, whenever someone asks for the binary variables. Therefore, such constraints can be used to get a
31  * "binary representation" of the domain of the linking variable which will be dynamically created.
32  *
33  *
34  * @todo add pairwise comparison of constraints in presolving (fast hash table version and complete pairwise comparison)
35  * @todo in case the integer variable is set to lower or upper bound it follows that only the corresponding binary
36  * variable has a positive value which is one, this can be used to fasten the checking routine
37  */
38 
39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 
41 #include "blockmemshell/memory.h"
42 #include "scip/cons_linear.h"
43 #include "scip/cons_linking.h"
44 #include "scip/cons_setppc.h"
45 #include "scip/pub_cons.h"
46 #include "scip/pub_event.h"
47 #include "scip/pub_lp.h"
48 #include "scip/pub_message.h"
49 #include "scip/pub_misc.h"
50 #include "scip/pub_misc_sort.h"
51 #include "scip/pub_var.h"
52 #include "scip/scip_conflict.h"
53 #include "scip/scip_cons.h"
54 #include "scip/scip_copy.h"
55 #include "scip/scip_cut.h"
56 #include "scip/scip_event.h"
57 #include "scip/scip_general.h"
58 #include "scip/scip_lp.h"
59 #include "scip/scip_mem.h"
60 #include "scip/scip_message.h"
61 #include "scip/scip_nlp.h"
62 #include "scip/scip_numerics.h"
63 #include "scip/scip_param.h"
64 #include "scip/scip_prob.h"
65 #include "scip/scip_probing.h"
66 #include "scip/scip_sol.h"
67 #include "scip/scip_tree.h"
68 #include "scip/scip_var.h"
69 #include <ctype.h>
70 #include <string.h>
71 
72 /* constraint handler properties */
73 #define CONSHDLR_NAME "linking"
74 #define CONSHDLR_DESC "linking constraint x = sum_{i=1}^{n} c_i*y_i, y1+...+yn = 1, x real, y's binary"
75 
76 #define EVENTHDLR_NAME "linking"
77 #define EVENTHDLR_DESC "event handler for linking constraints"
78 
79 #define CONSHDLR_SEPAPRIORITY 750000 /**< priority of the constraint handler for separation */
80 #define CONSHDLR_ENFOPRIORITY -2050000 /**< priority of the constraint handler for constraint enforcing */
81 #define CONSHDLR_CHECKPRIORITY -750000 /**< priority of the constraint handler for checking feasibility */
82 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
83 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
84 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only */
85 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
86 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
87 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
88 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
89 
90 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
91 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
92 
93 
94 #define HASHSIZE_BINVARSCONS 500 /**< minimal size of hash table in linking constraint handler */
95 #define DEFAULT_LINEARIZE FALSE /**< should the linking constraint be linearize after the binary variable are created */
96 
97 /*
98  * Data structures
99  */
100 
101 /** constraint data for linking constraints */
102 struct SCIP_ConsData
103 {
104  SCIP_VAR* linkvar; /**< continuous variable which is linked */
105  SCIP_VAR** binvars; /**< binary variables */
106  SCIP_Real* vals; /**< coefficients */
107  SCIP_ROW* row1; /**< LP row for the linking itself */
108  SCIP_ROW* row2; /**< LP row ensuring the set partitioning condition of the binary variables */
109  SCIP_NLROW* nlrow1; /**< NLP row for the linking itself */
110  SCIP_NLROW* nlrow2; /**< NLP row ensuring the set partitioning condition of the binary variables */
111  int nbinvars; /**< number of binary variables */
112  int sizebinvars; /**< size of the binary variable array */
113  int nfixedzeros; /**< current number of variables fixed to zero in the constraint */
114  int nfixedones; /**< current number of variables fixed to one in the constraint */
115  int firstnonfixed; /**< index of first locally non-fixed binary variable in binvars array */
116  int lastnonfixed; /**< index of last locally non-fixed binary variable in binvars array */
117  unsigned int cliqueadded:1; /**< was the set partitioning condition already added as clique? */
118  unsigned int sorted:1; /**< are the coefficients of the binary variables are sorted in non-decreasing order */
119 };
120 
121 /** constraint handler data */
122 struct SCIP_ConshdlrData
123 {
124  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events on binary variables */
125  SCIP_HASHMAP* varmap; /**< hash map mapping a linking variable to its linking constraint */
126  SCIP_Bool linearize; /**< should the linking constraint be linearize after the binary variable are created */
127 };
128 
129 /*
130  * Local methods
131  */
132 
133 /** returns for a given linking variable the corresponding hash map key */
134 static
136  SCIP_VAR* var /**< variable to get the hash map key for */
137  )
138 {
139  /* return the unique variable index + 1 */
140  return (void*)(size_t)(SCIPvarGetIndex(var) + 1); /*lint !e571 !e776*/
141 }
142 
143 /* sort binary variable in non-decreasing order w.r.t. coefficients */
144 static
146  SCIP_CONSDATA* consdata /**< linking constraint data */
147  )
148 {
149  if( consdata->sorted )
150  return;
151 
152  /* sort binary variable in non-decreasing order w.r.t. coefficients */
153  SCIPsortRealPtr(consdata->vals, (void**)consdata->binvars, consdata->nbinvars);
154 
155  consdata->sorted = TRUE;
156 }
157 
158 
159 /** installs rounding locks for the binary variables in the given linking constraint */
160 static
162  SCIP* scip, /**< SCIP data structure */
163  SCIP_CONS* cons, /**< linking constraint */
164  SCIP_VAR** binvars, /**< binary variables */
165  int nbinvars /**< number of binary variables */
166  )
167 {
168  int b;
169 
170  for( b = 0; b < nbinvars; ++b )
171  {
172  SCIP_CALL( SCIPlockVarCons(scip, binvars[b], cons, TRUE, TRUE) );
173  }
174 
175  return SCIP_OKAY;
176 }
177 
178 /** creates constraint handler data for the linking constraint handler */
179 static
181  SCIP* scip, /**< SCIP data structure */
182  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
183  SCIP_EVENTHDLR* eventhdlr /**< event handler */
184  )
185 {
186  assert(scip != NULL);
187  assert(conshdlrdata != NULL);
188  assert(eventhdlr != NULL);
189 
190  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
191 
192  /* create hash map */
193  (*conshdlrdata)->varmap = NULL;
194 
195  /* set event handler for bound change events on binary variables */
196  (*conshdlrdata)->eventhdlr = eventhdlr;
197 
198  return SCIP_OKAY;
199 }
200 
201 /** frees constraint handler data for linking constraint handler */
202 static
204  SCIP* scip, /**< SCIP data structure */
205  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
206  )
207 {
208  assert(conshdlrdata != NULL);
209  assert(*conshdlrdata != NULL);
210 
211  /* free hash map */
212  if( (*conshdlrdata)->varmap != NULL )
213  SCIPhashmapFree(&(*conshdlrdata)->varmap);
214 
215  /* free memory of constraint handler data */
216  SCIPfreeBlockMemory(scip, conshdlrdata);
217 }
218 
219 /** prints linking constraint to file stream */
220 static
222  SCIP* scip, /**< SCIP data structure */
223  SCIP_CONSDATA* consdata, /**< linking constraint data */
224  FILE* file /**< output file (or NULL for standard output) */
225  )
226 {
227  SCIP_VAR** binvars;
228  SCIP_VAR* linkvar;
229  int nbinvars;
230 
231  assert(scip != NULL);
232  assert(consdata != NULL);
233 
234  linkvar = consdata->linkvar;
235  binvars = consdata->binvars;
236  nbinvars = consdata->nbinvars;
237 
238  assert(linkvar != NULL);
239  assert(binvars != NULL || nbinvars == 0);
240 
241  /* print linking variable */
242  SCIP_CALL( SCIPwriteVarName(scip, file, linkvar, FALSE) );
243 
244  SCIPinfoMessage(scip, file, " = ");
245 
246  if( nbinvars == 0 )
247  {
248  SCIPinfoMessage(scip, file, " no binary variables yet");
249  }
250  else
251  {
252  assert(binvars != NULL);
253 
254  SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, binvars, consdata->vals, nbinvars, FALSE) );
255  }
256 
257  return SCIP_OKAY;
258 }
259 
260 /** catches events for variable at given position */
261 static
263  SCIP* scip, /**< SCIP data structure */
264  SCIP_CONSDATA* consdata, /**< linking constraint data */
265  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
266  int pos /**< array position of variable to catch bound change events for */
267  )
268 {
269  SCIP_VAR* var;
270 
271  assert(consdata != NULL);
272  assert(eventhdlr != NULL);
273  assert(0 <= pos && pos < consdata->nbinvars);
274  assert(consdata->binvars != NULL);
275 
276  var = consdata->binvars[pos];
277  assert(var != NULL);
278 
279  /* catch bound change events on variable */
280  /**@todo do we have to add the event SCIP_EVENTTYPE_VARFIXED? */
281  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
282 
283  /* update the fixed variables counters for this variable */
284  if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
285  consdata->nfixedzeros++;
286  else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
287  consdata->nfixedones++;
288 
289  return SCIP_OKAY;
290 }
291 
292 /** drops events for variable at given position */
293 static
295  SCIP* scip, /**< SCIP data structure */
296  SCIP_CONSDATA* consdata, /**< linking constraint data */
297  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
298  int pos /**< array position of variable to catch bound change events for */
299  )
300 {
301  SCIP_VAR* var;
302 
303  assert(consdata != NULL);
304  assert(eventhdlr != NULL);
305  assert(0 <= pos && pos < consdata->nbinvars);
306  assert(consdata->binvars != NULL);
307 
308  var = consdata->binvars[pos];
309  assert(var != NULL);
310 
311  /* drop events on variable */
312  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
313 
314  /* update the fixed variables counters for this variable */
315  if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
316  consdata->nfixedzeros--;
317  else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
318  consdata->nfixedones--;
319 
320  return SCIP_OKAY;
321 }
322 
323 /** catches bound change events for all variables in transformed linking constraint */
324 static
326  SCIP* scip, /**< SCIP data structure */
327  SCIP_CONSDATA* consdata, /**< linking constraint data */
328  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
329  )
330 {
331  int i;
332 
333  assert(consdata != NULL);
334 
335  /* author bzfhende
336  *
337  * TODO should we catch events even in the trivial case of only 1 binary variable
338  */
339 
340  /* catch event for every single variable */
341  for( i = 0; i < consdata->nbinvars; ++i )
342  {
343  SCIP_CALL( catchEvent(scip, consdata, eventhdlr, i) );
344  }
345 
346  return SCIP_OKAY;
347 }
348 
349 /** drops bound change events for all variables in transformed linking constraint */
350 static
352  SCIP* scip, /**< SCIP data structure */
353  SCIP_CONSDATA* consdata, /**< linking constraint data */
354  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
355  )
356 {
357  int i;
358 
359  assert(consdata != NULL);
360 
361  /* author bzfhende
362  *
363  * TODO drop the events even in the trivial case nbinvars == 1?
364  */
365 
366  /* drop event of every single variable */
367  for( i = 0; i < consdata->nbinvars; ++i )
368  {
369  SCIP_CALL( dropEvent(scip, consdata, eventhdlr, i) );
370  }
371 
372  return SCIP_OKAY;
373 }
374 
375 /** linearize the given linking constraint into a set partitioning constraint for the binary variables and a linear
376  * constraint for the linking between the linking variable and the binary variables */
377 static
379  SCIP* scip, /**< SCIP data structure */
380  SCIP_CONS* cons, /**< linking constraint */
381  SCIP_CONSDATA* consdata /**< linking constraint data */
382  )
383 {
384  SCIP_CONS* lincons;
385  int b;
386 
387  SCIPdebugMsg(scip, "linearized linking constraint <%s>\n", SCIPconsGetName(cons));
388 
389  /* create set partitioning constraint for the binary variables */
390  SCIP_CALL( SCIPcreateConsSetpart(scip, &lincons, SCIPconsGetName(cons), consdata->nbinvars, consdata->binvars,
394  SCIP_CALL( SCIPaddCons(scip, lincons) );
395  SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
396 
397  /* create linear constraint for the linking between the binary variables and the linking variable */
398  SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons), 0, NULL, NULL, 0.0, 0.0,
402 
403  for( b = 0; b < consdata->nbinvars; ++b )
404  {
405  SCIP_CALL( SCIPaddCoefLinear(scip, lincons, consdata->binvars[b], consdata->vals[b]) );
406  }
407  SCIP_CALL( SCIPaddCoefLinear(scip, lincons, consdata->linkvar, -1.0) );
408 
409  SCIP_CALL( SCIPaddCons(scip, lincons) );
410  SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
411 
412  return SCIP_OKAY;
413 }
414 
415 /** creates the binary variables */
416 static
418  SCIP* scip, /**< SCIP data structure */
419  SCIP_CONS* cons, /**< linking constraint */
420  SCIP_CONSDATA* consdata, /**< linking constraint data */
421  SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events on binary variables */
422  SCIP_Bool linearize /**< should the linking constraint be linearized */
423  )
424 {
425  SCIP_VAR* linkvar;
426  SCIP_VAR* binvar;
427  int lb;
428  int ub;
429  char name[SCIP_MAXSTRLEN];
430  int nbinvars;
431  int b;
432 
433  assert(scip != NULL);
434  assert(consdata != NULL);
435  assert(consdata->nbinvars == 0);
436  assert(consdata->binvars == NULL);
437 
438  SCIPdebugMsg(scip, "create binary variables for linking variable <%s>\n", SCIPvarGetName(consdata->linkvar));
439 
440  /* author bzfhende
441  *
442  * TODO ensure that this method is only called for integer linking variables, because it does not make sense for continuous linking variables.
443  */
444 
445  linkvar = consdata->linkvar;
446  lb = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(linkvar));
447  ub = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(linkvar));
448 
449  nbinvars = ub - lb + 1;
450  assert(nbinvars > 0);
451 
452  /* allocate block memory for the binary variables */
453  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->binvars, nbinvars) );
454  /* allocate block memory for the binary variables */
455  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vals, nbinvars) );
456  consdata->sizebinvars = nbinvars;
457 
458  /* check if the linking variable is fixed */
459  if( nbinvars == 1 )
460  {
461  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d]", SCIPvarGetName(linkvar), lb);
462 
463  /* creates and captures a fixed binary variables */
464  SCIP_CALL( SCIPcreateVar(scip, &binvar, name, 1.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
465  FALSE, TRUE, NULL, NULL, NULL, NULL, NULL) );
466  SCIP_CALL( SCIPaddVar(scip, binvar) );
467 
468  consdata->binvars[0] = binvar;
469  consdata->vals[0] = lb;
470  }
471  else
472  {
473  for( b = 0; b < nbinvars; ++b)
474  {
475  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d]", SCIPvarGetName(linkvar), lb + b);
476 
477  /* creates and captures variables */
478  SCIP_CALL( SCIPcreateVar(scip, &binvar, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
479  TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
480 
481  /* add variable to the problem */
482  SCIP_CALL( SCIPaddVar(scip, binvar) );
483  consdata->binvars[b] = binvar;
484  consdata->vals[b] = lb + b;
485  }
486  }
487 
488  consdata->nbinvars = nbinvars;
489 
490  assert(consdata->nfixedzeros == 0);
491  assert(consdata->nfixedones == 0);
492 
493  if( SCIPisTransformed(scip) )
494  {
495  /* (rounding) lock binary variable */
496  SCIP_CALL( lockRounding(scip, cons, consdata->binvars, consdata->nbinvars) );
497 
498  /* catch bound change events of variables */
499  SCIP_CALL( catchAllEvents(scip, consdata, eventhdlr) );
500 
501  if( nbinvars > 1 )
502  {
503  if( linearize )
504  {
505  SCIP_CALL( consdataLinearize(scip, cons, consdata) );
506  }
507  else
508  {
509  /* enable constraint */
510  SCIP_CALL( SCIPenableCons(scip, cons) );
511  }
512  }
513  }
514 
515  return SCIP_OKAY;
516 }
517 
518 /** creates consdata */
519 static
521  SCIP* scip, /**< SCIP data structure */
522  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
523  SCIP_CONSDATA** consdata, /**< pointer to constraint data */
524  SCIP_VAR* linkvar, /**< linking variable which is linked */
525  SCIP_VAR** binvars, /**< binary variables */
526  SCIP_Real* vals, /**< coefficients of the binary variables */
527  int nbinvars /**< number of binary starting variables */
528  )
529 {
530  int v;
531 
532  assert(scip!= NULL);
533  assert(consdata != NULL);
534  assert(linkvar != NULL);
535  assert(binvars != NULL || nbinvars == 0);
536  assert(SCIPvarGetType(linkvar) != SCIP_VARTYPE_CONTINUOUS || nbinvars > 0);
537 
538  /* allocate memory for consdata */
539  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
540 
541  (*consdata)->linkvar = linkvar;
542  (*consdata)->nbinvars = nbinvars;
543  (*consdata)->sizebinvars = nbinvars;
544  (*consdata)->row1 = NULL;
545  (*consdata)->row2 = NULL;
546  (*consdata)->nlrow1 = NULL;
547  (*consdata)->nlrow2 = NULL;
548  (*consdata)->cliqueadded = FALSE;
549 
550  /* initialize constraint state */
551  (*consdata)->sorted = FALSE;
552  (*consdata)->firstnonfixed = 0;
553  (*consdata)->lastnonfixed = nbinvars - 1;
554  (*consdata)->nfixedzeros = 0;
555  (*consdata)->nfixedones = 0;
556 
557  if( nbinvars == 0 )
558  {
559  (*consdata)->binvars = NULL;
560  (*consdata)->vals = NULL;
561  }
562  else
563  {
564  /* copy binary variable array */
565  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->binvars, binvars, nbinvars) );
566 
567  /* copy coefficients */
568  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vals, vals, nbinvars) );
569  }
570 
571  /* get transformed variable, if we are in the transformed problem */
572  if( SCIPisTransformed(scip) )
573  {
574  if( nbinvars > 0 )
575  {
576  SCIP_CALL( SCIPgetTransformedVars(scip, nbinvars, (*consdata)->binvars, (*consdata)->binvars) );
577 
578  /* catch bound change events of variables */
579  SCIP_CALL( catchAllEvents(scip, *consdata, eventhdlr) );
580  }
581 
582  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->linkvar, &(*consdata)->linkvar) );
583  }
584 
585  /* author bzfhende
586  *
587  * TODO do we need to forbid multi-aggregations? This was only needed if we substitute and resubstitute linking
588  * variables into linear constraints.
589  */
590 
591  /* capture variables */
592  for( v = 0; v < nbinvars; ++v )
593  {
594  assert((*consdata)->binvars[v] != NULL);
595  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->binvars[v]) );
596  }
597  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->linkvar) );
598 
599  return SCIP_OKAY;
600 }
601 
602 
603 /** free consdata */
604 static
606  SCIP* scip, /**< SCIP data structure */
607  SCIP_CONSDATA** consdata /**< pointer to consdata */
608  )
609 {
610  int v;
611 
612  assert(consdata != NULL);
613  assert(*consdata != NULL);
614  assert((*consdata)->nbinvars == 0 || (*consdata)->binvars != NULL);
615 
616  /* release the rows */
617  if( (*consdata)->row1 != NULL )
618  {
619  assert((*consdata)->row2 != NULL);
620 
621  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row1) );
622  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row2) );
623  }
624 
625  /* release the nlrows */
626  if( (*consdata)->nlrow1 != NULL )
627  {
628  assert((*consdata)->nlrow2 != NULL);
629 
630  SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow1) );
631  SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow2) );
632  }
633 
634  /* capture variables */
635  for( v = 0; v < (*consdata)->nbinvars; ++v )
636  {
637  assert((*consdata)->binvars[v] != NULL);
638  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->binvars[v]) );
639  }
640  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->linkvar) );
641 
642  /* free binary variable array */
643  if( (*consdata)->sizebinvars > 0 )
644  {
645  /* if constraint belongs to transformed problem space, drop bound change events on variables */
646  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vals, (*consdata)->sizebinvars);
647  SCIPfreeBlockMemoryArray(scip, &(*consdata)->binvars, (*consdata)->sizebinvars);
648  }
649 
650  /* check if the fixed counters are reset */
651  assert((*consdata)->nfixedzeros == 0);
652  assert((*consdata)->nfixedones == 0);
653 
654  /* free constraint data */
655  SCIPfreeBlockMemory(scip, consdata);
656 
657  return SCIP_OKAY;
658 }
659 
660 
661 /** analyzes conflicting assignment on given constraint where reason comes from the linking variable lower or upper
662  * bound
663  */
664 static
666  SCIP* scip, /**< SCIP data structure */
667  SCIP_CONS* cons, /**< linking constraint to be processed */
668  SCIP_VAR* linkvar, /**< linking variable */
669  SCIP_VAR* binvar, /**< binary variable is the reason */
670  SCIP_Bool lblinkvar, /**< lower bound of linking variable is the reason */
671  SCIP_Bool ublinkvar /**< upper bound of linking variable is the reason */
672  )
673 {
674  assert(scip != NULL);
675 
676  /* conflict analysis can only be applied in solving stage and if it is turned on */
678  return SCIP_OKAY;
679 
680  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
682 
683  if( lblinkvar )
684  {
685  assert(linkvar != NULL);
686  SCIP_CALL( SCIPaddConflictLb(scip, linkvar, NULL) );
687  }
688 
689  if( ublinkvar )
690  {
691  assert(linkvar != NULL);
692  SCIP_CALL( SCIPaddConflictUb(scip, linkvar, NULL) );
693  }
694 
695  if( binvar != NULL )
696  {
697  SCIP_CALL( SCIPaddConflictBinvar(scip, binvar) );
698  }
699 
700  /* analyze the conflict */
701  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
702 
703  return SCIP_OKAY;
704 }
705 
706 /* author bzfhende
707  *
708  * TODO check if the method below produces valid results even if the variable is continuous
709  */
710 
711 /** fix linking variable to the value of the binary variable at pos */
712 static
714  SCIP* scip, /**< SCIP data structure */
715  SCIP_CONS* cons, /**< linking constraint to be processed */
716  int pos, /**< position of binary variable */
717  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
718  )
719 {
720  SCIP_CONSDATA* consdata;
721  SCIP_VAR* linkvar;
722  SCIP_Bool infeasible;
723  SCIP_Bool tightened;
724  SCIP_Real coef;
725 
726  consdata = SCIPconsGetData(cons);
727  assert(consdata != NULL);
728 
729  linkvar = consdata->linkvar;
730  coef = consdata->vals[pos];
731 
732  /* change lower bound of the linking variable */
733  SCIP_CALL( SCIPinferVarLbCons(scip, linkvar, coef, cons, pos, TRUE, &infeasible, &tightened) );
734 
735  if( infeasible )
736  {
737  assert(coef > SCIPvarGetUbLocal(linkvar));
738  assert(coef >= SCIPvarGetLbLocal(linkvar));
739 
740  SCIP_CALL( analyzeConflict(scip, cons, linkvar, consdata->binvars[pos], FALSE, TRUE) );
741 
742  *cutoff = TRUE;
743  return SCIP_OKAY;
744  }
745  assert(SCIPisFeasLE(scip, coef, SCIPvarGetUbLocal(linkvar)));
746 
747  /* change upper bound of the integer variable */
748  SCIP_CALL( SCIPinferVarUbCons(scip, linkvar, coef, cons, pos, TRUE, &infeasible, &tightened) );
749 
750  if( infeasible )
751  {
752  assert(coef < SCIPvarGetLbLocal(linkvar));
753  assert(coef <= SCIPvarGetUbLocal(linkvar));
754 
755  SCIP_CALL( analyzeConflict(scip, cons, linkvar, consdata->binvars[pos], TRUE, FALSE) );
756 
757  *cutoff = TRUE;
758  return SCIP_OKAY;
759  }
760 
761  assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(linkvar), SCIPvarGetLbLocal(linkvar)));
762 
763  return SCIP_OKAY;
764 }
765 
766 /** checks constraint for violation from the local bound of the linking variable, applies fixings to the binary
767  * variables if possible
768  */
769 static
771  SCIP* scip, /**< SCIP data structure */
772  SCIP_CONS* cons, /**< linking constraint to be processed */
773  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
774  int* nchgbds, /**< pointer to store the number of changes (foxed) variable bounds */
775  SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
776  )
777 {
778  SCIP_CONSDATA* consdata;
779  SCIP_VAR** binvars;
780  SCIP_VAR* linkvar;
781  SCIP_Real* vals;
782  SCIP_Real lb;
783  SCIP_Real ub;
784  int nbinvars;
785  int b;
786  SCIP_Bool infeasible;
787  SCIP_Bool tightened;
788 
789  assert(cons != NULL);
790  assert(SCIPconsGetHdlr(cons) != NULL);
791  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
792  assert(cutoff != NULL);
793  assert(nchgbds != NULL);
794  assert(mustcheck != NULL);
795 
796  consdata = SCIPconsGetData(cons);
797  assert(consdata != NULL);
798 
799  /* ensure that the binary variables are sorted in non-decreasing order w.r.t. their coefficients */
800  consdataSort(consdata);
801 
802  nbinvars = consdata->nbinvars;
803 
804  /* in case there is only at most one binary variables, the constraints should already be disabled */
805  assert(nbinvars > 1);
806 
807  /* if more than one binary variable is fixed to one or at least nbinvars minus one variable are fixed to zero */
808  if( consdata->nfixedones > 0 || consdata->nfixedzeros >= nbinvars-1 )
809  return SCIP_OKAY;
810 
811  linkvar = consdata->linkvar;
812  assert(linkvar != NULL);
813 
814  binvars = consdata->binvars;
815  vals = consdata->vals;
816 
817  lb = SCIPvarGetLbLocal(linkvar);
818  ub = SCIPvarGetUbLocal(linkvar);
819 
820  assert(lb <= ub);
821 
822 #ifndef NDEBUG
823  /* check that the first variable are locally fixed to zero */
824  for( b = 0; b < consdata->firstnonfixed; ++b )
825  assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
826 
827  /* check that the last variable are locally fixed to zero */
828  for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b )
829  assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
830 #endif
831 
832  for( b = consdata->firstnonfixed; b < nbinvars; ++b )
833  {
834  if( SCIPisLT(scip, vals[b], lb) )
835  {
836  SCIP_VAR* var;
837 
838  var = binvars[b];
839  assert(var != NULL);
840 
841  SCIPdebugMsg(scip, "fix variable <%s> to zero due to the lower bound of the linking variable <%s> [%g,%g]\n",
842  SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub);
843 
844  SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -2, &infeasible, &tightened) );
845 
846  if( infeasible )
847  {
848  SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, TRUE, FALSE) );
849  *cutoff = TRUE;
850  return SCIP_OKAY;
851  }
852 
853  if( tightened )
854  (*nchgbds)++;
855 
856  /* adjust constraint state */
857  consdata->firstnonfixed++;
858  }
859  else
860  break;
861  }
862 
863  /* fix binary variables to zero if not yet fixed, from local upper bound + 1*/
864  for( b = consdata->lastnonfixed; b >= 0; --b )
865  {
866  if( SCIPisGT(scip, vals[b], ub) )
867  {
868  SCIP_VAR* var;
869 
870  var = binvars[b];
871  assert(var != NULL);
872 
873  SCIPdebugMsg(scip, "fix variable <%s> to zero due to the upper bound of the linking variable <%s> [%g,%g]\n",
874  SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub);
875 
876  SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -3, &infeasible, &tightened) );
877 
878  if( infeasible )
879  {
880  SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, FALSE, TRUE) );
881  *cutoff = TRUE;
882  return SCIP_OKAY;
883  }
884 
885  if( tightened )
886  (*nchgbds)++;
887 
888  /* adjust constraint state */
889  consdata->lastnonfixed--;
890  }
891  else
892  break;
893  }
894 
895  if( consdata->firstnonfixed > consdata->lastnonfixed )
896  {
897  *cutoff = TRUE;
898  return SCIP_OKAY;
899  }
900 
901  *mustcheck = (*nchgbds) == 0;
902 
903  /* if linking variable is fixed, create for the binary variables which have a coefficient equal to the fixed value a
904  * set partitioning constraint
905  */
906  if( SCIPisEQ(scip, lb, ub) )
907  {
908  if( consdata->firstnonfixed == consdata->lastnonfixed )
909  {
910  SCIP_VAR* var;
911 
912  var = binvars[consdata->firstnonfixed];
913 
914  SCIPdebugMsg(scip, "fix variable <%s> to one due to the fixed linking variable <%s> [%g,%g]\n",
915  SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub);
916 
917  /* TODO can the forbidden cases be covered more elegantly? */
919  return SCIP_OKAY;
920 
924  return SCIP_OKAY;
925 
926  SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, -6, &infeasible, &tightened) );
927 
928  if( infeasible )
929  {
930  SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, TRUE, TRUE) );
931  *cutoff = TRUE;
932  return SCIP_OKAY;
933  }
934 
935  if( tightened )
936  (*nchgbds)++;
937 
938  SCIPdebugMsg(scip, " -> disabling linking constraint <%s>\n", SCIPconsGetName(cons));
939  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
940 
941  *mustcheck = FALSE;
942  }
943  else if( SCIPgetDepth(scip) <= 0 )
944  {
945  SCIP_CONS* setppc;
946  SCIP_VAR** vars;
947  int nvars;
948 
949  /* get sub array of variables which have the same coefficient */
950  vars = &consdata->binvars[consdata->firstnonfixed];
951  nvars = consdata->lastnonfixed - consdata->firstnonfixed + 1;
952 
953  SCIP_CALL( SCIPcreateConsSetpart(scip, &setppc, SCIPconsGetName(cons), nvars, vars,
957 
958  SCIP_CALL( SCIPaddCons(scip, setppc) );
959  SCIP_CALL( SCIPreleaseCons(scip, &setppc) );
960 
961  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
962  }
963  }
964 
965  return SCIP_OKAY;
966 }
967 
968 /** deletes coefficient at given position from the binary variable array */
969 static
971  SCIP* scip, /**< SCIP data structure */
972  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
973  SCIP_CONS* cons, /**< linking constraint */
974  int pos /**< position of coefficient to delete */
975  )
976 {
977  SCIP_CONSDATA* consdata;
978  SCIP_VAR* var;
979 
980  assert(scip != NULL);
981  assert(eventhdlr != NULL);
982 
983  consdata = SCIPconsGetData(cons);
984  assert(consdata != NULL);
985  assert(0 <= pos && pos < consdata->nbinvars);
986 
987  var = consdata->binvars[pos];
988  assert(var != NULL);
989  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
990 
991  /* remove the rounding locks for the deleted variable */
992  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
993 
994  /* if we are in transformed problem, delete the event data of the variable */
995  if( SCIPconsIsTransformed(cons) )
996  {
997  SCIP_CONSHDLR* conshdlr;
998  SCIP_CONSHDLRDATA* conshdlrdata;
999 
1000  /* get event handler */
1001  conshdlr = SCIPconsGetHdlr(cons);
1002  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1003  assert(conshdlrdata != NULL);
1004  assert(conshdlrdata->eventhdlr != NULL);
1005 
1006  /* drop bound change events of variable */
1007  SCIP_CALL( dropEvent(scip, consdata, conshdlrdata->eventhdlr, pos) );
1008  }
1009 
1010  /* move the last variable to the free slot */
1011  if( pos != consdata->nbinvars - 1 )
1012  {
1013  consdata->binvars[pos] = consdata->binvars[consdata->nbinvars-1];
1014  consdata->vals[pos] = consdata->vals[consdata->nbinvars-1];
1015  consdata->sorted = FALSE;
1016  }
1017 
1018  consdata->nbinvars--;
1019 
1020  /* release variable */
1021  SCIP_CALL( SCIPreleaseVar(scip, &var) );
1022 
1023  return SCIP_OKAY;
1024 }
1025 
1026 /** remove the trailing and leading binary variables that are fixed to zero */
1027 static
1029  SCIP* scip, /**< SCIP data structure */
1030  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1031  SCIP_CONS* cons /**< linking constraint */
1032  )
1033 {
1034  SCIP_CONSDATA* consdata;
1035  int nbinvars;
1036  int b;
1037 
1038  consdata = SCIPconsGetData(cons);
1039  assert(consdata != NULL);
1040  assert(consdata->sorted);
1041 
1042  assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetDepth(scip) <= 0);
1043  assert(!SCIPinProbing(scip));
1044  assert(!SCIPinRepropagation(scip));
1045 
1046  nbinvars = consdata->nbinvars;
1047 
1048  for( b = nbinvars - 1; b > consdata->lastnonfixed; --b )
1049  {
1050  SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) );
1051  }
1052 
1053  for( b = consdata->firstnonfixed - 1; b >= 0; --b )
1054  {
1055  SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) );
1056  }
1057 
1058  for( b = consdata->nbinvars - 1; b >= 0; --b )
1059  {
1060  if( SCIPvarGetUbLocal(consdata->binvars[b]) < 0.5 )
1061  {
1062  SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) );
1063  }
1064  }
1065 
1066  /* set the constraint state */
1067  consdata->firstnonfixed = 0;
1068  consdata->lastnonfixed = consdata->nbinvars - 1;
1069 
1070  return SCIP_OKAY;
1071 }
1072 
1073 /** tightened the linking variable due to binary variables which are fixed to zero */
1074 static
1076  SCIP* scip, /**< SCIP data structure */
1077  SCIP_CONS* cons, /**< linking constraint to be processed */
1078  SCIP_CONSDATA* consdata, /**< linking constraint to be processed */
1079  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1080  int* nchgbds /**< pointer to store the number of changed variable bounds */
1081  )
1082 {
1083  SCIP_VAR** binvars;
1084  SCIP_VAR* linkvar;
1085  SCIP_Real* vals;
1086 
1087  SCIP_Bool infeasible;
1088  SCIP_Bool tightened;
1089  int nbinvars;
1090  int b;
1091 
1092  /* if more than one binary variable is fixed to one or at least nbinvars minus one variable are fixed to zero return */
1093  if( consdata->nfixedones > 1 || consdata->nfixedzeros >= consdata->nbinvars-1 )
1094  return SCIP_OKAY;
1095 
1096  if( *cutoff )
1097  return SCIP_OKAY;
1098 
1099  assert(consdata->sorted);
1100 
1101  linkvar = consdata->linkvar;
1102  binvars = consdata->binvars;
1103  vals = consdata->vals;
1104  nbinvars = consdata->nbinvars;
1105 
1106 #ifndef NDEBUG
1107  /* check that the first variable are locally fixed to zero */
1108  for( b = 0; b < consdata->firstnonfixed; ++b )
1109  assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
1110 #endif
1111 
1112  assert(consdata->firstnonfixed < nbinvars);
1113  assert(consdata->lastnonfixed < nbinvars);
1114 
1115  /* find first non fixed binary variable */
1116  for( b = consdata->firstnonfixed; b < nbinvars; ++b )
1117  {
1118  if( SCIPvarGetUbLocal(binvars[b]) > 0.5 )
1119  break;
1120 
1121  consdata->firstnonfixed++;
1122  }
1123 
1124  SCIP_CALL( SCIPinferVarLbCons(scip, linkvar, vals[b], cons, -4, TRUE, &infeasible, &tightened) );
1125 
1126  /* start conflict analysis if infeasible */
1127  if( infeasible )
1128  {
1129  /* analyze the cutoff if if SOLVING stage and conflict analysis is turned on */
1131  {
1132  SCIPdebugMsg(scip, "conflict at <%s> due to bounds and fixed binvars: [lb,ub] = [%g,%g]; b= %d; coef = %g \n",
1133  SCIPvarGetName(linkvar), SCIPvarGetLbLocal(linkvar), SCIPvarGetUbLocal(linkvar), b, vals[b]);
1134 
1136 
1137  /* ??????????? use resolve method and only add binvars which are needed to exceed the upper bound */
1138 
1139  /* add conflicting variables */
1140  SCIP_CALL( SCIPaddConflictUb(scip, linkvar, NULL) );
1141 
1142  for( b = 0; b < consdata->firstnonfixed; ++b )
1143  {
1144  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
1145  }
1146 
1147  /* analyze the conflict */
1148  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1149  }
1150 
1151  *cutoff = TRUE;
1152  return SCIP_OKAY;
1153  }
1154 
1155  if( tightened )
1156  (*nchgbds)++;
1157 
1158 #ifndef NDEBUG
1159  /* check that the last variable are locally fixed to zero */
1160  for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b )
1161  assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
1162 #endif
1163 
1164  /* find last non fixed variable */
1165  for( b = consdata->lastnonfixed; b >= 0; --b )
1166  {
1167  if( SCIPvarGetUbLocal(binvars[b]) > 0.5 )
1168  break;
1169 
1170  consdata->lastnonfixed--;
1171  }
1172 
1174  SCIP_CALL( SCIPinferVarUbCons(scip, linkvar, (SCIP_Real)vals[b], cons, -5, TRUE, &infeasible, &tightened) );
1175 
1176  if( infeasible )
1177  {
1178  /* conflict analysis can only be applied in solving stage and if conflict analysis is turned on */
1180  {
1181  SCIPdebugMsg(scip, "conflict at <%s> due to bounds and fixed binvars: [lb,ub] = [%g,%g]; b = %d; coef = %g,\n",
1182  SCIPvarGetName(linkvar), SCIPvarGetLbLocal(linkvar), SCIPvarGetUbLocal(linkvar), b, vals[b]);
1183 
1185 
1186  /* ??????????? use resolve method and only add binvars which are needed to fall below the lower bound */
1187 
1188  /* add conflicting variables */
1189  SCIP_CALL( SCIPaddConflictLb(scip, linkvar, NULL) );
1190 
1191  for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b )
1192  {
1193  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
1194  }
1195 
1196  /* analyze the conflict */
1197  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1198  }
1199 
1200  *cutoff = TRUE;
1201  return SCIP_OKAY;
1202  }
1203 
1204  if( tightened )
1205  (*nchgbds)++;
1206 
1207  return SCIP_OKAY;
1208 }
1209 
1210 /** checks constraint for violation only looking at the fixed binary variables, applies further fixings if possible */
1211 static
1213  SCIP* scip, /**< SCIP data structure */
1214  SCIP_CONS* cons, /**< linking constraint to be processed */
1215  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1216  int* nchgbds, /**< pointer to store the number of changed variable bounds */
1217  SCIP_Bool* addcut, /**< pointer to store whether this constraint must be added as a cut */
1218  SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
1219  )
1220 {
1221  SCIP_CONSDATA* consdata;
1222  SCIP_Bool infeasible;
1223  SCIP_Bool tightened;
1224 
1225  assert(cons != NULL);
1226  assert(SCIPconsGetHdlr(cons) != NULL);
1227  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1228  assert(cutoff != NULL);
1229  assert(nchgbds != NULL);
1230  assert(addcut != NULL);
1231  assert(mustcheck != NULL);
1232 
1233  consdata = SCIPconsGetData(cons);
1234  assert(consdata != NULL);
1235  assert(consdata->nbinvars == 0 || consdata->binvars != NULL);
1236  assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nbinvars);
1237  assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nbinvars);
1238 
1239  /* ensure that the binary variables are sorted in non-decreasing order w.r.t. their coefficients */
1240  consdataSort(consdata);
1241 
1242  /* in case there is only at most one binary variables, the constraints should already be disabled */
1243  assert(consdata->nbinvars > 1);
1244 
1245  if( *cutoff )
1246  return SCIP_OKAY;
1247 
1248  if( consdata->nfixedones == 1 )
1249  {
1250  /* exactly one variable is fixed to 1:
1251  * - all other binary variables in a set partitioning must be zero
1252  * - linking variable is fixed to that binary variable
1253  */
1254  if( consdata->nfixedzeros < consdata->nbinvars - 1 ||
1255  SCIPisLT(scip, SCIPvarGetLbLocal(consdata->linkvar), SCIPvarGetUbLocal(consdata->linkvar)) )
1256  {
1257  SCIP_VAR** vars;
1258  SCIP_VAR* var;
1259 #ifndef NDEBUG
1260  SCIP_Bool fixedonefound;
1261 #endif
1262  int nvars;
1263  int v;
1264 
1265  SCIPdebugMsg(scip, " -> fixing all other variables to zero due to the set partitioning condition <%s>\n",
1266  SCIPconsGetName(cons));
1267 
1268  /* unfixed variables exist: fix them to zero;
1269  * this could result in additional variables fixed to one due to aggregations; in this case, the
1270  * constraint is infeasible in local bounds
1271  */
1272  vars = consdata->binvars;
1273  nvars = consdata->nbinvars;
1274 #ifndef NDEBUG
1275  fixedonefound = FALSE;
1276 #endif
1277 
1278  for( v = 0; v < nvars && consdata->nfixedones == 1 && !(*cutoff); ++v )
1279  {
1280  var = vars[v];
1281  assert(SCIPvarIsBinary(var));
1282  /* TODO can this be handled more elegantly? */
1284  continue;
1285 
1289  continue;
1290 
1291  if( SCIPvarGetLbLocal(var) < 0.5 )
1292  {
1293  SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -1, &infeasible, &tightened) );
1294  assert(!infeasible);
1295  SCIPdebugMsg(scip, " -> fixed <%s> to zero (tightened=%u)\n", SCIPvarGetName(var), tightened);
1296  }
1297  else
1298  {
1299 #ifndef NDEBUG
1300  fixedonefound = TRUE;
1301 #endif
1302  /* fix linking variable */
1303  /* TODO check if variable status allows fixing (probably in consFixLinkvar) */
1304  SCIP_CALL( consFixLinkvar(scip, cons, v, cutoff) );
1305  }
1306  }
1307  if( !(*cutoff) )
1308  {
1309  /* the fixed to one variable must have been found, and at least one variable must have been fixed */
1310  assert(consdata->nfixedones >= 1 || fixedonefound);
1311 
1312  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1313  (*nchgbds)++;
1314  }
1315  }
1316 
1317  /* now all other variables are fixed to zero:
1318  * the constraint is feasible, and if it's not modifiable, it is redundant
1319  */
1320  if( !SCIPconsIsModifiable(cons) && consdata->nfixedones == 1 )
1321  {
1322  SCIPdebugMsg(scip, " -> disabling set linking constraint <%s>\n", SCIPconsGetName(cons));
1323  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1324  }
1325  }
1326  else if( consdata->nfixedones >= 2 )
1327  {
1328  /* at least two variables are fixed to 1:
1329  * - the set partitioning condition is violated
1330  */
1331  SCIPdebugMsg(scip, " -> conflict on " CONSHDLR_NAME " constraint <%s> due to the set partitioning condition\n", SCIPconsGetName(cons));
1332 
1333  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1334 
1335  /* conflict analysis can only be applied in solving stage and if it is applicable */
1337  {
1338  SCIP_VAR** vars;
1339  int nvars;
1340  int n;
1341  int v;
1342 
1343  vars = consdata->binvars;
1344  nvars = consdata->nbinvars;
1345 
1346  /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
1348 
1349  n = 0;
1350 
1351  for( v = 0; v < nvars && n < 2; ++v )
1352  {
1353  if( SCIPvarGetLbLocal(vars[v]) > 0.5 )
1354  {
1355  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[v]) );
1356  n++;
1357  }
1358  }
1359  assert(n == 2);
1360 
1361  /* analyze the conflict */
1362  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1363  }
1364 
1365  *cutoff = TRUE;
1366  }
1367  else if( consdata->nfixedzeros == consdata->nbinvars )
1368  {
1369  /* all variables are fixed to zero:
1370  * - the set partitioning condition is violated, and if it's unmodifiable, the node
1371  * can be cut off -- otherwise, the constraint must be added as a cut and further pricing must
1372  * be performed
1373  */
1374  assert(consdata->nfixedones == 0);
1375 
1376  SCIPdebugMsg(scip, " -> " CONSHDLR_NAME " constraint <%s> is infeasible due to the set partitioning condition\n",
1377  SCIPconsGetName(cons));
1378 
1379  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1380  if( SCIPconsIsModifiable(cons) )
1381  *addcut = TRUE;
1382  else
1383  {
1384  /* conflict analysis can only be applied in solving stage and if it is applicable */
1386  {
1387  SCIP_VAR** vars;
1388  int nvars;
1389  int v;
1390 
1391  vars = consdata->binvars;
1392  nvars = consdata->nbinvars;
1393 
1394  /* initialize conflict analysis, add all variables of infeasible constraint to conflict candidate queue */
1396 
1397  for( v = 0; v < nvars; ++v )
1398  {
1399  assert(SCIPvarGetUbLocal(vars[v]) < 0.5);
1400  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[v]) );
1401  }
1402 
1403  /* analyze the conflict */
1404  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1405  }
1406  *cutoff = TRUE;
1407  }
1408  }
1409  else if( consdata->nfixedzeros == consdata->nbinvars - 1 )
1410  {
1411  /* all variables except one are fixed to zero:
1412  * - an unmodifiable set partitioning constraint is feasible and can be disabled after the
1413  * remaining variable is fixed to one
1414  * - a modifiable set partitioning constraint must be checked manually
1415  */
1416  assert(consdata->nfixedones == 0);
1417 
1418  if( !SCIPconsIsModifiable(cons) )
1419  {
1420  SCIP_VAR** vars;
1421  SCIP_VAR* var;
1422  int nvars;
1423  int v;
1424 
1425  /* search the single variable that can be fixed */
1426  vars = consdata->binvars;
1427  nvars = consdata->nbinvars;
1428  for( v = 0; v < nvars && !(*cutoff); ++v )
1429  {
1430  var = vars[v];
1431  assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)));
1432  assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
1433 
1434  if( SCIPvarGetUbLocal(var) > 0.5 )
1435  {
1436  assert(SCIPvarGetLbLocal(var) < 0.5);
1437  SCIPdebugMsg(scip, " -> fixing remaining binary variable <%s> to one in " CONSHDLR_NAME " constraint <%s>\n",
1438  SCIPvarGetName(var), SCIPconsGetName(cons));
1439 
1441  {
1442  SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, -1, &infeasible, &tightened) );
1443  assert(!infeasible);
1444  assert(tightened);
1445  }
1446 
1447  /* fix linking variable */
1448  /* TODO check if variable status allows fixing (probably in consFixLinkvar)*/
1449  SCIP_CALL( consFixLinkvar(scip, cons, v, cutoff) );
1450  break;
1451  }
1452  }
1453  assert(v < nvars);
1454  assert(consdata->nfixedzeros == consdata->nbinvars - 1);
1455  assert(consdata->nfixedones == 1);
1456 
1457  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1458  (*nchgbds)++;
1459  }
1460  }
1461  else
1462  {
1463  SCIP_CALL( tightenedLinkvar(scip, cons, consdata, cutoff, nchgbds) );
1464  }
1465 
1466  *mustcheck = (*nchgbds) == 0;
1467 
1468  assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nbinvars);
1469 
1470  return SCIP_OKAY;
1471 }
1472 
1473 /** returns whether the given solution is feasible for the given linking constraint */
1474 static
1476  SCIP* scip, /**< SCIP data structure */
1477  SCIP_CONS* cons, /**< linking constraint to be checked */
1478  SCIP_SOL* sol /**< primal solution, or NULL for current LP/pseudo solution */
1479  )
1480 {
1481  SCIP_CONSDATA* consdata;
1482  SCIP_VAR** binvars;
1483  SCIP_Real* vals;
1484  SCIP_Real solval;
1485  SCIP_Real linksum;
1486  SCIP_Real linkvarval;
1487  SCIP_Real setpartsum;
1488  SCIP_Real setpartsumbound;
1489  SCIP_Real absviol;
1490  SCIP_Real relviol;
1491  int nbinvars;
1492  int b;
1493 
1494  assert(scip != NULL);
1495  assert(cons != NULL);
1496 
1497  SCIPdebugMsg(scip, "checking linking constraint <%s> for feasibility of solution %p\n", SCIPconsGetName(cons), (void*)sol);
1498 
1499  consdata = SCIPconsGetData(cons);
1500  assert(consdata != NULL);
1501  assert(consdata->binvars != NULL || consdata->nbinvars == 0);
1502 
1503  /* in case there is only at most one binary variables, the constraints should already be disabled */
1504  assert(consdata->nbinvars > 1);
1505 
1506  /* calculate the constraint's activity for the linking part and the set partitioning part */
1507  binvars = consdata->binvars;
1508  vals = consdata->vals;
1509  nbinvars = consdata->nbinvars;
1510 
1511  linksum = 0.0;
1512  setpartsum = 0.0;
1513  setpartsumbound = 1.0 + 2*SCIPfeastol(scip);
1514 
1515  for( b = 0; b < nbinvars && setpartsum < setpartsumbound; ++b ) /* if sum >= sumbound, the feasibility is clearly decided */
1516  {
1517  assert(SCIPvarIsBinary(binvars[b]));
1518 
1519  solval = SCIPgetSolVal(scip, sol, binvars[b]);
1520  assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0));
1521 
1522  linksum += vals[b] * solval;
1523  setpartsum += solval;
1524  }
1525 
1526  /* calculate and update absolute and relative violation of the equality constraint */
1527  linkvarval = SCIPgetSolVal(scip, sol, consdata->linkvar);
1528  absviol = REALABS(linksum - linkvarval);
1529  relviol = REALABS(SCIPrelDiff(linksum, linkvarval));
1530  if( sol != NULL )
1531  SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);
1532 
1533  /* calculate and update absolute and relative violation of the set partitioning constraint */
1534  absviol = REALABS(setpartsum - 1.0);
1535  relviol = REALABS(SCIPrelDiff(setpartsum, 1.0));
1536  if( sol != NULL )
1537  SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);
1538 
1539  /* check if the fixed binary variable match with the linking variable */
1540  return SCIPisFeasEQ(scip, linksum, linkvarval) && SCIPisFeasEQ(scip, setpartsum, 1.0);
1541 }
1542 
1543 #if 0
1544 /** transfer aggregated integer variables to the corresponding binary variables */
1545 static
1547  SCIP* scip, /**< SCIP data structure */
1548  SCIP_HASHMAP* varmap, /**< hash map mapping a integer variables to its linking constraint */
1549  SCIP_CONS** conss, /**< array of linking constraint */
1550  int nconss, /**< number of linking constraints */
1551  int* naggrvars, /**< pointer to store the number of aggregate variables */
1552  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
1553  )
1554 {
1555  SCIP_CONS* aggrcons;
1556  SCIP_CONSDATA* aggrconsdata;
1557  SCIP_CONSDATA* consdata;
1558  SCIP_VAR** binvars;
1559  SCIP_VAR** aggrbinvars;
1560  SCIP_VAR* linkvar;
1561  SCIP_VAR* aggrvar;
1562  SCIP_Real aggrconst;
1563  SCIP_Real aggrscalar;
1564  SCIP_Bool infeasible;
1565  SCIP_Bool redundant;
1566  SCIP_Bool aggregated;
1567  int offset;
1568  int aggroffset;
1569  int nbinvars;
1570  int shift;
1571  int b;
1572  int c;
1573 
1574  assert(varmap != NULL);
1575 
1576  for( c = 0; c < nconss; ++c )
1577  {
1578  consdata = SCIPconsGetData(conss[c]);
1579  assert(consdata != NULL);
1580 
1581  linkvar = consdata->linkvar;
1582  assert(linkvar != NULL);
1583 
1585  {
1586  aggrvar = SCIPvarGetAggrVar(linkvar);
1587  aggrcons = (SCIP_CONS*) SCIPhashmapGetImage(varmap, getHashmapKey(aggrvar));
1588 
1589  /* check if the aggregate variable belongs to a linking constraint */
1590  if( aggrcons != NULL )
1591  {
1592  aggrconsdata = SCIPconsGetData(aggrcons);
1593  assert(aggrconsdata != NULL);
1594 
1595  aggrconst = SCIPvarGetAggrConstant(linkvar);
1596  aggrscalar = SCIPvarGetAggrScalar(linkvar);
1597 
1598  /**@todo extend the aggregation for those cases were the aggrscalar is not equal to 1.0 */
1599  if( SCIPisEQ(scip, aggrscalar, 1.0 ) )
1600  {
1601  /* since both variables are integer variable and the aggrscalar is 1.0 the aggrconst should
1602  * integral
1603  */
1604  assert(SCIPisIntegral(scip, aggrconst));
1605  shift = SCIPconvertRealToInt(scip, aggrconst);
1606 
1607  offset = consdata->offset;
1608  binvars = consdata->binvars;
1609  aggroffset = aggrconsdata->offset;
1610  aggrbinvars = aggrconsdata->binvars;
1611 
1612  nbinvars = MIN(consdata->nbinvars + offset, aggrconsdata->nbinvars + shift + aggroffset);
1613 
1614  for( b = MAX(offset, aggroffset-shift); b < nbinvars; ++b )
1615  {
1616  assert(b - offset >= 0);
1617  assert(b + shift - aggroffset >= 0);
1618  assert(b < consdata->nbinvars);
1619  assert(b < aggrconsdata->nbinvars - shift);
1620 
1621  /* add aggregation x - y = 0.0 */
1622  SCIP_CALL( SCIPaggregateVars(scip, binvars[b-offset], aggrbinvars[b+shift-aggroffset], 1.0, -1.0, 0.0,
1623  &infeasible, &redundant, &aggregated) );
1624 
1625  if( infeasible )
1626  {
1627  (*cutoff) = TRUE;
1628  return SCIP_OKAY;
1629  }
1630 
1631  if( aggregated )
1632  (*naggrvars)++;
1633  }
1634  }
1635  }
1636  }
1637  }
1638  return SCIP_OKAY;
1639 }
1640 #endif
1641 
1642 /** create two rows for the linking constraint
1643  *
1644  * - row1: {sum_{b=1}^n-1 vals[b] * binvars[b]} - linkvar = 0
1645  * - row2: {sum_{b=0}^n-1 binvars[b]} = 1.0
1646  */
1647 static
1649  SCIP* scip, /**< SCIP data structure */
1650  SCIP_CONS* cons /**< linking constraint */
1651  )
1652 {
1653  SCIP_CONSDATA* consdata;
1654  char rowname[SCIP_MAXSTRLEN];
1655  int b;
1656 
1657  assert( cons != NULL);
1658 
1659  /* get constraint data */
1660  consdata = SCIPconsGetData(cons);
1661  assert(consdata != NULL);
1662  assert(consdata->row1 == NULL);
1663  assert(consdata->row2 == NULL);
1664  assert(consdata->nbinvars > 1);
1665 
1666  /* create the LP row which captures the linking between the real and binary variables */
1667  (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[link]", SCIPconsGetName(cons));
1668 
1669  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row1, cons, rowname, 0.0, 0.0,
1671 
1672  /* add linking variable to the row */
1673  assert(consdata->linkvar != NULL);
1674  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row1, consdata->linkvar, -1.0) );
1675 
1676  /* adding binary variables to the row */
1677  assert(consdata->binvars != NULL);
1678  for( b = 0; b < consdata->nbinvars; ++b )
1679  {
1680  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row1, consdata->binvars[b], consdata->vals[b]) );
1681  }
1682 
1683  /* create the LP row which captures the set partitioning condition of the binary variables */
1684  (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[setppc]", SCIPconsGetName(cons));
1685  assert( consdata->nbinvars > 0 );
1686 
1687  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row2, cons, rowname, 1.0, 1.0,
1689 
1690  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row2, consdata->nbinvars, consdata->binvars, 1.0) );
1691 
1692  return SCIP_OKAY;
1693 }
1694 
1695 
1696 /** adds linking constraint as cut to the LP */
1697 static
1699  SCIP* scip, /**< SCIP data structure */
1700  SCIP_CONS* cons, /**< linking constraint */
1701  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1702  )
1703 {
1704  SCIP_CONSDATA* consdata;
1705 
1706  assert( cutoff != NULL );
1707  *cutoff = FALSE;
1708 
1709  consdata = SCIPconsGetData(cons);
1710  assert(consdata != NULL);
1711 
1712  /* in case there is only at most one binary variables, the constraints should already be disabled */
1713  assert(consdata->nbinvars > 1);
1714 
1715  if( consdata->row1 == NULL )
1716  {
1717  assert(consdata->row2 == NULL);
1718 
1719  /* convert linking data into LP rows */
1720  SCIP_CALL( createRows(scip, cons) );
1721  }
1722  assert(consdata->row1 != NULL);
1723  assert(consdata->row2 != NULL);
1724 
1725  /* insert LP linking row as cut */
1726  if( !SCIProwIsInLP(consdata->row1) )
1727  {
1728  SCIPdebugMsg(scip, "adding linking row of constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
1729  SCIP_CALL( SCIPaddRow(scip, consdata->row1, TRUE/*FALSE*/, cutoff) );
1730  }
1731 
1732  /* insert LP set partitioning row as cut */
1733  if( !SCIProwIsInLP(consdata->row2) )
1734  {
1735  SCIPdebugMsg(scip, "adding set partitioning row of constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
1736  SCIP_CALL( SCIPaddRow(scip, consdata->row2, TRUE/*FALSE*/, cutoff) );
1737  }
1738 
1739  return SCIP_OKAY;
1740 }
1741 
1742 /** adds linking constraint as rows to the NLP, if not added yet */
1743 static
1745  SCIP* scip, /**< SCIP data structure */
1746  SCIP_CONS* cons /**< linking constraint */
1747  )
1748 {
1749  SCIP_CONSDATA* consdata;
1750 
1751  assert(SCIPisNLPConstructed(scip));
1752 
1753  /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
1754  if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
1755  return SCIP_OKAY;
1756 
1757  consdata = SCIPconsGetData(cons);
1758  assert(consdata != NULL);
1759 
1760  if( consdata->nlrow1 == NULL )
1761  {
1762  char rowname[SCIP_MAXSTRLEN];
1763  SCIP_Real* coefs;
1764  int i;
1765 
1766  assert(consdata->nlrow2 == NULL);
1767 
1768  /* create the NLP row which captures the linking between the real and binary variables */
1769  (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[link]", SCIPconsGetName(cons));
1770 
1771  /* create nlrow1 with binary variables */
1772  SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow1, rowname,
1773  0.0, consdata->nbinvars, consdata->binvars, consdata->vals, NULL, 0.0, 0.0, SCIP_EXPRCURV_LINEAR) );
1774  /* add linking variable to the row */
1775  SCIP_CALL( SCIPaddLinearCoefToNlRow(scip, consdata->nlrow1, consdata->linkvar, -1.0) );
1776 
1777  /* create the NLP row which captures the set partitioning condition of the binary variables */
1778  (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[setppc]", SCIPconsGetName(cons));
1779 
1780  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nbinvars) );
1781  for( i = 0; i < consdata->nbinvars; ++i )
1782  coefs[i] = 1.0;
1783 
1784  SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow2, rowname,
1785  0.0, consdata->nbinvars, consdata->binvars, coefs, NULL, 1.0, 1.0, SCIP_EXPRCURV_LINEAR) );
1786 
1787  SCIPfreeBufferArray(scip, &coefs);
1788  }
1789 
1790  assert(SCIPnlrowIsInNLP(consdata->nlrow1) == SCIPnlrowIsInNLP(consdata->nlrow2));
1791  if( !SCIPnlrowIsInNLP(consdata->nlrow1) )
1792  {
1793  SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow1) );
1794  SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow2) );
1795  }
1796 
1797  return SCIP_OKAY;
1798 }
1799 
1800 /** checks constraint for violation, and adds it as a cuts if possible */
1801 static
1803  SCIP* scip, /**< SCIP data structure */
1804  SCIP_CONS* cons, /**< linking constraint to be separated */
1805  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1806  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1807  SCIP_Bool* separated, /**< pointer to store TRUE, if a cut was found */
1808  int* nchgbds /**< pointer to store the number of changed variables bounds */
1809  )
1810 {
1811  SCIP_CONSDATA* consdata;
1812  SCIP_Bool addcut;
1813  SCIP_Bool mustcheck;
1814 
1815  assert(cons != NULL);
1816  assert(SCIPconsGetHdlr(cons) != NULL);
1817  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1818  assert(cutoff != NULL);
1819  assert(separated != NULL);
1820  assert(nchgbds != NULL);
1821 
1822  consdata = SCIPconsGetData(cons);
1823  assert(consdata != NULL);
1824 
1825  /* in case there is only at most one binary variables, the constraints should already be disabled */
1826  assert(consdata->nbinvars > 1);
1827 
1828  SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons));
1829 
1830  *cutoff = FALSE;
1831  addcut = FALSE;
1832  mustcheck = TRUE;
1833 
1834  /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
1835  if( sol == NULL )
1836  {
1837  SCIP_CALL( processRealBoundChg(scip, cons, cutoff, nchgbds, &mustcheck) );
1838  }
1839 
1840  if( mustcheck && !(*cutoff) )
1841  {
1842  /* variable's fixings didn't give us any information -> we have to check the constraint */
1843  if( sol == NULL && consdata->row1 != NULL )
1844  {
1845  SCIP_Real feasibility;
1846  SCIP_Real tmp;
1847 
1848  assert(consdata->row2 != NULL);
1849 
1850  /* skip constraints already in the LP */
1851  if( SCIProwIsInLP(consdata->row1) && SCIProwIsInLP(consdata->row2))
1852  return SCIP_OKAY;
1853 
1854  feasibility = 1.0;
1855 
1856  /* check first row (linking) for feasibility */
1857  if( !SCIProwIsInLP(consdata->row1) )
1858  {
1859  tmp = SCIPgetRowLPFeasibility(scip, consdata->row1);
1860  feasibility = MIN(feasibility, tmp);
1861  }
1862 
1863  /* check second row (setppc) for feasibility */
1864  if( !SCIProwIsInLP(consdata->row2) )
1865  {
1866  tmp = SCIPgetRowLPFeasibility(scip, consdata->row2);
1867  feasibility = MIN(feasibility, tmp);
1868  }
1869  addcut = SCIPisFeasNegative(scip, feasibility);
1870  }
1871  else
1872  addcut = !checkCons(scip, cons, sol);
1873 
1874  if( !addcut )
1875  {
1876  /* constraint was feasible -> increase age */
1877  SCIP_CALL( SCIPincConsAge(scip, cons) );
1878  }
1879  }
1880 
1881  if( addcut )
1882  {
1883  /* insert LP row as cut */
1884  assert(!(*cutoff));
1885  SCIP_CALL( addCuts(scip, cons, cutoff) );
1886  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1887  *separated = TRUE;
1888  }
1889 
1890  return SCIP_OKAY;
1891 }
1892 
1893 /** enforces the pseudo solution on the given constraint */
1894 static
1896  SCIP* scip, /**< SCIP data structure */
1897  SCIP_CONS* cons, /**< linking constraint to be separated */
1898  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1899  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
1900  int* nchgbds, /**< pointer to store the number of changed variable bounds */
1901  SCIP_Bool* solvelp /**< pointer to store TRUE, if the LP has to be solved */
1902  )
1903 {
1904  SCIP_Bool addcut;
1905  SCIP_Bool mustcheck;
1906 
1907  assert(!SCIPhasCurrentNodeLP(scip));
1908  assert(cons != NULL);
1909  assert(SCIPconsGetHdlr(cons) != NULL);
1910  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1911  assert(cutoff != NULL);
1912  assert(infeasible != NULL);
1913  assert(nchgbds != NULL);
1914  assert(solvelp != NULL);
1915 
1916  addcut = FALSE;
1917  mustcheck = TRUE;
1918 
1919  /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
1920  SCIP_CALL( processRealBoundChg(scip, cons, cutoff, nchgbds, &mustcheck) );
1921  SCIP_CALL( processBinvarFixings(scip, cons, cutoff, nchgbds, &addcut, &mustcheck) );
1922 
1923  if( mustcheck )
1924  {
1925  assert(!addcut);
1926 
1927  if( checkCons(scip, cons, NULL) )
1928  {
1929  /* constraint was feasible -> increase age */
1930  SCIP_CALL( SCIPincConsAge(scip, cons) );
1931  }
1932  else
1933  {
1934  /* constraint was infeasible -> reset age */
1935  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1936  *infeasible = TRUE;
1937  }
1938  }
1939 
1940  if( addcut )
1941  {
1942  assert(!(*cutoff));
1943  /* a cut must be added to the LP -> we have to solve the LP immediately */
1944  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1945  *solvelp = TRUE;
1946  }
1947 
1948  return SCIP_OKAY;
1949 }
1950 
1951 /** helper function to enforce constraints */
1952 static
1954  SCIP* scip, /**< SCIP data structure */
1955  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1956  SCIP_CONS** conss, /**< constraints to process */
1957  int nconss, /**< number of constraints */
1958  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
1959  SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
1960  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
1961  )
1962 {
1963  SCIP_Bool cutoff;
1964  SCIP_Bool separated;
1965  int nchgbds;
1966  int c;
1967 
1968  assert(conshdlr != NULL);
1969  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1970  assert(nconss == 0 || conss != NULL);
1971  assert(result != NULL);
1972 
1973  SCIPdebugMsg(scip, "Enforcing %d linking constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
1974 
1975  cutoff = FALSE;
1976  separated = FALSE;
1977  nchgbds = 0;
1978 
1979  /* check all useful linking constraints for feasibility */
1980  for( c = 0; c < nusefulconss && !cutoff && nchgbds == 0; ++c )
1981  {
1982  SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) );
1983  }
1984 
1985  /* check all obsolete linking constraints for feasibility */
1986  for( c = nusefulconss; c < nconss && !cutoff && !separated && nchgbds == 0; ++c )
1987  {
1988  SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) );
1989  }
1990 
1991  /* return the correct result */
1992  if( cutoff )
1993  *result = SCIP_CUTOFF;
1994  else if( nchgbds > 0 )
1995  *result = SCIP_REDUCEDDOM;
1996  else if( separated )
1997  *result = SCIP_SEPARATED;
1998  else
1999  *result = SCIP_FEASIBLE;
2000 
2001  return SCIP_OKAY;
2002 }
2003 
2004 /*
2005  * Callback methods of constraint handler
2006  */
2007 
2008 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2009 static
2010 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLinking)
2011 { /*lint --e{715}*/
2012  assert(scip != NULL);
2013  assert(conshdlr != NULL);
2014  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2015 
2016  /* call inclusion method of constraint handler */
2018 
2019  *valid = TRUE;
2020 
2021  return SCIP_OKAY;
2022 }
2023 
2024 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
2025 static
2026 SCIP_DECL_CONSFREE(consFreeLinking)
2027 {
2028  SCIP_CONSHDLRDATA* conshdlrdata;
2029 
2030  assert(conshdlr != NULL);
2031  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2032  assert(scip != NULL);
2033 
2034  /* free constraint handler data */
2035  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2036  assert(conshdlrdata != NULL);
2037 
2038  conshdlrdataFree(scip, &conshdlrdata);
2039 
2040  return SCIP_OKAY;
2041 }
2042 
2043 
2044 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
2045 static
2046 SCIP_DECL_CONSINITPRE(consInitpreLinking)
2047 { /*lint --e{715}*/
2048  SCIP_CONSHDLRDATA* conshdlrdata;
2049  SCIP_CONSDATA* consdata;
2050  int c;
2051 
2052  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2053  assert(conshdlrdata != NULL);
2054 
2055  /* disable all linking constraints which contain at most one binary variable */
2056  for( c = 0; c < nconss; ++c )
2057  {
2058  consdata = SCIPconsGetData(conss[c]);
2059  assert(consdata != NULL);
2060 
2061  /* skip constraints which are not added */
2062  if( !SCIPconsIsAdded(conss[c]) )
2063  continue;
2064 
2065  if( consdata->nbinvars <= 1 )
2066  {
2067  SCIP_CALL( SCIPdisableCons(scip, conss[c]) );
2068  assert(consdata->nbinvars == 0 || SCIPvarGetLbGlobal(consdata->binvars[0]) > 0.5);
2069  }
2070  else if( conshdlrdata->linearize )
2071  {
2072  SCIP_CALL( consdataLinearize(scip, conss[c], consdata) );
2073  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2074  }
2075  }
2076 
2077  return SCIP_OKAY;
2078 }
2079 
2080 /** solving process initialization method of constraint handler */
2081 static
2082 SCIP_DECL_CONSINITSOL(consInitsolLinking)
2083 { /*lint --e{715}*/
2084 
2085  /* add nlrow representations to NLP, if NLP had been constructed */
2086  if( SCIPisNLPConstructed(scip) )
2087  {
2088  int c;
2089  for( c = 0; c < nconss; ++c )
2090  {
2091  SCIP_CALL( addNlrow(scip, conss[c]) );
2092  }
2093  }
2094 
2095  return SCIP_OKAY;
2096 }
2097 
2098 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
2099 static
2100 SCIP_DECL_CONSEXITSOL(consExitsolLinking)
2101 { /*lint --e{715}*/
2102  SCIP_CONSDATA* consdata;
2103  int c;
2104 
2105  for( c = 0; c < nconss; ++c )
2106  {
2107  consdata = SCIPconsGetData(conss[c]);
2108  assert(consdata != NULL);
2109 
2110  /* release the rows and nlrows of all constraints */
2111  if( consdata->row1 != NULL )
2112  {
2113  assert(consdata->row2 != NULL);
2114 
2115  SCIP_CALL( SCIPreleaseRow(scip, &consdata->row1) );
2116  SCIP_CALL( SCIPreleaseRow(scip, &consdata->row2) );
2117  }
2118 
2119  if( consdata->nlrow1 != NULL )
2120  {
2121  assert(consdata->nlrow2 != NULL);
2122 
2123  SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow1) );
2124  SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow2) );
2125  }
2126  }
2127 
2128  return SCIP_OKAY;
2129 }
2130 
2131 
2132 /** frees specific constraint data */
2133 static
2134 SCIP_DECL_CONSDELETE(consDeleteLinking)
2135 { /*lint --e{715}*/
2136  SCIP_CONSHDLRDATA* conshdlrdata;
2137 
2138  assert(conshdlr != NULL);
2139  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2140  assert(consdata != NULL);
2141  assert(*consdata != NULL);
2142 
2143  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2144  assert(conshdlrdata != NULL);
2145  assert(conshdlrdata->eventhdlr != NULL);
2146 
2147  /* remove linking constraint form variable hash map */
2148  assert(conshdlrdata->varmap != NULL);
2149  assert(SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey((*consdata)->linkvar)));
2150  SCIP_CALL( SCIPhashmapRemove(conshdlrdata->varmap, getHashmapKey((*consdata)->linkvar)) );
2151 
2152  if( (*consdata)->nbinvars > 0 && SCIPisTransformed(scip) )
2153  {
2154  SCIP_CALL( dropAllEvents(scip, *consdata, conshdlrdata->eventhdlr) );
2155  }
2156 
2157  /* free consdata */
2158  SCIP_CALL( consdataFree(scip, consdata) );
2159 
2160  return SCIP_OKAY;
2161 }
2162 
2163 
2164 /** transforms constraint data into data belonging to the transformed problem */
2165 static
2166 SCIP_DECL_CONSTRANS(consTransLinking)
2167 { /*lint --e{715}*/
2168  SCIP_CONSDATA* sourcedata;
2169  SCIP_CONSDATA* targetdata;
2170  SCIP_CONSHDLRDATA* conshdlrdata;
2171 
2172  assert(conshdlr != NULL);
2173  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2174  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
2175  assert(sourcecons != NULL);
2176  assert(targetcons != NULL);
2177 
2178  /* free constraint handler data */
2179  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2180  assert(conshdlrdata != NULL);
2181  assert(conshdlrdata->eventhdlr != NULL);
2182 
2183  sourcedata = SCIPconsGetData(sourcecons);
2184  assert(sourcedata != NULL);
2185  assert(sourcedata->row1 == NULL); /* in original problem, there cannot be LP rows */
2186  assert(sourcedata->row2 == NULL); /* in original problem, there cannot be LP rows */
2187 
2188  SCIPdebugMsg(scip, "transform linking constraint for variable <%s>\n", SCIPvarGetName(sourcedata->linkvar));
2189 
2190  /* create constraint data for target constraint */
2191  SCIP_CALL( consdataCreate(scip, conshdlrdata->eventhdlr, &targetdata,
2192  sourcedata->linkvar, sourcedata->binvars, sourcedata->vals, sourcedata->nbinvars) );
2193 
2194  /* create target constraint */
2195  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2196  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2197  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2198  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2199  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2200 
2201  /* insert (transformed) linking constraint into the hash map */
2202  assert(conshdlrdata->varmap != NULL);
2203  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varmap, getHashmapKey(targetdata->linkvar), *targetcons) );
2204 
2205  return SCIP_OKAY;
2206 }
2207 
2208 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
2209 static
2210 SCIP_DECL_CONSINITLP(consInitlpLinking)
2211 { /*lint --e{715}*/
2212  SCIP_CONSDATA* consdata;
2213  int c;
2214 
2215  *infeasible = FALSE;
2216 
2217  for( c = 0; c < nconss && !(*infeasible); ++c )
2218  {
2219  assert(SCIPconsIsInitial(conss[c]));
2220 
2221  consdata = SCIPconsGetData(conss[c]);
2222  assert(consdata != NULL);
2223 
2224  if( consdata->nbinvars <= 1 )
2225  continue;
2226 
2227  SCIP_CALL( addCuts(scip, conss[c], infeasible) );
2228  }
2229 
2230  return SCIP_OKAY;
2231 }
2232 
2233 
2234 /** separation method of constraint handler for LP solutions */
2235 static
2236 SCIP_DECL_CONSSEPALP(consSepalpLinking)
2237 { /*lint --e{715}*/
2238  SCIP_Bool cutoff;
2239  SCIP_Bool separated;
2240  int nchgbds;
2241  int c;
2242 
2243  assert(conshdlr != NULL);
2244  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2245  assert(nconss == 0 || conss != NULL);
2246  assert(result != NULL);
2247 
2248  SCIPdebugMsg(scip, "separating %d/%d linking constraints\n", nusefulconss, nconss);
2249 
2250  cutoff = FALSE;
2251  separated = FALSE;
2252  nchgbds = 0;
2253 
2254  /* check all useful linking constraints for feasibility */
2255  for( c = 0; c < nusefulconss && !cutoff; ++c )
2256  {
2257  SCIP_CALL( separateCons(scip, conss[c], NULL, &cutoff, &separated, &nchgbds) );
2258  }
2259 
2260  /* return the correct result */
2261  if( cutoff )
2262  *result = SCIP_CUTOFF;
2263  else if( nchgbds > 0 )
2264  *result = SCIP_REDUCEDDOM;
2265  else if( separated )
2266  *result = SCIP_SEPARATED;
2267  else
2268  *result = SCIP_DIDNOTFIND;
2269 
2270  return SCIP_OKAY;
2271 }
2272 
2273 
2274 /** separation method of constraint handler for arbitrary primal solutions */
2275 static
2276 SCIP_DECL_CONSSEPASOL(consSepasolLinking)
2277 { /*lint --e{715}*/
2278  SCIP_Bool cutoff;
2279  SCIP_Bool separated;
2280  int nchgbds;
2281  int c;
2282 
2283  assert(conshdlr != NULL);
2284  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2285  assert(nconss == 0 || conss != NULL);
2286  assert(result != NULL);
2287 
2288  SCIPdebugMsg(scip, "separating %d/%d " CONSHDLR_NAME " constraints\n", nusefulconss, nconss);
2289 
2290  cutoff = FALSE;
2291  separated = FALSE;
2292  nchgbds = 0;
2293 
2294  /* check all useful set partitioning / packing / covering constraints for feasibility */
2295  for( c = 0; c < nusefulconss && !cutoff; ++c )
2296  {
2297  SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) );
2298  }
2299 
2300  /* return the correct result */
2301  if( cutoff )
2302  *result = SCIP_CUTOFF;
2303  else if( nchgbds > 0 )
2304  *result = SCIP_REDUCEDDOM;
2305  else if( separated )
2306  *result = SCIP_SEPARATED;
2307  else
2308  *result = SCIP_DIDNOTFIND;
2309 
2310  return SCIP_OKAY;
2311 }
2312 
2313 
2314 /** constraint enforcing method of constraint handler for LP solutions */
2315 static
2316 SCIP_DECL_CONSENFOLP(consEnfolpLinking)
2317 { /*lint --e{715}*/
2318  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
2319 
2320  return SCIP_OKAY;
2321 }
2322 
2323 
2324 /** constraint enforcing method of constraint handler for relaxation solutions */
2325 static
2326 SCIP_DECL_CONSENFORELAX(consEnforelaxLinking)
2327 { /*lint --e{715}*/
2328  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
2329 
2330  return SCIP_OKAY;
2331 }
2332 
2333 
2334 /** constraint enforcing method of constraint handler for pseudo solutions */
2335 static
2336 SCIP_DECL_CONSENFOPS(consEnfopsLinking)
2337 { /*lint --e{715}*/
2338  SCIP_Bool cutoff;
2339  SCIP_Bool infeasible;
2340  int nchgbds;
2341  SCIP_Bool solvelp;
2342  int c;
2343 
2344  assert(conshdlr != NULL);
2345  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2346  assert(nconss == 0 || conss != NULL);
2347  assert(result != NULL);
2348 
2349  SCIPdebugMsg(scip, "pseudo enforcing %d " CONSHDLR_NAME " constraints\n", nconss);
2350 
2351  if( objinfeasible )
2352  {
2353  *result = SCIP_DIDNOTRUN;
2354  return SCIP_OKAY;
2355  }
2356 
2357  cutoff = FALSE;
2358  infeasible = FALSE;
2359  nchgbds = 0;
2360  solvelp = FALSE;
2361 
2362  /* check all linking constraint for domain reductions and feasibility */
2363  for( c = 0; c < nconss && !cutoff && !solvelp; ++c )
2364  {
2365  SCIP_CALL( enforcePseudo(scip, conss[c], &cutoff, &infeasible, &nchgbds, &solvelp) );
2366  }
2367 
2368  if( cutoff )
2369  *result = SCIP_CUTOFF;
2370  else if( nchgbds > 0 )
2371  *result = SCIP_REDUCEDDOM;
2372  else if( solvelp )
2373  *result = SCIP_SOLVELP;
2374  else if( infeasible )
2375  *result = SCIP_INFEASIBLE;
2376  else
2377  *result = SCIP_FEASIBLE;
2378 
2379  return SCIP_OKAY;
2380 }
2381 
2382 
2383 /** feasibility check method of constraint handler for integral solutions */
2384 static
2385 SCIP_DECL_CONSCHECK(consCheckLinking)
2386 { /*lint --e{715}*/
2387  SCIP_CONS* cons;
2388  SCIP_CONSDATA* consdata;
2389  int c;
2390 
2391  assert(conshdlr != NULL);
2392  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2393  assert(nconss == 0 || conss != NULL);
2394  assert(result != NULL);
2395 
2396  *result = SCIP_FEASIBLE;
2397 
2398  /* check all linking constraints for feasibility */
2399  for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2400  {
2401  cons = conss[c];
2402  consdata = SCIPconsGetData(cons);
2403  assert(consdata != NULL);
2404 
2405  if( consdata->nbinvars > 1 && (checklprows || consdata->row1 == NULL || !SCIProwIsInLP(consdata->row1)) )
2406  {
2407  if( !checkCons(scip, cons, sol) )
2408  {
2409  /* constraint is violated */
2410  *result = SCIP_INFEASIBLE;
2411 
2412  if( printreason )
2413  {
2414  int pos;
2415  int b;
2416 
2417  pos = -1;
2418 
2419 #ifndef NDEBUG
2420  for( b = 0; b < consdata->nbinvars; ++b )
2421  {
2422  assert(consdata->binvars[b] != NULL);
2423  assert(SCIPvarIsBinary(consdata->binvars[b]));
2424  }
2425 #endif
2426 
2427  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2428  SCIPinfoMessage(scip, NULL, ";\n");
2429 
2430  /* check that at most one binary variable is fixed */
2431  for( b = 0; b < consdata->nbinvars; ++b )
2432  {
2433  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, consdata->binvars[b])) );
2434 
2435  /* check if binary variable is fixed */
2436  if( SCIPgetSolVal(scip, sol, consdata->binvars[b]) > 0.5 )
2437  {
2438  if( pos != -1 )
2439  {
2440  SCIPinfoMessage(scip, NULL, "violation: more than one binary variable is set to one");
2441  break;
2442  }
2443  pos = b ;
2444  }
2445  }
2446 
2447  /* check that at least one binary variable is fixed */
2448  if( pos == -1 )
2449  {
2450  SCIPinfoMessage(scip, NULL, "violation: none of the binary variables is set to one\n");
2451  }
2452  else if( !SCIPisFeasEQ(scip, consdata->vals[pos], SCIPgetSolVal(scip, sol, consdata->linkvar)) )
2453  {
2454  /* check if the fixed binary variable match with the linking variable */
2455  SCIPinfoMessage(scip, NULL, "violation: <%s> = <%g> and <%s> is one\n",
2456  SCIPvarGetName(consdata->linkvar), SCIPgetSolVal(scip, sol, consdata->linkvar),
2457  SCIPvarGetName(consdata->binvars[pos]) );
2458  }
2459  }
2460  }
2461  }
2462  }
2463 
2464  return SCIP_OKAY;
2465 }
2466 
2467 /** domain propagation method of constraint handler */
2468 static
2469 SCIP_DECL_CONSPROP(consPropLinking)
2470 { /*lint --e{715}*/
2471  SCIP_Bool cutoff = FALSE;
2472  int nchgbds = 0;
2473  int c;
2474 
2475  assert(conshdlr != NULL);
2476  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2477  assert(nconss == 0 || conss != NULL);
2478  assert(result != NULL);
2479 
2480  SCIPdebugMsg(scip, "propagating %d/%d " CONSHDLR_NAME " constraints\n", nusefulconss, nconss);
2481 
2482  /* propagate all useful set partitioning / packing / covering constraints */
2483  for( c = 0; c < nusefulconss && !cutoff; ++c )
2484  {
2485  SCIP_Bool addcut;
2486  SCIP_Bool mustcheck;
2487 
2488  SCIP_CALL( processRealBoundChg(scip, conss[c], &cutoff, &nchgbds, &mustcheck) );
2489  SCIP_CALL( processBinvarFixings(scip, conss[c], &cutoff, &nchgbds, &addcut, &mustcheck) );
2490  } /*lint !e438*/
2491 
2492  /* return the correct result */
2493  if( cutoff )
2494  *result = SCIP_CUTOFF;
2495  else if( nchgbds > 0 )
2496  *result = SCIP_REDUCEDDOM;
2497  else
2498  *result = SCIP_DIDNOTFIND;
2499 
2500  return SCIP_OKAY;
2501 }
2502 
2503 
2504 /** presolving method of constraint handler */
2505 static
2506 SCIP_DECL_CONSPRESOL(consPresolLinking)
2507 { /*lint --e{715}*/
2508  SCIP_CONSHDLRDATA* conshdlrdata;
2509  int oldnfixedvars;
2510  int oldnchgbds;
2511  int oldnaggrvars;
2512  int oldndelconss;
2513  int firstchange;
2514  int firstclique;
2515  int lastclique;
2516  int c;
2517  SCIP_Bool fixed;
2518  SCIP_Bool cutoff;
2519  SCIP_Bool infeasible;
2520  SCIP_Bool mustcheck;
2521 
2522  assert(conshdlr != NULL);
2523  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2524  assert(scip != NULL);
2525  assert(result != NULL);
2526 
2527  SCIPdebugMsg(scip, "presolve %d linking constraints\n", nconss);
2528 
2529  (*result) = SCIP_DIDNOTFIND;
2530 
2531  oldnchgbds = *nchgbds;
2532  oldnaggrvars = *naggrvars;
2533  oldnfixedvars = *nfixedvars;
2534  oldndelconss = *ndelconss;
2535  cutoff = FALSE;
2536 
2537  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2538  assert(conshdlrdata != NULL);
2539 
2540  /* process constraints */
2541  firstchange = INT_MAX;
2542  firstclique = INT_MAX;
2543  lastclique = -1;
2544 
2545  /* check for each linking constraint the set partitioning condition */
2546  for( c = 0; c < nconss && !SCIPisStopped(scip); ++c )
2547  {
2548  SCIP_CONS* cons;
2549  SCIP_CONSDATA* consdata;
2550 
2551  assert(*result != SCIP_CUTOFF);
2552 
2553  cons = conss[c];
2554  assert(cons != NULL);
2555  assert(!SCIPconsIsModifiable(cons));
2556 
2557  SCIPdebugMsg(scip, "presolve linking constraints <%s>\n", SCIPconsGetName(cons));
2558 
2559  consdata = SCIPconsGetData(cons);
2560  assert(consdata != NULL);
2561 
2562  if( !SCIPconsIsEnabled(cons) /* || consdata->nbinvars <= 1 */ )
2563  continue;
2564 
2565  /* in case there is only at most one binary variables, the constraints should already be disabled */
2566  assert(consdata->nbinvars > 1);
2567 
2568  /*SCIPdebugMsg(scip, "presolving set partitioning / packing / covering constraint <%s>\n", SCIPconsGetName(cons));*/
2569  if( consdata->nfixedones >= 2 )
2570  {
2571  /* at least two variables are fixed to 1:
2572  * - a linking constraint is infeasible due to the set partitioning condition
2573  */
2574  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2575  *result = SCIP_CUTOFF;
2576  return SCIP_OKAY;
2577  }
2578 
2579  if( consdata->nfixedones == 1 )
2580  {
2581  /* exactly one variable is fixed to 1:
2582  * - all other binary variables must be zero due to the set partitioning condition
2583  * - linking variable has to be fixed to corresponding binary variable which is fixed to one
2584  * - if constraint is not modifiable it can be removed
2585  */
2586  SCIP_VAR* var;
2587  int v;
2588 
2589  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> has a binary variable fixed to 1.0\n", SCIPconsGetName(cons));
2590 
2591  for( v = 0; v < consdata->nbinvars; ++v )
2592  {
2593  var = consdata->binvars[v];
2594  assert(var != NULL);
2595 
2596  if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
2597  {
2598  SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
2599 
2600  if( infeasible )
2601  {
2602  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == 0\n",
2603  SCIPconsGetName(cons), SCIPvarGetName(var));
2604 
2605  *result = SCIP_CUTOFF;
2606  return SCIP_OKAY;
2607  }
2608  assert(fixed);
2609  (*nfixedvars)++;
2610  }
2611  else if( SCIPvarGetLbGlobal(var) > 0.5 )
2612  {
2613  /* fix linking variable */
2614  assert(SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_LOOSE
2615  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_AGGREGATED
2616  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_COLUMN
2617  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_FIXED
2618  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_NEGATED);
2619  SCIP_CALL( SCIPfixVar(scip, consdata->linkvar, consdata->vals[v], &infeasible, &fixed) );
2620 
2621  if( infeasible )
2622  {
2623  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == %g\n",
2624  SCIPconsGetName(cons), SCIPvarGetName(consdata->linkvar), consdata->vals[v]);
2625 
2626  *result = SCIP_CUTOFF;
2627  return SCIP_OKAY;
2628  }
2629 
2630  if( fixed )
2631  (*nfixedvars)++;
2632  }
2633  }
2634 
2635  /* now all other variables are fixed to zero:
2636  * the constraint is feasible, and if it's not modifiable, it is redundant
2637  */
2638  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> is redundant\n", SCIPconsGetName(cons));
2639  SCIP_CALL( SCIPdelCons(scip, cons) );
2640  (*ndelconss)++;
2641  continue;
2642  }
2643 
2644  if( consdata->nfixedzeros == consdata->nbinvars )
2645  {
2646  /* all variables are fixed to zero:
2647  * - a linking constraint is infeasible due the set partitioning condition
2648  */
2649  assert(consdata->nfixedones == 0);
2650 
2651  SCIPdebugMsg(scip, "linking constraint <%s> is infeasible due to set partitioning condition\n", SCIPconsGetName(cons));
2652  *result = SCIP_CUTOFF;
2653  return SCIP_OKAY;
2654  }
2655 
2656  if( consdata->nfixedzeros == consdata->nbinvars - 1 )
2657  {
2658  /* all variables except one are fixed to zero:
2659  * - a linking constraint is feasible due the set partitioning condition
2660  * - the remaining binary variable can be fixed to one
2661  * - linking variable has to be fixed to corresponding binary variable which is fixed to one
2662  * - constraint can be deleted since it is not modifiable
2663  */
2664  SCIP_VAR* var;
2665  int v;
2666 
2667  assert(consdata->nfixedones == 0);
2668 
2669  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> has only one binary variable not fixed to zero\n",
2670  SCIPconsGetName(cons));
2671 
2672  /* search unfixed variable */
2673  /* intentional empty for loop to increment counter to proper position */
2674  /* TODO speed up loop by considering only variables between firstnonfixed and lastnonfixed */
2675  for( v = 0; v < consdata->nbinvars && SCIPvarGetUbGlobal(consdata->binvars[v]) < 0.5; ++v ); /*lint !e722*/
2676  assert(v < consdata->nbinvars);
2677  var = consdata->binvars[v];
2678 
2679  /* fix remaining binary variable */
2680  SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) );
2681  if( infeasible )
2682  {
2683  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == 1\n",
2684  SCIPconsGetName(cons), SCIPvarGetName(var));
2685  *result = SCIP_CUTOFF;
2686  return SCIP_OKAY;
2687  }
2688  assert(fixed);
2689  (*nfixedvars)++;
2690 
2691  /* fix linking variable */
2692  assert(SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_LOOSE
2693  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_AGGREGATED
2694  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_COLUMN
2695  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_FIXED
2696  || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_NEGATED);
2697  SCIP_CALL( SCIPfixVar(scip, consdata->linkvar, consdata->vals[v], &infeasible, &fixed) );
2698 
2699  if( infeasible )
2700  {
2701  SCIPdebugMsg(scip, CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == %g\n",
2702  SCIPconsGetName(cons), SCIPvarGetName(consdata->linkvar), consdata->vals[v]);
2703 
2704  *result = SCIP_CUTOFF;
2705  return SCIP_OKAY;
2706  }
2707  assert(!SCIPvarIsActive(consdata->linkvar) || fixed);
2708  if( fixed )
2709  (*nfixedvars)++;
2710 
2711  /* delete constraint from problem */
2712  SCIP_CALL( SCIPdelCons(scip, cons) );
2713  (*ndelconss)++;
2714  continue;
2715  }
2716 
2717  if( consdata->nfixedzeros == consdata->nbinvars - 2 ) /*lint !e641*/
2718  {
2719  SCIP_VAR* var;
2720  SCIP_VAR* var1;
2721  SCIP_VAR* var2;
2722  SCIP_Bool redundant;
2723  SCIP_Bool aggregated;
2724  int v;
2725 
2726  /* aggregate variable, if set partitioning condition consists only of two
2727  * non-fixed variables
2728  */
2729 
2730  /* search unfixed variable */
2731  var1 = NULL;
2732  var2 = NULL;
2733  for( v = 0; v < consdata->nbinvars && var2 == NULL; ++v )
2734  {
2735  var = consdata->binvars[v];
2736  if( SCIPvarGetUbGlobal(var) > 0.5 )
2737  {
2738  if( var1 == NULL )
2739  var1 = var;
2740  else
2741  var2 = var;
2742  }
2743  }
2744  assert(var1 != NULL && var2 != NULL);
2745 
2746  /* aggregate binary equality var1 + var2 == 1 */
2747  SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: aggregate <%s> + <%s> == 1\n",
2748  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
2749  SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
2750 
2751  /* evaluate aggregation result */
2752  if( infeasible )
2753  {
2754  SCIPdebugMsg(scip, "linking constraint <%s>: infeasible aggregation <%s> + <%s> == 1\n",
2755  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
2756  *result = SCIP_CUTOFF;
2757  return SCIP_OKAY;
2758  }
2759  if( aggregated )
2760  (*naggrvars)++;
2761  }
2762 
2763  /* apply real bound to binary variables */
2764  SCIP_CALL( processRealBoundChg(scip, cons, &cutoff, nchgbds, &mustcheck) );
2765 
2766  /* tightened linking variable */
2767  SCIP_CALL( tightenedLinkvar(scip, cons, consdata, &cutoff, nchgbds) );
2768 
2769  /* remove the trailing and leeading binary variable which are fixed to zero */
2770  SCIP_CALL( removeFixedBinvars(scip, conshdlrdata->eventhdlr, cons) );
2771 
2772  /* fix the linking variable to the only remaining value and the corresponding binary variable to 1.0 */
2773  if( ! cutoff && consdata->nbinvars == 1 )
2774  {
2775  SCIP_VAR* linkvar;
2776  SCIP_VAR* binvar;
2777  SCIP_Real val;
2778 
2779  linkvar = consdata->linkvar;
2780  binvar = consdata->binvars[0];
2781  val = consdata->vals[0];
2782 
2783  SCIPdebugMsg(scip, "linking constraint <%s>: fix <%s> to %16.9g as only one binary variable remains",
2784  SCIPconsGetName(cons), SCIPvarGetName(linkvar), val);
2785 
2786  SCIP_CALL( SCIPfixVar(scip, binvar, 1.0, &infeasible, &fixed) );
2787  assert(fixed);
2788  ++(*nfixedvars);
2789 
2790  if( ! infeasible )
2791  {
2792  SCIP_CALL( SCIPfixVar(scip, linkvar, val, &infeasible, &fixed) );
2793  assert(fixed);
2794  ++(*nfixedvars);
2795  }
2796  cutoff = infeasible;
2797 
2798  SCIP_CALL(SCIPdelCons(scip, cons));
2799  ++(*ndelconss);
2800  }
2801 
2802  if( cutoff )
2803  {
2804  *result = SCIP_CUTOFF;
2805  return SCIP_OKAY;
2806  }
2807 
2808  /* remember the first changed constraint to begin the next redundancy round with */
2809  if( firstchange == INT_MAX )
2810  firstchange = c;
2811 
2812  /* remember the first and last constraints for which we have to add the clique information */
2813  if( !consdata->cliqueadded && consdata->nbinvars >= 2 )
2814  {
2815  if( firstclique == INT_MAX )
2816  firstclique = c;
2817  lastclique = c;
2818  }
2819  }
2820 
2821  /* add clique and implication information */
2822  for( c = firstclique; c < lastclique && !SCIPisStopped(scip); ++c )
2823  {
2824  SCIP_CONS* cons;
2825  SCIP_CONSDATA* consdata;
2826 
2827  assert(*result != SCIP_CUTOFF);
2828 
2829  cons = conss[c];
2830  assert(cons != NULL);
2831 
2832  /* ignore deleted constraints */
2833  if( !SCIPconsIsActive(cons) )
2834  continue;
2835 
2836  consdata = SCIPconsGetData(cons);
2837  assert(consdata != NULL);
2838 
2839  if( !consdata->cliqueadded && consdata->nbinvars >= 3 )
2840  {
2841  /* add set partitioning condition as clique */
2842  int ncliquebdchgs;
2843 
2844  SCIP_CALL( SCIPaddClique(scip, consdata->binvars, NULL, consdata->nbinvars, TRUE, &infeasible, &ncliquebdchgs) );
2845  *nchgbds += ncliquebdchgs;
2846 
2847  if( infeasible )
2848  {
2849  *result = SCIP_CUTOFF;
2850  return SCIP_OKAY;
2851  }
2852 
2853  consdata->cliqueadded = TRUE;
2854  }
2855  }
2856 
2857 #if 0
2858  /* transfer aggregated linking variables to the corresponding binary variables */
2859  assert(conshdlrdata->varmap != NULL);
2860  SCIP_CALL( aggregateVariables(scip, conshdlrdata->varmap, conss, nconss, naggrvars, &cutoff) );
2861 #endif
2862 
2863  if( cutoff )
2864  *result = SCIP_CUTOFF;
2865  else if( oldndelconss < *ndelconss || oldnfixedvars < *nfixedvars || oldnchgbds < *nchgbds || oldnaggrvars < *naggrvars)
2866  *result = SCIP_SUCCESS;
2867 
2868  return SCIP_OKAY; /*lint !e438*/
2869 }
2870 
2871 
2872 /** propagation conflict resolving method of constraint handler */
2873 static
2874 SCIP_DECL_CONSRESPROP(consRespropLinking)
2875 { /*lint --e{715}*/
2876  SCIP_CONSDATA* consdata;
2877  SCIP_VAR* linkvar;
2878  int v;
2879 
2880  SCIPdebugMsg(scip, "conflict resolving method of " CONSHDLR_NAME " constraint handler\n");
2881 
2882  consdata = SCIPconsGetData(cons);
2883  assert(consdata != NULL);
2884 
2885  linkvar = consdata->linkvar;
2886  assert(linkvar != NULL);
2887 
2888  *result = SCIP_DIDNOTFIND;
2889 
2890  if( inferinfo == -1 )
2891  {
2892  /* we have to resolve a fixing of a binary variable which was done due to fixed binary variables */
2893  assert(SCIPvarIsBinary(infervar));
2894  assert(SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)));
2895  assert(SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)));
2896 
2897  if( boundtype == SCIP_BOUNDTYPE_UPPER )
2898  {
2899  /* we fixed the binary variable to zero since one of the other binary variable was fixed to one (set
2900  * partitioning condition)
2901  */
2902  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2903 
2904  for( v = 0; v < consdata->nbinvars; ++v )
2905  {
2906  if( SCIPgetVarLbAtIndex(scip, consdata->binvars[v], bdchgidx, FALSE) > 0.5 )
2907  {
2908  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) );
2909  break;
2910  }
2911  }
2912  assert(v < consdata->nbinvars);
2913  }
2914  else
2915  {
2916  /* we fixed the binary variable to one since all other binary variable were fixed to zero */
2917  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
2918  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
2919 
2920  for( v = 0; v < consdata->nbinvars; ++v )
2921  {
2922  if( consdata->binvars[v] != infervar )
2923  {
2924  /* the reason variable must be assigned to zero */
2925  assert(SCIPgetVarUbAtIndex(scip, consdata->binvars[v], bdchgidx, FALSE) < 0.5);
2926  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) );
2927  }
2928  }
2929  }
2930  }
2931  else if( inferinfo == -2 )
2932  {
2933  /* we have to resolve a fixing of a binary variable which was done due to the linking variable lower bound */
2934  assert(SCIPvarIsBinary(infervar));
2935  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2936  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); /*@repair: neu*/
2937  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) > 0.5); /*@repair: neu*/
2938  assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2939  assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2940 
2941  SCIP_CALL( SCIPaddConflictLb(scip, linkvar, bdchgidx) );
2942  }
2943  else if( inferinfo == -3 )
2944  {
2945  /* we have to resolve a fixing of a binary variable which was done due to the linking variable upper bound */
2946  assert(SCIPvarIsBinary(infervar));
2947  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2948  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2949  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) > 0.5);
2950  assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2951  assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2952 
2953  SCIP_CALL( SCIPaddConflictUb(scip, linkvar, bdchgidx) );
2954  }
2955  else if( inferinfo == -4 )
2956  {
2957  SCIP_VAR** binvars;
2958  SCIP_Real* vals;
2959  SCIP_Real lb;
2960  int nbinvars;
2961  int b;
2962 
2963  /* we tightened the lower bound of the linking variable due the fixing of the corresponding binary variable to zero */
2964  assert(infervar == linkvar);
2965  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
2966 
2967  binvars = consdata->binvars;
2968  nbinvars = consdata->nbinvars;
2969  vals = consdata->vals;
2970 
2971  /* get propagated lower bound */
2972  lb = SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE);
2973 
2974  for( b = 0; b < nbinvars; ++b )
2975  {
2976  if( vals[b] >= lb )
2977  break;
2978 
2979  assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
2980  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
2981  }
2982  }
2983  else if( inferinfo == -5 )
2984  {
2985  SCIP_VAR** binvars;
2986  SCIP_Real* vals;
2987  SCIP_Real ub;
2988  int nbinvars;
2989  int b;
2990 
2991  /* we tightened the upper bound of the linking variable due the fixing of the corresponding binary variable two zero */
2992 
2993  assert(infervar == linkvar);
2994  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
2995 
2996  binvars = consdata->binvars;
2997  nbinvars = consdata->nbinvars;
2998  vals = consdata->vals;
2999 
3000  /* get old and new upper bound */
3001  ub = SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE);
3002 
3003  /* resolve tightening of upper bound of the linking variable by binary variables */
3004  for( b = nbinvars - 1; b >= 0; --b )
3005  {
3006  if( vals[b] <= ub )
3007  break;
3008 
3009  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
3010  }
3011  }
3012  else if( inferinfo == -6 )
3013  {
3014  /* we fixed a binary variable to one since the linking variable was fixed */
3015  assert(SCIPvarIsBinary(infervar));
3016  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3017  assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3018  assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3019  assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3020  assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3021 
3022  assert( !SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE)) );
3023 
3024  SCIP_CALL( SCIPaddConflictLb(scip, linkvar, bdchgidx) );
3025  SCIP_CALL( SCIPaddConflictUb(scip, linkvar, bdchgidx) );
3026  }
3027  else
3028  {
3029  /* we fixed the linking variable to (vals[inferinfo]) since the corresponding binary variable was fixed to one */
3030  assert(infervar == linkvar);
3031  assert(inferinfo >= 0);
3032  assert(inferinfo < consdata->nbinvars);
3033  assert(SCIPisEQ(scip, consdata->vals[inferinfo], SCIPgetVarUbAtIndex(scip, consdata->linkvar, bdchgidx, TRUE))
3034  || SCIPisEQ(scip, consdata->vals[inferinfo], SCIPgetVarLbAtIndex(scip, consdata->linkvar, bdchgidx, TRUE)));
3035 
3036  assert(SCIPgetVarLbAtIndex(scip, consdata->binvars[inferinfo], bdchgidx, FALSE) > 0.5);
3037  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[inferinfo]) );
3038  }
3039 
3040  *result = SCIP_SUCCESS;
3041 
3042  return SCIP_OKAY;
3043 }
3044 
3045 /** variable rounding lock method of constraint handler */
3046 static
3047 SCIP_DECL_CONSLOCK(consLockLinking)
3048 { /*lint --e{715}*/
3049  SCIP_CONSDATA* consdata;
3050  int b;
3051 
3052  assert(locktype == SCIP_LOCKTYPE_MODEL);
3053 
3054  consdata = SCIPconsGetData(cons);
3055  assert(consdata != NULL);
3056 
3057  /* lock linking variable in both directions */
3058  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->linkvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3059 
3060  /* look binary variables in both directions */
3061  for( b = 0; b < consdata->nbinvars; ++b )
3062  {
3063  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvars[b], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3064  }
3065 
3066  return SCIP_OKAY;
3067 }
3068 
3069 /** constraint activation notification method of constraint handler */
3070 static
3071 SCIP_DECL_CONSACTIVE(consActiveLinking)
3072 { /*lint --e{715}*/
3073  assert(cons != NULL);
3074  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3075  assert(SCIPconsIsTransformed(cons));
3076 
3077  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPisNLPConstructed(scip) )
3078  {
3079  SCIP_CALL( addNlrow(scip, cons) );
3080  }
3081 
3082  return SCIP_OKAY;
3083 }
3084 
3085 
3086 /** constraint deactivation notification method of constraint handler */
3087 static
3088 SCIP_DECL_CONSDEACTIVE(consDeactiveLinking)
3089 { /*lint --e{715}*/
3090  SCIP_CONSDATA* consdata;
3091 
3092  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3093  assert(SCIPconsIsTransformed(cons));
3094 
3095  /* get constraint data */
3096  consdata = SCIPconsGetData(cons);
3097  assert(consdata != NULL);
3098 
3099  /* remove row from NLP, if still in solving
3100  * if we are in exitsolve, the whole NLP will be freed anyway
3101  */
3102  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow1 != NULL )
3103  {
3104  assert(consdata->nlrow2 != NULL);
3105  SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow1) );
3106  SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow2) );
3107  }
3108 
3109  return SCIP_OKAY;
3110 }
3111 
3112 /** constraint enabling notification method of constraint handler */
3113 static
3114 SCIP_DECL_CONSENABLE(consEnableLinking)
3115 { /*lint --e{715}*/
3116 #if 0
3117  SCIP_CONSHDLRDATA* conshdlrdata;
3118  SCIP_CONSDATA* consdata;
3119 
3120  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3121  assert(conshdlrdata != NULL);
3122 
3123  consdata = SCIPconsGetData(cons);
3124  assert(consdata != NULL);
3125 
3126  if( consdata->nbinvars <= 1 )
3127  {
3128  SCIP_CALL( SCIPdisableCons(scip, cons) );
3129  assert(consdata->nbinvars == 0 || SCIPvarGetLbGlobal(consdata->binvars[0]) > 0.5);
3130  }
3131  else if( conshdlrdata->linearize )
3132  {
3133  SCIP_CALL( consdataLinearize(scip, cons, consdata) );
3134  SCIP_CALL( SCIPdelCons(scip, cons) );
3135  }
3136 #endif
3137  return SCIP_OKAY;
3138 }
3139 
3140 /** constraint display method of constraint handler */
3141 static
3142 SCIP_DECL_CONSPRINT(consPrintLinking)
3143 { /*lint --e{715}*/
3144  assert(scip != NULL);
3145  assert(conshdlr != NULL);
3146  assert(cons != NULL);
3147 
3148  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
3149 
3150  return SCIP_OKAY;
3151 }
3152 
3153 
3154 /** constraint copying method of constraint handler */
3155 static
3156 SCIP_DECL_CONSCOPY(consCopyLinking)
3157 { /*lint --e{715}*/
3158  SCIP_CONSDATA* sourceconsdata;
3159  SCIP_VAR** binvars;
3160  SCIP_VAR* linkvar;
3161  SCIP_Real* vals;
3162  const char* consname;
3163  int nbinvars;
3164  int v;
3165 
3166  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) != 0 )
3167  {
3168  SCIPerrorMessage("constraint is not a linking constraint\n");
3169  SCIPABORT();
3170  return SCIP_INVALIDDATA; /*lint !e527*/
3171  }
3172 
3173  (*valid) = TRUE;
3174 
3175  sourceconsdata = SCIPconsGetData(sourcecons);
3176  assert(sourceconsdata != NULL);
3177 
3178  /* get number of binary variables, linking variables */
3179  nbinvars = sourceconsdata->nbinvars;
3180  linkvar = sourceconsdata->linkvar;
3181 
3182  /* duplicate variable array */
3183  if( nbinvars > 0 )
3184  {
3185  SCIP_CALL( SCIPduplicateBufferArray(scip, &binvars, sourceconsdata->binvars, nbinvars) );
3186  SCIP_CALL( SCIPduplicateBufferArray(scip, &vals, sourceconsdata->vals, nbinvars) );
3187  }
3188  else
3189  {
3190  binvars = NULL;
3191  vals = NULL;
3192  }
3193 
3194  /* get copy for the binary variables */
3195  for( v = 0; v < nbinvars && *valid; ++v )
3196  {
3197  assert(binvars != NULL); /* for flexelint */
3198  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, binvars[v], &binvars[v], varmap, consmap, global, valid) );
3199  assert(!(*valid) || binvars[v] != NULL);
3200  }
3201 
3202  /* copy the linking variable */
3203  if( *valid )
3204  {
3205  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, linkvar, &linkvar, varmap, consmap, global, valid) );
3206  assert(!(*valid) || linkvar != NULL);
3207  }
3208 
3209  /* only create the target constraint, if all variables could be copied */
3210  if( *valid )
3211  {
3212  if( name != NULL )
3213  consname = name;
3214  else
3215  consname = SCIPconsGetName(sourcecons);
3216 
3217  SCIP_CALL( SCIPcreateConsLinking(scip, cons, consname, linkvar, binvars, vals, nbinvars,
3218  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3219  }
3220 
3221  /* free buffer array */
3222  if( nbinvars > 0 )
3223  {
3224  SCIPfreeBufferArrayNull(scip, &vals);
3225  SCIPfreeBufferArrayNull(scip, &binvars);
3226  }
3227 
3228  return SCIP_OKAY;
3229 }
3230 
3231 /** constraint parsing method of constraint handler */
3232 static
3233 SCIP_DECL_CONSPARSE(consParseLinking)
3234 { /*lint --e{715}*/
3235  SCIP_VAR** binvars;
3236  SCIP_VAR* linkvar;
3237  SCIP_Real* vals;
3238  char* endptr;
3239  int varssize;
3240  int nbinvars;
3241 
3242  assert(scip != NULL);
3243  assert(success != NULL);
3244  assert(str != NULL);
3245  assert(name != NULL);
3246  assert(cons != NULL);
3247 
3248  *success = TRUE;
3249 
3250  /* parse linking variable */
3251  SCIP_CALL( SCIPparseVarName(scip, str, &linkvar, &endptr) );
3252 
3253  if( linkvar == NULL )
3254  {
3255  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "unknown variable name at '%s'\n", str);
3256  *success = FALSE;
3257  return SCIP_OKAY;
3258  }
3259  str = endptr;
3260 
3261  nbinvars = 0;
3262  varssize = 16;
3263 
3264  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, varssize) );
3265  SCIP_CALL( SCIPallocBufferArray(scip, &vals, varssize) );
3266 
3267  while( *str != '=' )
3268  ++str;
3269 
3270  /* skip '=' */
3271  ++str;
3272 
3273  /* skip whitespace */
3274  while( isspace((int)*str) )
3275  ++str;
3276 
3277  /* check for the string "no binary variables yet" */
3278  if( strncmp(str, "no binary variables yet", 24) != 0 )
3279  {
3280  int requsize;
3281  int v;
3282 
3283  /* parse linear sum to get variables and coefficients */
3284  SCIP_CALL( SCIPparseVarsLinearsum(scip, str, binvars, vals, &nbinvars, varssize, &requsize, &endptr, success) );
3285 
3286  if( *success && requsize > varssize )
3287  {
3288  /* realloc buffers and try again */
3289  varssize = requsize;
3290  SCIP_CALL( SCIPreallocBufferArray(scip, &binvars, varssize) );
3291  SCIP_CALL( SCIPreallocBufferArray(scip, &vals, varssize) );
3292 
3293  SCIP_CALL( SCIPparseVarsLinearsum(scip, str, binvars, vals, &nbinvars, varssize, &requsize, &endptr, success) );
3294  assert(!*success || requsize <= varssize); /* if successful, then should have had enough space now */
3295  }
3296 
3297  /* check coefficients */
3298  if( *success )
3299  {
3300  /* convert SCIP_Real to integer */
3301  for( v = 0; v < nbinvars; ++v )
3302  {
3303  if( SCIPisIntegral(scip, vals[v]) )
3304  vals[v] = SCIPconvertRealToInt(scip, vals[v]);
3305  }
3306  }
3307  }
3308 
3309  if( *success )
3310  {
3311  SCIP_CALL( SCIPcreateConsLinking(scip, cons, name, linkvar, binvars, vals, nbinvars,
3312  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3313  }
3314 
3315  SCIPfreeBufferArray(scip, &vals);
3316  SCIPfreeBufferArray(scip, &binvars);
3317 
3318  return SCIP_OKAY;
3319 }
3320 
3321 /** constraint method of constraint handler which returns the variables (if possible) */
3322 static
3323 SCIP_DECL_CONSGETVARS(consGetVarsLinking)
3324 { /*lint --e{715}*/
3325  SCIP_CONSDATA* consdata;
3326 
3327  consdata = SCIPconsGetData(cons);
3328  assert(consdata != NULL);
3329 
3330  if( varssize < consdata->nbinvars + 1)
3331  (*success) = FALSE;
3332  else
3333  {
3334  assert(vars != NULL);
3335 
3336  BMScopyMemoryArray(vars, consdata->binvars, consdata->nbinvars);
3337  vars[consdata->nbinvars] = consdata->linkvar;
3338  (*success) = TRUE;
3339  }
3340 
3341  return SCIP_OKAY;
3342 }
3343 
3344 /** constraint method of constraint handler which returns the number of variables (if possible) */
3345 static
3346 SCIP_DECL_CONSGETNVARS(consGetNVarsLinking)
3347 { /*lint --e{715}*/
3348  SCIP_CONSDATA* consdata;
3349 
3350  consdata = SCIPconsGetData(cons);
3351  assert(consdata != NULL);
3352 
3353  (*nvars) = consdata->nbinvars + 1;
3354  (*success) = TRUE;
3355 
3356  return SCIP_OKAY;
3357 }
3358 
3359 /*
3360  * Callback methods of event handler
3361  */
3362 
3363 /** execution method of event handler */
3364 static
3365 SCIP_DECL_EVENTEXEC(eventExecBinvar)
3366 { /*lint --e{715}*/
3367  SCIP_CONSDATA* consdata;
3368  SCIP_EVENTTYPE eventtype;
3369 
3370  assert(eventhdlr != NULL);
3371  assert(eventdata != NULL);
3372  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3373  assert(event != NULL);
3374 
3375  consdata = (SCIP_CONSDATA*)eventdata;
3376  assert(consdata != NULL);
3377 
3378  eventtype = SCIPeventGetType(event);
3379  switch( eventtype )
3380  {
3382  consdata->nfixedones++;
3383  break;
3385  consdata->nfixedones--;
3386  consdata->firstnonfixed = 0;
3387  consdata->lastnonfixed = consdata->nbinvars - 1;
3388  break;
3390  consdata->nfixedzeros++;
3391  break;
3393  consdata->firstnonfixed = 0;
3394  consdata->lastnonfixed = consdata->nbinvars - 1;
3395  consdata->nfixedzeros--;
3396  break;
3397  default:
3398  SCIPerrorMessage("invalid event type\n");
3399  return SCIP_INVALIDDATA;
3400  }
3401  assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nbinvars);
3402  assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nbinvars);
3403 
3404  /*debugMsg(scip, " -> constraint has %d zero-fixed and %d one-fixed of %d variables\n",
3405  consdata->nfixedzeros, consdata->nfixedones, consdata->nvars);*/
3406 
3407  return SCIP_OKAY;
3408 }
3409 
3410 /*
3411  * constraint specific interface methods
3412  */
3413 
3414 /** creates the handler for linking constraints and includes it in SCIP */
3416  SCIP* scip /**< SCIP data structure */
3417  )
3418 {
3419  SCIP_CONSHDLRDATA* conshdlrdata;
3420  SCIP_CONSHDLR* conshdlr;
3421  SCIP_EVENTHDLR* eventhdlr;
3422 
3423  /* create event handler for bound change events */
3425  eventExecBinvar, NULL) );
3426 
3427  /* create linking constraint handler data */
3428  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
3429 
3430  /* include constraint handler */
3433  consEnfolpLinking, consEnfopsLinking, consCheckLinking, consLockLinking,
3434  conshdlrdata) );
3435 
3436  assert(conshdlr != NULL);
3437 
3438  /* set non-fundamental callbacks via specific setter functions */
3439  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyLinking, consCopyLinking) );
3440  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveLinking) );
3441  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveLinking) );
3442  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteLinking) );
3443  SCIP_CALL( SCIPsetConshdlrEnable(scip, conshdlr, consEnableLinking) );
3444  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolLinking) );
3445  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolLinking) );
3446  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeLinking) );
3447  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsLinking) );
3448  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsLinking) );
3449  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreLinking) );
3450  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpLinking) );
3451  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseLinking) );
3452  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolLinking, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3453  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintLinking) );
3454  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLinking, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3456  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropLinking) );
3457  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLinking, consSepasolLinking, CONSHDLR_SEPAFREQ,
3459  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransLinking) );
3460  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxLinking) );
3461 
3462  /* include the linear constraint to linking constraint upgrade in the linear constraint handler */
3463  /* SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdLinking, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) ); */
3464 
3465  /* add linking constraint handler parameters */
3467  "constraints/" CONSHDLR_NAME "/linearize", "this constraint will not propagate or separate, linear and setppc are used?",
3468  &conshdlrdata->linearize, FALSE, DEFAULT_LINEARIZE, NULL, NULL) );
3469 
3470  return SCIP_OKAY;
3471 }
3472 
3473 /** creates and captures a linking constraint
3474  *
3475  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3476  */
3478  SCIP* scip, /**< SCIP data structure */
3479  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3480  const char* name, /**< name of constraint */
3481  SCIP_VAR* linkvar, /**< linking variable (continuous or integer) which should be linked */
3482  SCIP_VAR** binvars, /**< binary variables */
3483  SCIP_Real* vals, /**< coefficients of the binary variables */
3484  int nbinvars, /**< number of binary starting variables */
3485  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3486  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3487  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3488  * Usually set to TRUE. */
3489  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3490  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3491  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3492  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3493  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3494  * Usually set to TRUE. */
3495  SCIP_Bool local, /**< is constraint only valid locally?
3496  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3497  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3498  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3499  * adds coefficients to this constraint. */
3500  SCIP_Bool dynamic, /**< is constraint subject to aging?
3501  * Usually set to FALSE. Set to TRUE for own cuts which
3502  * are separated as constraints. */
3503  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3504  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3505  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3506  * if it may be moved to a more global node?
3507  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3508  )
3509 {
3510  SCIP_CONSHDLR* conshdlr;
3511  SCIP_CONSDATA* consdata;
3512  SCIP_CONSHDLRDATA* conshdlrdata;
3513  int k;
3514 
3515  assert(scip != NULL);
3516  assert(!SCIPisInfinity(scip, -SCIPvarGetLbGlobal(linkvar)));
3517  assert(!SCIPisInfinity(scip, SCIPvarGetUbGlobal(linkvar)));
3518 
3519  /* find the linking constraint handler */
3520  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3521  if( conshdlr == NULL )
3522  {
3523  SCIPerrorMessage("linking constraint handler not found\n");
3524  return SCIP_PLUGINNOTFOUND;
3525  }
3526 
3527  SCIPdebugMsg(scip, "create linking constraint for variable <%s> with %d binary variables (SCIP stage %d)\n",
3528  SCIPvarGetName(linkvar), nbinvars, SCIPgetStage(scip));
3529  for( k = 0; k < nbinvars; k++ )
3530  {
3531  SCIPdebugMsg(scip, "Var %d : <%s>\n", k, SCIPvarGetName(binvars[k]));
3532  }
3533 
3534  /* get constraint handler data */
3535  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3536  assert(conshdlrdata != NULL);
3537 
3538  if( conshdlrdata->varmap == NULL )
3539  {
3540  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varmap, SCIPblkmem(scip), HASHSIZE_BINVARSCONS) );
3541  }
3542  assert(conshdlrdata->varmap != NULL);
3543 
3544  /* check if the linking for the requests linking variable already exists */
3545  assert(!SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar)));
3546 
3547  /* create the constraint specific data */
3548  SCIP_CALL( consdataCreate(scip, conshdlrdata->eventhdlr, &consdata, linkvar, binvars, vals, nbinvars) );
3549 
3550  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata,
3551  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3552 
3553  /* create binary variables for the real domain */
3554  if( nbinvars == 0 )
3555  {
3556  SCIP_CALL( consdataCreateBinvars(scip, *cons, consdata, conshdlrdata->eventhdlr, conshdlrdata->linearize) );
3557  }
3558 
3559  /* insert linking constraint into the hash map */
3560  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varmap, getHashmapKey(linkvar), *cons) );
3561  assert(SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar)));
3562 
3563  return SCIP_OKAY;
3564 }
3565 
3566 /** creates and captures a linking constraint
3567  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3568  * method SCIPcreateConsLinking(); all flags can be set via SCIPsetCons<Flagname>-methods in scip.h
3569  *
3570  * @see SCIPcreateConsLinking() for information about the basic constraint flag configuration
3571  *
3572  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3573  */
3575  SCIP* scip, /**< SCIP data structure */
3576  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3577  const char* name, /**< name of constraint */
3578  SCIP_VAR* linkvar, /**< linking variable (continuous or integer) which should be linked */
3579  SCIP_VAR** binvars, /**< binary variables, or NULL */
3580  SCIP_Real* vals, /**< coefficients of the binary variables */
3581  int nbinvars /**< number of binary variables */
3582  )
3583 {
3584  assert(scip != NULL);
3585 
3586  SCIP_CALL( SCIPcreateConsLinking(scip, cons, name, linkvar, binvars, vals, nbinvars,
3587  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3588 
3589  return SCIP_OKAY;
3590 }
3591 
3592 /** checks if for the given linking variable (continuous or integer) a linking constraint exists */
3594  SCIP* scip, /**< SCIP data structure */
3595  SCIP_VAR* linkvar /**< linking variable (continuous or integer) which should be linked */
3596  )
3597 {
3598  SCIP_CONSHDLR* conshdlr;
3599  SCIP_CONSHDLRDATA* conshdlrdata;
3600 
3601  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3602  assert(conshdlr != NULL);
3603 
3604  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3605  assert(conshdlrdata != NULL);
3606 
3607  return (conshdlrdata->varmap != NULL) && SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar));
3608 }
3609 
3610 /** returns the linking constraint belonging the given linking variable (continuous or integer) or NULL if it does not exist yet */
3612  SCIP* scip, /**< SCIP data structure */
3613  SCIP_VAR* linkvar /**< linking variable (continuous or integer) which should be linked */
3614  )
3615 {
3616  SCIP_CONSHDLR* conshdlr;
3617  SCIP_CONSHDLRDATA* conshdlrdata;
3618 
3619  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3620  assert(conshdlr != NULL);
3621 
3622  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3623  assert(conshdlrdata != NULL);
3624 
3625  if( conshdlrdata->varmap != NULL )
3626  return (SCIP_CONS*) SCIPhashmapGetImage(conshdlrdata->varmap, getHashmapKey(linkvar));
3627  else
3628  return NULL;
3629 }
3630 
3631 /** returns the linking variable (continuous or integer) of the linking constraint */
3633  SCIP* scip, /**< SCIP data structure */
3634  SCIP_CONS* cons /**< linking constraint */
3635  )
3636 {
3637  SCIP_CONSDATA* consdata;
3638 
3639  assert(scip != NULL);
3640 
3641  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3642  {
3643  SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3644  SCIPABORT();
3645  return NULL; /*lint !e527*/
3646  }
3647 
3648  consdata = SCIPconsGetData(cons);
3649  assert(consdata != NULL);
3650 
3651  return consdata->linkvar;
3652 }
3653 
3654 /** returns the binary variables of the linking constraint */
3656  SCIP* scip, /**< SCIP data structure */
3657  SCIP_CONS* cons, /**< linking constraint */
3658  SCIP_VAR*** binvars, /**< pointer to store the binary variables array pointer */
3659  int* nbinvars /**< pointer to store the number of returned binary variables */
3660  )
3661 {
3662  SCIP_CONSDATA* consdata;
3663 
3664  assert(scip != NULL);
3665 
3666  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3667  {
3668  SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3669  SCIPABORT();
3670  return SCIP_INVALIDDATA; /*lint !e527*/
3671  }
3672 
3673  consdata = SCIPconsGetData(cons);
3674  assert(consdata != NULL);
3675 
3676  if( consdata->binvars == NULL )
3677  {
3678  SCIP_CONSHDLR* conshdlr;
3679  SCIP_CONSHDLRDATA* conshdlrdata;
3680 
3681  conshdlr = SCIPconsGetHdlr(cons);
3682  assert(conshdlr != NULL);
3683 
3684  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3685  assert(conshdlrdata != NULL);
3686 
3687  SCIP_CALL( consdataCreateBinvars(scip, cons, consdata, conshdlrdata->eventhdlr, conshdlrdata->linearize) );
3688  }
3689 
3690  assert(consdata->binvars != NULL);
3691 
3692  if( binvars != NULL )
3693  (*binvars) = consdata->binvars;
3694  if( nbinvars != NULL )
3695  (*nbinvars) = consdata->nbinvars;
3696 
3697  return SCIP_OKAY;
3698 }
3699 
3700 /** returns the number of binary variables of the linking constraint */
3702  SCIP* scip, /**< SCIP data structure */
3703  SCIP_CONS* cons /**< linking constraint */
3704  )
3705 {
3706  SCIP_CONSDATA* consdata;
3707 
3708  assert(scip != NULL);
3709 
3710  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3711  {
3712  SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3713  SCIPABORT();
3714  return -1; /*lint !e527*/
3715  }
3716 
3717  consdata = SCIPconsGetData(cons);
3718  assert(consdata != NULL);
3719 
3720  return consdata->nbinvars;
3721 }
3722 
3723 /** returns the coefficients of the binary variables */
3725  SCIP* scip, /**< SCIP data structure */
3726  SCIP_CONS* cons /**< linking constraint */
3727  )
3728 {
3729  SCIP_CONSDATA* consdata;
3730 
3731  assert(scip != NULL);
3732 
3733  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3734  {
3735  SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3736  SCIPABORT();
3737  return NULL; /*lint !e527*/
3738  }
3739 
3740  consdata = SCIPconsGetData(cons);
3741  assert(consdata != NULL);
3742  consdataSort(consdata);
3743 
3744  return consdata->vals;
3745 }
3746 
3747 /** return all binary variable information of the linking constraint */
3749  SCIP_CONS* cons, /**< linking constraint */
3750  SCIP_VAR*** binvars, /**< pointer to store binary variables, or NULL */
3751  SCIP_Real** vals, /**< pointer to store the binary coefficients, or NULL */
3752  int* nbinvars /**< pointer to store the number of binary variables, or NULL */
3753  )
3754 {
3755  SCIP_CONSDATA* consdata;
3756 
3757  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3758  {
3759  SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3760  SCIPABORT();
3761  return SCIP_ERROR;
3762  }
3763 
3764  consdata = SCIPconsGetData(cons);
3765  assert(consdata != NULL);
3766 
3767  consdataSort(consdata);
3768 
3769  if( binvars != NULL )
3770  *binvars = consdata->binvars;
3771  if( vals != NULL )
3772  *vals = consdata->vals;
3773  if( nbinvars != NULL )
3774  *nbinvars = consdata->nbinvars;
3775 
3776  return SCIP_OKAY;
3777 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1758
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1721
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1413
SCIP_RETCODE SCIPincludeConshdlrLinking(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:137
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition: cons.c:8182
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2125
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define CONSHDLR_DELAYPROP
Definition: cons_linking.c:87
static SCIP_DECL_EVENTEXEC(eventExecBinvar)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSDATA **consdata, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars)
Definition: cons_linking.c:520
static SCIP_DECL_CONSTRANS(consTransLinking)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1989
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_linking.c:221
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
#define CONSHDLR_ENFOPRIORITY
Definition: cons_linking.c:80
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
static SCIP_RETCODE removeFixedBinvars(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:816
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_linking.c:203
#define SCIP_MAXSTRLEN
Definition: def.h:293
public methods for conflict handler plugins and conflict analysis
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1749
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2842
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
#define DEFAULT_LINEARIZE
Definition: cons_linking.c:95
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
static SCIP_DECL_CONSENFORELAX(consEnforelaxLinking)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
static SCIP_DECL_CONSPRINT(consPrintLinking)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:678
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8514
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1436
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:524
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:477
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_EAGERFREQ
Definition: cons_linking.c:84
#define CONSHDLR_NEEDSCONS
Definition: cons_linking.c:88
static SCIP_RETCODE createRows(SCIP *scip, SCIP_CONS *cons)
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11063
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
static SCIP_DECL_CONSSEPASOL(consSepasolLinking)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_linking.c:605
#define CONSHDLR_NAME
Definition: cons_linking.c:73
SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
Definition: var.c:17654
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8394
public methods for problem variables
static SCIP_Bool checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
static SCIP_RETCODE processRealBoundChg(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nchgbds, SCIP_Bool *mustcheck)
Definition: cons_linking.c:770
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define CONSHDLR_PROP_TIMING
Definition: cons_linking.c:90
static SCIP_DECL_CONSDEACTIVE(consDeactiveLinking)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:220
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *linkvar, SCIP_VAR *binvar, SCIP_Bool lblinkvar, SCIP_Bool ublinkvar)
Definition: cons_linking.c:665
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static SCIP_RETCODE dropAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_linking.c:351
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:566
public methods for SCIP variables
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:116
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
int SCIPgetNBinvarsLinking(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff, SCIP_Bool *separated, int *nchgbds)
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1477
static SCIP_DECL_CONSINITLP(consInitlpLinking)
SCIP_RETCODE SCIPaddLinearCoefToNlRow(SCIP *scip, SCIP_NLROW *nlrow, SCIP_VAR *var, SCIP_Real val)
Definition: scip_nlp.c:1107
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:793
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8146
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
SCIP_RETCODE SCIPparseVarsLinearsum(SCIP *scip, const char *str, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int varssize, int *requiredsize, char **endptr, SCIP_Bool *success)
Definition: scip_var.c:700
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
static SCIP_DECL_CONSINITSOL(consInitsolLinking)
SCIP_Bool SCIPexistsConsLinking(SCIP *scip, SCIP_VAR *linkvar)
static void * getHashmapKey(SCIP_VAR *var)
Definition: cons_linking.c:135
public methods for numerical tolerances
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17489
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:69
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPenableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1774
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6918
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12217
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
SCIP_RETCODE SCIPcreateConsBasicLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars)
public methods for managing constraints
static SCIP_DECL_CONSENFOLP(consEnfolpLinking)
static SCIP_DECL_CONSGETVARS(consGetVarsLinking)
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **binvars, int nbinvars)
Definition: cons_linking.c:161
static SCIP_DECL_CONSLOCK(consLockLinking)
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
Definition: nlp.c:1863
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332
#define CONSHDLR_DELAYSEPA
Definition: cons_linking.c:86
#define EVENTHDLR_DESC
Definition: cons_linking.c:77
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:354
static SCIP_DECL_CONSPARSE(consParseLinking)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3473
SCIP_RETCODE SCIPgetBinvarsDataLinking(SCIP_CONS *cons, SCIP_VAR ***binvars, SCIP_Real **vals, int *nbinvars)
public methods for event handler plugins and event handlers
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLinking)
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition: scip_nlp.c:1016
SCIP_RETCODE SCIPcreateConsLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4434
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
Definition: var.c:17666
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
static SCIP_RETCODE aggregateVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9201
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
#define NULL
Definition: lpi_spx1.cpp:155
#define CONSHDLR_PROPFREQ
Definition: cons_linking.c:83
#define REALABS(x)
Definition: def.h:201
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:71
public methods for problem copies
static SCIP_RETCODE tightenedLinkvar(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *nchgbds)
#define SCIP_CALL(x)
Definition: def.h:384
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:68
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata)
Definition: cons_linking.c:378
static SCIP_RETCODE catchEvent(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_linking.c:262
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:276
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8324
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:632
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
SCIP_RETCODE SCIPdisableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1808
static SCIP_RETCODE catchAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_linking.c:325
#define HASHSIZE_BINVARSCONS
Definition: cons_linking.c:94
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
public methods for constraint handler plugins and constraints
static SCIP_DECL_CONSACTIVE(consActiveLinking)
static SCIP_DECL_CONSRESPROP(consRespropLinking)
static SCIP_DECL_CONSDELETE(consDeleteLinking)
static SCIP_DECL_CONSINITPRE(consInitpreLinking)
constraint handler for linking binary variables to a linking (continuous or integer) variable ...
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static SCIP_RETCODE consFixLinkvar(SCIP *scip, SCIP_CONS *cons, int pos, SCIP_Bool *cutoff)
Definition: cons_linking.c:713
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_CONSPRESOL(consPresolLinking)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
static SCIP_DECL_CONSCHECK(consCheckLinking)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
#define EVENTHDLR_NAME
Definition: cons_linking.c:76
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2473
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_DECL_CONSPROP(consPropLinking)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
#define CONSHDLR_DESC
Definition: cons_linking.c:74
public methods for LP management
public methods for cuts and aggregation rows
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
static SCIP_DECL_CONSFREE(consFreeLinking)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
Definition: var.c:17642
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:105
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
Definition: scip_nlp.c:912
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4348
static SCIP_DECL_CONSENFOPS(consEnfopsLinking)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:770
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:70
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPconvertRealToInt(SCIP *scip, SCIP_Real real)
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5498
SCIP_RETCODE SCIPsetConshdlrEnable(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENABLE((*consenable)))
Definition: scip_cons.c:701
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
#define CONSHDLR_CHECKPRIORITY
Definition: cons_linking.c:81
static void consdataSort(SCIP_CONSDATA *consdata)
Definition: cons_linking.c:145
SCIP_RETCODE SCIPdelNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:382
public methods for nonlinear relaxation
SCIP_RETCODE SCIPwriteVarsLinearsum(SCIP *scip, FILE *file, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool type)
Definition: scip_var.c:334
static SCIP_DECL_CONSGETNVARS(consGetNVarsLinking)
methods for sorting joint arrays of various types
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int pos)
Definition: cons_linking.c:970
public methods for managing events
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3379
general public methods
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
public methods for solutions
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
static SCIP_DECL_CONSENABLE(consEnableLinking)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5612
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
static SCIP_DECL_CONSEXITSOL(consExitsolLinking)
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
public methods for message output
static SCIP_RETCODE processBinvarFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nchgbds, SCIP_Bool *addcut, SCIP_Bool *mustcheck)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1995
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8398
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:839
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_linking.c:180
public methods for message handling
#define CONSHDLR_PRESOLTIMING
Definition: cons_linking.c:91
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
SCIP_CONS * SCIPgetConsLinking(SCIP *scip, SCIP_VAR *linkvar)
static SCIP_DECL_CONSSEPALP(consSepalpLinking)
#define CONSHDLR_SEPAFREQ
Definition: cons_linking.c:82
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17393
static SCIP_DECL_CONSCOPY(consCopyLinking)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3096
static SCIP_RETCODE addCuts(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:655
static SCIP_RETCODE enforcePseudo(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *infeasible, int *nchgbds, SCIP_Bool *solvelp)
SCIPallocBlockMemory(scip, subsol))
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:453
#define SCIPABORT()
Definition: def.h:356
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:221
public methods for global and local (sub)problems
#define CONSHDLR_SEPAPRIORITY
Definition: cons_linking.c:79
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5720
#define CONSHDLR_MAXPREROUNDS
Definition: cons_linking.c:85
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
static SCIP_RETCODE dropEvent(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_linking.c:294
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
static SCIP_RETCODE consdataCreateBinvars(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool linearize)
Definition: cons_linking.c:417
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
memory allocation routines