A new formulation for the Traveling Deliveryman Problem

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonia...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Méndez Díaz, Isabel, Zabala, Paula
Publicado:	2008
Materias:	Branch-and-cut algorithms Integer programming Traveling deliveryman problem Dynamic programming Hamiltonians Linearization Meats Particle size analysis Branch-and-Bound Computational results Convex hulls Cutting plane algorithms Enumeration trees Feasible solutions Hamiltonian path problems Hamiltonian paths Integer programming formulations Linear programming relaxations Minimum costs Valid inequalities Linear programming
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n17_p3223_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n17_p3223_MendezDiaz
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0166218X_v156_n17_p3223_MendezDiaz
record_format	dspace
spelling	paper:paper_0166218X_v156_n17_p3223_MendezDiaz2023-06-08T15:15:27Z A new formulation for the Traveling Deliveryman Problem Méndez Díaz, Isabel Zabala, Paula Branch-and-cut algorithms Integer programming Traveling deliveryman problem Dynamic programming Hamiltonians Integer programming Linearization Meats Particle size analysis Branch-and-Bound Branch-and-cut algorithms Computational results Convex hulls Cutting plane algorithms Enumeration trees Feasible solutions Hamiltonian path problems Hamiltonian paths Integer programming formulations Linear programming relaxations Minimum costs Traveling deliveryman problem Valid inequalities Linear programming The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree. © 2008 Elsevier B.V. All rights reserved. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Zabala, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n17_p3223_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n17_p3223_MendezDiaz
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Branch-and-cut algorithms Integer programming Traveling deliveryman problem Dynamic programming Hamiltonians Integer programming Linearization Meats Particle size analysis Branch-and-Bound Branch-and-cut algorithms Computational results Convex hulls Cutting plane algorithms Enumeration trees Feasible solutions Hamiltonian path problems Hamiltonian paths Integer programming formulations Linear programming relaxations Minimum costs Traveling deliveryman problem Valid inequalities Linear programming
spellingShingle	Branch-and-cut algorithms Integer programming Traveling deliveryman problem Dynamic programming Hamiltonians Integer programming Linearization Meats Particle size analysis Branch-and-Bound Branch-and-cut algorithms Computational results Convex hulls Cutting plane algorithms Enumeration trees Feasible solutions Hamiltonian path problems Hamiltonian paths Integer programming formulations Linear programming relaxations Minimum costs Traveling deliveryman problem Valid inequalities Linear programming Méndez Díaz, Isabel Zabala, Paula A new formulation for the Traveling Deliveryman Problem
topic_facet	Branch-and-cut algorithms Integer programming Traveling deliveryman problem Dynamic programming Hamiltonians Integer programming Linearization Meats Particle size analysis Branch-and-Bound Branch-and-cut algorithms Computational results Convex hulls Cutting plane algorithms Enumeration trees Feasible solutions Hamiltonian path problems Hamiltonian paths Integer programming formulations Linear programming relaxations Minimum costs Traveling deliveryman problem Valid inequalities Linear programming
description	The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree. © 2008 Elsevier B.V. All rights reserved.
author	Méndez Díaz, Isabel Zabala, Paula
author_facet	Méndez Díaz, Isabel Zabala, Paula
author_sort	Méndez Díaz, Isabel
title	A new formulation for the Traveling Deliveryman Problem
title_short	A new formulation for the Traveling Deliveryman Problem
title_full	A new formulation for the Traveling Deliveryman Problem
title_fullStr	A new formulation for the Traveling Deliveryman Problem
title_full_unstemmed	A new formulation for the Traveling Deliveryman Problem
title_sort	new formulation for the traveling deliveryman problem
publishDate	2008
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n17_p3223_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n17_p3223_MendezDiaz
work_keys_str_mv	AT mendezdiazisabel anewformulationforthetravelingdeliverymanproblem AT zabalapaula anewformulationforthetravelingdeliverymanproblem AT mendezdiazisabel newformulationforthetravelingdeliverymanproblem AT zabalapaula newformulationforthetravelingdeliverymanproblem
_version_	1768545922114912256

A new formulation for the Traveling Deliveryman Problem

Ejemplares similares