Much of the nation's production process reflects the application of tools developed from optimization concepts and related theories from economics. One of the most useful of these tools is the simplex method for solving linear programming problems. Linear programming is concerned with the maximization of output subject to constraints on the availability of factors of production. The simplex method can be interpreted as a decentralized search for prices which equilibrate the demand for factors of production with their supply. This project is concerned with solving maximization problems when the production set involves indivisibilities. Indivisibilities are introduced into a linear problem by requiring that some, or all of the activity levels take on integral values, rather than arbitrary real values. This field of research is called integer programming. In contrast to the simplex method, which performs remarkably well on all linear programming problems, existing integer programming algorithms are capricious, unreliable and none of these algorithms are capable of being interpreted in any meaningful economic terms. Under his previous grant the investigator found a new method for solving integer programming problems that could be a major breakthrough in this extremely difficult line of research. He proved that a globally intractable integer programming problem can be reduced to a small number of tractable, local integer programming problems that eventually converge to the global solution. The sequence of programming problems is a decision tree in which the number of branches (the number of possible local linear programs) at each step in the process is a small and declining fraction of the size of the problem. The project examines methods for determining these decision trees explicitly, explores their economic interpretation, and studies how well these algorithms work in practice. Most real world problems in such fields as operations research, economics and industrial planning involve indivisibilities, so a new set of powerful mathematical tools to solve these problems would be extremely valuable.
