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