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