Derivations on ideals in commutative AW*-algebras

LetA be a commutativeAW*-algebra.We denote by S(A) the *-algebra of measurable operators that are affiliated with A. For an ideal I in A, let s(I) denote the support of I. Let Y be a solid linear subspace in S(A). We find necessary and sufficient conditions for existence of nonzero band preserving derivations from I to Y. We prove that no nonzero band preserving derivation from I to Y exists if either Y ? Aor Y is a quasi-normed solid space. We also show that a nonzero band preserving derivation from I to S(A) exists if and only if the boolean algebra of projections in the AW*-algebra s(I)A is not σ-distributive.     

Elements with prime and small indices in bicyclic biquadratic number fields

We give necessary and sufficient conditions for the existence of primitive algebraic integers with index A in totally complex bicyclic biquadratic number fields where A is an odd prime or a positive rational integer at most 10. We also determine all these elements and prove that there are infinitely many totally complex bicyclic biquadratic number fields containing elements with index A.     

Equidistribution of numerical semigroup gaps modulo m

For a positive integer m, a finite set of integers is said to be equidistributed modulo m if the set contains an equal number of elements in each congruence class modulo m. In this paper, we consider the problem of determining when the set of gaps of a numerical semigroup S is equidistributed modulo m. Of particular interest is the case when the nonzero elements of an Apéry set of S form an arithmetic sequence. We explicitly describe such numerical semigroups S and determine conditions for which the sets of gaps of these numerical semigroups are equidistributed modulo m.     

On the integrality of an extreme solution to pluperfect graph and balanced systems

Let A be a nonnegative integer matrix, and let e denote the vector all of whose components are equal to 1. The pluperfect graph theorem states that if for all integer vectors b the optimal objective value of the linear program minse′xvbAx ? b, x ? 0 s is integer, then those linear programs possess optimal integer solutions. We strengthen this theorem and show that any lexicomaximal optimal solution to the above linear program (under any arbitrary ordering of the variables) is integral and an extreme point of sxvbAx ? b, x ? 0 s. We note that this extremality property of integer solutions is also shared by covering as well as packing problems defined by a balanced matrix A.     

On absolute valued algebras with involution

Let A be an absolute valued algebra with involution, in the sense of Urbanik [K. Urbanik, Absolute valued algebras with an involution, Fund. Math. 49 (1961) 247-258]. We prove that A is finite-dimensional if and only if the algebra obtained by symmetrizing the product of A is simple, if and only if eA_s = A_s, where e denotes the unique nonzero self-adjoint idempotent of A, and A_s stands for the set of all skew elements of A. We determine the idempotents of A, and show that A is the linear hull of the set of its idempotents if and only if A is equal to either McClay’s algebra [A.A. Albert, A note of correction, Bull. Amer. Math. Soc. 55 (1949) 1191], the para-quaternion algebra, or the para-octonion algebra. We also prove that, if A is infinite-dimensional, then it can be enlarged to an absolute valued algebra with involution having a nonzero idempotent different from the unique nonzero self-adjoint idempotent.     

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax−by⩽z+c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions.Nonmonotone integer programs are optimization problems with constraints of the type ax+by⩽z+c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe.The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover.Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality.     

Monomial patterns in the sequence Akb

We consider the pattern of zero and nonzero elements in the sequence A^kb, where A is an n × n nonnegative matrix and b is an n × 1 nonnegative column vector. We establish a tight bound of k < n for the first occurrence of a given monomial pattern, and we give a graph theoretic characterization of triples (A, b, i) such that there exists a k, k ⩾ n, for which A^kb is an i-monomial. The appearance of monomial patterns with a single nonzero entry is linked to controllability of discrete n-dimensional linear dynamic systems with positivity constraints on the state and control.     

The average shadow price for MILPs with integral resource availability and its relationship to the marginal unit shadow price

The economic significance of the average shadow price for integer and mixed integer linear programming (MILP) problems has been established by researchers [Kim and Cho, Eur. J. Operat. Res. 37 (1988) 328; Crema Eur. J. Operat. Res. 85 (1995) 625]. In this paper we introduce a valid shadow price (ASPIRA) for integer programs where the right-hand side resource availability can only be varied in discrete steps. We also introduce the concept of marginal unit shadow price (MUSP). We show that for integer programs, a sufficient condition for the marginal unit shadow price to equal the average shadow price is that the Law of Diminishing Returns should hold. The polyhedral structures that will guarantee this equivalence have been explored. Identification of the problem classes for which the equivalence holds complements the existing procedure for determining shadow price for such integer programs. The concepts of ASPIRA and MUSP introduced in this paper can play a vital role in resource acquisition plans and in defining efficient market clearing prices in the presence of indivisibilities.     

Total dual integrality and integer polyhedra

A linear system Ax ? b (A, b rational) is said to be totally dual integral (TDI) if for any integer objective function c such that max {cx: Ax ? b} exists, there is an integer optimum dual solution. We show that if P is a polytope all of whose vertices are integer valued, then it is the solution set of a TDI system Ax ? b where b is integer valued. This was shown by Edmonds and Giles [4] to be a sufficient condition for a polytope to have integer vertices.     

