Search

We investigate the convex polytope Ω n (123 ‾) of doubly stochastic matrices spanned by the n × n permutation matrices that avoid an increasing pattern of length 3, the 123 ‾ -permutation matrices. We determine some of its facets and other faces, including faces of small dimension, and their connection to facets and faces of the polytope Ω n of all n × n doubly stochastic matrices. The paper concludes with some relations concerning the frequencies of the positions of the 1's in n × n 123 ‾ -permutation matrices, and the vertex-edge graph of Ω n (123 ‾). [ABSTRACT FROM AUTHOR]

Let N be a weakly unitarily invariant norm (i.e. invariant for the coadjoint action of the unitary group) in the space of skew-Hermitian matrices u n (C). In this paper we study the geometry of the unit sphere of such a norm, and we show how its geometric properties are encoded by the majorization properties of the eigenvalues of the matrices. We give a detailed characterization of norming functionals of elements for a given norm, and we then prove a sharp criterion for the commutator [ X , [ X , V ] ] to be in the hyperplane that supports V in the unit sphere. We show that the adjoint action V ↦ V + [ X , V ] of u n (C) on itself pushes vectors away from the unit sphere. As an application of the previous results, for a strictly convex norm, we prove that the norm is preserved by this last action if and only if X commutes with V. We give a more detailed description in the case of any weakly Ad -invariant norm. [ABSTRACT FROM AUTHOR]

We introduce the following cycle selection problem which is motivated by an application to kidney exchange problems. Given a directed graph G = (V , A) , a cycle selection is a subset of arcs B ⊆ A forming a union of directed cycles. A related optimization problem, the Maximum Weighted Cycle Selection problem can be defined as follows: given a weight w i , j ∈ R for all arcs (i , j) ∈ A , find a cycle selection B which maximizes w (B). We prove that this problem is strongly NP-hard. Next, we focus on cycle selections in complete directed graphs. We provide several ILP formulations of the problem: an arc formulation featuring an exponential number of constraints which can be separated in polynomial time, four extended compact formulations, and an extended non compact formulation. We investigate the relative strength of these formulations. We concentrate on the arc formulation and on the description of the associated cycle selection polytope. We prove that this polytope is full-dimensional, and that all the inequalities used in the arc formulation are facet-defining. Furthermore, we describe three new classes of facet-defining inequalities and a class of valid inequalities. We also consider the consequences of including additional constraints on the cardinality of a selection or on the length of the associated cycles. [ABSTRACT FROM AUTHOR]

In this paper we study some geometrical questions about the polytope of bi-capacities. For this, we introduce the concept of pointed order polytope, a natural generalization of order polytopes. Basically, a pointed order polytope is a polytope that takes advantage of the order relation of a partially ordered set and such that there is a relevant element in the structure. We study which are the set of vertices of pointed order polytopes and sort out a simple way to determine whether two vertices are adjacent. We also study the general form of its faces. Next, we show that the set of bi-capacities is a special case of pointed order polytope. Then, we apply the results obtained for general pointed order polytopes for bi-capacities, allowing to characterize vertices and adjacency, and obtaining a bound for the diameter of this important polytope arising in Multicriteria Decision Making. [ABSTRACT FROM AUTHOR]

Given an undirected simple graph G = (V , E) and integer values f v , v ∈ V , a node subset D ⊆ V is called an f -tuple dominating set if, for each node v ∈ V , its closed neighborhood intersects D in at least f v nodes. We study the polytope that is defined as the convex hull of the incidence vectors in R V of the f -tuple dominating sets in G. New families of valid inequalities are introduced and a complete formulation is given for the case of stars. A corollary of our results is a proof that the conjecture reported in Argiroffo (2013) on a complete formulation of the 2-tuple dominating set polytope of trees does not hold. Preliminary computational results are also reported. [ABSTRACT FROM AUTHOR]

