euclidean distance geometry problem 

Get Complete Project Material File(s) Now! »

ORBITAL INDEPENDENCE

It is well-known that symmetric Mathematical Programs are harder to solve to global optimality using Branch-and-Bound type algorithms, since the solution symmetry is reflected in the size of the Branch-and-Bound tree. It is also well-known that some of the solution sym-metries are usually evident in the formulation, making it possible to attempt to deal with symmetries as a preprocessing step. One of the easiest approaches is to break symmetries by adjoining some Symmetry-Breaking Constraints to the formulation, thereby remov-ing some symmetric global optima, then solve the reformulation with a generic solver. Sets of such constraints can be generated from each orbit of the action of the symmetries on the variable index set. It is unclear, however, whether and how it is possible to choose two or more separate orbits to generate Symmetry-Breaking Constraints which are compatible with each other (in the sense that they do not make all global optima infeasible). In this chapter we discuss and test a new concept of orbit independence which clarifies this issue.

introduction

An important issue that arises when breaking symmetries of MPs in view of solving them using BB type algorithms is addressed in the following sections. Symmetry-breaking devices are usually derived from orbits of the action of the formulation group on the decision vari-ables. However, one cannot simply use such devices for all the orbits simultaneously: some orbits depend on each other, in a very precise mathematical sense, and hence it may be impossible to use more than one orbit for symmetry-breaking purposes. Next, we discuss a notion of orbit independence which permits to break symmetries from dis-tinct orbits concurrently. Briefly, a short theory describing sufficient conditions is developed and used to devise an algorithm that poten-tially identifies the largest independent set of orbits of any Mathe-matical Program. We then provide extensive computational results to showcase the correctness and usefulness of the Orbital Indepen-dence (OI) ideas. The tests are performed against symmetric instances taken from the public libraries MIPLIB2010 and MINLPLib2.
The rest of this chapter is organized as follows: in Section 2.2 we introduce notation, recall concepts of Group Theory and review pre-vious work related to symmetries in MP; in Section 2.3 we present all the theoretical developments concerning the OI framework; in Sec-tion 2.4 we describe in details the SBCs generator algorithm devised based on the theory recently constructed; and finally, computational experiments are provided and analysed in Section 2.5.

notation and previous work

Group Theory

From now on, we consider that groups act on vectors in Rn by per-muting 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 H G.
Finally, if H is isomorphic to G, we write H G. h i 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 mathemat-ical 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 con-traction of the well-known parsing tree) using a fairly simple context-free grammar [10, 18]. The leaf nodes of T are labelled by constants or decision variable symbols, whereas the other nodes of T are la-belled 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.

 Formulation and solution groups

Liberti has shown in [49] that:
(a) the action of G can be projected to the leaf nodes of V(T), which represent decision variables;
(b) this projection induces a group homomorphism mapping G to a certain group image GP;
(c) GP is a group of permutations of the indices of the variable symbols x1, : : : , xn;
(d) GP is precisely the group of variable permutations of P which keeps f(x) and fgi(x) j i 6 mg invariant.
In other words, [49] provides (among other things) a practical method-ology for computing the formulation group GP of a MP given as in Eq. (1). Since it is not hard to show that GP is a subgroup of the so-lution group of P, meant as the group of permutations which keeps the set G (P) of global optima of P invariant, this methodology can be used to extract symmetries from P prior to solving it.

Symmetry exploitation

