Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?

The Miller–Tucker–Zemlin (MTZ) Subtour Elimination Constraints (SECs) and the improved version by Desrochers and Laporte (DL) have been and are still in regular use to model a variety of routing problems. This paper presents a systematic way of deriving inequalities that are more complicated than the MTZ and DL inequalities and that, in a certain way, “generalize” the underlying idea of the original inequalities. We present a polyhedral approach that studies and analyses the convex hull of feasible sets for small dimensions. This approach allows us to generate generalizations of the MTZ and DL inequalities, which are “good” in the sense that they define facets of these small polyhedra. It is well known that DL inequalities imply a subset of Dantzig–Fulkerson–Johnson (DFJ) SECs for two-node subsets. Through the approach presented, we describe a generalization of these inequalities which imply DFJ SECs for three-node subsets and show that generalizations for larger subsets are unlikely to exist. Our study presents a similar analysis with generalizations of MTZ inequalities and their relation with the lifted circuit inequalities for three node subsets.     

A note on the existence of multiple solutions for a class of systems of second order ODEs

We prove the existence of multiple solutions for some systems of second order ODEs with Dirichlet boundary conditions. Such systems are obtained by coupling scalar ODEs with different growth conditions. The proof relies on a global continuation technique.     

A binary algorithm with low divergence for modular inversion on SIMD architectures

When performing modular arithmetic the most computationally expensive operation is the modular inversion of an integer. Its cost might be a problem for cryptanalytical applications (like the transformation from projective to affine coordinates within a Pollard rho algorithm implementation to solve the discrete logarithm problem on an elliptic curve) where performances constitute a key aspect. Good platforms for such operations are single-instruction multiple-data architectures, like graphic processing units (GPUs) because of their extremely competitive performance/price ratio. Unfortunately, when a single thread computes a single inversion, the whole computation on GPUs can be significantly slowed down in the presence of divergent threads. In this paper we describe a new algorithm to compute modular inversion on GPUs based on Stein’s Binary GCD. By exploiting the De Bruijn sequences and the Montgomery arithmetic, our version of Stein’s algorithm better fits GPUs, since it reduces the divergence among threads of the original algorithm. The paper includes a brief report on tests of our algorithm in six prime fields with characteristics of size ranging from 109 to 359 bits and in the two prime fields associated to the Mersenne primes \(2^{521} - 1\) and \(2^{607} - 1\).     

Bounds for Maximal Functions Associated with Rotational Invariant Measures in High Dimensions

In recent articles (A. Criado in Proc. R. Soc. Edinb. Sect. A 140(3):541–552, 2010; Aldaz and Pérez Lázaro in Positivity 15:199–213, 2011) it was proved that when μ is a finite, radial measure in ? ⁿ with a bounded, radially decreasing density, the L ^p (μ) norm of the associated maximal operator M _μ grows to infinity with the dimension for a small range of values of p near 1. We prove that when μ is Lebesgue measure restricted to the unit ball and p<2, the L ^p operator norms of the maximal operator are unbounded in dimension, even when the action is restricted to radially decreasing functions. In spite of this, this maximal operator admits dimension-free L ^p bounds for every p>2, when restricted to radially decreasing functions. On the other hand, when μ is the Gaussian measure, the L ^p operator norms of the maximal operator grow to infinity with the dimension for any finite p>1, even in the subspace of radially decreasing functions.     

Extremal problems involving isotropic sets and functions on spaces of rectangular matrices

Let \(\mathbb{M}_{m,n}\) be the linear space of real matrices of dimension m × n. A variational problem that arises quite often in applications is that of minimizing a real-valued function f on some feasible set \(\Upomega\subseteq \mathbb{M}_{m,n}.\) Matrix optimization problems of such a degree of generality are not always easy to deal with, especially if the decision variable is a high-dimensional rectangular matrix. Sometimes, it is possible to reduce the size and complexity of the matrix optimization problem in the presence of symmetry assumptions (isotropy, orthogonal invariance, etc.). This work establishes a localization result for the solutions to a class of extremal problems involving isotropic sets and functions.     

Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic

Metaheuristics represent an important class of techniques to solve, approximately, hard combinatorial optimization problems for which the use of exact methods is impractical. Some researches have been combining machine learning techniques with metaheuristics to adaptively guide and improve the search for near optimal solutions. An example of such development is the DM-GRASP, a hybrid version of the Greedy Randomized Adaptative Search Procedures (GRASP) metaheuristic which incorporates a data mining process. In this hybrid proposal, after executing half of the total number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following half GRASP iterations in the search through the solution space. In this work, we explore new versions of the DM-GRASP metaheuristic to experiment, not a single activation, but multiple and adaptive executions of the data mining process during the metaheuristic execution. We also applied the data mining technique into a reactive GRASP to show that a more sophisticated and not memoryless GRASP approach can also benefit from the use of this technique. In order to evaluate these new proposals, we adopted the server replication for reliable multicast problem since the best known results for this problem were obtained by GRASP and DM-GRASP implementations. The computational experiments, comparing traditional GRASP, DM-GRASP, and the new proposals, showed that multiple and adaptive executions of the data mining process can improve the results obtained by the DM-GRASP hybrid metaheuristic—the new proposals were able to find better results in less computational time for the reliable multicast problem.     

A Class of {n}-Entire Schrödinger operators

We study singular Schrödinger operators on a finite interval as selfadjoint extensions of a symmetric operator. We give sufficient conditions for the symmetric operator to be in the \(n\) -entire class, which was defined in our previous work (Silva and Toloza in J Phys A Math Theor 46:025202, 2013) for some \(n\) . As a consequence of this classification, we obtain a detailed spectral characterization for a wide class of radial Schrödinger operators. The results given here make use of de Branges Hilbert space techniques.     

A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows

The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongoing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.     

An essential tension in mathematics education

There is a problem that goes through the history of calculus: the tension between the intuitive and the formal. Calculus continues to be taught as if it were natural to introduce the study of change and accumulation by means of the formalized ideas and concepts known as the mathematics of ε and δ. It is frequently considered as a failure that “students still seem to conceptualize limits via the imagination of motion.” These kinds of assertions show the tension, the rift created by traditional education between students’ intuitions and a misdirected formalization. In fact, I believe that the internal connections of the intuition of change and accumulation are not correctly translated into that arithmetical approach of ε and δ. There are other routes to formalization which cohere with these intuitions, and those are the ones discussed in this paper. My departing point is epistemic and once this discussion is put forward, I produce a narrative of classroom work, giving a special place to local conceptual organizations.