Fast algorithm for singly linearly constrained quadratic programs with box-like constraints

This paper focuses on a singly linearly constrained class of convex quadratic programs with box-like constraints. We propose a new fast algorithm based on parametric approach and secant approximation method to solve this class of quadratic problems. We design efficient implementations for our proposed algorithm and compare its performance with two state-of-the-art standard solvers called Gurobi and Mosek. Numerical results on a variety of test problems demonstrate that our algorithm is able to efficiently solve the large-scale problems with the dimension up to fifty million and it substantially outperforms Gurobi and Mosek in terms of the running time.     

Optimal transport and a bilevel location-allocation problem

In this paper a two-stage optimization model is studied to find the optimal location of new facilities and the optimal partition of the consumers (location-allocation problem). The social planner minimizes the social costs, i.e. the fixed costs plus the waiting time costs, taking into account that the citizens are partitioned in the region according to minimizing the capacity costs plus the distribution costs in the service regions. By using optimal transport tools, existence results of solutions to the location-allocation problem are presented together with some examples.     

Dynamic algorithm selection for pareto optimal set approximation

This paper presents a meta-algorithm for approximating the Pareto optimal set of costly black-box multiobjective optimization problems given a limited number of objective function evaluations. The key idea is to switch among different algorithms during the optimization search based on the predicted performance of each algorithm at the time. Algorithm performance is modeled using a machine learning technique based on the available information. The predicted best algorithm is then selected to run for a limited number of evaluations. The proposed approach is tested on several benchmark problems and the results are compared against those obtained using any one of the candidate algorithms alone.     

On parallel Branch and Bound frameworks for Global Optimization

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.     

On the number of derangements and derangements of prime power order of the affine general linear groups

A derangement is a permutation that has no fixed points. In this paper, we are interested in the proportion of derangements of the finite affine general linear groups. We prove a remarkably simple and explicit formula for this proportion. We also give a formula for the proportion of derangements of prime power order. Both formulae rely on a result of independent interest on partitions: we determine the generating function for the partitions with m parts and with the kth largest part not k, for every \(k\in \mathbb {N}\).     

Schur-positive sets of permutations via products and grid classes

Characterizing sets of permutations whose associated quasisymmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. In this paper, we present a general method to construct Schur-positive sets and multisets, based on geometric grid classes and the product operation. Our approach produces many new instances of Schur-positive sets and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.     

Perfect contrast XOR-based visual cryptography schemes via linear algebra

XOR-based visual cryptography scheme (XVCS) was proposed to solve the poor visual quality problem without darkening the background in the reconstructed secret image. However, investigations on XVCS are not sufficient. In this paper, we focus on the traditional model of VCS for general access structures and exploit some extended capabilities for XVCS. Our main contributions are: (1) we put forward constructions of perfect contrast XVCS using the linear algebraic technique without any assumptions such as participants may carry multiple shares or prior information about the shares are to be submitted during the secret reconstruction phase; (2) for some restricted access structures, we achieve perfect contrast and perfect pixel expansion, namely both 1, which is impossible for any OR-based visual cryptography scheme (OVCS); (3) for general access structures, we achieve perfect contrast with smaller pixel expansion compared with many of the results in the literature; (4) Theoretical analysis on the proposed constructions are provided, as well as extensive experimental results and comparisons for demonstrating the effectiveness and advantages of our constructions.     

On Pimsner–Popa bases

In this paper, we examine bases for finite index inclusion of II₁ factors and connected inclusion of finite dimensional C ^?-algebras. These bases behave nicely with respect to basic construction towers. As applications we have studied automorphisms of the hyperfinite II₁ factor R which are ‘compatible with respect to the Jones’ tower of finite dimensional C ^?-algebras’. As a further application, in both cases we obtain a characterization, in terms of bases, of basic constructions. Finally we use these bases to describe the phenomenon of multistep basic constructions (in both the cases).     

Qualitative behaviour of incompressible two-phase flows with phase transitions: The isothermal case

A thermodynamically consistent model for incompressible two-phase flows with phase transitions is considered mathematically. The model is based on first principles, i.e., balance of mass, momentum and energy. In the isothermal case, this problem is analysed to obtain local well-posedness, stability of non-degenerate equilibria, and global existence and convergence to equilibria of solutions which do not develop singularities.     

Matrix-analytic solution of infinite,finite and level-dependent second-order fluid models

This paper presents a matrix-analytic solution for second-order Markov fluid models (also known as Markov-modulated Brownian motion) with level-dependent behavior. A set of thresholds is given that divide the fluid buffer into homogeneous regimes. The generator matrix of the background Markov chain, the fluid rates (drifts) and the variances can be regime dependent. The model allows the mixing of second-order states (with positive variance) and first-order states (with zero variance) and states with zero drift. The behavior at the upper and lower boundary can be reflecting, absorbing, or a combination of them. In every regime, the solution is expressed as a matrix-exponential combination, whose matrix parameters are given by the minimal nonnegative solution of matrix quadratic equations that can be obtained by any of the well-known solution methods available for quasi birth death processes. The probability masses and the initial vectors of the matrix-exponential terms are the solutions of a set of linear equations. However, to have the necessary number of equations, new relations are required for the level boundary behavior, relations that were not needed in first-order level dependent and in homogeneous (non-level-dependent) second-order fluid models. The method presented can solve systems with hundreds of states and hundreds of thresholds without numerical issues.