Abstract: Abstract This paper proposes a representation of the family of Minkowski distances using fuzzy sets. The proposed method helps to represent human-like perceptions about distances, which can help decision making in presence of non-probabilistic uncertainties such as imprecision and ambiguity. This way we propose to define a fuzzy set regarding the concept of closeness of two elements/sets measured by a Minkowski metric. Two application examples are presented, solved, and compared to some classical approaches. Finally some concluding remarks are provided and some interpretation issues are explained. PubDate: 2020-03-01

Abstract: Abstract A branch-and-prune (BP) algorithm is presented for the discretizable distance geometry problem in \(\mathbb {R}^K\) with inexact distances. The algorithm consists in a sequential buildup procedure where possible positions for each new point to be localized are computed by using distances to at least K previously placed reference points and solving a system of quadratic equations. Such a system is solved in a least-squares sense, by finding the best positive semidefinite rank K approximation for an induced Gram matrix. When only K references are available, a second candidate position is obtained by reflecting the least-squares solution through the hyperplane defined by the reference points. This leads to a search tree which is explored by BP, where infeasible branches are pruned on the basis of Schoenberg’s theorem. In order to study the influence of the noise level, numerical results on some instances with distances perturbed by a small additive noise are presented. PubDate: 2020-03-01

Abstract: Abstract A definition of chirality based on group theory is presented. It is shown to be equivalent to the usual one in the case of Euclidean spaces, and it permits to define chirality in metric spaces which are not Euclidean. PubDate: 2020-03-01

Abstract: Abstract This paper presents a new approach to the generalized distance geometry problem, based on a model that uses constraint interval arithmetic. In addition to theoretical results, we give some computational experiments that illustrate the better performance of the proposed approach, compared to others from the literature. PubDate: 2020-03-01

