SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
symmetry_orbitopal.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 symmetry_orbitopal.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for handling orbitopal symmetries
28 * @author Jasper van Doornmalen
29 *
30 * This implements orbitopal reducion, which generalizes full orbitope propagation to work for non-binary variable
31 * domains, and is dynamified. See cons_orbitope.c for the variant for binary variables, both the static and partially
32 * dynamic variant.
33 * Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables
34 * branched on from the root node to the focus node.
35 *
36 * See Section 4.2, Example 12 and Section 5.1 in [vD,H]:@n
37 * J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023,
38 * https://doi.org/10.48550/arXiv.2211.01295.
39 *
40 * Orbitopal reduction can be used to handle symmetries of the following type.
41 * If the variables can be arranged in a matrix and the symmetries correspond to all column permutations of this matrix,
42 * then these symmetries are called orbitopal.
43 * Symmetry is completely handled by enforcing that the columns are lexicographically decreasing.
44 * If a reduction on a variable is applied, and if this variable is high up in the variable matrix, then this has a
45 * relatively large impact on the lexicographic ordering. Moreover, the ordering of the columns also matter.
46 * Dynamification allows for choosing a custom ordering of a subset of rows and a permutation of the columns.
47 * For every node, we maintain the ordered subset of rows and the column order.
48 * The root node assumes no rows and an arbitrary column order (we choose the identity).
49 * If towards a new node it is branched on a variable, that appears in a row which is not included in the subset of
50 * rows for the current node, then the row set of the new children is the ordered row set of the current node, appended
51 * by this new row.
52 * For the column order, if at the current node columns are symmetrically equivalent, then these can be permuted for
53 * the sake of symmetry handling. In the implementation, we only swap the column containing the branching variable
54 * with a symmetrically equivalent column elsewhere. We use one of the following heuristics:
55 *
56 * - None: Keep the column-order as-is.
57 * - First: Permute such that the column containing the branching variable is in the symmetrically equivalent column
58 * with minimal index.
59 * - Last: The same, but to the symmetrically equivalent column with maximal index.
60 * - Centre: The same, but to the symmetrically equivalent column closest to to the middlemost column among all columns.
61 * - Median: The same, but to the median of all symmetrically equivalent columns. (This is the default)
62 *
63 * Since the dynamic row and column ordering rule for a branch-and-bound tree node depends on the decisions made up to
64 * that branch-and-bound tree node, we compute and store the row and column order for the branch-and-bound tree children
65 * at the moment of branching. This is done by the eventhandler in this file.
66 * Instead of storing those, we could have chosen to reconstruct this row and column ordering to save memory.
67 * However, we cannot reliably reconstruct this order from the branch-and-bound tree itself,
68 * because the row and column ordering depends on symmetrical equivalence of columns in the orbitope matrix,
69 * and because SCIP can change the tree structure during solving that may re-write historic variable bound changes
70 * (for instance when global variable bound changes are found, or when the root node is moved down the tree to become
71 * the new effective root node).
72 * We are not concerned about storing the row and column ordering, since we only store the mutations with its parent.
73 * These are usually at most one column swap and usually at most one additional row.
74 *
75 * @todo Exploiting packing-partitioning structures
76 * @todo for packing-partitioning rows, use the FIRST column swap heuristic.
77 */
78
79/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
80
83#include "scip/pub_cons.h"
84#include "scip/pub_message.h"
85#include "scip/pub_var.h"
86#include "scip/struct_var.h"
87#include "scip/type_var.h"
88#include "scip/scip.h"
89#include "scip/scip_branch.h"
90#include "scip/scip_conflict.h"
91#include "scip/scip_cons.h"
92#include "scip/scip_copy.h"
93#include "scip/scip_cut.h"
94#include "scip/scip_general.h"
95#include "scip/scip_lp.h"
96#include "scip/scip_mem.h"
97#include "scip/scip_message.h"
98#include "scip/scip_numerics.h"
99#include "scip/scip_param.h"
100#include "scip/scip_prob.h"
101#include "scip/scip_probing.h"
102#include "scip/scip_sol.h"
103#include "scip/scip_var.h"
104#include "scip/struct_scip.h"
105#include "scip/struct_mem.h"
106#include "scip/struct_tree.h"
107#include "scip/symmetry.h"
108#include "scip/debug.h"
109#include <string.h>
111
112
113/* symmetry handler properties */
114#define SYMHDLR_NAME "orbitopalreduction"
115
116/* orbitopal symmetry handler properties */
117#define EVENTHDLR_NAME "symmetry_orbitopal_eventhdlr"
118#define EVENTHDLR_DESC "event handler for maintaining the branch-and-bound tree"
119#define DEFAULT_COLUMNORDERING SCIP_COLUMNORDERING_MEDIAN /**< the column ordering variant */
120
121/*
122 * Data structures
123 */
124
125/** orbitopal symmetry handling data for a single orbitope */
127{
128 SCIP_VAR** vars; /**< orbitope variable array representing orbitope matrix row-wise */
129 int nrows; /**< number of rows */
130 int ncols; /**< number of columns */
131 int nbranchrows; /**< number of rows containing variables potentially used for branching */
132 SCIP_HASHMAP* rowindexmap; /**< map of variables to row index in orbitope matrix */
133 SCIP_HASHMAP* colindexmap; /**< map of variables to column index in orbitope matrix */
134#ifndef NDEBUG
135 SCIP_Longint lastnodenumber; /**< the last node number where the row and column order is computed */
136 int dbghash; /**< a hash for the column order in the last iteration */
137#endif
138 SCIP_HASHTABLE* nodeinfos; /**< symmetry handling information per branch-and-bound tree node */
139 SCIP_COLUMNORDERING columnordering; /**< policy for the column ordering */
140 SCIP_ROWORDERING rowordering; /**< policy for the row ordering */
141};
142typedef struct OrbitopeData ORBITOPEDATA; /**< orbitopal symmetry handling data for a single orbitope */
143
144/** wrapper for all orbitopes in orbitopal symmetry handling data */
145struct SCIP_OrbitopalReductionData
146{
147 SCIP_COLUMNORDERING defaultcolumnordering; /**< default policy for the column ordering */
148 SCIP_EVENTHDLR* eventhdlr; /**< pointer to the event handler for managing the branching tree */
149 ORBITOPEDATA** orbitopes; /**< array of pointers to orbitope data structs */
150 int norbitopes; /**< number of orbitope data structs in array */
151 int maxnorbitopes; /**< allocated orbitopes array size */
152 SCIP_CONSHDLR* conshdlr_nonlinear; /**< nonlinear constraint handler,
153 * is used to determine if a variable is a branching variable */
154 SCIP_Bool conshdlr_nonlinear_checked; /**< nonlinear constraint handler is already added? */
155 int nred; /**< total number of reductions */
156 int ncutoff; /**< total number of cutoffs */
157};
158
159/*
160 * Local methods
161 */
162
163/** gets whether a variable type is a branchrow-type */
164static
166 SCIP* scip, /**< SCIP data structure */
167 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
168 SCIP_VARTYPE vartype /**< var type */
169)
170{
171 assert( scip != NULL );
172 assert( orbireddata != NULL );
173 assert( orbireddata->conshdlr_nonlinear_checked );
174
175 switch (vartype)
176 {
179 return TRUE;
182 /* potential branching variables if nonlinear constraints exist */
183 assert( orbireddata->conshdlr_nonlinear_checked );
184 return orbireddata->conshdlr_nonlinear == NULL ? FALSE :
185 SCIPconshdlrGetNActiveConss(orbireddata->conshdlr_nonlinear) > 0;
186 default:
187 SCIPerrorMessage("unknown vartype\n");
188 SCIPABORT();
189 /* resolve compiler warning: no asserts in optimized mode */
190 return FALSE;
191 }
192}
193
194
195/** container for column index permutations */
197{
198 int from; /**< from which column ID */
199 int to; /**< to which column ID */
200};
201typedef struct ColSwap COLSWAP;
202
203/** information stored for branch-and-bound nodes */
205{
206 SCIP_Longint nodenumber; /**< node number of the branch-and-bound tree node */
207 COLSWAP* colswaps; /**< list containing column swaps by node branching decisions */
208 int ncolswaps; /**< number of elements in colswaps. ncolswaps == 0 <=> colswaps == NULL */
209 int* rows; /**< list of new variable rows by node branching decisions */
210 int nrows; /**< number of new variable rows added. nrows == 0 <=> rows == NULL */
211};
213
214/** hash key for virtual branch and bound nodeinfo struct */
215static
217{ /*lint --e{715}*/
218 return elem;
219}
220
221/** returns TRUE iff the indices of both node numbers are equal */
222static
224{ /*lint --e{715}*/
227 return nodeinfo1->nodenumber == nodeinfo2->nodenumber;
228}
229
230/** returns the hash value of the key */
231static
233{ /*lint --e{715}*/
235 return (unsigned int) nodeinfo->nodenumber;
236}
237
238
239/** tests if two columns are symmetrically equivalent
240 *
241 * We test if the columns with index col1 and col2 have elementwise the same bounds.
242 * If all symmetry-compatible reductions are applied, then it suffices to check only as many rows as are selected
243 * for orbitopal reduction. However, to be resilient to reductions that are not symmetry-compatible,
244 * we test all variables in the columns.
245 */
246static
248 SCIP* scip, /**< SCIP data structure */
249 ORBITOPEDATA* orbidata, /**< orbitope information */
250 int col1, /**< first column to compare */
251 int col2 /**< second column to compare */
252 )
253{
254 int i;
255 SCIP_VAR* var1;
256 SCIP_VAR* var2;
257
258 assert( scip != NULL );
259 assert( orbidata != NULL );
260 assert( col1 >= 0 );
262 assert( col2 >= 0 );
264
265 /* @todo test only for the selected rows (see function description) */
266 for (i = 0; i < orbidata->nrows; ++i)
267 {
268 var1 = orbidata->vars[i * orbidata->ncols + col1];
269 var2 = orbidata->vars[i * orbidata->ncols + col2];
270
271 /* if variable bounds differ: columns c and origcolid are not the same */
272 if (
274 ||
276 )
277 return FALSE;
278 }
279
280 /* loop terminated, so columns are equal */
281 return TRUE;
282}
283
284/** updates the column order with a bound change
285 *
286 * When it is branched on a variable in a column, update the column order for the children of the focusnode.
287 * Symmetrically equivalent columns, that is the columns where the variables have elementwise the same domain,
288 * at the focusnode at the moment of branching can be permuted.
289 * In this function, we select such a permutation, based on the column containing the branching variable(s).
290 * In all cases, we swap the column containing the branching variable with a symmetrically equivalent column,
291 * and the @param columnordering specifies if we prefer it to be the leftmost, rightmost, centermost symmetrically
292 * equivalent column, or the median column among the symmetrically equivalent columns.
293 *
294 * The column ordering is determined and stored at the moment of branching.
295 */
296static
298 SCIP* scip, /**< SCIP data structure */
299 ORBITOPEDATA* orbidata, /**< orbitope data */
300 int* colorder, /**< array to populate with column order, of size colorder */
301 int* colorderinv, /**< inverse array of the column order, of size colorder */
302 SCIP_VAR* var, /**< variable that we branch on */
303 COLSWAP* thiscolswap /**< the colswap to populate */
304 )
305{
306 int origcolid;
307 int swaporigcolid;
308 int c;
309 int ncols;
310 int* origequalcolids;
312 int middlecolumn = 0;
315
316#ifndef NDEBUG
317 SCIP_VAR* var1;
318 SCIP_VAR* var2;
319 int i;
320 int nrows;
321#endif
322
323 assert( scip != NULL );
324 assert( orbidata != NULL );
325 assert( colorder != NULL );
326 assert( colorderinv != NULL );
327 assert( var != NULL );
328 assert( thiscolswap != NULL );
329 assert( orbidata->ncols > 0 );
330 assert( orbidata->nrows > 0 );
331
332 ncols = orbidata->ncols;
333 assert( ncols > 0 );
334#ifndef NDEBUG
335 nrows = orbidata->nrows > 0;
336 assert( nrows > 0 );
337#endif
338
339 /* do not apply a column swap if no column permutations are applied */
340 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
341 {
342 thiscolswap->from = 0;
343 thiscolswap->to = 0;
344 return SCIP_OKAY;
345 }
346
347 /* only variables from the orbitope matrix are of interest */
348 origcolid = SCIPhashmapGetImageInt(orbidata->colindexmap, (void*) var);
349 if ( origcolid == INT_MAX )
350 {
351 thiscolswap->from = 0;
352 thiscolswap->to = 0;
353 return SCIP_OKAY;
354 }
355 assert( origcolid >= 0 );
356 assert( origcolid < ncols );
357
358 /* policy: swap with identical column that is closest to the center in relabeled order */
359 /* @todo other policies: If the variable is in a ppc-row, then select the minimal/second to minimal to branch on */
361
362 switch (orbidata->columnordering)
363 {
365 /* CENTRE uses the same code as FIRST and LAST, but requires that middlecolumn = ncols / 2 is set */
366 middlecolumn = ncols / 2;
367 /*lint -fallthrough*/
370 /* for each column, test column ordering condition, then if the column is identical to the var-column */
371 for (c = 0; c < ncols; ++c)
372 {
373 /* origcolid is not interesting */
374 if ( c == origcolid )
375 continue;
376
377 /* test if c is a better choice than swaporigcolid,
378 * otherwise continue to next iteration through CONDITIONFAIL
379 */
380 switch (orbidata->columnordering)
381 {
383 /* only swap with c if c is earlier in column order than swaporigcolid */
385 goto CONDITIONFAIL;
386 break;
388 /* only swap with c if c is later in column order than swaporigcolid */
390 goto CONDITIONFAIL;
391 break;
393 /* if the column is not more central than swaporigcolid, ignore */
394 if ( ABS(colorderinv[c] - middlecolumn) >=
396 goto CONDITIONFAIL;
397 break;
398 default:
399 return SCIP_ERROR;
400 }
401
402 /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */
404 continue;
405
406 /* the variable domain reductions in c and origcolid are the same */
408
410 ; /* no-op for going to the next iteration */
411 }
412
413 /* end switch */
414 break;
415
417 /* collect columns identical to the var-column, then select column satisfying ordering condition */
420
421 /* collect equal columns */
422#ifdef SCIP_MORE_DEBUG
423 SCIPdebugMessage("Detect columns identical to original column %d: ", origcolid);
424#endif
425 for (c = 0; c < ncols; ++c)
426 {
427 /* column origcolid is always equal to itself */
428 if ( c == origcolid )
429 {
431#ifdef SCIP_MORE_DEBUG
432 SCIPdebugPrintf("%d ", c);
433#endif
434 assert( norigequalcolids <= ncols );
435 continue;
436 }
437
438 /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */
440 continue;
441
442 /* the variable domain reductions in c and origcolid are the same */
444#ifdef SCIP_MORE_DEBUG
445 SCIPdebugPrintf("%d ", c);
446#endif
447 assert( norigequalcolids <= ncols );
448 }
449#ifdef SCIP_MORE_DEBUG
450 SCIPdebugPrintf("\n");
451#endif
452
453 /* we should have found origcolid, at least */
454 assert( norigequalcolids >= 1 );
455
456 /* from origequalcolids, select the column satisfying the column ordering policy */
457
458 /* get median column; since colorder maps origcolids to our ordering,
459 * we need to use colorderinv as the argument. */
460 /* @todo computing the median is O(n) by repeated median-of-medians (CLRS, Ch9), but let's just sort things */
462 /* get the median, that is swaporigcolid */
464
466
467 /* end switch */
468 break;
469
471 /* already handled earlier in this function */
472 default:
473 /* unknown column ordering variant */
474 return SCIP_ERROR;
475 }
476
479
480 /* if we do not replace origcolid */
481 if ( swaporigcolid == origcolid )
482 return SCIP_OKAY;
483
484#ifndef NDEBUG
485 /* swapped columns should be equivalent */
486 for (i = 0; i < nrows; ++i)
487 {
488 var1 = orbidata->vars[i * ncols + swaporigcolid];
489 var2 = orbidata->vars[i * ncols + origcolid];
492 }
493#endif
494
495 /* now swap the permuted column indices of swaporigcolid and origcolid */
496
497 /* at which column is origcolid? */
502
503 /* at which column is swaporigcolid? */
508
509 SCIPdebugMessage("Orbitope %p: Swapping column %d (at position %d) with column %d (at position %d)\n",
511
512 /* swap them, also keep track of the inverses */
517
518 return SCIP_OKAY;
519}
520
521
522/** yields entry at index in array, or returns entry if array is NULL */
523static
525 int* arr, /**< array */
526 int idx /**< index */
527)
528{
529 assert( idx >= 0 );
530 if ( arr == NULL )
531 return idx;
532 return arr[idx];
533}
534
535/** frees the row order */
536static
538 SCIP* scip, /**< SCIP data structure */
539 ORBITOPEDATA* orbidata, /**< orbitope data */
540 int** roworder /**< roworder array that is initialized with the roworder in the dynamic
541 * case, and NULL in the static case */
542)
543{
544 assert( scip != NULL );
545 assert( orbidata != NULL );
546 assert( roworder != NULL );
547
548 if ( orbidata->rowordering == SCIP_ROWORDERING_NONE )
549 {
550 assert( *roworder == NULL );
551 return;
552 }
553
554 assert( *roworder != NULL );
555 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
556 SCIPfreeBlockMemoryArray(scip, roworder, orbidata->nrows);
557
558 return;
559}
560
561/** gets the row order at the node
562 *
563 * this is NULL (i.e., the identity map) in the static (none) setting.
564 * this is an array of size orbidata->nrows in the dynamic (branching) setting.
565 *
566 * The row order is given in the order of the variables that is branched on.
567 * @todo combine with variant of cons_orbitope.c
568 */
569static
571 SCIP* scip, /**< SCIP data structure */
572 ORBITOPEDATA* orbidata, /**< orbitope data */
573 SCIP_NODE* node, /**< node for which the row order should be detected */
574 int** roworder, /**< array to populate with row order */
575 int* nselrows /**< pointer to populate with the number of rows part of the row order */
576 )
577{
578 int i;
579 int j;
581 BNBNODEINFO tmpnodeinfo; /* used for lookups in hash table */
582
583 assert( orbidata != NULL );
584 assert( orbidata->nrows > 0 );
585 assert( orbidata->ncols > 0 );
586 assert( node != NULL );
587 assert( roworder != NULL );
588 assert( nselrows != NULL );
589
590 if ( orbidata->rowordering == SCIP_ROWORDERING_NONE )
591 {
592 *roworder = NULL;
593 *nselrows = orbidata->nrows;
594 return SCIP_OKAY;
595 }
596
597 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
598
599 /* allocate number of rows */
600 SCIP_CALL( SCIPallocBlockMemoryArray(scip, roworder, orbidata->nrows) );
601
602 *nselrows = 0;
603
604 /* get the present row order up to this node (excluding the node itself) */
605 node = SCIPnodeGetParent(node);
606 while (node != NULL)
607 {
608 /* retrieve the nodeinfo of this ancestor node */
609 tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node);
611 if ( ancestornodeinfo != NULL )
612 {
613 assert( ancestornodeinfo->nrows >= 0 );
614 for (i = ancestornodeinfo->nrows - 1; i >= 0; --i)
615 {
616 (*roworder)[(*nselrows)++] = ancestornodeinfo->rows[i];
617#ifndef NDEBUG
618 {
619 /* check if this row is not featured earlier */
620 for (j = 0; j < (*nselrows) - 1; ++j)
621 {
622 assert( ancestornodeinfo->rows[i] != (*roworder)[j] );
623 }
624 }
625#endif
626 }
627 }
628
629 node = SCIPnodeGetParent(node);
630 }
631
632 /* row order is in reverse order now, so reverse the array */
633 for (i = 0; i < (*nselrows) / 2; ++i)
634 {
635 /* swap entry i with nselrows - 1 - i */
636 j = (*roworder)[i];
637 (*roworder)[i] = (*roworder)[(*nselrows) - 1 - i];
638 (*roworder)[(*nselrows) - 1 - i] = j;
639 }
640
641 return SCIP_OKAY;
642}
643
644
645/** gets rooted path up to node and populates column ordering array */
646static
648 ORBITOPEDATA* orbidata, /**< orbitope data */
649 SCIP_NODE* node, /**< node considered */
650 SCIP_NODE** rootedpath, /**< array to populate with the rooted path, must be sufficiently long */
651 int* colorder, /**< array to populate with the column order, must be nvars long */
652 int* colorderinv /**< array to populate with the inverse column order, must be nvars long */
653 )
654{
655 int i;
656 int j;
657 int depth;
661
662 assert( orbidata != NULL );
663 assert( node != NULL );
664 assert( rootedpath != NULL );
665 assert( colorder != NULL );
666 assert( colorderinv != NULL );
667
668 depth = SCIPnodeGetDepth(node);
669 i = depth;
670 while ( node != NULL )
671 {
672 assert( SCIPnodeGetDepth(node) == i );
673 rootedpath[i--] = node;
674 node = SCIPnodeGetParent(node);
675 }
676 assert( i == -1 );
677
678 for (i = 0; i <= depth; ++i)
679 {
680 node = rootedpath[i];
681
682 assert( SCIPnodeGetDepth(node) == i );
683
684 /* get the node info of that node */
685 tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node);
687
688 /* skip nodes that do not imply any row or column swaps */
689 if ( ancestornodeinfo == NULL )
690 continue;
691
692 /* ncolswaps == 0 iff colswaps == NULL */
693 assert( (ancestornodeinfo->ncolswaps == 0) != (ancestornodeinfo->colswaps != NULL) );
694
695 for (j = 0; j < ancestornodeinfo->ncolswaps; ++j)
696 {
699
700 thiscolswap = &ancestornodeinfo->colswaps[j];
701 assert( thiscolswap->from != thiscolswap->to ); /* there are no trivial swaps in the list */
702 assert( thiscolswap->from >= 0 && thiscolswap->from < orbidata->ncols );
703 assert( thiscolswap->to >= 0 && thiscolswap->to < orbidata->ncols );
704
705 /* at which column is origcolid? */
710
711 /* at which column is swaporigcolid? */
716
717 /* swap them, also keep track of the inverses */
722 }
723 }
724
725 return SCIP_OKAY;
726}
727
728/** at branching decisions, maintains the column swap and potential new rows in the orbitope */
729static
731{
733 SCIP_NODE* node;
735 SCIP_NODE** children;
737 SCIP_DOMCHG* domchg;
739 SCIP_VAR* var;
741 int maxnbranchvars;
742 int nbranchvars;
743 int nboundchgs;
744 int nchildren;
745 int i;
746 int j;
747 int c;
748 int rowid;
751
752 assert( eventdata != NULL );
754
757
758 orbidata = (ORBITOPEDATA*) eventdata;
759 assert( orbidata != NULL );
760 assert( orbidata->nrows > 0 );
761 assert( orbidata->ncols > 0 );
762 assert( orbidata->vars != NULL );
763 assert( orbidata->colindexmap != NULL );
764 assert( orbidata->rowindexmap != NULL );
765
766 SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
767
768 /* arrays used within the loop */
769 maxnbranchvars = 1; /* it's a good guess that there's one branching variable, because that's likely the number */
772
773 /* get all variables branched upon (check all branches) */
774 nbranchvars = 0;
775 for (c = 0; c < nchildren; ++c)
776 {
777 childnode = children[c];
779
780 /* loop through all bound changes */
781 nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
782 for (i = 0; i < nboundchgs; ++i)
783 {
784 /* get bound change info */
786 assert( boundchg != NULL );
787
788 /* branching decisions have to be in the beginning of the bound change array */
790 break;
791
792 /* get corresponding branching variable */
794
795 /* only variables from the orbitope matrix are of interest */
796 if ( ! SCIPhashmapExists(orbidata->rowindexmap, (void*) var) )
797 continue;
798
799 /* skip variables that are already stored */
800 if ( nbranchvars > 0 )
801 {
802 for (j = 0; j < nbranchvars; ++j)
803 {
804 if ( branchvars[j] == var )
805 break;
806 }
807 /* if the loop above is stopped with `break`, `j < nbranchvars` is not satisfied.
808 * then, go to the next iteration
809 */
810 if ( j < nbranchvars )
811 continue;
812 }
813
814 /* the variable is not already in the array, so store it */
816 {
818 assert( maxnbranchvars > 0 );
821 }
824 }
825 }
826
827 /* skip orbitopes whose variable matrices do not contain any branching variable */
828 if ( nbranchvars <= 0 )
829 goto FREE;
830
833 newnodeinfo->colswaps = NULL;
834 newnodeinfo->ncolswaps = 0;
835 newnodeinfo->rows = NULL;
836 newnodeinfo->nrows = 0;
837
838 /* store data about row ordering */
839 if ( orbidata->rowordering != SCIP_ROWORDERING_NONE )
840 {
841 int* roworder;
842 int nselrows;
843
844 assert( orbidata->nrows > 0 );
845 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
846
847 /* get the present row order up to this node */
849 assert( roworder != NULL );
850
851 /* extend the row fixings with the steps from this node */
852 for (i = 0; i < nbranchvars; ++i)
853 {
854 var = branchvars[i];
855
856 assert( SCIPhashmapExists(orbidata->rowindexmap, (void*) var) ); /* otherwise was not added to branchvars */
857 rowid = SCIPhashmapGetImageInt(orbidata->rowindexmap, (void*) var);
858 assert( rowid >= 0 );
860
861 /* avoid adding row to row order twice */
862 if ( nselrows > 0 )
863 {
864 for (j = 0; j < nselrows; ++j)
865 {
866 if ( rowid == roworder[j] )
867 break;
868 }
869 if ( j < nselrows ) /* if the loop is interrupted */
870 continue;
871 }
872
873 /* if we end up here, the row index does not appear for any ancestor or the present row order */
874
875 /* append rowid to present roworder */
876 roworder[nselrows++] = rowid;
877
878 /* mark that this row index is the new one in the node */
879 if ( newnodeinfo->rows == NULL )
880 {
881 assert( newnodeinfo->nrows == 0 );
883 }
884 else
885 {
886 /* reallocate with linear increments, because we expect 1 branching variable most of the time */
888 newnodeinfo->nrows, newnodeinfo->nrows + 1) );
889 }
890 newnodeinfo->rows[newnodeinfo->nrows++] = rowid;
891 }
892
893 freeRowOrder(scip, orbidata, &roworder);
894 }
895
896 /* store data about column ordering */
897 if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE )
898 {
899 int* colorder;
900 int* colorderinv;
903
904 assert( orbidata->ncols > 0 );
907
908 /* populate colorder with standard ordering */
909 for (i = 0; i < orbidata->ncols; ++i)
910 colorder[i] = i;
911
912 /* introduce inverse column ordering */
913 for (i = 0; i < orbidata->ncols; ++i)
914 colorderinv[i] = i;
915
916 /* get the rooted path
917 *
918 * We want to iterate through the bound changes in the order of the rooted path to this node.
919 */
921 if ( node != NULL )
922 {
924 }
925
926 /* get the swap for this node */
927 for (i = 0; i < nbranchvars; ++i)
928 {
931
932 /* skip trivial swaps of columns */
933 if ( tmpcolswap.from == tmpcolswap.to )
934 continue;
935
936 /* mark that this row index is the new one in the node */
937 if ( newnodeinfo->rows == NULL )
938 {
939 assert( newnodeinfo->nrows == 0 );
940 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps + 1) );
941 }
942 else
943 {
944 /* reallocate with linear increments, because we expect 1 branching variable most of the time */
946 newnodeinfo->ncolswaps + 1) );
947 }
948 thiscolswap = &(newnodeinfo->colswaps[newnodeinfo->ncolswaps++]);
949 thiscolswap->from = tmpcolswap.from;
950 thiscolswap->to = tmpcolswap.to;
951 }
952
955 }
956
957 /* store updates of row/column order or free memory if no change applied */
958 if ( newnodeinfo->nrows > 0 || newnodeinfo->ncolswaps > 0 )
959 {
961 }
962 else
963 {
965 }
966
967FREE:
970
971 return SCIP_OKAY;
972} /*lint !e715*/
973
974
975/** at branching decisions, maintains the column swap and potential new rows in the orbitope */
976static
978{
979 switch (SCIPeventGetType(event))
980 {
982 return eventExecNodeBranched(scip, eventhdlr, event, eventdata);
983 default:
984 SCIPerrorMessage("Eventhandler " EVENTHDLR_NAME " is called with an unsupported eventtype.\n");
985 return SCIP_ERROR;
986 }
987}
988
989
990/** returns whether a row contains potential branching variables */
991static
993 SCIP* scip, /**< SCIP data structure */
994 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
995 ORBITOPEDATA* orbidata, /**< symmetry handling data for orbitopal structure */
996 int rowid /**< row id for which to check */
997 )
998{
999 SCIP_VAR* var;
1000#ifndef NDEBUG
1001 int c;
1002#endif
1003
1004 assert( scip != NULL );
1005 assert( orbireddata != NULL );
1006 assert( orbidata != NULL );
1007 assert( orbidata->nrows > 0 );
1008 assert( orbidata->ncols > 0 );
1009 assert( rowid >= 0 );
1011 assert( orbidata->vars != NULL );
1012 assert( orbidata->vars[rowid * orbidata->ncols] ); /* variable in first column must be set */
1013
1014 /* get the first variable from the row */
1015 var = orbidata->vars[rowid * orbidata->ncols];
1016
1017 /* debugging: the variable types in a row should all be the same */
1018#ifndef NDEBUG
1019 for (c = 1; c < orbidata->ncols; ++c)
1020 {
1021 /* the actual vartypes can be different,
1022 * for example when an INTEGER vartype turns into BINARY due to bound changes
1023 */
1026 }
1027#endif
1028
1030}
1031
1032
1033/** frees orbitope data */
1034static
1036 SCIP* scip, /**< SCIP data structure */
1037 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
1038 ORBITOPEDATA** orbidata /**< pointer to orbitope data */
1039 )
1040{
1042 int i;
1043 int nentries;
1044 int nelem;
1045
1046 assert( scip != NULL );
1047 assert( orbireddata != NULL );
1048 assert( orbidata != NULL );
1049 assert( *orbidata != NULL );
1050 assert( (*orbidata)->vars != NULL );
1051 assert( (*orbidata)->nrows > 0 );
1052 assert( (*orbidata)->ncols > 0 );
1053 assert( (*orbidata)->nrows * (*orbidata)->ncols > 0 );
1055
1056 /* free data if orbitopal reduction is dynamic */
1057 if ( (*orbidata)->columnordering != SCIP_COLUMNORDERING_NONE || (*orbidata)->rowordering != SCIP_ROWORDERING_NONE )
1058 {
1059 /* drop event */
1061 (SCIP_EVENTDATA*) *orbidata, -1 ) );
1062
1063 /* free nodeinfos */
1064 nentries = SCIPhashtableGetNEntries((*orbidata)->nodeinfos);
1065 for (i = 0; i < nentries; ++i)
1066 {
1067 /* @todo in principle, can deal with memory sparsity by first getting all nodeinfos,
1068 * then sorting by address and free them in descending order
1069 */
1070 nodeinfo = (BNBNODEINFO*) (SCIPhashtableGetEntry((*orbidata)->nodeinfos, i));
1071 if ( nodeinfo == NULL )
1072 continue;
1073
1074 assert( nodeinfo != NULL );
1075 assert( nodeinfo->nrows > 0 || nodeinfo->ncolswaps > 0 );
1076
1077 assert( (nodeinfo->ncolswaps == 0) != (nodeinfo->colswaps != NULL) );
1078 SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->colswaps), nodeinfo->ncolswaps);
1079
1080 assert( (nodeinfo->nrows == 0) != (nodeinfo->rows != NULL) );
1082
1084 }
1085 SCIPhashtableFree(&((*orbidata)->nodeinfos));
1086 }
1087
1088 /* free index lookup hashsets */
1089 SCIPhashmapFree(&((*orbidata)->colindexmap));
1090 SCIPhashmapFree(&((*orbidata)->rowindexmap));
1091
1092 /* free and release vars */
1093 nelem = (*orbidata)->nrows * (*orbidata)->ncols;
1094 assert( nelem > 0 );
1095 for (i = 0; i < nelem; ++i)
1096 {
1097 SCIP_CALL( SCIPreleaseVar(scip, &(*orbidata)->vars[i]) );
1098 }
1099 SCIPfreeBlockMemoryArray(scip, &((*orbidata)->vars), (*orbidata)->nrows * (*orbidata)->ncols); /*lint !e647*/
1100
1102
1103 return SCIP_OKAY;
1104}
1105
1106
1107/** adds an orbitope to the orbitopal reduction data */
1108static
1110 SCIP* scip, /**< SCIP data structure */
1111 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
1112 SCIP_ROWORDERING rowordering, /**< specifies how rows of orbitope are ordered */
1113 SCIP_COLUMNORDERING colordering, /**< specifies how columnss of orbitope are ordered */
1114 SCIP_VAR** vars, /**< variables array, must have size nrows * ncols */
1115 int nrows, /**< number of rows in orbitope */
1116 int ncols, /**< number of columns in orbitope */
1117 SCIP_Bool* success /**< to store whether the component is successfully added */
1118 )
1119{
1121 SCIP_VAR* var;
1122 int i;
1123 int rowid;
1124 int colid;
1125 int nelem;
1126
1127 assert( scip != NULL );
1128 assert( orbireddata != NULL );
1129 assert( orbireddata->eventhdlr != NULL );
1130 assert( vars != NULL );
1131 assert( nrows >= 0 );
1132 assert( ncols >= 0 );
1133
1134 nelem = nrows * ncols;
1135 assert( nelem >= 0 );
1136
1137 /* prevent trivial case with empty orbitope */
1138 if ( nelem == 0 )
1139 {
1140 *success = FALSE;
1141 return SCIP_OKAY;
1142 }
1143
1144 *success = TRUE;
1145
1147
1148 orbidata->nrows = nrows;
1149 orbidata->ncols = ncols;
1150 orbidata->columnordering = colordering;
1151 orbidata->rowordering = rowordering;
1152
1153#ifndef NDEBUG
1154 orbidata->lastnodenumber = -1;
1155 orbidata->dbghash = 0;
1156#endif
1157
1158 /* variable array enumerates the orbitope matrix row-wise */
1160
1161 /* create row and column index lookup maps */
1163 SCIP_CALL( SCIPhashmapCreate(&orbidata->colindexmap, SCIPblkmem(scip), ncols) );
1164
1165 SCIPdebugMessage("Orbitope variables for (%dx%d) orbitope with orbidata %p\n", nrows, ncols, (void*) orbidata);
1166
1167 /* populate variable array defining orbitope matrix for orbitope data */
1168 for (i = 0, rowid = 0, colid = 0; i < nelem; ++i, ++colid)
1169 {
1170 if ( colid == ncols )
1171 {
1172 colid = 0;
1173 ++rowid;
1174 }
1175 assert( nrows > 0 );
1176 assert( ncols > 0 );
1177 assert( rowid == i / ncols );
1178 assert( colid == i % ncols );
1179
1180 var = vars[i];
1181 assert( var != NULL );
1183
1186
1187 orbidata->vars[i] = var;
1188
1189 /* variables cannot be repeated in the variable matrix */
1190 assert( ! SCIPhashmapExists(orbidata->rowindexmap, var) );
1191 SCIP_CALL( SCIPhashmapInsertInt(orbidata->rowindexmap, var, rowid) );
1192
1193 assert( ! SCIPhashmapExists(orbidata->colindexmap, var) );
1194 SCIP_CALL( SCIPhashmapInsertInt(orbidata->colindexmap, var, colid) );
1195
1196 SCIPdebugMessage("%4d %4d -> %s\n", rowid, colid, var->name);
1197 }
1198
1199 /* count number of branchable rows in orbitope */
1200 orbidata->nbranchrows = 0;
1201 /* @todo at getRowData: If nselrows == nbranchrows, append the non-branch rows (like before) */
1202 for (i = 0; i < nrows; ++i)
1203 {
1205 ++orbidata->nbranchrows;
1206 }
1207
1208 /* cannot add orbitope when already branching */
1210
1211 /* possibly create data needed for dynamic orbitopal reduction */
1212 if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE || orbidata->rowordering != SCIP_ROWORDERING_NONE )
1213 {
1214 /* add the event to store the row and column updates of nodes in the branch-and-bound tree */
1217
1218 /* nodeinfos: every node that implies a column swap is represented
1219 *
1220 * Assuming at most one branching on every variable implying a column swap, initial hashtable size nelem.
1221 * In case that there are many more rows than columns, we do not expect too many column swaps.
1222 */
1223 SCIP_CALL( SCIPhashtableCreate(&orbidata->nodeinfos, scip->mem->probmem, MIN(16 * ncols + 64, nelem),
1225 }
1226
1227 /* resize orbitope array if needed */
1228 assert( orbireddata->norbitopes >= 0 );
1229 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
1230 assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes );
1231 if ( orbireddata->norbitopes == orbireddata->maxnorbitopes )
1232 {
1233 int newsize;
1234
1235 newsize = SCIPcalcMemGrowSize(scip, orbireddata->norbitopes + 1);
1236 assert( newsize >= 0 );
1237
1238 if ( orbireddata->norbitopes == 0 )
1239 {
1241 }
1242 else
1243 {
1245 }
1246
1247 orbireddata->maxnorbitopes = newsize;
1248 }
1249 assert( orbireddata->orbitopes != NULL );
1250 assert( orbireddata->norbitopes < orbireddata->maxnorbitopes );
1251
1252 /* add orbitope to orbitopal reduction data */
1253 assert( orbireddata->norbitopes < orbireddata->maxnorbitopes );
1254 orbireddata->orbitopes[orbireddata->norbitopes++] = orbidata;
1255
1256 SCIPdebugMsg(scip, "Added orbitope for orbitopal reduction of size %d by %d\n", nrows, ncols);
1257
1258 return SCIP_OKAY;
1259}
1260
1261
1262/** frees the column order */
1263static
1265 SCIP* scip, /**< SCIP data structure */
1266 ORBITOPEDATA* orbidata, /**< orbitope data */
1267 int** colorder, /**< colorder array that is initialized with the colorder in the dynamic
1268 * case, of size ncols, and NULL in the static case */
1269 int** colorderinv /**< array with the inverse column order, of size ncols */
1270)
1271{
1272 assert( scip != NULL );
1273 assert( orbidata != NULL );
1274 assert( colorder != NULL );
1275 assert( colorderinv != NULL );
1276
1277 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
1278 {
1279 assert( *colorder == NULL );
1280 assert( *colorderinv == NULL );
1281 return;
1282 }
1283 assert( *colorder != NULL );
1284 assert( *colorderinv != NULL );
1285
1288}
1289
1290
1291/** gets the column order at the node
1292 *
1293 * The column order is (deterministically) dynamically decided based on the policy for column ordering.
1294 */
1295static
1297 SCIP* scip, /**< SCIP data structure */
1298 ORBITOPEDATA* orbidata, /**< orbitope data */
1299 SCIP_NODE* eventnode, /**< node where this should be determined at */
1300 int** colorder, /**< array to populate with column order, of size ncols */
1301 int** colorderinv /**< array to populate with inverse column order, of size ncols */
1302 )
1303{
1304 SCIP_NODE* node;
1306 int i;
1307 int depth;
1308 int ncols;
1309
1310 assert( scip != NULL );
1311 assert( orbidata != NULL );
1312 assert( eventnode != NULL );
1313 assert( colorder != NULL );
1314 assert( colorderinv != NULL );
1315
1316 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
1317 {
1318 *colorder = NULL;
1319 *colorderinv = NULL;
1320 return SCIP_OKAY;
1321 }
1322 ncols = orbidata->ncols;
1323 assert( ncols > 0 );
1324
1327
1328 /* populate colorder with standard ordering */
1329 for (i = 0; i < ncols; ++i)
1330 (*colorder)[i] = i;
1331
1332 /* introduce inverse column ordering */
1333 for (i = 0; i < ncols; ++i)
1334 (*colorderinv)[i] = i;
1335
1336 /* get the rooted path
1337 *
1338 * We want to iterate through the bound changes in the order of the rooted path to this node.
1339 */
1341 if ( node != NULL )
1342 {
1343 depth = SCIPnodeGetDepth(node);
1347 }
1348
1349 return SCIP_OKAY;
1350}
1351
1352
1353#ifndef NDEBUG
1354/** checks if the columns of the matrix are lexicographically decreasing, using the specified row and column ordering */
1355static
1357 SCIP* scip, /**< SCIP data structure */
1358 ORBITOPEDATA* orbidata, /**< orbitope data */
1359 int* roworder, /**< array with the row order */
1360 int* colorder, /**< array with the column order */
1361 SCIP_Real* matrix, /**< a matrix */
1362 int nrows, /**< number of rows of matrix */
1363 int ncols, /**< number of cols of matrix */
1364 int* infinitesimal, /**< array specifying where the infinitesimals are at */
1365 SCIP_Bool addinfinitesimals /**< whether infinitesimals are added (TRUE) or subtracted (FALSE) */
1366 )
1367{
1368 int rowid;
1369 int colid;
1370 int idx;
1371 int origrowid;
1372 int origcolid;
1373 int origidx;
1374 SCIP_VAR* var;
1375
1376 assert( scip != NULL );
1377 assert( matrix != NULL );
1378 assert( orbidata != NULL );
1379 assert( orbidata->vars != NULL );
1380 assert( nrows >= 0 );
1382 assert( ncols >= 0 );
1385
1386 /* respect variable bounds */
1387 for (rowid = 0; rowid < nrows; ++rowid)
1388 {
1390 for (colid = 0; colid < ncols; ++colid)
1391 {
1393 idx = rowid * ncols + colid;
1394 origidx = origrowid * ncols + origcolid;
1395 var = orbidata->vars[origidx];
1396 assert( SCIPsymGE(scip, matrix[idx], SCIPvarGetLbLocal(var)) );
1397 assert( SCIPsymLE(scip, matrix[idx], SCIPvarGetUbLocal(var)) );
1398 }
1399 }
1400
1401 /* is orbitope */
1402 for (colid = 0; colid < ncols - 1; ++colid)
1403 {
1404 /* compare column colid with colid + 1 */
1405 for (rowid = 0; rowid < nrows; ++rowid)
1406 {
1407 /* entry is >= entry to the right */
1408 assert( SCIPsymGE(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) );
1409
1410 if ( SCIPsymGT(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) )
1411 {
1412 /* critical row */
1413 break;
1414 }
1415 else
1416 {
1417 /* check for infinitesimal values
1418 * If infinitesimals are added (lexminface case), then if the left column has a +epsilon,
1419 * it does not matter whether the right column has +epsilon or not, then the left column is >,
1420 * due to the axioms x + epsilon > x + epsilon and x + epsilon > x.
1421 * Analogously, x > x - epsilon and x - epsilon > x - epsilon.
1422 */
1423 assert( SCIPsymEQ(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) );
1425 ? (infinitesimal[colid] == rowid) /* left has +epsilon term */
1426 : (infinitesimal[colid + 1] == rowid) /* right has -epsilon term */
1427 )
1428 {
1429 /* critical row */
1430 break;
1431 }
1432 }
1433 }
1434 }
1435}
1436#endif
1437
1438#ifndef NDEBUG
1439/** to test if arrays are the same, generates some hash for an array of integers */
1440static
1442 int* array, /** array */
1443 int len /** array length */
1444 )
1445{
1446 int i;
1447 unsigned int hash = 0;
1448
1449 assert( array != NULL );
1450 assert( len >= 0 );
1451
1452 for (i = 0; i < len; i++)
1453 {
1454 hash ^= (unsigned int) (array[i]);
1455 hash = (hash << 1) ^ (hash >> 1);
1456 }
1457
1458 return (int) hash;
1459}
1460#endif
1461
1462#ifdef SCIP_MORE_DEBUG
1463/** prints nrows × ncols matrix of floats with 2 decimals */
1464static
1465void debugPrintMatrix(
1466 SCIP_Real* matrix, /** matrix, encoded as array enumerating the elements row-wise */
1467 int nrows, /** number of rows */
1468 int ncols /** number of rows */
1469 )
1470{
1471 int row;
1472 int col;
1473
1474 assert( matrix != NULL );
1475 assert( nrows >= 0 );
1476 assert( ncols >= 0 );
1477
1478 for (row = 0; row < nrows; ++row)
1479 {
1480 SCIPdebugPrintf("[");
1481 for (col = 0; col < ncols; ++col)
1482 {
1483 SCIPdebugPrintf(" %+10.2f", matrix[row * ncols + col]);
1484 }
1485 SCIPdebugPrintf(" ]\n");
1486 }
1487}
1488#endif
1489
1490
1491/** gets the column order at the node */
1492static
1494 SCIP* scip, /**< SCIP data structure */
1495 ORBITOPEDATA* orbidata, /**< orbitope data */
1496 int* roworder, /**< array with the row order (or NULL if identity function is used) */
1497 int nselrows, /**< number of selected rows */
1498 int* colorder, /**< array with the column order (or NULL if identity function is used) */
1499 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1500 int* nfixedvars /**< pointer to counter of number of variable domain reductions */
1501 )
1502{
1503 /* @todo also make "nselcols" to allow for colorders smaller than orbidata->ncols */
1504 SCIP_Real* lexminface = NULL;
1505 int* lexminepsrow = NULL;
1506 SCIP_Real* lexmaxface = NULL;
1507 int* lexmaxepsrow = NULL;
1508 int nelem;
1509 int rowid;
1510 int colid;
1511 int ncols;
1512 int origrowid;
1513 int origcolid;
1514 int origidx;
1515 int i;
1516 int lastunfixed;
1517 SCIP_Real lb;
1518 SCIP_Real ub;
1519 SCIP_Bool iseq;
1520 SCIP_Bool success;
1521 SCIP_VAR* var;
1523
1524 assert( scip != NULL );
1525 assert( orbidata != NULL );
1526 assert( orbidata->vars != NULL );
1527 assert( nselrows >= 0 );
1528 assert( infeasible != NULL );
1529 assert( nfixedvars != NULL );
1530
1531 *infeasible = FALSE;
1532
1533 assert( orbidata->nrows > 0 );
1534 assert( orbidata->nrows >= nselrows );
1535 ncols = orbidata->ncols;
1536 assert( ncols > 1 );
1537
1538 /* nothing to propagate without any rows */
1539 if ( nselrows <= 0 )
1540 return SCIP_OKAY;
1541
1542#ifdef SCIP_MORE_DEBUG
1543 /* print matrix for debugging purposes */
1544 {
1545 int k;
1546 int r;
1548 SCIPdebugMessage("Start propagating static orbitope: \n");
1549 SCIPdebugPrintf(">");
1550 for (k = 0; k < ncols; ++k)
1551 {
1552 SCIPdebugPrintf("%12d ", colorder[k]);
1553 }
1554 SCIPdebugPrintf("< (IDs)\n");
1555
1556 for (r = 0; r < nselrows; ++r)
1557 {
1558 SCIPdebugPrintf("[");
1559 for (k = 0; k < ncols; ++k)
1560 {
1561 thisvar = orbidata->vars[roworder[r] * ncols + colorder[k]];
1562 SCIPdebugPrintf("%4s %+1.2f,%+1.2f ", SCIPvarGetName(thisvar),
1564 }
1565 SCIPdebugPrintf("] (row %d)\n", roworder[r]);
1566 }
1567 }
1568#endif
1569
1570 nelem = nselrows * ncols;
1571
1572 /* compute lexmin face */
1574
1575 /* array to store for each column at which row we add an infinitesimal value, initially at none (-1) */
1577 for (colid = 0; colid < ncols; ++colid)
1578 lexminepsrow[colid] = -1;
1579
1580 /* last column takes the minimally possible values. */
1581 colid = ncols - 1;
1583 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1584 {
1586 origidx = origrowid * ncols + origcolid;
1587 var = orbidata->vars[origidx];
1588
1589 assert( i == rowid * ncols + colid );
1590 assert( var != NULL );
1591
1593 }
1594 /* all previous columns: One-column replacement algorithm */
1595 for (colid = ncols - 2; colid >= 0; --colid)
1596 {
1597 /* "rowid" of the last unfixed entry whose domain allows for larger values than the current chosen.
1598 * If there is none, -1. */
1599 lastunfixed = -1;
1600 /* whether column "colid" is the same as column "colid + 1" up (but excluding) to "rowid" */
1601 iseq = TRUE;
1602
1604 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1605 {
1607 origidx = origrowid * ncols + origcolid;
1608 assert( i == rowid * ncols + colid );
1609
1610 /* the entry one to the right is not the first column */
1611 assert( (i + 1) % ncols > 0 );
1612
1613 var = orbidata->vars[origidx];
1614 assert( var != NULL );
1615
1616 if ( iseq )
1617 {
1618 /* equality holds up to this row
1619 * Compare to the entry value on the column immediately right.
1620 * The value we choose on the left must be at least this.
1621 * 2 Options:
1622 * Option 1: The upper bound is smaller. Then we're in an infeasible situation. Resolve as described below.
1623 * Option 2: The upper bound is greater or equal.
1624 */
1625 ub = SCIPvarGetUbLocal(var);
1626
1627 /* compare to the value in the column right of it */
1628 if ( SCIPsymLT(scip, ub, lexminface[i + 1]) ||
1629 ( lexminepsrow[colid + 1] == rowid && SCIPsymEQ(scip, ub, lexminface[i + 1]) ) )
1630 {
1631 /* value of this column can only be strictly smaller than the value in the column to its right
1632 * This may not be possible.
1633 * Try to repair: Go back to the last row with "room" left, and make the value minimally larger.
1634 */
1635 if ( lastunfixed >= 0 )
1636 {
1637 /* repair: return to the last row with "room", and increase the lexmin-value at that row. */
1639 lexminface[lastunfixed * ncols + colid + 1]) );
1640 othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid];
1641 switch (SCIPvarGetType(othervar))
1642 {
1646 /* discrete type with unit steps: Add one to the bound. */
1647 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1649 lexminface[lastunfixed * ncols + colid] += 1.0;
1652 break;
1654 /* continuous type, so add an infinitesimal value to the bound */
1656 assert( lexminepsrow[colid] == -1 );
1658 break;
1659 default:
1660 return SCIP_ERROR;
1661 }
1662 /* now row "lastunfixed" is greater. Restart from here. */
1663 iseq = FALSE;
1664 rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */
1665 i = rowid * ncols + colid;
1666 continue;
1667 }
1668 else
1669 {
1670 /* cannot repair. It is infeasible. */
1671 *infeasible = TRUE;
1672 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), min\n", colid, origcolid);
1673 goto FREE;
1674 }
1675 }
1676 else
1677 {
1678 assert( SCIPsymGE(scip, ub, lexminface[i + 1]) );
1679 lb = SCIPvarGetLbLocal(var);
1680 assert( SCIPsymLE(scip, lb, ub) );
1681 lexminface[i] = MAX(lexminface[i + 1], lb);
1683
1684 /* are we still equal? */
1685 if ( SCIPsymGT(scip, lexminface[i], lexminface[i + 1]) )
1686 iseq = FALSE;
1687 else if ( lexminepsrow[colid + 1] == rowid )
1688 {
1693 /* right column (colid+1) has value x + epsilon, left column (colid) has value x, now
1694 * must also become x + epsilon in order to be larger or equal
1695 * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon.
1696 */
1697 iseq = FALSE;
1698 assert( lexminepsrow[colid] == -1 );
1700 }
1701
1702 /* is there room left to increase this variable further? */
1703 switch (SCIPvarGetType(var))
1704 {
1708 /* discrete type with unit steps: Add one to the bound. */
1709 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1710 /* @todo in principle, this can be made more tight using the hole-lists... */
1712 if ( SCIPsymLE(scip, lexminface[i] + 1.0, ub) )
1714 break;
1716 /* continuous type: if we can add an infinitesimal value to the current lexminface[i] value,
1717 * mark row as 'lastunfixed'
1718 */
1719 if ( SCIPsymLT(scip, lexminface[i], ub) )
1721 break;
1722 default:
1723 return SCIP_ERROR;
1724 }
1725 }
1726 }
1727 else
1728 {
1729 /* there had been a row before which breaks the equality-condition, choose minimally possible value */
1731 }
1732 }
1733 }
1734
1735#ifndef NDEBUG
1736 /* sanity checks */
1738#endif
1739
1740 /* compute lexmax face */
1742
1743 /* array to store for each column at which row we subtract an infinitesimal value, initially at none (-1) */
1745 for (colid = 0; colid < ncols; ++colid)
1746 lexmaxepsrow[colid] = -1;
1747
1748 /* first column, fill all unfixed entries with maximally possible values */
1749 colid = 0;
1751 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1752 {
1754 origidx = origrowid * ncols + origcolid;
1755 var = orbidata->vars[origidx];
1756
1757 assert( i == rowid * ncols + colid );
1758 assert( var != NULL );
1759
1761 }
1762 /* all next columns: One-column replacement algorithm */
1763 for (colid = 1; colid < ncols; ++colid)
1764 {
1765 /* "rowid" of the last unfixed entry whose domain allows for smaller values than the current chosen.
1766 * If there is none, -1. */
1767 lastunfixed = -1;
1768 /* whether column "colid" is the same as column "colid - 1" up (but excluding) to "rowid" */
1769 iseq = TRUE;
1770
1772 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1773 {
1775 origidx = origrowid * ncols + origcolid;
1776 assert( i == rowid * ncols + colid );
1777
1778 /* the entry one to the left is not the last column, i.e., this column cannot be the first column */
1779 assert( i % ncols > 0 );
1780
1781 var = orbidata->vars[origidx];
1782 assert( var != NULL );
1783
1784 if ( iseq )
1785 {
1786 /* equality holds up to this row
1787 * Compare to the entry value on the column immediately left.
1788 * The value we choose on the right must be at most this.
1789 * 2 Options:
1790 * Option 1: The lower bound is larger. Then we're in an infeasible situation. Resolve as described below.
1791 * Option 2: The lower bound is smaller or equal.
1792 */
1793 lb = SCIPvarGetLbLocal(var);
1794
1795 /* compare to the value in the column left of it */
1796 if ( SCIPsymGT(scip, lb, lexmaxface[i - 1]) ||
1797 ( lexmaxepsrow[colid - 1] == rowid && SCIPsymEQ(scip, lb, lexmaxface[i - 1]) ) )
1798 {
1799 /* value of this column can only be strictly larger than the value in the column to its left
1800 * This may not be possible.
1801 * Try to repair: Go back to the last row with "room" left, and make the value minimally smaller.
1802 */
1803 if ( lastunfixed >= 0 )
1804 {
1805 /* repair: return to the last row with "room", and decrease the lexmax-value at that row. */
1807 lexmaxface[lastunfixed * ncols + colid - 1]) );
1808 othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid];
1809 switch (SCIPvarGetType(othervar))
1810 {
1814 /* discrete type with unit steps: Remove one from the lexmax-value. */
1815 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1817 lexmaxface[lastunfixed * ncols + colid] -= 1.0;
1821 break;
1823 /* continuous type, so subtract an infinitesimal value to the bound */
1826 assert( lexmaxepsrow[colid] == -1 );
1828 break;
1829 default:
1830 return SCIP_ERROR;
1831 }
1832 /* now row "lastunfixed" is greater. Restart from here. */
1833 iseq = FALSE;
1834 rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */
1835 i = rowid * ncols + colid;
1836 continue;
1837 }
1838 else
1839 {
1840 /* cannot repair. It is infeasible. */
1841 *infeasible = TRUE;
1842 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), max\n", colid, origcolid);
1843 goto FREE;
1844 }
1845 }
1846 else
1847 {
1848 assert( SCIPsymLE(scip, lb, lexmaxface[i - 1]) );
1849 ub = SCIPvarGetUbLocal(var);
1850 assert( SCIPsymLE(scip, lb, ub) );
1851 lexmaxface[i] = MIN(lexmaxface[i - 1], ub);
1853
1854 /* are we still equal? */
1855 if ( SCIPsymGT(scip, lexmaxface[i - 1], lexmaxface[i]) )
1856 iseq = FALSE;
1857 else if ( lexmaxepsrow[colid - 1] == rowid )
1858 {
1863 /* left column (colid-1) has value x - epsilon, right column (colid) has value x, now
1864 * must also become x - epsilon in order to be larger or equal
1865 * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon.
1866 */
1867 iseq = FALSE;
1868 assert( lexmaxepsrow[colid] == -1 );
1870 }
1871
1872 /* is there room left to decrease this variable further? */
1873 switch (SCIPvarGetType(var))
1874 {
1878 /* discrete type with unit steps: Remove one from the lexmax-value. */
1879 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1880 /* @todo in principle, this can be made more tight using the hole-lists... */
1882 if ( SCIPsymGE(scip, lexmaxface[i] - 1.0, lb) )
1884 break;
1886 /* continuous type: if we can subtract an infinitesimal value to the current lexmaxface[i] value,
1887 * mark row as 'lastunfixed'
1888 */
1889 if ( SCIPsymGT(scip, lexmaxface[i], lb) )
1891 break;
1892 default:
1893 return SCIP_ERROR;
1894 }
1895 }
1896 }
1897 else
1898 {
1899 /* there had been a row before which breaks the equality-condition, choose maximally possible value */
1901 }
1902 }
1903 }
1904
1905#ifndef NDEBUG
1906 /* sanity checks */
1908#endif
1909
1910#ifdef SCIP_MORE_DEBUG
1911 /* show lexmin and lexmax face */
1912 SCIPdebugMessage("Lex min face\n");
1914 SCIPdebugMessage("Lex max face\n");
1916#endif
1917
1918 /* compare the two column-wise and apply domain reductions */
1919 for (colid = 0; colid < ncols; ++colid)
1920 {
1921 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1922 {
1923 assert( i == rowid * ncols + colid );
1924
1925 /* get var */
1928 origidx = origrowid * ncols + origcolid;
1929 var = orbidata->vars[origidx];
1930
1932 {
1933 /* tighten LB and UB to same value (i.e. fixing) */
1935 if ( success )
1936 {
1937 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1938 *nfixedvars += 1;
1939 }
1940 else
1941 {
1942 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1943 lexminface[i]);
1944 }
1945 if ( *infeasible )
1946 {
1947 SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1949 goto FREE;
1950 }
1951
1953 if ( success )
1954 {
1955 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1956 *nfixedvars += 1;
1957 }
1958 else
1959 {
1960 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1961 lexminface[i]);
1962 }
1963 if ( *infeasible )
1964 {
1965 SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1967 goto FREE;
1968 }
1969 }
1970 else
1971 {
1972 /* This is the row index where the min- and max-face have a different value for this column entry.
1973 * Update the lower bound and upper bound */
1974
1975 /* lower bound, based on lexminface */
1977 if ( success )
1978 {
1979 SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid,
1980 lexminface[i]);
1981 *nfixedvars += 1;
1982 }
1983 else
1984 {
1985 SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name,
1986 rowid, colid, lexminface[i]);
1987 }
1988 if ( *infeasible )
1989 {
1990 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s (%3d,%3d) to %5.2f\n",
1992 goto FREE;
1993 }
1994
1995 /* upper bound, based on lexmaxface */
1997 if ( success )
1998 {
1999 SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid,
2000 lexmaxface[i]);
2001 *nfixedvars += 1;
2002 }
2003 else
2004 {
2005 SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name,
2006 rowid, colid, lexmaxface[i]);
2007 }
2008 if ( *infeasible )
2009 {
2010 SCIPdebugMessage("Detected infeasibility restricting variable UB %12s (%3d,%3d) to %5.2f\n",
2012 goto FREE;
2013 }
2014 break;
2015 }
2016 }
2017 }
2018
2019FREE:
2024
2025 return SCIP_OKAY;
2026}
2027
2028
2029/** propagation method for a single orbitope matrix */
2030static
2032 SCIP* scip, /**< SCIP data structure */
2033 ORBITOPEDATA* orbidata, /**< orbitope data */
2034 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
2035 int* nfixedvars /**< pointer to store the number of found domain reductions */
2036 )
2037{
2038 SCIP_NODE* focusnode;
2039 int* roworder;
2040 int nselrows;
2041 int* colorder;
2042 int* colorderinv;
2043
2044 assert( scip != NULL );
2045 assert( orbidata != NULL );
2046 assert( infeasible != NULL );
2047 assert( nfixedvars != NULL );
2048
2049 *nfixedvars = 0;
2050 *infeasible = FALSE;
2051
2052 assert( orbidata->ncols > 0 );
2053 assert( orbidata->nrows > 0 );
2054
2055 focusnode = SCIPgetFocusNode(scip);
2056 assert( focusnode != NULL );
2057
2058 /* get row order */
2059 SCIP_CALL( getRowOrder(scip, orbidata, focusnode, &roworder, &nselrows) );
2060 assert( nselrows >= 0 );
2062 if ( nselrows == 0 )
2063 goto FREEROWS;
2064
2065 /* get column order */
2067
2068#ifndef NDEBUG
2069 /* DEBUG: if propagation is repeated in the same node, the same column order and row order is needed */
2070 /* @todo: performance: move roworder and colorder to orbidata, then re-use */
2071 {
2072 int colhash = (colorder == NULL) ? 1 : debugGetArrayHash(colorder, orbidata->ncols);
2073 int rowhash = (roworder == NULL) ? 0 : debugGetArrayHash(roworder, nselrows);
2074 int hash = colhash ^ rowhash;
2075
2076#ifdef SCIP_DEBUG
2077 SCIPdebugPrintf("Col hash %32d; Row hash %32d; Hash %32d\n", colhash, rowhash, hash);
2078 {
2081 while ( tmpnode != NULL )
2082 {
2083 int nbranchings, nconsprop, nprop;
2085 SCIPnodeGetNDomchg(tmpnode, &nbranchings, &nconsprop, &nprop);
2086 SCIPdebugPrintf(" node %lld: (%d, %d, %d) \n", tmpnode->number, nbranchings, nconsprop, nprop);
2088 }
2089 }
2090#endif
2091
2092 assert( SCIPgetCurrentNode(scip) == SCIPgetFocusNode(scip) ); /* no probing */
2093 if ( orbidata->lastnodenumber == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
2094 {
2095 assert( orbidata->dbghash == hash );
2096 }
2097 orbidata->dbghash = hash;
2098 }
2100#endif
2101
2102 SCIP_CALL( propagateStaticOrbitope(scip, orbidata, roworder, nselrows, colorder, infeasible, nfixedvars) );
2103
2105FREEROWS:
2106 freeRowOrder(scip, orbidata, &roworder);
2107
2108#ifdef SCIP_MORE_DEBUG
2109 SCIPdebugPrintf("\n\n");
2110#endif
2111
2112 return SCIP_OKAY;
2113}
2114
2115
2116/*
2117 * Interface methods
2118 */
2119
2120
2121/** gets the number of reductions */
2123 SCIP* scip, /**< SCIP data structure */
2124 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */
2125 int* nred, /**< total number of reductions applied */
2126 int* ncutoff /**< total number of cutoffs applied */
2127 )
2128{
2129 assert( scip != NULL );
2130 assert( orbireddata != NULL );
2131 assert( nred != NULL );
2132
2133 *nred = orbireddata->nred;
2134 *ncutoff = orbireddata->ncutoff;
2135
2136 return SCIP_OKAY;
2137}
2138
2139
2140/** prints orbitopal reduction data */
2142 SCIP* scip, /**< SCIP data structure */
2143 SCIP_ORBITOPALREDDATA* orbireddata /**< orbitopal reduction data structure */
2144 )
2145{
2146 int i;
2147
2148 assert( scip != NULL );
2149 assert( orbireddata != NULL );
2150
2151 if ( orbireddata->norbitopes == 0 )
2152 {
2153 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " orbitopal reduction: no components\n");
2154 return SCIP_OKAY;
2155 }
2156
2158 " orbitopal reduction: %4d components: ", orbireddata->norbitopes);
2159 for (i = 0; i < orbireddata->norbitopes; ++i)
2160 {
2161 if ( i > 0 )
2164 "%dx%d", orbireddata->orbitopes[i]->nrows, orbireddata->orbitopes[i]->ncols);
2165 }
2167
2168 return SCIP_OKAY;
2169}
2170
2171
2172/** propagates orbitopal reduction */
2174 SCIP* scip, /**< SCIP data structure */
2175 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */
2176 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
2177 int* nred, /**< pointer to store the number of domain reductions */
2178 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
2179 * only set this to TRUE when a reduction is found, never set to FALSE */
2180 )
2181{
2183 int c;
2184 int thisfixedvars;
2185
2186 assert( scip != NULL );
2187 assert( orbireddata != NULL );
2188 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
2189 assert( infeasible != NULL );
2190 assert( nred != NULL );
2191
2192 *infeasible = FALSE;
2193 *nred = 0;
2194
2195 /* @todo Can the following be removed? */
2196 /* @todo shouldn't this be SCIPallowWeakDualReds, since we do not regard the objective */
2198 return SCIP_OKAY;
2199
2200 /* cannot do anything during probing
2201 * @todo can find deductions for the probing node, maybe?
2202 */
2203 if ( SCIPinProbing(scip) )
2204 return SCIP_OKAY;
2205
2206 /* propagate all orbitopes */
2207 for (c = 0; c < orbireddata->norbitopes; ++c)
2208 {
2209 orbidata = orbireddata->orbitopes[c];
2210 assert( orbidata != NULL );
2211
2213 SCIPdebugMessage("Found %d reductions during orbitopal reduction for orbitope %d\n", thisfixedvars, c);
2214 *nred += thisfixedvars;
2215
2216 /* a symmetry propagator has ran, so set didrun to TRUE */
2217 *didrun = TRUE;
2218
2219 /* stop if we find infeasibility in one of the methods */
2220 if ( *infeasible )
2221 {
2222 SCIPdebugMessage("Detected infeasibility during orbitopal reduction for orbitope %d\n", c);
2223 break;
2224 }
2225 }
2226
2227 orbireddata->nred += *nred;
2228 if ( *infeasible )
2229 ++orbireddata->ncutoff;
2230
2231 return SCIP_OKAY;
2232}
2233
2234/** adds orbitopal component to orbitopal symmetry handler */
2236 SCIP* scip, /**< SCIP data structure */
2237 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */
2238 SCIP_ROWORDERING rowordering, /**< specifies how rows of orbitope are ordered */
2239 SCIP_COLUMNORDERING colordering, /**< specifies how columnss of orbitope are ordered */
2240 SCIP_VAR** vars, /**< matrix of variables on which the symmetry acts */
2241 int nrows, /**< number of rows */
2242 int ncols, /**< number of columns */
2243 SCIP_Bool* success /**< to store whether the component is successfully added */
2244 )
2245{
2246 assert( scip != NULL );
2247 assert( orbireddata != NULL );
2248 assert( vars != NULL );
2249 assert( nrows > 0 );
2250 assert( ncols > 0 );
2251
2252 /* dynamic symmetry reductions cannot be performed on original problem */
2254
2255 /* if this is the first time adding an orbitope, check if the nonlinear conshlr exists */
2256 if ( !orbireddata->conshdlr_nonlinear_checked )
2257 {
2258 orbireddata->conshdlr_nonlinear = SCIPfindConshdlr(scip, "nonlinear");
2259 orbireddata->conshdlr_nonlinear_checked = TRUE;
2260 }
2261
2262 /* create orbitope data */
2263 SCIP_CALL( addOrbitope(scip, orbireddata, rowordering, colordering, vars, nrows, ncols, success) );
2264
2265 return SCIP_OKAY;
2266}
2267
2268
2269/** resets orbitopal reduction data structure (clears all orbitopes) */
2271 SCIP* scip, /**< SCIP data structure */
2272 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */
2273 )
2274{
2275 assert( scip != NULL );
2276 assert( orbireddata != NULL );
2277 assert( orbireddata->norbitopes >= 0 );
2278 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
2279 assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes );
2280 assert( orbireddata->eventhdlr != NULL );
2281
2282 /* free orbitopes that are added */
2283 while (orbireddata->norbitopes > 0)
2284 {
2285 SCIP_CALL( freeOrbitope(scip, orbireddata, &(orbireddata->orbitopes[--orbireddata->norbitopes])) );
2286 }
2287 assert( orbireddata->norbitopes == 0 );
2288 SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->orbitopes, orbireddata->maxnorbitopes);
2289 orbireddata->orbitopes = NULL;
2290 orbireddata->maxnorbitopes = 0;
2291
2292 return SCIP_OKAY;
2293}
2294
2295
2296/** frees orbitopal reduction data */
2298 SCIP* scip, /**< SCIP data structure */
2299 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */
2300 )
2301{
2302 assert( scip != NULL );
2303 assert( orbireddata != NULL );
2304 assert( *orbireddata != NULL );
2305
2307
2309 return SCIP_OKAY;
2310}
2311
2312
2313/** initializes structures needed for orbitopal reduction
2314 *
2315 * This is only done exactly once.
2316 */
2318 SCIP* scip, /**< SCIP data structure */
2319 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */
2320 )
2321{
2322 SCIP_EVENTHDLR* eventhdlr;
2323
2324 assert( scip != NULL );
2325 assert( orbireddata != NULL );
2326
2327 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitopalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2329
2330 /* create orbitope handler data */
2332
2333 /* default column ordering param */
2334 SCIP_CALL( SCIPaddIntParam(scip, "propagating/symmetry/" SYMHDLR_NAME "/columnordering",
2335 "The column ordering variant, respects enum SCIP_ColumnOrdering.",
2336 (int*) &(*orbireddata)->defaultcolumnordering, TRUE, DEFAULT_COLUMNORDERING, 0, 4,
2337 NULL, NULL) ); /*lint !e641*/
2338
2339 /* initialize event handler. */
2342 assert( eventhdlr != NULL );
2343 (*orbireddata)->eventhdlr = eventhdlr;
2344
2345 /* orbitopes array */
2346 (*orbireddata)->orbitopes = NULL;
2347 (*orbireddata)->norbitopes = 0;
2348 (*orbireddata)->maxnorbitopes = 0;
2349
2350 /* conshdlr nonlinear */
2351 (*orbireddata)->conshdlr_nonlinear = NULL;
2352 (*orbireddata)->conshdlr_nonlinear_checked = FALSE;
2353
2354 /* counter of total number of reductions and cutoffs */
2355 (*orbireddata)->nred = 0;
2356 (*orbireddata)->ncutoff = 0;
2357
2358 return SCIP_OKAY;
2359}
2360
2361
2362/** returns the default column ordering */
2364 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */
2365 )
2366{
2367 assert( orbireddata != NULL );
2368
2369 return orbireddata->defaultcolumnordering;
2370}
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition debug.c:2208
methods for debugging
#define NULL
Definition def.h:267
#define MIN(x, y)
Definition def.h:243
#define ABS(x)
Definition def.h:235
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIPABORT()
Definition def.h:346
#define SCIP_CALL(x)
Definition def.h:374
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition misc.c:3192
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition misc.c:2346
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition misc.c:2777
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition misc.c:2579
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition misc.c:2785
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition misc.c:2608
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4670
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition scip_event.c:104
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition scip_event.c:234
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition event.c:1030
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition scip_event.c:286
SCIP_NODE * SCIPeventGetNode(SCIP_EVENT *event)
Definition event.c:1300
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition scip_event.c:320
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition tree.c:7549
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition tree.c:7539
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7444
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition tree.c:7724
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition tree.c:7454
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2264
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2192
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2302
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2340
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2226
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition scip_tree.c:164
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition scip_tree.c:72
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5205
SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
Definition var.c:17326
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition var.c:17374
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition var.c:17336
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition var.c:17561
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5322
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
Definition var.c:17366
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:8717
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:8631
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
return SCIP_OKAY
int c
int depth
int r
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR * var
static SCIP_VAR ** vars
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebugMessage
Definition pub_message.h:96
#define SCIPdebugPrintf
Definition pub_message.h:99
public methods for problem variables
SCIP callable library.
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for SCIP variables
SCIP_Longint nodenumber
SCIP_HASHMAP * rowindexmap
SCIP_Longint lastnodenumber
SCIP_HASHTABLE * nodeinfos
SCIP_ROWORDERING rowordering
SCIP_HASHMAP * colindexmap
SCIP_COLUMNORDERING columnordering
char * name
Definition struct_var.h:235
datastructures for block memory pools and memory buffers
SCIP main data structure.
data structures for branch and bound tree
datastructures for problem variables
methods for handling symmetries
static SCIP_RETCODE propagateStaticOrbitope(SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int nselrows, int *colorder, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_RETCODE getRowOrder(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *node, int **roworder, int *nselrows)
static SCIP_RETCODE populateRootedPathColumnOrder(ORBITOPEDATA *orbidata, SCIP_NODE *node, SCIP_NODE **rootedpath, int *colorder, int *colorderinv)
static SCIP_RETCODE freeOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA **orbidata)
static int debugGetArrayHash(int *array, int len)
static void freeColumnOrder(SCIP *scip, ORBITOPEDATA *orbidata, int **colorder, int **colorderinv)
SCIP_RETCODE SCIPincludeOrbitopalReduction(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitopalReductionFree(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitopalReductionReset(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
static SCIP_RETCODE propagateOrbitope(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_Bool *infeasible, int *nfixedvars)
#define SYMHDLR_NAME
SCIP_RETCODE SCIPorbitopalReductionAddOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
static SCIP_Bool rowIsBranchRow(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA *orbidata, int rowid)
SCIP_RETCODE SCIPorbitopalReductionPropagate(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
static void freeRowOrder(SCIP *scip, ORBITOPEDATA *orbidata, int **roworder)
SCIP_RETCODE SCIPorbitopalReductionGetStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, int *nred, int *ncutoff)
static SCIP_RETCODE updateColumnOrderWhenBranchingOnColumn(SCIP *scip, ORBITOPEDATA *orbidata, int *colorder, int *colorderinv, SCIP_VAR *var, COLSWAP *thiscolswap)
static SCIP_RETCODE addOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
SCIP_RETCODE SCIPorbitopalReductionPrintStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
static SCIP_Bool testColumnsAreSymmetricallyEquivalent(SCIP *scip, ORBITOPEDATA *orbidata, int col1, int col2)
static SCIP_RETCODE getColumnOrder(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *eventnode, int **colorder, int **colorderinv)
static SCIP_Bool vartypeIsBranchRowType(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_VARTYPE vartype)
#define EVENTHDLR_DESC
SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering(SCIP_ORBITOPALREDDATA *orbireddata)
#define EVENTHDLR_NAME
static int getArrayEntryOrIndex(int *arr, int idx)
#define DEFAULT_COLUMNORDERING
static void assertIsOrbitopeMatrix(SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int *colorder, SCIP_Real *matrix, int nrows, int ncols, int *infinitesimal, SCIP_Bool addinfinitesimals)
@ SCIP_COLUMNORDERING_CENTRE
@ SCIP_COLUMNORDERING_FIRST
@ SCIP_COLUMNORDERING_NONE
@ SCIP_COLUMNORDERING_LAST
@ SCIP_COLUMNORDERING_MEDIAN
enum SCIP_ColumnOrdering SCIP_COLUMNORDERING
@ SCIP_ROWORDERING_BRANCHING
@ SCIP_ROWORDERING_NONE
struct SCIP_OrbitopalReductionData SCIP_ORBITOPALREDDATA
enum SCIP_RowOrdering SCIP_ROWORDERING
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_NODEBRANCHED
Definition type_event.h:95
@ SCIP_VERBLEVEL_HIGH
#define SCIP_DECL_HASHKEYEQ(x)
Definition type_misc.h:194
#define SCIP_DECL_HASHGETKEY(x)
Definition type_misc.h:191
#define SCIP_DECL_HASHKEYVAL(x)
Definition type_misc.h:197
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
type definitions for symmetry computations
type definitions for problem variables
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_BOUNDCHGTYPE_BRANCHING
Definition type_var.h:87
enum SCIP_Vartype SCIP_VARTYPE
Definition type_var.h:73