Journal of the Operational Research Society

This paper describes a problem faced by the Public Transport Corporation (PTC) in the Australian State of Victoria. It involved the allocation of locomotives to the freight trains operated by the Corporation. Such a problem can be classified as a multi-class multi-locomotive problem since different types (or classes) of locomotive are available to pull the trains and some of the trains are heavy enough to require more than one locomotive. Because of the features of the services operated by the PTC, formulation of this problem as a pure integer program is straightforward, provided the objective function can be linearised. However, obtaining the optimal solution from this formulation is not. Large optimality gaps remained after various attempts to tighten the problem. Other authors have reported similar difficulties with similar problems. The original problem was therefore reformulated using special ordered covering sets of type 1. After reformulation, the optimal solution was obtained in less than a second of CPU time. This enabled alternative methods of linearising the objective function to be evaluated, resulting eventually in the decision to extend the concept of minimal covering sets so that each integer variable in the problem was expressed as a linear sum of a special ordered covering set of binary variables. In this way, the objective function was both exact and linear and the model, although much larger, still solved in under a second of CPU time. The methods of solution proposed in this paper should be capable of extension to more general resource allocation problems exhibiting similar features.

Two projected gradient algorithms for linear programming are discussed. The first uses a conventional enough steepest edge approach, and implements a version of Wolfe's method for resolving any problems of degeneracy. The second makes use of a steepest descent direction which is calculated by solving a linear least squares problem subject to bound constraints, and avoids problems of degeneracy altogether. They are compared using randomly generated problems which permit the specification of (known) degenerate minima. The results appear to favour the more conventional method as problem sizes get larger.

This note establishes a connection between two problems that appear in different contexts: the Product Rate Variation (PRV) problem (sequencing units in a mixed-model assembly line in order to maximize the regularity of the sequence with regard to the output of units) and the apportionment problem. This allows us to apply to the PRV problem the properties of the apportionment problem and known procedures for solving it, and suggests alternative approaches to the former problem.