Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



On a Traveling Salesman based Bilevel Programming Problem
Indexado
WoS WOS:000413254200035
Scopus SCOPUS_ID:85049232392
DOI 10.5220/0006190503290336
Año 2017
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



In this paper, we consider a linear bilevel programming problem where both the leader and the follower maximize their profits subject to budget constraints. Additionally, we impose a Hamiltonian cycle topology constraint in the leader problem. In particular, models of this type can be motivated by telecommunication companies when dealing with traffic network flows from one server to another one within a ring topology framework. We transform the bilevel programming problem into an equivalent single level optimization problem that we further linearize in order to derive mixed integer linear programming (MILP) formulations. This is achieved by replacing the follower problem with the equivalent Karush Kuhn Tucker conditions and with a linearization approach to deal with the complementarity constraints. The topology constraint is handled by the means of two compact formulations and an exponential one from the classic traveling salesman problem. Thus, we compute optimal solutions and upper bounds with linear programs. One of the compact models allows to solve instances with up to 250 nodes to optimality. Finally, we propose an iterative procedure that allows to compute optimal solutions in remarkably less computational effort when compared to the compact models.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 ADASME-SOTO, PABLO ALBERTO Hombre Universidad de Santiago de Chile - Chile
2 Andrade, Rafael Hombre Univ Fed Ceara - Brasil
Universidade Federal do Ceará - Brasil
3 Leung, Janny Mujer Chinese Univ Hong Kong - China
Chinese University of Hong Kong - Hong Kong
Chinese University of Hong Kong - China
4 Lisser, Abdel Hombre Univ Paris Sud 11 - Francia
Laboratoire de Recherche en Informatique - Francia
Universite Paris-Saclay - Francia
5 Liberatore, F -
6 Parlier, GH -
7 Demange, M -

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
Departamento de Investigaciones Científicas y Tecnológicas, Universidad de Santiago de Chile
USACH/DICYT
USACH/DICYT Project

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
The first author acknowledges the financial support of the USACH/DICYT Project 061513VC_DAS.
The first author acknowledges the financial support of the USACH/DICYT Project 061513VC_DAS.

Muestra la fuente de financiamiento declarada en la publicación.