This paper explores a displacement-based formation control problem in the presence of misaligned orientations among different body coordinate frames. When agents sense and adjust their relative positions, these misalignments suggest the attitudes of the agents in the absence of an agreement, thereby distorting collective behavior. To mitigate this distortion, an angular velocity control protocol is provided and embedded into a positively invariant set, aiming to establish a predefined attitude agreement. Based on this agreement, a formation control protocol is then to achieve the desired formation shape. Unlike the original alignment case, not only the dynamics of the agents among different coordinate frames are considered, but also the connectivity on the underlying topologies is relaxed. It should be pointed out that constructing a common Lyapunov function for these systems is challenging, since typical conditions for its existence and solvability, e.g., the double stochasticity condition or the non-trivial eigenvalue assignment, may not be satisfied. To address these challenges, a geometric analysis framework, derived as several polytopes and associated properties, is extended to handle these systems without the requirement for such conditions. By utilizing these properties, the control objectives of attitude and formation control are achieved, indicating that the desired formation shape is guaranteed through the implementation procedure of the attitude consensus. Finally, an example is conducted to verify the main results. [ABSTRACT FROM AUTHOR]

This paper investigates the passivity analysis problem of a class of fractional-order neural networks with interval parameter uncertainties (FONNs-IPUs). The previous IPU processing methods are mainly divided into three categories, i.e., directly using the maximum upper bound matrix or the minimum lower bound matrix, using the combination of these two matrices, and using the maximum norm bound matrix. These methods have some shortcomings, for example, the coupling of information between different intervals and the effect of the negative sign of connection weight are not considered. In order to better analyze the passivity of FONNs-IPUs, firstly, a novel treatment approach of IPUs called interval matrix polytope is proposed, which considers all possible boundary information matrices and the sign of IPUs. Secondly, based on the interval matrix polytope approach, the passivity criteria of FONNs-IPUs are established in linear matrix inequality forms. Finally, the effectiveness of the theoretical results is illustrated by simulation example. [ABSTRACT FROM AUTHOR]

Speakman and Lee (2017) gave a formula for the volume of the convex hull of the graph of a trilinear monomial, y = x 1 x 2 x 3 , over a box in the nonnegative orthant, in terms of the upper and lower bounds on the variables. This was done in the context of using volume as a measure for comparing alternative convexifications to guide the implementation of spatial branch-and-bound for mixed integer nonlinear optimization problems. Here, we introduce an alternative method for computing this volume, making use of the rich theory of mixed volumes. This new method may lead to a natural approach for considering extensions of the problem. [ABSTRACT FROM AUTHOR]

We study sign-restricted matrices (SRMs), a class of rectangular (0 , ± 1) -matrices generalizing the alternating sign matrices (ASMs). In an SRM each partial column sum, starting from row 1, equals 0 or 1, and each partial row sum, starting from column 1, is nonnegative. We determine the maximum number of nonzeros in SRMs and characterize the possible row and column sum vectors. Moreover, a number of results on interchange operations are shown, both for SRMs and, more generally, for (0 , ± 1) -matrices. The Bruhat order on ASMs can be extended to SRMs with the result a distributive lattice. Also, we study polytopes associated with SRMs and some relates decompositions. [ABSTRACT FROM AUTHOR]

Matrices in R n × n with determinant equal to ∑ i ≤ n μ (i) , where μ represents the Möbius function, have been studied for decades. The motivation to study such matrices is the close connection that they have to the prime number theorem, Dirichlet convolution, and related concepts. We introduce two parameterized families of bordered Hermitian matrices that possess similar properties. Each family is comprised of matrices M s ∈ C (n − 1) × (n − 1) that satisfy det ⁡ M 0 = ∑ i ≤ n | μ (i) | , det ⁡ M 1 = (∑ i ≤ n μ (i)) 2 , and we show det ⁡ M s is a quadratic polynomial in s. We apply the Cauchy interlacing theorem to show that, for each matrix in one of the families, the product of all of the subdominant eigenvalues is bounded above by 6 / π 2 + O (n − 1 / 2). [ABSTRACT FROM AUTHOR]

In recent years, polygonal and polyhedral finite elements have gained much interest from researchers as an alternative approach for discretizing complicated domains. Findings to enhance their performance are still desirable to solve a broad class of mechanics problems. In this study, we propose a new formulation based on arbitrary polytopes, which we name as Polytopal Composite finite Element (PCE). The key idea is to devise a polynomial projection of compatible strain fields through the least-squares approximation. For nearly incompressible problems, we design a pair of projection operators of volumetric and deviatoric strains resulting in stability of pressure solution. The present approach fulfills a patch test and satisfies the inf–sup stability. Through several numerical investigations, we show that the proposed method reaches the theoretical convergence rate and significantly improves the accuracy of polygonal element based solutions. • We propose a polytopal composite finite element approach for solid mechanics problems. • The method relies on a polynomial projection of strain field performed over macro-elements. • The present method passes a linear patch test and verifies the inf–sup condition for nearly incompressible materials. • It works well with arbitrary polygonal/polyhedral meshes. • An applicable capability of the proposed method to industrial problems is confirmed. [ABSTRACT FROM AUTHOR]

