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 allocation--for 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 decision-makers 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 algorithms--variations 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 production-scheduling 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 special-purpose 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 large-scale, specially-structured, hard combinatorial-optimization problems. An earlier project investigated the use of heuristic techniques in the efficient sequencing of x-ray diffraction readings in crystallographic experiments. More recent efforts included service projects involving vehicle routing for a local non-profit, and examination scheduling at Cornell.

Back to Cornell ORIE