On the secant varieties to the tangential varieties of a Veronesean

We study the dimensions of the higher secant varieties to the tangent varieties of Veronese varieties. Our approach, generalizing that of Terracini, concerns 0-dimensional schemes which are the union of second infinitesimal neighbourhoods of generic points, each intersected with a generic double line.

We find the deficient secant line varieties for all the Veroneseans and all the deficient higher secant varieties for the quadratic Veroneseans. We conjecture that these are the only deficient secant varieties in this family and prove this up to secant projective 4-spaces.

     

Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems

In this paper, we propose a generic approach to find compromise solutions for multiple-objective scheduling problems using metaheuristics. As an illustration, we present a new hybrid tabu search/variable neighbourhood search application of this approach for the solution of a bi-objective scheduling problem. Through numerical experiments we demonstrate its efficiency and effectiveness. We have confirmed that compromise programming with the tabu-VNS metaheuristic generates solutions that approach those of the known reference sets.     

Clustering of search trajectory and its application to parameter tuning

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.     

Curvature of Hessian manifolds

We prove that, in dimensions greater than 2, the generic metric is not a Hessian metric and find a curvature condition on Hessian metrics in dimensions greater than 3. In particular we prove that the forms used to define the Pontryagin classes in terms of the curvature vanish on a Hessian manifold. By contrast all analytic Riemannian 2-metrics are Hessian metrics.     

New Classes of Counterexamples to Hendrickson’s Global Rigidity Conjecture

We examine the generic local and global rigidity of various graphs in ℝ ^d . Bruce Hendrickson showed that some necessary conditions for generic global rigidity are (d+1)-connectedness and generic redundant rigidity, and hypothesized that they were sufficient in all dimensions. We analyze two classes of graphs that satisfy Hendrickson’s conditions for generic global rigidity, yet fail to be generically globally rigid. We find a large family of bipartite graphs for d>3, and we define a construction that generates infinitely many graphs in ℝ⁵. Finally, we state some conjectures for further exploration.     

Event detection occurrence for planar piece-wise affine hybrid systems

Many switched circuits are made of linear components switched by a simple logic unit. In this paper, we use a generic planar Piece-wise Affine Hybrid System (PWAHS) to model this kind of circuit. Usually, simulations are run by analytical methods (adapted to a specific simple model) or by numerical simulations that can miss some events’ occurrences. We propose a generic planar method to simulate PWAHSs with periodic and state dependent events. Using analytical expressions, our approach can reach arbitrary accuracy in event detections without any loss. As a result, we have implemented our method in Scilab and Matlab toolboxes.     

Double variable neighbourhood search with smoothing for the molecular distance geometry problem

We discuss the geometrical interpretation of a well-known smoothing operator applied to the Molecular Distance Geometry Problem (MDGP), and we then describe a heuristic approach based on Variable Neighbourhood Search on the smoothed and original problem. This algorithm often manages to find solutions having higher accuracy than other methods. This is important as small differences in the objective function value may point to completely different 3D molecular structures.     

Multi-pattern matching with bidirectional indexes

We study multi-pattern matching in a scenario where the pattern set is to be matched to several texts and hence indexing the pattern set is affordable. This kind of scenarios arise, for example, in metagenomics, where pattern set represents DNA of several species and the goal is to find out which species are represented in the sample and in which quantity. We develop a generic search method that exploits bidirectional indexes both for the pattern set and texts, and analyze the best and worst case running time of the method on worst case text. We show that finding the instance of the search method with minimum best case running time on worst case text is NP-hard. The positive result is that an instance with logarithm factor approximation to minimum best case running time can be found in polynomial time using a bidirectional index called affix tree. We further show that affix trees can be simulated, in reduced space, using bidirectional variant of compressed suffix trees. Lastly, we provide a practical implementation of this approach. We show that one can obtain 3-fold speed up against the basic scenario of searching each pattern independently with data sets typical in high-throughput DNA sequencing.     

An exact approach to sparse principal component analysis

We show a branch and bound approach to exactly find the best sparse dimension reduction of a matrix. We can choose between enforcing orthogonality of the coefficients and uncorrelation of the components, and can explicitly set the degree of sparsity. We suggest methods to choose the number of non-zero loadings for each component; illustrate and compare our approach with existing methods through a benchmark data set.     

Weighted energy decay for 3D Klein-Gordon equation

We obtain a dispersive long-time decay in weighted energy norms for solutions of the 3D Klein-Gordon equation with generic potential. The decay extends the results obtained by Jensen and Kato for the 3D Schrödinger equation. For the proof we modify the spectral approach of Jensen and Kato to make it applicable to relativistic equations.     

Solving an integrated job-shop problem with human resource constraints