Weighted cone-volume functionals are introduced for the convex polytopes in R n. For these functionals, geometric inequalities are proved and the equality conditions are characterized. A variety of corollaries are derived, including extremal properties of the regular polytopes involving the L p surface area. Some applications to crystallography and quantum theory are also presented. [ABSTRACT FROM AUTHOR]

The max-cut problem is a fundamental and much-studied NP -hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently. [ABSTRACT FROM AUTHOR]

In this paper we propose a way to triangulate a pointed order polytope. Pointed order polytopes are a generalization of order polytopes that include some important groups of polytopes appearing when bipolar scales arise in Decision Making or Game Theory, as the set of bi-capacities or the set of normalized bi-games, even for cases with restricted cooperation. Triangulating polytopes is an important and difficult problem that allows an elegant way to generate uniform random points in the polytope. For order polytopes, there exists a nice result that allows a way to triangulate this family of polytopes based on generating linear extensions. In this paper we prove a similar result for pointed order polytopes. The results in this paper allow to derive a procedure to generate random points inside a pointed order polytope that depends only on the structure of the subjacent poset, a problem that usually is simpler to tackle. In particular, this could be applied to generate bi-capacities or bi-capacities belonging to some subfamilies (e.g. k -symmetric, k -interactive,...) in a random way. [ABSTRACT FROM AUTHOR]

We consider Hurwitz stability region in the parameter space of monic polynomials. Firstly, a multilinear map from the positive first octant of the cartesian coordinate system to the stability region is defined. Based on this map a necessary and sufficient condition for stability is obtained. Starting from stable points, polytopes with infinite edge lengths are defined. Stability of the edges of these polytopes is equivalent to the stability of the convex combinations of third and fourth order factor polynomials. If all edges of polytope are stable then by the edge theorem the polytope is robust stable. The obtained result is important for understanding the geometry of stability domain, and can be used for generation of convex subsets of stable polynomials and for stabilization by fixed order controllers and other related problems. [ABSTRACT FROM AUTHOR]

Motivated by the study of polytopes formed as the convex hull of permutation matrices and alternating sign matrices, we define several new families of polytopes as convex hulls of sign matrices, which are certain { 0 , 1 , − 1 } -matrices in bijection with semistandard Young tableaux. We investigate various properties of these polytopes, including their inequality descriptions, vertices, facets, and face lattices, as well as connections to alternating sign matrix polytopes and transportation polytopes. [ABSTRACT FROM AUTHOR]

We study cyclic sieving phenomena (CSP) on combinatorial objects from an abstract point of view by considering a rational polyhedral cone determined by the linear equations that define such phenomena. Each lattice point in the cone corresponds to a non-negative integer matrix which jointly records the statistic and cyclic order distribution associated with the set of objects realizing the CSP. In particular we consider a universal subcone onto which every CSP matrix linearly projects such that the projection realizes a CSP with the same cyclic orbit structure, but via a universal statistic that has even distribution on the orbits. Reiner et.al. showed that every cyclic action gives rise to a unique polynomial (mod q n − 1) complementing the action to a CSP. We give a necessary and sufficient criterion for the converse to hold. This characterization allows one to determine if a combinatorial set with a statistic gives rise (in principle) to a CSP without having a combinatorial realization of the cyclic action. We apply the criterion to conjecture a new CSP involving stretched Schur polynomials and prove our conjecture for certain rectangular tableaux. Finally we study some geometric properties of the CSP cone. We explicitly determine its half-space description and in the prime order case we determine its extreme rays. [ABSTRACT FROM AUTHOR]

Abstract Given a graph G = (V , E) and integer values f v , v ∈ V , a node subset D ⊂ V is a total f -dominating set if every node v ∈ V is adjacent to at least f v nodes of D. Given a weight system c (v) , v ∈ V , the minimum weight total f -dominating set problem is to find a total f -dominating set of minimum total weight. In this article, we propose a polyhedral study of the associated polytope together with a complete and compact description of the polytope for totally unimodular graphs and cycles. We also propose a linear time dynamic programming algorithm for the case of trees. [ABSTRACT FROM AUTHOR]

