INTEGER PROGRAMMING:SOME BIP APPLICATIONS

By -

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:

INTRODUCTION TO OPERATIONS RESEARCH-0094

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?

INTRODUCTION TO OPERATIONS RESEARCH-0095

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.

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more