We propose two exact methods to solve an integrated employee-timetable and job-shop-scheduling problem. The problem is to find a minimum cost employee-timetable, where employees have different competences and work during shifts, so that the production, that corresponds to a job-shop with resource availability constraints, can be achieved. We introduce two new exact procedures: (1) a decomposition and cut generation approach and (2) a hybridization of a cut generation process with a branch and bound strategy. We also propose initial cuts that strongly improve these methods as well as a standard MIP approach. The computational performances of those methods on benchmark instances are compared to that of other methods from the literature.     

Contact Relative Differential Invariants for Non Generic Parabolic Monge-Ampère Equations

We find relative differential invariants of different orders for non generic parabolic Monge-Ampère equations (MAE’s). They are constructed in terms of some tensors associated with the derived flag of the characteristic distribution. The vanishing of such invariants allows one to determine the classes of each non generic parabolic MAE with respect to contact transformations.     

Automorphisms of Jacobian Kummer surfaces

We study automorphisms of a generic Jacobian Kummer surface. First weanalyse the action of classically known automorphisms on the Picard lattice of the surface, then proceed to construct new automorphisms not generated by classical ones. We find 192 such automorphisms, all conjugateby the symmetry group of the (16,6)-configuration.     

Lagrangian Manifolds and Efficient Short-Wave Asymptotics in a Neighborhood of a Caustic Cusp

Mathematical Notes - We develop an approach to writing efficient short-wave asymptotics based on the representation of the Maslov canonical operator in a neighborhood of generic caustics in the...     

Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism

We present a self-adaptive and distributed metaheuristic called Coalition-Based Metaheuristic (CBM). This method is based on the Agent Metaheuristic Framework (AMF) and hyper-heuristic approach. In CBM, several agents, grouped in a coalition, concurrently explore the search space of a given problem instance. Each agent modifies a solution with a set of operators. The selection of these operators is determined by heuristic rules dynamically adapted by individual and collective learning mechanisms. The intention of this study is to exploit AMF and hyper-heuristic approaches to conceive an efficient, flexible and modular metaheuristic. AMF provides a generic model of metaheuristic that encourages modularity, and hyper-heuristic approach gives some guidelines to design flexible search methods. The performance of CBM is assessed by computational experiments on the vehicle routing problem.     

A probabilistic (max, +) approach for determining railway infrastructure capacity

We consider the problem of determining the capacity of a planned railway infrastructure layout under uncertainties. In order to address the long-term nature of the problem, in which the exact (future) demand of service is unknown, we develop a “timetable”-free approach to avoid the specification of a particular timetable. We consider a generic infra-element that allows a concise representation of many different combinations of infrastructure, safety systems and traffic regimes, such as mixed double and single track lines (e.g., a double track line including a single tunnel tube), and train operations on partly overlapping routes at station yards. We translate the capacity assessment problem for such a generic infra-element into an optimization problem and provide a solution procedure. We illustrate our approach with a capacity assessment for the newly built high-speed railway line in The Netherlands.     

A line search filter algorithm with inexact step computations for equality constrained optimization

In this paper, a new line search filter algorithm for equality constrained optimization is presented. The approach belongs to the class of inexact Newton-like methods. It can also be regarded as an inexact version of generic sequential quadratic programming (SQP) methods. The trial step is obtained by truncatedly solving the primal-dual system based on any robust and efficient linear system solver. Practical termination tests for the linear system solver are established to ensure global convergence. Preliminary numerical results demonstrate the approach is potentially useful.     

Iterative methods for solving nonlinear irregular operator equations in banach space

We present an approach to constructing stable methods for solving nonlinear operator equations in Banach space without anyassumptions on the regularity of the operator. The approach is based on the linearization of the equation and the use of aregularization algorithm to find an approximate solution of the linearized equation at each iteration. The local convergence of proposed methods is proved and the estimations of the rate of convergence are established, provided that solution satisfies a sourcewise representation condition. The case of noisy data is also analysed.     

Study of discrete automaton models of gene networks of nonregular structure using symbolic calculations

We introduce the discrete automaton models of gene networks with weight functions of vertices accounting for the various forms of the regulatory interaction of agents. We study the discrete mapping that describes the operation of a fragment of the gene network of the bacteria E. coli. For this mapping, we find its fixed points (stationary states) on using the SAT approach. We also study the mappings that are defined by the random graphs of the network which we generate in accordance with the Gilbert-Erdos-Renyi and Watts-Strogatz models. For these mappings, we find the fixed points and the length 2 and 3 cycles. This article can be regarded as a survey of our results on the discrete models of gene networks and the numerical methods for studying their operation.     

Symmetry in complex networks

We consider the size and structure of the automorphism groups of a variety of empirical ‘real-world’ networks and find that, in contrast to classical random graph models, many real-world networks are richly symmetric. We construct a practical network automorphism group decomposition, relate automorphism group structure to network topology and discuss generic forms of symmetry and their origin in real-world networks. We also comment on how symmetry can affect network redundancy and robustness.