A Lagrangian relaxation approach to the edge-weighted clique problem

The b-clique polytope CPⁿ_b is the convex hull of the node and edge incidence vectors of all subcliques of size at most b of a complete graph on n nodes. Including the Boolean quadric polytope QPⁿ=CPⁿ_n as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over CPⁿ_n. The problem of optimizing linear functions over CPⁿ_b has so far been approached via heuristic combinatorial algorithms and cutting-plane methods.We study the structure of CPⁿ_b in further detail and present a new computational approach to the linear optimization problem based on the idea of integrating cutting planes into a Lagrangian relaxation of an integer programming problem that Balas and Christofides had suggested for the traveling salesman problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.     

Long monotone paths on simple 4-polytopes

TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M _ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path.     

On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

The monotone asymmetric travelling salesman polytope P?ⁿ_T is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?ⁿ_T. This result indicates that P?ⁿ_T has very complicated facets and that it is very unlikely that an explicit complete characterization of P?ⁿ_T can ever be given.     

A Polyhedral Approach for Nonconvex Quadratic Programming Problems with Box Constraints

We apply a linearization technique for nonconvex quadratic problems with box constraints. We show that cutting plane algorithms can be designed to solve the equivalent problems which minimize a linear function over a convex region. We propose several classes of valid inequalities of the convex region which are closely related to the Boolean quadric polytope. We also describe heuristic procedures for generating cutting planes. Results of preliminary computational experiments show that our inequalities generate a polytope which is a fairly tight approximation of the convex region.     

Partial linear characterizations of the asymmetric travelling salesman polytope

We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

Approximately reducing subspaces for unbounded linear operators

We give sufficient conditions for generation of strongly continuous contraction semigroups of linear operators on Hilbert or Banach space. Let L be a dissipative (unbounded) linear operator in a Hilbert space $\text{H}$ and let {P_n} be an increasing sequence of self-adjoint projections converging weakly to the identity projection. We show that if there is a positive integer k such that for all n the range of P_n is contained in the domain of L and mapped by L into the range of P_{n + k}, and if the sequence {LP_n ? P_nLP_n} is dominated in norm (∥LP_n ? P_nLP_n∥ ? a_n) by some {a_n} ? $\text{R}$₊ with ∑_{n = 1}^∞a_n^?1 = ∞, then the closure of the restriction of L to ∪_{n = 1}^∞ range (P_n) is the infinitesimal generator of a strongly continuous contraction semigroup on $\text{H}$. Applications to an important class of finite perturbations, properly larger than the finite Kato perturbations, are given.We also give sufficient conditions for generation of contraction semigroups when {P_γ} (indexed by a directed set) is a set of bounded self-adjoint operators converging weakly to the identity and each having range contained in D(L). In the latter theorem, and in an analogous theorem for dissipative linear operators L in a Banach space, we do not assume that L interchanges at most finitely many of the approximately reducing operators P_γ.     

On CCZ-equivalence of addition mod 2 n

We show that addition mod 2 ⁿ is CCZ-equivalent to a quadratic vectorial Boolean function. We use this to reduce the solution of systems of differential equations of addition to the solution of an equivalent system of linear equations and to derive a fully explicit formula for the correlation coefficients, which leads to enhanced results about the Walsh transform of addition mod 2 ⁿ . The results have direct applications in the cryptanalysis of cryptographic primitives which use addition mod 2 ⁿ .     

A new class of facets for the Latin square polytope

Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP_n). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities.     

Polytopes of partitions of numbers

We study the vertices and facets of the polytopes of partitions of numbers. The partition polytope P_n is the convex hull of the set of incidence vectors of all partitions n=x₁+2x₂++nx_n. We show that the sequence P₁,P₂,…,P_n,… can be treated as an embedded chain. The dynamics of behavior of the vertices of P_n, as n increases, is established. Some sufficient and some necessary conditions for a point of P_n to be its vertex are proved. Representation of the partition polytope as a polytope on a partial algebra—which is a generalization of the group polyhedron in the group theoretic approach to the integer linear programming—allows us to prove subadditive characterization of the nontrivial facets of P_n. These facets correspond to extreme rays of the cone of subadditive functions with additional requirements p₀=p_n and p_i+p_n−i=p_n,1≤i<n. The trivial facets are explicitly indicated. We also show how all vertices and facets of the polytopes of constrained partitions—in which some numbers are forbidden to participate—can be obtained from those of the polytope P_n. All vertices and facets of P_n for n≤8 and n≤6, respectively, are presented.     

On the Skeleton of the Polytope of Pyramidal Tours

We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city n, and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR(n) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph K _n . The skeleton of PYR(n) is the graph whose vertex set is the vertex set of PYR(n) and the edge set is the set of geometric edges or one-dimensional faces of PYR(n). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR(n). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR(n) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR(n) is Θ(n²). It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.     

On the truncated assignment polytope

We investigate the convex polytope Ω_m,n(r) which is the convex hull of the m × nr-subpermutation matrices. The faces of Ω_m,n(r) are characterized, and formulae are obtained to compute their dimensions. The faces of Ω_m,n(r) are themselves convex polytopes, and we determine their facets.     

Analytic efficient solution set for multi-criteria quadratic programs

