%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@archivingpolicy denypublisher denyfinaldraft36
%@issn 0305-0548
%@resumeid 8JMKD3MGP5W/3C9JHMQ
%@usergroup administrator
%3 lorena.pdf
%B Computers and Operations Research
%@dissemination WEBSCI; PORTALCAPES.
%X 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 São José dos Campos’ city.
%8 May
%N 6
%T A column generation approach to capacitated p-median problems
%K COMPUTER SCIENCE, Capacitated p-median problems, Columns, Lagrangian function, Relaxation method (mathematics), Median (statistics), COMPUTAÇÃO APLICADA, Problemas de capacitação da p-mediana, Colunas, Função lagrangeana, Método de relaxação (matemática), Mediana (estatística).
%@secondarytype PRE PI
%@group LAC-INPE-MCT-BR
%@copyholder SID/SCD
%@secondarykey INPE-10796-PRE/6252
%2 sid.inpe.br/marciana/2004/01.19.11.14.21
%@affiliation Instituto Nacional de Pesquisas Espaciais, Laboratório Associado Computação e Matemática  Aplicada (INPE.LAC),
%@affiliation Universidade Estadual Paulista, Faculdade Engenharia, Departamento de Matemática (UNESP.FEG),
%@project Otimização combinatória
%@language English
%P 863-876
%4 sid.inpe.br/marciana/2004/01.19.11.14
%D 2004
%V 31
%A Lorena, Luiz Antonio Nogueira,
%A Senne, Edson Luiz França,
%@ 0305-0548
%@area COMP