Abstract This paper first presents an algorithm to compute bounding polytopes of a compact set in arbitrary dimensions. Different from most of the existing work that deals with a finite point set, the compact set handled in this paper can also be an infinite set described by continuous parametric functions. Starting with any bounding polytope of the compact set, the proposed algorithm iteratively finds a sequence of cutting hyperplanes to truncate the polytope and gradually reduce its volume. As a result, a tight bounding polytope of the compact set can be computed and its tightness is controlled by a user-specified tolerance for terminating the iteration. While the algorithm keeps iterating, the polytope can get arbitrarily close to the convex hull of the compact set. Furthermore, the proposed algorithm is extended to computing the maximum distance between compact sets and the diameter of a compact set. Finally, numerical examples show that the proposed algorithms possess linear time complexity with the number of iterations. Highlights • Efficient algorithm is proposed to compute tight bounding polytopes of compact sets. • A sequence of hyperplanes are computed to cut a bounding polytope of a compact set • The algorithm is extended to the maximum distance and the diameter of compact sets • Compact sets can be infinite and described by parametric functions in any dimension • The proposed algorithms have linear time complexity with the number of iterations [ABSTRACT FROM AUTHOR]

Abstract In this paper we consider a variant of the k -separator problem. Given a graph G = (V ∪ T , E) with V ∪ T the set of vertices, where T is a set of k terminals, the multi-terminal vertex separator problem consists in partitioning V ∪ T into k + 1 subsets { S , V 1 , ... , V k } such that there is no edge between two different subsets V i and V j , each V i contains exactly one terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study. [ABSTRACT FROM AUTHOR]

Abstract Recently calculating the number of lattice points which is an open issue in higher dimension space is appeared. Considering a structure in higher dimension that is practical or aesthetic will be the reason for counting lattice points. Our fundamental object is to present a strategy which counts or at least to estimate how many lattice points on a polytope P in four-dimensional that makes the inconvenience of factorizing the product of the form p.q , with p and q substantial primes easy to compute, this would broke RSA cryptosystem. These approaches depend on finding the lattice point's numbers of of 4-dimensional polytope that is approximate to the number of four dimensional balls, using the properties of the Ehrhart polynomial for a 4-polytope and the cross product of two polytopes. Results are obtained for N = pq and the factorizing of it. Two methodologies are utilized one of them is presented now and the other is in work. [ABSTRACT FROM AUTHOR]

Abstract The realization of stable b-matchings as matroid kernels yields the existing linear description of the stable b -matching (MM) problem. We revisit that description to derive the dimension, the facets, and the minimum equation system of the stable b -matching polytope. The derived minimal description includes O (m) constraints, m being the number of pairs, thus being significantly smaller than the existing one and linear with respect to the problem size. The result carries over to the stable admissions (SA) problem, whose existing linear description relies on an exponential number of comb inequalities; i.e., we identify O (m) among these inequalities that define a minimal description of SA. [ABSTRACT FROM AUTHOR]

A maniplex of rank n is a combinatorial object that generalises the notion of a rank n abstract polytope. A maniplex with the highest possible degree of symmetry is called regular. In this paper we prove that there is a rank 4 regular maniplex with automorphism group PSL 2 (q) for infinitely many prime powers q , and that no regular maniplex of rank n > 4 exists that has PSL 2 (q) as its full automorphism group. [ABSTRACT FROM AUTHOR]

Due to the dependence of large sectors of industrial, commercial, and residential consumers on electricity, the necessity of a reliable and economic generation system that has a regulated frequency is a crucial task. Frequency regulation within permissible standard limits is called load frequency control (LFC). The LFC based on PID controller has proven its effectiveness due to its simple structure and clear concept. However, a fixed gains PID controller can be designed to provide an optimal response at a particular operating condition, but it may exhibit unsatisfactory performance with change in the system's working conditions due to system nonlinearities and parameters variation. To cope with this issue, this article proposes a polytope representation of the system and designs a set of optimal PID controllers at the vertices of the polytope model. After that, Takagi-Sugino fuzzy controller is utilized to blend these optimal controllers to provide the necessary control action based on the actual operating condition. The resultant controller ensures optimal operation at the operation of polytope vertices. To ensure the system's stability over the space of parameter variation, the stability condition as a set of linear matrix inequalities (LMIs) is deduced. Because the number of LMI conditions grows dramatically with the number of system vertices, the paper employs a tensor product transformation technique to represent the system with the minimum number of vertices. The local controllers are optimized using the Grey Wolf Optimizer (GWO) considering a customized objective function that considers the system's integral time absolute error (ITAE), the frequency nadir, and the oscillation. To validate the proposed methodology, the system closed loop poles are determined at a large number of operating conditions. Eventually, the system response is evaluated at different operating conditions with varying load and generation capacity. The proposed control provides a supreme response compared to fixed optimal PID and fixed gain robust PID controller based on H ∞ design criteria controllers. [ABSTRACT FROM AUTHOR]

