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
19namespace operations_research {
20namespace 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.
44std::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.
52std::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.
58std::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< int > GetOrbits(int n, const std::vector< std::unique_ptr< SparsePermutation > > &generators)
std::vector< std::vector< int > > BasicOrbitopeExtraction(const std::vector< std::unique_ptr< SparsePermutation > > &generators)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...