Technical Note—A Vertex Ranking Procedure for Solving the Linear Fixed-Charge Problem

Abstract

Murty has suggested that the linear fixed-charge problem can be solved by ranking the vertices of the polyhedral constraint set according to their continuous objective values and then adding the fixed charges to determine an optimal solution. Several problems involving degeneracy and inequality constraints arise when one attempts to implement Murty's method directly. This note describes a method that uses the vertex ranking approach in conjunction with procedures that resolve these difficulties. We also give computational results.