We consider linear dynamical systems with a structure of a multigraph. The vertices are associated to linear spaces and the edges correspond to linear maps between those spaces. We analyse the asymptotic growth of trajectories (associated to paths along the multigraph), the stability and the stabilizability problems. This generalizes the classical linear switching systems and their recent extensions to Markovian systems, to systems generated by regular languages, etc. We show that an arbitrary system can be factorized into several irreducible systems on strongly connected multigraphs. For the latter systems, we prove the existence of invariant (Barabanov) multinorm and derive a method for its construction. The method works for a vast majority of systems and finds the joint spectral radius (Lyapunov exponent). Numerical examples are presented and applications to the study of fractals, attractors, and multistep methods for ODEs are discussed. [ABSTRACT FROM AUTHOR]

Let k , n denote two positive integers and consider the family of the polytopes defined as the convex hull of pairs of the form ( Y , h ) where Y is a 0/1-matrix with k rows, n columns, containing exactly one nonzero coefficient per column, and where h stands for the smallest index of a nonzero row of Y . These polytopes and some variants naturally emerge in formulations of different classical combinatorial optimization problems such as minimum makespan scheduling and minimum span frequency assignment. In this paper, we provide complete formulations for these polytopes and show the associated separation problem can be solved in polynomial time. The complete formulations in the original space of variables generally contain an exponential number of inequalities. Alternative extended compact formulations are also presented. [ABSTRACT FROM AUTHOR]

We construct two families of Dantzig figures, which are d -dimensional polytopes with 2 d facets and an antipodal vertex pair, from convex hulls of initial subsets for the graded lexicographic (grlex) and graded reverse lexicographic (grevlex) orders on Z ≥ 0 d . These two polytopes have the same number of vertices, O ( d 2 ) , and the same number of edges, O ( d 3 ) , but are not combinatorially equivalent. We provide an explicit description of the vertices and the facets for both families and describe their graphs along with analyzing their basic properties such as the radius, diameter, existence of Hamiltonian circuits, and chromatic number. Moreover, we also analyze the edge expansions of these graphs. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Taibah University Medical Sciences is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper presents an efficient approach to contact force distribution, which is aimed at computing optimal contact forces to generate the required wrench for grasping an object. It has been derived in the previous work that this problem can be reduced to computing the intersection of the ray originating from the origin along the required wrench with the boundary of the grasp wrench set. Noticing that the grasp wrench set is fixed once contact positions are determined, we propose an algorithm to pre-compute a hierarchy of polytopes in the grasp wrench set and a list of facets from the interior of the grasp wrench set to its boundary. Then, the ray’s intersection can be quickly found by searching the list of facets and optimal contact forces can be computed in real time. Numerical examples show that the online computation of the proposed approach is one order of magnitude faster than the latest algorithm to compute the ray’s intersection and two orders of magnitude faster than general-purpose optimization algorithms. This approach to contact force distribution is an iterative solution that can run until reaching a desired accuracy. [ABSTRACT FROM AUTHOR]

New approach to linear systems with uncertain parameters is proposed. The notion of AE solution sets is extended to the case when the domain of parameters need not be an interval vector. The tools from the theory of convex sets are applied to the characterization of AE solution sets. The description of these sets by systems of inequalities is presented. Some examples are included. [ABSTRACT FROM AUTHOR]

We construct an orthogonal basis for the space of m × n matrices with row and column sums equal to zero. This vector space corresponds to the affine space naturally associated with the Birkhoff polytope, contingency tables and Latin squares. We also provide orthogonal bases for the spaces underlying magic squares and Sudoku boards. Our construction combines the outer (i.e., tensor or dyadic) product on vectors with certain rooted, vector-labeled, binary trees. Our bases naturally respect the decomposition of a vector space into centrosymmetric and skew-centrosymmetric pieces; the bases can be easily modified to respect the usual matrix symmetry and skew-symmetry as well. [ABSTRACT FROM AUTHOR]

