INTEGER PROGRAMMING:SOME BIP APPLICATIONS

SOME BIP APPLICATIONS

Just as in the California Manufacturing Co. example, managers frequently must face yes- or-no decisions. Therefore, binary integer programming (BIP) is widely used to aid in these decisions.

We now will introduce various types of yes-or-no decisions. This section includes two application vignettes to help illustrate two of these types. For the other types, we also will mention some other examples of actual applications where BIP was used to address these decisions. All of these examples are included in the selected references of award- winning applications cited at the end of the chapter, so a link to these articles is provided on the book’s website.

Investment Analysis

Linear programming sometimes is used to make capital budgeting decisions about how much to invest in various projects. However, as the California Manufacturing Co. example demonstrates, some capital budgeting decisions do not involve how much to invest, but rather, whether to invest a fixed amount. Specifically, the four decisions in the example were whether to invest the fixed amount of capital required to build a certain kind of facility (factory or warehouse) in a certain location (Los Angeles or San Francisco).

Management often must face decisions about whether to make fixed investments (those where the amount of capital required has been fixed in advance). Should we ac- quire a certain subsidiary being spun off by another company? Should we purchase a certain source of raw materials? Should we add a new production line to produce a certain input item ourselves rather than continuing to obtain it from a supplier?

In general, capital budgeting decisions about fixed investments are yes-or-no decisions of the following type.

Each yes-or-no decision:

An example that falls somewhat into this category is described in Selected Refer- ence A6. A major OR study was conducted for the South African National Defense Force to upgrade its capabilities with a smaller budget. The “investments” under consideration in this case were acquisition costs and ongoing expenses that would be required to pro- vide specific types of military capabilities. A mixed BIP model was formulated to choose those specific capabilities that would maximize the overall effectiveness of the Defense Force while satisfying a budget constraint. The model had over 16,000 variables (in- cluding 256 binary variables) and over 5,000 functional constraints. The resulting opti- mization of the size and shape of the defense force provided savings of over $1.1 billion per year as well as vital nonmonetary benefits.

Selected Reference A2 presents another award-winning application of a mixed BIP model to investment analysis. This particular model has been used by the investment firm Grantham, Mayo, Van Otterloo and Company to construct many quantitatively managed portfolios representing over $8 billion in assets. In each case, a portfolio has been con- structed that is close (in terms of sector and security exposure) to a target portfolio but with a far smaller and more manageable number of distinct stocks. A binary variable is used to represent each yes-or-no decision as to whether a particular stock should be included in the portfolio and then a separate continuous variable represents the amount of the stock to include. Given a current portfolio that needs to be rebalanced, it is desirable to reduce trans- action costs by minimizing the number of transactions needed to obtain the final portfolio,

An Application Vignette

The Midwest Independent Transmission System Oper- ator, Inc. (MISO) is a nonprofit organization formed in 1998 to administer the generation and transmission of electricity throughout the midwestern United States. It serves over 40 million customers (both individuals and businesses) through its control of nearly 60,000 miles of high-voltage transmission lines and more than 1,000 power plants capable of generating 146,000 megawatts of electricity. This infrastructure spans 13 midwestern U.S. states plus the Canadian province of Manitoba.

The key mission of any regional transmission organization is to reliably and efficiently provide the electric- ity needed by its customers. MISO transformed the way this was done by using mixed binary integer programming to minimize the total cost of providing the needed electricity. Each main binary variable in the model represents a yes-or-no decision about whether a particular power plant should be on during a particular time period. After solving this model, the results are then fed into a

linear programming model to set electricity output levels and establish prices for electricity trades.

The mixed BIP model is a massive one with about 3,300,000 continuous variables, 450,000 binary variables, and 3,900,000 functional constraints. A special technique (Lagrangian relaxation) is used to solve such a huge model.

This innovative application of operations research yielded savings of approximately $2.5 billion over the four years from 2007 to 2010, with an additional savings of about $7 billion expected through 2020. These dramatic results led to MISO winning the prestigious First Prize in the 2011 international competition for the Franz Edelman Award for Achievement in Operations Research and the Management Sciences.

Source: B. Carlson and 12 co-authors, “MISO Unlocks Billions in Savings Through the Application of Operations Research for Energy and Ancillary Services Markets,” Interfaces, 42(1): 58–73, Jan.–Feb. 2012. (A link to this article is provided on our website, www.mhhe.com/hillier.)

so binary variables also are included to represent the yes-or-no decisions as to whether to make the transactions to change the amounts of individual stocks being held. The inclu- sion of this consideration in the model has reduced the annual cost of trading the portfo- lios being managed by at least $4 million.

Site Selection

In this global economy, many corporations are opening up new plants in various parts of the world to take advantage of lower labor costs, etc. Before selecting a site for a new plant, many potential sites may need to be analyzed and compared. (The California Manu- facturing Co. example had just two potential sites for each of two kinds of facilities.) Each of the potential sites involves a yes-or-no decision of the following type.

Each yes-or-no decision:

Should a certain site be selected for the location of a certain new facility?

In many cases, the objective is to select the sites so as to minimize the total cost of the new facilities that will provide the required output.

As described in Selected Reference A10, AT&T used a BIP model to help dozens of their customers select the sites for their telemarketing centers. The model minimizes labor, communications, and real estate costs while providing the desired level of coverage by the centers. In one year alone, this approach enabled 46 AT&T customers to make their yes- or-no decisions on site locations swiftly and confidently, while committing to $375 mil- lion in annual network services and $31 million in equipment sales from AT&T.

Selected Reference A5 describes how global papermaker Norske Skog used a similar model, but this time for selecting sites to close facilities rather than opening new ones. The company had been experiencing declining demand for its products as electronic me- dia replaced newsprint publications. Therefore, a large BIP model (312 binary variables, 47,000 continuous variables, and 2600 functional constraints) was used to select two paper mills and a paper machine to close, saving the company $100 million annually.

We next describe an important type of problem for many corporations where site se- lection plays a key role.