# SCIP

Solving Constraint Integer Programs

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