This paper is devoted to systematically extend f -mirror symmetry between families of hypersurfaces in complete toric varieties, as introduced in [17] , to families of complete intersections subvarieties. Namely, f -mirror symmetry is induced by framed duality of framed toric varieties extending Batyrev-Borisov polar duality between Fano toric varieties. Framed duality has been defined and essentially well described for families of hypersurfaces in toric varieties in the previous [17]. Here it is developed for families of complete intersections, allowing us to strengthen some previous results on hypersurfaces. In particular, the class of projective complete intersections and their mirror partners are studied in detail. Moreover, a (generalized) Landau-Ginzburg/Complete-Intersection correspondence is discussed, extending to the complete intersection setup the LG/CY correspondence firstly studied Chiodo-Ruan and Krawitz. [ABSTRACT FROM AUTHOR]

Let P be a simple polytope with n − d = 2 , where d is the dimension and n is the number of facets. The graph of such a polytope is also called a grid . It is known that the directed random walk along the edges of P terminates after O ( log 2 ⁡ n ) steps, if the edges are oriented in a (pseudo-)linear fashion. We prove that the same bound holds for the more general unique sink orientations. [ABSTRACT FROM AUTHOR]

Aggregations of flexible loads can provide several power system services through demand response programs, for example load shifting and curtailment. The capabilities of demand response should therefore be represented in system operators’ planning and operational routines. However, incorporating models of every load in an aggregation into these routines could compromise their tractability by adding exorbitant numbers of new variables and constraints. In this paper, we propose a novel approximation for concisely representing the capabilities of a heterogeneous aggregation of flexible loads. We assume that each load is mathematically described by a convex polytope, i.e., a set of linear constraints, a class which includes deferrable loads, thermostatically controlled loads, and generic energy storage. The set-wise sum of the loads is the Minkowski sum, which is in general computationally intractable. Our representation is an outer approximation of the Minkowski sum. The new approximation is easily computable and only uses one variable per time period corresponding to the aggregation’s net power usage. Theoretical and numerical results indicate that the approximation is accurate for broad classes of loads. [ABSTRACT FROM AUTHOR]

Let P be a finite poset. By definition, the linear extension polytope of P has as vertices the characteristic vectors of all linear extensions of P . In case P is an antichain, it is the linear ordering polytope. The linear extension polytope appears in combinatorial optimization in the context of scheduling with precedence constraints, see e.g. [A. Schulz, Polytopes and Scheduling, Phd Thesis, TU Berlin, 1996]. It seems also relevant to order theory, being similar in spirit to other constructions such as the linear extension graph, see e.g. [M. Massow, Linear extension graphs and linear extension diameter, PhD thesis, TU Berlin, 2009]. In this work, we relate the combinatorial properties of the poset P to the polyhedral structure of its linear extension polytope. Of particular interest is a natural relaxation of the linear extension polytope. We prove that the relaxation is exact in case P is a width-2 poset, and formulate a conjecture stating exactly when the relaxation is exact. [ABSTRACT FROM AUTHOR]

In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we focus on binary Steiner trees in which all node degrees are required to be at most three. It is shown that finding a binary Steiner tree is NP -complete for arbitrary graphs. We relate the problem to Steiner trees without degree constraints as well as degree-constrained spanning trees by proving approximation ratios. Further, we give integer programming formulations for this problem on undirected and directed graphs and study the associated polytopes for both cases. Some classes of facets are introduced. Based on this study a branch-&-cut approach is developed and evaluated on biological instances coming from the reconstruction of phylogenetic trees. We are able to solve nearly all instances up to 200 nodes to optimality within a limited amount of time. This shows the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

In this paper we consider the k-node connected subgraph problem. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We introduce further classes of valid inequalities and discuss their facial aspect. We also devise separation routines and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using those results, we devise a Branch-and-Cut algorithm and present some preliminary computational results. [ABSTRACT FROM AUTHOR]

