Show simple item record

dc.contributor.advisorUster, Halit
dc.contributor.advisorMoreno-Centeno, Erick
dc.creatorMarzouk, Ahmed Mohamed Badr Aly
dc.date.accessioned2017-02-02T16:23:39Z
dc.date.available2018-12-01T07:20:25Z
dc.date.created2016-12
dc.date.issued2016-10-06
dc.date.submittedDecember 2016
dc.identifier.urihttps://hdl.handle.net/1969.1/158668
dc.description.abstractThe main objective of this dissertation is to present a new exact optimization method, the Slim Branch and Price (SBP) method, which is an improvement over the traditional Branch and Price (B&P) framework. SBP can be used to solve a large class of combinatorial optimization problems that can be solved by B&P type algorithms and that have binary master problems with fixed support (i.e., the sum of the variables in any feasible solution is fixed). This is an important class of problems as it includes several classical and fundamental problems. Towards this objective, this dissertation develops three algorithms to solve an interesting optimization problem, the Hamiltonian p-median problem (HpMP), which is a generalization of the wellknown traveling salesman problem. In HpMP, the target is to find p cycles that partition a given undirected graph with the objective of minimizing the total sum of the costs of these p cycles. This dissertation is divided into three main parts with the objective of showing the superiority of SBP over B&P while using HpMP as a running example. Towards this objective, the first part presents a B&P algorithm for HpMP, the second part presents SBP and how it can be tailored to solve HpMP, and finally, the third part explains how the preprocessing techniques developed for integer programs can dramatically enhance the performance of SBP. In the first part, we devise a Branch and Price algorithm that is able to solve instances with up to 318 nodes (within acceptable optimality gaps). To achieve this, we modified the set partitioning formulation of HpMP|a minor modification yet with significant algorithmic and computational advantages. Furthermore our computational results demonstrate that the practical complexity of HpMP and the performance of the algorithms to solve it strongly depend on the value of p. In addition, in order to solve the pricing problem we make contributions on a couple of problems that are important on their own right: 1) we develop a new efficient algorithm to find the least cost cycle in undirected graphs with arbitrary edge costs and no negative cycles; and 2) we develop an algorithm to find the most negative cycle in undirected graphs with arbitrary edge costs. Finally, we prove that for every value of p, HpMP is NP-hard even when restricted to Euclidean graphs. In the second part, we present SBP method which is an improvement over traditional B&P in the case of binary master problems with fixed support. The main advantage in SBP is that the branching tree has only one main branch with several leaves. In addition, we show that all the problems defined on the leaves can be merged to form a larger problem that can be solved very fast without further branching. We illustrate the computational advantage of SBP over B&P on HpMP. In particular, within one hour time limit, SBP can solve to optimality instances with up to 200 nodes; whereas B&P can solve to optimality instances with up to 127 nodes. In the third part, we exploit the reduced cost fixing preprocessing technique to enhance the performance of B&P. To this end, we develop a heuristic based on k-opt moves to find good feasible solutions for HpMP. We also introduce two separation algorithms to improve the linear programming relaxation of the natural variable space model of HpMP. Using these upper and lower bounds, reduced cost fixing was then implemented to reduce the graph size by deleting the edges that cannot be in any optimal solution. We compared the computational times reported by SBP with preprocessing versus those reported by SBP without preprocessing. The former algorithm performed better than the latter algorithm in 88.3% of the test instances.en
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.subjectSlim Branch and Priceen
dc.subjectBranch and Priceen
dc.subjectinteger programmingen
dc.subjectcombinatorial optimizationen
dc.subjectHamiltonian p-median Problemen
dc.titleThe Slim Branch and Price Method with an Application to the Hamiltonian p-median Problemen
dc.typeThesisen
thesis.degree.departmentIndustrial and Systems Engineeringen
thesis.degree.disciplineIndustrial Engineeringen
thesis.degree.grantorTexas A & M Universityen
thesis.degree.nameDoctor of Philosophyen
thesis.degree.levelDoctoralen
dc.contributor.committeeMemberCetinkaya, Sila
dc.contributor.committeeMemberAmato, Nancy
dc.type.materialtexten
dc.date.updated2017-02-02T16:23:39Z
local.embargo.terms2018-12-01
local.etdauthor.orcid0000-0002-0725-4295


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record