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