A note on the divergence of geodesic rays in manifolds without conjugate points

Let (M, g) be a compact Riemannian manifold without conjugate points and let be its universal covering endowed with the pullback of the metric g by the covering map. We show that geodesic rays in which meet an axis of a covering isometry diverge from this axis. This result generalizes well known results by Morse and Hedlund in the context of globally minimizing geodesics in the universal covering of compact surfaces.      

A finite element approach to the position problems in open-loop variable geometry trusses

The present paper looks at some kinematic and static-equilibrium problems that arise with variable-geometry trusses (VGTs). The first part of the paper looks at the use of active controls in the correction of static deformations, the second part at the position problems. The separation between deformable- and rigid-body displacements makes it possible to consider separately the corrections in each component of the structure. VGTs are considered as open-loop linkages with redundant rigid-body degrees of freedom. Owing to this redundancy, possible solutions to the inverse problem are in general infinite, for which reason it is necessary to use some optimization criteria. To tackle the problem an optimization procedure with constraints is developed for the purpose of minimizing the displacements of the actuators. Suitable use of the constraints allows us to solve the direct position problem using the same optimization procedure.     

Efficient elementary and restricted non-elementary route pricing

Column generation is involved in the current most efficient approaches to routing problems. Set partitioning formulations model routing problems by considering all possible routes and selecting a subset that visits all customers. These formulations often produce tight lower bounds and require column generation for their pricing step. The bounds in the resulting branch-and-price are tighter when elementary routes are considered, but this approach leads to a more difficult pricing problem. Balancing the pricing with route relaxations has become crucial for the efficiency of the branch-and-price for routing problems. Recently, the ng-routes relaxation was proposed as a compromise between elementary and non-elementary routes. The ng-routes are non-elementary routes with the restriction that when following a customer, the route is not allowed to visit another customer that was visited before if they belong to a dynamically computed set. The larger the size of these sets, the closer the ng-route is to an elementary route. This work presents an efficient pricing algorithm for ng-routes and extends this algorithm for elementary routes. Therefore, we address the Shortest Path Problem with Resource Constraint (SPPRC) and the Elementary Shortest Path Problem with Resource Constraint (ESPPRC). The proposed algorithm combines the Decremental State-Space Relaxation technique (DSSR) with completion bounds. We apply this algorithm for the Generalized Vehicle Routing Problem (GVRP) and for the Capacitated Vehicle Routing Problem (CVRP), demonstrating that it is able to price elementary routes for instances up to 200 customers, a result that doubles the size of the ESPPRC instances solved to date.     

Pareto Optimal Allocation and Price Equilibrium for a Duopoly with Negative Externality

A spatial competition model involving decisions made by consumers and firms is proposed. A regulating agent assigns the demand, taking into account the price, transport and externality cost, and minimizing the joint consumer cost to obtain a Pareto optimal allocation. Assuming the Pareto optimal allocation, firms fix prices in order to maximize the profit. An equilibrium problem is studied and some results are presented. The problem and results are illustrated with an example.     

Approximating Unknown Mappings: An Experimental Evaluation

Different methodologies have been introduced in recent years with the aim of approximating unknown functions. Basically, these methodologies are general frameworks for representing non-linear mappings from several input variables to several output variables. Research into this problem occurs in applied mathematics (multivariate function approximation), statistics (nonparametric multiple regression) and computer science (neural networks). However, since these methodologies have been proposed in different fields, most of the previous papers treat them in isolation, ignoring contributions in the other areas. In this paper we consider five well known approaches for function approximation. Specifically we target polynomial approximation, general additive models (Gam), local regression (Loess), multivariate additive regression splines (Mars) and artificial neural networks (Ann).Neural networks can be viewed as models of real systems, built by tuning parameters known as weights. In training the net, the problem is to find the weights that optimize its performance (i.e. to minimize the error over the training set). Although the most popular method for Ann training is back propagation, other optimization methods based on metaheuristics have recently been adapted to this problem, outperforming classical approaches. In this paper we propose a short term memory tabu search method, coupled with path relinking and BFGS (a gradient-based local NLP solver) to provide high quality solutions to this problem. The experimentation with 15 functions previously reported shows that a feed-forward neural network with one hidden layer, trained with our procedure, can compete with the best-known approximating methods. The experimental results also show the effectiveness of a new mechanism to avoid overfitting in neural network training.     

Scatter search for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this problem, such as Simulated Annealing and Evolutionary Path Relinking.     

Multi-service multi-facility network design under uncertainty

The problem of designing high speed networks using different modules of link capacities, in the same model, in order to meet uncertain demands obtained from different probability distribution functions (PDF) is a very hard and challenging real network design problem. The novelty of the new model, compared to previous ones, is to allow installing more than one module per link having equal or different capacities. Moreover, the scenarios of traffic can be generated, according to practical observations, from the main classes of uncertain demands (multi-service) simulated from different PDFs, including heavy tailed ones. These classes of traffic are considered simultaneously for the scenario generation, different from related works in the literature that use only one probability distribution function to simulate the scenarios of traffic. In this work we present the problem formulation and report computational results using branch-and-bound and L-shaped decomposition solution approaches. We consider in the same model up to three different types of modular capacities (multi-facility), since it seems that using more than this can lead to an intractable model. The objective is to minimize penalty (in case of unmet demands) and investment costs. We obtain confidence intervals (with 95% of covering rate) on the expected optimal solution value for the resulting two-stage stochastic integer-modular problem and discuss when they are meaningful. Numerical experiments show that our model can handle up to medium real size instances.