A distributed computation algorithm for solving portfolio problems with integer variables

A portfolio problem with integer variables can facilitate the use of complex models, including models containing discrete asset values, transaction costs, and logical constraints. This study proposes a distributed algorithm for solving a portfolio program to obtain a global optimum. For a portfolio problem with n integer variables, the objective function first is converted into an ellipse function containing n separated quadratic terms. Next, the problem is decomposed into m equal-size separable programming problems solvable by a distributed computation system composed of m personal computers linked via the Internet. The numerical examples illustrate that the proposed method can obtain the global optimum effectively for large scale portfolio problems involving integral variables.     

Second-order neutral delay-differential equations with piecewise constant time dependence

We find conditions for the existence and uniqueness of almost periodic solutions of second-order neutral delay-differential equations with almost periodic time dependence of the form (x(t)+px(t−1))″=qx([t])+f(t); here [·] is the greatest integer function, p and q are nonzero constants, and f(t) is Bohr almost periodic.     

Lower bounds for commutative radical Banach algebras

One says a commutative radical Banach algebra A has a lower bound if there is a lower growth condition on $\text{∥x}{}^{\mathrm{n}}\text{∥}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ for all nonzero elements x in A. If A is a separable algebra we give necessary and sufficient conditions for A to possess a lower bound.     

Test sets for integer programs

In this paper I discuss various properties of the simplicial complex of maximal lattice free bodies associated with a matrixA. If the matrix satisfies some mild conditions, and isgeneric, the edges of the complex form the minimal test set for the family of integer programs obtained by selecting a particular row ofA as the objective function, and using the remaining rows to impose constraints on the integer variables.     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.     

Squarefree numbers in sumsets

We solve a problem of Filaseta by proving, that if N is sufficiently large, A ⊆ [N], |A| > N/9 and A + Adoes not contain any squarefree integer then all elements of A are congruent to 0 (mod 4) or 2 (mod 4). In order to show the main result we characterize the structure of all dense sets, whose elements sum to no squarefree number.     

RENS

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution $\bar{x}$ of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables $x_j$ with $\bar{x} _{j} \in \mathbb {Z}$ and bounding the remaining integer variables to $x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}$ . We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.     

Simplicity transformations for three-way arrays with symmetric slices, and applications to Tucker-3 models with sparse core arrays

Tucker three-way PCA and Candecomp/Parafac are two well-known methods of generalizing principal component analysis to three way data. Candecomp/Parafac yields component matrices A (e.g., for subjects or objects), B (e.g., for variables) and C (e.g., for occasions) that are typically unique up to jointly permuting and rescaling columns. Tucker-3 analysis, on the other hand, has full transformational freedom. That is, the fit does not change when A,B, and C are postmultiplied by nonsingular transformation matrices, provided that the inverse transformations are applied to the so-called core array . This freedom of transformation can be used to create a simple structure in A,B,C, and/or in . This paper deals with the latter possibility exclusively. It revolves around the question of how a core array, or, in fact, any three-way array can be transformed to have a maximum number of zero elements. Direct applications are in Tucker-3 analysis, where simplicity of the core may facilitate the interpretation of a Tucker-3 solution, and in constrained Tucker-3 analysis, where hypotheses involving sparse cores are taken into account. In the latter cases, it is important to know what degree of sparseness can be attained as a tautology, by using the transformational freedom. In addition, simplicity transformations have proven useful as a mathematical tool to examine rank and generic or typical rank of three-way arrays. So far, a number of simplicity results have been attained, pertaining to arrays sampled randomly from continuous distributions. These results do not apply to three-way arrays with symmetric slices in one direction. The present paper offers a number of simplicity results for arrays with symmetric slices of order 2×2,3×3 and 4×4. Some generalizations to higher orders are also discussed. As a mathematical application, the problem of determining the typical rank of 4×3×3 and 5×3×3 arrays with symmetric slices will be revisited, using a sparse form with only 8 out of 36 elements nonzero for the former case and 10 out of 45 elements nonzero for the latter one, that can be attained almost surely for such arrays. The issue of maximal simplicity of the targets to be presented will be addressed, either by formal proofs or by relying on simulation results.     

Dualizing,projecting, and restricting GKZ systems

Let A be an integer matrix, and assume that its semigroup ring $\mathbb{C}[\mathbb{N}A]$ is normal. Fix a face F of the cone of A. We show that the projection and restriction of an A-hypergeometric system to the coordinate subspace corresponding to F are essentially F-hypergeometric; moreover, at most one of them is nonzero.We also show that, if A is in addition homogeneous, the holonomic dual of an A-hypergeometric system is itself A-hypergeometric. This extends a result from [16], proving a conjecture of Nobuki Takayama in the normal homogeneous case.     

Lengths of central linear generalized polynomials in matrix algebras

Let D be a division algebra finite-dimensional over its center C and let A=M_m(D), the m×m matrix ring over D. By the length of a linear generalized polynomial (GP) ?(X), we mean the least positive integer n such that ?(X) can be represented in the form for some . We denote by L(?)=n the length of ?. By a central linear GP for A we mean a nonzero linear GP with central values on A. In this paper we characterize all central linear GPs for A and determine the lengths of all central linear GPs for A.