This paper is devoted to the research of global dynamics for the Hamiltonian system formed by the unified scalar field cosmology. We prove that this system possesses only unbounded dynamics in the space of negative curvature. It is found the invariant domain filled only by unbounded dynamics for the space with positive curvature. Further, we construct a set of polytopes depending on the Hamiltonian level surface that contain all compact invariant sets. Besides, one invariant two dimensional plane is described. Finally, we establish nonchaoticity of dynamics in one special case. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a connected graph, and k a positive integer. A subset D ⊆ V is a k-hop connected dominating set ( k -CDS) if the subgraph of G induced by D is connected and, for every vertex v in G , there is a vertex u in D such that the distance between v and u is at most k . We study the problem of finding a minimum k -hop connected dominating set, denoted by the acronym Min k -CDS. Firstly, we prove that Min k -CDS is NP -hard on planar bipartite graphs of maximum degree 4 and on planar biconnected graphs of maximum degree 5. We present an inapproximability threshold for Min k -CDS on bipartite and on (1, 2)-split graphs, and we also prove that Min k -CDS is APX -hard on bipartite graphs of maximum degree 4. These results are shown to hold for every positive integer k . For k = 1 , the classical minimum connected dominating set problem, we present an integer linear programming formulation and show some classes of inequalities that define facets of the corresponding polytope. We also present an approximation algorithm for this case. [ABSTRACT FROM AUTHOR]

Matrix algorithms are an important part of many digital signal processing applications as they are core kernels that are usually required to be applied many times while computing different tasks. Hardware assisted implementations using FPGAs provide a good compromise between performance, cost and power consumption, specially when high level synthesis techniques are employed for deriving co-processors. In this paper a high level synthesis approach to generate embedded processor arrays for matrix algorithms based on the polytope model is presented. The proposed approach provides a solution for efficient data memory accesses and data transferring for feeding the processor array, as well as support for solving problems independently of their size and limited only by the FPGA available resources. The proposed approach has been validated by generating processor arrays for three different matrix algorithms used in digital signal processing applications; more precisely matrix–matrix multiplication, Cholesky and LU decomposition algorithms. These algorithms were targeted for a Spartan-6 device and compared against their sequential implementations targeted for a MicroBlaze processor in order to provide a general view of the gain achieved by the processor arrays when the arrays and sequential processors are implemented in the same technology. Results show that the implemented arrays outperforms hardware and software implementations considering an embedded platforms scenario with a Spartan-6 device. [ABSTRACT FROM AUTHOR]

To determine the relative position of any two surfaces in a system, one approach is to use operations (Minkowski sum and intersection) on sets of constraints. These constraints are made compliant with half-spaces of R n where each set of half-spaces defines an operand polyhedron. These operands are generally unbounded due to the inclusion of degrees of invariance for surfaces and degrees of freedom for joints defining theoretically unlimited displacements. To solve operations on operands, Minkowski sums in particular, “cap” half-spaces are added to each polyhedron to make it compliant with a polytope which is by definition a bounded polyhedron. The difficulty of this method lies in controlling the influence of these additional half-spaces on the topology of polytopes calculated by sum or intersection. This is necessary to validate the geometric tolerances that ensure the compliance of a mechanical system in terms of functional requirements. [ABSTRACT FROM AUTHOR]

In tolerancing analysis area, a classical approach consists in handling sets of linear constraints. These sets of constraints characterize the boundaries of the relative displacements between two surfaces of the same workpiece or between two surfaces of two different parts, potentially in contact. The relative position between any two surfaces of a mechanism is determined by operations on these sets of constraints (Minkowski sum and intersection). A method for solving these operations is to model each set of constraints by a polytope, which by definition is a bounded intersection of many finitely closed half-spaces in some . However, the intersection of half-spaces simulating geometric constraints or contact is generally not bounded. This is due to the degree of invariance of a surface and the degree of freedom of a joint characterizing theoretically unbounded displacement. This article introduces the concept of “cap” half-spaces to delimit sets of constraints in . They are added to the operand set and in this way determining the relative position of two surfaces of a mechanical system is based solely on operations on operand polytopes generating a calculated polytope. By checking that a calculated polytope is included within a functional polytope the conformity of a mechanical system can be simulated with respect to a functional requirement. The addition of cap half-spaces to the operand sets will affect the topology of a calculated polytope. Hence it has to be possible to differentiate among all the facets of a calculated polytope between those that are generated by the cap half-spaces and the others generated by half-spaces that derive from geometric and contact constraints. This is essential in order to validate the geometric tolerances that ensure that a mechanical system is compliant in relation to a functional requirement. This article describes how to identify the facets generated by the cap half-spaces of a polytope resulting from a Minkowski sum or an intersection between two operand polytopes. [ABSTRACT FROM AUTHOR]

