ADMM for the SDP relaxation of the QAP

Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal–dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds.     

Erratum: A tight formulation for uncapacitated lot-sizing with stock upper bounds

For an n-period uncapacitated lot-sizing problem with stock upper bounds, stock fixed costs, stock overload and backlogging, we present a tight extended shortest path formulation of the convex hull of solutions with O\((n^2)\) variables and constraints, also giving an O\((n^2)\) algorithm for the problem. This corrects and extends a formulation in Section 4.4 of our article “Lot-sizing with production and delivery time windows”, Mathematical Programming A, 107:471–489, 2006, for the problem with just stock upper bounds.     

A Lagrangian search method for the <Emphasis Type="Italic">P</Emphasis>-median problem

In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Branch-and-price for <Emphasis Type="Italic">p</Emphasis>-cluster editing

Given an input graph, the p-cluster editing problem consists of minimizing the number of editions, i.e., additions and/or deletions of edges, so as to create p vertex-disjoint cliques (clusters). In order to solve this \({\mathscr {NP}}\)-hard problem, we propose a branch-and-price algorithm over a set partitioning based formulation with exponential number of variables. We show that this formulation theoretically dominates the best known formulation for the problem. Moreover, we compare the performance of three mathematical formulations for the pricing subproblem, which is strongly \({\mathscr {NP}}\)-hard. A heuristic algorithm is also proposed to speedup the column generation procedure. We report improved bounds for benchmark instances available in the literature.     

Revisiting <Emphasis Type="Italic">k</Emphasis>-sum optimization

In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this problem. Moreover, the results developed for k-sum optimization have been extended to the more general case of the convex ordered median problem, improving upon existing solution approaches.     

An Analog of Titchmarsh’s Theorem for the Fourier–Walsh Transform

The space clos(X) of all nonempty closed subsets of an unbounded metric space X is considered. The space clos(X) is endowed with a metric in which a sequence of closed sets converges if and only if the distances from these sets to a fixed point θ are bounded and, for any r, the sequence of the unions of the given sets with the exterior balls of radius r centered at θ converges in the Hausdorff metric. The metric on clos(X) thus defined is not equivalent to the Hausdorff metric, whatever the initial metric space X. Conditions for a set to be closed, totally bounded, or compact in clos(X) are obtained; criteria for the bounded compactness and separability of clos(X) are given. The space of continuous maps from a compact space to clos(X) is considered; conditions for a set to be totally bounded in this space are found.     

Bounding Averages Rigorously Using Semidefinite Programming: Mean Moments of the Lorenz System

We describe methods for proving bounds on infinite-time averages in differential dynamical systems. The methods rely on the construction of nonnegative polynomials with certain properties, similarly to the way nonlinear stability can be proved using Lyapunov functions. Nonnegativity is enforced by requiring the polynomials to be sums of squares, a condition which is then formulated as a semidefinite program (SDP) that can be solved computationally. Although such computations are subject to numerical error, we demonstrate two ways to obtain rigorous results: using interval arithmetic to control the error of an approximate SDP solution, and finding exact analytical solutions to relatively small SDPs. Previous formulations are extended to allow for bounds depending analytically on parametric variables. These methods are illustrated using the Lorenz equations, a system with three state variables (x, y, z) and three parameters \((\beta ,\sigma ,r)\). Bounds are reported for infinite-time averages of all eighteen moments \(x^ly^mz^n\) up to quartic degree that are symmetric under \((x,y)\mapsto (-x,-y)\). These bounds apply to all solutions regardless of stability, including chaotic trajectories, periodic orbits, and equilibrium points. The analytical approach yields two novel bounds that are sharp: the mean of \(z^3\) can be no larger than its value of \((r-1)^3\) at the nonzero equilibria, and the mean of \(xy^3\) must be nonnegative. The interval arithmetic approach is applied at the standard chaotic parameters to bound eleven average moments that all appear to be maximized on the shortest periodic orbit. Our best upper bound on each such average exceeds its value on the maximizing orbit by less than 1%. Many bounds reported here are much tighter than would be possible without computer assistance.     

A two-level graph partitioning problem arising in mobile wireless communications

In the k -partition problem (k-PP), one is given an edge-weighted undirected graph, and one must partition the node set into at most k subsets, in order to minimise (or maximise) the total weight of the edges that have their end-nodes in the same subset. Various hierarchical variants of this problem have been studied in the context of data mining. We consider a ‘two-level’ variant that arises in mobile wireless communications. We show that an exact algorithm based on intelligent preprocessing, cutting planes and symmetry-breaking is capable of solving small- and medium-size instances to proven optimality, and providing strong lower bounds for larger instances.     

Hölder exponents for the pluricomplex green function of Julia type sets

Assume that the pluricomplex Green function V _E of some compact set E ? ? ^N is Hölder continuous and define the Hölder exponent of the set E to be the supremum over all such exponents, with which V _E is Hölder continuous. We give some lower bounds of the Hölder exponents for the filled-in and composite Julia sets of polynomial mappings.     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.     

Gradient continuity estimates

We consider degenerate elliptic equations of p-Laplacean type

$$-{\rm{div}}\, (\gamma(x)|Du|^{p-2}Du)=\mu\,,$$

and give a sufficient condition for the continuity of Du in terms of a natural non-linear Wolff potential of the right-hand side measure μ. As a corollary we identify borderline condition for the continuity of Du in terms of the data: namely μ belongs to the Lorentz space L(n, 1/(p ? 1)), and γ(x) is a Dini continuous elliptic coefficient. This last result, together with pointwise gradient bounds via non-linear potentials, extends to the non homogeneous p-Laplacean system, thereby giving a positive answer in the vectorial case to a conjecture of Verbitsky. Continuity conditions related to the density of μ, or to the decay rate of its L ⁿ -norm on small balls, are identified as well as corollaries of the main non-linear potential criterium.

     

