A branch-and-price approach to p-median location problems

This paper describes a branch-and-price algorithm for the p-median location problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand point to its nearest facility is minimized. The traditional column generation process is compared with a stabilized approach that combines the column generation and Lagrangean/surrogate relaxation. The Lagrangean/surrogate multiplier modifies; the reduced cost criterion, providing the selection of new productive columns at the search tree. Computational experiments are conducted considering especially difficult instances to the traditional column generation and also with some large-scale instances. (C) 2004 Elsevier Ltd. All rights reserved.

Spinning Hopf solitons on S-3 x R

We consider a field theory with target space being the two dimensional sphere S-2 and defined on the space-time S-3 x R. The Lagrangean is the square of the pull-back of the area form on S-2. It is invariant under the conformal group SO(4, 2) and the infinite dimensional group of area preserving diffeomorphisms of S-2. We construct an infinite number of exact soliton solutions with non-trivial Hopf topological charges. The solutions spin with a frequency which is bounded above by a quantity proportional to the inverse of the radius of S-3. The construction of the solutions is made possible by an ansatz which explores the conformal symmetry and a U(1) subgroup of the area preserving diffeomorphism group.

Abordagens complementares para problemas de p-medianas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Métodos de geração de colunas para problemas de atribuição

Este trabalho apresenta métodos de geração de colunas para dois importantes problemas de atribuição: o Problema Generalizado de Atribuição (PGA) e o Problema de Atribuição de Antenas a Comutadores (PAAC). O PGA é um dos mais representativos problemas de Otimização Combinatória e consiste em otimizar a atribuição de n tarefas a m agentes, de forma que cada tarefa seja atribuída a exatamente um agente e a capacidade de cada agente seja respeitada. O PAAC consiste em atribuir n antenas a m comutadores em uma rede de telefonia celular, de forma a minimizar os custos de cabeamento entre antenas e comutadores e os custos de transferência de chamadas entre comutadores. A abordagem tradicional de geração de colunas é comparada com as propostas neste trabalho, que utilizam a relaxação lagrangeana/surrogate. São apresentados testes computacionais que demonstram a efetividade dos algoritmos propostos.

Integração de modelos de localização a sistemas de informações geográficas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A column generation approach to capacitated p-median problems

The Capacitated p-median problem (CPMP) seeks to solve the optimal location of p facilities, considering distances and capacities for the service to be given by each median. In this paper we present a column generation approach to CPMP. The identified restricted master problem optimizes the covering of 1-median clusters satisfying the capacity constraints, and new columns are generated considering knapsack subproblems. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. In this work the Lagrangean/surrogate relaxation is directly identified from the master problem dual and provides new bounds and new productive columns through a modified knapsack subproblem. The overall column generation process is accelerated, even when multiple pricing is observed. Computational tests are presented using instances taken from real data from Sao Jose dos Campos' city.

Integrability and conformal symmetry in higher dimensions: A model with exact hopfion solutions

We use ideas on integrability in higher dimensions to define Lorentz invariant field theories with an infinite number of local conserved currents. The models considered have a two-dimensional target space. Requiring the existence of lagrangean and the stability of static solutions singles out a class of models which have an additional conformal symmetry. That is used to explain the existence of an ansatz leading to solutions with non-trivial Hopf charges. © SISSA/ISAS 2002.

Spinning Hopf solitons on S3 × ℝ

We consider a field theory with target space being the two dimensional sphere S2 and defined on the space-time S3 × . The Lagrangean is the square of the pull-back of the area form on S2. It is invariant under the conformal group SO(4,2) and the infinite dimensional group of area preserving diffeomorphisms of S2. We construct an infinite number of exact soliton solutions with non-trivial Hopf topological charges. The solutions spin with a frequency which is bounded above by a quantity proportional to the inverse of the radius of S3. The construction of the solutions is made possible by an ansatz which explores the conformal symmetry and a U(1) subgroup of the area preserving diffeomorphism group. © SISSA 2006.

A decomposition heuristic for the maximal covering location problem

This paper proposes a cluster partitioning technique to calculate improved upper bounds to the optimal solution of maximal covering location problems. Given a covering distance, a graph is built considering as vertices the potential facility locations, and with an edge connecting each pair of facilities that attend a same client. Coupling constraints, corresponding to some edges of this graph, are identified and relaxed in the Lagrangean way, resulting in disconnected subgraphs representing smaller subproblems that are computationally easier to solve by exact methods. The proposed technique is compared to the classical approach, using real data and instances from the available literature. © 2010 Edson Luiz França Senne et al.

Métodos analíticos, numéricos e experimentais para o cálculo de ondas de impacto em meios líquidos

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Aspectos Clássicos da Eletrodinâmica de Podolsky

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Nonlinear ball and beam control system identification

The Ball and Beam system is a common didactical experiment in control laboratories that can be used to illustrate many different closed-loop control techniques. The plant itself is subjected to many nonlinear effects, which the most common comes from the relative motion between the ball and the beam. The modeling process normally uses the lagrangean formulation. However, many other nonlinear effects, such as non-viscous friction, beam flexibility, ball slip, actuator elasticity, collisions at the end of the beam, to name a few, are present. Besides that, the system is naturally unstable. In this work, we analyze a subset of these characteristics, in which the ball rolls with slipping and the friction force between the ball and the beam is non-viscous (Coulomb friction). Also, we consider collisions at the ends of the beam, the actuator consists of a (rubber made) belt attached at the free ends of the beam and connected to a DC motor. The model becomes, with those nonlinearities, a differential inclusion system. The elastic coefficients of the belt are experimentally identified, as well as the collision coefficients. The nonlinear behavior of the system is studied and a control strategy is proposed.

Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Construção exata de sólitons de Hopf

Pós-graduação em Física - IFT