In this paper, we study the connected subgraph polytope which is the convex hull of the solutions to a related combinatorial optimization problem called the maximum weight connected subgraph problem. We strengthen a cut-based formulation by considering some new partition inequalities for which we give necessary and sufficient conditions to be facet defining. Based on the separation problem associated with these inequalities, we give a complete polyhedral characterization of the connected subgraph polytope on cycles and trees. [ABSTRACT FROM AUTHOR]

It is crucial for maintaining the security of supply that transmission networks continue to operate even if a single line fails. Modeling N − 1 security in power system capacity expansion problems introduces many extra constraints if all possible outages are accounted for, which leads to a high computational burden. Typical approaches to avoid this burden consider only a subset of possible outages relevant to a given dispatch situation. However, this relies on knowing the dispatch situation beforehand, and it is not suitable for investment optimization problems where the generation fleet is not known in advance. In this paper, we introduce a heuristic approach to model the fully secured N − 1 feasible space using a smaller number of constraints in a way that only depends on the topology of transmission networks. In our proposed approach, the network's security is modeled by comparing the polytope of the feasible space of nodal net power obtained from the security-constrained linearized AC optimal power flow problem. To approximate this polytope, a buffer capacity factor is defined for transmission lines in the N − 0 secure case, thereby avoiding the introduction of many additional constraints. In this way, three approaches are introduced for obtaining a buffer capacity factor consisting of approximate, robust and line-specific approaches. Finally, the performance of our proposed approaches is assessed in different scales of transmission networks for determining the proposed buffer capacity factors, contingency analysis and economic evaluation. Moreover, we find that our proposed heuristics provide excellent approximations of the fully secured N − 1 solutions with a much lower computational burden. • Three approaches are introduced to find buffer capacity factor for transmission lines. • The full N-1 secured network is compared with our proposed heuristic approaches. • A sensitivity analysis is performed in different topologies and German network. [ABSTRACT FROM AUTHOR]

We consider the Bipartite Boolean Quadratic Programming Problem (BQP01), which generalizes the well-known Boolean quadratic programming problem (QP01). The model has applications in graph theory, matrix factorization and bioinformatics, among others. The primary focus of this paper is on studying the structure of the Bipartite Boolean Quadric Polytope (BQP m , n) resulting from a linearization of a quadratic integer programming formulation of BQP01. We present some basic properties and partial relaxations of BQP m , n , as well as some families of facets and valid inequalities. We find facet-defining inequalities including a family of odd-cycle inequalities. We discuss various approaches to obtain a valid inequality and facets from those of the related Boolean quadric polytope. The key strategy is based on rounding coefficients, and it is applied to the families of clique and cut inequalities in BQP m , n. [ABSTRACT FROM AUTHOR]

Abstract: We provide an analytical description of the Minkowski sum of simplices in . The convex polytope is determined by the coordinates of facets' vertices, may the polytope be degenerate or not. The pre-established description of the polytope allows a rapid implementation using popular applications, here achieved using Matlab®. [Copyright &y& Elsevier]

Abstract: An implicit linear description of the stable matching polytope is provided in terms of the blocker and antiblocker sets of constraints of the matroid-kernel polytope. The explicit identification of both these sets is based on a partition of the stable pairs in which each agent participates. Here, we expose the relation of such a partition to rotations. We provide a time-optimal algorithm for obtaining such a partition and establish some new related results; most importantly, that this partition is unique. [Copyright &y& Elsevier]

Abstract: Given a regular polytope in Euclidean space and an orthogonal projection to the complex plane, the function which assigns to each vertex its projected value satisfies a quadratic difference equation. The form of the equation is the same, whatever the polytope, except for a real parameter ρ which varies from polytope to polytope. It is independent of the projection used and the size of the polytope. When we consider an orthogonal projection of a smooth hypersurface in Euclidean space, remarkably we find the same phenomena, namely that a smooth version of the equation is satisfied independently of the projection, where the parameter ρ depends only on the mean curvature. We therefore make an unconventional definition of a constant mean-curvature polytope as one which satisfies this same equation with ρ constant, independently of the orthogonal projection. We discuss some examples of constant mean curvature polytopes. [Copyright &y& Elsevier]