Scippy

SCIP

Solving Constraint Integer Programs

cons_setppc.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_setppc.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
28 * @author Tobias Achterberg
29 * @author Michael Winkler
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/cons_nonlinear.h"
36#include "scip/cons_linear.h"
37#include "scip/cons_setppc.h"
38#include "scip/pub_conflict.h"
39#include "scip/pub_cons.h"
40#include "scip/pub_event.h"
41#include "scip/pub_lp.h"
42#include "scip/pub_message.h"
43#include "scip/pub_misc.h"
44#include "scip/pub_misc_sort.h"
45#include "scip/pub_var.h"
46#include "scip/scip_conflict.h"
47#include "scip/scip_cons.h"
48#include "scip/scip_cut.h"
49#include "scip/scip_event.h"
50#include "scip/scip_general.h"
51#include "scip/scip_lp.h"
52#include "scip/scip_mem.h"
53#include "scip/scip_message.h"
54#include "scip/scip_nlp.h"
55#include "scip/scip_numerics.h"
56#include "scip/scip_param.h"
57#include "scip/scip_prob.h"
58#include "scip/scip_probing.h"
60#include "scip/scip_sol.h"
62#include "scip/scip_var.h"
63#include "scip/symmetry_graph.h"
65#include <string.h>
66
67
68#define CONSHDLR_NAME "setppc"
69#define CONSHDLR_DESC "set partitioning / packing / covering constraints"
70#define CONSHDLR_SEPAPRIORITY +700000 /**< priority of the constraint handler for separation */
71#define CONSHDLR_ENFOPRIORITY -700000 /**< priority of the constraint handler for constraint enforcing */
72#define CONSHDLR_CHECKPRIORITY -700000 /**< priority of the constraint handler for checking feasibility */
73#define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
74#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
75#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
76 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
77#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
78#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
79#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
80#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
81
82#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
83#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
84
85#define LINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
86#define NONLINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of nonlinear constraints */
87
88#define EVENTHDLR_NAME "setppc"
89#define EVENTHDLR_DESC "bound change event handler for set partitioning / packing / covering constraints"
90
91#define CONFLICTHDLR_NAME "setppc"
92#define CONFLICTHDLR_DESC "conflict handler creating set covering constraints"
93#define CONFLICTHDLR_PRIORITY LINCONSUPGD_PRIORITY
94
95#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
96
97#define HASHSIZE_SETPPCCONS 500 /**< minimal size of hash table in setppc constraint tables */
98#define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
99#define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
100#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
101
102#define DEFAULT_RANDSEED 3
103
104/*#define VARUSES*/ /* activate variable usage counting, that is necessary for LP and pseudo branching */
105/*#define BRANCHLP*/ /* BRANCHLP is only useful if the ENFOPRIORITY is set to a positive value */
106#ifdef BRANCHLP
107#define MINBRANCHWEIGHT 0.3 /**< minimum weight of both sets in binary set branching */
108#define MAXBRANCHWEIGHT 0.7 /**< maximum weight of both sets in binary set branching */
109#endif
110#define DEFAULT_NPSEUDOBRANCHES 2 /**< number of children created in pseudo branching (0: disable branching) */
111#define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving steps be performed? */
112
113#define DEFAULT_CLIQUELIFTING FALSE /**< should we try to lift variables into other clique constraints, fix
114 * variables, aggregate them, and also shrink the amount of variables in
115 * clique constraints
116 */
117#define DEFAULT_ADDVARIABLESASCLIQUES FALSE/**< should we try to generate extra clique constraint out of all binary
118 * variables to hopefully fasten the detection of redundant clique
119 * constraints */
120#define DEFAULT_CLIQUESHRINKING TRUE /**< should we try to shrink the number of variables in a clique constraints, by
121 * replacing more than one variable by only one
122 */
123
124/* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
125
126/*
127 * Data structures
128 */
129
130/** constraint handler data */
131struct SCIP_ConshdlrData
132{
133 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
134 SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
135#ifdef VARUSES
136 SCIP_INTARRAY* varuses; /**< number of times a var is used in the active setppc constraints */
137#endif
138 SCIP_Longint nsetpart; /**< number of set partitioning constraints in transformed problem */
139 int npseudobranches; /**< number of children created in pseudo branching (0 to disable branching) */
140 int noldfixedvars; /**< number of fixed variables after last clique lifting run */
141 int noldimpls; /**< number of implication before last clique lifting run */
142 int noldcliques; /**< number of cliques before last clique lifting run */
143 int noldupgrs; /**< number of setppc constraints since the last clique lifting run */
144 int nclqpresolve; /**< number of setppc clique lifting runs */
145 SCIP_Bool updatedsetppctype; /**< remember whether we upgraded a constraint type */
146 SCIP_Bool cliquelifting; /**< should we perform the clique lifting procedure */
147 SCIP_Bool enablecliquelifting;/**< check whether we have enough changes to run the lifting procedure again */
148 SCIP_Bool cliqueshrinking; /**< should we try to shrink the number of variables in a clique
149 * constraints, by replacing more than one variable by only one
150 */
151 SCIP_Bool addvariablesascliques;/**< should we try to generate extra clique constraint out of all binary
152 * variables to hopefully fasten the detection of redundant clique
153 * constraints */
154 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
155 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
156 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
157 SCIP_Bool dualpresolving; /**< should dual presolving steps be performed? */
158};
159
160/** constraint data for set partitioning / packing / covering constraints */
161struct SCIP_ConsData
162{
163 uint64_t signature; /**< bit signature of vars array */
164 SCIP_ROW* row; /**< LP row, if constraint is already stored in LP row format */
165 SCIP_NLROW* nlrow; /**< NLP row, if constraint has been added to NLP relaxation */
166 SCIP_VAR** vars; /**< variables of the constraint */
167 int varssize; /**< size of vars array */
168 int nvars; /**< number of variables in the constraint */
169 int nfixedzeros; /**< current number of variables fixed to zero in the constraint */
170 int nfixedones; /**< current number of variables fixed to one in the constraint */
171 unsigned int setppctype:2; /**< type of constraint: set partitioning, packing or covering */
172 unsigned int sorted:1; /**< are the constraint's variables sorted? */
173 unsigned int cliqueadded:1; /**< was the set partitioning / packing constraint already added as clique? */
174 unsigned int validsignature:1; /**< is the bit signature valid? */
175 unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
176 unsigned int varsdeleted:1; /**< were variables deleted after last cleanup? */
177 unsigned int merged:1; /**< are the constraint's equal/negated variables already merged? */
178 unsigned int presolpropagated:1; /**< was the constraint already propagated in presolving w.r.t. the current domains? */
179 unsigned int existmultaggr:1; /**< does this constraint contain aggregations */
180 unsigned int catchevents:1; /**< are events installed for this constraint? */
181};
182
183
184
185
186/*
187 * Local methods
188 */
189
190/** compares two active constraints of type set partitioning or set packing such that a "-1" is return if
191 * 1. the first constraint is a set partitioning constraint and the second is a set packing or
192 * 2. both constraints are set partitioning constraints and the second has more! variables than the first or
193 * 3. both constraints are set packing constraints and the second has less! variables than the first
194 * a "0" is return if
195 * 1. both constraint are of the same type and have the amount of variables or
196 * and a "1" is returned otherwise
197 */
198static
200 SCIP_CONS*const cons1, /**< first problem variable */
201 SCIP_CONS*const cons2 /**< second problem variable */
202 )
203{
204 SCIP_CONSDATA* consdata1;
205 SCIP_CONSDATA* consdata2;
206
207 assert(cons1 != NULL);
208 assert(cons2 != NULL);
209 assert(SCIPconsIsActive(cons1));
210 assert(SCIPconsIsActive(cons2));
211
212 /* the partitioning type should be the smallest value and the packing the second smallest */
214
215 consdata1 = SCIPconsGetData(cons1);
216 assert(consdata1 != NULL);
217 assert(consdata1->setppctype != SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
218 consdata2 = SCIPconsGetData(cons2);
219 assert(consdata2 != NULL);
220 assert(consdata2->setppctype != SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
221
222 if( consdata1->setppctype < consdata2->setppctype ||
223 (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) || /*lint !e641*/
224 (consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars) ) /*lint !e641*/
225 return -1;
226 else if( (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars) ) /*lint !e641*/
227 return 0;
228 else
229 {
230 assert(consdata1->setppctype > consdata2->setppctype || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars > consdata2->nvars) || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars < consdata2->nvars)); /*lint !e641*/
231 return +1;
232 }
233}
234
235/** sort constraints first after type (partitioning before packing before covering) and second after number of
236 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
237 * have decreasing number of variables */
238static
239SCIP_DECL_SORTPTRCOMP(setppcConssSort)
240{
241 return setppcCompare((SCIP_CONS*)elem1, (SCIP_CONS*)elem2);
242}
243
244/** compares two setppc constraints such that a "-1" is return if the first constraint is active and
245 * 1. the second constraint is deleted
246 * 2. the first constraint is a set partitioning constraint and the second is a set packing or
247 * 3. both constraints are set partitioning constraints and the second has more! variables than the first or
248 * 4. both constraints are set packing constraints and the second has less! variables than the first
249 * a "0" is return if
250 * 1. both constraint are set-covering constraints
251 * 2. both constraint are of the same type and have the amount of variables or
252 * and a "1" is returned otherwise
253 */
254static
256 SCIP_CONS*const cons1, /**< first problem variable */
257 SCIP_CONS*const cons2 /**< second problem variable */
258 )
259{
260 SCIP_CONSDATA* consdata1;
261 SCIP_CONSDATA* consdata2;
262
263 assert(cons1 != NULL);
264 assert(cons2 != NULL);
265
266 if( SCIPconsIsDeleted(cons1) )
267 {
268 if( SCIPconsIsDeleted(cons2) )
269 return 0;
270 else
271 return +1;
272 }
273 else if( SCIPconsIsDeleted(cons2) )
274 return -1;
275
276 consdata1 = SCIPconsGetData(cons1);
277 assert(consdata1 != NULL);
278 consdata2 = SCIPconsGetData(cons2);
279 assert(consdata2 != NULL);
280
281 /* the partitioning type should be the smallest value and the packing the second smallest */
283
284 if( consdata1->setppctype < consdata2->setppctype ||
285 ((SCIP_SETPPCTYPE)consdata1->setppctype != SCIP_SETPPCTYPE_COVERING &&
286 (((SCIP_SETPPCTYPE)consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) ||
287 ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars))) )
288 return -1;
289 else if( ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_COVERING || (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars)) )
290 return 0;
291 else
292 {
293 assert(consdata1->setppctype > consdata2->setppctype || ((consdata1->setppctype == consdata2->setppctype) &&
294 ((consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars > consdata2->nvars)
295 || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars < consdata2->nvars)))); /*lint !e641*/
296 return +1;
297 }
298}
299
300/** sort constraints first after type (partitioning before packing before covering) and second after number of
301 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
302 * have decreasing number of variables */
303static
304SCIP_DECL_SORTPTRCOMP(setppcConssSort2)
305{
306 return setppcCompare2((SCIP_CONS*)elem1, (SCIP_CONS*)elem2);
307}
308
309
310/** installs rounding locks for the given variable in the given setppc constraint */
311static
313 SCIP* scip, /**< SCIP data structure */
314 SCIP_CONS* cons, /**< setppc constraint */
315 SCIP_VAR* var /**< variable of constraint entry */
316 )
317{
318 SCIP_CONSDATA* consdata;
319
320 consdata = SCIPconsGetData(cons);
321 assert(consdata != NULL);
322
323 switch( consdata->setppctype )
324 {
326 SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
327 break;
329 SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) );
330 break;
332 SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, FALSE) );
333 break;
334 default:
335 SCIPerrorMessage("unknown setppc type\n");
336 return SCIP_INVALIDDATA;
337 }
338
339 return SCIP_OKAY;
340}
341
342/** removes rounding locks for the given variable in the given setppc constraint */
343static
345 SCIP* scip, /**< SCIP data structure */
346 SCIP_CONS* cons, /**< setppc constraint */
347 SCIP_VAR* var /**< variable of constraint entry */
348 )
349{
350 SCIP_CONSDATA* consdata;
351
352 consdata = SCIPconsGetData(cons);
353 assert(consdata != NULL);
354
355 switch( consdata->setppctype )
356 {
358 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
359 break;
361 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, FALSE, TRUE) );
362 break;
364 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, FALSE) );
365 break;
366 default:
367 SCIPerrorMessage("unknown setppc type\n");
368 return SCIP_INVALIDDATA;
369 }
370
371 return SCIP_OKAY;
372}
373
374/** creates constraint handler data for set partitioning / packing / covering constraint handler */
375static
377 SCIP* scip, /**< SCIP data structure */
378 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
379 SCIP_EVENTHDLR* eventhdlr /**< event handler */
380 )
381{
382 assert(scip != NULL);
383 assert(conshdlrdata != NULL);
384 assert(eventhdlr != NULL);
385
386 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
387#ifdef VARUSES
388 SCIP_CALL( SCIPcreateIntarray(scip, &(*conshdlrdata)->varuses) );
389#endif
390 (*conshdlrdata)->npseudobranches = DEFAULT_NPSEUDOBRANCHES;
391
392 /* set event handler for bound change events */
393 (*conshdlrdata)->eventhdlr = eventhdlr;
394 (*conshdlrdata)->nsetpart = 0;
395
396 /* create a random number generator */
397 SCIP_CALL( SCIPcreateRandom(scip, &(*conshdlrdata)->randnumgen,
399
400 return SCIP_OKAY;
401}
402
403/** frees constraint handler data for set partitioning / packing / covering constraint handler */
404static
406 SCIP* scip, /**< SCIP data structure */
407 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
408 )
409{
410 assert(conshdlrdata != NULL);
411 assert(*conshdlrdata != NULL);
412
413#ifdef VARUSES
414 SCIP_CALL( SCIPfreeIntarray(scip, &(*conshdlrdata)->varuses) );
415#endif
416
417 /* free random number generator */
418 SCIPfreeRandom(scip, &(*conshdlrdata)->randnumgen);
419
420 SCIPfreeBlockMemory(scip, conshdlrdata);
421
422 return SCIP_OKAY;
423}
424
425#ifdef VARUSES
426/** adds the given value to the usage counter of the given variable */
427static
428SCIP_RETCODE conshdlrdataAddVaruses(
429 SCIP* scip, /**< SCIP data structure */
430 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
431 SCIP_VAR* var, /**< variable to increase usage counter for */
432 int addval /**< value to add to the usage counter */
433 )
434{
435 SCIP_INTARRAY* varuses;
436
437 assert(conshdlrdata != NULL);
438 assert(var != NULL);
439
440 varuses = conshdlrdata->varuses;
441 assert(varuses != NULL);
442
443 /* if the variable is the negation of a problem variable, count the varuses in the problem variable */
444 if( SCIPvarIsNegated(var) )
445 {
446 SCIP_VAR* negvar;
447 int varindex;
448
449 /* move the varuses value of the negated variable to the active problem variable */
450 varindex = SCIPvarGetIndex(var);
451 addval += SCIPgetIntarrayVal(scip, varuses, varindex);
452 SCIP_CALL( SCIPsetIntarrayVal(scip, varuses, varindex, 0) );
453 SCIP_CALL( SCIPgetNegatedVar(scip, var, &negvar) );
454 var = negvar;
455 }
456
457 /* increase varuses counter */
458 SCIP_CALL( SCIPincIntarrayVal(scip, varuses, SCIPvarGetIndex(var), addval) );
459
460 SCIPdebugMsg(scip, "added %d to varuses of <%s>: %d\n",
461 addval, SCIPvarGetName(var), SCIPgetIntarrayVal(scip, varuses, SCIPvarGetIndex(var)));
462
463 return SCIP_OKAY;
464}
465
466/** increases the usage counter of the given variable */
467static
468SCIP_RETCODE conshdlrdataIncVaruses(
469 SCIP* scip, /**< SCIP data structure */
470 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
471 SCIP_VAR* var /**< variable to increase usage counter for */
472 )
473{
474 assert(conshdlrdata != NULL);
475
476 SCIPdebugMsg(scip, "increasing varuses of <%s>: %d\n",
477 SCIPvarGetName(var), SCIPgetIntarrayVal(scip, conshdlrdata->varuses, SCIPvarGetIndex(var)));
478
479 SCIP_CALL( conshdlrdataAddVaruses(scip, conshdlrdata, var, +1) );
480
481 return SCIP_OKAY;
482}
483
484/** decreases the usage counter of the given variable */
485static
486SCIP_RETCODE conshdlrdataDecVaruses(
487 SCIP* scip, /**< SCIP data structure */
488 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
489 SCIP_VAR* var /**< variable to increase usage counter for */
490 )
491{
492 assert(conshdlrdata != NULL);
493
494 SCIPdebugMsg(scip, "decreasing varuses of <%s>: %d\n",
495 SCIPvarGetName(var), SCIPgetIntarrayVal(scip, conshdlrdata->varuses, SCIPvarGetIndex(var)));
496
497 SCIP_CALL( conshdlrdataAddVaruses(scip, conshdlrdata, var, -1) );
498
499 return SCIP_OKAY;
500}
501
502/** increases the usage counter of all variable in the constraint */
503static
504SCIP_RETCODE consdataIncVaruses(
505 SCIP* scip, /**< SCIP data structure */
506 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
507 SCIP_CONSDATA* consdata /**< setppc constraint data */
508 )
509{
510 int v;
511
512 assert(consdata != NULL);
513
514 for( v = 0; v < consdata->nvars; ++v )
515 {
516 SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, consdata->vars[v]) );
517 }
518
519 return SCIP_OKAY;
520}
521
522/** decreases the usage counter of all variable in the constraint */
523static
524SCIP_RETCODE consdataDecVaruses(
525 SCIP* scip, /**< SCIP data structure */
526 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
527 SCIP_CONSDATA* consdata /**< setppc constraint data */
528 )
529{
530 int v;
531
532 assert(consdata != NULL);
533
534 for( v = 0; v < consdata->nvars; ++v )
535 {
536 SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, consdata->vars[v]) );
537 }
538
539 return SCIP_OKAY;
540}
541#endif
542
543/** ensures, that the vars array can store at least num entries */
544static
546 SCIP* scip, /**< SCIP data structure */
547 SCIP_CONSDATA* consdata, /**< setppc constraint data */
548 int num /**< minimum number of entries to store */
549 )
550{
551 assert(consdata != NULL);
552 assert(consdata->nvars <= consdata->varssize);
553
554 if( num > consdata->varssize )
555 {
556 int newsize;
557
558 newsize = SCIPcalcMemGrowSize(scip, num);
559 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
560 consdata->varssize = newsize;
561 }
562 assert(num <= consdata->varssize);
563
564 return SCIP_OKAY;
565}
566
567/** creates a set partitioning / packing / covering constraint data object */
568static
570 SCIP* scip, /**< SCIP data structure */
571 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
572 int nvars, /**< number of variables in the constraint */
573 SCIP_VAR** vars, /**< variables of the constraint */
574 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
575 )
576{
577 assert(consdata != NULL);
578 assert(nvars == 0 || vars != NULL);
579
580 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
581
582 (*consdata)->signature = 0;
583 (*consdata)->row = NULL;
584 (*consdata)->nlrow = NULL;
585 (*consdata)->existmultaggr = FALSE;
586 (*consdata)->catchevents = FALSE;
587 (*consdata)->nfixedzeros = 0;
588 (*consdata)->nfixedones = 0;
589
590 if( nvars > 0 )
591 {
592 int v;
593
594 /* @todo the setppc constraint handler does not remove fixed variables from its var array; removing those
595 * variables is only possible if we consider the values of nfixedones and nfixedzeros in all propagation methods
596 */
597#ifdef SCIP_DISABLED_CODE
598
600 {
601 SCIP_VAR** varsbuffer;
602 int k;
603
604 /* allocate temporary buffer storage for active variables */
605 SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
606
607 k = 0;
608 /* collect fixed variables to compress the required memory */
609 for( v = 0; v < nvars; ++v )
610 {
611 assert(SCIPvarIsBinary(vars[v]));
612
613 /* already fixed variables account as fixed ones or zero, only unfixed are appended */
614 if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
615 (*consdata)->nfixedones++;
616 else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
617 (*consdata)->nfixedzeros++;
618 else
619 varsbuffer[k++] = vars[v];
620 }
621
622 (*consdata)->varssize = k;
623 (*consdata)->nvars = k;
624 /* copy unfixed variables into constraint data */
625 if( k > 0 )
626 {
627 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
628 }
629
630 /* free temporary storage */
631 SCIPfreeBufferArray(scip, &varsbuffer);
632 }
633 else
634#endif
635 {
636 /* for uncompressed copies, simply duplicate the whole array */
637 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
638 (*consdata)->varssize = nvars;
639 (*consdata)->nvars = nvars;
640 }
641
643 {
644 /* get transformed variables */
645 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
646
647 /* check for multi-aggregations and capture variables */
648 for( v = 0; v < (*consdata)->nvars; v++ )
649 {
650 SCIP_VAR* var = SCIPvarGetProbvar((*consdata)->vars[v]);
651 assert(var != NULL);
652 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
653 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
654 }
655 }
656 else
657 {
658 /* capture variables */
659 for( v = 0; v < (*consdata)->nvars; v++ )
660 {
661 assert((*consdata)->vars[v] != NULL);
662 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
663 }
664 }
665 }
666 else
667 {
668 (*consdata)->vars = NULL;
669 (*consdata)->varssize = 0;
670 (*consdata)->nvars = 0;
671 }
672 (*consdata)->setppctype = setppctype; /*lint !e641*/
673 (*consdata)->sorted = (nvars <= 1);
674 (*consdata)->cliqueadded = FALSE;
675 (*consdata)->validsignature = FALSE;
676 (*consdata)->changed = TRUE;
677 (*consdata)->varsdeleted = FALSE;
678 (*consdata)->merged = FALSE;
679 (*consdata)->presolpropagated = FALSE;
680
681 return SCIP_OKAY;
682}
683
684/** creates a transformed set partitioning / packing / covering constraint data object */
685static
687 SCIP* scip, /**< SCIP data structure */
688 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
689 int nvars, /**< number of variables in the constraint */
690 SCIP_VAR** vars, /**< variables of the constraint */
691 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
692 )
693{
694 assert(consdata != NULL);
695 assert(nvars == 0 || vars != NULL);
696
697 /* create constraint data */
698 SCIP_CALL( consdataCreate(scip, consdata, nvars, vars, setppctype) );
699
700 /* transform the variables */
701 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
702
703 return SCIP_OKAY;
704}
705
706/** frees a set partitioning / packing / covering constraint data */
707static
709 SCIP* scip, /**< SCIP data structure */
710 SCIP_CONSDATA** consdata /**< pointer to store the set partitioning / packing / covering constraint */
711 )
712{
713 int v;
714
715 assert(consdata != NULL);
716 assert(*consdata != NULL);
717
718 /* release the row */
719 if( (*consdata)->row != NULL )
720 {
721 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
722 }
723
724 /* release the nlrow */
725 if( (*consdata)->nlrow != NULL )
726 {
727 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
728 }
729
730 /* release variables */
731 for( v = 0; v < (*consdata)->nvars; v++ )
732 {
733 assert((*consdata)->vars[v] != NULL);
734 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
735 }
736
737 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
738 SCIPfreeBlockMemory(scip, consdata);
739
740 return SCIP_OKAY;
741}
742
743/** prints set partitioning / packing / covering constraint to file stream */
744static
746 SCIP* scip, /**< SCIP data structure */
747 SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint data */
748 FILE* file /**< output file (or NULL for standard output) */
749 )
750{
751 assert(consdata != NULL);
752
753 /* print coefficients */
754 if( consdata->nvars == 0 )
755 SCIPinfoMessage(scip, file, "0 ");
756
757 /* write linear sum */
758 SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, NULL, consdata->nvars, TRUE) );
759
760 /* print right hand side */
761 switch( consdata->setppctype )
762 {
764 SCIPinfoMessage(scip, file, " == 1");
765 break;
767 SCIPinfoMessage(scip, file, " <= 1");
768 break;
770 SCIPinfoMessage(scip, file, " >= 1");
771 break;
772 default:
773 SCIPerrorMessage("unknown setppc type\n");
774 return SCIP_ERROR;
775 }
776
777 return SCIP_OKAY;
778}
779
780/** returns the bit signature of the given constraint data */
781static
783 SCIP_CONSDATA* consdata /**< set partitioning / packing / covering constraint data */
784 )
785{
786 assert(consdata != NULL);
787
788 if( !consdata->validsignature )
789 {
790 int i;
791
792 consdata->signature = 0;
793 for( i = 0; i < consdata->nvars; ++i )
794 consdata->signature |= SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[i]));
795 consdata->validsignature = TRUE;
796 }
797
798 return consdata->signature;
799}
800
801/** sorts setppc constraint's variables by non-decreasing variable index */
802static
804 SCIP_CONSDATA* consdata /**< linear constraint data */
805 )
806{
807 assert(consdata != NULL);
808
809 if( !consdata->sorted )
810 {
811 if( consdata->nvars <= 1 )
812 consdata->sorted = TRUE;
813 else
814 {
815 SCIPsortPtr((void**)consdata->vars, SCIPvarComp, consdata->nvars);
816 consdata->sorted = TRUE;
817 }
818 }
819 assert(consdata->sorted);
820#ifdef SCIP_DEBUG
821 /* check sorting */
822 {
823 int v;
824
825 for( v = 0; v < consdata->nvars; ++v )
826 {
827 assert(v == consdata->nvars-1 || SCIPvarCompare(consdata->vars[v], consdata->vars[v+1]) <= 0);
828 }
829 }
830#endif
831}
832
833/** changes the type of a setppc constraint */
834static
836 SCIP* scip, /**< SCIP data structure */
837 SCIP_CONS* cons, /**< setppc constraint */
838 SCIP_SETPPCTYPE setppctype /**< new type of constraint */
839 )
840{
841 SCIP_CONSHDLR* conshdlr;
842 SCIP_CONSHDLRDATA* conshdlrdata;
843 SCIP_CONSDATA* consdata;
844 SCIP_Bool locked;
845 int i;
846
847 consdata = SCIPconsGetData(cons);
848 assert(consdata != NULL);
849
850 if( (SCIP_SETPPCTYPE)consdata->setppctype == setppctype )
851 return SCIP_OKAY;
852
853 SCIPdebugMsg(scip, " -> converting <%s> into setppc type %d\n", SCIPconsGetName(cons), setppctype);
854
855 /* remove rounding locks */
856 locked = FALSE;
857 for( i = 0; i < NLOCKTYPES && !locked; i++ )
858 locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
859
860 if( locked )
861 {
862 for( i = 0; i < consdata->nvars; ++i )
863 {
864 SCIP_CALL( unlockRounding(scip, cons, consdata->vars[i]) );
865 }
866 }
867
868 conshdlr = SCIPconsGetHdlr(cons);
869 assert(conshdlr != NULL);
870 conshdlrdata = SCIPconshdlrGetData(conshdlr);
871 assert(conshdlrdata != NULL);
872
874 {
875 if( setppctype == SCIP_SETPPCTYPE_PARTITIONING )
876 {
877 ++(conshdlrdata->nsetpart);
878 assert(conshdlrdata->nsetpart >= 0);
879 }
880 else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
881 {
882 --(conshdlrdata->nsetpart);
883 assert(conshdlrdata->nsetpart >= 0);
884 }
885 }
886
887 /* change the constraint type */
888 consdata->setppctype = setppctype; /*lint !e641*/
889
890 /* reinstall rounding locks again */
891 if( locked )
892 {
893 for( i = 0; i < consdata->nvars; ++i )
894 {
895 SCIP_CALL( lockRounding(scip, cons, consdata->vars[i]) );
896 }
897 }
898
899 /* remember that we changed a constraint type for clique lifting procedure */
900 if( setppctype != SCIP_SETPPCTYPE_COVERING )
901 conshdlrdata->updatedsetppctype = TRUE;
902
903 return SCIP_OKAY;
904}
905
906/** catches events for variable at given position */
907static
909 SCIP* scip, /**< SCIP data structure */
910 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
911 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
912 int pos /**< array position of variable to catch bound change events for */
913 )
914{
915 SCIP_CONSDATA* consdata;
916 SCIP_EVENTTYPE eventtype;
917 SCIP_VAR* var;
918
919 consdata = SCIPconsGetData(cons);
920 assert(consdata != NULL);
921 assert(eventhdlr != NULL);
922 assert(0 <= pos && pos < consdata->nvars);
923 assert(consdata->vars != NULL);
924
925 var = consdata->vars[pos];
926 assert(var != NULL);
927
928 /* we are catching the following events:
929 *
930 * - SCIP_EVENTTYPE_BOUNDCHANGED: Is used to count the number of variable fixed locally to zero and one. That helps
931 * to speed up the propagation
932 *
933 * - SCIP_EVENTTYPE_VARDELETED: Is caught to remove a deleted variable from the constraint
934 *
935 * - SCIP_EVENTTYPE_VARFIXED: Is used to get informed if a variable of the constraint was aggregated which means was
936 * detected to be equal or a negated variable of on other variable. in case of a negation
937 * this could lead to a redundant constraint if the (other) active variable is also part
938 * of the constraint.
939 */
941
942 /* catch bound change events on variable */
943 SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) );
944
945 /* update the fixed variables counters for this variable */
946 if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
947 {
948 consdata->nfixedzeros++;
949
950 /* during presolving, we may fix the last unfixed variable or do an aggregation if there are two unfixed variables */
951 if( SCIPconsIsActive(cons) && ((SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE) && (consdata->nfixedzeros >= consdata->nvars - 2)) )
952 {
953 consdata->presolpropagated = FALSE;
954
955 /* during solving, we only propagate again if there is only one unfixed variable left */
956 if( consdata->nfixedzeros >= consdata->nvars - 1 )
957 {
959 }
960 }
961 }
962 else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
963 {
964 consdata->nfixedones++;
965
966 if( SCIPconsIsActive(cons) )
967 {
968 consdata->presolpropagated = FALSE;
970 }
971 }
972
973 return SCIP_OKAY;
974}
975
976/** drops events for variable at given position */
977static
979 SCIP* scip, /**< SCIP data structure */
980 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
981 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
982 int pos /**< array position of variable to catch bound change events for */
983 )
984{
985 SCIP_CONSDATA* consdata;
986 SCIP_EVENTTYPE eventtype;
987 SCIP_VAR* var;
988
989 consdata = SCIPconsGetData(cons);
990 assert(consdata != NULL);
991 assert(eventhdlr != NULL);
992 assert(0 <= pos && pos < consdata->nvars);
993 assert(consdata->vars != NULL);
994
995 var = consdata->vars[pos];
996 assert(var != NULL);
997
999
1000 /* drop events on variable */
1001 SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );
1002
1003 /* update the fixed variables counters for this variable */
1004 if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
1005 consdata->nfixedzeros--;
1006 else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
1007 consdata->nfixedones--;
1008
1009 return SCIP_OKAY;
1010}
1011
1012/** catches bound change events for all variables in transformed setppc constraint */
1013static
1015 SCIP* scip, /**< SCIP data structure */
1016 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1017 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1018 )
1019{
1020 SCIP_CONSDATA* consdata;
1021 int i;
1022
1023 consdata = SCIPconsGetData(cons);
1024 assert(consdata != NULL);
1025
1026 if( consdata->catchevents == TRUE )
1027 return SCIP_OKAY;
1028
1029 /* catch event for every single variable */
1030 for( i = 0; i < consdata->nvars; ++i )
1031 {
1032 SCIP_CALL( catchEvent(scip, cons, eventhdlr, i) );
1033 }
1034
1035 consdata->catchevents = TRUE;
1036
1037 return SCIP_OKAY;
1038}
1039
1040/** drops bound change events for all variables in transformed setppc constraint */
1041static
1043 SCIP* scip, /**< SCIP data structure */
1044 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1045 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1046 )
1047{
1048 SCIP_CONSDATA* consdata;
1049 int i;
1050
1051 consdata = SCIPconsGetData(cons);
1052 assert(consdata != NULL);
1053
1054 if( consdata->catchevents == FALSE )
1055 return SCIP_OKAY;
1056
1057 /* drop event of every single variable */
1058 for( i = 0; i < consdata->nvars; ++i )
1059 {
1060 SCIP_CALL( dropEvent(scip, cons, eventhdlr, i) );
1061 }
1062
1063 consdata->catchevents = FALSE;
1064
1065 return SCIP_OKAY;
1066}
1067
1068/** adds coefficient in setppc constraint */
1069static
1071 SCIP* scip, /**< SCIP data structure */
1072 SCIP_CONS* cons, /**< setppc constraint */
1073 SCIP_VAR* var /**< variable to add to the constraint */
1074 )
1075{
1076 SCIP_CONSDATA* consdata;
1077 SCIP_Bool transformed;
1078
1079 assert(var != NULL);
1080
1081 consdata = SCIPconsGetData(cons);
1082 assert(consdata != NULL);
1083
1084 /* are we in the transformed problem? */
1085 transformed = SCIPconsIsTransformed(cons);
1086
1087 /* always use transformed variables in transformed constraints */
1088 if( transformed )
1089 {
1090 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
1091 }
1092 assert(var != NULL);
1093 assert(transformed == SCIPvarIsTransformed(var));
1094
1095 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
1096 consdata->vars[consdata->nvars] = var;
1097 consdata->nvars++;
1098 if( consdata->validsignature )
1099 consdata->signature |= SCIPhashSignature64(SCIPvarGetIndex(var));
1100 consdata->sorted = (consdata->nvars == 1);
1101 consdata->changed = TRUE;
1102
1103 /* capture the variable */
1104 SCIP_CALL( SCIPcaptureVar(scip, var) );
1105
1106 /* if we are in transformed problem, catch the variable's events */
1107 if( transformed )
1108 {
1109 SCIP_CONSHDLR* conshdlr;
1110 SCIP_CONSHDLRDATA* conshdlrdata;
1111
1112 /* get event handler */
1113 conshdlr = SCIPconsGetHdlr(cons);
1114 assert(conshdlr != NULL);
1115 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1116 assert(conshdlrdata != NULL);
1117 assert(conshdlrdata->eventhdlr != NULL);
1118
1119 /* catch bound change events of variable */
1120 if( consdata->catchevents )
1121 {
1122 SCIP_CALL( catchEvent(scip, cons, conshdlrdata->eventhdlr, consdata->nvars-1) );
1123 }
1124
1125 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
1126 consdata->existmultaggr = TRUE;
1127
1128#ifdef VARUSES
1129 /* if the constraint is currently active, increase the variable usage counter */
1130 if( SCIPconsIsActive(cons) )
1131 {
1132 SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var) );
1133 }
1134#endif
1135 }
1136
1137 /* install the rounding locks for the new variable */
1138 SCIP_CALL( lockRounding(scip, cons, var) );
1139
1140 /* add the new coefficient to the LP row */
1141 if( consdata->row != NULL )
1142 {
1143 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, 1.0) );
1144 }
1145
1146 consdata->merged = FALSE;
1147 consdata->cliqueadded = FALSE;
1148
1149 return SCIP_OKAY;
1150}
1151
1152/** deletes coefficient at given position from setppc constraint data */
1153static
1155 SCIP* scip, /**< SCIP data structure */
1156 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1157 int pos /**< position of coefficient to delete */
1158 )
1159{
1160 SCIP_CONSDATA* consdata;
1161 SCIP_VAR* var;
1162
1163 assert(scip != NULL);
1164 assert(cons != NULL);
1165
1166 consdata = SCIPconsGetData(cons);
1167 assert(consdata != NULL);
1168 assert(0 <= pos && pos < consdata->nvars);
1169
1170 var = consdata->vars[pos];
1171 assert(var != NULL);
1172 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
1173
1174 /* remove the rounding locks for the deleted variable */
1175 SCIP_CALL( unlockRounding(scip, cons, var) );
1176
1177 /* if we are in transformed problem, delete the event data of the variable */
1178 if( SCIPconsIsTransformed(cons) )
1179 {
1180 SCIP_CONSHDLR* conshdlr;
1181 SCIP_CONSHDLRDATA* conshdlrdata;
1182
1183 /* get event handler */
1184 conshdlr = SCIPconsGetHdlr(cons);
1185 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1186 assert(conshdlrdata != NULL);
1187 assert(conshdlrdata->eventhdlr != NULL);
1188
1189 /* drop bound change events of variable */
1190 if( consdata->catchevents )
1191 {
1192 SCIP_CALL( dropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
1193 }
1194
1195 /* the last variable of the constraint was deleted; mark it for propagation (so that it can be deleted) */
1196 if( consdata->nvars == 1 )
1197 {
1198 consdata->presolpropagated = FALSE;
1199 }
1200 }
1201
1202 /* delete coefficient from the LP row */
1203 if( consdata->row != NULL )
1204 {
1205 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, -1.0) );
1206 }
1207
1208 /* move the last variable to the free slot */
1209 if( pos != consdata->nvars - 1 )
1210 {
1211 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
1212 consdata->sorted = FALSE;
1213 }
1214 consdata->nvars--;
1215 consdata->validsignature = FALSE;
1216 consdata->changed = TRUE;
1217
1218 /* release variable */
1219 SCIP_CALL( SCIPreleaseVar(scip, &var) );
1220
1221 return SCIP_OKAY;
1222}
1223
1224/** preform dual presolving
1225 *
1226 * In case a part (more than one variable) in the setppc constraint is independent of everything else (is locked only by
1227 * this constraint), we can perform dual reductions:
1228 *
1229 * (1) set covering
1230 *
1231 * - fix all independent variables with negative object coefficient to one
1232 * - fix all remaining independent variables to zero
1233 *
1234 * (i) all variables are independent and the constraint is not modifiable
1235 *
1236 * - fix the variable with the smallest object coefficient to one
1237 *
1238 * (ii) a variable x has exactly 0 uplocks and arbitrary downlocks and a variable y has exactly 1 downlock and
1239 * arbitrary uplocks and obj(x) <= obj(y) and obj(y) >= 0
1240 *
1241 * - fix y to 0, because it is dominated by x
1242 *
1243 * (2) set partitioning
1244 *
1245 * (i) all variables are independent and the constraint is not modifiable
1246 *
1247 * - fix the variable with the smallest object coefficient to one
1248 * - fix all remaining independent variables to zero
1249 *
1250 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 1 downlock and
1251 * arbitrary uplocks and obj(x) <= obj(y)
1252 *
1253 * - fix y to 0, because it is dominated by x
1254 *
1255 * (3) set packing
1256 *
1257 * (i) all variables are independent and the constraint is not modifiable
1258 *
1259 * - fix the variable with the smallest object coefficient to one if the object coefficient is negative or zero
1260 * - fix all remaining independent variables to zero
1261 *
1262 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 0 downlocks and
1263 * arbitrary uplocks and obj(x) <= obj(y)
1264 *
1265 * - fix y to 0, because it is dominated by x
1266 *
1267 *
1268 * Note: the following dual reduction for set covering and set packing constraints is already performed by the presolver
1269 * "dualfix"
1270 * (1) in case of a set covering constraint the following dual reduction can be performed:
1271 * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
1272 * objective coefficient than it can be fixed to one
1273 * (2) in case of a set packing constraint the following dual reduction can be performed:
1274 * - if a variable in a set packing constraint is only locked by that constraint and has positive or zero
1275 * objective coefficient than it can be fixed to zero
1276 *
1277 * Note: all dual reduction (ii) could also be performed by the "domcol" presolver, but because the pairwise comparison of
1278 * columns is only done heuristically (and here it should be even cheaper) we perform them here (too).
1279 *
1280 * Moreover, if there exists a variable that is only locked by a covering or packing constraint with two variables, one
1281 * can aggregate variables.
1282 */
1283static
1285 SCIP* scip, /**< SCIP data structure */
1286 SCIP_CONS* cons, /**< setppc constraint */
1287 int* nfixedvars, /**< pointer to count number of fixings */
1288 int* ndelconss, /**< pointer to count number of deleted constraints */
1289 int* naggrvars, /**< pointer to count number of variables aggregated */
1290 SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
1291 )
1292{
1293 SCIP_CONSDATA* consdata;
1294 SCIP_SETPPCTYPE setppctype;
1295 SCIP_VAR** vars;
1296 SCIP_VAR* activevar;
1297 SCIP_VAR* var;
1298 SCIP_Real bestobjval;
1299 SCIP_Real objval;
1300 SCIP_Real objsign;
1301 SCIP_Real fixval;
1302 SCIP_Bool infeasible;
1303 SCIP_Bool fixed;
1304 SCIP_Bool negated;
1305 int noldfixed;
1306 int nposfixings;
1307 int nlockdowns;
1308 int nlockups;
1309 int nvars;
1310 int indepidx = -1;
1311 int idx;
1312 int v;
1313
1314 assert(scip != NULL);
1315 assert(cons != NULL);
1316 assert(nfixedvars != NULL);
1317 assert(ndelconss != NULL);
1318 assert(result != NULL);
1319
1320 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
1321 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
1322 * added to the problems have the check flag set to FALSE
1323 */
1324 if( !SCIPconsIsChecked(cons) )
1325 return SCIP_OKAY;
1326
1327 assert(SCIPconsIsActive(cons));
1328
1329 consdata = SCIPconsGetData(cons);
1330 assert(consdata != NULL);
1331
1332 /* modifiable non-covering constraints cannot be deleted if one variable is fixed to one, because the propagation for
1333 * newly inserted variables must be considered later
1334 */
1335 if( consdata->nfixedones == 1 && SCIPconsIsModifiable(cons) )
1336 return SCIP_OKAY;
1337
1338 /* all fixed variables should be removed at that point */
1339 assert(consdata->nfixedones == 0);
1340 assert(consdata->nfixedzeros == 0);
1341
1342 nvars = consdata->nvars;
1343
1344 /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
1345 * constraint)
1346 */
1347 if( nvars < 2 )
1348 return SCIP_OKAY;
1349
1350 setppctype = (SCIP_SETPPCTYPE)consdata->setppctype;
1351 vars = consdata->vars;
1352 idx = -1;
1353 bestobjval = SCIP_INVALID;
1354
1355 /* collect the rounding locks depending on the setppc type */
1356 switch( setppctype )
1357 {
1359 nlockdowns = 1;
1360 nlockups = 1;
1361 objsign = 0.0;
1362 break;
1364 nlockdowns = 0;
1365 nlockups = 1;
1366 objsign = -1.0;
1367 break;
1369 nlockdowns = 1;
1370 nlockups = 0;
1371 objsign = 1.0;
1372 break;
1373 default:
1374 SCIPerrorMessage("unknown setppc type\n");
1375 SCIPABORT();
1376 return SCIP_INVALIDDATA; /*lint !e527*/
1377 }
1378
1379 nposfixings = 0;
1380
1381 /* check if we can apply the dual reduction; therefore count the number of variables where the setppc has the only
1382 * locks on this constraint
1383 */
1384 for( v = 0; v < nvars; ++v )
1385 {
1386 var = vars[v];
1387 assert(var != NULL);
1388
1389 /* the variable should not be (globally) fixed */
1390 assert(SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5);
1391
1392 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) >= nlockdowns
1393 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == nlockups )
1394 {
1395 activevar = var;
1396 negated = FALSE;
1397
1398 /* get the active variable */
1399 SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
1400 assert(SCIPvarIsActive(activevar));
1401
1402 if( negated )
1403 objval = -SCIPvarGetObj(activevar);
1404 else
1405 objval = SCIPvarGetObj(activevar);
1406
1407 /* check if the current variable has a smaller objective coefficient */
1408 if( idx == -1 || objval < bestobjval )
1409 {
1410 idx = v;
1411 bestobjval = objval;
1412 }
1413
1414 /* determine independent variable, i.e., only locked by the current constraint */
1415 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns )
1416 {
1417 assert(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == nlockups);
1418
1419 /* store variables that have the right objective sign */
1420 if ( objval * objsign >= 0.0 )
1421 indepidx = v;
1422 }
1423 }
1424
1425 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1426 * variables
1427 */
1428 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
1429 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
1430 ++nposfixings;
1431 }
1432
1433 if( idx == -1 || nposfixings == 0 )
1434 return SCIP_OKAY;
1435
1436 SCIPdebugMsg(scip, "dual fixing constraint: \n");
1439
1440 assert(idx >= 0 && idx < nvars);
1441 assert(bestobjval < SCIPinfinity(scip));
1442
1443 noldfixed = *nfixedvars;
1444
1445 /* In the special case of two variables, where one variable is independent and will be minimized for covering or
1446 * maximized for packing or does not appear in the objective, we can aggregate variables:
1447 * - Covering: var1 + var2 >= 1 and the objective of var1 is non-negative.
1448 * - Packing: var1 + var2 <= 1 and the objective of var1 is non-positive.
1449 * In both cases, var1 + var2 = 1 holds in every optimal solution.
1450 */
1451 if( setppctype != SCIP_SETPPCTYPE_PARTITIONING && nvars == 2 && indepidx >= 0 )
1452 {
1453 SCIP_Bool redundant;
1454 SCIP_Bool aggregated;
1455 int idx2;
1456
1457 idx2 = 1 - indepidx;
1458 assert( 0 <= idx2 && idx2 < 2 );
1459
1460 SCIP_CALL( SCIPaggregateVars(scip, vars[indepidx], vars[idx2], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
1461 assert(!infeasible);
1462 assert(redundant);
1463 assert(aggregated);
1464 ++(*naggrvars);
1465
1466 /* remove constraint since it is redundant */
1467 SCIP_CALL( SCIPdelCons(scip, cons) );
1468 ++(*ndelconss);
1469
1470 *result = SCIP_SUCCESS;
1471
1472 return SCIP_OKAY;
1473 }
1474
1475 /* in case of set packing and set partitioning we fix the dominated variables to zero */
1476 if( setppctype != SCIP_SETPPCTYPE_COVERING )
1477 {
1478 /* first part of all variables */
1479 for( v = nvars - 1; v >= 0; --v )
1480 {
1481 if( v == idx )
1482 continue;
1483
1484 var = vars[v];
1485 assert(var != NULL);
1486
1487 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1488 * variables
1489 */
1490 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
1491 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
1492 {
1493 activevar = var;
1494 negated = FALSE;
1495
1496 /* get the active variable */
1497 SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
1498 assert(SCIPvarIsActive(activevar));
1499
1500 if( negated )
1501 objval = -SCIPvarGetObj(activevar);
1502 else
1503 objval = SCIPvarGetObj(activevar);
1504
1505 if( objval >= bestobjval )
1506 {
1507 SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
1508 assert(!infeasible);
1509 assert(fixed);
1510
1511 SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == 0.0\n", SCIPvarGetName(var));
1512 ++(*nfixedvars);
1513 }
1514 }
1515 }
1516 }
1517 /* if we got a set covering constraint and not all variables are locked from this constraint it might not get
1518 * redundant (which is case if it is not possible to fix at least one variable to one), we fix all redundant
1519 * variables to their best bound
1520 */
1521 else
1522 {
1523 /* first part of all variables */
1524 for( v = nvars - 1; v >= 0; --v )
1525 {
1526 if( v == idx )
1527 continue;
1528
1529 var = vars[v];
1530 assert(var != NULL);
1531
1532 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1533 * variables
1534 */
1535 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
1536 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
1537 {
1538 activevar = var;
1539 negated = FALSE;
1540
1541 /* get the active variable */
1542 SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
1543 assert(SCIPvarIsActive(activevar));
1544 assert(negated
1547 assert(!negated
1550
1551 if( negated )
1552 objval = -SCIPvarGetObj(activevar);
1553 else
1554 objval = SCIPvarGetObj(activevar);
1555
1556 if( objval > 0.0 )
1557 fixval = 0.0;
1558 else
1559 fixval = 1.0;
1560
1561 /* if variables has a negative objective contribution, and is uplocked by another constraint we cannot fix
1562 * the variables to 1
1563 */
1564 if( (fixval == 1.0 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > nlockups) || objval < bestobjval )
1565 continue;
1566
1567 SCIP_CALL( SCIPfixVar(scip, var, fixval, &infeasible, &fixed) );
1568 assert(!infeasible);
1569 assert(fixed);
1570
1571 SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == %g\n", SCIPvarGetName(var), fixval);
1572 ++(*nfixedvars);
1573 }
1574 }
1575 }
1576
1577 /* if all variables but the domination variable is fixed and the constraint is not modifiable or the constraint is a
1578 * covering constraint and the bestobjval is less than or equal to zero, we can fix the domination variable (with best
1579 * objective coefficient) and the constraint gets redundant
1580 */
1581 if( ((*nfixedvars - noldfixed == nvars - 1) && !SCIPconsIsModifiable(cons)) || (setppctype == SCIP_SETPPCTYPE_COVERING && bestobjval <= 0.0) )
1582 {
1583 /* in case of a set packing constraint with positive objective values, all variables can be fixed to zero; in all
1584 * other cases the variable with the smallest objective values is fixed to one
1585 */
1586 if( (setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0
1588 || setppctype != SCIP_SETPPCTYPE_PACKING || bestobjval <= 0.0 )
1589 {
1590 if( setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0 )
1591 fixval = 0.0;
1592 else
1593 fixval = 1.0;
1594
1595 SCIP_CALL( SCIPfixVar(scip, vars[idx], fixval, &infeasible, &fixed) );
1596 assert(!infeasible);
1597 assert(fixed);
1598
1599 SCIPdebugMsg(scip, " -> dual-fixed best variable <%s> == %g\n", SCIPvarGetName(vars[idx]), fixval);
1600 ++(*nfixedvars);
1601 }
1602
1603 /* check that we really have a non-violated constraint in hand before deleting */
1604 assert((setppctype == SCIP_SETPPCTYPE_PACKING && consdata->nfixedones <= 1) ||
1605 (setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedones == 1) ||
1606 (setppctype == SCIP_SETPPCTYPE_COVERING && consdata->nfixedones >= 1));
1607
1608 /* remove constraint since it is redundant */
1609 SCIP_CALL( SCIPdelCons(scip, cons) );
1610 ++(*ndelconss);
1611 }
1612
1613 assert(*nfixedvars >= noldfixed);
1614
1615 /* set result pointer to SCIP_SUCCESS, if variables could be fixed */
1616 if( *nfixedvars != noldfixed )
1617 *result = SCIP_SUCCESS;
1618
1619 return SCIP_OKAY;
1620}
1621
1622/** find pairs of negated variables in constraint:
1623 * partitioning/packing: all other variables must be zero, constraint is redundant
1624 * covering: constraint is redundant
1625 *
1626 * find sets of equal variables in constraint:
1627 * partitioning/packing: variable must be zero
1628 * covering: multiple entries of variable can be replaced by single entry
1629 */
1630static
1632 SCIP* scip, /**< SCIP data structure */
1633 SCIP_CONS* cons, /**< knapsack constraint */
1634 int* nfixedvars, /**< pointer to store number of fixed variables */
1635 int* ndelconss, /**< pointer to store number of deleted constraints */
1636 int* nchgcoefs, /**< pointer to store number of changed coefficients */
1637 SCIP_Bool* cutoff /**< pointer to store whether a fixing leads to a cutoff */
1638 )
1639{
1640 SCIP_CONSDATA* consdata;
1641 int v;
1642
1643 assert(scip != NULL);
1644 assert(cons != NULL);
1645 assert(nfixedvars != NULL);
1646 assert(ndelconss != NULL);
1647 assert(nchgcoefs != NULL);
1648 assert(cutoff != NULL);
1649
1650 consdata = SCIPconsGetData(cons);
1651 assert(consdata != NULL);
1652
1653 if( consdata->merged || SCIPconsIsDeleted(cons) )
1654 return SCIP_OKAY;
1655
1656 if( consdata->nvars <= 1 )
1657 {
1658 consdata->merged = TRUE;
1659 return SCIP_OKAY;
1660 }
1661
1662 assert(consdata->vars != NULL || consdata->nvars == 0);
1663
1664 /* sorting array after indices of variables, that's only for faster merging */
1665 SCIPsortPtr((void**)consdata->vars, SCIPvarCompActiveAndNegated, consdata->nvars);
1666 /* setppc sorting now lost */
1667 consdata->sorted = FALSE;
1668
1669 /* loop backwards through the items: deletion only affects rear items */
1670 for( v = consdata->nvars - 1; v > 0; --v )
1671 {
1672 SCIP_VAR* var1;
1673 SCIP_VAR* var2;
1674 SCIP_Bool negated1;
1675 SCIP_Bool negated2;
1676
1677 negated1 = FALSE;
1678 negated2 = FALSE;
1679
1680 var1 = consdata->vars[v];
1681 assert(SCIPvarIsBinary(var1));
1684 {
1685 var1 = SCIPvarGetNegatedVar(var1);
1686 negated1 = TRUE;
1687 }
1688 assert(var1 != NULL);
1689
1690 var2 = consdata->vars[v-1];
1691 assert(SCIPvarIsBinary(var2));
1694 {
1695 var2 = SCIPvarGetNegatedVar(var2);
1696 negated2 = TRUE;
1697 }
1698 assert(var2 != NULL);
1699
1700 if( var1 == var2 )
1701 {
1702 SCIP_Bool infeasible;
1703 SCIP_Bool fixed;
1704
1705 /* one variables is active and the other is the same negated variable */
1706 if( negated1 != negated2 )
1707 {
1708 /* all other variable have to be zero if it's a partitioning or packing constraint */
1709 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
1710 {
1711 int i;
1712
1713 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
1714 || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
1715
1716 for( i = consdata->nvars - 1; i >= 0; --i )
1717 if( i != v && i != (v-1) )
1718 {
1719 SCIP_CALL( SCIPfixVar(scip, consdata->vars[i], 0.0, &infeasible, &fixed) );
1720 if( infeasible )
1721 {
1722 SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
1723 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[i]));
1724 *cutoff = TRUE;
1725 return SCIP_OKAY;
1726 }
1727
1728 if( fixed )
1729 ++(*nfixedvars);
1730 }
1731 }
1732 /* all setppc-type constraints are redundant */
1733 SCIP_CALL( SCIPdelCons(scip, cons) );
1734 ++(*ndelconss);
1735 return SCIP_OKAY;
1736 }
1737 /* both variables are either active or negated */
1738 else
1739 {
1740 /* this variable can be fixed to zero if it's a partitioning or packing constraint */
1741 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
1742 {
1743 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
1744 || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
1745
1746 SCIP_CALL( SCIPfixVar(scip, var1, negated1 ? 1.0 : 0.0, &infeasible, &fixed) );
1747 if( infeasible )
1748 {
1749 SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == %g\n",
1750 SCIPconsGetName(cons), SCIPvarGetName(var1), negated1 ? 1.0 : 0.0);
1751 *cutoff = TRUE;
1752 return SCIP_OKAY;
1753 }
1754
1755 if( fixed )
1756 ++(*nfixedvars);
1757 }
1758 /* multiple entries of variable can be replaced by single entry */
1759 else
1760 {
1761 SCIP_CALL( delCoefPos(scip, cons, v) ); /* only some changed behind position v-1, so it's okay */
1762 ++(*nchgcoefs);
1763 }
1764 }
1765 consdata->changed = TRUE;
1766 }
1767 }
1768 consdata->merged = TRUE;
1769
1770 return SCIP_OKAY;
1771}
1772
1773/** deletes all zero-fixed variables and replace aggregated variables */
1774static
1776 SCIP* scip, /**< SCIP data structure */
1777 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1778 int* naddconss, /**< pointer to count number of added constraints, or NULL indicating we
1779 * can not resolve multi-aggregations
1780 */
1781 int* ndelconss, /**< pointer to count number of deleted constraints, or NULL indicating we
1782 * can not resolve multi-aggregations
1783 */
1784 int* nfixedvars, /**< pointer to store number of fixed variables, or NULL indicating we can
1785 * not resolve multi-aggregations
1786 */
1787 SCIP_Bool* cutoff /**< pointer to store whether a fixing leads to a cutoff, or NULL
1788 * indicating we can not resolve multi-aggregations
1789 */
1790 )
1791{
1792 SCIP_CONSDATA* consdata;
1793 int v;
1794
1795 assert(scip != NULL);
1796 assert(cons != NULL);
1797
1798 consdata = SCIPconsGetData(cons);
1799 assert(consdata != NULL);
1800
1801 /* all multi-aggregations should be resolved */
1802 consdata->existmultaggr = FALSE;
1803
1804 v = 0;
1805 while( v < consdata->nvars )
1806 {
1807 SCIP_VAR* var;
1808
1809 var = consdata->vars[v];
1810 assert(SCIPvarIsBinary(var));
1811
1812 if( SCIPvarGetUbGlobal(var) < 0.5 )
1813 {
1814 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
1815 SCIP_CALL( delCoefPos(scip, cons, v) );
1816 }
1817 else
1818 {
1819 SCIP_VAR* repvar;
1820 SCIP_Bool negated;
1821
1822 /* get binary representative of variable */
1823 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
1824
1825 /* resolve multi-aggregation */
1827 {
1828 SCIP_VAR** consvars;
1829 SCIP_Real* consvals;
1830 SCIP_Real constant = 0.0;
1831 SCIP_Bool easycase;
1832 int nconsvars;
1833 int requiredsize;
1834 int v2;
1835
1836 nconsvars = 1;
1837 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 1) );
1838 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 1) );
1839 consvars[0] = repvar;
1840 consvals[0] = 1.0;
1841
1842 /* get active variables for new constraint */
1843 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
1844 /* if space was not enough we need to resize the buffers */
1845 if( requiredsize > nconsvars )
1846 {
1847 SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
1848 SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );
1849
1850 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1851 assert(requiredsize <= nconsvars);
1852 }
1853
1854 easycase = FALSE;
1855
1856 if( SCIPisZero(scip, constant) )
1857 {
1858 /* add active representation */
1859 for( v2 = nconsvars - 1; v2 >= 0; --v2 )
1860 {
1861 if( !SCIPvarIsBinary(consvars[v2]) )
1862 break;
1863
1864 if( !SCIPisEQ(scip, consvals[v2], 1.0) )
1865 break;
1866 }
1867
1868 if( v2 < 0 )
1869 easycase = TRUE;
1870 }
1871 else if( SCIPisFeasEQ(scip, constant, 1.0) )
1872 {
1873 /* check for another multi-aggregation */
1874 for( v2 = consdata->nvars - 1; v2 > v; --v2 )
1875 {
1877 break;
1878 }
1879
1880 /* constraint is redundant */
1881 if( v2 == v && nconsvars == 0 )
1882 {
1883 /* we can fix */
1884 if( consdata->nvars > 1 && (SCIP_SETPPCTYPE)consdata->setppctype != SCIP_SETPPCTYPE_COVERING )
1885 {
1886 if( nfixedvars != NULL )
1887 {
1888 SCIP_Bool fixed;
1889
1890 assert(cutoff != NULL);
1891
1892 for( v2 = consdata->nvars - 1; v2 >= 0; --v2 )
1893 {
1894 if( consdata->vars[v2] != var )
1895 {
1896 SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(consdata->vars[v2]));
1897
1898 /* fix all remaining variables to zero, constraint is already feasible or infeasible */
1899 SCIP_CALL( SCIPfixVar(scip, consdata->vars[v2], 0.0, cutoff, &fixed) );
1900 if( *cutoff )
1901 {
1902 SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
1903 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v2]));
1904
1905 SCIPfreeBufferArray(scip, &consvals);
1906 SCIPfreeBufferArray(scip, &consvars);
1907
1908 goto TERMINATE;
1909 }
1910
1911 if( fixed )
1912 ++(*nfixedvars);
1913 }
1914 }
1915 }
1916 }
1917
1918 if( ndelconss != NULL && (nfixedvars != NULL || consdata->nvars == 1 || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING) )
1919 {
1920 /* delete old constraint */
1921 SCIP_CALL( SCIPdelCons(scip, cons) );
1922 ++(*ndelconss);
1923 }
1924 SCIPfreeBufferArray(scip, &consvals);
1925 SCIPfreeBufferArray(scip, &consvars);
1926
1927 goto TERMINATE;
1928 }
1929 }
1930
1931 /* we can easily add the coefficients and still have a setppc constraint */
1932 if( easycase )
1933 {
1934 /* delete old (multi-aggregated) variable */
1935 SCIP_CALL( delCoefPos(scip, cons, v) );
1936
1937 /* add active representation */
1938 for( v2 = nconsvars - 1; v2 >= 0; --v2 )
1939 {
1940 assert(SCIPvarIsBinary(consvars[v2]));
1941 assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
1942
1943 SCIP_CALL( addCoef(scip, cons, consvars[v2]) );
1944 }
1945 }
1946 /* we need to degrade this setppc constraint to a linear constraint */
1947 else if( (ndelconss != NULL && naddconss != NULL) || SCIPconsIsAdded(cons) )
1948 {
1949 char name[SCIP_MAXSTRLEN];
1950 SCIP_CONS* newcons;
1951 SCIP_Real lhs;
1952 SCIP_Real rhs;
1953 int size;
1954 int k;
1955
1956 /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole
1957 * probvar sum over all variables
1958 */
1959
1960 size = MAX(nconsvars, 1) + consdata->nvars - 1;
1961
1962 /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1963 SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, size) );
1964 SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, size) );
1965
1966 nconsvars = consdata->nvars;
1967
1968 /* add constraint variables to new linear variables */
1969 for( k = consdata->nvars - 1; k >= 0; --k )
1970 {
1971 consvars[k] = consdata->vars[k];
1972 consvals[k] = 1.0;
1973 }
1974
1975 constant = 0.0;
1976
1977 /* get active variables for new constraint */
1978 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1979
1980 /* if space was not enough (we found another multi-aggregation), we need to resize the buffers */
1981 if( requiredsize > nconsvars )
1982 {
1983 SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
1984 SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );
1985
1986 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1987 assert(requiredsize <= nconsvars);
1988 }
1989
1990 /* compute sides */
1991 if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
1992 {
1993 lhs = -SCIPinfinity(scip);
1994 rhs = 1.0 - constant;
1995 }
1996 else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
1997 {
1998 lhs = 1.0 - constant;
1999 rhs = 1.0 - constant;
2000 }
2001 else
2002 {
2003 assert((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING);
2004 lhs = 1.0 - constant;
2005 rhs = SCIPinfinity(scip);
2006 }
2007
2008 /* create linear constraint */
2009 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPconsGetName(cons));
2010 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, nconsvars, consvars, consvals, lhs, rhs,
2011 SCIPconsIsInitial(cons),
2015 SCIP_CALL( SCIPaddCons(scip, newcons) );
2016
2017 SCIPdebugMsg(scip, "added linear constraint: ");
2018 SCIPdebugPrintCons(scip, newcons, NULL);
2019 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2020
2021 SCIPfreeBufferArray(scip, &consvals);
2022 SCIPfreeBufferArray(scip, &consvars);
2023
2024 /* delete old constraint */
2025 SCIP_CALL( SCIPdelCons(scip, cons) );
2026 if( ndelconss != NULL && naddconss != NULL )
2027 {
2028 ++(*ndelconss);
2029 ++(*naddconss);
2030 }
2031
2032 goto TERMINATE;
2033 }
2034 /* we need to degrade this setppc constraint to a linear constraint*/
2035 else
2036 {
2037 /* check, if the variable should be replaced with the representative */
2038 if( repvar != var )
2039 {
2040 /* delete old (aggregated) variable */
2041 SCIP_CALL( delCoefPos(scip, cons, v) );
2042
2043 /* add representative instead */
2044 SCIP_CALL( addCoef(scip, cons, repvar) );
2045 }
2046
2047 SCIPwarningMessage(scip, "setppc constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
2048 ++v;
2049 }
2050
2051 SCIPfreeBufferArray(scip, &consvals);
2052 SCIPfreeBufferArray(scip, &consvars);
2053 }
2054 else
2055 {
2056 /* check, if the variable should be replaced with the representative */
2057 if( repvar != var )
2058 {
2059 /* delete old (aggregated) variable */
2060 SCIP_CALL( delCoefPos(scip, cons, v) );
2061
2062 /* add representative instead */
2063 SCIP_CALL( addCoef(scip, cons, repvar) );
2064 }
2065 else
2066 ++v;
2067 }
2068 }
2069 }
2070
2071 TERMINATE:
2072 /* all multi-aggregations should be resolved */
2073 consdata->existmultaggr = FALSE;
2074
2075 return SCIP_OKAY;
2076}
2077
2078/** analyzes conflicting assignment on given constraint where all of the variables where assigned to zero,
2079 * and adds conflict constraint to problem
2080 */
2081static
2083 SCIP* scip, /**< SCIP data structure */
2084 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2085 )
2086{
2087 SCIP_CONSDATA* consdata;
2088 int v;
2089
2090 /* conflict analysis can only be applied in solving stage and if it is applicable */
2092 return SCIP_OKAY;
2093
2094 consdata = SCIPconsGetData(cons);
2095 assert(consdata != NULL);
2096 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
2097 || consdata->setppctype == SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
2098
2099 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2101
2102 for( v = 0; v < consdata->nvars; ++v )
2103 {
2104 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
2105 }
2106
2107 /* analyze the conflict */
2109
2110 return SCIP_OKAY;
2111}
2112
2113/** analyzes conflicting assignment on given constraint where two of the variables where assigned to one,
2114 * and adds conflict constraint to problem
2115 */
2116static
2118 SCIP* scip, /**< SCIP data structure */
2119 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2120 )
2121{
2122 SCIP_CONSDATA* consdata;
2123 int v;
2124 int n;
2125
2126 /* conflict analysis can only be applied in solving stage and if it is applicable */
2128 return SCIP_OKAY;
2129
2130 consdata = SCIPconsGetData(cons);
2131 assert(consdata != NULL);
2132 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
2133 || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2134
2135 /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
2137
2138 n = 0;
2139 for( v = 0; v < consdata->nvars && n < 2; ++v )
2140 {
2141 if( SCIPvarGetLbLocal(consdata->vars[v]) > 0.5 )
2142 {
2143 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
2144 n++;
2145 }
2146 }
2147 assert(n == 2);
2148
2149 /* analyze the conflict */
2151
2152 return SCIP_OKAY;
2153}
2154
2155/** checks constraint for violation only looking at the fixed variables, applies further fixings if possible */
2156static
2158 SCIP* scip, /**< SCIP data structure */
2159 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint to be processed */
2160 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2161 int* nfixedvars, /**< pointer to count number of deleted variables */
2162 SCIP_Bool* addcut, /**< pointer to store whether this constraint must be added as a cut */
2163 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
2164 )
2165{
2166 SCIP_CONSDATA* consdata;
2167#ifndef NDEBUG
2168 int oldnfixedvars;
2169#endif
2170
2171 assert(cons != NULL);
2172 assert(SCIPconsGetHdlr(cons) != NULL);
2173 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
2174 assert(cutoff != NULL);
2175 assert(nfixedvars != NULL);
2176 assert(addcut != NULL);
2177 assert(mustcheck != NULL);
2178
2179#ifndef NDEBUG
2180 oldnfixedvars = *nfixedvars;
2181#endif
2182
2183 consdata = SCIPconsGetData(cons);
2184 assert(consdata != NULL);
2185 assert(consdata->nvars == 0 || consdata->vars != NULL);
2186 assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nvars);
2187 assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nvars);
2188
2189 *addcut = FALSE;
2190 *mustcheck = TRUE;
2191
2192 /*SCIPdebugMsg(scip, "processing constraint <%s> with respect to fixed variables (%d fixed to 0.0, %d fixed to 1.0)\n",
2193 SCIPconsGetName(cons), consdata->nfixedzeros, consdata->nfixedones);*/
2194
2195 if( consdata->nfixedones == 1 )
2196 {
2197 /* exactly one variable is fixed to 1:
2198 * - a set covering constraint is feasible anyway and can be disabled
2199 * - all other variables in a set partitioning or packing constraint must be zero
2200 */
2201 if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
2202 {
2203 SCIPdebugMsg(scip, " -> disabling set covering constraint <%s>\n", SCIPconsGetName(cons));
2205 }
2206 else
2207 {
2208 if( consdata->nfixedzeros < consdata->nvars - 1 )
2209 {
2210 SCIP_VAR** vars;
2211 SCIP_VAR* var;
2212#ifndef NDEBUG
2213 SCIP_Bool fixedonefound;
2214#endif
2215 SCIP_Bool infeasible;
2216 SCIP_Bool tightened;
2217 int nvars;
2218 int v;
2219 int oneidx = -1;
2220
2221 SCIPdebugMsg(scip, " -> fixing all other variables to zero in set packing/partitioning constraint <%s>\n",
2222 SCIPconsGetName(cons));
2223
2224 /* unfixed variables exist: fix them to zero;
2225 * this could result in additional variables fixed to one due to aggregations; in this case, the
2226 * constraint is infeasible in local bounds
2227 */
2228 vars = consdata->vars;
2229 nvars = consdata->nvars;
2230#ifndef NDEBUG
2231 fixedonefound = FALSE;
2232#endif
2233 for( v = 0; v < nvars && consdata->nfixedones == 1; ++v )
2234 {
2235 var = vars[v];
2237 if( SCIPvarGetLbLocal(var) < 0.5 )
2238 {
2239 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, oneidx, &infeasible, &tightened) );
2240 assert(!infeasible);
2241
2242 if( tightened )
2243 ++(*nfixedvars);
2244
2245 SCIPdebugMsg(scip, " -> fixed <%s> to zero (tightened=%u)\n", SCIPvarGetName(var), tightened);
2246 }
2247 else
2248 {
2249#ifndef NDEBUG
2250 fixedonefound = TRUE;
2251#endif
2252 oneidx = v;
2253 }
2254 }
2255 /* the fixed to one variable must have been found, and at least one variable must have been fixed */
2256 assert(consdata->nfixedones >= 2 || (fixedonefound && *nfixedvars > oldnfixedvars));
2257
2259 }
2260
2261 /* now all other variables are fixed to zero:
2262 * the constraint is feasible, and if it's not modifiable, it is redundant
2263 */
2264 if( !SCIPconsIsModifiable(cons) && consdata->nfixedones == 1 )
2265 {
2266 SCIPdebugMsg(scip, " -> disabling set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2268 }
2269 }
2270 *mustcheck = FALSE;
2271 }
2272
2273 if( consdata->nfixedones >= 2 )
2274 {
2275 /* at least two variables are fixed to 1:
2276 * - a set covering constraint is feasible anyway and can be disabled
2277 * - a set partitioning or packing constraint is infeasible
2278 */
2279 if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
2280 {
2281 SCIPdebugMsg(scip, " -> disabling set covering constraint <%s>\n", SCIPconsGetName(cons));
2283 }
2284 else
2285 {
2286 SCIPdebugMsg(scip, " -> conflict on set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2287
2289
2290 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
2292
2293 *cutoff = TRUE;
2294 }
2295 *mustcheck = FALSE;
2296 }
2297 else if( consdata->nfixedzeros == consdata->nvars )
2298 {
2299 /* all variables are fixed to zero:
2300 * - a set packing constraint is feasible anyway, and if it's unmodifiable, it can be disabled
2301 * - a set partitioning or covering constraint is infeasible, and if it's unmodifiable, the node
2302 * can be cut off -- otherwise, the constraint must be added as a cut and further pricing must
2303 * be performed
2304 */
2305 assert(consdata->nfixedones == 0);
2306
2307 if( consdata->setppctype == SCIP_SETPPCTYPE_PACKING ) /*lint !e641*/
2308 {
2309 if( !SCIPconsIsModifiable(cons) )
2310 {
2311 SCIPdebugMsg(scip, " -> disabling set packing constraint <%s>\n", SCIPconsGetName(cons));
2313 }
2314 }
2315 else
2316 {
2317 SCIPdebugMsg(scip, " -> set covering/partitioning constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2318
2320 if( SCIPconsIsModifiable(cons) )
2321 *addcut = TRUE;
2322 else
2323 {
2324 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
2326
2327 *cutoff = TRUE;
2328 }
2329 }
2330 *mustcheck = FALSE;
2331 }
2332 else if( consdata->nfixedzeros == consdata->nvars - 1 && consdata->nfixedones == 0 )
2333 {
2334 /* all variables except one are fixed to zero:
2335 * - a set packing constraint is feasible anyway, and if it's unmodifiable, it can be disabled
2336 * - an unmodifiable set partitioning or covering constraint is feasible and can be disabled after the
2337 * remaining variable is fixed to one
2338 * - a modifiable set partitioning or covering constraint must be checked manually
2339 */
2340 if( consdata->setppctype == SCIP_SETPPCTYPE_PACKING ) /*lint !e641*/
2341 {
2342 if( !SCIPconsIsModifiable(cons) )
2343 {
2344 SCIPdebugMsg(scip, " -> disabling set packing constraint <%s>\n", SCIPconsGetName(cons));
2346 }
2347 *mustcheck = FALSE;
2348 }
2349 else if( !SCIPconsIsModifiable(cons) )
2350 {
2351 SCIP_VAR** vars;
2352 SCIP_VAR* var;
2353 SCIP_Bool infeasible;
2354 SCIP_Bool tightened;
2355 int nvars;
2356 int v;
2357
2358 /* search the single variable that can be fixed */
2359 vars = consdata->vars;
2360 nvars = consdata->nvars;
2361 for( v = 0; v < nvars; ++v )
2362 {
2363 var = vars[v];
2364 assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)));
2366 if( SCIPvarGetUbLocal(var) > 0.5 )
2367 {
2368 SCIPdebugMsg(scip, " -> fixing remaining variable <%s> to one in set covering/partitioning constraint <%s>\n",
2369 SCIPvarGetName(var), SCIPconsGetName(cons));
2370 SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, 0, &infeasible, &tightened) );
2371 assert(!infeasible);
2372 assert(tightened);
2373
2374 ++(*nfixedvars);
2375 break;
2376 }
2377 }
2378 assert(v < nvars);
2379 assert(consdata->nfixedzeros == consdata->nvars - 1);
2380 assert(consdata->nfixedones == 1);
2381
2383 *mustcheck = FALSE;
2384 }
2385 }
2386 assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nvars);
2387
2388 return SCIP_OKAY;
2389}
2390
2391/** checks constraint for violation, returns TRUE iff constraint is feasible */
2392static
2394 SCIP* scip, /**< SCIP data structure */
2395 SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint to be checked */
2396 SCIP_SOL* sol /**< primal CIP solution */
2397 )
2398{
2399 SCIP_VAR** vars;
2400 SCIP_Real solval;
2401 SCIP_Real sum;
2402 SCIP_Real sumbound;
2403 SCIP_Real absviol;
2404 SCIP_Real relviol;
2405 SCIP_Bool check;
2406 int nvars;
2407 int v;
2408
2409 /* calculate the constraint's activity */
2410 vars = consdata->vars;
2411 nvars = consdata->nvars;
2412 sum = 0.0;
2413 sumbound = ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING ? 1.0 : 1.0 + 2*SCIPfeastol(scip));
2414 for( v = 0; v < nvars && sum < sumbound; ++v ) /* if sum >= sumbound, the feasibility is clearly decided */
2415 {
2416 assert(SCIPvarIsBinary(vars[v]));
2417
2418 solval = SCIPgetSolVal(scip, sol, vars[v]);
2419 assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0));
2420
2421 sum += solval;
2422 }
2423
2424 absviol = sum - 1.0;
2425 relviol = SCIPrelDiff(sum, 1.0);
2426 switch( consdata->setppctype )
2427 {
2429 /* in case of partitioning, the violation is equal to the absolute difference between sum and 1 */
2430 absviol = REALABS(absviol);
2431 relviol = REALABS(relviol);
2432 check = SCIPisFeasEQ(scip, sum, 1.0);
2433 break;
2435 /* in case of packing, the violation is equal to how much sum exceeds 1 */
2436 check = SCIPisFeasLE(scip, sum, 1.0);
2437 break;
2439 /* in case of covering, the violation is equal to how much 1 exceeds sum */
2440 absviol = -absviol;
2441 relviol = -relviol;
2442 check = SCIPisFeasGE(scip, sum, 1.0);
2443 break;
2444 default:
2445 SCIPerrorMessage("unknown setppc type\n");
2446 SCIPABORT();
2447 return FALSE; /*lint !e527*/
2448 }
2449
2450 if( sol != NULL )
2451 SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);
2452
2453 return check;
2454}
2455
2456/** creates an LP row in a set partitioning / packing / covering constraint data object */
2457static
2459 SCIP* scip, /**< SCIP data structure */
2460 SCIP_CONS* cons /**< set partitioning / packing / covering constraint */
2461 )
2462{
2463 SCIP_CONSDATA* consdata;
2464 SCIP_Real lhs;
2465 SCIP_Real rhs;
2466
2467 consdata = SCIPconsGetData(cons);
2468 assert(consdata != NULL);
2469 assert(consdata->row == NULL);
2470
2471 switch( consdata->setppctype )
2472 {
2474 lhs = 1.0;
2475 rhs = 1.0;
2476 break;
2478 lhs = -SCIPinfinity(scip);
2479 rhs = 1.0;
2480 break;
2482 lhs = 1.0;
2483 rhs = SCIPinfinity(scip);
2484 break;
2485 default:
2486 SCIPerrorMessage("unknown setppc type\n");
2487 return SCIP_INVALIDDATA;
2488 }
2489
2490 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, cons, SCIPconsGetName(cons), lhs, rhs,
2492
2493 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
2494
2495 return SCIP_OKAY;
2496}
2497
2498/** adds setppc constraint as cut to the LP */
2499static
2501 SCIP* scip, /**< SCIP data structure */
2502 SCIP_CONS* cons, /**< setppc constraint */
2503 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
2504 )
2505{
2506 SCIP_CONSDATA* consdata;
2507
2508 assert( cutoff != NULL );
2509 *cutoff = FALSE;
2510
2511 consdata = SCIPconsGetData(cons);
2512 assert(consdata != NULL);
2513
2514 if( consdata->row == NULL )
2515 {
2516 /* convert set partitioning constraint data into LP row */
2517 SCIP_CALL( createRow(scip, cons) );
2518 }
2519 assert(consdata->row != NULL);
2520
2521 /* insert LP row as cut */
2522 if( !SCIProwIsInLP(consdata->row) )
2523 {
2524 SCIPdebugMsg(scip, "adding constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
2525 SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, cutoff) );
2526 }
2527
2528 return SCIP_OKAY;
2529}
2530
2531/** adds setppc constraint as row to the NLP, if not added yet */
2532static
2534 SCIP* scip, /**< SCIP data structure */
2535 SCIP_CONS* cons /**< setppc constraint */
2536 )
2537{
2538 SCIP_CONSDATA* consdata;
2539
2540 assert(SCIPisNLPConstructed(scip));
2541
2542 /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
2543 if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
2544 return SCIP_OKAY;
2545
2546 consdata = SCIPconsGetData(cons);
2547 assert(consdata != NULL);
2548
2549 if( consdata->nlrow == NULL )
2550 {
2551 SCIP_Real lhs, rhs;
2552 SCIP_Real* coefs;
2553 int i;
2554
2555 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nvars) );
2556 for( i = 0; i < consdata->nvars; ++i )
2557 coefs[i] = 1.0;
2558
2559 switch( SCIPgetTypeSetppc(scip, cons) )
2560 {
2562 lhs = 1.0;
2563 rhs = 1.0;
2564 break;
2565
2567 lhs = -SCIPinfinity(scip);
2568 rhs = 1.0;
2569 break;
2570
2572 lhs = 1.0;
2573 rhs = SCIPinfinity(scip);
2574 break;
2575
2576 default:
2577 SCIPerrorMessage("unexpected setppc type\n");
2578 return SCIP_ERROR;
2579 }
2580
2581 SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow, SCIPconsGetName(cons),
2582 0.0, consdata->nvars, consdata->vars, coefs, NULL, lhs, rhs, SCIP_EXPRCURV_LINEAR) );
2583 assert(consdata->nlrow != NULL);
2584
2585 SCIPfreeBufferArray(scip, &coefs);
2586 }
2587
2588 if( !SCIPnlrowIsInNLP(consdata->nlrow) )
2589 {
2590 SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow) );
2591 }
2592
2593 return SCIP_OKAY;
2594}
2595
2596/** checks constraint for violation, and adds it as a cut if possible */
2597static
2599 SCIP* scip, /**< SCIP data structure */
2600 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint to be separated */
2601 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
2602 SCIP_Bool lpfeas, /**< is the given solution feasible for the current LP ? */
2603 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2604 SCIP_Bool* separated, /**< pointer to store TRUE, if a cut was found */
2605 SCIP_Bool* reduceddom /**< pointer to store TRUE, if a domain reduction was found */
2606 )
2607{
2608 SCIP_CONSDATA* consdata;
2609 SCIP_Bool addcut;
2610 SCIP_Bool mustcheck;
2611
2612 assert(cons != NULL);
2613 assert(SCIPconsGetHdlr(cons) != NULL);
2614 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
2615 assert(cutoff != NULL);
2616 assert(separated != NULL);
2617 assert(reduceddom != NULL);
2618
2619 *cutoff = FALSE;
2620
2621 consdata = SCIPconsGetData(cons);
2622 assert(consdata != NULL);
2623 assert(consdata->nvars == 0 || consdata->vars != NULL);
2624 assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nvars);
2625 assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nvars);
2626
2627 /* skip constraints already in the LP */
2628 if( lpfeas && consdata->row != NULL && SCIProwIsInLP(consdata->row) )
2629 return SCIP_OKAY;
2630
2631 SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons));
2632
2633 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2634 if( lpfeas )
2635 {
2636 int nfixedvars = 0;
2637
2638 SCIP_CALL( processFixings(scip, cons, cutoff, &nfixedvars, &addcut, &mustcheck) );
2639
2640 *reduceddom = (nfixedvars > 0);
2641 }
2642 else
2643 {
2644 mustcheck = TRUE;
2645 addcut = FALSE;
2646 }
2647
2648 if( mustcheck )
2649 {
2650 assert(!addcut);
2651
2652 /* variable's fixings didn't give us any information -> we have to check the constraint */
2653 if( lpfeas && consdata->row != NULL )
2654 {
2655 SCIP_Real feasibility;
2656
2657 assert(!SCIProwIsInLP(consdata->row));
2658 feasibility = SCIPgetRowSolFeasibility(scip, consdata->row, sol);
2659 addcut = SCIPisFeasNegative(scip, feasibility);
2660 }
2661 else
2662 addcut = !checkCons(scip, consdata, sol);
2663
2664 if( !addcut )
2665 {
2666 /* constraint was feasible -> increase age */
2667 SCIP_CALL( SCIPincConsAge(scip, cons) );
2668 }
2669 }
2670
2671 if( addcut )
2672 {
2673 /* insert LP row as cut */
2674 SCIP_CALL( addCut(scip, cons, cutoff) );
2676 *separated = TRUE;
2677 }
2678
2679 return SCIP_OKAY;
2680}
2681
2682/** enforces the pseudo solution on the given constraint */
2683static
2685 SCIP* scip, /**< SCIP data structure */
2686 SCIP_CONS* cons, /**< set partitioning / packing / covering constraint to be separated */
2687 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2688 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
2689 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
2690 SCIP_Bool* solvelp /**< pointer to store TRUE, if the LP has to be solved */
2691 )
2692{
2693 SCIP_Bool addcut;
2694 SCIP_Bool mustcheck;
2695 int nfixedvars = 0;
2696
2697 assert(!SCIPhasCurrentNodeLP(scip));
2698 assert(cons != NULL);
2699 assert(SCIPconsGetHdlr(cons) != NULL);
2700 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
2701 assert(cutoff != NULL);
2702 assert(infeasible != NULL);
2703 assert(reduceddom != NULL);
2704 assert(solvelp != NULL);
2705
2706 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2707 SCIP_CALL( processFixings(scip, cons, cutoff, &nfixedvars, &addcut, &mustcheck) );
2708
2709 *reduceddom = (nfixedvars > 0);
2710
2711 if( mustcheck )
2712 {
2713 SCIP_CONSDATA* consdata;
2714
2715 assert(!addcut);
2716
2717 consdata = SCIPconsGetData(cons);
2718 assert(consdata != NULL);
2719
2720 if( checkCons(scip, consdata, NULL) )
2721 {
2722 /* constraint was feasible -> increase age */
2723 SCIP_CALL( SCIPincConsAge(scip, cons) );
2724 }
2725 else
2726 {
2727 /* constraint was infeasible -> reset age */
2729 *infeasible = TRUE;
2730 }
2731 }
2732
2733 if( addcut )
2734 {
2735 /* a cut must be added to the LP -> we have to solve the LP immediately */
2737 *solvelp = TRUE;
2738 }
2739
2740 return SCIP_OKAY;
2741}
2742
2743/** gets the key of the given element */
2744static
2745SCIP_DECL_HASHGETKEY(hashGetKeySetppccons)
2746{ /*lint --e{715}*/
2747 /* the key is the element itself */
2748 return elem;
2749}
2750
2751/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
2752static
2753SCIP_DECL_HASHKEYEQ(hashKeyEqSetppccons)
2754{
2755#ifndef NDEBUG
2756 SCIP* scip;
2757#endif
2758 SCIP_CONSDATA* consdata1;
2759 SCIP_CONSDATA* consdata2;
2760 SCIP_Bool coefsequal;
2761 int i;
2762
2763 consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
2764 consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
2765 assert(consdata1->sorted);
2766 assert(consdata2->sorted);
2767#ifndef NDEBUG
2768 scip = (SCIP*)userptr;
2769 assert(scip != NULL);
2770#endif
2771
2772 /* checks trivial case */
2773 if( consdata1->nvars != consdata2->nvars )
2774 return FALSE;
2775
2776 coefsequal = TRUE;
2777
2778 for( i = 0; i < consdata1->nvars; ++i )
2779 {
2780 /* tests if variables are equal */
2781 if( consdata1->vars[i] != consdata2->vars[i] )
2782 {
2783 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
2784 SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
2785 coefsequal = FALSE;
2786 break;
2787 }
2788 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
2789 }
2790
2791 return coefsequal;
2792}
2793
2794/** returns the hash value of the key */
2795static
2796SCIP_DECL_HASHKEYVAL(hashKeyValSetppccons)
2797{
2798 SCIP_CONSDATA* consdata;
2799 int minidx;
2800 int mididx;
2801 int maxidx;
2802#ifndef NDEBUG
2803 SCIP* scip;
2804
2805 scip = (SCIP*)userptr;
2806 assert(scip != NULL);
2807#endif
2808
2809 consdata = SCIPconsGetData((SCIP_CONS*)key);
2810 assert(consdata != NULL);
2811 assert(consdata->nvars > 0);
2812
2813 /* sorts the constraints */
2814 consdataSort(consdata);
2815
2816 minidx = SCIPvarGetIndex(consdata->vars[0]);
2817 mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
2818 maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
2819 assert(minidx >= 0 && minidx <= maxidx);
2820
2821 return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
2822}
2823
2824/** add extra clique-constraints resulting from a given cliquepartition to SCIP */
2825static
2827 SCIP*const scip, /**< SCIP data structure */
2828 SCIP_VAR**const binvars, /**< binary variables to create clique constraints */
2829 int const nbinvars, /**< number of binary variables to create clique constraints */
2830 int*const cliquepartition, /**< clique partition of binary variables */
2831 int const ncliques, /**< number of cliques in cliquepartition */
2832 SCIP_CONS**const usefulconss, /**< storage for created constraints */
2833 int*const nusefulconss, /**< pointer to store number of useful created constraints */
2834 int const nrounds, /**< actual presolving round */
2835 int*const nfixedvars, /**< pointer to count number of deleted variables */
2836 int*const naddconss, /**< pointer to count number of added constraints */
2837 int*const ndelconss, /**< pointer to count number of deleted constraints */
2838 int*const nchgcoefs, /**< pointer to count number of deleted coefficients */
2839 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
2840 )
2841{
2842 SCIP_CONS* cliquecons;
2843 char name[SCIP_MAXSTRLEN];
2844 int lastclqidx;
2845 int nadded;
2846 int c;
2847 int v;
2848
2849 assert(scip != NULL);
2850 assert(binvars != NULL || nbinvars == 0);
2851 assert(cliquepartition != NULL || nbinvars == 0);
2852 assert(ncliques >= 0 && ncliques <= nbinvars);
2853 assert(usefulconss != NULL);
2854 assert(nusefulconss != NULL);
2855 assert(nfixedvars != NULL);
2856 assert(naddconss != NULL);
2857 assert(ndelconss != NULL);
2858 assert(nchgcoefs != NULL);
2859 assert(cutoff != NULL);
2860
2861 /* no given binary variables */
2862 if( nbinvars == 0 || ncliques == 0 )
2863 return SCIP_OKAY;
2864
2865 assert(binvars != NULL);
2866 assert(cliquepartition != NULL);
2867
2868 /* no useful clique information */
2869 if( ncliques == nbinvars )
2870 return SCIP_OKAY;
2871
2872 lastclqidx = 0;
2873
2874 /* @todo: maybe sort cliques and accordingly the variables so it will be faster to add the constraints */
2875 for( c = 0; c < ncliques - 1; ++c )
2876 {
2877 if( lastclqidx >= cliquepartition[c] )
2878 continue;
2879
2880 nadded = 0;
2881
2882 /* name the clique constraint */
2883 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extra_clq_%d_round_%d", cliquepartition[c], nrounds);
2884 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 0, NULL,
2886
2887 /* add variables to clique constraint */
2888 for( v = c; v < nbinvars - 1; ++v )
2889 {
2890 if( cliquepartition[c] == cliquepartition[v] )
2891 {
2892 SCIP_CALL( addCoef(scip, cliquecons, binvars[v]) );
2893 ++nadded;
2894 }
2895 }
2896
2897 /* @todo: try to find a good value for what are enough variables to create this constraint, maybe at least
2898 * (nmaxvars(over all conss)-nminvars(over all conss))/2 */
2899 if( nadded >= 2 )
2900 {
2901 SCIP_CONSDATA* cliqueconsdata;
2902
2903 SCIPdebugMsg(scip, " -> adding clique constraint: ");
2904 SCIPdebugPrintCons(scip, cliquecons, NULL);
2905 SCIP_CALL( SCIPaddCons(scip, cliquecons) );
2906 ++(*naddconss);
2907
2908 /* we only want to consider merged constraints */
2909 SCIP_CALL( mergeMultiples(scip, cliquecons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
2910 if( *cutoff )
2911 {
2912 SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2913
2914 return SCIP_OKAY;
2915 }
2916
2917 cliqueconsdata = SCIPconsGetData(cliquecons);
2918 assert(cliqueconsdata != NULL);
2919
2920 /* the artificial constraints could be deleted while merging */
2921 if( !SCIPconsIsDeleted(cliquecons) && nadded - cliqueconsdata->nfixedzeros >= 2 )
2922 {
2923 assert(cliqueconsdata->nfixedones == 0);
2924
2925 /* save the type and constraint */
2926 usefulconss[*nusefulconss] = cliquecons;
2927 ++(*nusefulconss);
2928 }
2929 SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2930 }
2931 else
2932 {
2933 SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2934 }
2935 lastclqidx = cliquepartition[c];
2936 }
2937
2938 return SCIP_OKAY;
2939}
2940
2941
2942/** start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
2943 * constraints
2944 */
2945static
2947 SCIP*const scip, /**< SCIP data structure */
2948 SCIP_CONS**const conss, /**< constraint set */
2949 int const nconss, /**< number of constraints in constraint set */
2950 SCIP_CONS**const usefulconss, /**< storage for created constraints */
2951 int*const nusefulconss, /**< pointer to store number of useful created constraints */
2952 int*const nfixedvars, /**< pointer to count number of deleted variables */
2953 int*const ndelconss, /**< pointer to count number of deleted constraints */
2954 int*const nchgcoefs, /**< pointer to count number of deleted coefficients */
2955 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
2956 )
2957{
2958 SCIP_CONS* cons;
2959 SCIP_CONSDATA* consdata;
2960 SCIP_Bool addcut;
2961 SCIP_Bool mustcheck;
2962 int nlocaladdconss = 0;
2963 int c;
2964
2965 assert(scip != NULL);
2966 assert(conss != NULL || nconss == 0);
2967 assert(usefulconss != NULL);
2968 assert(nusefulconss != NULL);
2969 assert(nfixedvars != NULL);
2970 assert(ndelconss != NULL);
2971 assert(nchgcoefs != NULL);
2972 assert(cutoff != NULL);
2973
2974 if( nconss == 0 )
2975 return SCIP_OKAY;
2976
2977 assert(conss != NULL);
2978
2979 for( c = nconss - 1; c >= 0; --c )
2980 {
2981 cons = conss[c];
2982
2983 /* we only want to consider constraints with either active or negated of active variables, applyfixings removes
2984 * aggregated and fixed variables to zero, processFixings removes fixings to one but no aggregation
2985 *
2986 * @todo: maybe write a new method for deleting aggregations and all fixings
2987 */
2988 SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );
2989 if( *cutoff )
2990 return SCIP_OKAY;
2991
2992 if( SCIPconsIsDeleted(cons) )
2993 {
2994 /* reset nlocaladdconss and continue */
2995 nlocaladdconss = 0;
2996 continue;
2997 }
2998 assert(nlocaladdconss == 0);
2999
3000 SCIP_CALL( processFixings(scip, cons, cutoff, nfixedvars, &addcut, &mustcheck) );
3001 if( *cutoff )
3002 return SCIP_OKAY;
3003
3004 consdata = SCIPconsGetData(cons);
3005 assert(consdata != NULL);
3006
3007 /* we only want to consider merged constraints */
3008 SCIP_CALL( mergeMultiples(scip, cons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
3009 if( *cutoff )
3010 return SCIP_OKAY;
3011
3012 if( SCIPconsIsModifiable(cons) || !SCIPconsIsActive(cons) )
3013 continue;
3014
3015 assert(consdata->nfixedones == 0);
3016
3017 if( consdata->nvars == 0 )
3018 continue;
3019
3020 /* @todo: check for covering constraints with only two variables which are equal to a packing constraint with
3021 * negated variables */
3022 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3023 {
3024 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3025
3026 usefulconss[*nusefulconss] = cons;
3027 ++(*nusefulconss);
3028 }
3029 }
3030
3031 return SCIP_OKAY; /*lint !e438*/
3032}
3033
3034/** creating all necessary data in array structure, collect all clique constraint variables and occurrences,
3035 * @note works only with merged and active not set-covering constraints
3036 */
3037static
3039 SCIP*const scip, /**< SCIP data structure */
3040 SCIP_CONS**const usefulconss, /**< clique constraints */
3041 int const nusefulconss, /**< number of clique constraints */
3042 SCIP_VAR**const usefulvars, /**< storage for all found variables */
3043 int*const nusefulvars, /**< pointer to store number of added variables */
3044 SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3045 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3046 int*const maxnvarconsidx, /**< storage for the maximal number of occurrences of a variable */
3047 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3048 int*const maxnvars /**< pointer to store maximal number of variables of a constraint */
3049 )
3050{
3051 SCIP_CONS* cons;
3052 SCIP_CONSDATA* consdata;
3053 int varindex;
3054 int c;
3055 int v;
3056
3057 assert(scip != NULL);
3058 assert(usefulconss != NULL || nusefulconss == 0);
3059 assert(usefulvars != NULL);
3060 assert(nusefulvars != NULL);
3061 assert(vartoindex != NULL);
3062 assert(varnconss != NULL);
3063 assert(maxnvarconsidx != NULL);
3064 assert(varconsidxs != NULL);
3065 assert(maxnvars != NULL);
3066
3067 if( nusefulconss == 0 )
3068 return SCIP_OKAY;
3069
3070 assert(usefulconss != NULL);
3071
3072 for( c = nusefulconss - 1; c >= 0; --c )
3073 {
3074 cons = usefulconss[c];
3075
3076 assert(SCIPconsIsActive(cons));
3077
3078 consdata = SCIPconsGetData(cons);
3079 assert(consdata != NULL);
3080
3081 /* here we should have no covering constraints anymore and the constraint data should be merged */
3082 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3083 assert(consdata->merged);
3084
3085 /* save maximal number of vars */
3086 if( consdata->nvars > *maxnvars )
3087 *maxnvars = consdata->nvars;
3088
3089 /* adding variables and information about occurrences to local data structure */
3090 for( v = consdata->nvars - 1; v >= 0; --v )
3091 {
3092 SCIP_VAR* var;
3093
3094 var = consdata->vars[v];
3095 assert(var != NULL);
3096
3097 /* don't remember fixed vars */
3098 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
3099 continue;
3100
3101 /* only collect active or negated active variables */
3103
3104 if( !SCIPhashmapExists(vartoindex, (void*) var) )
3105 {
3106 SCIP_VAR* tmpvar;
3107
3108 usefulvars[*nusefulvars] = var;
3109 ++(*nusefulvars);
3110 varindex = *nusefulvars;
3111 SCIP_CALL( SCIPhashmapInsertInt(vartoindex, (void*) var, varindex) );
3112
3113 /* get the maximal number of occurrences of this variable, if this variables */
3114 tmpvar = SCIPvarIsNegated(var) ? SCIPvarGetNegatedVar(var) : var;
3115 maxnvarconsidx[varindex] = SCIPvarGetNLocksDownType(tmpvar, SCIP_LOCKTYPE_MODEL)
3117 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3118 }
3119 else
3120 {
3121 assert(SCIPhashmapExists(vartoindex, (void*) var));
3122 varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var);
3123 }
3124
3125 /* the number of occurrences of a variable is not limited by the locks (so maybe we have to increase memory),
3126 * because for examples converted cuts are not check and therefore they have no locks on their variables */
3127 if( varnconss[varindex] == maxnvarconsidx[varindex] )
3128 {
3129 maxnvarconsidx[varindex] = SCIPcalcMemGrowSize(scip, maxnvarconsidx[varindex] + 1);
3130 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3131 }
3132
3133 assert(varnconss[varindex] < maxnvarconsidx[varindex]);
3134 /* add the constraint number to the variable list */
3135 varconsidxs[varindex][varnconss[varindex]] = c;
3136 /* increase number of occurrences for variables */
3137 ++(varnconss[varindex]);
3138 }
3139 } /* data structure created */
3140
3141 return SCIP_OKAY;
3142}
3143
3144/** correct clique data due to an aggregation */
3145static
3147 SCIP_VAR*const var, /**< variable which appears less */
3148 int const considx, /**< constraint index which to remove */
3149 SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3150 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3151 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3152 )
3153{
3154 int varindex;
3155 int i;
3156#ifndef NDEBUG
3157 SCIP_Bool found = FALSE;
3158#endif
3159
3160 assert(var != NULL);
3161 assert(SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5);
3162 assert(considx >= 0);
3163 assert(vartoindex != NULL);
3164 assert(varnconss != NULL);
3165 assert(varconsidxs != NULL);
3166
3167 assert(SCIPhashmapExists(vartoindex, (void*) var));
3168 varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var);
3169
3170 /* remove entry of variable at the given position */
3171 for( i = 0; i < varnconss[varindex]; ++i )
3172 {
3173 if( varconsidxs[varindex][i] == considx )
3174 {
3175 varconsidxs[varindex][i] = varconsidxs[varindex][varnconss[varindex] - 1];
3176#ifndef NDEBUG
3177 found = TRUE;
3178#endif
3179 --(varnconss[varindex]);
3180 break;
3181 }
3182 }
3183 assert(found);
3184}
3185
3186/* correct local data structure, add constraint entry to variable data */
3187static
3189 SCIP*const scip, /**< SCIP data structure */
3190 SCIP_VAR*const addvar, /**< variable which was added */
3191 int const considx, /**< constraint index which to add */
3192 SCIP_Bool const maybenew, /**< could be a new variables, a negated of an already existing */
3193 SCIP_VAR**const usefulvars, /**< storage for all found variables */
3194 int*const nusefulvars, /**< pointer to store number of added variables */
3195 SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3196 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3197 int*const maxnvarconsidx, /**< storage for the maximal number of occurrences of a variable */
3198 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3199 )
3200{
3201 int varindex;
3202
3203 assert(scip != NULL);
3204 assert(addvar != NULL);
3205 assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
3206 assert(usefulvars != NULL);
3207 assert(nusefulvars != NULL);
3208 assert(vartoindex != NULL);
3209 assert(varnconss != NULL);
3210 assert(maxnvarconsidx != NULL);
3211 assert(varconsidxs != NULL);
3212
3213 /* we add the variable to the hashmap if its new */
3214 if( maybenew && !SCIPhashmapExists(vartoindex, (void*) addvar) )
3215 {
3216 assert(SCIPvarIsActive(addvar) || SCIPvarIsNegated(addvar));
3217 assert(SCIPvarGetNegatedVar(addvar) != NULL && SCIPhashmapExists(vartoindex, (void*) SCIPvarGetNegatedVar(addvar)));
3218
3219 /* @note because we can only have created a negated variable, and we already allocated enough memory for
3220 * all (even not existing) negated variables the usefulvars array should be big enough
3221 */
3222 SCIPsortedvecInsertDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, addvar, nusefulvars, NULL);
3223 varindex = *nusefulvars;
3224 SCIP_CALL( SCIPhashmapInsertInt(vartoindex, (void*) addvar, varindex) );
3225
3226 assert(varconsidxs[varindex] == NULL);
3227
3228 maxnvarconsidx[varindex] = 1;
3229 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3230 varnconss[varindex] = 0;
3231 }
3232 else
3233 {
3234 varindex = SCIPhashmapGetImageInt(vartoindex, (void*) addvar);
3235
3236 /* grow the needed memory if we added a variable */
3237 if( varnconss[varindex] == maxnvarconsidx[varindex] )
3238 {
3239 maxnvarconsidx[varindex] = SCIPcalcMemGrowSize(scip, maxnvarconsidx[varindex] + 1);
3240 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3241 }
3242 }
3243 assert(varnconss[varindex] < maxnvarconsidx[varindex]);
3244 varconsidxs[varindex][varnconss[varindex]] = considx;
3245
3246 /* increase number of occurrences for variables */
3247 ++(varnconss[varindex]);
3248
3249 return SCIP_OKAY;
3250}
3251
3252
3253/** check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3254 * possible
3255 */
3256static
3258 SCIP*const scip, /**< SCIP data structure */
3259 SCIP_CONS*const cons, /**< constraint */
3260 SCIP_Bool const aggregate, /**< try to aggregate if possible */
3261 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3262 * yet; both variables are standing next to each other; or NULL if
3263 * aggregate == TRUE
3264 */
3265 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3266 * type FALSE means the aggregation is of the form x + y = 1; type TRUE means
3267 * the aggregation is of the form x = y; or NULL if aggregate == TRUE
3268 */
3269 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed;
3270 * or NULL if aggregate == TRUE
3271 */
3272 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3273 * the value is the size of the array for the aggregation variables which
3274 * are not yet performed; or NULL if aggregate == TRUE
3275 */
3276 int*const nfixedvars, /**< pointer to count number of deleted variables */
3277 int*const naggrvars, /**< pointer to count number of aggregated variables */
3278 int*const ndelconss, /**< pointer to count number of deleted constraints */
3279 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
3280 )
3281{
3282 SCIP_CONSDATA* consdata;
3283 SCIP_VAR** vars;
3284 int nvars;
3285 int v;
3286 SCIP_Bool fixed;
3287
3288 assert(scip != NULL);
3289 assert(cons != NULL);
3290 assert(nfixedvars != NULL);
3291 assert(naggrvars != NULL);
3292 assert(ndelconss != NULL);
3293 assert(cutoff != NULL);
3294
3295 if( !SCIPconsIsActive(cons) )
3296 return SCIP_OKAY;
3297
3298 consdata = SCIPconsGetData(cons);
3299 assert(consdata != NULL);
3300
3301 if( consdata->presolpropagated )
3302 return SCIP_OKAY;
3303
3304 consdata->presolpropagated = TRUE;
3305
3306 vars = consdata->vars;
3307 nvars = consdata->nvars;
3308
3309 /* no variables left */
3310 if( nvars == 0 && !SCIPconsIsModifiable(cons) )
3311 {
3312 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3313 {
3314 SCIPdebugMsg(scip, "empty set-partition/-covering constraint <%s> found -> cutoff\n", SCIPconsGetName(cons));
3315 *cutoff = TRUE;
3316
3317 return SCIP_OKAY;
3318 }
3319 else
3320 {
3321 assert(consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3322
3323 /* delete constraint */
3324 SCIPdebugMsg(scip, " -> deleting constraint <%s>, no variables left\n", SCIPconsGetName(cons));
3325 SCIP_CALL( SCIPdelCons(scip, cons) );
3326 ++(*ndelconss);
3327
3328 return SCIP_OKAY;
3329 }
3330 }
3331
3332 /* more then two variables are fixed */
3333 if( consdata->nfixedones > 1 )
3334 {
3335 /* at least two variables are fixed to 1:
3336 * - a set covering constraint is feasible anyway and can be deleted
3337 * - a set partitioning or packing constraint is infeasible
3338 */
3339 if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3340 {
3341 /* delete constraint */
3342 SCIPdebugMsg(scip, " -> deleting set-covering constraint <%s>, at least two variables are fixed to 1\n", SCIPconsGetName(cons));
3343 SCIP_CALL( SCIPdelCons(scip, cons) );
3344 ++(*ndelconss);
3345
3346 return SCIP_OKAY;
3347 }
3348
3349 SCIPdebugMsg(scip, "set partitioning / packing constraint <%s> is infeasible, %d variables fixed to one\n", SCIPconsGetName(cons), consdata->nfixedones);
3350 *cutoff = TRUE;
3351
3352 return SCIP_OKAY;
3353 }
3354
3355 if( consdata->nfixedones == 1 )
3356 {
3357 /* exactly one variable is fixed to 1:
3358 * - a set covering constraint is feasible anyway and can be disabled
3359 * - all other variables in a set partitioning or packing constraint must be zero
3360 */
3361 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING && consdata->nfixedzeros < nvars - 1 ) /*lint !e641*/
3362 {
3363 assert(vars != NULL);
3364
3365 for( v = nvars - 1; v >= 0; --v )
3366 {
3367 if( SCIPvarGetLbLocal(vars[v]) + 0.5 < SCIPvarGetUbLocal(vars[v]) )
3368 {
3369 SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(vars[v]));
3370
3371 /* fix all remaining variables to zero, constraint is already feasible or infeasible */
3372 SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
3373 if( *cutoff )
3374 {
3375 SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
3376 SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
3377
3378 return SCIP_OKAY;
3379 }
3380
3381 assert(fixed);
3382 ++(*nfixedvars);
3383 }
3384 }
3385 }
3386
3387 if( !SCIPconsIsModifiable(cons) || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3388 {
3389 /* delete constraint */
3390 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3391 assert(SCIPconsIsActive(cons));
3392 SCIP_CALL( SCIPdelCons(scip, cons) );
3393 ++(*ndelconss);
3394 }
3395
3396 return SCIP_OKAY;
3397 }
3398
3399 /* other propagations can only be done on not modifiable constraints */
3400 if( SCIPconsIsModifiable(cons) )
3401 return SCIP_OKAY;
3402
3403 assert(vars != NULL);
3404
3405 /* all variables were fixed to zero then either delete the constraint or stop with infeasibility */
3406 if( consdata->nfixedzeros == nvars )
3407 {
3408 assert(consdata->nfixedones == 0);
3409
3410 /* all variables are fixed to zero:
3411 * - a set packing constraint is feasible anyway and can be deleted
3412 * - a set partitioning or covering constraint is infeasible, and so is the whole problem
3413 */
3414 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3415 {
3416 SCIPdebugMsg(scip, "set partitioning / covering constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3417 *cutoff = TRUE;
3418
3419 return SCIP_OKAY;
3420 }
3421
3422 /* delete constraint */
3423 SCIPdebugMsg(scip, " -> deleting set-packing constraint <%s>, all variables are fixed to zero\n", SCIPconsGetName(cons));
3424 assert(SCIPconsIsActive(cons));
3425 SCIP_CALL( SCIPdelCons(scip, cons) );
3426 ++(*ndelconss);
3427
3428 return SCIP_OKAY;
3429 }
3430
3431 /* all but one variable were fixed to zero then delete the constraint and for setpartition fix the remaining variable to 1 */
3432 if( consdata->nfixedzeros + 1 == nvars )
3433 {
3434 assert(consdata->nfixedones == 0);
3435
3436 /* all variables except one are fixed to zero:
3437 * - a set packing constraint is feasible anyway, and can be deleted
3438 * - a set partitioning or covering constraint is feasible and can be deleted after the
3439 * remaining variable is fixed to one
3440 */
3441 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3442 {
3443 fixed = FALSE;
3444 for( v = nvars - 1; v >= 0; --v )
3445 {
3446 assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
3447 if( SCIPvarGetUbLocal(vars[v]) > 0.5 )
3448 {
3449 SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to it's the last unfixed variable is the set-partitioning/covering constraint\n", SCIPvarGetName(vars[v]));
3450
3451 /* fix the remaining set partition variable */
3452 SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, cutoff, &fixed) );
3453 if( *cutoff )
3454 {
3455 SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 1\n",
3456 SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
3457
3458 return SCIP_OKAY;
3459 }
3460
3461 assert(fixed);
3462 ++(*nfixedvars);
3463 break;
3464 }
3465 }
3466 assert(fixed);
3467 }
3468
3469 /* delete constraint */
3470 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all %svariables are fixed\n", SCIPconsGetName(cons), consdata->setppctype == (int) SCIP_SETPPCTYPE_PACKING ? "but one " : "");
3471 assert(SCIPconsIsActive(cons));
3472 SCIP_CALL( SCIPdelCons(scip, cons) );
3473 ++(*ndelconss);
3474
3475 return SCIP_OKAY;
3476 }
3477
3478 /* all but two variable were fixed to zero in a setpartitioning constraint then delete the constraint and
3479 * aggregate the remaining two variables
3480 */
3481 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros + 2 == nvars ) /*lint !e641*/
3482 {
3483 SCIP_VAR* var;
3484
3485 var = NULL;
3486 for( v = nvars - 1; v >= 0; --v )
3487 {
3488 assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
3489
3490 if( SCIPvarGetUbLocal(vars[v]) > 0.5 )
3491 {
3492 if( var == NULL )
3493 var = vars[v];
3494 else
3495 {
3496 SCIP_Bool redundant;
3497 SCIP_Bool aggregated;
3498#ifdef VARUSES
3499 SCIP_CONSHDLR* conshdlr;
3500 SCIP_CONSHDLRDATA* conshdlrdata;
3501
3502 /* get event handler and event handler data */
3503 conshdlr = SCIPconsGetHdlr(cons);
3504 assert(conshdlr != NULL);
3505 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3506 assert(conshdlrdata != NULL);
3507#endif
3508 if( aggregate )
3509 {
3510 SCIPdebugMsg(scip, "trying to aggregate <%s> and <%s> due to they are the last two unfixed variables in the set partitionning constraint <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));
3511
3512#ifdef VARUSES
3513 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
3514 * and increase usage counting again
3515 */
3516 SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var) );
3517 SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, vars[v]) );
3518#endif
3519
3520 /* aggregate last remaining variables in the set partitioning constraint */
3521 SCIP_CALL( SCIPaggregateVars(scip, var, vars[v], 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
3522 if( *cutoff )
3523 {
3524 SCIPdebugMsg(scip, "set partitioning constraint <%s>: aggregate <%s> + <%s> == 1\n",
3525 SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(vars[v]));
3526
3527 return SCIP_OKAY;
3528 }
3529
3530#ifdef VARUSES
3531 /* increase variable usage counting again */
3532 SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var) );
3533 SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, vars[v]) );
3534#endif
3535
3536 if( aggregated )
3537 ++(*naggrvars);
3538
3539 if( redundant )
3540 {
3541 /* delete constraint */
3542 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3543 assert(SCIPconsIsActive(cons));
3544 SCIP_CALL( SCIPdelCons(scip, cons) );
3545 ++(*ndelconss);
3546 }
3547 }
3548 else
3549 {
3550 assert(undoneaggrvars != NULL);
3551 assert(undoneaggrtypes != NULL);
3552 assert(naggregations != NULL);
3553 assert(saggregations != NULL);
3554
3555 SCIPdebugMsg(scip, "memorize the aggregation of <%s> + <%s> = 1, because they are the last two unfixed variable in the set partitioning constraints <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));
3556
3557 /* resize the aggregation arrays if necessary */
3558 if( *saggregations == *naggregations )
3559 {
3560 *saggregations = SCIPcalcMemGrowSize(scip, *naggregations + 1);
3561 assert(*saggregations > *naggregations);
3562 SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrtypes, *saggregations) );
3563 SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrvars, 2 * (*saggregations)) );
3564
3565 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
3566 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
3567 }
3568
3569 /* memorize aggregation variables*/
3570 assert(undoneaggrtypes[*naggregations] == FALSE);
3571 undoneaggrvars[2 * (*naggregations)] = var;
3572 undoneaggrvars[2 * (*naggregations) + 1] = vars[v];
3573 ++(*naggregations);
3574
3575 if( !SCIPdoNotAggr(scip) )
3576 {
3577 /* delete constraint */
3578 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3579 assert(SCIPconsIsActive(cons));
3580 SCIP_CALL( SCIPdelCons(scip, cons) );
3581 ++(*ndelconss);
3582 }
3583 }
3584
3585 return SCIP_OKAY;
3586 }
3587 }
3588 }
3589 /* we should never be here, because the last to unfixed variables should have been either aggregated or a cutoff
3590 * should be applied
3591 */
3592 assert(FALSE); /*lint !e506*/
3593 }
3594
3595 return SCIP_OKAY;
3596}
3597
3598/** check for overlapping constraint */
3599static
3601 SCIP*const scip, /**< SCIP data structure */
3602 SCIP_CONS*const cons, /**< constraint which may overlap */
3603 int const considx, /**< constraint index to avoid checking against itself */
3604 int const endidx, /**< end index to check against given constraint */
3605 SCIP_CONS**const usefulconss, /**< clique constraints */
3606 int const nusefulconss, /**< number of clique constraints */
3607 SCIP_VAR**const usefulvars, /**< storage for all found variables */
3608 int*const nusefulvars, /**< pointer to store number of added variables */
3609 SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3610 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3611 int*const maxnvarconsidx, /**< storage for the maximal number of occurrences of a variable */
3612 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3613 int*const countofoverlapping, /**< the amount of variables of cons which overlap in all other constraint */
3614 SCIP_Bool const shrinking, /**< try to replace some variables with one variable */
3615 SCIP_Bool*const chgcons, /**< pointer to store if the given constraint was changed, due to
3616 * added/deleted variables
3617 */
3618 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3619 * yet; both variables are standing next to each other;
3620 */
3621 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3622 * type FALSE means the aggregation is of the form x + y = 1; type TRUE means
3623 * the aggregation is of the form x = y;
3624 */
3625 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed; */
3626 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3627 * the value is the size of the array for the aggregation variables which
3628 * are not yet performed;
3629 */
3630 int*const nfixedvars, /**< pointer to count number of deleted variables */
3631 int*const naggrvars, /**< pointer to count number of aggregated variables */
3632 int*const nchgcoefs, /**< pointer to count number of changed coefficients */
3633 int*const ndelconss, /**< pointer to count number of deleted constraints */
3634 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
3635 )
3636{
3637 SCIP_CONS* cons1;
3638 SCIP_CONSDATA* consdata1;
3639 SCIP_CONSDATA* consdata;
3640 SCIP_VAR** vars;
3641 SCIP_VAR** vars1;
3642 SCIP_VAR* var;
3643 SCIP_VAR* var1;
3644 SCIP_Bool fixed;
3645 SCIP_Bool overlapdestroyed;
3646 int nvars;
3647 int nvars1;
3648 int oldnfixedzeros;
3649 int c;
3650 int v;
3651 int v1;
3652#ifndef NDEBUG
3653 int oldnaggrvars;
3654#endif
3655
3656 assert(scip != NULL);
3657 assert(cons != NULL);
3658 assert(usefulconss != NULL && nusefulconss > 0);
3659 assert(0 <= considx && considx < nusefulconss);
3660 assert(usefulconss[considx] == cons);
3661 assert(0 <= endidx && endidx <= nusefulconss);
3662 assert(countofoverlapping != NULL);
3663 assert(chgcons != NULL);
3664 assert(undoneaggrvars != NULL);
3665 assert(undoneaggrtypes != NULL);
3666 assert(naggregations != NULL);
3667 assert(saggregations != NULL);
3668 assert(nfixedvars != NULL);
3669 assert(naggrvars != NULL);
3670 assert(nchgcoefs != NULL);
3671 assert(ndelconss != NULL);
3672 assert(cutoff != NULL);
3673
3674 if( !SCIPconsIsActive(cons) )
3675 return SCIP_OKAY;
3676
3677 consdata = SCIPconsGetData(cons);
3678 assert(consdata != NULL);
3679
3680 nvars = consdata->nvars;
3681
3682 if( nvars == 0 )
3683 return SCIP_OKAY;
3684
3685 vars = consdata->vars;
3686 assert(vars != NULL);
3687
3688 oldnfixedzeros = consdata->nfixedzeros;
3689 overlapdestroyed = FALSE;
3690
3691 /* first check for redundancy for all unprocessed constraints with cons */
3692 for( c = endidx - 1; c >= 0; --c )
3693 {
3694 cons1 = usefulconss[c];
3695
3696 if( !SCIPconsIsActive(cons1) )
3697 continue;
3698
3699 /* avoid checking constraint against itself */
3700 if( considx == c )
3701 continue;
3702
3703 assert(usefulconss[c] != cons);
3704
3705#ifndef NDEBUG
3706 oldnaggrvars = *naggrvars;
3707#endif
3708
3709 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3710 * possible
3711 */
3712 SCIP_CALL( presolvePropagateCons(scip, cons1, FALSE, undoneaggrvars, undoneaggrtypes, naggregations, saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
3713
3714 if( *cutoff )
3715 return SCIP_OKAY;
3716
3717 /* we can't handle aggregated variables later on so we should have saved them for later */
3718 assert(*naggrvars == oldnaggrvars);
3719
3720 if( !SCIPconsIsActive(cons1) )
3721 continue;
3722
3723 consdata1 = SCIPconsGetData(cons1);
3724 assert(consdata1 != NULL);
3725
3726 nvars1 = consdata1->nvars;
3727
3728 if( nvars1 == 0 )
3729 continue;
3730
3731 /* no more variables from cons as nvars1 can overlap */
3732 assert(countofoverlapping[c] <= nvars1);
3733
3734 /* constraint should not be redundant or infeasible */
3735 assert(consdata1->nfixedones == 0);
3736
3737 SCIPdebugMsg(scip, "constraint <%s> overlaps with constraint <%s> by %d variables\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), countofoverlapping[c]);
3738
3739 /* cons1 includes cons */
3740 if( !overlapdestroyed && countofoverlapping[c] == nvars - consdata->nfixedzeros )
3741 {
3742 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
3743 {
3744 if( nvars - consdata->nfixedzeros < nvars1 )
3745 {
3746#ifndef NDEBUG
3747 SCIP_Bool negated0;
3748 SCIP_Bool negated1;
3749#endif
3750
3751 /* both constraints should stay merged */
3752 assert(consdata->merged);
3753 assert(consdata1->merged);
3754
3755 vars1 = consdata1->vars;
3756 assert(vars1 != NULL);
3757
3758 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3759 SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
3760 /* standard setppc-sorting now lost */
3761 consdata1->sorted = FALSE;
3762
3763 /* iterate over the both cliques variables the "same" time */
3764 for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
3765 {
3766 if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
3767 {
3768 --v1;
3769 continue;
3770 }
3771 if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
3772 {
3773 --v;
3774 continue;
3775 }
3776
3777 /* all variables inside the second clique constraint should be either active or negated of an active one */
3778 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3779
3780 /* get not negated variable and clique value in cons */
3782 {
3783 var = vars[v];
3784#ifndef NDEBUG
3785 negated0 = FALSE;
3786#endif
3787 }
3788 else
3789 {
3790 var = SCIPvarGetNegationVar(vars[v]);
3791#ifndef NDEBUG
3792 negated0 = TRUE;
3793#endif
3794 }
3795
3796 /* get active variable and clique value of next variable */
3797 if( SCIPvarIsActive(vars1[v1]) )
3798 {
3799 var1 = vars1[v1];
3800#ifndef NDEBUG
3801 negated1 = FALSE;
3802#endif
3803 }
3804 else
3805 {
3807 var1 = SCIPvarGetNegationVar(vars1[v1]);
3808#ifndef NDEBUG
3809 negated1 = TRUE;
3810#endif
3811 }
3812
3813 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3814 if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
3815 --v;
3816 /* variable index in the constraint is greater than the other one, so fix this variable */
3817 else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
3818 {
3819 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3820
3821 /* fix all variables except the one which has the negated var in the clique to zero */
3822 SCIP_CALL( SCIPfixVar(scip, vars1[v1], 0.0, cutoff, &fixed) );
3823 if( *cutoff )
3824 {
3825 SCIPdebugMsg(scip, "fixing led to cutoff\n");
3826
3827 return SCIP_OKAY;
3828 }
3829
3830 assert(fixed);
3831 ++(*nfixedvars);
3832 --v1;
3833 }
3834 else
3835 {
3836 /* because the constraint's are merged it is not possible that one constraint contains a negated
3837 * variable of another and because all variables in cons are in cons1 this should be really the
3838 * same variable here; so we can decrease v and v1
3839 */
3840 assert(negated0 == negated1);
3841
3842 --v;
3843 --v1;
3844 }
3845 }
3846 /* maybe we ended because of cons(v reached -1) so try to add rest of cons1 to cons */
3847 for( ; v1 >= 0; --v1)
3848 {
3849 if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
3850 continue;
3851
3852 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3853
3854 /* fix all variables except the one which has the negated var in the clique to zero */
3855 SCIP_CALL( SCIPfixVar(scip, vars1[v1], 0.0, cutoff, &fixed) );
3856 if( *cutoff )
3857 {
3858 SCIPdebugMsg(scip, "fixing led to cutoff\n");
3859
3860 return SCIP_OKAY;
3861 }
3862
3863 assert(fixed);
3864 ++(*nfixedvars);
3865 }
3866 }
3867
3868 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3869 * fixed to one, it's infeasible */
3870 if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nfixedzeros == nvars1 && consdata1->nfixedones != 1 ) /*lint !e641*/
3871 {
3872 SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3873 *cutoff = TRUE;
3874
3875 return SCIP_OKAY;
3876 }
3877
3878 assert(SCIPconsIsActive(cons1));
3879 /* delete second constraint */
3880 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3881
3882 SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
3883 SCIP_CALL( SCIPdelCons(scip, cons1) );
3884 ++(*ndelconss);
3885 }
3886 /* could already be deleted because the constraint was included in another set partition constraint */
3887 else if( SCIPconsIsActive(cons) )
3888 {
3889 /* delete cons due to redundancy to cons1 */
3890 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3891
3892 SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
3893 SCIP_CALL( SCIPdelCons(scip, cons) );
3894 ++(*ndelconss);
3895 }
3896 }
3897 /* cons includes cons1
3898 *
3899 * @note that zero fixations from above can only appear through a set-partitioning constraint, this means if
3900 * cons was the set-partitioning constraint only variables which are not in this constraint could be fixed
3901 * to zero, and this also means that the overlapping variables in this particular case are still active or
3902 * fixed to 1
3903 * later on it could be possible that even variables in cons are fixed to zero, which can lead to wrong
3904 * results when checking if countofoverlapping[c] + consdata1->nfixedzeros == nvars1, because a fixed
3905 * variable could be counted twice
3906 */
3907 else if( (!overlapdestroyed && countofoverlapping[c] + consdata1->nfixedzeros == nvars1) || countofoverlapping[c] == nvars1 )
3908 {
3909 /* even in deleted constraints we may fix unfixed variables */
3910 if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
3911 {
3912 const int oldnfixedvars = *nfixedvars;
3913#ifndef NDEBUG
3914 SCIP_Bool negated0;
3915 SCIP_Bool negated1;
3916#endif
3917 /* both constraints should stay merged */
3918 assert(consdata->merged);
3919 assert(consdata1->merged);
3920
3921 vars1 = consdata1->vars;
3922
3923 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3924 SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
3925 /* standard setppc-sorting now lost */
3926 consdata1->sorted = FALSE;
3927
3928 /* iterate over the both cliques variables the "same" time */
3929 for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
3930 {
3931 if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
3932 {
3933 --v1;
3934 continue;
3935 }
3936 if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
3937 {
3938 --v;
3939 continue;
3940 }
3941
3942 /* all variables inside the second clique constraint should be either active or negated of an active one */
3943 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3944 /* all variables inside the first clique constraint should be either active or negated of an active one */
3946
3947 /* get not negated variable and clique value in cons */
3948 if( SCIPvarIsActive(vars[v]) )
3949 {
3950 var = vars[v];
3951#ifndef NDEBUG
3952 negated0 = FALSE;
3953#endif
3954 }
3955 else
3956 {
3958 var = SCIPvarGetNegationVar(vars[v]);
3959#ifndef NDEBUG
3960 negated0 = TRUE;
3961#endif
3962 }
3963
3964 /* get active variable and clique value of next variable */
3965 if( SCIPvarIsActive(vars1[v1]) )
3966 {
3967 var1 = vars1[v1];
3968#ifndef NDEBUG
3969 negated1 = FALSE;
3970#endif
3971 }
3972 else
3973 {
3975 var1 = SCIPvarGetNegationVar(vars1[v1]);
3976#ifndef NDEBUG
3977 negated1 = TRUE;
3978#endif
3979 }
3980
3981 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3982 if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
3983 {
3984 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(var));
3985
3986 /* fix all variables except the one which has the negated var in the clique to zero */
3987 SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
3988 if( *cutoff )
3989 {
3990 SCIPdebugMsg(scip, "fixing led to cutoff\n");
3991
3992 return SCIP_OKAY;
3993 }
3994
3995 assert(fixed);
3996 ++(*nfixedvars);
3997
3998 --v;
3999 }
4000 /* variable index in the constraint is greater than the other one, so fix this variable */
4001 else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4002 --v1;
4003 else
4004 {
4005 /* because the constraint's are merged it is not possible that one constraint contains a negated
4006 * variable of another and because all variables in cons1 are in cons this should be really the same
4007 * variable here; so we can decrease v and v1
4008 */
4009 assert(negated0 == negated1);
4010
4011 --v;
4012 --v1;
4013 }
4014 }
4015
4016 /* maybe we ended because of cons1(v1 reached -1) so try to add rest of cons to cons1 */
4017 for( ; v >= 0; --v)
4018 {
4019 if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
4020 continue;
4021
4022 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars[v]));
4023
4024 /* fix all variables except the one which has the negated var in the clique to zero */
4025 SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
4026 if( *cutoff )
4027 {
4028 SCIPdebugMsg(scip, "fixing led to cutoff\n");
4029
4030 return SCIP_OKAY;
4031 }
4032
4033 assert(fixed);
4034 ++(*nfixedvars);
4035 }
4036
4037 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
4038 * fixed to one, it's infeasible */
4039 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros == nvars && consdata->nfixedones != 1 ) /*lint !e641*/
4040 {
4041 SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
4042 *cutoff = TRUE;
4043
4044 return SCIP_OKAY;
4045 }
4046
4047 /* could already be deleted because the constraint was included in another set partition constraint */
4048 if( SCIPconsIsActive(cons) )
4049 {
4050 /* delete cons because it include another set partitioning constraint */
4051 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
4052 assert(SCIPconsIsActive(cons));
4053
4054 SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
4055 SCIP_CALL( SCIPdelCons(scip, cons) );
4056 ++(*ndelconss);
4057 }
4058
4059 /* due to fixings in cons0 mark overlapping invalid for checking with fixedzero variables together */
4060 if( oldnfixedvars < *nfixedvars )
4061 overlapdestroyed = TRUE;
4062 }
4063 else
4064 {
4065 assert(consdata1->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
4066
4067 /* delete cons1 due to redundancy to cons */
4068 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
4069 assert(SCIPconsIsActive(cons1));
4070
4071 SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
4072 SCIP_CALL( SCIPdelCons(scip, cons1) );
4073 ++(*ndelconss);
4074 }
4075 }
4076 /* if cons has only one unfixed variable which is not in cons1 and cons1 has one variable which does not appear in
4077 * cons and both constraints are setpartitioning constraints we might aggregate both not overlapping variables and
4078 * delete one constraint
4079 */
4080 else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1 && countofoverlapping[c] == nvars1 - 1 ) /*lint !e641*/
4081 {
4082 SCIP_VAR* aggvar1;
4083 SCIP_VAR* aggvar2;
4084 SCIP_Bool negated0;
4085 SCIP_Bool negated1;
4086
4087 aggvar1 = NULL;
4088 aggvar2 = NULL;
4089
4090 /* both constraints should stay merged */
4091 assert(consdata->merged);
4092 assert(consdata1->merged);
4093
4094 vars1 = consdata1->vars;
4095
4096 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4097 SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
4098 /* standard setppc-sorting now lost */
4099 consdata1->sorted = FALSE;
4100
4101 /* iterate over the both cliques variables the "same" time */
4102 for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
4103 {
4104 if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
4105 {
4106 --v1;
4107 continue;
4108 }
4109 if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
4110 {
4111 --v;
4112 continue;
4113 }
4114
4115 /* all variables inside the second clique constraint should be either active or negated of an active one */
4116 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
4117 /* all variables inside the first clique constraint should be either active or negated of an active one */
4119
4120 /* get not negated variable and clique value in cons */
4121 if( SCIPvarIsActive(vars[v]) )
4122 {
4123 var = vars[v];
4124 negated0 = FALSE;
4125 }
4126 else
4127 {
4129 var = SCIPvarGetNegationVar(vars[v]);
4130 negated0 = TRUE;
4131 }
4132
4133 /* get active variable and clique value of next variable */
4134 if( SCIPvarIsActive(vars1[v1]) )
4135 {
4136 var1 = vars1[v1];
4137 negated1 = FALSE;
4138 }
4139 else
4140 {
4142 var1 = SCIPvarGetNegationVar(vars1[v1]);
4143 negated1 = TRUE;
4144 }
4145
4146 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4147 if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
4148 {
4149 assert(aggvar1 == NULL);
4150 aggvar1 = vars[v];
4151
4152 if( aggvar2 != NULL )
4153 break;
4154
4155 --v;
4156 }
4157 /* variable index in the constraint is greater than the other one, so fix this variable */
4158 else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4159 {
4160 assert(aggvar2 == NULL);
4161 aggvar2 = vars1[v1];
4162
4163 if( aggvar1 != NULL )
4164 break;
4165
4166 --v1;
4167 }
4168 else
4169 {
4170 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4171 * of another, but both variables in both constraints still can be negated to each other
4172 */
4173 if( negated0 != negated1 )
4174 {
4175 /* cons is except for one variable equal to cons1 and the unequal variable in cons is negated
4176 * to the one in cons1, so the problem is infeasible
4177 */
4178 SCIPdebugMsg(scip, "two set-partitioning constraint <%s> and <%s> have only one variable not in common, but this variable <%s> appears in one constraint as the negated version as in the other constraint\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), SCIPvarGetName(vars[v]));
4179 *cutoff = TRUE;
4180
4181 return SCIP_OKAY;
4182 }
4183 --v;
4184 --v1;
4185 }
4186 }
4187
4188 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4189 if( aggvar1 == NULL && aggvar2 == NULL )
4190 continue;
4191
4192 /* determine second aggregation var, if not yet done */
4193 if( aggvar2 == NULL )
4194 {
4195 for( ; v1 >= 0; --v1)
4196 {
4197 if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
4198 continue;
4199
4200 aggvar2 = vars1[v1];
4201 break;
4202 }
4203 }
4204 /* determine first aggregation var, if not yet done */
4205 else if( aggvar1 == NULL )
4206 {
4207 /* maybe we ended because of cons1(v1 reached -1) so find the aggvar1 in cons */
4208 for( ; v >= 0; --v)
4209 {
4210 if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
4211 continue;
4212
4213 aggvar1 = vars[v];
4214 break;
4215 }
4216 }
4217
4218 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4219 if( aggvar1 == NULL || aggvar2 == NULL )
4220 continue;
4221
4222 SCIPdebugMsg(scip, "memorize the aggregation of <%s> == <%s>, because they are the last two variable which are different in these two set partitioning constraints <%s> <%s>\n", SCIPvarGetName(aggvar1), SCIPvarGetName(aggvar2), SCIPconsGetName(cons), SCIPconsGetName(cons1));
4223
4224 /* resize the aggregation arrays if necessary */
4225 if( *saggregations == *naggregations )
4226 {
4227 *saggregations = SCIPcalcMemGrowSize(scip, *naggregations + 1);
4228 assert(*saggregations > *naggregations);
4229 SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrtypes, *saggregations) );
4230 SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrvars, 2 * (*saggregations)) );
4231
4232 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
4233 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
4234 }
4235
4236 /* memorize aggregation variables*/
4237 undoneaggrtypes[*naggregations] = TRUE;
4238 undoneaggrvars[2 * (*naggregations)] = aggvar1;
4239 undoneaggrvars[2 * (*naggregations) + 1] = aggvar2;
4240 ++(*naggregations);
4241
4242 if( !SCIPdoNotAggr(scip) )
4243 {
4244 /* delete constraint */
4245 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it is dominated by constraint <%s>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons));
4246 assert(SCIPconsIsActive(cons1));
4247
4248 SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
4249 SCIP_CALL( SCIPdelCons(scip, cons1) );
4250 ++(*ndelconss);
4251 }
4252 }
4253 /* w.l.o.g. cons is a setpartitioning constraint and countofoverlapping == nvars - oldnfixedzeros - 1 we can
4254 * delete all overlapping variables in cons1 and add the negated variable of the not overlapped variable to cons
4255 * 1; the result should be a shorter constraint with the same impact
4256 */
4257 else if( shrinking && !overlapdestroyed && countofoverlapping[c] > 1 && ((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars1 - 1)) ) /*lint !e641*/
4258 {
4259 SCIP_CONSDATA* consdatachange;
4260 SCIP_VAR** varstostay;
4261 SCIP_VAR** varstochange;
4262 SCIP_CONS* constochange;
4263 SCIP_CONS* constostay;
4264 SCIP_VAR* addvar;
4265 SCIP_Bool negated0;
4266 SCIP_Bool negated1;
4267 int nvarstostay;
4268 int nvarstochange;
4269 int constochangeidx;
4270#ifndef NDEBUG
4271 const int oldnchgcoefs = *nchgcoefs;
4272#endif
4273
4274 addvar = NULL;
4275
4276 assert((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING) != (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING) || countofoverlapping[c] != nvars - 1 || countofoverlapping[c] != nvars1 - 1); /*lint !e641*/
4277
4278 /* both constraints should stay merged */
4279 assert(consdata->merged);
4280 assert(consdata1->merged);
4281
4282 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4283 SCIPsortDownPtr((void**)(consdata1->vars), SCIPvarCompActiveAndNegated, nvars1);
4284 /* standard setppc-sorting now lost */
4285 consdata1->sorted = FALSE;
4286
4287 /* initialize variables */
4288 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) /*lint !e641*/
4289 {
4290 varstostay = vars;
4291 varstochange = consdata1->vars;
4292 nvarstostay = nvars;
4293 nvarstochange = nvars1;
4294 constostay = cons;
4295 constochange = cons1;
4296 consdatachange = consdata1;
4297 constochangeidx = c;
4298 }
4299 else
4300 {
4301 varstostay = consdata1->vars;
4302 varstochange = vars;
4303 nvarstostay = nvars1;
4304 nvarstochange = nvars;
4305 constostay = cons1;
4306 constochange = cons;
4307 consdatachange = consdata;
4308 constochangeidx = considx;
4309
4310 *chgcons = TRUE;
4311 }
4312
4313 /* iterate over the both cliques variables the "same" time, here we need the backward loop, because we
4314 * delete some variables and we don not want to loose order
4315 */
4316 for( v = nvarstostay - 1, v1 = nvarstochange - 1; v >= 0 && v1 >= 0; )
4317 {
4318 if( SCIPvarGetLbLocal(varstochange[v1]) > 0.5 || SCIPvarGetUbLocal(varstochange[v1]) < 0.5 )
4319 {
4320 --v1;
4321 continue;
4322 }
4323 if( SCIPvarGetLbLocal(varstostay[v]) > 0.5 || SCIPvarGetUbLocal(varstostay[v]) < 0.5 )
4324 {
4325 --v;
4326 continue;
4327 }
4328
4329 /* all variables inside the second clique constraint should be either active or negated of an active one */
4330 assert(SCIPvarIsActive(varstochange[v1]) || (SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1]))));
4331 /* all variables inside the first clique constraint should be either active or negated of an active one */
4332 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4333
4334 /* get not negated variable and clique value in constostay */
4335 if( SCIPvarIsActive(varstostay[v]) )
4336 {
4337 var = varstostay[v];
4338 negated0 = FALSE;
4339 }
4340 else
4341 {
4342 assert(SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v])));
4343 var = SCIPvarGetNegationVar(varstostay[v]);
4344 negated0 = TRUE;
4345 }
4346
4347 /* get active variable and clique value of in constochange*/
4348 if( SCIPvarIsActive(varstochange[v1]) )
4349 {
4350 var1 = varstochange[v1];
4351 negated1 = FALSE;
4352 }
4353 else
4354 {
4355 assert(SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1])));
4356 var1 = SCIPvarGetNegationVar(varstochange[v1]);
4357 negated1 = TRUE;
4358 }
4359
4360 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4361 if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
4362 {
4363 assert(addvar == NULL);
4364 addvar = varstostay[v];
4365 --v;
4366 }
4367 /* variable index in the constraint is greater than the other one, so fix this variable */
4368 else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4369 {
4370 --v1;
4371 }
4372 else
4373 {
4374 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4375 * of another, but both constraint might have a variable in negated form of the other
4376 */
4377 if( negated0 != negated1 )
4378 {
4379 assert(addvar == NULL);
4380
4381 SCIPdebugMsg(scip, "-> trying to fix <%s> to 0 because it would exist twice in a constraint\n", SCIPvarGetName(varstochange[v1]));
4382
4383 /* fix variable to zero */
4384 SCIP_CALL( SCIPfixVar(scip, varstochange[v1], 0.0, cutoff, &fixed) );
4385 if( *cutoff )
4386 {
4387 SCIPdebugMsg(scip, "fixing led to cutoff\n");
4388
4389 return SCIP_OKAY;
4390 }
4391
4392 assert(fixed);
4393 ++(*nfixedvars);
4394
4395 /* the above fixing is equal to the fixation of varstostay[v] to 1, so we can call presolvePropagateCons() for consstay */
4396 SCIP_CALL( presolvePropagateCons(scip, constostay, FALSE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, cutoff) );
4397
4398 return SCIP_OKAY;
4399 }
4400 else
4401 {
4402 /* correct local data structure, remove variable from constraint entry where it will be removed */
4403 deleteCliqueDataEntry(varstochange[v1], constochangeidx, vartoindex, varnconss, varconsidxs);
4404
4405 SCIPdebugMsg(scip, " -> deleting variable <%s> in constraint <%s> number %d, because it will be replaced\n", SCIPvarGetName(varstochange[v1]), SCIPconsGetName(constochange), constochangeidx);
4406 /* delete overlapping variables in constochange */
4407 SCIP_CALL( delCoefPos(scip, constochange, v1) );
4408 ++(*nchgcoefs);
4409 }
4410
4411 --v;
4412 --v1;
4413 }
4414 }
4415 assert(addvar != NULL || v >= 0);
4416 /* we should have removed exactly countofoverlapping[c] variables from the constochange */
4417 assert(*nchgcoefs - oldnchgcoefs == countofoverlapping[c]);
4418
4419 /* determine addvar if not yet found */
4420 if( addvar == NULL )
4421 {
4422 for( ; v >= 0; --v)
4423 {
4424 if( SCIPvarGetLbLocal(varstostay[v]) > 0.5 || SCIPvarGetUbLocal(varstostay[v]) < 0.5 )
4425 continue;
4426
4427 /* all variables inside the first clique constraint should be either active or negated of an active one */
4428 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4429
4430 addvar = varstostay[v];
4431 break;
4432 }
4433 }
4434 assert(addvar != NULL);
4435
4436 /* get representative variable for all deleted variables */
4437 SCIP_CALL( SCIPgetNegatedVar(scip, addvar, &addvar) );
4438 assert(addvar != NULL);
4439
4440 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(constochange), constochangeidx);
4441 /* add representative for overlapping instead */
4442 SCIP_CALL( addCoef(scip, constochange, addvar) );
4443 ++(*nchgcoefs);
4444
4445 /* constraint should be still merged because this added variable is new in this constraint */
4446 consdatachange->merged = TRUE;
4447 assert(constochangeidx == (cons == constochange ? considx : c));
4448
4449 /* correct local data structure, add constraint entry to variable data */
4450 SCIP_CALL( addCliqueDataEntry(scip, addvar, constochangeidx, TRUE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4451
4452 /* cons changed so much, that it cannot be used for more overlapping checks */
4453 if( *chgcons )
4454 return SCIP_OKAY;
4455 }
4456 }
4457
4458 return SCIP_OKAY;
4459}
4460
4461/** try to lift variables to given constraint */
4462/** @todo try another variant by determine lifting variables as the intersection of all cliques variables of the
4463 * constraint variables, note that the intersection changes after one variable was added
4464 */
4465static
4467 SCIP*const scip, /**< SCIP data structure */
4468 SCIP_CONS*const cons, /**< constraint which may overlap */
4469 int const arraypos, /**< position of constraint in global array */
4470 SCIP_VAR**const usefulvars, /**< possible variables to lift */
4471 int*const nusefulvars, /**< pointer to store number of added variables */
4472 int const endidx, /**< end index for possible lifting variables */
4473 SCIP_Bool** cliquevalues, /**< pointer to clique values of constraint-variables, either one if the
4474 * variable is active or zero if the variable is negated
4475 * @note this array can be resized in this method
4476 */
4477 SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
4478 int*const varnconss, /**< array with number of constraints a variable occurs */
4479 int*const maxnvarconsidx, /**< array with the maximal number of occurrences of a variable */
4480 int**const varconsidxs, /**< array with constraint indices in which the corresponding variable
4481 * exists
4482 */
4483 int*const maxnvars, /**< pointer to store maximal number of variables of a constraint */
4484 int*const nadded, /**< pointer to store number of possible added variables */
4485 SCIP_Bool*const chgcons, /**< pointer to store if the constraint was changed, due to added
4486 * variables
4487 */
4488 int*const nfixedvars, /**< pointer to count number of deleted variables */
4489 int*const ndelconss, /**< pointer to count number of deleted constraints */
4490 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
4491 )
4492{
4493 SCIP_CONSDATA* consdata;
4494 SCIP_VAR** vars;
4495 SCIP_VAR* var;
4496 SCIP_VAR* var1;
4497 SCIP_Bool fixed;
4498 SCIP_Bool value;
4499 int nvars;
4500 int nottocheck; /* will be the position for a variable in cons0 which is in negated form in the same clique */
4501 int v;
4502 int v1;
4503 int k;
4504
4505 assert(scip != NULL);
4506 assert(cons != NULL);
4507 assert(usefulvars != NULL);
4508 assert(cliquevalues != NULL);
4509 assert(*cliquevalues != NULL);
4510 assert(vartoindex != NULL);
4511 assert(varnconss != NULL);
4512 assert(maxnvarconsidx != NULL);
4513 assert(varconsidxs != NULL);
4514 assert(maxnvars != NULL);
4515 assert(nadded != NULL);
4516 assert(chgcons != NULL);
4517 assert(nfixedvars != NULL);
4518 assert(ndelconss != NULL);
4519 assert(cutoff != NULL);
4520
4521 if( !SCIPconsIsActive(cons) )
4522 return SCIP_OKAY;
4523
4524 consdata = SCIPconsGetData(cons);
4525 assert(consdata != NULL);
4526
4527 nvars = consdata->nvars;
4528
4529 if( nvars == 0 )
4530 return SCIP_OKAY;
4531
4532 assert(nvars <= *maxnvars);
4533
4534 vars = consdata->vars;
4535 assert(vars != NULL);
4536
4537 v1 = endidx;
4538
4539 /* now we try to add variables with index prior to endidx to cons */
4540 for( v = nvars - 1; v >= 0 && v1 >= 0; )
4541 {
4542 if( SCIPvarGetLbLocal(usefulvars[v1]) > 0.5 || SCIPvarGetUbLocal(usefulvars[v1]) < 0.5 )
4543 {
4544 --v1;
4545 continue;
4546 }
4547 if( SCIPvarGetUbLocal(vars[v]) < 0.5 )
4548 {
4549 --v;
4550 continue;
4551 }
4552
4553 /* check that constraint variables are still correctly sorted, indices of active variables should be decreasing */
4554 assert(v == 0 || SCIPvarCompareActiveAndNegated(vars[v], vars[v - 1]) <= 0);
4555
4556 /* there should no variables fixed to one occur in our constraint */
4557 assert(SCIPvarGetLbLocal(vars[v]) < 0.5 && SCIPvarGetUbLocal(vars[v]) > 0.5);
4558 assert(SCIPvarGetLbLocal(usefulvars[v1]) < 0.5 && SCIPvarGetUbLocal(usefulvars[v1]) > 0.5);
4559
4560 /* all variables which we have inside the clique constraint and which can possibly be added should be either active or negated */
4562 assert(SCIPvarIsActive(usefulvars[v1]) || (SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1]))));
4563
4564 /* constraint should during adding of variables stay merged, because for each variable which is added holds that
4565 * the index of this corresponding active variable is pairwise different to all indices of all active
4566 * corresponding variables inside the constraint
4567 * @note it should not happen that we add one variable and the corresponding counterpart to the same constraint */
4568 assert(consdata->merged);
4569
4570 /* get active variable and clique value in cons */
4571 if( (*cliquevalues)[v] )
4572 var = vars[v];
4573 else
4574 {
4576 var = SCIPvarGetNegationVar(vars[v]);
4577 }
4578
4579 /* get active variable and clique value of next variable */
4580 if( SCIPvarIsActive(usefulvars[v1]) )
4581 {
4582 var1 = usefulvars[v1];
4583 value = TRUE;
4584 }
4585 else
4586 {
4587 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4588 var1 = SCIPvarGetNegationVar(usefulvars[v1]);
4589 value = FALSE;
4590 }
4591
4592 nottocheck = -1;
4593 k = 0;
4594
4595 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4596 if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
4597 {
4598 --v;
4599 continue;
4600 }
4601 /* variable index in the constraint is greater than the other one, so check for possible inclusion of the variable */
4602 else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4603 {
4604 assert(consdata == SCIPconsGetData(cons));
4605
4606 /* check if every variable in the actual clique is in clique with the new variable */
4607 for( k = nvars - 1; k >= 0; --k )
4608 {
4609 if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4610 {
4611 /* there should no variables fixed to one occur in our constraint */
4612 assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
4614
4615 if( (*cliquevalues)[k] )
4616 {
4617 assert(SCIPvarIsActive(vars[k]));
4618 var = vars[k];
4619 }
4620 else
4621 {
4623 var = SCIPvarGetNegationVar(vars[k]);
4624 }
4625 if( !SCIPhaveVarsCommonClique(scip, var1, value, var, (*cliquevalues)[k], TRUE) )
4626 break;
4627 }
4628 }
4629 --v1;
4630 }
4631 /* variable index in the constraint is equal to the index of the other variable, check if these variables are
4632 * negated of each other so memorize the position and check for possible inclusion of the new variable and if
4633 * possible decrease indices
4634 */
4635 else
4636 {
4637 /* one clique contains the negated and the other clique the corresponding active var */
4638 if( value != (*cliquevalues)[v] )
4639 {
4640 nottocheck = v;
4641
4642 assert(consdata == SCIPconsGetData(cons));
4643 assert(nvars <= consdata->nvars);
4644
4645 /* check if every variable in the actual clique is in clique with the new variable */
4646 for( k = nvars - 1; k >= 0; --k )
4647 {
4648 if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4649 {
4650 /* there should no variables fixed to one occur in our constraint */
4651 assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
4652
4654
4655 if( k == nottocheck )
4656 continue;
4657
4658 if( (*cliquevalues)[k] )
4659 {
4660 assert(SCIPvarIsActive(vars[k]));
4661 var = vars[k];
4662 }
4663 else
4664 {
4666 var = SCIPvarGetNegationVar(vars[k]);
4667 }
4668
4669 if( !SCIPhaveVarsCommonClique(scip, var1, value, var, (*cliquevalues)[k], TRUE) )
4670 break;
4671 }
4672 }
4673 }
4674 /* don't decrease v because it might happen that the corresponding negated variable of var is next in
4675 * usefulvars
4676 */
4677 --v1;
4678 }
4679
4680 /* if k is smaller than 0 than the possible new variables is in the same clique with all variables of cons,
4681 * so we add the new variable to clique constraint or fix some variables */
4682 if( k < 0 )
4683 {
4684 ++(*nadded);
4685
4686 /* we found a variable which is the negated variable of another one in this clique so we can fix all
4687 * other variable to zero and if it's a partitioning constraint we can also fix the variable of the
4688 * negated to one and we can delete the constraint too */
4689 if( nottocheck >= 0 )
4690 {
4691 assert(consdata == SCIPconsGetData(cons));
4692 assert(nvars <= consdata->nvars);
4693 assert(consdata->merged);
4694
4695 /* process all vars for possible fixing */
4696 for( k = consdata->nvars - 1; k >= 0; --k )
4697 {
4698 if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4699 {
4700 /* there should no variables fixed to one occur in our constraint */
4701 assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
4702
4704
4705 if( k != nottocheck )
4706 {
4707 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because we could lift a negated variable of another constraint variable\n", SCIPvarGetName(vars[k]));
4708 /* fix variable to zero */
4709 SCIP_CALL( SCIPfixVar(scip, vars[k], 0.0, cutoff, &fixed) );
4710
4711 if( *cutoff )
4712 {
4713 SCIPdebugMsg(scip, "fixing led to cutoff\n");
4714
4715 return SCIP_OKAY;
4716 }
4717
4718 assert(fixed);
4719
4720 ++(*nfixedvars);
4721 }
4722 }
4723 }
4724 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
4725 {
4726 assert(SCIPvarIsActive(vars[nottocheck]) || (SCIPvarGetStatus(vars[nottocheck]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[nottocheck]))));
4727
4728 SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to this setpartitioning variable is with its negated in the same clique\n", SCIPvarGetName(vars[nottocheck]));
4729 /* fix the remaining variable to one, due to it's the only one left to satisfy the constraint */
4730 SCIP_CALL( SCIPfixVar(scip, vars[nottocheck], 1.0, cutoff, &fixed) );
4731 if( *cutoff )
4732 {
4733 SCIPdebugMsg(scip, "fixing led to cutoff\n");
4734
4735 return SCIP_OKAY;
4736 }
4737
4738 assert(fixed);
4739 ++(*nfixedvars);
4740 }
4741
4742 /* delete constraint */
4743 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to active and negated variable in the same clique constraint\n", SCIPconsGetName(cons), arraypos);
4744 assert(SCIPconsIsActive(cons));
4745 SCIP_CALL( SCIPdelCons(scip, cons) );
4746 ++(*ndelconss);
4747
4748 break;
4749 }
4750 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4751 else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
4752 {
4753 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1 + 1]));
4754 /* fix variable to zero */
4755 SCIP_CALL( SCIPfixVar(scip, usefulvars[v1 + 1], 0.0, cutoff, &fixed) );
4756
4757 if( *cutoff )
4758 {
4759 SCIPdebugMsg(scip, "fixing led to cutoff\n");
4760
4761 return SCIP_OKAY;
4762 }
4763
4764 assert(fixed);
4765
4766 ++(*nfixedvars);
4767 }
4768 /* we have found a new variable for a set packing constraint cons, so add the found variable to the first constraint */
4769 else
4770 {
4771 SCIP_VAR* addvar;
4772
4773 assert(SCIPconsIsActive(cons));
4774
4775 addvar = usefulvars[v1 + 1];
4776
4777 assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
4778
4779 /* add representative instead */
4780 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(usefulvars[v1 + 1]), SCIPconsGetName(cons), arraypos);
4781 SCIP_CALL( addCoef(scip, cons, addvar) );
4782 assert(consdata == SCIPconsGetData(cons));
4783 /* we know that this constraint stays merged but later on we have to resort */
4784 consdata->merged = TRUE;
4785
4786 /* second we add the constraint index to the list of indices where this variable occurs */
4787 assert(SCIPhashmapExists(vartoindex, (void*) addvar));
4788
4789 /* correct local data structure, add constraint entry to variable data */
4790 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4791
4792 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4793 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4794 * added variable was inserted at the end and we are decreasing v in our for loop
4795 */
4796 vars = consdata->vars;
4797 nvars = consdata->nvars;
4798
4799 /* we need to update our data structure */
4800
4801 /* resize clique array if necessary, due to adding variables */
4802 if( (*maxnvars) < nvars )
4803 {
4804 while( (*maxnvars) < nvars )
4805 (*maxnvars) *= 2 ;
4806 SCIP_CALL( SCIPreallocBufferArray(scip, cliquevalues, (*maxnvars)) );
4807 }
4808 (*cliquevalues)[nvars - 1] = SCIPvarIsActive(addvar) ? TRUE : FALSE;
4809
4810 (*chgcons) = TRUE;
4811 }
4812 }
4813 }
4814
4815 if( !SCIPconsIsActive(cons) )
4816 return SCIP_OKAY;
4817
4818 /* maybe we stopped because of cons(v reached -1) so try to add rest in usefulvars */
4819 for( ; v1 >= 0; --v1)
4820 {
4821 if( SCIPvarGetLbLocal(usefulvars[v1]) > 0.5 || SCIPvarGetUbLocal(usefulvars[v1]) < 0.5 )
4822 continue;
4823
4824 /* get active variable and clique value */
4825 if( SCIPvarIsActive(usefulvars[v1]) )
4826 {
4827 var1 = usefulvars[v1];
4828 value = TRUE;
4829 }
4830 else
4831 {
4832 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4833 var1 = SCIPvarGetNegationVar(usefulvars[v1]);
4834 value = FALSE;
4835 }
4836
4837 assert(consdata == SCIPconsGetData(cons));
4838 assert(nvars <= consdata->nvars);
4839
4840 /* check if every variable in the actual clique is in clique with the new variable */
4841 for( k = nvars - 1; k >= 0; --k )
4842 {
4843 if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4844 {
4845 /* there should no variables fixed to one occur in our constraint */
4846 assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
4847
4849
4850 if( (*cliquevalues)[k] )
4851 {
4852 assert(SCIPvarIsActive(vars[k]));
4853 var = vars[k];
4854 }
4855 else
4856 {
4858 var = SCIPvarGetNegationVar(vars[k]);
4859 }
4860
4861 if( !SCIPvarsHaveCommonClique(var1, value, var, (*cliquevalues)[k], TRUE) )
4862 break;
4863 }
4864 }
4865
4866 /* add new variable to clique constraint or fix some variables */
4867 if( k < 0 )
4868 {
4869 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4870 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
4871 {
4872 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1]));
4873
4874 /* fix variable to zero */
4875 SCIP_CALL( SCIPfixVar(scip, usefulvars[v1], 0.0, cutoff, &fixed) );
4876 if( *cutoff )
4877 {
4878 SCIPdebugMsg(scip, "fixing led to cutoff\n");
4879
4880 return SCIP_OKAY;
4881 }
4882 assert(fixed);
4883
4884 ++(*nfixedvars);
4885 ++(*nadded);
4886 }
4887 /* add the found variable to the first constraint */
4888 else
4889 {
4890 SCIP_VAR* addvar;
4891
4892 assert(SCIPconsIsActive(cons));
4893
4894 addvar = usefulvars[v1];
4895
4896 assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
4897
4898 /* add representative instead */
4899 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(cons), arraypos);
4900 SCIP_CALL( addCoef(scip, cons, addvar) );
4901 assert(consdata == SCIPconsGetData(cons));
4902 /* we know that this constraint stays merged but later on we have to resort */
4903 consdata->merged = TRUE;
4904
4905 /* second we add the constraint index to the list of indices where this variable occurs */
4906 assert(SCIPhashmapExists(vartoindex, (void*) addvar));
4907
4908 /* correct local data structure, add constraint entry to variable data */
4909 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4910
4911 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4912 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4913 * added variable was inserted at the end and we are decreasing v in our for loop
4914 */
4915 vars = consdata->vars;
4916 nvars = consdata->nvars;
4917
4918 /* we need to update our data structure */
4919
4920 /* resize clique array if necessary, due to adding variables */
4921 if( (*maxnvars) < nvars )
4922 {
4923 while( (*maxnvars) < nvars )
4924 (*maxnvars) *= 2 ;
4925 SCIP_CALL( SCIPreallocBufferArray(scip, cliquevalues, (*maxnvars)) );
4926 }
4927 (*cliquevalues)[nvars - 1] = SCIPvarIsActive(addvar) ? TRUE : FALSE;
4928
4929 ++(*nadded);
4930 (*chgcons) = TRUE;
4931 }
4932 }
4933 }
4934
4935 return SCIP_OKAY;
4936}
4937
4938/** perform all collected aggregations */
4939static
4941 SCIP*const scip, /**< SCIP data structure */
4942 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4943 SCIP_VAR**const undoneaggrvars, /**< aggregation variables storage */
4944 SCIP_Bool*const undoneaggrtypes, /**< aggregation type storage, type FALSE means the aggregation is of the
4945 * form x + y = 1; type TRUE means the aggregation is of the form x = y;
4946 */
4947 int const naggregations, /**< number of aggregations to performed */
4948 int*const naggrvars, /**< pointer to count number of aggregated variables */
4949 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
4950 )
4951{ /*lint --e{715}*/
4952 SCIP_VAR* var1;
4953 SCIP_VAR* var2;
4954 SCIP_Bool aggregated;
4955 SCIP_Bool redundant;
4956 int a;
4957
4958 assert(scip != NULL);
4959 assert(conshdlrdata != NULL);
4960 assert(undoneaggrvars != NULL);
4961 assert(undoneaggrtypes != NULL);
4962 assert(naggregations > 0);
4963 assert(naggrvars != NULL);
4964 assert(cutoff != NULL);
4965
4966 /* loop over all open aggregations and try to aggregate them */
4967 for( a = 0; a < naggregations; ++a )
4968 {
4969 var1 = undoneaggrvars[2 * a];
4970 var2 = undoneaggrvars[2 * a + 1];
4971 assert(var1 != NULL);
4972 assert(var2 != NULL);
4973
4974 SCIPdebugMsg(scip, "trying to aggregate <%s> %s <%s>%s\n", SCIPvarGetName(var1), undoneaggrtypes[a] ? "=" : "+", SCIPvarGetName(var2), undoneaggrtypes[a] ? "" : " = 1");
4975
4976#ifdef VARUSES
4977 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
4978 * and increase usage counting again
4979 */
4980 SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var1) );
4981 SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var2) );
4982#endif
4983
4984 /* aggregate last remaining variables in the set partitioning constraint */
4985 if( undoneaggrtypes[a] )
4986 {
4987 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, -1.0, 0.0, cutoff, &redundant, &aggregated) );
4988 }
4989 else
4990 {
4991 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
4992 }
4993
4994 if( *cutoff )
4995 {
4996 SCIPdebugMsg(scip, "aggregation was infeasible\n");
4997
4998 return SCIP_OKAY;
4999 }
5000 /* binary variables should always be aggregated, or due to fixation the aggregation is redundant */
5001 assert(redundant);
5002
5003 if( aggregated )
5004 ++(*naggrvars);
5005
5006#ifdef VARUSES
5007 /* increase variable usage counting again */
5008 SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var1) );
5009 SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var2) );
5010#endif
5011 }
5012
5013 return SCIP_OKAY;
5014}
5015
5016/** check whether we can combine or grow cliques so some constraints become redundant or we can fix variables */
5017/** @todo try another variant, by building up the clique graph and delete unnecessary (transitive closure) edges and do
5018 * a bfs search to search for common ancestors to get all possible lifting variables
5019 */
5020static
5022 SCIP*const scip, /**< SCIP data structure */
5023 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5024 SCIP_CONS**const conss, /**< constraint set */
5025 int const nconss, /**< number of constraints in constraint set */
5026 int const nrounds, /**< actual presolving round */
5027 int*const firstchange, /**< pointer to store first changed constraint */
5028 int*const firstclique, /**< pointer to store first constraint to start adding clique again */
5029 int*const lastclique, /**< pointer to store last constraint to add cliques again */
5030 int*const nfixedvars, /**< pointer to count number of deleted variables */
5031 int*const naggrvars, /**< pointer to count number of aggregated variables */
5032 int*const ndelconss, /**< pointer to count number of deleted constraints */
5033 int*const nchgcoefs, /**< pointer to count number of deleted coefficients */
5034 SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
5035 )
5036{
5037 /* extend cliques/constraints by checking whether some variables are in the same clique, no pairwise clique lifting
5038 * which would be slower
5039 */
5040 SCIP_CONS** usefulconss; /* array with pointers of constraint of setpartitioning and setpacking type */
5041 SCIP_VAR** usefulvars; /* array with pointers of variables in setpartitioning and setpacking constraints */
5042 int** varconsidxs; /* array consisting of constraint indices in which the corresponding variable exists */
5043 int* varnconss; /* array consisting of number of constraints the variable occurs */
5044 int* maxnvarconsidx; /* maximal number of occurrences of a variable */
5045 int* countofoverlapping = NULL; /* the amount of variables which are in another constraint */
5046 SCIP_Bool* cliquevalues = NULL; /* values of clique-variables, either one if the variable is active or zero if the variable is negated */
5047
5048 SCIP_HASHMAP* vartoindex; /* mapping of SCIP variables to indices */
5049 SCIP_CONSDATA* consdata;
5050
5051 SCIP_Bool chgcons0;
5052 int nvars;
5053 int c;
5054 int v;
5055 int nusefulconss;
5056 int nusefulvars;
5057 int susefulvars;
5058 int maxnvars;
5059 int varindex;
5060
5061 SCIP_VAR** undoneaggrvars; /* storage for not yet performed aggregations */
5062 SCIP_Bool* undoneaggrtypes; /* storage for not yet performed aggregation type (x = y or x + y = 1) */
5063 int saggregations;
5064 int naggregations;
5065
5066 assert(scip != NULL);
5067 assert(conshdlrdata != NULL);
5068 assert(conss != NULL || nconss == 0);
5069 assert(firstchange != NULL);
5070 assert(firstclique != NULL);
5071 assert(lastclique != NULL);
5072 assert(nfixedvars != NULL);
5073 assert(naggrvars != NULL);
5074 assert(ndelconss != NULL);
5075 assert(nchgcoefs != NULL);
5076 assert(cutoff != NULL);
5077
5078 *cutoff = FALSE;
5079
5080 if( nconss == 0 )
5081 return SCIP_OKAY;
5082
5083 nvars = SCIPgetNVars(scip);
5084
5085 if( nvars == 0 )
5086 return SCIP_OKAY;
5087
5088 susefulvars = 2 * nvars; /* two times because of negated vars, maybe due to deleted variables we need to increase this */
5089
5090 /* a hashmap from varindex to postion in varconsidxs array, because above is still too small */
5091 SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), nvars) );
5092
5093 /* get temporary memory for the aggregation storage, to memorize aggregations which will be performed later, otherwise we would destroy our local data structures */
5094 saggregations = nvars;
5095 SCIP_CALL( SCIPallocBufferArray(scip, &undoneaggrvars, 2 * saggregations) );
5096 SCIP_CALL( SCIPallocBufferArray(scip, &undoneaggrtypes, saggregations) );
5097 BMSclearMemoryArray(undoneaggrtypes, saggregations);
5098 naggregations = 0;
5099
5100 /* get temporary memory for all clique constraints, all appearing variables and the mapping from variables to constraints */
5101 SCIP_CALL( SCIPallocBufferArray(scip, &usefulconss, nconss) );
5102 SCIP_CALL( SCIPallocBufferArray(scip, &usefulvars, susefulvars) );
5103 BMSclearMemoryArray(usefulvars, susefulvars);
5104 SCIP_CALL( SCIPallocBufferArray(scip, &varnconss, susefulvars + 1) );
5105 BMSclearMemoryArray(varnconss, susefulvars + 1);
5106 SCIP_CALL( SCIPallocBufferArray(scip, &maxnvarconsidx, susefulvars + 1) );
5107 SCIP_CALL( SCIPallocBufferArray(scip, &varconsidxs, susefulvars + 1) );
5108 BMSclearMemoryArray(varconsidxs, susefulvars + 1);
5109 nusefulvars = 0;
5110 nusefulconss = 0;
5111 maxnvars = 0;
5112
5113 /* @todo: check for round limit for adding extra clique constraints */
5114 /* adding clique constraints which arises from global clique information */
5115 if( conshdlrdata->nclqpresolve == 0 && conshdlrdata->addvariablesascliques )
5116 {
5117 SCIP_VAR** vars = SCIPgetVars(scip);
5118 SCIP_VAR** binvars;
5119 int* cliquepartition;
5120 int ncliques;
5121 int nbinvars;
5122 int naddconss;
5123
5124 nbinvars = SCIPgetNBinVars(scip);
5125 SCIP_CALL( SCIPduplicateBufferArray(scip, &binvars, vars, nbinvars) );
5126 SCIP_CALL( SCIPallocBufferArray(scip, &cliquepartition, nbinvars) );
5127
5128 /* @todo: check for better permutations/don't permute the first round
5129 * @todo: take binary variables which are not of vartype SCIP_VARTYPE_BINARY into account
5130 */
5131 SCIPrandomPermuteArray(conshdlrdata->randnumgen, (void**)binvars, 0, nbinvars);
5132
5133 /* try to create a clique-partition over all binary variables and create these cliques as new setppc constraints
5134 * and add them to the usefulconss array and adjust all necessary data this will hopefully lead to faster
5135 * detection of redundant constraints
5136 */
5137 SCIP_CALL( SCIPcalcCliquePartition(scip, binvars, nbinvars, cliquepartition, &ncliques) );
5138
5139 /* resize usefulconss array if necessary */
5140 SCIP_CALL( SCIPreallocBufferArray(scip, &usefulconss, nconss + ncliques) );
5141
5142 naddconss = 0;
5143
5144 /* add extra clique constraints resulting from the cliquepartition calculation to SCIP and to the local data structure */
5145 SCIP_CALL( addExtraCliques(scip, binvars, nbinvars, cliquepartition, ncliques, usefulconss, &nusefulconss,
5146 nrounds, nfixedvars, &naddconss, ndelconss, nchgcoefs, cutoff) );
5147
5148 /* bad hack, we don't want to count these artificial created constraints if they got deleted, so ndelconss
5149 * can become negative which will be change to zero at the end of this method if it's still negative
5150 */
5151 *ndelconss -= naddconss;
5152
5153 SCIPfreeBufferArray(scip, &cliquepartition);
5154 SCIPfreeBufferArray(scip, &binvars);
5155
5156 if( *cutoff )
5157 goto TERMINATE;
5158 }
5159
5160 /* start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
5161 * constraints
5162 */
5163 SCIP_CALL( collectCliqueConss(scip, conss, nconss, usefulconss, &nusefulconss, nfixedvars, ndelconss, nchgcoefs, cutoff) );
5164 /* @Note: Even after the call above some constraints can have fixed variables, because it might happen that caused by
5165 * mergeMultiplies some variables were fixed which occurred already in previous constraints
5166 */
5167 if( *cutoff )
5168 goto TERMINATE;
5169
5170 /* no usefulconss found */
5171 if( nusefulconss <= 1 )
5172 goto TERMINATE;
5173
5174 /* @todo: maybe sort them after biggest indices too, or another variant would be to restore the order as they were
5175 * read in
5176 */
5177 /* sort constraints first after type (partitioning before packing) and second after number of variables such that the
5178 * partitioning constraints have increasing number of variables and the packing constraints have decreasing number of
5179 * variables, because we loop from back to front we sort them downwards, so they are the other way around
5180 */
5181 SCIPsortDownPtr((void**)usefulconss, setppcConssSort, nusefulconss);
5182
5183 /* creating all necessary data in array structure, collect all clique constraint variables and occurrences */
5184 SCIP_CALL( collectCliqueData(scip, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs, &maxnvars) );
5185 assert(maxnvars > 0);
5186
5187 /* allocate temporary memory for actual clique */
5188 SCIP_CALL( SCIPallocBufferArray(scip, &cliquevalues, maxnvars) );
5189 /* allocate temporary memory for counting an overlap of variables */
5190 SCIP_CALL( SCIPallocBufferArray(scip, &countofoverlapping, nusefulconss) );
5191
5192 /* sort usefulvars after indices of variables, negated and active counterparts will stand side by side */
5193 SCIPsortDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, nusefulvars);
5194
5195 /* extend cliques/constraints by checking whether some variables of a second constraint are in the same clique */
5196 for( c = nusefulconss - 1; c >= 0 && !SCIPisStopped(scip); --c )
5197 {
5198 SCIP_VAR** cons0vars; /* these are the clique variables */
5199 SCIP_CONS* cons0;
5200 int ncons0vars;
5201 SCIP_VAR* var0;
5202 int v1;
5203 int nadded; /* number of possible added variables to constraint */
5204 int cons0fixedzeros;
5205 int oldnchgcoefs;
5206#ifndef NDEBUG
5207 const int oldnaggrvars = *naggrvars;
5208#endif
5209 cons0 = usefulconss[c];
5210
5211 if( !SCIPconsIsActive(cons0) )
5212 continue;
5213
5214 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5215 * possible
5216 */
5217 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5218
5219 if( *cutoff )
5220 break;
5221
5222 /* we can't handle aggregated variables later on so we should have saved them for later */
5223 assert(*naggrvars == oldnaggrvars);
5224
5225 if( !SCIPconsIsActive(cons0) )
5226 continue;
5227
5228 /* we need to determine the cliquedata in each iteration because we eventual will change it later */
5229 consdata = SCIPconsGetData(cons0);
5230 assert(consdata != NULL);
5231
5232 cons0vars = consdata->vars;
5233 ncons0vars = consdata->nvars;
5234
5235 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5236 SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
5237 /* standard setppc-sorting now lost */
5238 consdata->sorted = FALSE;
5239
5240 /* clique array should be long enough */
5241 assert(maxnvars >= ncons0vars);
5242
5243 /* clear old entries in overlapping constraint */
5244 BMSclearMemoryArray(countofoverlapping, nusefulconss);
5245
5246 /* calculate overlapping */
5247 for( v = ncons0vars - 1; v >= 0 ; --v )
5248 {
5249 var0 = cons0vars[v];
5250
5251 /* fixed variables later to the count */
5252 if( SCIPvarGetLbLocal(var0) > 0.5 || SCIPvarGetUbLocal(var0) < 0.5 )
5253 continue;
5254
5255 assert(SCIPhashmapExists(vartoindex, (void*) var0));
5256
5257 varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var0);
5258 for( v1 = varnconss[varindex] - 1; v1 >= 0 ; --v1 )
5259 ++(countofoverlapping[varconsidxs[varindex][v1]]);
5260 }
5261
5262 oldnchgcoefs = *nchgcoefs;
5263 cons0fixedzeros = consdata->nfixedzeros;
5264
5265 chgcons0 = FALSE;
5266
5267 /* check for overlapping constraint before starting lifting */
5268 SCIP_CALL( checkForOverlapping(scip, cons0, c, c, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex,
5269 varnconss, maxnvarconsidx, varconsidxs, countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
5270 undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations,
5271 nfixedvars, naggrvars, nchgcoefs, ndelconss, cutoff) );
5272
5273 if( *cutoff )
5274 break;
5275
5276 /* we can't handle aggregated variables later on so we should have saved them for later */
5277 assert(*naggrvars == oldnaggrvars);
5278
5279 /* if cons0 changed, we need to reorder the variables */
5280 if( chgcons0 && *nchgcoefs > oldnchgcoefs )
5281 {
5282 consdata = SCIPconsGetData(cons0);
5283 assert(consdata != NULL);
5284
5285 cons0vars = consdata->vars;
5286 ncons0vars = consdata->nvars;
5287
5288 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5289 SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
5290 /* standard setppc-sorting now lost */
5291 consdata->sorted = FALSE;
5292 }
5293
5294 /* check cons0 again for redundancy/fixings, because due to fixings in all other constraints it might happen that cons0 is redundant now */
5295 if( consdata->nfixedones > 0 || consdata->nfixedzeros > cons0fixedzeros )
5296 {
5297 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5298 * possible
5299 */
5300 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndel