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