Continuous reducibility and dimension of metric spaces

If (X, d) is a Polish metric space of dimension 0, then by Wadge’s lemma, no more than two Borel subsets of X are incomparable with respect to continuous reducibility. In contrast, our main result shows that for any metric space (X, d) of positive dimension, there are uncountably many Borel subsets of (X, d) that are pairwise incomparable with respect to continuous reducibility. In general, the reducibility that is given by the collection of continuous functions on a topological space \((X,\tau )\) is called the Wadge quasi-order for \((X,\tau )\). As an application of the main result, we show that this quasi-order, restricted to the Borel subsets of a Polish space \((X,\tau )\), is a well-quasiorder if and only if \((X,\tau )\) has dimension 0. Moreover, we give further examples of applications of the construction of graph colorings that is used in the proofs.     

The absolute continuity of convolution products of orbital measures in exceptional symmetric spaces

Let G be a non-compact group, K the compact subgroup fixed by a Cartan involution and assume G / K is an exceptional, symmetric space, one of Cartan type E, F or G. We find the minimal integer, L(G),  such that any convolution product of L(G) continuous, K-bi-invariant measures on G is absolutely continuous with respect to Haar measure. Further, any product of L(G) double cosets has non-empty interior. The number L(G) is either 2 or 3, depending on the Cartan type, and in most cases is strictly less than the rank of G.     

New Criteria for the Existence of a Continuous <Emphasis Type="Italic">ε</Emphasis>-Selection

We study sets admitting a continuous selection of near-best approximations and characterize those sets in Banach spaces for which there exists a continuous ε-selection for each ε > 0. The characterization is given in terms of P-cell-likeness and similar properties. In particular, we show that a closed uniqueness set in a uniformly convex space admits a continuous ε-selection for each ε > 0 if and only if it is B-approximately trivial. We also obtain a fixed point theorem.     

Large sublattices in subsets of Banach lattices

A classical problem (initially studied by N. Kalton and A. Wilansky) concerns finding closed infinite dimensional subspaces of X / Y, where Y is a subspace of a Banach space X. We study the Banach lattice analogue of this question. For a Banach lattice X, we prove that X / Y contains a closed infinite dimensional sublattice under the following conditions: either (i) Y is a closed infinite codimensional subspace of X, and X is either order continuous or a C(K) space, where K is a compact subset of \({\mathbb {R}}^n\); or (ii) Y is the range of a compact operator.     

A partition-based relaxation for Steiner trees

The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V, E), a set of terminals \({R\subseteq V}\) , and non-negative costs c _e for all edges \({e \in E}\) . Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The vertices \({V \backslash R}\) are called Steiner vertices. The best approximation algorithm known for the Steiner tree problem is a greedy algorithm due to Robins and Zelikovsky (SIAM J Discrete Math 19(1):122–134, 2005); it achieves a performance guarantee of \({1+\frac{\ln 3}{2}\approx 1.55}\) . The best known linear programming (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math Program 60:145–166, 1993) and achieves an approximation ratio of 2?2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky’s algorithm can be viewed as an iterated primal-dual algorithm with respect to a novel LP relaxation. The LP used in the first iteration is stronger than the well-known bidirected cut relaxation. An instance is b-quasi-bipartite if each connected component of \({G \backslash R}\) has at most b vertices. We show that Robins’ and Zelikovsky’s algorithm has an approximation ratio better than \({1+\frac{\ln 3}{2}}\) for such instances, and we prove that the integrality gap of our LP is between \({\frac{8}{7}}\) and \({\frac{2b+1}{b+1}}\) .     

On the measurable chromatic number of a space of dimension n ≤ 24

This paper is devoted to the classical problem of finding the measurable chromatic number of n-dimensional Euclidean space, i.e., the value χ _m (? ⁿ ) equal to the least possible number of Lebesgue measurable sets that do not contain pairs of points at a distance of 1 and cover the whole space. Assuming that a certain hypothesis is true, we significantly improve the lower bounds for χ _m (? ⁿ ).     

The order continuity in ordered algebras

Let A be an ordered algebra with a unit \(\mathbf{e}\) and a cone \(A^+\). The class of order continuous elements \(A_\mathrm{n}\) of A is introduced and studied. If \(A=L(E)\), where E is a Dedekind complete Riesz space, this class coincides with the band \(L_\mathrm{n}(E)\) of all order continuous operators on E. Special subclasses of \(A_\mathrm {n}\) are considered. Firstly, the order ideal \(A_\mathbf{e}\) generated by \(\mathbf{e}\). It is shown that \(A_\mathbf{e}\) can be embedded into the algebra of continuous functions and, in particular, is a commutative subalgebra of A. If A is an ordered Banach algebra with normal cone \(A^+\) then \(A_\mathbf{e}\) is an AM-space and is closed in A. Secondly, the notion of an orthomorphism in the ordered algebra A is introduced. Among others, the conditions under which orthomorphisms are order continuous, are considered. In the second part, the main emphasis will be on the case of an ordered \(C^*\)-algebra A and, in particular, on the case of the algebra B(H), where H is an ordered Hilbert space with self-adjoint cone \(H^+\). If the cone \(A^+\) is normal then every element of \(A_\mathbf{e}\) is hermitian. In H the operations are introduced which coincide with the lattice ones when H is a Riesz space. It is shown that every regular \(T\in B(H)\) is an order continuous element and operators \(T\in (B(H))_I\) have properties which are analogous to the properties of orthomorphisms on Riesz spaces.