1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file cons_symresack.c
17 * @ingroup DEFPLUGINS_CONS
18 * @brief constraint handler for symresack constraints
19 * @author Christopher Hojny
20 *
21 * The type of constraints of this constraint handler is described in cons_symresack.h.
22 *
23 * The details of the method implemented here are described in the following papers:
24 *
25 * Fundamental Domains for Integer Programs with Symmetries@n
26 * Eric J. Friedman,@n
27 * Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)
28 *
29 * This paper describes an inequality to handle symmetries of a single permutation. This
30 * so-called FD-inequality is the basic for the propagation routine of our implementation.
31 *
32 * Polytopes Associated with Symmetry Handling@n
33 * Christopher Hojny and Marc E. Pfetsch,@n
34 * Mathematical Programming 175, No. 1, 197-240, 2019
35 *
36 * This paper describes an almost linear time separation routine for so-called cover
37 * inequalities of symresacks. In our implementation, however, we use a separation routine with
38 * quadratic worst case running time.
39 *
40 * Packing, Partitioning, and Covering Symresacks@n
41 * Christopher Hojny,@n
42 * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/05/5990.html
43 *
44 * This paper introduces linearly many inequalities with ternary coefficients that suffice to
45 * characterize the binary points contained in a packing and partitioning symresack completely.
46 */
47
48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49
50 #include "blockmemshell/memory.h"
51 #include "scip/cons_orbisack.h"
52 #include "scip/cons_setppc.h"
53 #include "scip/cons_symresack.h"
54 #include "scip/pub_cons.h"
55 #include "scip/pub_message.h"
56 #include "scip/pub_misc.h"
57 #include "scip/pub_var.h"
58 #include "scip/scip.h"
59 #include "scip/scip_branch.h"
60 #include "scip/scip_conflict.h"
61 #include "scip/scip_cons.h"
62 #include "scip/scip_cut.h"
63 #include "scip/scip_general.h"
64 #include "scip/scip_lp.h"
65 #include "scip/scip_mem.h"
66 #include "scip/scip_message.h"
67 #include "scip/scip_numerics.h"
68 #include "scip/scip_param.h"
69 #include "scip/scip_prob.h"
70 #include "scip/scip_sol.h"
71 #include "scip/scip_var.h"
72 #include <string.h>
73
74 /* constraint handler properties */
75 #define CONSHDLR_NAME "symresack"
76 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"
77 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
78 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
79 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
80 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
81 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
82 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
83 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
84 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
85 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
86 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
87 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
88
89 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
90 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
91
92 #define DEFAULT_PPSYMRESACK TRUE /**< whether we allow upgrading to packing/partitioning symresacks */
93 #define DEFAULT_CHECKMONOTONICITY TRUE /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
94 #define DEFAULT_FORCECONSCOPY FALSE /**< whether symresack constraints should be forced to be copied to sub SCIPs */
95
96 /* macros for getting bounds of pseudo solutions in propagation */
97 #define ISFIXED0(x) (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)
98 #define ISFIXED1(x) (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)
99
100
101 /*
102 * Data structures
103 */
104
105 /** constraint handler data */
106 struct SCIP_ConshdlrData
107 {
108 SCIP_Bool checkppsymresack; /**< whether we allow upgrading to packing/partitioning symresacks */
109 SCIP_Bool checkmonotonicity; /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
110 int maxnvars; /**< maximal number of variables in a symresack constraint */
111 SCIP_Bool forceconscopy; /**< whether symresack constraints should be forced to be copied to sub SCIPs */
112 };
113
114
115 /** constraint data for symresack constraints */
116 struct SCIP_ConsData
117 {
118 SCIP_VAR** vars; /**< variables */
119 int nvars; /**< number of variables */
120 int* perm; /**< permutation associated to the symresack */
121 int* invperm; /**< inverse permutation */
122 SCIP_Bool ppupgrade; /**< whether constraint is upgraded to packing/partitioning symresack */
123 SCIP_Bool ismodelcons; /**< whether the symresack is a model constraint */
124 #ifdef SCIP_DEBUG
125 int debugcnt; /**< counter to store number of added cover inequalities */
126 #endif
127
128 /* data for upgraded symresack constraints */
129 int ncycles; /**< number of cycles in permutation */
130 int** cycledecomposition; /**< cycle decomposition */
131 int ndescentpoints; /**< number of descent points in perm (only used if perm is not monotone) */
132 int* descentpoints; /**< descent points in perm (only used if perm is not monotone) */
133 };
134
135
136 /*
137 * Local methods
138 */
139
140 /** frees a symresack constraint data */
141 static
consdataFree(SCIP * scip,SCIP_CONSDATA ** consdata)142 SCIP_RETCODE consdataFree(
143 SCIP* scip, /**< SCIP data structure */
144 SCIP_CONSDATA** consdata /**< pointer to symresack constraint data */
145 )
146 {
147 int nvars;
148 int i;
149
150 assert( consdata != NULL );
151 assert( *consdata != NULL );
152
153 nvars = (*consdata)->nvars;
154
155 if ( nvars == 0 )
156 {
157 assert( (*consdata)->vars == NULL );
158 assert( (*consdata)->perm == NULL );
159 assert( (*consdata)->invperm == NULL );
160 assert( (*consdata)->ncycles == 0 );
161 assert( (*consdata)->cycledecomposition == NULL );
162
163 SCIPfreeBlockMemory(scip, consdata);
164
165 return SCIP_OKAY;
166 }
167
168 if ( (*consdata)->ndescentpoints > 0 )
169 {
170 assert( (*consdata)->descentpoints != NULL );
171
172 SCIPfreeBlockMemoryArray(scip, &((*consdata)->descentpoints), (*consdata)->ndescentpoints);
173 }
174
175 if ( (*consdata)->ppupgrade )
176 {
177 for (i = 0; i < (*consdata)->ncycles; ++i)
178 {
179 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition[i]), nvars + 1);
180 }
181 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition), (*consdata)->ncycles);
182 }
183
184 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->invperm), nvars);
185 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->perm), nvars);
186
187 for (i = 0; i < nvars; ++i)
188 {
189 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i]) );
190 }
191 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nvars);
192
193 SCIPfreeBlockMemory(scip, consdata);
194
195 return SCIP_OKAY;
196 }
197
198
199 /** check whether constraint can be upgraded to packing/partitioning symresack */
200 static
packingUpgrade(SCIP * scip,SCIP_CONSDATA ** consdata,int * perm,SCIP_VAR ** vars,int nvars,SCIP_Bool checkmonotonicity,SCIP_Bool * upgrade)201 SCIP_RETCODE packingUpgrade(
202 SCIP* scip, /**< SCIP data structure */
203 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
204 int* perm, /**< permutation */
205 SCIP_VAR** vars, /**< variables affected by permutation */
206 int nvars, /**< length of permutation */
207 SCIP_Bool checkmonotonicity, /**< check whether permutation is monotone */
208 SCIP_Bool* upgrade /**< pointer to store whether upgrade was successful */
209 )
210 {
211 SCIP_Bool* covered;
212 SCIP_Bool descent;
213 SCIP_CONSHDLR* setppcconshdlr;
214 SCIP_CONS** setppcconss;
215 SCIP_VAR* var;
216 SCIP_Bool terminated = FALSE;
217 int** cycledecomposition;
218 int* indicesincycle;
219 int nsetppcconss;
220 int curcycle;
221 int maxcyclelength;
222 int ncycles = 0;
223 int c;
224 int i;
225 int j;
226 int ndescentpoints = 0;
227 int* descentpoints;
228
229 assert( scip != NULL );
230 assert( perm != NULL );
231 assert( vars != NULL );
232 assert( nvars > 0 );
233 assert( upgrade != NULL );
234
235 *upgrade = FALSE;
236
237 SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
238
239 for (i = 0; i < nvars; ++i)
240 covered[i] = FALSE;
241
242 /* get number of cycles in permutation */
243 for (i = 0; i < nvars; ++i)
244 {
245 /* skip checked indices */
246 if ( covered[i] )
247 continue;
248
249 ++ncycles;
250 j = i;
251 descent = FALSE;
252
253 do
254 {
255 covered[j] = TRUE;
256
257 if ( perm[j] < j )
258 {
259 ++ndescentpoints;
260
261 if ( ! descent )
262 descent = TRUE;
263 else if ( checkmonotonicity )
264 break;
265 }
266
267 j = perm[j];
268 }
269 while ( j != i );
270
271 /* if cycle is not monotone and we require the cycle to be monotone */
272 if ( j != i )
273 {
274 assert( checkmonotonicity );
275 SCIPfreeBufferArray(scip, &covered);
276
277 return SCIP_OKAY;
278 }
279 }
280 assert( ncycles <= nvars / 2 );
281
282 /* check for packing/partitioning type */
283 for (i = 0; i < nvars; ++i)
284 covered[i] = FALSE;
285
286 /* compute cycle decomposition: row i stores in entry 0 the length of the cycle,
287 * the remaining entries are the coordinates in the cycle;
288 * store descent points as well if permutation is not monotone */
289 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition, ncycles) );
290 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &descentpoints, ndescentpoints) );
291 for (i = 0; i < ncycles; ++i)
292 {
293 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1) );
294 }
295
296 curcycle = 0;
297 maxcyclelength = 0;
298 c = 0;
299 for (i = 0; i < nvars; ++i)
300 {
301 int cyclelength = 0;
302
303 /* skip checked indices */
304 if ( covered[i] )
305 continue;
306
307 j = i;
308 do
309 {
310 if ( perm[j] < j )
311 descentpoints[c++] = j;
312
313 covered[j] = TRUE;
314 cycledecomposition[curcycle][++cyclelength] = j;
315 j = perm[j];
316 }
317 while ( j != i );
318
319 cycledecomposition[curcycle][0] = cyclelength;
320 ++curcycle;
321
322 if ( maxcyclelength < cyclelength )
323 maxcyclelength = cyclelength;
324 }
325 assert( c == ndescentpoints );
326
327 /* permutation can be upgraded -> check whether the symresack is of packing/partitioning type */
328 setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
329 if ( setppcconshdlr == NULL )
330 {
331 SCIPerrorMessage("Setppc constraint handler not found.\n");
332 return SCIP_PLUGINNOTFOUND;
333 }
334 setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
335 nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
336
337 /* Check whether each cycle of the symresack is contained in a set packing/partitioning constraint.
338 * To this end, we have to guarantee that all affected variables are not negated since permutations
339 * are given w.r.t. original variables. */
340 *upgrade = TRUE;
341
342 SCIP_CALL( SCIPallocBufferArray(scip, &indicesincycle, maxcyclelength) );
343
344 for (i = 0; i < ncycles && *upgrade && ! terminated; ++i)
345 {
346 int cyclelength;
347
348 /* get indices of variables in current cycle */
349 for (j = 0; j < cycledecomposition[i][0]; ++ j)
350 {
351 var = vars[cycledecomposition[i][j + 1]];
352
353 if ( SCIPvarIsNegated(var) )
354 {
355 terminated = TRUE;
356 break;
357 }
358
359 indicesincycle[j] = SCIPvarGetProbindex(var);
360 }
361
362 cyclelength = cycledecomposition[i][0];
363
364 /* iterate over constraints
365 *
366 * @todo Improve the check by sorting the constraints in the setppcconss array
367 * by type and number of contained variables. */
368 for (c = 0; c < nsetppcconss; ++c)
369 {
370 int nsetppcvars;
371 SCIP_VAR** setppcvars;
372 int varidx;
373 int nfound = 0;
374 int k;
375
376 /* check type */
377 if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
378 continue;
379 assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING || SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING );
380
381 /* get set packing/partitioning variables */
382 nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
383
384 /* skip empty constraints (might not have been removed by presolving yet) */
385 if ( nsetppcvars == 0 )
386 continue;
387 assert( nsetppcvars > 0 );
388
389 setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
390 assert( setppcvars != NULL );
391
392 /* check whether all variables of the cycle are contained in setppc constraint */
393 for (j = 0; j < nsetppcvars && nfound < cyclelength; ++j)
394 {
395 var = setppcvars[j];
396
397 if ( SCIPvarIsNegated(var) )
398 continue;
399
400 varidx = SCIPvarGetProbindex(var);
401
402 for (k = 0; k < cyclelength; ++k)
403 {
404 if ( varidx == indicesincycle[k] )
405 {
406 ++nfound;
407 break;
408 }
409 }
410 }
411 assert( nfound <= cyclelength );
412
413 if ( nfound == cyclelength )
414 break;
415 }
416
417 /* row is not contained in a set packing/partitioning constraint */
418 if ( c >= nsetppcconss )
419 *upgrade = FALSE;
420 }
421
422 if ( *upgrade )
423 {
424 (*consdata)->ncycles = ncycles;
425 (*consdata)->cycledecomposition = cycledecomposition;
426 (*consdata)->ndescentpoints = ndescentpoints;
427 (*consdata)->descentpoints = descentpoints;
428 SCIPdebugMsg(scip, "added monotone PP symresack.\n");
429
430 SCIPfreeBufferArray(scip, &indicesincycle);
431 SCIPfreeBufferArray(scip, &covered);
432 }
433 else
434 {
435 SCIPfreeBlockMemoryArray(scip, &descentpoints, ndescentpoints);
436 SCIPfreeBufferArray(scip, &indicesincycle);
437 SCIPfreeBufferArray(scip, &covered);
438 for (i = 0; i < ncycles; ++i)
439 {
440 SCIPfreeBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1);
441 }
442 SCIPfreeBlockMemoryArray(scip, &cycledecomposition, ncycles);
443 }
444
445 return SCIP_OKAY;
446 }
447
448
449 /** creates symresack constraint data
450 *
451 * If the input data contains non-binary variables or fixed
452 * points, we delete these variables in a preprocessing step.
453 */
454 static
consdataCreate(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_CONSDATA ** consdata,SCIP_VAR * const * inputvars,int inputnvars,int * inputperm,SCIP_Bool ismodelcons)455 SCIP_RETCODE consdataCreate(
456 SCIP* scip, /**< SCIP data structure */
457 SCIP_CONSHDLR* conshdlr, /**< symresack constraint handler */
458 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
459 SCIP_VAR*const* inputvars, /**< input variables of the constraint handler */
460 int inputnvars, /**< input number of variables of the constraint handler*/
461 int* inputperm, /**< input permutation of the constraint handler */
462 SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
463 )
464 {
465 SCIP_CONSHDLRDATA* conshdlrdata;
466 SCIP_VAR** vars;
467 SCIP_Bool upgrade;
468 int* indexcorrection;
469 int* invperm;
470 int* perm;
471 int naffectedvariables;
472 int i;
473 int j = 0;
474
475 assert( consdata != NULL );
476 assert( conshdlr != NULL );
477 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
478
479 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
480
481 #ifdef SCIP_DEBUG
482 (*consdata)->debugcnt = 0;
483 #endif
484
485 (*consdata)->ndescentpoints = 0;
486 (*consdata)->descentpoints = NULL;
487 (*consdata)->ismodelcons = ismodelcons;
488
489 /* count the number of binary variables which are affected by the permutation */
490 SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, inputnvars) );
491 indexcorrection[0] = -1;
492 for (i = 0; i < inputnvars; ++i)
493 {
494 if ( inputperm[i] != i && SCIPvarIsBinary(inputvars[i]) )
495 {
496 if ( i == 0 )
497 indexcorrection[i] = 0;
498 else
499 indexcorrection[i] = indexcorrection[i - 1] + 1;
500 }
501 else
502 {
503 if ( i > 0 )
504 indexcorrection[i] = indexcorrection[i - 1];
505 }
506 }
507 naffectedvariables = indexcorrection[inputnvars - 1] + 1;
508
509 (*consdata)->nvars = naffectedvariables;
510
511 /* Stop if we detect that the permutation fixes each binary point. */
512 if ( naffectedvariables == 0 )
513 {
514 SCIPfreeBufferArrayNull(scip, &indexcorrection);
515
516 (*consdata)->vars = NULL;
517 (*consdata)->perm = NULL;
518 (*consdata)->invperm = NULL;
519 (*consdata)->ppupgrade = FALSE;
520 (*consdata)->ncycles = 0;
521 (*consdata)->cycledecomposition = NULL;
522
523 return SCIP_OKAY;
524 }
525
526 /* remove fixed points from permutation representation */
527 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, naffectedvariables) );
528 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &perm, naffectedvariables) );
529 for (i = 0; i < inputnvars; ++i)
530 {
531 if ( i == 0 )
532 {
533 if ( indexcorrection[i] > -1 )
534 {
535 vars[j] = inputvars[i];
536 perm[j++] = indexcorrection[inputperm[i]];
537 }
538 }
539 else
540 {
541 if ( indexcorrection[i] > indexcorrection[i - 1] )
542 {
543 vars[j] = inputvars[i];
544 perm[j++] = indexcorrection[inputperm[i]];
545 }
546 }
547 }
548 SCIPfreeBufferArrayNull(scip, &indexcorrection);
549
550 (*consdata)->vars = vars;
551 (*consdata)->perm = perm;
552
553 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &invperm, naffectedvariables) );
554 for (i = 0; i < naffectedvariables; ++i)
555 {
556 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i]) );
557 invperm[perm[i]] = i;
558 }
559 (*consdata)->invperm = invperm;
560
561 /* check for upgrade to packing/partitioning symresacks*/
562 conshdlrdata = SCIPconshdlrGetData(conshdlr);
563 upgrade = FALSE;
564 if ( conshdlrdata->checkppsymresack )
565 {
566 SCIP_CALL( packingUpgrade(scip, consdata, perm, vars, naffectedvariables, conshdlrdata->checkmonotonicity, &upgrade) );
567 }
568
569 (*consdata)->ppupgrade = upgrade;
570
571 /* get transformed variables, if we are in the transformed problem */
572 if ( SCIPisTransformed(scip) )
573 {
574 /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_symresack, since one cannot
575 * easily eliminate single variables from a symresack constraint. */
576 for (i = 0; i < naffectedvariables; ++i)
577 {
578 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i], &(*consdata)->vars[i]) );
579 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i]) );
580 }
581 }
582
583 return SCIP_OKAY;
584 }
585
586
587 /** generate initial LP cut
588 *
589 * We generate the ordering inequality for the pair \f$(1, \gamma^{-1}(1))\f$, i.e.,
590 * the inequality \f$-x_{1} + x_{\gamma^{-1}(1)} \leq 0\f$. This inequality is valid,
591 * because we guaranteed in a preprocessing step that all variables are binary.
592 *
593 * Furthermore, we add facet inequalities of packing/partitioning symresacks if
594 * we deal with packing/partitioning symresacks.
595 */
596 static
initLP(SCIP * scip,SCIP_CONS * cons,SCIP_Bool checkmonotonicity,SCIP_Bool * infeasible)597 SCIP_RETCODE initLP(
598 SCIP* scip, /**< SCIP pointer */
599 SCIP_CONS* cons, /**< constraint */
600 SCIP_Bool checkmonotonicity, /**< has it been checked whether permutation is monotone for packing/partitioning symresacks? */
601 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
602 )
603 {
604 SCIP_CONSDATA* consdata;
605 SCIP_VAR** vars;
606 SCIP_ROW* row;
607 int nvars;
608 #ifdef SCIP_DEBUG
609 char name[SCIP_MAXSTRLEN];
610 #endif
611 int i;
612 int j;
613 int k;
614
615 assert( scip != NULL );
616 assert( cons != NULL );
617 assert( infeasible != NULL );
618
619 *infeasible = FALSE;
620
621 consdata = SCIPconsGetData(cons);
622 assert( consdata != NULL );
623
624 nvars = consdata->nvars;
625
626 /* avoid stupid problems */
627 if ( nvars <= 1 )
628 return SCIP_OKAY;
629
630 assert( consdata->vars != NULL );
631 vars = consdata->vars;
632
633 /* there are no fixed points */
634 assert( consdata->invperm[0] != 0 );
635
636 /* add ordering inequality */
637 #ifdef SCIP_DEBUG
638 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_init_%s", SCIPconsGetName(cons));
639 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
640 #else
641 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
642 #endif
643 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[0], -1.0) );
644 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[consdata->invperm[0]], 1.0) );
645
646 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
647
648 SCIP_CALL( SCIPreleaseRow(scip, &row) );
649
650 /* check whether we have a packing/partioning symresack */
651 if ( consdata->ppupgrade && ! *infeasible )
652 {
653 if ( checkmonotonicity )
654 {
655 SCIP_VAR** varsincons;
656 SCIP_Real* coeffs;
657 int** cycledecomposition;
658 int ncycles;
659 int nvarsincons;
660 int nvarsincycle;
661 int firstelemincycle;
662
663 ncycles = consdata->ncycles;
664 cycledecomposition = consdata->cycledecomposition;
665
666 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
667 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nvars) );
668
669 coeffs[0] = 1.0;
670
671 /* add packing/partitioning symresack constraints */
672 for (i = 0; i < ncycles; ++i)
673 {
674 assert( cycledecomposition[i][0] > 0 );
675
676 nvarsincycle = cycledecomposition[i][0];
677 varsincons[0] = vars[cycledecomposition[i][nvarsincycle]];
678 firstelemincycle = cycledecomposition[i][1];
679
680 assert( firstelemincycle == consdata->perm[cycledecomposition[i][nvarsincycle]] );
681
682 nvarsincons = 1;
683
684 /* add variables of other cycles to the constraint */
685 for (j = 0; j < i; ++j)
686 {
687 nvarsincycle = cycledecomposition[j][0];
688 for (k = 1; k <= nvarsincycle; ++k)
689 {
690 if ( cycledecomposition[j][k] < firstelemincycle )
691 {
692 varsincons[nvarsincons] = vars[cycledecomposition[j][k]];
693 coeffs[nvarsincons++] = -1.0;
694 }
695 else
696 continue;
697 }
698 }
699
700 #ifdef SCIP_DEBUG
701 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", i, SCIPconsGetName(cons));
702 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
703 #else
704 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
705 #endif
706 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
707
708 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
709 SCIP_CALL( SCIPreleaseRow(scip, &row) );
710
711 if ( *infeasible )
712 break;
713 }
714
715 SCIPfreeBufferArray(scip, &coeffs);
716 SCIPfreeBufferArray(scip, &varsincons);
717 }
718 else
719 {
720 SCIP_Real* coeffs;
721 SCIP_VAR** varsincons;
722 int* imgdescentpoints;
723 int* descentpoints;
724 int* perm;
725 int ndescentpoints;
726 int lastascent = 0;
727 int newlastascent = 0;
728 int nvarsincons = 1;
729
730 descentpoints = consdata->descentpoints;
731 ndescentpoints = consdata->ndescentpoints;
732 perm = consdata->perm;
733
734 assert( descentpoints != NULL );
735 assert( ndescentpoints > 0 );
736 assert( perm != NULL );
737 assert( vars != NULL );
738 assert( nvars > 0 );
739
740 SCIP_CALL( SCIPallocBufferArray(scip, &imgdescentpoints, ndescentpoints) );
741
742 /* get images of descentpoints */
743 for (j = 0; j < ndescentpoints; ++j)
744 imgdescentpoints[j] = perm[descentpoints[j]];
745
746 /* sort descent points increasingly w.r.t. the corresponding image */
747 SCIPsortIntInt(imgdescentpoints, descentpoints, ndescentpoints);
748
749 /* iteratively generate coefficient vector: the first entry is the descent point j and the remaining entries
750 * are the corresponding ascent points less than perm[j]
751 */
752 SCIP_CALL( SCIPallocClearBufferArray(scip, &coeffs, nvars) );
753 SCIP_CALL( SCIPallocClearBufferArray(scip, &varsincons, nvars) );
754 coeffs[0] = 1.0;
755 for (j = 0; j < ndescentpoints; ++j)
756 {
757 varsincons[0] = vars[descentpoints[j]];
758 for (i = lastascent; i < imgdescentpoints[j]; ++i)
759 {
760 if ( perm[i] > i )
761 {
762 coeffs[nvarsincons] = -1.0;
763 varsincons[nvarsincons++] = vars[i];
764 newlastascent = i;
765 }
766 }
767 lastascent = newlastascent;
768
769 #ifdef SCIP_DEBUG
770 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", j, SCIPconsGetName(cons));
771 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
772 #else
773 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
774 #endif
775 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
776
777 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
778 SCIP_CALL( SCIPreleaseRow(scip, &row) );
779
780 if ( *infeasible )
781 break;
782 }
783
784 SCIPfreeBufferArray(scip, &varsincons);
785 SCIPfreeBufferArray(scip, &coeffs);
786 SCIPfreeBufferArray(scip, &imgdescentpoints);
787 }
788 }
789
790 return SCIP_OKAY;
791 }
792
793
794 /** perform propagation of symresack constraint */
795 static
propVariables(SCIP * scip,SCIP_CONS * cons,SCIP_Bool * infeasible,int * ngen)796 SCIP_RETCODE propVariables(
797 SCIP* scip, /**< SCIP pointer */
798 SCIP_CONS* cons, /**< constraint to be propagated */
799 SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */
800 int* ngen /**< pointer to store number of generated bound strengthenings */
801 )
802 {
803 SCIP_CONSDATA* consdata;
804 SCIP_VAR** vars;
805 int* invperm;
806 int nvars;
807 int i;
808
809 assert( scip != NULL );
810 assert( cons != NULL );
811 assert( infeasible != NULL );
812 assert( ngen != NULL );
813
814 SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
815
816 *ngen = 0;
817 *infeasible = FALSE;
818
819 /* get data of constraint */
820 consdata = SCIPconsGetData(cons);
821 assert( consdata != NULL );
822 nvars = consdata->nvars;
823
824 /* avoid trivial problems */
825 if ( nvars < 2 )
826 return SCIP_OKAY;
827
828 assert( consdata->vars != NULL );
829 assert( consdata->invperm != NULL );
830 vars = consdata->vars;
831 invperm = consdata->invperm;
832
833 /* loop through all variables */
834 for (i = 0; i < nvars; ++i)
835 {
836 SCIP_VAR* var2;
837 SCIP_VAR* var;
838 int r;
839 SCIP_Bool tightened;
840
841 /* there are no fixed points */
842 assert( invperm[i] != i );
843
844 /* get variables of first and second column */
845 var = vars[i];
846 var2 = vars[invperm[i]];
847 assert( var != NULL );
848 assert( var2 != NULL );
849
850 /* if first part of variable pair fixed to 0 and second part is fixed to 1 */
851 if ( ISFIXED0(var) && ISFIXED1(var2) )
852 {
853 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
854
855 SCIPdebugMsg(scip, " -> node infeasible (pair was fixed to (0,1) but there was no pair of type (1,0) before) ---> lexicographical order violated, infeasible.\n");
856
857 /* perform conflict analysis */
858 if ( SCIPisConflictAnalysisApplicable(scip) )
859 {
860 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
861
862 for (r = 0; r <= i; ++r)
863 {
864 /* there are no fixed points */
865 assert( invperm[r] != r );
866
867 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[r]) );
868 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) );
869 }
870
871 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
872 }
873
874 *infeasible = TRUE;
875 break;
876 }
877 /* if first part of the variable pair is fixed to 0 and the second part is free --> fix second part to 0 */
878 else if ( ISFIXED0(var) && ( ! ISFIXED0(var2) ) )
879 {
880 assert( SCIPvarGetUbLocal(var) < 0.5 );
881 assert( SCIPvarGetLbLocal(var2) < 0.5 );
882 assert( SCIPvarGetUbLocal(var2) > 0.5 );
883
884 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
885
886 assert( SCIPvarGetLbLocal(var2) < 0.5 );
887 SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
888 assert( ! *infeasible );
889
890 if ( tightened )
891 ++(*ngen);
892 }
893 /* if second part of the variable pair is fixed to 1 and the first part is free --> fix first part to 1 */
894 else if ( ( ! ISFIXED1(var) ) && ISFIXED1(var2) )
895 {
896 assert( SCIPvarGetLbLocal(var) < 0.5 );
897 assert( SCIPvarGetUbLocal(var) > 0.5 );
898 assert( SCIPvarGetLbLocal(var2) > 0.5 );
899
900 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
901
902 assert( SCIPvarGetUbLocal(var) > 0.5 );
903 SCIP_CALL( SCIPinferVarLbCons(scip, var, 1.0, cons, i + nvars, FALSE, infeasible, &tightened) ); /*lint !e713*/
904 assert( ! *infeasible );
905
906 if ( tightened )
907 ++(*ngen);
908 }
909 /* if solution is lexicographically maximal */
910 else if ( ISFIXED1(var) && ISFIXED0(var2) )
911 {
912 assert( SCIPvarGetLbLocal(var) > 0.5 );
913 assert( SCIPvarGetUbLocal(var2) < 0.5 );
914
915 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
916 SCIPdebugMsg(scip, " -> node is feasible (pair was fixed to (1,0) and every earlier pair is constant).\n");
917
918 break;
919 }
920 /* cannot apply propagation */
921 else
922 break;
923 }
924
925 return SCIP_OKAY;
926 }
927
928
929 /** add symresack cover inequality */
930 static
addSymresackInequality(SCIP * scip,SCIP_CONS * cons,int nvars,SCIP_VAR ** vars,int * coeffs,SCIP_Real rhs,SCIP_Bool * infeasible)931 SCIP_RETCODE addSymresackInequality(
932 SCIP* scip, /**< SCIP pointer */
933 SCIP_CONS* cons, /**< constraint */
934 int nvars, /**< number of variables */
935 SCIP_VAR** vars, /**< variables */
936 int* coeffs, /**< coefficient vector of inequality to be added */
937 SCIP_Real rhs, /**< right-hand side of inequality to be added */
938 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
939 )
940 {
941 SCIP_ROW* row;
942 int i;
943 #ifdef SCIP_DEBUG
944 SCIP_CONSDATA* consdata;
945 char name[SCIP_MAXSTRLEN];
946 #endif
947
948 assert( scip != NULL );
949 assert( cons != NULL );
950 assert( nvars > 0 );
951 assert( vars != NULL );
952 assert( coeffs != NULL );
953 assert( infeasible != NULL );
954
955 *infeasible = FALSE;
956
957 #ifdef SCIP_DEBUG
958 consdata = SCIPconsGetData(cons);
959 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_cover_%s_%d", SCIPconsGetName(cons), consdata->debugcnt);
960 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
961 ++consdata->debugcnt;
962 #else
963 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
964 #endif
965 SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
966
967 for (i = 0; i < nvars; ++i)
968 {
969 if ( coeffs[i] == 1 || coeffs[i] == -1 )
970 {
971 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], (SCIP_Real) coeffs[i]) );
972 }
973 }
974 SCIP_CALL( SCIPflushRowExtensions(scip, row) );
975 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
976 SCIP_CALL( SCIPreleaseRow(scip, &row) );
977
978 return SCIP_OKAY;
979 }
980
981
982 /** separate symresack cover inequalities
983 *
984 * We currently do NOT enter cuts into the pool.
985 */
986 static
separateSymresackCovers(SCIP * scip,SCIP_CONS * cons,const SCIP_CONSDATA * consdata,SCIP_Real * vals,int * ngen,SCIP_Bool * infeasible)987 SCIP_RETCODE separateSymresackCovers(
988 SCIP* scip, /**< SCIP pointer */
989 SCIP_CONS* cons, /**< constraint */
990 const SCIP_CONSDATA* consdata, /**< constraint data */
991 SCIP_Real* vals, /**< solution values of variables */
992 int* ngen, /**< pointer to store the number of separated covers */
993 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
994 )
995 {
996 SCIP_Real constobjective;
997 SCIP_Real* sepaobjective;
998 SCIP_Real tmpsoluobj = 0.0;
999 SCIP_Real maxsoluobj = 0.0;
1000 int* tmpsolu;
1001 int* maxsolu;
1002 int* invperm;
1003 int* perm;
1004 int nvars;
1005 int crit;
1006 int i;
1007
1008 *infeasible = FALSE;
1009 *ngen = 0;
1010
1011 assert( scip != NULL );
1012 assert( consdata != NULL );
1013
1014 /* we do not have to take care of trivial constraints */
1015 if ( consdata->nvars < 2 )
1016 return SCIP_OKAY;
1017
1018 assert( consdata->vars != NULL );
1019 assert( consdata->perm != NULL );
1020 assert( consdata->invperm != NULL );
1021 assert( infeasible != NULL );
1022 assert( ngen != NULL );
1023
1024 nvars = consdata->nvars;
1025 perm = consdata->perm;
1026 invperm = consdata->invperm;
1027
1028 /* initialize objective */
1029 SCIP_CALL( SCIPallocBufferArray(scip, &sepaobjective, nvars) );
1030
1031 constobjective = 1.0; /* constant part of separation objective */
1032 for (i = 0; i < nvars; ++i)
1033 {
1034 if ( i < perm[i] )
1035 {
1036 sepaobjective[i] = vals[i];
1037 constobjective -= vals[i];
1038 }
1039 else
1040 sepaobjective[i] = vals[i] - 1.0;
1041 }
1042
1043 /* allocate memory for temporary and global solution */
1044 SCIP_CALL( SCIPallocBufferArray(scip, &tmpsolu, nvars) );
1045 SCIP_CALL( SCIPallocBufferArray(scip, &maxsolu, nvars) );
1046
1047 /* start separation procedure by iterating over critical rows */
1048 for (crit = 0; crit < nvars; ++crit)
1049 {
1050 /* there are no fixed points */
1051 assert( perm[crit] != crit );
1052
1053 /* initialize temporary solution */
1054 for (i = 0; i < nvars; ++i)
1055 tmpsolu[i] = 2;
1056 tmpsoluobj = 0.0;
1057
1058 /* perform fixings implied by the critical row */
1059 tmpsolu[crit] = 0;
1060 assert( invperm[crit] < nvars );
1061
1062 tmpsolu[invperm[crit]] = 1;
1063 tmpsoluobj += sepaobjective[invperm[crit]];
1064
1065 /* perform 1-fixings */
1066 i = invperm[crit];
1067 while ( i < crit )
1068 {
1069 i = invperm[i];
1070 tmpsolu[i] = 1;
1071 tmpsoluobj += sepaobjective[i];
1072 }
1073
1074 /* row c cannot be critical */
1075 if ( i == crit )
1076 continue;
1077
1078 assert( tmpsolu[crit] == 0 );
1079
1080 /* perform 0-fixing */
1081 i = perm[crit];
1082 while ( i < crit )
1083 {
1084 tmpsolu[i] = 0;
1085 i = perm[i];
1086 }
1087
1088 /* iterate over rows above the critical row */
1089 for (i = 0; i < crit; ++i)
1090 {
1091 SCIP_Real objimpact = 0.0;
1092 int j;
1093
1094 /* skip already fixed entries */
1095 if ( tmpsolu[i] != 2 )
1096 continue;
1097
1098 /* Check effect of fixing entry i to 1 and apply all implied fixing to other entries.
1099 *
1100 * Observe: Experiments indicate that entries are more often fixed to 1 than to 0.
1101 * For this reason, we apply the 1-fixings directly. If it turns out that the 1-fixings
1102 * have a negative impact on the objective, we undo these fixings afterwards and apply
1103 * 0-fixings instead. */
1104
1105 /* check fixings in invperm direction */
1106 j = i;
1107 do
1108 {
1109 assert( tmpsolu[j] == 2 );
1110 tmpsolu[j] = 1;
1111 objimpact += sepaobjective[j];
1112 j = invperm[j];
1113 }
1114 while ( j < crit && j != i );
1115
1116 /* if we do not detect a cycle */
1117 if ( j != i )
1118 {
1119 /* fix entry j since this is not done in the above do-while loop */
1120 assert( tmpsolu[j] == 2 );
1121 tmpsolu[j] = 1;
1122 objimpact += sepaobjective[j];
1123
1124 /* check fixings in perm direction */
1125 j = perm[i];
1126 while ( j < crit )
1127 {
1128 assert( j != i );
1129 assert( tmpsolu[j] == 2 );
1130 tmpsolu[j] = 1;
1131 objimpact += sepaobjective[j];
1132 j = perm[j];
1133 }
1134
1135 assert( j != crit );
1136 }
1137
1138 /* if fixing entry i has a positive impact -> keep above fixings of entries to 1 */
1139 /* otherwise -> reset entries to 0 */
1140 if ( SCIPisEfficacious(scip, objimpact) )
1141 tmpsoluobj += objimpact;
1142 else
1143 {
1144 j = i;
1145 do
1146 {
1147 assert( tmpsolu[j] == 1 );
1148 tmpsolu[j] = 0;
1149 j = invperm[j];
1150 }
1151 while ( j < crit && j != i );
1152
1153 /* if we do not detect a cycle */
1154 if ( j != i )
1155 {
1156 /* fix entry j since this is not done in the above do-while loop */
1157 assert( tmpsolu[j] == 1 );
1158 tmpsolu[j] = 0;
1159
1160 /* check fixings in perm direction */
1161 j = perm[i];
1162 while ( j < crit )
1163 {
1164 assert( j != i );
1165 assert( tmpsolu[j] == 1 );
1166 tmpsolu[j] = 0;
1167 j = perm[j];
1168 }
1169
1170 assert( j != crit );
1171 }
1172 }
1173 }
1174
1175 /* iterate over unfixed entries below the critical row */
1176 for (i = crit + 1; i < nvars; ++i)
1177 {
1178 /* skip already fixed entries */
1179 if ( tmpsolu[i] != 2 )
1180 continue;
1181
1182 if ( SCIPisEfficacious(scip, sepaobjective[i]) )
1183 {
1184 assert( tmpsolu[i] == 2 );
1185 tmpsolu[i] = 1;
1186 tmpsoluobj += sepaobjective[i];
1187 }
1188 else
1189 {
1190 assert( tmpsolu[i] == 2 );
1191 tmpsolu[i] = 0;
1192 }
1193 }
1194
1195 /* check whether we have found a better solution which has positive separation objective*/
1196 if ( SCIPisEfficacious(scip, tmpsoluobj + constobjective - maxsoluobj) )
1197 {
1198 assert( SCIPisEfficacious(scip, tmpsoluobj + constobjective) );
1199 for (i = 0; i < nvars; ++i)
1200 maxsolu[i] = tmpsolu[i];
1201 maxsoluobj = tmpsoluobj + constobjective;
1202 }
1203 }
1204
1205 /* Check whether the separation objective is positive, i.e., a violated cover was found. */
1206 if ( SCIPisEfficacious(scip, maxsoluobj) )
1207 {
1208 SCIP_Real rhs = -1.0;
1209 SCIP_Real lhs = 0.0;
1210
1211 for (i = 0; i < nvars; ++i)
1212 {
1213 if ( i < perm[i] )
1214 {
1215 maxsolu[i] = maxsolu[i] - 1;
1216 lhs += vals[i] * maxsolu[i];
1217 }
1218 else
1219 {
1220 lhs += vals[i] * maxsolu[i];
1221 rhs += maxsolu[i];
1222 }
1223 }
1224
1225 assert( SCIPisGT(scip, lhs, rhs) );
1226
1227 /* add cover inequality */
1228 SCIP_CALL( addSymresackInequality(scip, cons, nvars, consdata->vars, maxsolu, rhs, infeasible) );
1229
1230 if ( ! *infeasible )
1231 ++(*ngen);
1232 }
1233
1234 SCIPfreeBufferArrayNull(scip, &maxsolu);
1235 SCIPfreeBufferArrayNull(scip, &tmpsolu);
1236 SCIPfreeBufferArrayNull(scip, &sepaobjective);
1237
1238 return SCIP_OKAY;
1239 }
1240
1241
1242 /** check whether solution is feasible for symresacks */
1243 static
checkSymresackSolution(SCIP * scip,SCIP_CONS * cons,SCIP_SOL * sol,SCIP_RESULT * result,SCIP_Bool printreason)1244 SCIP_RETCODE checkSymresackSolution(
1245 SCIP* scip, /**< SCIP pointer */
1246 SCIP_CONS* cons, /**< constrained for which we check the solution */
1247 SCIP_SOL* sol, /**< solution to be checked */
1248 SCIP_RESULT* result, /**< pointer to store whether we detected infeasibility */
1249 SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
1250 )
1251 {
1252 SCIP_CONSDATA* consdata;
1253 SCIP_VAR** vars;
1254 int* invperm;
1255 int nvars;
1256 int i;
1257
1258 assert( cons != NULL );
1259 consdata = SCIPconsGetData(cons);
1260 assert( consdata != NULL);
1261
1262 /* we do not have to take care of trivial constraints */
1263 if ( consdata->nvars < 2 )
1264 return SCIP_OKAY;
1265
1266 assert( consdata->vars != NULL );
1267 assert( consdata->invperm != NULL );
1268
1269 SCIPdebugMsg(scip, "Check method for symresack constraint <%s> (%d rows) ...\n", SCIPconsGetName(cons), consdata->nvars);
1270
1271 nvars = consdata->nvars;
1272 vars = consdata->vars;
1273 invperm = consdata->invperm;
1274
1275 /* detect first non-constant pair of variables */
1276 for (i = 0; i < nvars; ++i)
1277 {
1278 SCIP_Real solval;
1279 int val1;
1280 int val2;
1281
1282 /* there are no fixed points */
1283 assert( invperm[i] != i );
1284
1285 /* get value of variable i and its inverse */
1286 solval = SCIPgetSolVal(scip, sol, vars[i]);
1287 assert( SCIPisFeasIntegral(scip, solval) );
1288 if ( solval > 0.5 )
1289 val1 = 1;
1290 else
1291 val1 = 0;
1292
1293 solval = SCIPgetSolVal(scip, sol, vars[invperm[i]]);
1294 assert( SCIPisFeasIntegral(scip, solval) );
1295 if ( solval > 0.5 )
1296 val2 = 1;
1297 else
1298 val2 = 0;
1299
1300 /* if we detected a constant pair */
1301 if ( val1 == val2 )
1302 continue;
1303 /* pair is (1,0) --> lexicographically maximal */
1304 else if ( val1 > val2 )
1305 break;
1306
1307 /* pair is (0,1) --> solution is infeasible */
1308 assert( val2 > val1 );
1309 SCIPdebugMsg(scip, "Solution is infeasible.\n");
1310 *result = SCIP_INFEASIBLE;
1311
1312 if ( printreason )
1313 SCIPinfoMessage(scip, NULL, "First non-constant pair (%d, %d) of variables has pattern (0,1).\n", i, invperm[i]);
1314
1315 break;
1316 }
1317
1318 return SCIP_OKAY;
1319 }
1320
1321
1322 /** Upgrade symresack constraints to orbisacks */
1323 static
orbisackUpgrade(SCIP * scip,SCIP_CONS ** cons,const char * name,int * perm,SCIP_VAR ** inputvars,int nvars,SCIP_Bool * upgrade,SCIP_Bool ismodelcons,SCIP_Bool initial,SCIP_Bool separate,SCIP_Bool enforce,SCIP_Bool check,SCIP_Bool propagate,SCIP_Bool local,SCIP_Bool modifiable,SCIP_Bool dynamic,SCIP_Bool removable,SCIP_Bool stickingatnode)1324 SCIP_RETCODE orbisackUpgrade(
1325 SCIP* scip, /**< SCIP pointer */
1326 SCIP_CONS** cons, /**< pointer to hold the created constraint */
1327 const char* name, /**< name of constraint */
1328 int* perm, /**< permutation */
1329 SCIP_VAR** inputvars, /**< permuted variables array */
1330 int nvars, /**< size of perm array */
1331 SCIP_Bool* upgrade, /**< whether constraint was upgraded */
1332 SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
1333 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1334 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1335 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1336 * Usually set to TRUE. */
1337 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1338 * TRUE for model constraints, FALSE for additional, redundant constraints. */
1339 SCIP_Bool check, /**< should the constraint be checked for feasibility?
1340 * TRUE for model constraints, FALSE for additional, redundant constraints. */
1341 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1342 * Usually set to TRUE. */
1343 SCIP_Bool local, /**< is constraint only valid locally?
1344 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1345 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1346 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1347 * adds coefficients to this constraint. */
1348 SCIP_Bool dynamic, /**< is constraint subject to aging?
1349 * Usually set to FALSE. Set to TRUE for own cuts which
1350 * are separated as constraints. */
1351 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1352 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1353 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1354 * if it may be moved to a more global node?
1355 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1356 )
1357 {
1358 SCIP_CONSHDLR* conshdlr;
1359 SCIP_VAR** vars1;
1360 SCIP_VAR** vars2;
1361 int nrows = 0;
1362 int i;
1363
1364 assert( scip != NULL );
1365 assert( perm != NULL );
1366 assert( nvars > 0 );
1367 assert( inputvars != NULL );
1368 assert( upgrade != NULL );
1369
1370 *upgrade = TRUE;
1371
1372 /* check whether orbisack conshdlr is available */
1373 conshdlr = SCIPfindConshdlr(scip, "orbisack");
1374 if ( conshdlr == NULL )
1375 {
1376 *upgrade = FALSE;
1377 SCIPdebugMsg(scip, "Cannot check whether symresack constraint can be upgraded to orbisack constraint. ");
1378 SCIPdebugMsg(scip, "---> Orbisack constraint handler not found.\n");
1379
1380 return SCIP_OKAY;
1381 }
1382
1383 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nvars) );
1384 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nvars) );
1385
1386 /* check whether permutation is a composition of 2-cycles */
1387 for (i = 0; i < nvars; ++i)
1388 {
1389 /* ignore non-binary variables */
1390 if ( ! SCIPvarIsBinary(inputvars[i]) )
1391 continue;
1392
1393 if ( perm[perm[i]] != i )
1394 {
1395 *upgrade = FALSE;
1396 break;
1397 }
1398
1399 if ( perm[i] > i )
1400 {
1401 vars1[nrows] = inputvars[i];
1402 vars2[nrows++] = inputvars[perm[i]];
1403
1404 assert( nrows <= nvars );
1405 }
1406 }
1407
1408 /* if permutation can be upgraded to an orbisack */
1409 if ( nrows == 0 )
1410 *upgrade = FALSE;
1411 else if ( *upgrade )
1412 {
1413 SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, ismodelcons,
1414 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1415 }
1416
1417 SCIPfreeBufferArray(scip, &vars2);
1418 SCIPfreeBufferArray(scip, &vars1);
1419
1420 return SCIP_OKAY;
1421 }
1422
1423
1424 /** creates a symmetry breaking constraint
1425 *
1426 * Depending on the given permutation, either an orbisack or symresack constraint
1427 * is created.
1428 */
SCIPcreateSymbreakCons(SCIP * scip,SCIP_CONS ** cons,const char * name,int * perm,SCIP_VAR ** vars,int nvars,SCIP_Bool ismodelcons,SCIP_Bool initial,SCIP_Bool separate,SCIP_Bool enforce,SCIP_Bool check,SCIP_Bool propagate,SCIP_Bool local,SCIP_Bool modifiable,SCIP_Bool dynamic,SCIP_Bool removable,SCIP_Bool stickingatnode)1429 SCIP_RETCODE SCIPcreateSymbreakCons(
1430 SCIP* scip, /**< SCIP data structure */
1431 SCIP_CONS** cons, /**< pointer to hold the created constraint */
1432 const char* name, /**< name of constraint */
1433 int* perm, /**< permutation */
1434 SCIP_VAR** vars, /**< variables */
1435 int nvars, /**< number of variables in vars array */
1436 SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */
1437 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1438 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1439 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1440 * Usually set to TRUE. */
1441 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1442 * TRUE for model constraints, FALSE for additional, redundant constraints. */
1443 SCIP_Bool check, /**< should the constraint be checked for feasibility?
1444 * TRUE for model constraints, FALSE for additional, redundant constraints. */
1445 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1446 * Usually set to TRUE. */
1447 SCIP_Bool local, /**< is constraint only valid locally?
1448 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1449 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1450 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1451 * adds coefficients to this constraint. */
1452 SCIP_Bool dynamic, /**< is constraint subject to aging?
1453 * Usually set to FALSE. Set to TRUE for own cuts which
1454 * are separated as constraints. */
1455 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1456 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1457 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1458 * if it may be moved to a more global node?
1459 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1460 )
1461 {
1462 SCIP_Bool upgrade = FALSE;
1463
1464 assert( scip != NULL );
1465 assert( cons != NULL );
1466 assert( perm != NULL );
1467 assert( vars != NULL );
1468 assert( nvars > 0 );
1469
1470 SCIP_CALL( orbisackUpgrade(scip, cons, name, perm, vars, nvars, &upgrade, ismodelcons,
1471 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1472
1473 if ( ! upgrade )
1474 {
1475 SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
1476 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1477 }
1478
1479 return SCIP_OKAY;
1480 }
1481
1482
1483 /*--------------------------------------------------------------------------------------------
1484 *--------------------------------- SCIP functions -------------------------------------------
1485 *--------------------------------------------------------------------------------------------*/
1486
1487 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1488 static
SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)1489 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
1490 { /*lint --e{715}*/
1491 assert(scip != NULL);
1492 assert(conshdlr != NULL);
1493 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1494
1495 /* call inclusion method of constraint handler */
1496 SCIP_CALL( SCIPincludeConshdlrSymresack(scip) );
1497
1498 *valid = TRUE;
1499
1500 return SCIP_OKAY;
1501 }
1502
1503
1504 /** frees specific constraint data */
1505 static
SCIP_DECL_CONSDELETE(consDeleteSymresack)1506 SCIP_DECL_CONSDELETE(consDeleteSymresack)
1507 { /*lint --e{715}*/
1508 assert( scip != NULL );
1509 assert( conshdlr != NULL );
1510 assert( consdata != NULL );
1511 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1512
1513 SCIP_CALL( consdataFree(scip, consdata) );
1514
1515 return SCIP_OKAY;
1516 }
1517
1518
1519 /** frees constraint handler */
1520 static
SCIP_DECL_CONSFREE(consFreeSymresack)1521 SCIP_DECL_CONSFREE(consFreeSymresack)
1522 { /*lint --e{715}*/
1523 SCIP_CONSHDLRDATA* conshdlrdata;
1524
1525 assert( scip != NULL );
1526 assert( conshdlr != NULL );
1527 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1528
1529 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1530 assert( conshdlrdata != NULL );
1531
1532 SCIPfreeBlockMemory(scip, &conshdlrdata);
1533
1534 return SCIP_OKAY;
1535 }
1536
1537
1538 /** transforms constraint data into data belonging to the transformed problem */
1539 static
SCIP_DECL_CONSTRANS(consTransSymresack)1540 SCIP_DECL_CONSTRANS(consTransSymresack)
1541 {
1542 SCIP_CONSDATA* sourcedata;
1543 SCIP_CONSDATA* consdata = NULL;
1544 int nvars;
1545 int i;
1546
1547 assert( scip != NULL );
1548 assert( conshdlr != NULL );
1549 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1550 assert( sourcecons != NULL );
1551 assert( targetcons != NULL );
1552
1553 SCIPdebugMsg(scip, "Transforming constraint.\n");
1554
1555 /* get data of original constraint */
1556 sourcedata = SCIPconsGetData(sourcecons);
1557 assert( sourcedata != NULL);
1558
1559 /* constraint might be empty and not deleted if no presolving took place */
1560 assert( sourcedata->nvars == 0 || sourcedata->vars != NULL );
1561 assert( sourcedata->nvars == 0 || sourcedata->perm != NULL );
1562 assert( sourcedata->nvars == 0 || sourcedata->invperm != NULL );
1563 #ifndef NDEBUG
1564 if ( sourcedata->ppupgrade )
1565 {
1566 assert( sourcedata->nvars > 0 );
1567 assert( sourcedata->ncycles != 0 );
1568 assert( sourcedata->cycledecomposition != NULL );
1569 for (i = 0; i < sourcedata->ncycles; ++i)
1570 {
1571 assert( sourcedata->cycledecomposition[i] != NULL );
1572 assert( sourcedata->cycledecomposition[i][0] != 0 );
1573 }
1574 }
1575 #endif
1576
1577 /* create transformed constraint data */
1578 nvars = sourcedata->nvars;
1579
1580 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1581
1582 consdata->vars = NULL;
1583 consdata->nvars = nvars;
1584 consdata->perm = NULL;
1585 consdata->invperm = NULL;
1586 consdata->ppupgrade = sourcedata->ppupgrade;
1587 consdata->ismodelcons = sourcedata->ismodelcons;
1588 #ifdef SCIP_DEBUG
1589 consdata->debugcnt = 0;
1590 #endif
1591 consdata->ncycles = 0;
1592 consdata->cycledecomposition = NULL;
1593 consdata->ndescentpoints = 0;
1594 consdata->descentpoints = NULL;
1595
1596 if ( nvars > 0 )
1597 {
1598 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
1599 SCIP_CALL( SCIPgetTransformedVars(scip, nvars, sourcedata->vars, consdata->vars) );
1600 for (i = 0; i < nvars; ++i)
1601 {
1602 SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
1603 }
1604
1605 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->perm, sourcedata->perm, nvars) );
1606 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->invperm, sourcedata->invperm, nvars) );
1607
1608 if ( sourcedata->ppupgrade )
1609 {
1610 consdata->ncycles = sourcedata->ncycles;
1611 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition, sourcedata->cycledecomposition, sourcedata->ncycles) );
1612 for (i = 0; i < sourcedata->ncycles; ++i)
1613 {
1614 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition[i], sourcedata->cycledecomposition[i], nvars + 1) ); /*lint !e866*/
1615 }
1616
1617 consdata->ndescentpoints = sourcedata->ndescentpoints;
1618 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->descentpoints, sourcedata->descentpoints, sourcedata->ndescentpoints) );
1619 }
1620 }
1621
1622 /* create transformed constraint */
1623 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1624 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1625 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1626 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1627 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1628 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1629
1630 return SCIP_OKAY;
1631 }
1632
1633
1634 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1635 static
SCIP_DECL_CONSINITLP(consInitlpSymresack)1636 SCIP_DECL_CONSINITLP(consInitlpSymresack)
1637 {
1638 int c;
1639 SCIP_CONSHDLRDATA* conshdlrdata;
1640
1641 assert( infeasible != NULL );
1642 *infeasible = FALSE;
1643
1644 assert( scip != NULL );
1645 assert( conshdlr != NULL );
1646 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1647
1648 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1649 assert( conshdlrdata != NULL );
1650
1651 /* loop through constraints */
1652 for (c = 0; c < nconss; ++c)
1653 {
1654 assert( conss[c] != NULL );
1655
1656 SCIPdebugMsg(scip, "Generating initial symresack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1657
1658 SCIP_CALL( initLP(scip, conss[c], conshdlrdata->checkmonotonicity, infeasible) );
1659 if ( *infeasible )
1660 break;
1661 }
1662 SCIPdebugMsg(scip, "Generated initial symresack cuts.\n");
1663
1664 return SCIP_OKAY;
1665 }
1666
1667
1668 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1669 static
SCIP_DECL_CONSINITSOL(consInitsolSymresack)1670 SCIP_DECL_CONSINITSOL(consInitsolSymresack)
1671 {
1672 SCIP_CONSHDLRDATA* conshdlrdata;
1673 int c;
1674
1675 assert( scip != NULL );
1676 assert( conshdlr != NULL );
1677 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1678
1679 /* determine maximum number of vars in a symresack constraint */
1680 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1681 assert( conshdlrdata != NULL );
1682
1683 conshdlrdata->maxnvars = 0;
1684
1685 /* loop through constraints */
1686 for (c = 0; c < nconss; ++c)
1687 {
1688 SCIP_CONSDATA* consdata;
1689
1690 assert( conss[c] != NULL );
1691
1692 consdata = SCIPconsGetData(conss[c]);
1693 assert( consdata != NULL );
1694
1695 /* update conshdlrdata if necessary */
1696 if ( consdata->nvars > conshdlrdata->maxnvars )
1697 conshdlrdata->maxnvars = consdata->nvars;
1698 }
1699
1700 return SCIP_OKAY;
1701 }
1702
1703
1704 /** separation method of constraint handler for LP solution */
1705 static
SCIP_DECL_CONSSEPALP(consSepalpSymresack)1706 SCIP_DECL_CONSSEPALP(consSepalpSymresack)
1707 { /*lint --e{715}*/
1708 SCIP_CONSHDLRDATA* conshdlrdata;
1709 SCIP_CONSDATA* consdata;
1710 SCIP_Real* vals;
1711 int maxnvars;
1712 int c;
1713
1714 assert( scip != NULL );
1715 assert( conshdlr != NULL );
1716 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1717 assert( result != NULL );
1718
1719 SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
1720
1721 *result = SCIP_DIDNOTRUN;
1722
1723 /* if solution is not integer */
1724 if ( SCIPgetNLPBranchCands(scip) == 0 )
1725 return SCIP_OKAY;
1726
1727 if ( nconss == 0 )
1728 return SCIP_OKAY;
1729
1730 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1731 assert( conshdlrdata != NULL );
1732
1733 maxnvars = conshdlrdata->maxnvars;
1734 assert( maxnvars > 0 );
1735
1736 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1737
1738 /* loop through constraints */
1739 for (c = 0; c < nconss; ++c)
1740 {
1741 SCIP_Bool infeasible = FALSE;
1742 int ngen = 0;
1743
1744 SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1745
1746 /* get data of constraint */
1747 assert( conss[c] != NULL );
1748 consdata = SCIPconsGetData(conss[c]);
1749
1750 if ( consdata->nvars == 0 )
1751 continue;
1752
1753 /* get solution */
1754 assert( consdata->nvars <= maxnvars );
1755 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
1756 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1757
1758 if ( infeasible )
1759 {
1760 *result = SCIP_CUTOFF;
1761 SCIPfreeBufferArray(scip, &vals);
1762
1763 return SCIP_OKAY;
1764 }
1765
1766 if ( ngen > 0 )
1767 *result = SCIP_SEPARATED;
1768
1769 if ( *result == SCIP_DIDNOTRUN )
1770 *result = SCIP_DIDNOTFIND;
1771 }
1772 SCIPfreeBufferArray(scip, &vals);
1773
1774 return SCIP_OKAY;
1775 }
1776
1777
1778 /** separation method of constraint handler for arbitrary primal solution */
1779 static
SCIP_DECL_CONSSEPASOL(consSepasolSymresack)1780 SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
1781 { /*lint --e{715}*/
1782 SCIP_CONSHDLRDATA* conshdlrdata;
1783 SCIP_CONSDATA* consdata;
1784 SCIP_Real* vals;
1785 int maxnvars;
1786 int c;
1787
1788 assert( scip != NULL );
1789 assert( conshdlr != NULL );
1790 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1791 assert( result != NULL );
1792
1793 SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
1794
1795 *result = SCIP_DIDNOTRUN;
1796
1797 if ( nconss == 0 )
1798 return SCIP_OKAY;
1799
1800 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1801 assert( conshdlrdata != NULL );
1802
1803 maxnvars = conshdlrdata->maxnvars;
1804 assert( maxnvars > 0 );
1805
1806 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1807
1808 /* loop through constraints */
1809 for (c = 0; c < nconss; ++c)
1810 {
1811 SCIP_Bool infeasible = FALSE;
1812 int ngen = 0;
1813
1814 SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1815
1816 /* get data of constraint */
1817 assert( conss[c] != NULL );
1818 consdata = SCIPconsGetData(conss[c]);
1819
1820 if ( consdata->nvars == 0 )
1821 continue;
1822
1823 /* get solution */
1824 assert( consdata->nvars <= maxnvars );
1825 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
1826 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1827
1828 if ( infeasible )
1829 {
1830 *result = SCIP_CUTOFF;
1831 SCIPfreeBufferArray(scip, &vals);
1832
1833 return SCIP_OKAY;
1834 }
1835
1836 if ( ngen > 0 )
1837 *result = SCIP_SEPARATED;
1838
1839 if ( *result == SCIP_DIDNOTRUN )
1840 *result = SCIP_DIDNOTFIND;
1841 }
1842 SCIPfreeBufferArray(scip, &vals);
1843
1844 return SCIP_OKAY;
1845 }
1846
1847
1848 /** constraint enforcing method of constraint handler for LP solutions.
1849 *
1850 * To check feasibility, we separate cover inequalities.
1851 *
1852 * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
1853 */
1854 static
SCIP_DECL_CONSENFOLP(consEnfolpSymresack)1855 SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
1856 { /*lint --e{715}*/
1857 SCIP_CONSDATA* consdata;
1858 int c;
1859
1860 assert( scip != NULL );
1861 assert( conshdlr != NULL );
1862 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1863 assert( result != NULL );
1864
1865 SCIPdebugMsg(scip, "Enforcing method for symresack constraints (lp solutions) ...\n");
1866
1867 /* we have a negative priority, so we should come after the integrality conshdlr. */
1868 assert( SCIPgetNLPBranchCands(scip) == 0 );
1869
1870 *result = SCIP_FEASIBLE;
1871
1872 if ( nconss > 0 )
1873 {
1874 SCIP_CONSHDLRDATA* conshdlrdata;
1875 SCIP_Real* vals;
1876 int maxnvars;
1877
1878 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1879 assert( conshdlrdata != NULL );
1880
1881 maxnvars = conshdlrdata->maxnvars;
1882 assert( maxnvars > 0 );
1883
1884 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1885
1886 /* loop through constraints */
1887 for (c = 0; c < nconss; ++c)
1888 {
1889 SCIP_Bool infeasible = FALSE;
1890 int ngen = 0;
1891
1892 SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1893
1894 /* get data of constraint */
1895 assert( conss[c] != NULL );
1896 consdata = SCIPconsGetData(conss[c]);
1897 assert( consdata != NULL );
1898
1899 /* do not enforce non-model constraints */
1900 if ( !consdata->ismodelcons )
1901 continue;
1902
1903 if ( consdata->nvars == 0 )
1904 continue;
1905
1906 /* get solution */
1907 assert( consdata->nvars <= maxnvars );
1908 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
1909 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1910
1911 if ( infeasible )
1912 {
1913 *result = SCIP_CUTOFF;
1914 SCIPfreeBufferArray(scip, &vals);
1915
1916 return SCIP_OKAY;
1917 }
1918
1919 /* SCIPdebugMsg(scip, "Generated symresack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); */
1920
1921 if ( ngen > 0 )
1922 *result = SCIP_SEPARATED;
1923 }
1924 SCIPfreeBufferArray(scip, &vals);
1925 }
1926
1927 return SCIP_OKAY;
1928 }
1929
1930
1931 /** constraint enforcing method of constraint handler for pseudo solutions */
1932 static
SCIP_DECL_CONSENFOPS(consEnfopsSymresack)1933 SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
1934 { /*lint --e{715}*/
1935 SCIP_CONSDATA* consdata;
1936 int c;
1937
1938 assert( scip != NULL );
1939 assert( conshdlr != NULL );
1940 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1941 assert( result != NULL );
1942
1943 SCIPdebugMsg(scip, "Enforcing method for symresack constraints (pseudo solutions) ...\n");
1944
1945 *result = SCIP_FEASIBLE;
1946
1947 if ( objinfeasible || solinfeasible )
1948 return SCIP_OKAY;
1949
1950 /* loop through constraints */
1951 for (c = 0; c < nconss; ++c)
1952 {
1953 consdata = SCIPconsGetData(conss[c]);
1954 assert( consdata != NULL );
1955
1956 /* do not enforce non-model constraints */
1957 if ( !consdata->ismodelcons )
1958 continue;
1959
1960 SCIP_CALL( checkSymresackSolution(scip, conss[c], NULL, result, FALSE) );
1961
1962 if ( *result == SCIP_INFEASIBLE )
1963 break;
1964 }
1965
1966 return SCIP_OKAY;
1967 }
1968
1969
1970 /** constraint enforcing method of constraint handler for relaxation solutions
1971 *
1972 * To check feasibility, we separate cover inequalities.
1973 *
1974 */
1975 static
SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)1976 SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
1977 { /*lint --e{715}*/
1978 SCIP_CONSDATA* consdata;
1979 int c;
1980
1981 assert( scip != NULL );
1982 assert( conshdlr != NULL );
1983 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1984 assert( result != NULL );
1985
1986 SCIPdebugMsg(scip, "Enforcing method for symresack constraints (relaxation solutions) ...\n");
1987
1988 /* we have a negative priority, so we should come after the integrality conshdlr. */
1989 assert( SCIPgetNLPBranchCands(scip) == 0 );
1990
1991 *result = SCIP_FEASIBLE;
1992
1993 if ( nconss > 0 )
1994 {
1995 SCIP_CONSHDLRDATA* conshdlrdata;
1996 SCIP_Real* vals;
1997 int maxnvars;
1998
1999 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2000 assert( conshdlrdata != NULL );
2001
2002 maxnvars = conshdlrdata->maxnvars;
2003 assert( maxnvars > 0 );
2004
2005 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2006
2007 /* loop through constraints */
2008 for (c = 0; c < nconss; ++c)
2009 {
2010 SCIP_Bool infeasible = FALSE;
2011 int ngen = 0;
2012
2013 SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2014
2015 /* get data of constraint */
2016 assert( conss[c] != NULL );
2017 consdata = SCIPconsGetData(conss[c]);
2018 assert( consdata != NULL );
2019
2020 /* do not enforce non-model constraints */
2021 if ( !consdata->ismodelcons )
2022 continue;
2023
2024 if ( consdata->nvars == 0 )
2025 continue;
2026
2027 /* get solution */
2028 assert( consdata->nvars <= maxnvars );
2029 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
2030 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2031
2032 if ( infeasible )
2033 {
2034 *result = SCIP_CUTOFF;
2035 SCIPfreeBufferArray(scip, &vals);
2036
2037 return SCIP_OKAY;
2038 }
2039
2040 if ( ngen > 0 )
2041 *result = SCIP_SEPARATED;
2042 }
2043 SCIPfreeBufferArray(scip, &vals);
2044 }
2045
2046 return SCIP_OKAY;
2047 }
2048
2049
2050 /** feasibility check method of constraint handler for integral solutions */
2051 static
SCIP_DECL_CONSCHECK(consCheckSymresack)2052 SCIP_DECL_CONSCHECK(consCheckSymresack)
2053 { /*lint --e{715}*/
2054 SCIP_CONSDATA* consdata;
2055 int c;
2056
2057 assert( scip != NULL );
2058 assert( conshdlr != NULL );
2059 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2060 assert( result != NULL );
2061
2062 *result = SCIP_FEASIBLE;
2063
2064 /* loop through constraints */
2065 for (c = 0; c < nconss; ++c)
2066 {
2067 consdata = SCIPconsGetData(conss[c]);
2068 assert( consdata != NULL );
2069
2070 /* do not check non-model constraints */
2071 if ( !consdata->ismodelcons )
2072 continue;
2073
2074 SCIP_CALL( checkSymresackSolution(scip, conss[c], sol, result, printreason) );
2075
2076 if ( *result == SCIP_INFEASIBLE )
2077 break;
2078 }
2079
2080 if ( *result == SCIP_FEASIBLE )
2081 SCIPdebugMsg(scip, "Solution is feasible.\n");
2082
2083 return SCIP_OKAY;
2084 }
2085
2086
2087 /** domain propagation method of constraint handler */
2088 static
SCIP_DECL_CONSPROP(consPropSymresack)2089 SCIP_DECL_CONSPROP(consPropSymresack)
2090 { /*lint --e{715}*/
2091 int c;
2092 SCIP_Bool success = FALSE;
2093
2094 assert( scip != NULL );
2095 assert( conshdlr != NULL );
2096 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2097 assert( result != NULL );
2098
2099 *result = SCIP_DIDNOTRUN;
2100
2101 SCIPdebugMsg(scip, "Propagation method of symresack constraint handler.\n");
2102
2103 /* loop through constraints */
2104 for (c = 0; c < nconss; ++c)
2105 {
2106 SCIP_Bool infeasible = FALSE;
2107 int ngen = 0;
2108
2109 assert( conss[c] != NULL );
2110
2111 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2112
2113 if ( infeasible )
2114 {
2115 *result = SCIP_CUTOFF;
2116 return SCIP_OKAY;
2117 }
2118
2119 success = success || ( ngen > 0 );
2120
2121 *result = SCIP_DIDNOTFIND;
2122 }
2123
2124 if ( success )
2125 {
2126 *result = SCIP_REDUCEDDOM;
2127 return SCIP_OKAY;
2128 }
2129
2130 return SCIP_OKAY;
2131 }
2132
2133
2134 /** presolving method of constraint handler */
2135 static
SCIP_DECL_CONSPRESOL(consPresolSymresack)2136 SCIP_DECL_CONSPRESOL(consPresolSymresack)
2137 { /*lint --e{715}*/
2138 int c;
2139 SCIP_Bool success = FALSE;
2140 int oldndelconss;
2141
2142 assert( scip != NULL );
2143 assert( conshdlr != NULL );
2144 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2145 assert( result != NULL );
2146
2147 oldndelconss = *ndelconss;
2148
2149 SCIPdebugMsg(scip, "Presolving method of symresack constraint handler. Propagating symresack inequalities.\n");
2150 *result = SCIP_DIDNOTRUN;
2151
2152 /* loop through constraints */
2153 for (c = 0; c < nconss; ++c)
2154 {
2155 SCIP_Bool infeasible = FALSE;
2156 SCIP_CONSDATA* consdata;
2157 int ngen = 0;
2158
2159 assert( conss[c] != NULL );
2160
2161 consdata = SCIPconsGetData(conss[c]);
2162 assert( consdata != NULL );
2163
2164 /* avoid trivial problems */
2165 if ( consdata->nvars == 0 )
2166 {
2167 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2168 (*ndelconss)++;
2169 }
2170 else
2171 {
2172 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2173 }
2174
2175 if ( infeasible )
2176 {
2177 *result = SCIP_CUTOFF;
2178 break;
2179 }
2180
2181 if ( ngen > 0 )
2182 {
2183 *nfixedvars += ngen;
2184 success = TRUE;
2185 }
2186
2187 *result = SCIP_DIDNOTFIND;
2188 }
2189
2190 if ( *ndelconss > oldndelconss || success )
2191 *result = SCIP_SUCCESS;
2192
2193 return SCIP_OKAY;
2194 }
2195
2196
2197 /** Propagation resolution for conflict analysis */
2198 static
SCIP_DECL_CONSRESPROP(consRespropSymresack)2199 SCIP_DECL_CONSRESPROP(consRespropSymresack)
2200 { /*lint --e{715}*/
2201 SCIP_CONSDATA* consdata;
2202 SCIP_VAR** vars;
2203 int* invperm;
2204 int nvars;
2205 int i;
2206
2207 assert( scip != NULL );
2208 assert( conshdlr != NULL );
2209 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2210 assert( cons != NULL );
2211 assert( infervar != NULL );
2212 assert( bdchgidx != NULL );
2213 assert( result != NULL );
2214
2215 SCIPdebugMsg(scip, "Propagation resolution method of symresack constraint handler.\n");
2216
2217 *result = SCIP_DIDNOTFIND;
2218
2219 consdata = SCIPconsGetData(cons);
2220 assert( consdata != NULL );
2221
2222 /* we do not have to take care of trivial constraints */
2223 if ( consdata->nvars < 2 )
2224 return SCIP_OKAY;
2225
2226 assert( consdata->vars != NULL );
2227 assert( consdata->invperm != NULL );
2228
2229 vars = consdata->vars;
2230 nvars = consdata->nvars;
2231 invperm = consdata->invperm;
2232
2233 assert( 0 <= inferinfo && inferinfo < (2 * nvars - 1) );
2234
2235 /* if first part of variable pair was fixed to 0 */
2236 if ( inferinfo < nvars )
2237 {
2238 assert( vars[invperm[inferinfo]] == infervar );
2239 assert( SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, FALSE) > 0.5
2240 && SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, TRUE) < 0.5 );
2241
2242 if ( SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, FALSE) > 0.5
2243 && SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, TRUE) < 0.5 )
2244 {
2245 SCIPdebugMsg(scip, " -> reason for setting x[%d] = 0 was fixing x[%d] to 0 ", invperm[inferinfo], inferinfo);
2246 SCIPdebugMsg(scip, "and each pair of binary variables before (%d,%d) which are not fixed points is constant.\n",
2247 inferinfo, invperm[inferinfo]);
2248
2249 SCIP_CALL( SCIPaddConflictUb(scip, vars[inferinfo], bdchgidx) );
2250
2251 for (i = 0; i < inferinfo; ++i)
2252 {
2253 /* there are no fixed points */
2254 assert( invperm[i] != i );
2255
2256 SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2257 SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2258 SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2259 SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2260 }
2261 }
2262 }
2263 /* if second part of variable pair was fixed to 1 */
2264 else
2265 {
2266 int inferinfo2;
2267
2268 inferinfo2 = inferinfo - nvars;
2269 assert( vars[inferinfo2] == infervar );
2270 assert( SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, FALSE) < 0.5
2271 && SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, TRUE) > 0.5 );
2272
2273 if ( SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, FALSE) < 0.5
2274 && SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, TRUE) > 0.5 )
2275 {
2276 SCIPdebugMsg(scip, " -> reason for setting x[%d] = 1 was fixing x[%d] to 1 ", inferinfo2, invperm[inferinfo2]);
2277 SCIPdebugMsg(scip, "and each pair of binary variables before (%d,%d) which are not fixed points is constant.\n",
2278 inferinfo2, invperm[inferinfo2]);
2279
2280 SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[inferinfo2]], bdchgidx) );
2281
2282 for (i = 0; i < inferinfo2; ++i)
2283 {
2284 /* there are no fixed points */
2285 assert( invperm[i] != i );
2286
2287 SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2288 SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2289 SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2290 SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2291 }
2292 }
2293 }
2294
2295 *result = SCIP_SUCCESS;
2296
2297 return SCIP_OKAY;
2298 }
2299
2300
2301 /** lock variables
2302 *
2303 * We assume we have only one global (void) constraint and lock all binary variables
2304 * which do not correspond to fixed points of the permutation.
2305 *
2306 * - Symresack constraints may get violated if the variables with a negative coefficient
2307 * in the FD inequality are rounded down, we therefor call
2308 * SCIPaddVarLocksType(..., nlockspos, nlocksneg).
2309 * - Symresack constraints may get violated if the variables with a positive coefficient
2310 * in the FD inequality are rounded up, we therefor call
2311 * SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
2312 */
2313 static
SCIP_DECL_CONSLOCK(consLockSymresack)2314 SCIP_DECL_CONSLOCK(consLockSymresack)
2315 { /*lint --e{715}*/
2316 SCIP_CONSDATA* consdata;
2317 SCIP_VAR** vars;
2318 int* perm;
2319 int nvars;
2320 int i;
2321
2322 assert( scip != NULL );
2323 assert( conshdlr != NULL );
2324 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2325 assert( cons != NULL );
2326
2327 SCIPdebugMsg(scip, "Locking method for symresack constraint handler.\n");
2328
2329 /* get data of original constraint */
2330 consdata = SCIPconsGetData(cons);
2331 assert( consdata != NULL );
2332
2333 /* we do not have to take care of trivial constraints */
2334 if ( consdata->nvars < 2 )
2335 return SCIP_OKAY;
2336
2337 assert( consdata->vars != NULL );
2338 assert( consdata->perm != NULL );
2339
2340 nvars = consdata->nvars;
2341 vars = consdata->vars;
2342 perm = consdata->perm;
2343
2344 for (i = 0; i < nvars; ++i)
2345 {
2346 /* due to clean-up in consdataCreate, there are no fixed points */
2347 assert( perm[i] != i );
2348
2349 if ( perm[i] > i )
2350 {
2351 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlockspos, nlocksneg) );
2352 }
2353 else
2354 {
2355 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlocksneg, nlockspos) );
2356 }
2357 }
2358
2359 return SCIP_OKAY;
2360 }
2361
2362
2363 /** constraint copying method of constraint handler */
2364 static
SCIP_DECL_CONSCOPY(consCopySymresack)2365 SCIP_DECL_CONSCOPY(consCopySymresack)
2366 {
2367 SCIP_CONSHDLRDATA* conshdlrdata;
2368 SCIP_CONSDATA* sourcedata;
2369 SCIP_VAR** sourcevars;
2370 SCIP_VAR** vars;
2371 int nvars;
2372 int i;
2373
2374 assert( scip != NULL );
2375 assert( cons != NULL );
2376 assert( sourcescip != NULL );
2377 assert( sourceconshdlr != NULL );
2378 assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2379 assert( sourcecons != NULL );
2380 assert( varmap != NULL );
2381 assert( valid != NULL );
2382
2383 *valid = TRUE;
2384
2385 SCIPdebugMsg(scip, "Copying method for symresack constraint handler.\n");
2386
2387 sourcedata = SCIPconsGetData(sourcecons);
2388 assert( sourcedata != NULL );
2389 assert( sourcedata->vars != NULL );
2390 assert( sourcedata->perm != NULL );
2391 assert( sourcedata->nvars > 0 );
2392
2393 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
2394 assert( conshdlrdata != NULL );
2395
2396 /* do not copy non-model constraints */
2397 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
2398 {
2399 *valid = FALSE;
2400
2401 return SCIP_OKAY;
2402 }
2403
2404 sourcevars = sourcedata->vars;
2405 nvars = sourcedata->nvars;
2406
2407 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2408
2409 for (i = 0; i < nvars && *valid; ++i)
2410 {
2411 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i], &(vars[i]), varmap, consmap, global, valid) );
2412 assert( !(*valid) || vars[i] != NULL );
2413 }
2414
2415 /* only create the target constraint, if all variables could be copied */
2416 if ( *valid )
2417 {
2418 /* create copied constraint */
2419 if ( name == NULL )
2420 name = SCIPconsGetName(sourcecons);
2421
2422 SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, sourcedata->perm, vars, nvars, sourcedata->ismodelcons,
2423 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2424 }
2425
2426 SCIPfreeBufferArray(scip, &vars);
2427
2428 return SCIP_OKAY;
2429 }
2430
2431
2432 /** constraint display method of constraint handler
2433 *
2434 * The constraint handler should output a representation of the constraint into the given text file.
2435 */
2436 static
SCIP_DECL_CONSPRINT(consPrintSymresack)2437 SCIP_DECL_CONSPRINT(consPrintSymresack)
2438 { /*lint --e{715}*/
2439 SCIP_CONSDATA* consdata;
2440 SCIP_VAR** vars;
2441 SCIP_Bool* covered;
2442 int* perm;
2443 int nvars;
2444 int i;
2445 int j;
2446
2447 assert( scip != NULL );
2448 assert( conshdlr != NULL );
2449 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2450 assert( cons != NULL );
2451
2452 consdata = SCIPconsGetData(cons);
2453 assert( consdata != NULL );
2454
2455 SCIPdebugMsg(scip, "Printing method for symresack constraint handler\n");
2456
2457 /* we do not have to take care of trivial constraints */
2458 if ( consdata->nvars < 2 )
2459 {
2460 SCIPinfoMessage(scip, file, "symresack()");
2461 return SCIP_OKAY;
2462 }
2463
2464 assert( consdata->vars != NULL );
2465 assert( consdata->perm != NULL );
2466
2467 vars = consdata->vars;
2468 nvars = consdata->nvars;
2469 perm = consdata->perm;
2470
2471 SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
2472 for (i = 0; i < nvars; ++i)
2473 covered[i] = FALSE;
2474
2475 if ( consdata->ppupgrade )
2476 SCIPinfoMessage(scip, file, "ppSymresack(");
2477 else
2478 SCIPinfoMessage(scip, file, "symresack(");
2479
2480 for (i = 0; i < nvars; ++i)
2481 {
2482 if ( covered[i] )
2483 continue;
2484
2485 /* print cycle of perm containing i */
2486 SCIPinfoMessage(scip, file, "[%s", SCIPvarGetName(vars[i]));
2487 covered[i] = TRUE;
2488 j = perm[i];
2489 while ( j != i )
2490 {
2491 SCIPinfoMessage(scip, file, ",%s", SCIPvarGetName(vars[j]));
2492 covered[j] = TRUE;
2493 j = perm[j];
2494 }
2495 SCIPinfoMessage(scip, file, "]");
2496 }
2497 SCIPinfoMessage(scip, file, ")");
2498
2499 SCIPfreeBufferArray(scip, &covered);
2500
2501 return SCIP_OKAY;
2502 }
2503
2504
2505 /** constraint method of constraint handler which returns the variables (if possible) */
2506 static
SCIP_DECL_CONSGETVARS(consGetVarsSymresack)2507 SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
2508 { /*lint --e{715}*/
2509 SCIP_CONSDATA* consdata;
2510
2511 assert( cons != NULL );
2512 assert( success != NULL );
2513 assert( vars != NULL );
2514
2515 consdata = SCIPconsGetData(cons);
2516 assert( consdata != NULL );
2517
2518 if ( varssize < consdata->nvars )
2519 (*success) = FALSE;
2520 else
2521 {
2522 int cnt = 0;
2523 int i;
2524
2525 for (i = 0; i < consdata->nvars; ++i)
2526 vars[cnt++] = consdata->vars[i];
2527 (*success) = TRUE;
2528 }
2529
2530 return SCIP_OKAY;
2531 }
2532
2533
2534 /** constraint method of constraint handler which returns the number of variables (if possible) */
2535 static
SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)2536 SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
2537 { /*lint --e{715}*/
2538 SCIP_CONSDATA* consdata;
2539
2540 assert( cons != NULL );
2541 assert( success != NULL );
2542 assert( nvars != NULL );
2543
2544 consdata = SCIPconsGetData(cons);
2545 assert( consdata != NULL );
2546
2547 (*nvars) = consdata->nvars;
2548 (*success) = TRUE;
2549
2550 return SCIP_OKAY;
2551 }
2552
2553
2554 /** creates the handler for symresack constraints and includes it in SCIP */
SCIPincludeConshdlrSymresack(SCIP * scip)2555 SCIP_RETCODE SCIPincludeConshdlrSymresack(
2556 SCIP* scip /**< SCIP data structure */
2557 )
2558 {
2559 SCIP_CONSHDLRDATA* conshdlrdata = NULL;
2560 SCIP_CONSHDLR* conshdlr;
2561
2562 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2563
2564 /* include constraint handler */
2565 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2566 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2567 consEnfolpSymresack, consEnfopsSymresack, consCheckSymresack, consLockSymresack,
2568 conshdlrdata) );
2569 assert( conshdlr != NULL );
2570
2571 /* set non-fundamental callbacks via specific setter functions */
2572 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySymresack, consCopySymresack) );
2573 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSymresack) );
2574 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSymresack) );
2575 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSymresack) );
2576 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSymresack) );
2577 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSymresack) );
2578 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSymresack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2579 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSymresack) );
2580 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSymresack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
2581 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSymresack) );
2582 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSymresack, consSepasolSymresack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2583 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSymresack) );
2584 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSymresack) );
2585 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSymresack) );
2586
2587 /* whether we allow upgrading to packing/partioning symresack constraints*/
2588 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/ppsymresack",
2589 "Upgrade symresack constraints to packing/partioning symresacks?",
2590 &conshdlrdata->checkppsymresack, TRUE, DEFAULT_PPSYMRESACK, NULL, NULL) );
2591
2592 /* whether we check for monotonicity of perm when upgrading to packing/partioning symresacks */
2593 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkmonotonicity",
2594 "Check whether permutation is monotone when upgrading to packing/partioning symresacks?",
2595 &conshdlrdata->checkmonotonicity, TRUE, DEFAULT_CHECKMONOTONICITY, NULL, NULL) );
2596
2597 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
2598 "Whether symresack constraints should be forced to be copied to sub SCIPs.",
2599 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
2600
2601 return SCIP_OKAY;
2602 }
2603
2604
2605 /*
2606 * constraint specific interface methods
2607 */
2608
2609 /** creates and captures a symresack constraint
2610 *
2611 * In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate
2612 * the non-binary variables from the permutation.
2613 *
2614 * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
2615 */
SCIPcreateConsSymresack(SCIP * scip,SCIP_CONS ** cons,const char * name,int * perm,SCIP_VAR ** vars,int nvars,SCIP_Bool ismodelcons,SCIP_Bool initial,SCIP_Bool separate,SCIP_Bool enforce,SCIP_Bool check,SCIP_Bool propagate,SCIP_Bool local,SCIP_Bool modifiable,SCIP_Bool dynamic,SCIP_Bool removable,SCIP_Bool stickingatnode)2616 SCIP_RETCODE SCIPcreateConsSymresack(
2617 SCIP* scip, /**< SCIP data structure */
2618 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2619 const char* name, /**< name of constraint */
2620 int* perm, /**< permutation */
2621 SCIP_VAR** vars, /**< variables */
2622 int nvars, /**< number of variables in vars array */
2623 SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
2624 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2625 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2626 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2627 * Usually set to TRUE. */
2628 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2629 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2630 SCIP_Bool check, /**< should the constraint be checked for feasibility?
2631 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2632 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2633 * Usually set to TRUE. */
2634 SCIP_Bool local, /**< is constraint only valid locally?
2635 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2636 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2637 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2638 * adds coefficients to this constraint. */
2639 SCIP_Bool dynamic, /**< is constraint subject to aging?
2640 * Usually set to FALSE. Set to TRUE for own cuts which
2641 * are separated as constraints. */
2642 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2643 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2644 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2645 * if it may be moved to a more global node?
2646 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2647 )
2648 {
2649 SCIP_CONSHDLR* conshdlr;
2650 SCIP_CONSDATA* consdata;
2651
2652 assert( cons != NULL );
2653 assert( nvars > 0 );
2654
2655 /* find the symresack constraint handler */
2656 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2657 if ( conshdlr == NULL )
2658 {
2659 SCIPerrorMessage("Symresack constraint handler not found.\n");
2660 return SCIP_PLUGINNOTFOUND;
2661 }
2662
2663 /* create constraint data */
2664 SCIP_CALL( consdataCreate(scip, conshdlr, &consdata, vars, nvars, perm, ismodelcons) );
2665
2666 /* create constraint */
2667 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate && (! consdata->ppupgrade), enforce, check, propagate,
2668 local, modifiable, dynamic, removable, stickingatnode) );
2669
2670 return SCIP_OKAY;
2671 }
2672
2673
2674 /** creates and captures a symresack constraint
2675 * in its most basic variant, i.e., with all constraint flags set to their default values
2676 *
2677 * In a presolving step, we remove all fixed points and cycles that act on non-binary variables of the permutation
2678 *
2679 * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
2680 */
SCIPcreateConsBasicSymresack(SCIP * scip,SCIP_CONS ** cons,const char * name,int * perm,SCIP_VAR ** vars,int nvars,SCIP_Bool ismodelcons)2681 SCIP_RETCODE SCIPcreateConsBasicSymresack(
2682 SCIP* scip, /**< SCIP data structure */
2683 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2684 const char* name, /**< name of constraint */
2685 int* perm, /**< permutation */
2686 SCIP_VAR** vars, /**< variables */
2687 int nvars, /**< number of variables in vars array */
2688 SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
2689 )
2690 {
2691 SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
2692 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2693
2694 return SCIP_OKAY;
2695 }
2696