While operations research (OR) is practiced throughout IBM, the Research Division is a focal point for activities in both science and applications. IBM researchers have produced groundbreaking work in many areas of OR, including integer programming (Ralph Gomory and Ellis Johnson), decomposition methods (Phil Wolfe), as well as graph theory and linear programming (Alan Hoffman). We continue to build upon this tradition, by conducting research and developing tools in both the theory and the application of OR.

Our research in algorithm development focuses on three main topics: high-performance computational kernels consisting of basic scientific algorithmic building blocks; optimization algorithms and software for solving linear, integer, and nonlinear programming problems; and direct solution of sparse linear systems. We have developed a number of software products, including IBM OSL (Optimization Solutions and Library), the first commercial solver for workstations and PC platforms and the first optimization engine offering a stochastic solver, and the Watson Symmetric Sparse Matrix Package, a high-performance, robust software package.

We have used OR to develop solutions to industry problems. For example, in the manufacturing sector, we have developed integrated optimized solutions to interrelated combinatorial problems, including inventory management, product design, and production scheduling for leading steel manufacturers in Japan. These solutions resulted in significant savings, partly attributable to reduced production costs and lead time. As another example, Watson Implosion Technology (WIT) is a software solution that aids in constrained materials management and production planning. Once WIT is given a list of demands for products, supplies for product components, and a multilevel bill of manufacturing (BOM), WIT "implodes" the components supplies, via the BOM, into feasible shipments of products. Trade-offs are made to best satisfy manufacturing objectives, given limited supplies. WIT is used inside IBM and at customer locations worldwide.

Research in airline optimization includes yield management, crew scheduling, and service management. Our Crew Pairing Optimization System (CPOS) minimizes the cost of assigning crews to flights, while complying with FAA and company regulations. The CPOS effort led to the development of the Sprint method for pairing selection - now the industry standard - and a new, patented, subgradient method for fast approximate solutions. CPOS has been used by national and international airlines, resulting in millions of dollars of savings for these companies.

We are investigating methods to manage risk faced by nonfinancial enterprises, by combining financial risk-management techniques with traditional planning strategies. We have applied this research in such areas as supply chain and e-business management. For example, we have developed a suite of capacity planning tools, based upon stochastic optimization techniques, used by semiconductor tool planners. The tools in the suite optimally allocate investment budgets for tool purchasing plans in order to minimize the risk of unmet demand.

We are developing both theory and software to support e-commerce. Our Trust Establishment software incorporates a new approach for mapping strangers to predefined business roles, so that parties can confidently conduct e-business. In the business-to-business area, we have created a decision-support library; built upon OSL, for winner determination in combinatorial auctions and volume discount auctions. We are also exploring design of Internet auctions.

Common Optimization Interface for Operations Research (COIN-OR) is an IBM Research initiative to spur the development of open-source software for the OR community. The goal is to develop high-quality, high-performance, secure open code. Open-source code enables OR professionals to reuse software ideas and implement improvements more quickly. COIN-OR is a community initiative, and participation at all levels is welcome. For more on COIN-OR, visit www.coin-or.org.

Please contact Paridhi Verma to obtain copies of the Computer Science Brochure