Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.     

Chiral stationary phases for separation of intermedine and lycopsamine enantiomers from Symphytum uplandicum

Enantioseparation of the pyrrolizidine alkaloid isomers intermedine and lycopsamine, isolated from Symphytum uplandicum, is discussed. The separatory power of two immobilized carbohydrate‐based chiral HPLC columns, Chiralpak IA and IC, in different chromatographic conditions is compared. The study demonstrated the importance of solvent and column selection while developing such chiral HPLC separation methods. The baseline HPLC separation of the two alkaloid isomers in preparatory scale is reported for the first time. The optimized separations were achieved on a Chiralpak IA column with mobile phases of ACN/methanol (80:20) and methanol/methyl‐t‐butyl ether (90:10), both containing 0.1% diethylamine.     

Resource allocation games: a compromise stable extension of bankruptcy games

This paper presents an extension of the traditional bankruptcy problem. In a resource allocation problem there is a common-pool resource, which needs to be divided among agents. Each agent is characterized by a claim on this pool and an individual linear monetary reward function for assigned resources. Analyzing these problems a new class of transferable utility games is introduced, called resource allocation games. These games are based on the bankruptcy model, as introduced by O’Neill (Math Soc Sci 2:345–371, 1982). It is shown that the properties of totally balancedness and compromise stability can be extended to resource allocation games, although the property of convexity is not maintained in general. Moreover, an explicit expression for the nucleolus of these games is provided.     

Stability preserving model reduction for linearly coupled linear time-invariant systems

We develop a stability preserving model reduction method for linearly coupled linear time-invariant (LTI) systems. The method extends the work of Monshizadeh et al. for multi-agent systems with identical LTI agents. They propose using Bounded Real Balanced Truncation to preserve a sufficient condition for stability of the coupled system. Here, we extend this idea to arbitrary linearly coupled LTI systems using the sufficient condition for stability introduced by Reis and Stykel. The model reduction error bounds for this method also follow from results of Reis and Stykel, which allows the adaptive choice of reduced orders. We demonstrate the method on Reis's and Stykel's coupled string-beam example. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Variational Analysis of the Spectral Abscissa at a Matrix with a Nongeneric Multiple Eigenvalue

The spectral abscissa is a fundamental map from the set of complex matrices to the real numbers. Denoted α and defined as the maximum of the real parts of the eigenvalues of a matrix X, it has many applications in stability analysis of dynamical systems. The function α is nonconvex and is non-Lipschitz near matrices with multiple eigenvalues. Variational analysis of this function was presented in Burke and Overton (Math Program 90:317–352, 2001), including a complete characterization of its regular subgradients and necessary conditions which must be satisfied by all its subgradients. A complete characterization of all subgradients of α at a matrix X was also given for the case that all active eigenvalues of X (those whose real part equals α(X)) are nonderogatory (their geometric multiplicity is one) and also for the case that they are all nondefective (their geometric multiplicity equals their algebraic multiplicity). However, necessary and sufficient conditions for all subgradients in all cases remain unknown. In this paper we present necessary and sufficient conditions for the simplest example of a matrix X with a derogatory, defective multiple eigenvalue.     

Polynomial root radius optimization with affine constraints

The root radius of a polynomial is the maximum of the moduli of its roots (zeros). We consider the following optimization problem: minimize the root radius over monic polynomials of degree n, with either real or complex coefficients, subject to k linearly independent affine constraints on the coefficients. We show that there always exists an optimal polynomial with at most \(k-1\) inactive roots, that is, roots whose moduli are strictly less than the optimal root radius. We illustrate our results using some examples arising in feedback control.     

Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distributions the limiting value of the expected optimal cost of the MAP is determined by the location of the left endpoint of the support set of the distribution, and construct asymptotical bounds for the expected optimal cost.     

Family sequencing and cooperation

This paper analyzes a single-machine scheduling problem with family setup times both from an optimization and a cost allocation perspective. In a family sequencing situation jobs are processed on a single machine, there is an initial processing order on the jobs, and every job within a family has an identical cost function that depends linearly on its completion time. Moreover, a job does not require a setup when preceded by another job from the same family while a family specific setup time is required when a job follows a member of some other family.