OR-Tools  8.2
symmetry_util.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_SAT_SYMMETRY_UTIL_H_
15 #define OR_TOOLS_SAT_SYMMETRY_UTIL_H_
16 
18 
19 namespace operations_research {
20 namespace sat {
21 
22 // Given the generator for a permutation group of [0, n-1], tries to identify
23 // a grouping of the variables in an p x q matrix such that any permutations
24 // of the columns of this matrix is in the given group.
25 //
26 // The name comes from: "Packing and Partitioning Orbitopes", Volker Kaibel,
27 // Marc E. Pfetsch, https://arxiv.org/abs/math/0603678 . Here we just detect it,
28 // independently of the constraints on the variables in this matrix. We can also
29 // detect non-Boolean orbitope.
30 //
31 // In order to detect orbitope, this basic algorithm requires that the
32 // generators of the orbitope must only contain one or more 2-cyle (i.e
33 // transpositions). Thus they must be involutions. The list of transpositions in
34 // the SparsePermutation must also be listed in a canonical order.
35 //
36 // TODO(user): Detect more than one orbitope? Note that once detected, the
37 // structure can be exploited efficiently, but for now, a more "generic"
38 // algorithm based on stabilizator should achieve the same preprocessing power,
39 // so I don't know how hard we need to invest in orbitope detection.
40 //
41 // TODO(user): The heuristic is quite limited for now, but this works on
42 // graph20-20-1rand.mps.gz. I suspect the generators provided by the detection
43 // code follow our preconditions.
44 std::vector<std::vector<int>> BasicOrbitopeExtraction(
45  const std::vector<std::unique_ptr<SparsePermutation>>& generators);
46 
47 // Returns a vector of size n such that
48 // - orbits[i] == -1 iff i is never touched by the generators (singleton orbit).
49 // - orbits[i] = orbit_index, where orbits are numbered from 0 to num_orbits - 1
50 //
51 // TODO(user): We could reuse the internal memory if needed.
52 std::vector<int> GetOrbits(
53  int n, const std::vector<std::unique_ptr<SparsePermutation>>& generators);
54 
55 // Returns the orbits under the given orbitope action.
56 // Same results format as in GetOrbits(). Note that here, the orbit index
57 // is simply the row index of an element in the orbitope matrix.
58 std::vector<int> GetOrbitopeOrbits(
59  int n, const std::vector<std::vector<int>>& orbitope);
60 
61 // Given the generators for a permutation group of [0, n-1], update it to
62 // a set of generators of the group stabilizing the given element.
63 //
64 // Note that one can add symmetry breaking constraints by repeatedly doing:
65 // 1/ Call GetOrbits() using the current set of generators.
66 // 2/ Choose an element x0 in a large orbit (x0, .. xi ..) , and add x0 >= xi
67 // for all i.
68 // 3/ Update the set of generators to the one stabilizing x0.
69 //
70 // This is more or less what is described in "Symmetry Breaking Inequalities
71 // from the Schreier-Sims Table", Domenico Salvagnin,
72 // https://link.springer.com/chapter/10.1007/978-3-319-93031-2_37
73 //
74 // TODO(user): Implement!
76  int to_stabilize,
77  std::vector<std::unique_ptr<SparsePermutation>>* generators) {}
78 
79 } // namespace sat
80 } // namespace operations_research
81 
82 #endif // OR_TOOLS_SAT_SYMMETRY_UTIL_H_
std::vector< int > GetOrbitopeOrbits(int n, const std::vector< std::vector< int >> &orbitope)
void TransformToGeneratorOfStabilizer(int to_stabilize, std::vector< std::unique_ptr< SparsePermutation >> *generators)
Definition: symmetry_util.h:75
std::vector< std::vector< int > > BasicOrbitopeExtraction(const std::vector< std::unique_ptr< SparsePermutation >> &generators)
std::vector< int > GetOrbits(int n, const std::vector< std::unique_ptr< SparsePermutation >> &generators)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...