1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  methods for handling symmetries
28   	 * @author Jasper van Doornmalen
29   	 * @author Christopher Hojny
30   	 * @author Marc Pfetsch
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#ifndef __SCIP_SYMMETRY_H__
36   	#define __SCIP_SYMMETRY_H__
37   	
38   	#include "scip/def.h"
39   	#include "scip/pub_misc.h"
40   	#include "scip/type_retcode.h"
41   	#include "scip/type_scip.h"
42   	#include "scip/type_var.h"
43   	#include <symmetry/type_symmetry.h>
44   	
45   	#ifdef __cplusplus
46   	extern "C" {
47   	#endif
48   	
49   	
50   	/**@addtogroup PublicSymmetryMethods
51   	 *
52   	 * @{
53   	 */
54   	
55   	
56   	/** compute non-trivial orbits of symmetry group
57   	 *
58   	 *  The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
59   	 *  the indices of variables from the permvars array such that variables that are contained in the same orbit appear
60   	 *  consecutively in the orbits array. The variables of the i-th orbit have indices
61   	 *  orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
62   	 *  Note that the description of the orbits ends at orbitbegins[norbits] - 1.
63   	 */
64   	SCIP_EXPORT
65   	SCIP_RETCODE SCIPcomputeOrbitsSym(
66   	   SCIP*                 scip,               /**< SCIP instance */
67   	   SCIP_Bool             issigend,           /**< whether orbits for signed permutations shall be computed */
68   	   SCIP_VAR**            permvars,           /**< variables considered in a permutation array */
69   	   int                   npermvars,          /**< length of a permutation array */
70   	   int**                 perms,              /**< matrix containing in each row a permutation of the symmetry group */
71   	   int                   nperms,             /**< number of permutations encoded in perms */
72   	   int*                  orbits,             /**< array of non-trivial orbits */
73   	   int*                  orbitbegins,        /**< array containing begin positions of new orbits in orbits array */
74   	   int*                  norbits             /**< pointer to number of orbits currently stored in orbits */
75   	   );
76   	
77   	
78   	/** compute non-trivial orbits of symmetry group using filtered generators
79   	 *
80   	 *  The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
81   	 *  the indices of variables from the permvars array such that variables that are contained in the same orbit appear
82   	 *  consecutively in the orbits array. The variables of the i-th orbit have indices
83   	 *  orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
84   	 *  Note that the description of the orbits ends at orbitbegins[norbits] - 1.
85   	 *
86   	 *  Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
87   	 *  filter out permutations.
88   	 */
89   	SCIP_EXPORT
90   	SCIP_RETCODE SCIPcomputeOrbitsFilterSym(
91   	   SCIP*                 scip,               /**< SCIP instance */
92   	   int                   npermvars,          /**< length of a permutation array */
93   	   int**                 permstrans,         /**< transposed matrix containing in each column a
94   	                                              *   permutation of the symmetry group */
95   	   int                   nperms,             /**< number of permutations encoded in perms */
96   	   SCIP_Shortbool*       inactiveperms,      /**< array to store whether permutations are inactive */
97   	   int*                  orbits,             /**< array of non-trivial orbits */
98   	   int*                  orbitbegins,        /**< array containing begin positions of new orbits in orbits array */
99   	   int*                  norbits,            /**< pointer to number of orbits currently stored in orbits */
100  	   int*                  components,         /**< array containing the indices of permutations sorted by components */
101  	   int*                  componentbegins,    /**< array containing in i-th position the first position of
102  	                                              *   component i in components array */
103  	   int*                  vartocomponent,     /**< array containing for each permvar the index of the component it is
104  	                                              *   contained in (-1 if not affected) */
105  	   unsigned*             componentblocked,   /**< array to store which symmetry methods have been used on a component
106  	                                              *   using the same bitset information as for misc/usesymmetry */
107  	   int                   ncomponents,        /**< number of components of symmetry group */
108  	   int                   nmovedpermvars      /**< number of variables moved by any permutation in a symmetry component
109  	                                              *   that is handled by orbital fixing */
110  	   );
111  	
112  	/** compute non-trivial orbits of symmetry group
113  	 *
114  	 *  The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
115  	 *  the indices of variables from the permvars array such that variables that are contained in the same orbit appear
116  	 *  consecutively in the orbits array. The variables of the i-th orbit have indices
117  	 *  orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
118  	 *  Note that the description of the orbits ends at orbitbegins[norbits] - 1.
119  	 *
120  	 *  This function is adapted from SCIPcomputeOrbitsFilterSym().
121  	 */
122  	SCIP_EXPORT
123  	SCIP_RETCODE SCIPcomputeOrbitsComponentsSym(
124  	   SCIP*                 scip,               /**< SCIP instance */
125  	   int                   npermvars,          /**< length of a permutation array */
126  	   int**                 permstrans,         /**< transposed matrix containing in each column a permutation of the symmetry group */
127  	   int                   nperms,             /**< number of permutations encoded in perms */
128  	   int*                  components,         /**< array containing the indices of permutations sorted by components */
129  	   int*                  componentbegins,    /**< array containing in i-th position the first position of component i in components array */
130  	   int*                  vartocomponent,     /**< array containing for each permvar the index of the component it is
131  	                                              *   contained in (-1 if not affected) */
132  	   int                   ncomponents,        /**< number of components of symmetry group */
133  	   int*                  orbits,             /**< array of non-trivial orbits */
134  	   int*                  orbitbegins,        /**< array containing begin positions of new orbits in orbits array */
135  	   int*                  norbits,            /**< pointer to number of orbits currently stored in orbits */
136  	   int*                  varorbitmap         /**< array for storing the orbits for each variable */
137  	   );
138  	
139  	/** Compute orbit of a given variable and store it in @p orbit. The first entry of the orbit will
140  	 *  be the given variable index and the rest is filled with the remaining variables excluding
141  	 *  the ones specified in @p ignoredvars.
142  	 *
143  	 *  @pre orbit is an initialized array of size propdata->npermvars
144  	 *  @pre at least one of @p perms and @p permstrans should not be NULL
145  	 */
146  	SCIP_EXPORT
147  	SCIP_RETCODE SCIPcomputeOrbitVar(
148  	   SCIP*                 scip,               /**< SCIP instance */
149  	   int                   npermvars,          /**< number of variables in permvars */
150  	   int**                 perms,              /**< the generators of the permutation group (or NULL) */
151  	   int**                 permstrans,         /**< the transposed matrix of generators (or NULL) */
152  	   int*                  components,         /**< the components of the permutation group */
153  	   int*                  componentbegins,    /**< array containing the starting index of each component */
154  	   SCIP_Shortbool*       ignoredvars,        /**< array indicating which variables should be ignored */
155  	   SCIP_Shortbool*       varfound,           /**< bitmap to mark which variables have been added (or NULL) */
156  	   int                   varidx,             /**< index of variable for which the orbit is requested */
157  	   int                   component,          /**< component that var is in */
158  	   int *                 orbit,              /**< array in which the orbit should be stored */
159  	   int*                  orbitsize           /**< buffer to store the size of the orbit */
160  	   );
161  	
162  	/** Checks whether a permutation is a composition of 2-cycles and in this case determine the number of overall
163  	 *  2-cycles and binary 2-cycles. It is a composition of 2-cycles iff @p ntwocyclesperm > 0 upon termination.
164  	 */
165  	SCIP_EXPORT
166  	SCIP_RETCODE SCIPisInvolutionPerm(
167  	   int*                  perm,               /**< permutation */
168  	   SCIP_VAR**            vars,               /**< array of variables perm is acting on */
169  	   int                   nvars,              /**< number of variables */
170  	   int*                  ntwocyclesperm,     /**< pointer to store number of 2-cycles */
171  	   int*                  nbincyclesperm,     /**< pointer to store number of binary cycles */
172  	   SCIP_Bool             earlytermination    /**< whether we terminate early if not all affected variables are binary */
173  	   );
174  	
175  	/** determine number of variables affected by symmetry group */
176  	SCIP_EXPORT
177  	SCIP_RETCODE SCIPdetermineNVarsAffectedSym(
178  	   SCIP*                 scip,               /**< SCIP instance */
179  	   int**                 perms,              /**< permutations */
180  	   int                   nperms,             /**< number of permutations in perms */
181  	   SCIP_VAR**            permvars,           /**< variables corresponding to permutations */
182  	   int                   npermvars,          /**< number of permvars in perms */
183  	   int*                  nvarsaffected       /**< pointer to store number of all affected variables */
184  	   );
185  	
186  	/** compute components of symmetry group */
187  	SCIP_EXPORT
188  	SCIP_RETCODE SCIPcomputeComponentsSym(
189  	   SCIP*                 scip,               /**< SCIP instance */
190  	   SYM_SYMTYPE           symtype,            /**< type of symmetries in perms */
191  	   int**                 perms,              /**< permutation generators as
192  	                                              *   (either nperms x npermvars or npermvars x nperms) matrix */
193  	   int                   nperms,             /**< number of permutations */
194  	   SCIP_VAR**            permvars,           /**< variables on which permutations act */
195  	   int                   npermvars,          /**< number of variables for permutations */
196  	   SCIP_Bool             transposed,         /**< transposed permutation generators as (npermvars x nperms) matrix */
197  	   int**                 components,         /**< array containing the indices of permutations sorted by components */
198  	   int**                 componentbegins,    /**< array containing in i-th position the first position of
199  	                                              *   component i in components array */
200  	   int**                 vartocomponent,     /**< array containing for each permvar the index of the component it is
201  	                                              *   contained in (-1 if not affected) */
202  	   unsigned**            componentblocked,   /**< array to store which symmetry methods have been used on a component
203  	                                              *   using the same bitset information as for misc/usesymmetry */
204  	   int*                  ncomponents         /**< pointer to store number of components of symmetry group */
205  	   );
206  	
207  	/** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
208  	 *  checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
209  	 *  we add one column to the suborbitope of the first nfilledcols columns.
210  	 *
211  	 *  @pre Every non-trivial cycle of perm is a 2-cycle.
212  	 *  @pre perm has nrows many 2-cycles
213  	 */
214  	SCIP_EXPORT
215  	SCIP_RETCODE SCIPextendSubOrbitope(
216  	   int**                 suborbitope,        /**< matrix containing suborbitope entries */
217  	   int                   nrows,              /**< number of rows of suborbitope */
218  	   int                   nfilledcols,        /**< number of columns of suborbitope which are filled with entries */
219  	   int                   coltoextend,        /**< index of column that should be extended by perm */
220  	   int*                  perm,               /**< permutation */
221  	   SCIP_Bool             leftextension,      /**< whether we extend the suborbitope to the left */
222  	   int**                 nusedelems,         /**< pointer to array storing how often an element was used in the orbitope */
223  	   SCIP_VAR**            permvars,           /**< permutation vars array */
224  	   SCIP_Shortbool*       rowisbinary,        /**< array encoding whether variables in an orbitope row are binary */
225  	   SCIP_Bool*            success,            /**< pointer to store whether extension was successful */
226  	   SCIP_Bool*            infeasible          /**< pointer to store if the number of intersecting cycles is too small */
227  	   );
228  	
229  	/** generate variable matrix for orbitope constraint handler */
230  	SCIP_EXPORT
231  	SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(
232  	   SCIP*                 scip,               /**< SCIP instance */
233  	   SCIP_VAR****          vars,               /**< pointer to matrix of orbitope variables */
234  	   int                   nrows,              /**< number of rows of orbitope */
235  	   int                   ncols,              /**< number of columns of orbitope */
236  	   SCIP_VAR**            permvars,           /**< superset of variables that are contained in orbitope */
237  	   int                   npermvars,          /**< number of variables in permvars array */
238  	   int**                 orbitopevaridx,     /**< permuted index table of variables in permvars that are contained in orbitope */
239  	   int*                  columnorder,        /**< permutation to reorder column of orbitopevaridx */
240  	   int*                  nusedelems,         /**< array storing how often an element was used in the orbitope */
241  	   SCIP_Shortbool*       rowisbinary,        /**< array encoding whether a row contains only binary variables */
242  	   SCIP_Bool*            infeasible,         /**< pointer to store whether the potential orbitope is not an orbitope */
243  	   SCIP_Bool             storelexorder,      /**< whether the lexicographic order induced by the orbitope shall be stored */
244  	   int**                 lexorder,           /**< pointer to array storing the lexorder (or NULL) */
245  	   int*                  nvarsorder,         /**< pointer to store number of variables in lexorder (or NULL) */
246  	   int*                  maxnvarsorder       /**< pointer to store maximum number of variables in lexorder (or NULL) */
247  	   );
248  	
249  	/** checks whether an orbitope is a packing or partitioning orbitope */
250  	SCIP_EXPORT
251  	SCIP_RETCODE SCIPisPackingPartitioningOrbitope(
252  	   SCIP*                 scip,               /**< SCIP data structure */
253  	   SCIP_VAR***           vars,               /**< variable matrix of orbitope constraint */
254  	   int                   nrows,              /**< pointer to number of rows of variable matrix */
255  	   int                   ncols,              /**< number of columns of variable matrix */
256  	   SCIP_Bool**           pprows,             /**< pointer to store which rows are are contained in
257  	                                              *   packing/partitioning constraints or NULL if not needed */
258  	   int*                  npprows,            /**< pointer to store how many rows are contained
259  	                                              *   in packing/partitioning constraints or NULL if not needed */
260  	   SCIP_ORBITOPETYPE*    type                /**< pointer to store type of orbitope constraint after strengthening */
261  	   );
262  	
263  	/** detects whether permutations define single or double lex matrices
264  	 *
265  	 *  A single lex matrix is a matrix whose columns can be partitioned into blocks such that the
266  	 *  columns within each block can be permuted arbitrarily. A double lex matrix is a single lex
267  	 *  matrix such that also blocks of rows have the aforementioned property.
268  	 */
269  	SCIP_EXPORT
270  	SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(
271  	   SCIP*                 scip,               /**< SCIP pointer */
272  	   SCIP_Bool             detectsinglelex,    /**< whether single lex matrices shall be detected */
273  	   int**                 perms,              /**< array of permutations */
274  	   int                   nperms,             /**< number of permutations in perms */
275  	   int                   permlen,            /**< number of variables in a permutation */
276  	   SCIP_Bool*            success,            /**< pointer to store whether structure could be detected */
277  	   SCIP_Bool*            isorbitope,         /**< pointer to store whether detected matrix is orbitopal */
278  	   int***                lexmatrix,          /**< pointer to store single or double lex matrix */
279  	   int*                  nrows,              /**< pointer to store number of rows of lexmatrix */
280  	   int*                  ncols,              /**< pointer to store number of columns of lexmatrix */
281  	   int**                 lexrowsbegin,       /**< pointer to store array indicating begin of new row-lexmatrix */
282  	   int**                 lexcolsbegin,       /**< pointer to store array indicating begin of new col-lexmatrix */
283  	   int*                  nrowmatrices,       /**< pointer to store number of single lex row matrices in rows */
284  	   int*                  ncolmatrices        /**< pointer to store number of single lex column matrices in rows */
285  	   );
286  	
287  	/** tries to handle variable matrices with lex ordered rows and columns */
288  	SCIP_EXPORT
289  	SCIP_RETCODE tryHandleDoubleLexMatrices(
290  	   SCIP*                 scip,               /**< SCIP pointer */
291  	   SCIP_VAR**            vars,               /**< variables on which permutations act */
292  	   int**                 perms,              /**< array of permutations */
293  	   int                   nperms,             /**< number of permutations in perms */
294  	   int                   permlen,            /**< number of original (non-negated) variables in a permutation */
295  	   SCIP_Bool             issignedperm,       /**< whether permutations are encoded as signed */
296  	   SCIP_Bool*            success,            /**< pointer to store whether symmetries are handled */
297  	   int                   cidx,               /**< identifier of component to be handled by double lex matrices */
298  	   SCIP_CONS***          genorbconss,        /**< pointer to store generated orbitope constraints */
299  	   int*                  ngenorbconss,       /**< pointer to store number of generated orbitope constraints */
300  	   int*                  genorbconsssize     /**< pointer to store size genorbconss */
301  	   );
302  	
303  	/** helper function to test if val1 = val2 while permitting infinity-values */
304  	SCIP_Bool SCIPEQ(
305  	   SCIP*                 scip,               /**< SCIP data structure */
306  	   SCIP_Real             val1,               /**< left-hand side value */
307  	   SCIP_Real             val2                /**< right-hand side value */
308  	   );
309  	
310  	
311  	/** helper function to test if val1 <= val2 while permitting infinity-values */
312  	SCIP_Bool SCIPLE(
313  	   SCIP*                 scip,               /**< SCIP data structure */
314  	   SCIP_Real             val1,               /**< left-hand side value */
315  	   SCIP_Real             val2                /**< right-hand side value */
316  	   );
317  	
318  	
319  	/** helper function to test if val1 >= val2 while permitting infinity-values */
320  	SCIP_Bool SCIPGE(
321  	   SCIP*                 scip,               /**< SCIP data structure */
322  	   SCIP_Real             val1,               /**< left-hand side value */
323  	   SCIP_Real             val2                /**< right-hand side value */
324  	   );
325  	
326  	
327  	/** helper function to test if val1 < val2 while permitting infinity-values */
328  	SCIP_Bool SCIPLT(
329  	   SCIP*                 scip,               /**< SCIP data structure */
330  	   SCIP_Real             val1,               /**< left-hand side value */
331  	   SCIP_Real             val2                /**< right-hand side value */
332  	   );
333  	
334  	
335  	/** helper function to test if val1 > val2 while permitting infinity-values */
336  	SCIP_Bool SCIPGT(
337  	   SCIP*                 scip,               /**< SCIP data structure */
338  	   SCIP_Real             val1,               /**< left-hand side value */
339  	   SCIP_Real             val2                /**< right-hand side value */
340  	   );
341  	
342  	/** @} */
343  	
344  	#ifdef __cplusplus
345  	}
346  	#endif
347  	
348  	#endif
349