Traditional optimization approaches are no longer effective in solving practical, large scale, complex problems from many application domains. Typical applications require a sophisticated coupling of a number of optimization and complementarity modeling approaches with specific domain knowledge and expertize to generate solutions in a timely and robust manner. This project will develop tools and algorithms that help in solving coordinated problems of this nature by formulating and exploring the notion of an extended mathematical program (EMP). This provides the ability to model competition between agents using the notion of an embedded model, a feature that is missing from other optimization approaches. Specific instances include dynamic games that are used to analyze interactions between agents in multiple fields, including industrial organization, labor and financial bargaining and contracts, government design of fiscal and monetary policies, auction design, political decision-making and international conflict resolution. The major benefits are threefold: EMP will make the modelers task easier, in that the model can be described more naturally and at a higher conceptual level; the actual model to be solved can be reliably and efficiently generated; an algorithm can exploit additional structure in an effective computational manner. Building on earlier work, this project will develop theory-based, efficient, fast, reliable, user-friendly numerical methods to solve extended mathematical programs.
If successful, this project will develop a general modeling framework, applicable to a wide range of real problems and will produce a coherent and comprehensive suite of tools for modeling and computation that can be applied to systems in many application areas. It is anticipated that further significant advancements in operations research applications can be achieved via identification of specific problem structures within a given model, a notion that forms the core of an EMP. Difficulties associated with multiplicity of equilibria and the large dimension of the underlying problems will be addressed by communicating structure to solvers and developing new algorithms that explicitly utilize that structure for more robust solution. The project aims to demonstrate that the availability of such structure fosters the generation of new features to existing solvers and drives the development of new classes of algorithms. The algorithms and methods that will be implemented here will be made available to the whole user community via modeling system hookups to GAMS, AMPL and MATLAB, and via broad dissemination via the internet using resources such as the NEOS server and the COIN-OR project.
