Project topics and materials
Get Complete Project Material File(s) Now! »
Group Theory
From now on, we consider that groups act on vectors in Rn by permuting its components and that permutations act on sets of vectors by acting on each vector individually. Standard group nomenclature is employed: Sn and Cn are the symmetric and cyclic group of order n, respectively. Sym() is the symmetric group on the ground set (e.g. Sn = Sym([n])). Let H and G be groups. If H is a subgroup of G, we write H 6 G; if H is a normal subgroup of G, then we write HG. Finally, if H is isomorphic to G, we write H = G. hi denotes the group generated by the set of generators. For a group G 6 Sn and a set X of row vectors, XG = fxg j x 2 X^g 2 Gg. A similar definition is valid for a set Y of column vectors: GY = fgy j y 2 Y ^ g 2 Gg.
Symmetry detection
We emphasize that Eq. (1) subsumes the description of two mathematical entities: the MP itself, denoted by P, and its formal description P in the language L, which we obtain when replacing x, f, g by their representing symbols x, f, g. It is well-known that P can be parsed into a Directed Acyclic Graph data structure T (an elementary graph contraction of the well-known parsing tree) using a fairly simple contextfree grammar [10, 18]. The leaf nodes of T are labelled by constants or decision variable symbols, whereas the other nodes of T are labelled by operator symbols. The incidence structure of T encodes the parent-child relationships between operators, variables and constants. In practice, we can write P using a modelling language such as AMPL [30] and use an unpublished but effective AMPL API to derive T [32]. Since T is a labelled graph, we know how to compute the group G of its label-invariant isomorphisms (which must also respect a few other properties, such as noncommutativity of certain operators) [64, 65]. In addition, we can use the software codes NAUTY or TRACES [65] to obtain G and the set of the orbits of its action on the nodes V(T) of the DAG.
Algorithm description
The Algorithm 1 generates a set C containing SBCs derived from the largest independent set of orbits of P. It takes as inputs a nontrivial formulation group (parameter GP) and a reformulation strategy (parameter ). The following list of functions simplify the pseudocode of Alg. 1:
• computeOrbits(GP) returns the orbits of the group GP;
• computePointStab(!) returns the pointwise stabilizer of orbit !;
• pos(!) returns the position of orbit ! in the list GP ;
• isTransitive(G,!) returns true if the action of the group G is transitive on the orbit ! and false otherwise;
• buildGraph(V, E, ) returns a graph with vertices V, edges E and weights appropriate to the strategy ;
• solveMWCP(GI) returns a solution of the MWCP for the graph GI.
If GP has more than one orbit (j GP j > 1), the algorithm first iteratively looks for all the pairs of independent orbits in order to build the set E. Provided that the Condition (3) in Theorem 14 is not sufficient to ascertain whether two orbits !, 2 GP satisfy ! , ultimately we must check if the action of the stabilizers G! and G is transitive on and !, respectively. Thus the algorithm does not compare the sets ! and but rather directly checks whether the actions are transitive.
Table of contents :
i overview
1 introduction
1.1 Mathematical Programming
1.2 Symmetries in Mathematical Programming
1.2.1 Reformulations
1.3 Distances in Mathematical Programming
1.3.1 Applications
1.4 Semidefinite Programming
1.4.1 Diagonally Dominant Programming
1.5 Thesis structure
ii contributions
2 orbital independence
2.1 Introduction
2.2 Notation and previous work
2.2.1 Group Theory
2.2.2 Symmetry detection
2.2.3 Formulation and solution groups
2.2.4 Symmetry exploitation
2.2.5 Orbits
2.2.6 Symmetry-Breaking Constraints
2.2.7 Stabilizers
2.3 Orbital independence notions
2.3.1 Incompatible SBCs
2.3.2 Some existing OI conditions
2.3.3 New conditions for OI
2.3.4 SBCs from independent sets
2.4 Orbital independence algorithm
2.4.1 Independence graph
2.4.2 OI reformulations
2.4.3 Algorithm description
2.5 Computational experiments
2.5.1 Datasets
2.5.2 Environment
2.5.3 Reformulation algorithm
2.5.4 Results
2.6 Conclusions
3 binary quadratic programming
3.1 Introduction
3.2 Binary Quadratic Programs
3.3 SDP for BQP
3.4 DDP for BQP
3.5 BQP Generation
3.6 Computational Experiments
3.6.1 Dataset
3.6.2 Environment
3.6.3 Results: SDP/DDP
3.6.4 Results: OI
3.7 Conclusions
4 euclidean distance geometry problem
4.1 Introduction
4.2 Notation and definitions
4.3 EDGP formulations
4.3.1 Feasibility formulations
4.3.2 MP formulations
4.4 Efforts to solve the EDGP
4.4.1 Starting points via DDP
4.4.2 Modelling the rank
4.4.3 Bounds on the variables x, X and
4.4.4 Additional constraints
4.4.5 Modelling simplifications
4.4.6 Tackling large instances
4.5 Computational experiments
4.5.1 Dataset
4.5.2 Environment
4.5.3 Results
4.6 Conclusions
5 conclusions
bibliography
