
Robert G. Bland: Research Interests Linear programming is concerned with certain kinds of problems related to the optimal allocation of scarce resources among competing, but otherwise independent, activities. It is applicable when the consumption of each resource is a linear function of the levels at which the activities are pursued, and the measure of goodness of an allocationfor example, cost (to be minimized) or profit (to be maximized)is also linear. For sixty years linear programming has been an extremely effective tool in widespread use by decisionmakers in business and government. In order to develop more efficient algorithms capable of broader applicability, it would be helpful to have a better understanding of linear programming problems. A principal focus of our work has been to provide a precise and concise description of the combinatorial structure underlying linear programming duality theory. This mathematical simplification of the usual vector space setting has revealed surprisingly simple variations on traditional algorithmsvariations that exhibit interesting theoretical properties and, sometimes, interesting computational properties. Related work concerns variations on linear programming. How can we best exploit special structure in linear programming problems? How can we cope with problems in which additional complicating conditions have been imposed on an otherwise easily tractable structure? For example, certain productionscheduling problems are complicated by the possibility that items loaded at different times may be scheduled to be simultaneously resident on a machine with fixed capacity. For a particular class of problems, we have shown that the capacity conditions can be incorporated in a surprisingly easy way into an alternative model that is solvable by specialpurpose techniques used in network flow theory. The main tool used here is geometric duality of planar graphs. We have also done extensive computational work on network flow codes, employing statistical methods to model how execution times respond to variations in input characteristics. Other work involves the approximate solution of largescale, speciallystructured, hard combinatorialoptimization problems. An earlier project investigated the use of heuristic techniques in the efficient sequencing of xray diffraction readings in crystallographic experiments. More recent efforts included service projects involving vehicle routing for a local nonprofit, and examination scheduling at Cornell.
