Scippy

SCIP

Solving Constraint Integer Programs

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
216SCIP_DECL_HASHGETKEY(hashGetKeyBnbnodeinfo)
217{ /*lint --e{715}*/
218 return elem;
219}
220
221/** returns TRUE iff the indices of both node numbers are equal */
222static
223SCIP_DECL_HASHKEYEQ(hashKeyEqBnbnodeinfo)
224{ /*lint --e{715}*/
225 BNBNODEINFO* nodeinfo1 = (BNBNODEINFO*) key1;
226 BNBNODEINFO* nodeinfo2 = (BNBNODEINFO*) key2;
227 return nodeinfo1->nodenumber == nodeinfo2->nodenumber;
228}
229
230/** returns the hash value of the key */
231static
232SCIP_DECL_HASHKEYVAL(hashKeyValBnbnodeinfo)
233{ /*lint --e{715}*/
234 BNBNODEINFO* nodeinfo = (BNBNODEINFO*) key;
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 );
261 assert( col1 < orbidata->ncols );
262 assert( col2 >= 0 );
263 assert( col2 < orbidata->ncols );
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 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;
311 int norigequalcolids;
312 int middlecolumn = 0;
313 int positionorigcolidincolorder;
314 int positionswaporigcolidincolorder;
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 */
360 swaporigcolid = origcolid;
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 */
384 if ( colorderinv[c] >= colorderinv[swaporigcolid] )
385 continue;
386 break;
388 /* only swap with c if c is later in column order than swaporigcolid */
389 if ( colorderinv[c] <= colorderinv[swaporigcolid] )
390 continue;
391 break;
393 /* if the column is not more central than swaporigcolid, ignore */
394 if ( ABS(colorderinv[c] - middlecolumn) >=
395 ABS(colorderinv[swaporigcolid] - middlecolumn) )
396 continue;
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? */
403 if ( !testColumnsAreSymmetricallyEquivalent(scip, orbidata, c, origcolid) )
404 continue;
405
406 /* the variable domain reductions in c and origcolid are the same */
407 swaporigcolid = c;
408 }
409
410 /* end switch */
411 break;
412
414 /* collect columns identical to the var-column, then select column satisfying ordering condition */
415 norigequalcolids = 0;
416 SCIP_CALL( SCIPallocBufferArray(scip, &origequalcolids, ncols) );
417
418 /* collect equal columns */
419#ifdef SCIP_MORE_DEBUG
420 SCIPdebugMessage("Detect columns identical to original column %d: ", origcolid);
421#endif
422 for (c = 0; c < ncols; ++c)
423 {
424 /* column origcolid is always equal to itself */
425 if ( c == origcolid )
426 {
427 origequalcolids[norigequalcolids++] = c;
428#ifdef SCIP_MORE_DEBUG
429 SCIPdebugPrintf("%d ", c);
430#endif
431 assert( norigequalcolids <= ncols );
432 continue;
433 }
434
435 /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */
436 if ( !testColumnsAreSymmetricallyEquivalent(scip, orbidata, c, origcolid) )
437 continue;
438
439 /* the variable domain reductions in c and origcolid are the same */
440 origequalcolids[norigequalcolids++] = c;
441#ifdef SCIP_MORE_DEBUG
442 SCIPdebugPrintf("%d ", c);
443#endif
444 assert( norigequalcolids <= ncols );
445 }
446#ifdef SCIP_MORE_DEBUG
447 SCIPdebugPrintf("\n");
448#endif
449
450 /* we should have found origcolid, at least */
451 assert( norigequalcolids >= 1 );
452
453 /* from origequalcolids, select the column satisfying the column ordering policy */
454
455 /* get median column; since colorder maps origcolids to our ordering,
456 * we need to use colorderinv as the argument. */
457 /* @todo computing the median is O(n) by repeated median-of-medians (CLRS, Ch9), but let's just sort things */
458 SCIPsortInd(origequalcolids, SCIPsortArgsortInt, colorderinv, norigequalcolids);
459 /* get the median, that is swaporigcolid */
460 swaporigcolid = origequalcolids[norigequalcolids / 2];
461
462 SCIPfreeBufferArray(scip, &origequalcolids);
463
464 /* end switch */
465 break;
466
468 /* already handled earlier in this function */
469 default:
470 /* unknown column ordering variant */
471 return SCIP_ERROR;
472 }
473
474 thiscolswap->from = swaporigcolid;
475 thiscolswap->to = origcolid;
476
477 /* if we do not replace origcolid */
478 if ( swaporigcolid == origcolid )
479 return SCIP_OKAY;
480
481#ifndef NDEBUG
482 /* swapped columns should be equivalent */
483 for (i = 0; i < nrows; ++i)
484 {
485 var1 = orbidata->vars[i * ncols + swaporigcolid];
486 var2 = orbidata->vars[i * ncols + origcolid];
487 assert( SCIPsymEQ(scip, SCIPvarGetLbLocal(var1), SCIPvarGetLbLocal(var2)) );
488 assert( SCIPsymEQ(scip, SCIPvarGetUbLocal(var1), SCIPvarGetUbLocal(var2)) );
489 }
490#endif
491
492 /* now swap the permuted column indices of swaporigcolid and origcolid */
493
494 /* at which column is origcolid? */
495 positionorigcolidincolorder = colorderinv[origcolid];
496 assert( positionorigcolidincolorder >= 0 );
497 assert( positionorigcolidincolorder < ncols );
498 assert( colorder[positionorigcolidincolorder] == origcolid );
499
500 /* at which column is swaporigcolid? */
501 positionswaporigcolidincolorder = colorderinv[swaporigcolid];
502 assert( positionswaporigcolidincolorder >= 0 );
503 assert( positionswaporigcolidincolorder < ncols );
504 assert( colorder[positionswaporigcolidincolorder] == swaporigcolid );
505
506 SCIPdebugMessage("Orbitope %p: Swapping column %d (at position %d) with column %d (at position %d)\n",
507 (void*) orbidata, origcolid, positionorigcolidincolorder, swaporigcolid, positionswaporigcolidincolorder);
508
509 /* swap them, also keep track of the inverses */
510 colorder[positionswaporigcolidincolorder] = origcolid;
511 colorder[positionorigcolidincolorder] = swaporigcolid;
512 colorderinv[origcolid] = positionswaporigcolidincolorder;
513 colorderinv[swaporigcolid] = positionorigcolidincolorder;
514
515 return SCIP_OKAY;
516}
517
518
519/** yields entry at index in array, or returns entry if array is NULL */
520static
522 int* arr, /**< array */
523 int idx /**< index */
524 )
525{
526 assert( idx >= 0 );
527 if ( arr == NULL )
528 return idx;
529 return arr[idx];
530}
531
532/** frees the row order */
533static
535 SCIP* scip, /**< SCIP data structure */
536 ORBITOPEDATA* orbidata, /**< orbitope data */
537 int** roworder /**< roworder array that is initialized with the roworder in the dynamic
538 * case, and NULL in the static case */
539 )
540{
541 assert( scip != NULL );
542 assert( orbidata != NULL );
543 assert( roworder != NULL );
544
545 if ( orbidata->rowordering == SCIP_ROWORDERING_NONE )
546 {
547 assert( *roworder == NULL );
548 return;
549 }
550
551 assert( *roworder != NULL );
552 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
553 SCIPfreeBlockMemoryArray(scip, roworder, orbidata->nrows);
554
555 return;
556}
557
558/** gets the row order at the node
559 *
560 * this is NULL (i.e., the identity map) in the static (none) setting.
561 * this is an array of size orbidata->nrows in the dynamic (branching) setting.
562 *
563 * The row order is given in the order of the variables that is branched on.
564 * @todo combine with variant of cons_orbitope.c
565 */
566static
568 SCIP* scip, /**< SCIP data structure */
569 ORBITOPEDATA* orbidata, /**< orbitope data */
570 SCIP_NODE* node, /**< node for which the row order should be detected */
571 int** roworder, /**< array to populate with row order */
572 int* nselrows /**< pointer to populate with the number of rows part of the row order */
573 )
574{
575 int i;
576 int j;
577 BNBNODEINFO* ancestornodeinfo;
578 BNBNODEINFO tmpnodeinfo; /* used for lookups in hash table */
579
580 assert( orbidata != NULL );
581 assert( orbidata->nrows > 0 );
582 assert( orbidata->ncols > 0 );
583 assert( node != NULL );
584 assert( roworder != NULL );
585 assert( nselrows != NULL );
586
587 if ( orbidata->rowordering == SCIP_ROWORDERING_NONE )
588 {
589 *roworder = NULL;
590 *nselrows = orbidata->nrows;
591 return SCIP_OKAY;
592 }
593
594 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
595
596 /* allocate number of rows */
597 SCIP_CALL( SCIPallocBlockMemoryArray(scip, roworder, orbidata->nrows) );
598
599 *nselrows = 0;
600
601 /* get the present row order up to this node (excluding the node itself) */
602 node = SCIPnodeGetParent(node);
603 while (node != NULL)
604 {
605 /* retrieve the nodeinfo of this ancestor node */
606 tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node);
607 ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo);
608 if ( ancestornodeinfo != NULL )
609 {
610 assert( ancestornodeinfo->nrows >= 0 );
611 for (i = ancestornodeinfo->nrows - 1; i >= 0; --i)
612 {
613 (*roworder)[(*nselrows)++] = ancestornodeinfo->rows[i];
614#ifndef NDEBUG
615 {
616 /* check if this row is not featured earlier */
617 for (j = 0; j < (*nselrows) - 1; ++j)
618 {
619 assert( ancestornodeinfo->rows[i] != (*roworder)[j] );
620 }
621 }
622#endif
623 }
624 }
625
626 node = SCIPnodeGetParent(node);
627 }
628
629 /* row order is in reverse order now, so reverse the array */
630 for (i = 0; i < (*nselrows) / 2; ++i)
631 {
632 /* swap entry i with nselrows - 1 - i */
633 j = (*roworder)[i];
634 (*roworder)[i] = (*roworder)[(*nselrows) - 1 - i];
635 (*roworder)[(*nselrows) - 1 - i] = j;
636 }
637
638 return SCIP_OKAY;
639}
640
641
642/** gets rooted path up to node and populates column ordering array */
643static
645 ORBITOPEDATA* orbidata, /**< orbitope data */
646 SCIP_NODE* node, /**< node considered */
647 SCIP_NODE** rootedpath, /**< array to populate with the rooted path, must be sufficiently long */
648 int* colorder, /**< array to populate with the column order, must be nvars long */
649 int* colorderinv /**< array to populate with the inverse column order, must be nvars long */
650 )
651{
652 int i;
653 int j;
654 int depth;
655 BNBNODEINFO* ancestornodeinfo;
656 BNBNODEINFO tmpnodeinfo;
657 COLSWAP* thiscolswap;
658
659 assert( orbidata != NULL );
660 assert( node != NULL );
661 assert( rootedpath != NULL );
662 assert( colorder != NULL );
663 assert( colorderinv != NULL );
664
665 depth = SCIPnodeGetDepth(node);
666 i = depth;
667 while ( node != NULL )
668 {
669 assert( SCIPnodeGetDepth(node) == i );
670 rootedpath[i--] = node;
671 node = SCIPnodeGetParent(node);
672 }
673 assert( i == -1 );
674
675 for (i = 0; i <= depth; ++i)
676 {
677 node = rootedpath[i];
678
679 assert( SCIPnodeGetDepth(node) == i );
680
681 /* get the node info of that node */
682 tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node);
683 ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo);
684
685 /* skip nodes that do not imply any row or column swaps */
686 if ( ancestornodeinfo == NULL )
687 continue;
688
689 /* ncolswaps == 0 iff colswaps == NULL */
690 assert( (ancestornodeinfo->ncolswaps == 0) != (ancestornodeinfo->colswaps != NULL) );
691
692 for (j = 0; j < ancestornodeinfo->ncolswaps; ++j)
693 {
694 int positionfromincolorder;
695 int positiontoincolorder;
696
697 thiscolswap = &ancestornodeinfo->colswaps[j];
698 assert( thiscolswap->from != thiscolswap->to ); /* there are no trivial swaps in the list */
699 assert( thiscolswap->from >= 0 && thiscolswap->from < orbidata->ncols );
700 assert( thiscolswap->to >= 0 && thiscolswap->to < orbidata->ncols );
701
702 /* at which column is origcolid? */
703 positionfromincolorder = colorderinv[thiscolswap->from];
704 assert( positionfromincolorder >= 0 );
705 assert( positionfromincolorder < orbidata->ncols );
706 assert( colorder[positionfromincolorder] == thiscolswap->from );
707
708 /* at which column is swaporigcolid? */
709 positiontoincolorder = colorderinv[thiscolswap->to];
710 assert( positiontoincolorder >= 0 );
711 assert( positiontoincolorder < orbidata->ncols );
712 assert( colorder[positiontoincolorder] == thiscolswap->to );
713
714 /* swap them, also keep track of the inverses */
715 colorder[positiontoincolorder] = thiscolswap->from;
716 colorder[positionfromincolorder] = thiscolswap->to;
717 colorderinv[thiscolswap->from] = positiontoincolorder;
718 colorderinv[thiscolswap->to] = positionfromincolorder;
719 }
720 }
721
722 return SCIP_OKAY;
723}
724
725/** at branching decisions, maintains the column swap and potential new rows in the orbitope */
726static
727SCIP_DECL_EVENTEXEC(eventExecNodeBranched)
728{
729 ORBITOPEDATA* orbidata;
730 SCIP_NODE* node;
731 SCIP_NODE* eventnode;
732 SCIP_NODE** children;
733 SCIP_NODE* childnode;
734 SCIP_DOMCHG* domchg;
735 SCIP_BOUNDCHG* boundchg;
736 SCIP_VAR* var;
737 SCIP_VAR** branchvars;
738 int maxnbranchvars;
739 int nbranchvars;
740 int nboundchgs;
741 int nchildren;
742 int i;
743 int j;
744 int c;
745 int rowid;
746 BNBNODEINFO* newnodeinfo;
747 SCIP_NODE** rootedpath;
748
749 assert( eventdata != NULL );
750 assert( !SCIPinProbing(scip) );
751
752 eventnode = SCIPeventGetNode(event);
753 assert( SCIPgetFocusNode(scip) == eventnode );
754
755 orbidata = (ORBITOPEDATA*) eventdata;
756 assert( orbidata != NULL );
757 assert( orbidata->nrows > 0 );
758 assert( orbidata->ncols > 0 );
759 assert( orbidata->vars != NULL );
760 assert( orbidata->colindexmap != NULL );
761 assert( orbidata->rowindexmap != NULL );
762
763 SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
764
765 /* arrays used within the loop */
766 maxnbranchvars = 1; /* it's a good guess that there's one branching variable, because that's likely the number */
767 SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, maxnbranchvars) );
768 SCIP_CALL( SCIPallocBufferArray(scip, &rootedpath, SCIPnodeGetDepth(eventnode)) );
769
770 /* get all variables branched upon (check all branches) */
771 nbranchvars = 0;
772 for (c = 0; c < nchildren; ++c)
773 {
774 childnode = children[c];
775 domchg = SCIPnodeGetDomchg(childnode);
776
777 /* loop through all bound changes */
778 nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
779 for (i = 0; i < nboundchgs; ++i)
780 {
781 /* get bound change info */
782 boundchg = SCIPdomchgGetBoundchg(domchg, i);
783 assert( boundchg != NULL );
784
785 /* branching decisions have to be in the beginning of the bound change array */
787 break;
788
789 /* get corresponding branching variable */
790 var = SCIPboundchgGetVar(boundchg);
791
792 /* only variables from the orbitope matrix are of interest */
793 if ( ! SCIPhashmapExists(orbidata->rowindexmap, (void*) var) )
794 continue;
795
796 /* skip variables that are already stored */
797 if ( nbranchvars > 0 )
798 {
799 for (j = 0; j < nbranchvars; ++j)
800 {
801 if ( branchvars[j] == var )
802 break;
803 }
804 /* if the loop above is stopped with `break`, `j < nbranchvars` is not satisfied.
805 * then, go to the next iteration
806 */
807 if ( j < nbranchvars )
808 continue;
809 }
810
811 /* the variable is not already in the array, so store it */
812 if ( nbranchvars >= maxnbranchvars )
813 {
814 assert( nbranchvars == maxnbranchvars );
815 assert( maxnbranchvars > 0 );
816 maxnbranchvars = SCIPcalcMemGrowSize(scip, maxnbranchvars + 1);
817 SCIP_CALL( SCIPreallocBufferArray(scip, &branchvars, maxnbranchvars) );
818 }
819 assert( nbranchvars < maxnbranchvars );
820 branchvars[nbranchvars++] = var;
821 }
822 }
823
824 /* skip orbitopes whose variable matrices do not contain any branching variable */
825 if ( nbranchvars <= 0 )
826 goto FREE;
827
828 SCIP_CALL( SCIPallocBlockMemory(scip, &newnodeinfo) );
829 newnodeinfo->nodenumber = SCIPnodeGetNumber(eventnode);
830 newnodeinfo->colswaps = NULL;
831 newnodeinfo->ncolswaps = 0;
832 newnodeinfo->rows = NULL;
833 newnodeinfo->nrows = 0;
834
835 /* store data about row ordering */
836 if ( orbidata->rowordering != SCIP_ROWORDERING_NONE )
837 {
838 int* roworder;
839 int nselrows;
840
841 assert( orbidata->nrows > 0 );
842 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
843
844 /* get the present row order up to this node */
845 SCIP_CALL( getRowOrder(scip, orbidata, eventnode, &roworder, &nselrows) );
846 assert( roworder != NULL );
847
848 /* extend the row fixings with the steps from this node */
849 for (i = 0; i < nbranchvars; ++i)
850 {
851 var = branchvars[i];
852
853 assert( SCIPhashmapExists(orbidata->rowindexmap, (void*) var) ); /* otherwise was not added to branchvars */
854 rowid = SCIPhashmapGetImageInt(orbidata->rowindexmap, (void*) var);
855 assert( rowid >= 0 );
856 assert( rowid < orbidata->nrows );
857
858 /* avoid adding row to row order twice */
859 if ( nselrows > 0 )
860 {
861 for (j = 0; j < nselrows; ++j)
862 {
863 if ( rowid == roworder[j] )
864 break;
865 }
866 if ( j < nselrows ) /* if the loop is interrupted */
867 continue;
868 }
869
870 /* if we end up here, the row index does not appear for any ancestor or the present row order */
871
872 /* append rowid to present roworder */
873 roworder[nselrows++] = rowid;
874
875 /* mark that this row index is the new one in the node */
876 if ( newnodeinfo->rows == NULL )
877 {
878 assert( newnodeinfo->nrows == 0 );
879 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->rows, newnodeinfo->nrows + 1) );
880 }
881 else
882 {
883 /* reallocate with linear increments, because we expect 1 branching variable most of the time */
885 newnodeinfo->nrows, newnodeinfo->nrows + 1) );
886 }
887 newnodeinfo->rows[newnodeinfo->nrows++] = rowid;
888 }
889
890 freeRowOrder(scip, orbidata, &roworder);
891 }
892
893 /* store data about column ordering */
894 if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE )
895 {
896 int* colorder;
897 int* colorderinv;
898 COLSWAP* thiscolswap;
899 COLSWAP tmpcolswap;
900
901 assert( orbidata->ncols > 0 );
902 SCIP_CALL( SCIPallocBufferArray(scip, &colorder, orbidata->ncols) );
903 SCIP_CALL( SCIPallocBufferArray(scip, &colorderinv, orbidata->ncols) );
904
905 /* populate colorder with standard ordering */
906 for (i = 0; i < orbidata->ncols; ++i)
907 colorder[i] = i;
908
909 /* introduce inverse column ordering */
910 for (i = 0; i < orbidata->ncols; ++i)
911 colorderinv[i] = i;
912
913 /* get the rooted path
914 *
915 * We want to iterate through the bound changes in the order of the rooted path to this node.
916 */
917 node = SCIPnodeGetParent(eventnode);
918 if ( node != NULL )
919 {
920 SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, colorder, colorderinv) );
921 }
922
923 /* get the swap for this node */
924 for (i = 0; i < nbranchvars; ++i)
925 {
927 colorderinv, branchvars[i], &tmpcolswap) );
928
929 /* skip trivial swaps of columns */
930 if ( tmpcolswap.from == tmpcolswap.to ) /*lint !e644*/
931 continue;
932
933 /* mark that this row index is the new one in the node */
934 if ( newnodeinfo->rows == NULL )
935 {
936 assert( newnodeinfo->nrows == 0 );
937 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps + 1) );
938 }
939 else
940 {
941 /* reallocate with linear increments, because we expect 1 branching variable most of the time */
942 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps,
943 newnodeinfo->ncolswaps + 1) );
944 }
945 thiscolswap = &(newnodeinfo->colswaps[newnodeinfo->ncolswaps++]);
946 thiscolswap->from = tmpcolswap.from; /*lint !e644*/
947 thiscolswap->to = tmpcolswap.to; /*lint !e644*/
948 }
949
950 SCIPfreeBufferArray(scip, &colorder);
951 SCIPfreeBufferArray(scip, &colorderinv);
952 }
953
954 /* store updates of row/column order or free memory if no change applied */
955 if ( newnodeinfo->nrows > 0 || newnodeinfo->ncolswaps > 0 )
956 {
957 SCIP_CALL( SCIPhashtableSafeInsert(orbidata->nodeinfos, newnodeinfo) );
958 }
959 else
960 {
961 SCIPfreeBlockMemory(scip, &newnodeinfo);
962 }
963
964FREE:
965 SCIPfreeBufferArray(scip, &rootedpath);
966 SCIPfreeBufferArray(scip, &branchvars);
967
968 return SCIP_OKAY;
969} /*lint !e715*/
970
971
972/** at branching decisions, maintains the column swap and potential new rows in the orbitope */
973static
975{
976 switch (SCIPeventGetType(event))
977 {
979 return eventExecNodeBranched(scip, eventhdlr, event, eventdata);
980 default:
981 SCIPerrorMessage("Eventhandler " EVENTHDLR_NAME " is called with an unsupported eventtype.\n");
982 return SCIP_ERROR;
983 }
984}
985
986
987/** returns whether a row contains potential branching variables */
988static
990 SCIP* scip, /**< SCIP data structure */
991 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
992 ORBITOPEDATA* orbidata, /**< symmetry handling data for orbitopal structure */
993 int rowid /**< row id for which to check */
994 )
995{
996 SCIP_VAR* var;
997#ifndef NDEBUG
998 int c;
999#endif
1000
1001 assert( scip != NULL );
1002 assert( orbireddata != NULL );
1003 assert( orbidata != NULL );
1004 assert( orbidata->nrows > 0 );
1005 assert( orbidata->ncols > 0 );
1006 assert( rowid >= 0 );
1007 assert( rowid < orbidata->nrows );
1008 assert( orbidata->vars != NULL );
1009 assert( orbidata->vars[rowid * orbidata->ncols] ); /* variable in first column must be set */
1010
1011 /* get the first variable from the row */
1012 var = orbidata->vars[rowid * orbidata->ncols];
1013
1014 /* debugging: the variable types in a row should all be the same */
1015#ifndef NDEBUG
1016 for (c = 1; c < orbidata->ncols; ++c)
1017 {
1018 /* the actual vartypes can be different,
1019 * for example when an INTEGER vartype turns into BINARY due to bound changes
1020 */
1021 assert( vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(var)) ==
1022 vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(orbidata->vars[rowid * orbidata->ncols + c])) );
1023 }
1024#endif
1025
1026 return vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(var));
1027}
1028
1029
1030/** frees orbitope data */
1031static
1033 SCIP* scip, /**< SCIP data structure */
1034 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
1035 ORBITOPEDATA** orbidata /**< pointer to orbitope data */
1036 )
1037{
1038 BNBNODEINFO* nodeinfo;
1039 int i;
1040 int nentries;
1041 int nelem;
1042
1043 assert( scip != NULL );
1044 assert( orbireddata != NULL );
1045 assert( orbidata != NULL );
1046 assert( *orbidata != NULL );
1047 assert( (*orbidata)->vars != NULL );
1048 assert( (*orbidata)->nrows > 0 );
1049 assert( (*orbidata)->ncols > 0 );
1050 assert( (*orbidata)->nrows * (*orbidata)->ncols > 0 );
1051 assert( SCIPisTransformed(scip) );
1052
1053 /* free data if orbitopal reduction is dynamic */
1054 if ( (*orbidata)->columnordering != SCIP_COLUMNORDERING_NONE || (*orbidata)->rowordering != SCIP_ROWORDERING_NONE )
1055 {
1056 /* drop event */
1057 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED, orbireddata->eventhdlr,
1058 (SCIP_EVENTDATA*) *orbidata, -1 ) );
1059
1060 /* free nodeinfos */
1061 nentries = SCIPhashtableGetNEntries((*orbidata)->nodeinfos);
1062 for (i = 0; i < nentries; ++i)
1063 {
1064 /* @todo in principle, can deal with memory sparsity by first getting all nodeinfos,
1065 * then sorting by address and free them in descending order
1066 */
1067 nodeinfo = (BNBNODEINFO*) (SCIPhashtableGetEntry((*orbidata)->nodeinfos, i));
1068 if ( nodeinfo == NULL )
1069 continue;
1070
1071 assert( nodeinfo != NULL );
1072 assert( nodeinfo->nrows > 0 || nodeinfo->ncolswaps > 0 );
1073
1074 assert( (nodeinfo->ncolswaps == 0) != (nodeinfo->colswaps != NULL) );
1075 SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->colswaps), nodeinfo->ncolswaps);
1076
1077 assert( (nodeinfo->nrows == 0) != (nodeinfo->rows != NULL) );
1078 SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->rows), nodeinfo->nrows);
1079
1080 SCIPfreeBlockMemory(scip, &nodeinfo);
1081 }
1082 SCIPhashtableFree(&((*orbidata)->nodeinfos));
1083 }
1084
1085 /* free index lookup hashsets */
1086 SCIPhashmapFree(&((*orbidata)->colindexmap));
1087 SCIPhashmapFree(&((*orbidata)->rowindexmap));
1088
1089 /* free and release vars */
1090 nelem = (*orbidata)->nrows * (*orbidata)->ncols;
1091 assert( nelem > 0 );
1092 for (i = 0; i < nelem; ++i)
1093 {
1094 SCIP_CALL( SCIPreleaseVar(scip, &(*orbidata)->vars[i]) );
1095 }
1096 SCIPfreeBlockMemoryArray(scip, &((*orbidata)->vars), (*orbidata)->nrows * (*orbidata)->ncols); /*lint !e647*/
1097
1098 SCIPfreeBlockMemory(scip, orbidata);
1099
1100 return SCIP_OKAY;
1101}
1102
1103
1104/** adds an orbitope to the orbitopal reduction data */
1105static
1107 SCIP* scip, /**< SCIP data structure */
1108 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */
1109 SCIP_ROWORDERING rowordering, /**< specifies how rows of orbitope are ordered */
1110 SCIP_COLUMNORDERING colordering, /**< specifies how columnss of orbitope are ordered */
1111 SCIP_VAR** vars, /**< variables array, must have size nrows * ncols */
1112 int nrows, /**< number of rows in orbitope */
1113 int ncols, /**< number of columns in orbitope */
1114 SCIP_Bool* success /**< to store whether the component is successfully added */
1115 )
1116{
1117 ORBITOPEDATA* orbidata;
1118 SCIP_VAR* var;
1119 int i;
1120 int rowid;
1121 int colid;
1122 int nelem;
1123
1124 assert( scip != NULL );
1125 assert( orbireddata != NULL );
1126 assert( orbireddata->eventhdlr != NULL );
1127 assert( vars != NULL );
1128 assert( nrows >= 0 );
1129 assert( ncols >= 0 );
1130
1131 nelem = nrows * ncols;
1132 assert( nelem >= 0 );
1133
1134 /* prevent trivial case with empty orbitope */
1135 if ( nelem == 0 )
1136 {
1137 *success = FALSE;
1138 return SCIP_OKAY;
1139 }
1140
1141 *success = TRUE;
1142
1143 SCIP_CALL( SCIPallocBlockMemory(scip, &orbidata) );
1144
1145 orbidata->nrows = nrows;
1146 orbidata->ncols = ncols;
1147 orbidata->columnordering = colordering;
1148 orbidata->rowordering = rowordering;
1149
1150#ifndef NDEBUG
1151 orbidata->lastnodenumber = -1;
1152 orbidata->dbghash = 0;
1153#endif
1154
1155 /* variable array enumerates the orbitope matrix row-wise */
1156 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbidata->vars, nelem) );
1157
1158 /* create row and column index lookup maps */
1160 SCIP_CALL( SCIPhashmapCreate(&orbidata->colindexmap, SCIPblkmem(scip), ncols) );
1161
1162 SCIPdebugMessage("Orbitope variables for (%dx%d) orbitope with orbidata %p\n", nrows, ncols, (void*) orbidata);
1163
1164 /* populate variable array defining orbitope matrix for orbitope data */
1165 for (i = 0, rowid = 0, colid = 0; i < nelem; ++i, ++colid)
1166 {
1167 if ( colid == ncols )
1168 {
1169 colid = 0;
1170 ++rowid;
1171 }
1172 assert( nrows > 0 );
1173 assert( ncols > 0 );
1174 assert( rowid == i / ncols );
1175 assert( colid == i % ncols );
1176
1177 var = vars[i];
1178 assert( var != NULL );
1179 assert( SCIPvarIsTransformed(var) );
1180
1182 SCIP_CALL( SCIPcaptureVar(scip, var) );
1183
1184 orbidata->vars[i] = var;
1185
1186 /* variables cannot be repeated in the variable matrix */
1187 assert( ! SCIPhashmapExists(orbidata->rowindexmap, var) );
1188 SCIP_CALL( SCIPhashmapInsertInt(orbidata->rowindexmap, var, rowid) );
1189
1190 assert( ! SCIPhashmapExists(orbidata->colindexmap, var) );
1191 SCIP_CALL( SCIPhashmapInsertInt(orbidata->colindexmap, var, colid) );
1192
1193 SCIPdebugMessage("%4d %4d -> %s\n", rowid, colid, var->name);
1194 }
1195
1196 /* count number of branchable rows in orbitope */
1197 orbidata->nbranchrows = 0;
1198 /* @todo at getRowData: If nselrows == nbranchrows, append the non-branch rows (like before) */
1199 for (i = 0; i < nrows; ++i)
1200 {
1201 if ( rowIsBranchRow(scip, orbireddata, orbidata, i) )
1202 ++orbidata->nbranchrows;
1203 }
1204
1205 /* cannot add orbitope when already branching */
1207
1208 /* possibly create data needed for dynamic orbitopal reduction */
1210 {
1211 /* add the event to store the row and column updates of nodes in the branch-and-bound tree */
1212 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED, orbireddata->eventhdlr,
1213 (SCIP_EVENTDATA*) orbidata, NULL) );
1214
1215 /* nodeinfos: every node that implies a column swap is represented
1216 *
1217 * Assuming at most one branching on every variable implying a column swap, initial hashtable size nelem.
1218 * In case that there are many more rows than columns, we do not expect too many column swaps.
1219 */
1220 SCIP_CALL( SCIPhashtableCreate(&orbidata->nodeinfos, scip->mem->probmem, MIN(16 * ncols + 64, nelem),
1221 hashGetKeyBnbnodeinfo, hashKeyEqBnbnodeinfo, hashKeyValBnbnodeinfo, NULL) );
1222 }
1223
1224 /* resize orbitope array if needed */
1225 assert( orbireddata->norbitopes >= 0 );
1226 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
1227 assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes );
1228 if ( orbireddata->norbitopes == orbireddata->maxnorbitopes )
1229 {
1230 int newsize;
1231
1232 newsize = SCIPcalcMemGrowSize(scip, orbireddata->norbitopes + 1);
1233 assert( newsize >= 0 );
1234
1235 if ( orbireddata->norbitopes == 0 )
1236 {
1237 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbireddata->orbitopes, newsize) );
1238 }
1239 else
1240 {
1241 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orbireddata->orbitopes, orbireddata->norbitopes, newsize) );
1242 }
1243
1244 orbireddata->maxnorbitopes = newsize;
1245 }
1246 assert( orbireddata->orbitopes != NULL );
1247 assert( orbireddata->norbitopes < orbireddata->maxnorbitopes );
1248
1249 /* add orbitope to orbitopal reduction data */
1250 assert( orbireddata->norbitopes < orbireddata->maxnorbitopes );
1251 orbireddata->orbitopes[orbireddata->norbitopes++] = orbidata;
1252
1253 SCIPdebugMsg(scip, "Added orbitope for orbitopal reduction of size %d by %d\n", nrows, ncols);
1254
1255 return SCIP_OKAY;
1256}
1257
1258
1259/** frees the column order */
1260static
1262 SCIP* scip, /**< SCIP data structure */
1263 ORBITOPEDATA* orbidata, /**< orbitope data */
1264 int** colorder, /**< colorder array that is initialized with the colorder in the dynamic
1265 * case, of size ncols, and NULL in the static case */
1266 int** colorderinv /**< array with the inverse column order, of size ncols */
1267 )
1268{
1269 assert( scip != NULL );
1270 assert( orbidata != NULL );
1271 assert( colorder != NULL );
1272 assert( colorderinv != NULL );
1273
1274 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
1275 {
1276 assert( *colorder == NULL );
1277 assert( *colorderinv == NULL );
1278 return;
1279 }
1280 assert( *colorder != NULL );
1281 assert( *colorderinv != NULL );
1282
1283 SCIPfreeBlockMemoryArray(scip, colorder, orbidata->ncols);
1284 SCIPfreeBlockMemoryArray(scip, colorderinv, orbidata->ncols);
1285}
1286
1287
1288/** gets the column order at the node
1289 *
1290 * The column order is (deterministically) dynamically decided based on the policy for column ordering.
1291 */
1292static
1294 SCIP* scip, /**< SCIP data structure */
1295 ORBITOPEDATA* orbidata, /**< orbitope data */
1296 SCIP_NODE* eventnode, /**< node where this should be determined at */
1297 int** colorder, /**< array to populate with column order, of size ncols */
1298 int** colorderinv /**< array to populate with inverse column order, of size ncols */
1299 )
1300{
1301 SCIP_NODE* node;
1302 SCIP_NODE** rootedpath;
1303 int i;
1304 int depth;
1305 int ncols;
1306
1307 assert( scip != NULL );
1308 assert( orbidata != NULL );
1309 assert( eventnode != NULL );
1310 assert( colorder != NULL );
1311 assert( colorderinv != NULL );
1312
1313 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
1314 {
1315 *colorder = NULL;
1316 *colorderinv = NULL;
1317 return SCIP_OKAY;
1318 }
1319 ncols = orbidata->ncols;
1320 assert( ncols > 0 );
1321
1322 SCIP_CALL( SCIPallocBlockMemoryArray(scip, colorder, ncols) );
1323 SCIP_CALL( SCIPallocBlockMemoryArray(scip, colorderinv, ncols) );
1324
1325 /* populate colorder with standard ordering */
1326 for (i = 0; i < ncols; ++i)
1327 (*colorder)[i] = i;
1328
1329 /* introduce inverse column ordering */
1330 for (i = 0; i < ncols; ++i)
1331 (*colorderinv)[i] = i;
1332
1333 /* get the rooted path
1334 *
1335 * We want to iterate through the bound changes in the order of the rooted path to this node.
1336 */
1337 node = SCIPnodeGetParent(eventnode);
1338 if ( node != NULL )
1339 {
1340 depth = SCIPnodeGetDepth(node);
1341 SCIP_CALL( SCIPallocBufferArray(scip, &rootedpath, depth + 1) );
1342 SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, *colorder, *colorderinv) );
1343 SCIPfreeBufferArray(scip, &rootedpath);
1344 }
1345
1346 return SCIP_OKAY;
1347}
1348
1349
1350#ifndef NDEBUG
1351/** checks if the columns of the matrix are lexicographically decreasing, using the specified row and column ordering */
1352static
1354 SCIP* scip, /**< SCIP data structure */
1355 ORBITOPEDATA* orbidata, /**< orbitope data */
1356 int* roworder, /**< array with the row order */
1357 int* colorder, /**< array with the column order */
1358 SCIP_Real* matrix, /**< a matrix */
1359 int nrows, /**< number of rows of matrix */
1360 int ncols, /**< number of cols of matrix */
1361 int* infinitesimal, /**< array specifying where the infinitesimals are at */
1362 SCIP_Bool addinfinitesimals /**< whether infinitesimals are added (TRUE) or subtracted (FALSE) */
1363 )
1364{
1365 int rowid;
1366 int colid;
1367 int idx;
1368 int origrowid;
1369 int origcolid;
1370 int origidx;
1371 SCIP_VAR* var;
1372
1373 assert( scip != NULL );
1374 assert( matrix != NULL );
1375 assert( orbidata != NULL );
1376 assert( orbidata->vars != NULL );
1377 assert( nrows >= 0 );
1378 assert( nrows <= orbidata->nrows );
1379 assert( ncols >= 0 );
1380 assert( ncols <= orbidata->ncols );
1381 assert( infinitesimal != NULL );
1382
1383 /* respect variable bounds */
1384 for (rowid = 0; rowid < nrows; ++rowid)
1385 {
1386 origrowid = getArrayEntryOrIndex(roworder, rowid);
1387 for (colid = 0; colid < ncols; ++colid)
1388 {
1389 origcolid = getArrayEntryOrIndex(colorder, colid);
1390 idx = rowid * ncols + colid;
1391 origidx = origrowid * ncols + origcolid;
1392 var = orbidata->vars[origidx];
1393 assert( SCIPsymGE(scip, matrix[idx], SCIPvarGetLbLocal(var)) );
1394 assert( SCIPsymLE(scip, matrix[idx], SCIPvarGetUbLocal(var)) );
1395 }
1396 }
1397
1398 /* is orbitope */
1399 for (colid = 0; colid < ncols - 1; ++colid)
1400 {
1401 /* compare column colid with colid + 1 */
1402 for (rowid = 0; rowid < nrows; ++rowid)
1403 {
1404 /* entry is >= entry to the right */
1405 assert( SCIPsymGE(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) );
1406
1407 if ( SCIPsymGT(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) )
1408 {
1409 /* critical row */
1410 break;
1411 }
1412 else
1413 {
1414 /* check for infinitesimal values
1415 * If infinitesimals are added (lexminface case), then if the left column has a +epsilon,
1416 * it does not matter whether the right column has +epsilon or not, then the left column is >,
1417 * due to the axioms x + epsilon > x + epsilon and x + epsilon > x.
1418 * Analogously, x > x - epsilon and x - epsilon > x - epsilon.
1419 */
1420 assert( SCIPsymEQ(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) );
1421 if ( addinfinitesimals
1422 ? (infinitesimal[colid] == rowid) /* left has +epsilon term */
1423 : (infinitesimal[colid + 1] == rowid) /* right has -epsilon term */
1424 )
1425 {
1426 /* critical row */
1427 break;
1428 }
1429 }
1430 }
1431 }
1432}
1433#endif
1434
1435#ifndef NDEBUG
1436/** to test if arrays are the same, generates some hash for an array of integers */
1437static
1439 int* array, /**< array */
1440 int len /**< array length */
1441 )
1442{
1443 int i;
1444 unsigned int hash = 0;
1445
1446 assert( array != NULL );
1447 assert( len >= 0 );
1448
1449 for (i = 0; i < len; i++)
1450 {
1451 hash ^= (unsigned int) (array[i]);
1452 hash = (hash << 1) ^ (hash >> 1);
1453 }
1454
1455 return (int) hash;
1456}
1457#endif
1458
1459#ifdef SCIP_MORE_DEBUG
1460/** prints nrows × ncols matrix of floats with 2 decimals */
1461static
1462void debugPrintMatrix(
1463 SCIP_Real* matrix, /**< matrix, encoded as array enumerating the elements row-wise */
1464 int nrows, /**< number of rows */
1465 int ncols /**< number of rows */
1466 )
1467{
1468 int row;
1469 int col;
1470
1471 assert( matrix != NULL );
1472 assert( nrows >= 0 );
1473 assert( ncols >= 0 );
1474
1475 for (row = 0; row < nrows; ++row)
1476 {
1477 SCIPdebugPrintf("[");
1478 for (col = 0; col < ncols; ++col)
1479 {
1480 SCIPdebugPrintf(" %+10.2f", matrix[row * ncols + col]);
1481 }
1482 SCIPdebugPrintf(" ]\n");
1483 }
1484}
1485#endif
1486
1487
1488/** gets the column order at the node */
1489static
1491 SCIP* scip, /**< SCIP data structure */
1492 ORBITOPEDATA* orbidata, /**< orbitope data */
1493 int* roworder, /**< array with the row order (or NULL if identity function is used) */
1494 int nselrows, /**< number of selected rows */
1495 int* colorder, /**< array with the column order (or NULL if identity function is used) */
1496 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1497 int* nfixedvars /**< pointer to counter of number of variable domain reductions */
1498 )
1499{
1500 /* @todo also make "nselcols" to allow for colorders smaller than orbidata->ncols */
1501 SCIP_Real* lexminface = NULL;
1502 int* lexminepsrow = NULL;
1503 SCIP_Real* lexmaxface = NULL;
1504 int* lexmaxepsrow = NULL;
1505 int nelem;
1506 int rowid;
1507 int colid;
1508 int ncols;
1509 int origrowid;
1510 int origcolid;
1511 int origidx;
1512 int i;
1513 int lastunfixed;
1514 SCIP_Real lb;
1515 SCIP_Real ub;
1516 SCIP_Bool iseq;
1517 SCIP_Bool success;
1518 SCIP_VAR* var;
1519 SCIP_VAR* othervar;
1520
1521 assert( scip != NULL );
1522 assert( orbidata != NULL );
1523 assert( orbidata->vars != NULL );
1524 assert( nselrows >= 0 );
1525 assert( infeasible != NULL );
1526 assert( nfixedvars != NULL );
1527
1528 *infeasible = FALSE;
1529
1530 assert( orbidata->nrows > 0 );
1531 assert( orbidata->nrows >= nselrows );
1532 ncols = orbidata->ncols;
1533 assert( ncols > 1 );
1534
1535 /* nothing to propagate without any rows */
1536 if ( nselrows <= 0 )
1537 return SCIP_OKAY;
1538
1539#ifdef SCIP_MORE_DEBUG
1540 /* print matrix for debugging purposes */
1541 {
1542 int k;
1543 int r;
1544 SCIP_VAR* thisvar;
1545 SCIPdebugMessage("Start propagating static orbitope: \n");
1546 SCIPdebugPrintf(">");
1547 for (k = 0; k < ncols; ++k)
1548 {
1549 SCIPdebugPrintf("%12d ", colorder[k]);
1550 }
1551 SCIPdebugPrintf("< (IDs)\n");
1552
1553 for (r = 0; r < nselrows; ++r)
1554 {
1555 SCIPdebugPrintf("[");
1556 for (k = 0; k < ncols; ++k)
1557 {
1558 thisvar = orbidata->vars[roworder[r] * ncols + colorder[k]];
1559 SCIPdebugPrintf("%4s %+1.2f,%+1.2f ", SCIPvarGetName(thisvar),
1560 SCIPvarGetLbLocal(thisvar), SCIPvarGetUbLocal(thisvar));
1561 }
1562 SCIPdebugPrintf("] (row %d)\n", roworder[r]);
1563 }
1564 }
1565#endif
1566
1567 nelem = nselrows * ncols;
1568
1569 /* compute lexmin face */
1570 SCIP_CALL( SCIPallocBufferArray(scip, &lexminface, nelem) );
1571
1572 /* array to store for each column at which row we add an infinitesimal value, initially at none (-1) */
1573 SCIP_CALL( SCIPallocBufferArray(scip, &lexminepsrow, ncols) );
1574 for (colid = 0; colid < ncols; ++colid)
1575 lexminepsrow[colid] = -1;
1576
1577 /* last column takes the minimally possible values. */
1578 colid = ncols - 1;
1579 origcolid = getArrayEntryOrIndex(colorder, colid);
1580 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1581 {
1582 origrowid = getArrayEntryOrIndex(roworder, rowid);
1583 origidx = origrowid * ncols + origcolid;
1584 var = orbidata->vars[origidx];
1585
1586 assert( i == rowid * ncols + colid );
1587 assert( var != NULL );
1588
1589 lexminface[i] = SCIPvarGetLbLocal(var);
1590 }
1591 /* all previous columns: One-column replacement algorithm */
1592 for (colid = ncols - 2; colid >= 0; --colid)
1593 {
1594 /* "rowid" of the last unfixed entry whose domain allows for larger values than the current chosen.
1595 * If there is none, -1. */
1596 lastunfixed = -1;
1597 /* whether column "colid" is the same as column "colid + 1" up (but excluding) to "rowid" */
1598 iseq = TRUE;
1599
1600 origcolid = getArrayEntryOrIndex(colorder, colid);
1601 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1602 {
1603 origrowid = getArrayEntryOrIndex(roworder, rowid);
1604 origidx = origrowid * ncols + origcolid;
1605 assert( i == rowid * ncols + colid );
1606
1607 /* the entry one to the right is not the first column */
1608 assert( (i + 1) % ncols > 0 );
1609
1610 var = orbidata->vars[origidx];
1611 assert( var != NULL );
1612
1613 if ( iseq )
1614 {
1615 /* equality holds up to this row
1616 * Compare to the entry value on the column immediately right.
1617 * The value we choose on the left must be at least this.
1618 * 2 Options:
1619 * Option 1: The upper bound is smaller. Then we're in an infeasible situation. Resolve as described below.
1620 * Option 2: The upper bound is greater or equal.
1621 */
1622 ub = SCIPvarGetUbLocal(var);
1623
1624 /* compare to the value in the column right of it */
1625 if ( SCIPsymLT(scip, ub, lexminface[i + 1]) ||
1626 ( lexminepsrow[colid + 1] == rowid && SCIPsymEQ(scip, ub, lexminface[i + 1]) ) )
1627 {
1628 /* value of this column can only be strictly smaller than the value in the column to its right
1629 * This may not be possible.
1630 * Try to repair: Go back to the last row with "room" left, and make the value minimally larger.
1631 */
1632 if ( lastunfixed >= 0 )
1633 {
1634 /* repair: return to the last row with "room", and increase the lexmin-value at that row. */
1635 assert( SCIPsymEQ(scip, lexminface[lastunfixed * ncols + colid],
1636 lexminface[lastunfixed * ncols + colid + 1]) );
1637 othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid];
1638 switch (SCIPvarGetType(othervar))
1639 {
1643 /* discrete type with unit steps: Add one to the bound. */
1644 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1645 assert( SCIPisIntegral(scip, lexminface[lastunfixed * ncols + colid]) );
1646 lexminface[lastunfixed * ncols + colid] += 1.0;
1647 assert( SCIPisIntegral(scip, lexminface[lastunfixed * ncols + colid]) );
1648 assert( SCIPsymLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1649 break;
1651 /* continuous type, so add an infinitesimal value to the bound */
1652 assert( SCIPsymLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1653 assert( lexminepsrow[colid] == -1 );
1654 lexminepsrow[colid] = lastunfixed;
1655 break;
1656 default:
1657 return SCIP_ERROR;
1658 }
1659 /* now row "lastunfixed" is greater. Restart from here. */
1660 iseq = FALSE;
1661 rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */
1662 i = rowid * ncols + colid;
1663 continue;
1664 }
1665 else
1666 {
1667 /* cannot repair. It is infeasible. */
1668 *infeasible = TRUE;
1669 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), min\n", colid, origcolid);
1670 goto FREE;
1671 }
1672 }
1673 else
1674 {
1675 assert( SCIPsymGE(scip, ub, lexminface[i + 1]) );
1676 lb = SCIPvarGetLbLocal(var);
1677 assert( SCIPsymLE(scip, lb, ub) );
1678 lexminface[i] = MAX(lexminface[i + 1], lb);
1679 assert( SCIPsymGE(scip, lexminface[i], lexminface[i + 1]) );
1680
1681 /* are we still equal? */
1682 if ( SCIPsymGT(scip, lexminface[i], lexminface[i + 1]) )
1683 iseq = FALSE;
1684 else if ( lexminepsrow[colid + 1] == rowid )
1685 {
1686 assert( SCIPsymEQ(scip, lexminface[i], lexminface[i + 1]) );
1687 assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid])
1689 assert( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS );
1690 /* right column (colid+1) has value x + epsilon, left column (colid) has value x, now
1691 * must also become x + epsilon in order to be larger or equal
1692 * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon.
1693 */
1694 iseq = FALSE;
1695 assert( lexminepsrow[colid] == -1 );
1696 lexminepsrow[colid] = rowid;
1697 }
1698
1699 /* is there room left to increase this variable further? */
1700 switch (SCIPvarGetType(var))
1701 {
1705 /* discrete type with unit steps: Add one to the bound. */
1706 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1707 /* @todo in principle, this can be made more tight using the hole-lists... */
1708 assert( SCIPisIntegral(scip, lexminface[i]) );
1709 if ( SCIPsymLE(scip, lexminface[i] + 1.0, ub) )
1710 lastunfixed = rowid;
1711 break;
1713 /* continuous type: if we can add an infinitesimal value to the current lexminface[i] value,
1714 * mark row as 'lastunfixed'
1715 */
1716 if ( SCIPsymLT(scip, lexminface[i], ub) )
1717 lastunfixed = rowid;
1718 break;
1719 default:
1720 return SCIP_ERROR;
1721 }
1722 }
1723 }
1724 else
1725 {
1726 /* there had been a row before which breaks the equality-condition, choose minimally possible value */
1727 lexminface[i] = SCIPvarGetLbLocal(var);
1728 }
1729 }
1730 }
1731
1732#ifndef NDEBUG
1733 /* sanity checks */
1734 assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexminface, nselrows, ncols, lexminepsrow, TRUE);
1735#endif
1736
1737 /* compute lexmax face */
1738 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxface, nelem) );
1739
1740 /* array to store for each column at which row we subtract an infinitesimal value, initially at none (-1) */
1741 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxepsrow, ncols) );
1742 for (colid = 0; colid < ncols; ++colid)
1743 lexmaxepsrow[colid] = -1;
1744
1745 /* first column, fill all unfixed entries with maximally possible values */
1746 colid = 0;
1747 origcolid = getArrayEntryOrIndex(colorder, colid);
1748 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1749 {
1750 origrowid = getArrayEntryOrIndex(roworder, rowid);
1751 origidx = origrowid * ncols + origcolid;
1752 var = orbidata->vars[origidx];
1753
1754 assert( i == rowid * ncols + colid );
1755 assert( var != NULL );
1756
1757 lexmaxface[i] = SCIPvarGetUbLocal(var);
1758 }
1759 /* all next columns: One-column replacement algorithm */
1760 for (colid = 1; colid < ncols; ++colid)
1761 {
1762 /* "rowid" of the last unfixed entry whose domain allows for smaller values than the current chosen.
1763 * If there is none, -1. */
1764 lastunfixed = -1;
1765 /* whether column "colid" is the same as column "colid - 1" up (but excluding) to "rowid" */
1766 iseq = TRUE;
1767
1768 origcolid = getArrayEntryOrIndex(colorder, colid);
1769 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1770 {
1771 origrowid = getArrayEntryOrIndex(roworder, rowid);
1772 origidx = origrowid * ncols + origcolid;
1773 assert( i == rowid * ncols + colid );
1774
1775 /* the entry one to the left is not the last column, i.e., this column cannot be the first column */
1776 assert( i % ncols > 0 );
1777
1778 var = orbidata->vars[origidx];
1779 assert( var != NULL );
1780
1781 if ( iseq )
1782 {
1783 /* equality holds up to this row
1784 * Compare to the entry value on the column immediately left.
1785 * The value we choose on the right must be at most this.
1786 * 2 Options:
1787 * Option 1: The lower bound is larger. Then we're in an infeasible situation. Resolve as described below.
1788 * Option 2: The lower bound is smaller or equal.
1789 */
1790 lb = SCIPvarGetLbLocal(var);
1791
1792 /* compare to the value in the column left of it */
1793 if ( SCIPsymGT(scip, lb, lexmaxface[i - 1]) ||
1794 ( lexmaxepsrow[colid - 1] == rowid && SCIPsymEQ(scip, lb, lexmaxface[i - 1]) ) )
1795 {
1796 /* value of this column can only be strictly larger than the value in the column to its left
1797 * This may not be possible.
1798 * Try to repair: Go back to the last row with "room" left, and make the value minimally smaller.
1799 */
1800 if ( lastunfixed >= 0 )
1801 {
1802 /* repair: return to the last row with "room", and decrease the lexmax-value at that row. */
1803 assert( SCIPsymEQ(scip, lexmaxface[lastunfixed * ncols + colid],
1804 lexmaxface[lastunfixed * ncols + colid - 1]) );
1805 othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid];
1806 switch (SCIPvarGetType(othervar))
1807 {
1811 /* discrete type with unit steps: Remove one from the lexmax-value. */
1812 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1813 assert( SCIPisIntegral(scip, lexmaxface[lastunfixed * ncols + colid]) );
1814 lexmaxface[lastunfixed * ncols + colid] -= 1.0;
1815 assert( SCIPisIntegral(scip, lexmaxface[lastunfixed * ncols + colid]) );
1816 assert( SCIPsymGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) );
1817 assert( SCIPsymLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1818 break;
1820 /* continuous type, so subtract an infinitesimal value to the bound */
1821 assert( SCIPsymGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) );
1822 assert( SCIPsymLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1823 assert( lexmaxepsrow[colid] == -1 );
1824 lexmaxepsrow[colid] = lastunfixed;
1825 break;
1826 default:
1827 return SCIP_ERROR;
1828 }
1829 /* now row "lastunfixed" is greater. Restart from here. */
1830 iseq = FALSE;
1831 rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */
1832 i = rowid * ncols + colid;
1833 continue;
1834 }
1835 else
1836 {
1837 /* cannot repair. It is infeasible. */
1838 *infeasible = TRUE;
1839 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), max\n", colid, origcolid);
1840 goto FREE;
1841 }
1842 }
1843 else
1844 {
1845 assert( SCIPsymLE(scip, lb, lexmaxface[i - 1]) );
1846 ub = SCIPvarGetUbLocal(var);
1847 assert( SCIPsymLE(scip, lb, ub) );
1848 lexmaxface[i] = MIN(lexmaxface[i - 1], ub);
1849 assert( SCIPsymGE(scip, lexmaxface[i - 1], lexmaxface[i]) );
1850
1851 /* are we still equal? */
1852 if ( SCIPsymGT(scip, lexmaxface[i - 1], lexmaxface[i]) )
1853 iseq = FALSE;
1854 else if ( lexmaxepsrow[colid - 1] == rowid )
1855 {
1856 assert( SCIPsymEQ(scip, lexmaxface[i - 1], lexmaxface[i]) );
1857 assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid])
1859 assert( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS );
1860 /* left column (colid-1) has value x - epsilon, right column (colid) has value x, now
1861 * must also become x - epsilon in order to be larger or equal
1862 * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon.
1863 */
1864 iseq = FALSE;
1865 assert( lexmaxepsrow[colid] == -1 );
1866 lexmaxepsrow[colid] = rowid;
1867 }
1868
1869 /* is there room left to decrease this variable further? */
1870 switch (SCIPvarGetType(var))
1871 {
1875 /* discrete type with unit steps: Remove one from the lexmax-value. */
1876 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1877 /* @todo in principle, this can be made more tight using the hole-lists... */
1878 assert( SCIPisIntegral(scip, lexmaxface[i]) );
1879 if ( SCIPsymGE(scip, lexmaxface[i] - 1.0, lb) )
1880 lastunfixed = rowid;
1881 break;
1883 /* continuous type: if we can subtract an infinitesimal value to the current lexmaxface[i] value,
1884 * mark row as 'lastunfixed'
1885 */
1886 if ( SCIPsymGT(scip, lexmaxface[i], lb) )
1887 lastunfixed = rowid;
1888 break;
1889 default:
1890 return SCIP_ERROR;
1891 }
1892 }
1893 }
1894 else
1895 {
1896 /* there had been a row before which breaks the equality-condition, choose maximally possible value */
1897 lexmaxface[i] = SCIPvarGetUbLocal(var);
1898 }
1899 }
1900 }
1901
1902#ifndef NDEBUG
1903 /* sanity checks */
1904 assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexmaxface, nselrows, ncols, lexmaxepsrow, FALSE);
1905#endif
1906
1907#ifdef SCIP_MORE_DEBUG
1908 /* show lexmin and lexmax face */
1909 SCIPdebugMessage("Lex min face\n");
1910 debugPrintMatrix(lexminface, nselrows, ncols);
1911 SCIPdebugMessage("Lex max face\n");
1912 debugPrintMatrix(lexmaxface, nselrows, ncols);
1913#endif
1914
1915 /* compare the two column-wise and apply domain reductions */
1916 for (colid = 0; colid < ncols; ++colid)
1917 {
1918 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1919 {
1920 assert( i == rowid * ncols + colid );
1921
1922 /* get var */
1923 origrowid = getArrayEntryOrIndex(roworder, rowid);
1924 origcolid = getArrayEntryOrIndex(colorder, colid);
1925 origidx = origrowid * ncols + origcolid;
1926 var = orbidata->vars[origidx];
1927
1928 if ( SCIPsymEQ(scip, lexminface[i], lexmaxface[i]) )
1929 {
1930 /* tighten LB and UB to same value (i.e. fixing) */
1931 SCIP_CALL( SCIPtightenVarLb(scip, var, lexminface[i], FALSE, infeasible, &success) );
1932 if ( success )
1933 {
1934 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1935 *nfixedvars += 1;
1936 }
1937 else
1938 {
1939 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1940 lexminface[i]);
1941 }
1942 if ( *infeasible )
1943 {
1944 SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1945 var->name, rowid, colid, lexminface[i]);
1946 goto FREE;
1947 }
1948
1949 SCIP_CALL( SCIPtightenVarUb(scip, var, lexminface[i], FALSE, infeasible, &success) );
1950 if ( success )
1951 {
1952 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1953 *nfixedvars += 1;
1954 }
1955 else
1956 {
1957 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1958 lexminface[i]);
1959 }
1960 if ( *infeasible )
1961 {
1962 SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1963 var->name, rowid, colid, lexminface[i]);
1964 goto FREE;
1965 }
1966 }
1967 else
1968 {
1969 /* This is the row index where the min- and max-face have a different value for this column entry.
1970 * Update the lower bound and upper bound */
1971
1972 /* lower bound, based on lexminface */
1973 SCIP_CALL( SCIPtightenVarLb(scip, var, lexminface[i], FALSE, infeasible, &success) );
1974 if ( success )
1975 {
1976 SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid,
1977 lexminface[i]);
1978 *nfixedvars += 1;
1979 }
1980 else
1981 {
1982 SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name,
1983 rowid, colid, lexminface[i]);
1984 }
1985 if ( *infeasible )
1986 {
1987 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s (%3d,%3d) to %5.2f\n",
1988 var->name, rowid, colid, lexminface[i]);
1989 goto FREE;
1990 }
1991
1992 /* upper bound, based on lexmaxface */
1993 SCIP_CALL( SCIPtightenVarUb(scip, var, lexmaxface[i], FALSE, infeasible, &success) );
1994 if ( success )
1995 {
1996 SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid,
1997 lexmaxface[i]);
1998 *nfixedvars += 1;
1999 }
2000 else
2001 {
2002 SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name,
2003 rowid, colid, lexmaxface[i]);
2004 }
2005 if ( *infeasible )
2006 {
2007 SCIPdebugMessage("Detected infeasibility restricting variable UB %12s (%3d,%3d) to %5.2f\n",
2008 var->name, rowid, colid, lexmaxface[i]);
2009 goto FREE;
2010 }
2011 break;
2012 }
2013 }
2014 }
2015
2016FREE:
2017 SCIPfreeBufferArrayNull(scip, &lexmaxepsrow);
2018 SCIPfreeBufferArrayNull(scip, &lexmaxface);
2019 SCIPfreeBufferArrayNull(scip, &lexminepsrow);
2020 SCIPfreeBufferArrayNull(scip, &lexminface);
2021
2022 return SCIP_OKAY;
2023}
2024
2025
2026/** propagation method for a single orbitope matrix */
2027static
2029 SCIP* scip, /**< SCIP data structure */
2030 ORBITOPEDATA* orbidata, /**< orbitope data */
2031 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
2032 int* nfixedvars /**< pointer to store the number of found domain reductions */
2033 )
2034{
2035 SCIP_NODE* focusnode;
2036 int* roworder;
2037 int nselrows;
2038 int* colorder;
2039 int* colorderinv;
2040
2041 assert( scip != NULL );
2042 assert( orbidata != NULL );
2043 assert( infeasible != NULL );
2044 assert( nfixedvars != NULL );
2045
2046 *nfixedvars = 0;
2047 *infeasible = FALSE;
2048
2049 assert( orbidata->ncols > 0 );
2050 assert( orbidata->nrows > 0 );
2051
2052 focusnode = SCIPgetFocusNode(scip);
2053 assert( focusnode != NULL );
2054
2055 /* get row order */
2056 SCIP_CALL( getRowOrder(scip, orbidata, focusnode, &roworder, &nselrows) );
2057 assert( nselrows >= 0 );
2058 assert( nselrows <= orbidata->nrows );
2059 if ( nselrows == 0 )
2060 goto FREEROWS;
2061
2062 /* get column order */
2063 SCIP_CALL( getColumnOrder(scip, orbidata, focusnode, &colorder, &colorderinv) );
2064
2065#ifndef NDEBUG
2066 /* DEBUG: if propagation is repeated in the same node, the same column order and row order is needed */
2067 /* @todo: performance: move roworder and colorder to orbidata, then re-use */
2068 {
2069 int colhash = (colorder == NULL) ? 1 : debugGetArrayHash(colorder, orbidata->ncols);
2070 int rowhash = (roworder == NULL) ? 0 : debugGetArrayHash(roworder, nselrows);
2071 int hash = colhash ^ rowhash;
2072
2073#ifdef SCIP_DEBUG
2074 SCIPdebugPrintf("Col hash %32d; Row hash %32d; Hash %32d\n", colhash, rowhash, hash);
2075 {
2076 SCIP_NODE* tmpnode;
2077 tmpnode = SCIPgetFocusNode(scip);
2078 while ( tmpnode != NULL )
2079 {
2080 int nbranchings, nconsprop, nprop;
2081 SCIPnodeGetDomchg(tmpnode);
2082 SCIPnodeGetNDomchg(tmpnode, &nbranchings, &nconsprop, &nprop);
2083 SCIPdebugPrintf(" node %lld: (%d, %d, %d) \n", tmpnode->number, nbranchings, nconsprop, nprop);
2084 tmpnode = SCIPnodeGetParent(tmpnode);
2085 }
2086 }
2087#endif
2088
2089 assert( SCIPgetCurrentNode(scip) == SCIPgetFocusNode(scip) ); /* no probing */
2091 {
2092 assert( orbidata->dbghash == hash );
2093 }
2094 orbidata->dbghash = hash;
2095 }
2097#endif
2098
2099 SCIP_CALL( propagateStaticOrbitope(scip, orbidata, roworder, nselrows, colorder, infeasible, nfixedvars) );
2100
2101 freeColumnOrder(scip, orbidata, &colorder, &colorderinv);
2102FREEROWS:
2103 freeRowOrder(scip, orbidata, &roworder);
2104
2105#ifdef SCIP_MORE_DEBUG
2106 SCIPdebugPrintf("\n\n");
2107#endif
2108
2109 return SCIP_OKAY;
2110}
2111
2112
2113/*
2114 * Interface methods
2115 */
2116
2117
2118/** gets the number of reductions */
2120 SCIP* scip, /**< SCIP data structure */
2121 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */
2122 int* nred, /**< total number of reductions applied */
2123 int* ncutoff /**< total number of cutoffs applied */
2124 )
2125{
2126 assert( scip != NULL );
2127 assert( orbireddata != NULL );
2128 assert( nred != NULL );
2129
2130 *nred = orbireddata->nred;
2131 *ncutoff = orbireddata->ncutoff;
2132
2133 return SCIP_OKAY;
2134}
2135
2136
2137/** prints orbitopal reduction data */
2139 SCIP* scip, /**< SCIP data structure */
2140 SCIP_ORBITOPALREDDATA* orbireddata /**< orbitopal reduction data structure */
2141 )
2142{
2143 int i;
2144
2145 assert( scip != NULL );
2146 assert( orbireddata != NULL );
2147
2148 if ( orbireddata->norbitopes == 0 )
2149 {
2150 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " orbitopal reduction: no components\n");
2151 return SCIP_OKAY;
2152 }
2153
2155 " orbitopal reduction: %4d components: ", orbireddata->norbitopes);
2156 for (i = 0; i < orbireddata->norbitopes; ++i)
2157 {
2158 if ( i > 0 )
2161 "%dx%d", orbireddata->orbitopes[i]->nrows, orbireddata->orbitopes[i]->ncols);
2162 }
2164
2165 return SCIP_OKAY;
2166}
2167
2168
2169/** propagates orbitopal reduction */
2171 SCIP* scip, /**< SCIP data structure */
2172 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */
2173 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
2174 int* nred, /**< pointer to store the number of domain reductions */
2175 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
2176 * only set this to TRUE when a reduction is found, never set to FALSE */
2177 )
2178{
2179 ORBITOPEDATA* orbidata;
2180 int c;
2181 int thisfixedvars;
2182
2183 assert( scip != NULL );
2184 assert( orbireddata != NULL );
2185 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
2186 assert( infeasible != NULL );
2187 assert( nred != NULL );
2188
2189 *infeasible = FALSE;
2190 *nred = 0;
2191
2192 /* @todo Can the following be removed? */
2193 /* @todo shouldn't this be SCIPallowWeakDualReds, since we do not regard the objective */
2195 return SCIP_OKAY;
2196
2197 /* cannot do anything during probing
2198 * @todo can find deductions for the probing node, maybe?
2199 */
2200 if ( SCIPinProbing(scip) )
2201 return SCIP_OKAY;
2202
2203 /* propagate all orbitopes */
2204 for (c = 0; c < orbireddata->norbitopes; ++c)
2205 {
2206 orbidata = orbireddata->orbitopes[c];
2207 assert( orbidata != NULL );
2208
2209 SCIP_CALL( propagateOrbitope(scip, orbidata, infeasible, &thisfixedvars) );
2210 SCIPdebugMessage("Found %d reductions during orbitopal reduction for orbitope %d\n", thisfixedvars, c);
2211 *nred += thisfixedvars;
2212
2213 /* a symmetry propagator has ran, so set didrun to TRUE */
2214 *didrun = TRUE;
2215
2216 /* stop if we find infeasibility in one of the methods */
2217 if ( *infeasible )
2218 {
2219 SCIPdebugMessage("Detected infeasibility during orbitopal reduction for orbitope %d\n", c);
2220 break;
2221 }
2222 }
2223
2224 orbireddata->nred += *nred;
2225 if ( *infeasible )
2226 ++orbireddata->ncutoff;
2227
2228 return SCIP_OKAY;
2229}
2230
2231/** adds orbitopal component to orbitopal symmetry handler */
2233 SCIP* scip, /**< SCIP data structure */
2234 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */
2235 SCIP_ROWORDERING rowordering, /**< specifies how rows of orbitope are ordered */
2236 SCIP_COLUMNORDERING colordering, /**< specifies how columnss of orbitope are ordered */
2237 SCIP_VAR** vars, /**< matrix of variables on which the symmetry acts */
2238 int nrows, /**< number of rows */
2239 int ncols, /**< number of columns */
2240 SCIP_Bool* success /**< to store whether the component is successfully added */
2241 )
2242{
2243 assert( scip != NULL );
2244 assert( orbireddata != NULL );
2245 assert( vars != NULL );
2246 assert( nrows > 0 );
2247 assert( ncols > 0 );
2248
2249 /* dynamic symmetry reductions cannot be performed on original problem */
2250 assert( SCIPisTransformed(scip) );
2251
2252 /* if this is the first time adding an orbitope, check if the nonlinear conshlr exists */
2253 if ( !orbireddata->conshdlr_nonlinear_checked )
2254 {
2255 orbireddata->conshdlr_nonlinear = SCIPfindConshdlr(scip, "nonlinear");
2256 orbireddata->conshdlr_nonlinear_checked = TRUE;
2257 }
2258
2259 /* create orbitope data */
2260 SCIP_CALL( addOrbitope(scip, orbireddata, rowordering, colordering, vars, nrows, ncols, success) );
2261
2262 return SCIP_OKAY;
2263}
2264
2265
2266/** resets orbitopal reduction data structure (clears all orbitopes) */
2268 SCIP* scip, /**< SCIP data structure */
2269 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */
2270 )
2271{
2272 assert( scip != NULL );
2273 assert( orbireddata != NULL );
2274 assert( orbireddata->norbitopes >= 0 );
2275 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
2276 assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes );
2277 assert( orbireddata->eventhdlr != NULL );
2278
2279 /* free orbitopes that are added */
2280 while (orbireddata->norbitopes > 0)
2281 {
2282 SCIP_CALL( freeOrbitope(scip, orbireddata, &(orbireddata->orbitopes[--orbireddata->norbitopes])) );
2283 }
2284 assert( orbireddata->norbitopes == 0 );
2285 SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->orbitopes, orbireddata->maxnorbitopes);
2286 orbireddata->orbitopes = NULL;
2287 orbireddata->maxnorbitopes = 0;
2288
2289 return SCIP_OKAY;
2290}
2291
2292
2293/** frees orbitopal reduction data */
2295 SCIP* scip, /**< SCIP data structure */
2296 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */
2297 )
2298{
2299 assert( scip != NULL );
2300 assert( orbireddata != NULL );
2301 assert( *orbireddata != NULL );
2302
2303 SCIP_CALL( SCIPorbitopalReductionReset(scip, *orbireddata) );
2304
2305 SCIPfreeBlockMemory(scip, orbireddata);
2306 return SCIP_OKAY;
2307}
2308
2309
2310/** initializes structures needed for orbitopal reduction
2311 *
2312 * This is only done exactly once.
2313 */
2315 SCIP* scip, /**< SCIP data structure */
2316 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */
2317 )
2318{
2319 SCIP_EVENTHDLR* eventhdlr;
2320
2321 assert( scip != NULL );
2322 assert( orbireddata != NULL );
2323
2324 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitopalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2326
2327 /* create orbitope handler data */
2328 SCIP_CALL( SCIPallocBlockMemory(scip, orbireddata) );
2329
2330 /* default column ordering param */
2331 SCIP_CALL( SCIPaddIntParam(scip, "propagating/symmetry/" SYMHDLR_NAME "/columnordering",
2332 "The column ordering variant, respects enum SCIP_ColumnOrdering.",
2333 (int*) &(*orbireddata)->defaultcolumnordering, TRUE, DEFAULT_COLUMNORDERING, 0, 4,
2334 NULL, NULL) ); /*lint !e641*/
2335
2336 /* initialize event handler. */
2339 assert( eventhdlr != NULL );
2340 (*orbireddata)->eventhdlr = eventhdlr;
2341
2342 /* orbitopes array */
2343 (*orbireddata)->orbitopes = NULL;
2344 (*orbireddata)->norbitopes = 0;
2345 (*orbireddata)->maxnorbitopes = 0;
2346
2347 /* conshdlr nonlinear */
2348 (*orbireddata)->conshdlr_nonlinear = NULL;
2349 (*orbireddata)->conshdlr_nonlinear_checked = FALSE;
2350
2351 /* counter of total number of reductions and cutoffs */
2352 (*orbireddata)->nred = 0;
2353 (*orbireddata)->ncutoff = 0;
2354
2355 return SCIP_OKAY;
2356}
2357
2358
2359/** returns the default column ordering */
2361 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */
2362 )
2363{
2364 assert( orbireddata != NULL );
2365
2366 return orbireddata->defaultcolumnordering;
2367}
SCIP_Real * r
Definition: circlepacking.c:59
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 SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#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)
Definition: scip_general.c:596
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
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,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
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:7598
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7588
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7773
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2283
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2211
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2321
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2359
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2245
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:5203
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:5320
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:1248
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
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
COLSWAP * colswaps
SCIP_HASHMAP * rowindexmap
SCIP_Longint lastnodenumber
SCIP_HASHTABLE * nodeinfos
SCIP_ROWORDERING rowordering
SCIP_HASHMAP * colindexmap
SCIP_VAR ** vars
SCIP_COLUMNORDERING columnordering
SCIP_Longint number
Definition: struct_tree.h:143
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_DECL_EVENTEXEC(eventExecNodeBranched)
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)
static SCIP_DECL_HASHGETKEY(hashGetKeyBnbnodeinfo)
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_DECL_HASHKEYVAL(hashKeyValBnbnodeinfo)
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
static SCIP_DECL_HASHKEYEQ(hashKeyEqBnbnodeinfo)
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_EVENTTYPE_NODEBRANCHED
Definition: type_event.h:95
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_ERROR
Definition: type_retcode.h:43
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ 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