Abstract: Abstract A lattice (d,k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers ranging between 0 and k. We consider the largest possible distance \(\delta \)(d,k) between two vertices in the edge-graph of a lattice (d,k)-polytope. We show that \(\delta \)(5,3) and \(\delta \)(3,6) are equal to 10. This substantiates the conjecture whereby \(\delta \)(d,k) is achieved by a Minkowski sum of lattice vectors. PubDate: 2020-03-01

Abstract: Abstract We demonstrate that an earlier semidefinite-programming relaxation for the kissing-number problem cannot provide good upper bounds. Furthermore, we show the existence of an optimal solution for this relaxation that cannot be used as a basis for establishing a good lower bound. PubDate: 2020-03-01

Abstract: Abstract Discretizable distance geometry problems (DDGPs) constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. Finding such vertex orders is an essential step to identify and solve DDGPs. Here we look for discretization orders that minimize an indicator of the size of the search tree. This paper sets the ground for exact solution of the optimal discretization order problem by proposing two integer programming formulations and a constraint generation procedure for an extended formulation. We discuss some theoretical aspects of the problem and numerical experiments on protein-like instances of DDGP are also reported. PubDate: 2020-03-01

Abstract: Abstract Distance Geometry Problem (DGP) and Nonlinear Mapping (NLM) are two well established questions: DGP is about finding a Euclidean realization of an incomplete set of distances in a Euclidean space, whereas Nonlinear Mapping is a weighted Least Square Scaling (LSS) method. We show how all these methods (LSS, NLM, DGP) can be assembled in a common framework, being each identified as an instance of an optimization problem with a choice of a weight matrix. We study the continuity between the solutions (which are point clouds) when the weight matrix varies, and the compactness of the set of solutions (after centering). We finally study a numerical example, showing that solving the optimization problem is far from being simple and that the numerical solution for a given procedure may be trapped in a local minimum. PubDate: 2020-03-01

Abstract: Abstract We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs. PubDate: 2020-03-01

Abstract: Abstract A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been investigated mostly in computational complexity terms. Indeed, we could find no previous explicit mathematical formulation or exact algorithm for the problem. Furthermore, testing our algorithms also represented a challenge. Standard randomly generated graphs tend to contain a single perfect edge dominating solution, i.e., the trivial one, containing all edges in the graph. Accordingly, some quite elaborated procedures had to be devised to have access to more challenging instances. A total of 736 graphs were thus generated, all of them containing feasible solutions other than the trivial ones. Every graph giving rise to a weighted and a non weighted instance, all instances solved to proven optimality by two of the algorithms tested. PubDate: 2020-03-01

Abstract: Abstract The Distance Geometry Problem (DGP) is the problem of determining whether a realization for a simple weighted undirected graph \(G=(V,E,d)\) in a given Euclidean space exists so that the distances between pairs of realized vertices u, \(v \in V\) correspond to the weights \(d_{uv}\), for each \(\{u,v\} \in E\). We focus on a special class of DGP instances, referred to as the Discretizable DGP (DDGP), and we introduce the K-discretization and the K-incident graphs for the DDGP class. The K-discretization graph is independent on the vertex order that can be assigned to V, and can be useful for discovering whether one of such orders actually exists so that the DDGP assumptions are satisfied. The use of a given vertex order allows the definition of another important graph, the K-incident graph, which is potentially useful for performing pre-processing analysis on the solution set of DDGP instances. PubDate: 2020-03-01

Abstract: Abstract Let \(\widehat{m}_{ij}\) be the hitting (mean first passage) time from state i to state j in an n-state ergodic homogeneous Markov chain with transition matrix T. Let \(\Gamma \) be the weighted digraph whose vertex set coincides with the set of states of the Markov chain and arc weights are equal to the corresponding transition probabilities. It holds that $$\begin{aligned} \widehat{m}_{ij}= q_j^{-1}\cdot {\left\{ \begin{array}{ll} f_{ij},&{}\text {if }\;\; i\ne j,\\ q, &{}\text {if }\;\; i=j, \end{array}\right. } \end{aligned}$$where \(f_{ij}\) is the total weight of 2-tree spanning converging forests in \(\Gamma \) that have one tree containing i and the other tree converging to j, \(q_j\) is the total weight of spanning trees converging to j in \(\Gamma ,\) and \(q=\sum _{j=1}^nq_j\) is the total weight of all spanning trees in \(\Gamma .\) Moreover, \(f_{ij}\) and \(q_j\) can be calculated by an algebraic recurrent procedure. A forest expression for Kemeny’s constant is an immediate consequence of this result. Further, we discuss the properties of the hitting time quasi-metric m on the set of vertices of \(\Gamma \): \(m(i,j)=\widehat{m}_{ij}\), \(i\ne j\), and \(m(i,i)=0\). We also consider a number of other metric structures on the set of graph vertices related to the hitting time quasi-metric m—along with various connections between them. The notions and relationships under study are illustrated by two examples. PubDate: 2020-03-01

Abstract: Abstract The dynamical distance geometry problem (dynDGP) is the problem of finding a realization in a Euclidean space of a weighted undirected graph G representing an animation by relative distances, so that the distances between realized vertices are as close as possible to the edge weights. In the dynDGP, the vertex set of the graph G is the set product of V, representing certain objects, and T, representing time as a sequence of discrete steps. We suppose moreover that distance information is given together with the priority of every distance value. The dynDGP is a special class of the DGP where the dynamics of the problem comes to play an important role. In this work, we propose an application-based characterization of dynDGP instances, where the main criteria are the presence or absence of a skeletal structure, and the rigidity of such a skeletal structure. Examples of considered applications include: multi-robot coordination, crowd simulations, and human motion retargeting. PubDate: 2020-03-01

Abstract: Abstract The metric polytope \({{\mathrm{METP}}}(K_n)\) of the complete graph on n nodes is defined by the triangle inequalities \(x(i,j)\le x(i,k) + x(k,j)\) and \(x(i,j) + x(j,k) + x(k,i)\le 2\) for all triples i, j, k of \(\{1,\dots ,n\}\). The cut polytope \({{\mathrm{CUTP}}}(K_n)\) is the convex hull of the \(\{0,1\}\) vectors of \({{\mathrm{METP}}}(K_n)\). For a graph G on n vertices the metric polytope \({{\mathrm{METP}}}(G)\) and cut polytope \({{\mathrm{CUTP}}}(G)\) are the projections of \({{\mathrm{METP}}}(K_n)\) and \({{\mathrm{CUTP}}}(K_n)\) on the edge set of G. The facets of the cut polytopes are of special importance in optimization and are studied here in some detail for many simple graphs. Then we define variants \({{\mathrm{QMETP}}}(G)\) for quasi-metrics, i.e. not necessarily symmetric distances and we give an explicit description by inequalities. Finally we generalize distances to m-dimensional area between \(m+1\) points and this defines an hemimetric. In that setting the generalization of the notion of graph is the notion of m-dimensional simplicial complex \({\mathcal {K}}\) for which we define a cone of hemimetric \({{\mathrm{HMET}}}({\mathcal {K}})\). PubDate: 2020-03-01

Abstract: Abstract We consider the problems of determining the metric dimension and the minimum cardinality of doubly resolving sets in n-cubes. Most heuristics developed for these two NP-hard problems use a function that counts the number of pairs of vertices that are not (doubly) resolved by a given subset of vertices, which requires an exponential number of distance evaluations, with respect to n. We show that it is possible to determine whether a set of vertices (doubly) resolves the n-cube by solving an integer program with O(n) variables and O(n) constraints. We then demonstrate that small resolving and doubly resolving sets can easily be determined by solving a series of such integer programs within a swapping algorithm. Results are given for hypercubes having up to a quarter of a billion vertices, and new upper bounds are reported. PubDate: 2020-03-01

Abstract: Abstract We supply proofs for a few key results concerning smoothing square roots and model strengthening for a mixed-integer nonlinear-optimization formulation of the the Euclidean Steiner tree problem. PubDate: 2020-03-01

Abstract: Abstract Neighborhood search techniques are often employed to deal with combinatorial optimization problems. Previous works got good results in applying a novel neighborhood search methodology called Multi Improvement (MI). First and best improvement are classical approaches for neighborhood exploration, while the MI has emerged due to the advance of new parallel computing technologies. The MI formalizes the concept of heuristic and exact exploration of independent moves for a given neighborhood structure, however, the advantages of an application of MI face the difficulty to select a great set of independent moves (which can be performed simultaneously). Most of the existing implementations of MI select these moves through heuristic methods, while others have succeeded in implementing exact dynamic programming approaches. In this paper, we propose a formal description for the Maximum Multi Improvement Problem (MMIP), as a theoretical background for the MI. Moreover, we develop three dynamic programming algorithms for solving the MMIP, given a solution tour for a Traveling Salesman Problem and neighborhood operators 2-Opt, 3-Opt, and OrOpt-k. The analysis suggests the rise of a new open topic focused on developing novel efficient neighborhood searches. PubDate: 2020-02-22

Abstract: Abstract This paper proposes a hybrid method for solving systems of nonsmooth equations with box constraints, which combines the idea of Levenberg–Marquard-like method with the nonmonotone strategy and the smoothing approximation technique. Under mild assumptions, the proposed method is proven to possess global and local superlinear convergence. Preliminary numerical results are reported to show the efficiency of this proposed method in practical computation. PubDate: 2020-02-21