A primal simplex approach to a special class of generalized networks

Abstract

The objective of this thesis is to modify a network specialization of the simplex algorithm to fit the network structure of a special class of engineering project allocation problems. Simply, this kind of problem can be defined as that of selecting one option, either in-house engineers or private contractors, for each project in order to maximize benefits without exceeding available funds and manpower. Although the solution of the problem requires binary flows, which are usually obtained by a branch and bound methodology, this thesis focuses only on the linear programming relaxation of the problem. The modified network simplex algorithm selects a more efficient initial basis to significantly reduce computational time before identifying an optimal solution. This conclusion is based on a comparison from the modified and general algorithms for a collection of sixteen problems having from 5 to 315 projects each.