We present active set methods to evaluate the exact analytic efficient solution set for multi-criteria convex quadratic programming problems (MCQP) subject to linear constraints. The idea is based on the observations that a strictly convex programming problem admits a unique solution, and that the efficient solution set for a multi-criteria strictly convex quadratic programming problem with linear equality constraints can be parameterized. The case of bi-criteria quadratic programming (BCQP) is first discussed since many of the underlying ideas can be explained much more clearly in the case of two objectives. In particular we note that the efficient solution set of a BCQP problem is a curve on the surface of a polytope. The extension to problems with more than two objectives is straightforward albeit some slightly more complicated notation. Two numerical examples are given to illustrate the proposed methods.     

The aggregate capacity of virtual resources – linear models

This article addresses resource modelling with a specific interest on capacity aggregation. The capacity of a resource with regard to d types of tasks is modelled by a simplex and by a cube in the d-dimensional space. The aggregate capacity model of a virtual resource, that is, of a pool of r resources, is the d-polytope provided by the Minkowski sum of the simplices and cubes modelling the resources. The parametric identification of the d-planes supporting the facets of the polytope is established for r?=?2 and linear simplifications are provided in the (r,?d) general case. Formulated as linear inequalities, the aggregate capacity models fit in with linear programming and quadratic programming optimization techniques.     

A new algorithm for the intersection of a line with the independent set polytope of a matroid

We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n⁵). Finally, numerical tests reveal that it should only require O(n²) iterations in practice.     

On the Number of Facets of Polytopes Representing Comparative Probability Orders

Fine and Gill (Ann Probab 4:667–673, 1976) introduced the geometric representation for those comparative probability orders on n atoms that have an underlying probability measure. In this representation every such comparative probability order is represented by a region of a certain hyperplane arrangement. Maclagan (Order 15:279–295, 1999) asked how many facets a polytope, which is the closure of such a region, might have. We prove that the maximal number of facets is at least F _n?+?1, where F _n is the nth Fibonacci number. We conjecture that this lower bound is sharp. Our proof is combinatorial and makes use of the concept of a flippable pair introduced by Maclagan. We also obtain an upper bound which is not too far from the lower bound.     

A bound for the number of vertices of a polytope with applications

We prove that the number of vertices of a polytope of a particular kind is exponentially large in the dimension of the polytope. As a corollary, we prove that an n-dimensional centrally symmetric polytope with O(n) facets has {ie1-1} vertices and that the number of r-factors in a k-regular graph is exponentially large in the number of vertices of the graph provided k≥2r+1 and every cut in the graph with at least two vertices on each side has more than k/r edges.     

A theorem about antiprisms

Let P be a polytope in Rⁿ containing the origin in its interior, and let P¹ be the algebraic dual polytope of P. Let Q ? Rⁿ×[0,1] be the (n+1)-dimensional polytope that is the convex hull of P×{1} and P¹×{0}. For each face F of P, let Q(F) denote the convex hull of F×{1} and F¹×{0}, where F¹ is the dual face of P¹. Then Q is an antiprism if the set of facets of Q is precisely the collection {Q (F)} for all faces F of P. If Q is an antiprism, the correspondence between primal and dual faces of P and P¹ is manifested in the facets of Q. In this paper, necessary and sufficient conditions for the existence of antiprisms are stated and proved.     

Completely unimodal numberings of a simple polytope

A completely unimodal numbering of the m vertices of a simple d-dimensional polytope is a numbering 0, 1, …,m−1 of the vertices such that on every k-dimensional face (2≤k≤d) there is exactly one local minimum (a vertex with no lower-numbered neighbors on that face). Such numberings are abstract objective functions in the sense of Adler and Saigal [1]. It is shown that a completely unimodal numbering of the vertices of a simple polytope induces a shelling of the facets of the dual simplicial polytope. The h-vector of the dual simplicial polytope is interpreted in terms of the numbering (with respect to using a local-improvement algorithm to locate the vertex numbered 0). In the case that the polytope is combinatorially equivalent to a d-dimensional cube, a ‘successor-tuple’ for each vertex is defined which carries the crucial information of the numbering for local-improvement algorithms. Combinatorial properties of these d-tuples are studied. Finally the running time of one particular local-improvement algorithm, the Random Algorithm, is studied for completely unimodal numberings of the d-cube. It is shown that for a certain class of numberings (which includes the example of Klee and Minty [8] showing that the simplex algorithm is not polynomial and all Hamiltonian saddle-free injective pseudo-Boolean functions [6]) this algorithm has expected running time that is at worst quadratic in the dimension d.     

Bilinear and quadratic variants on the Littlewood-Offord problem

If f(x ₁, …, x _n ) is a polynomial dependent on a large number of independent Bernoulli random variables, what can be said about the maximum concentration of f on any single value? For linear polynomials, this reduces to one version of the classical Littlewood-Offord problem: Given nonzero constants a ₁, …,a _n , what is the maximum number of sums of the form ±a ₁ ± a ₂ ± … ± a _n which take on any single value? Here we consider the case where f is either a bilinear form or a quadratic form. For the bilinear case, we show that the only forms having concentration significantly larger than n ^?1 are those which are in a certain sense very close to being degenerate. For the quadratic case, we show that no form having many nonzero coefficients has concentration significantly larger than n ^?1/2. In both cases the results are nearly tight.