Once the formulation symmetries are known, their most efficient ex-ploitation appears to be their usage within the BB algorithm itself [60, 61, 71, 72]. Such approaches are, unfortunately, difficult to implement, as each solver code must be addressed separately. Their simplest ex-ploitation is the SSB [62, §8.2] which, simply put, consists in adjoin-ing some Symmetry-Breaking Constraints to the original formulation Eq. (1) in the hope of making all but one of the symmetric global op-tima infeasible. Following the usual trade-off between efficiency and generality, approaches which offer provable guarantees of removing symmetric optima are limited to special structures [40], whereas ap-proaches which hold for any MP in the large class Eq. (1) are mostly common-sense constraints designed to work in general [50]. The con-sensus seems to be that sets of SBCs are derived from each orbit of the action of GP on X.
Remark 7. This is not the only possibility provided that SBCs can also be derived from cyclic subgroups of GP or single permutations.
Though breaking symmetries may work well with BB type algo-rithms, local-search based heuristics usually find optima faster if there are many of them. So it may not always be worth eliminating them [50]. The first attempt to propose a paradigm shift as concerns ex-ploiting symmetries in MPs is Orbital Shrinking (OS) [29]. This recent philosophy sustains that symmetry shall be exploited as much as pos-sible and broken as a last resort. Developed at first to Mixed-Integer Linear Programs (MILPs), the idea behind the technique is to derive relaxations which are at the same time smaller (fewer variables) and symmetry free.
where is the set of orbits of a particular subgroup of the formula-tion group of P. Simply put, the x variables indexed by the orbit ! are replaced by a single z! variable.
The OS paradimg has already unveiled proofs of its promising future [79, 80]. A survey on the subject will become public soon where one will be able to find an extension of the OS method to con-vex Mixed-Integer Nonlinear Programs (MINLPs) and to nonconvex MINLPs having a special structure.
Finally, we would like to refer the reader to a very recent survey paper [73], which contains an extensive and detailed assessment of the state of the art in symmetry handling methods in Mathematical Programming.

READ  A brief history of RF and microwave power measurement

Orbits

We recall that an orbit is an equivalence class of the quotient set X= , where i j if there is g 2 GP such that g(i) = j. This way, GP parti-tions X into a set GP of orbits !1, : : : , !p, each of which can be used to generate SBCs. The projection homomorphism defined above for G and the leaf nodes of the parsing tree can be restricted to act on GP and generalized to project its action to any subset Y X as follows: for each 2 GP let ( ) be the product of the cycles of having all components in Y. We denote by Y this generalized action projection homomorphism. The image of Y, when Y is some orbit ! 2 GP , is a group GP[!] called the transitive constituent of !. A group action is transitive on a set S if s t for each s, t 2 S.

Symmetry-Breaking Constraints

We borrow the square bracket notation to localize vectors: if x 2 G (P) is a global optimum of P, then x [!] is a projection of x on the coordinates indexed by !. If GP[!] is the full symmetric group Sym(!) on the orbit, it means that G (P) contains vectors which, when projected onto !, yield every possible order of x [!]. This implies that we can arbitrarily choose one order, e.g.: 8‘ < j!j x!(‘) 6 x!(‘+1), (19)
where !(‘) is the ‘-th element of ! (stored as a list), enforce this order by means of SBCs, and still be sure that at least one global optimum remains feasible. The SBCs in Eq. (19) are called strong SBCs. If GP[!] has any other structure, we observe that, by transitivity of the tran-sitive constituents, at least one permutation in GP[!] will map the component having minimum value in x [!] to the first component.
Remark 8. The choice of minimum value and first components are arbitrary. Alternative SBC sets can occur by choosing maximum and/or any other com-ponent.
This, nonetheless, yields the weak SBCs: 8‘ 2 ! r f!(1)g x!(1) 6 x!(‘). (20)
Strong SBCs select one order out of j!j! many, and hence are able to break all the symmetries in GP[!]. Weak SBCs , on the other hand, are unlikely to be able to achieve that. We let g(x[B]) 6 0 denote SBCs involving only variables xj with j in a given set B.

Stabilizers

Let Y X. We recall that the pointwise stabilizer of Y with respect to GP (or any group G) is defined as the subgroup of elements of GP fixing each element of Y, i.e., GY = fg 2 GP j 8y 2 Y (gy = y)g. The setwise stabilizer of Y with respect to GP is the subgroup of those elements of GP under which Y is invariant, i.e., stab(Y, GP) = fg 2 GP j 8y 2 Y (gy 2 Y)g. By definition, if Y is an orbit of GP, then GY is the kernel of Y and stab(Y, GP) = GP.

orbital independence notions

In this section we introduce our main results regarding OI. First we illustrate how SBCs built from different orbits may cut global optima from a MP; then we recall the conditions of OI originally introduced in [49], and finally we present a new concept of OI based on pointwise stabilizers.

Incompatible SBCs

In general, one may only adjoin to P the SBCs from one orbit. Adjoin-ing SBCs from two or more orbits chosen arbitrarily may result in all global optima being infeasible, as Example 9 shows.

Table of contents :

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
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 

GET THE COMPLETE PROJECT

Related Posts