In this section, we demonstrate how 0–1 decision variables can be used to model several diverse situations. Typically, a 0–1 decision variable is assigned a value of 0 if a certain condition is not met and 1 if the condition is met. Another name for a 0–1 decision variable is a binary variable. A common problem of this type, the assignment problem, involves deciding which individuals to assign to a set of jobs. (This is discussed in Chapter 9.) In this assignment problem, a value of 1 indicates a person is assigned to a specific job, and a value of 0 indicates the assignment was not made. We present other types of 0–1 problems to show the wide applicability of this modeling technique.
A common capital budgeting decision involves selecting from a set of possible projects when budget limitations make it impossible to select all of these. A separate 0–1 variable can be defined for each project. We will see this in the following example.
Quemo Chemical Company is considering three possible improvement projects for its plant: a new catalytic converter, a new software program for controlling operations, and an expansion of the warehouse used for storage. Capital requirements and budget limitations in the next 2 years prevent the firm from undertaking all of these at this time. The net present value (the future value discounted back to the present time) of each project, the capital requirements for each project, and the available funds for the next 2 years are given in Table 10.2.
PROJECT | NET PRESENT VALUE | YEAR 1 | YEAR 2 |
---|---|---|---|
Catalytic converter | $25,000 | $8,000 | $7,000 |
Software | $18,000 | $6,000 | $4,000 |
Warehouse expansion | $32,000 | $12,000 | $8,000 |
Available funds | $20,000 | $16,000 |
To formulate this as an integer programming problem, we identify the objective function and the constraints as follows:
We define the decision variables as
The mathematical statement of the integer programming problem becomes
Program 10.5 provides the Solver solution in Excel 2016. You specify the variables to be binary (0–1) by selecting bin from the Change Constraint window. The optimal solution is , with an objective function value of 57,000. This means that Quemo should fund the catalytic converter project and the warehouse expansion project but not the new software project. The net present value of these investments will be $57,000.
Solver Parameter Inputs and Selections | Key Formulas |
---|---|
Set Objective: E5 |
Copy E5 to E8:E9 |
By Changing cells: B4:D4 | |
To: Max | |
Subject to the Constraints: | |
E8:E9 <= G8:G9 | |
B4:D4 = binary | |
Solving Method: Simplex LP | |
☑ Make Variables Non-Negative |
One common use of 0–1 variables involves limiting the number of projects or items that are selected from a group. Suppose that in the Quemo Chemical Company example, the company is required to select no more than two of the three projects regardless of the funds available. This could be modeled by adding the following constraint to the problem:
If we wished to force the selection of exactly two of the three projects for funding, the following constraint should be used:
This forces exactly two of the variables to have values of 1, whereas the other variable must have a value of 0.
At times, the selection of one project depends in some way on the selection of another project. This situation can be modeled with the use of 0–1 variables. Now suppose in the Quemo Chemical problem that the new catalytic converter can be purchased only if the software is also purchased. The following constraint would force this to occur:
or, equivalently,
Thus, if the software is not purchased, the value of is 0, and the value of must also be 0 because of this constraint. However, if the software is purchased , then it is possible that the catalytic converter could also be purchased , although this is not required.
If we wished for the catalytic converter and the software projects to either both be selected or both not be selected, we should use the following constraint:
or, equivalently,
Thus, if either of these variables is equal to 0, the other must also be 0. If either of these is equal to 1, the other must also be 1.
Often businesses are faced with decisions involving a fixed charge that will affect the cost of future operations. Building a new factory or entering into a long-term lease on an existing facility would involve a fixed cost that might vary, depending on the size and the location of the facility. Once a factory is built, the variable production costs will be affected by the labor cost in the particular city where it is located. An example follows.
Sitka Manufacturing is planning to build at least one new plant, and three cities are being considered: Baytown, Texas; Lake Charles, Louisiana; and Mobile, Alabama. Once the plant or plants have been constructed, the company wishes to have sufficient capacity to produce at least 38,000 units each year. The costs associated with the possible locations are given in Table 10.3.
SITE | ANNUAL FIXED COST | VARIABLE COST PER UNIT | ANNUAL CAPACITY |
---|---|---|---|
Baytown, TX | $340,000 | $32 | 21,000 |
Lake Charles, LA | $270,000 | $33 | 20,000 |
Mobile, AL | $290,000 | $30 | 19,000 |
In modeling this as an integer program, the objective function is to minimize the total of the fixed cost and the variable cost. The constraints are as follows: (1) total production capacity is at least 38,000; (2) number of units produced at the Baytown plant is 0 if the plant is not built, and it is no more than 21,000 if the plant is built; (3) number of units produced at the Lake Charles plant is 0 if the plant is not built, and it is no more than 20,000 if the plant is built; (4) number of units produced at the Mobile plant is 0 if the plant is not built, and it is no more than 19,000 if the plant is built.
Then we define the decision variables as
The integer programming problem formulation becomes
Notice that if (meaning the Baytown plant is not built), then (the number of units produced at the Baytown plant) must also equal zero due to the second constraint. If , then may be any integer value less than or equal to the limit of 21,000. The third and fourth constraints are similarly used to guarantee that no units are produced at the other locations if the plants are not built. The optimal solution, shown in Program 10.6, is
Solver Parameter Inputs and Selections | Key Formulas |
---|---|
Set Objective: E5 |
Copy H5 to H8:H11 |
By Changing cells: B4:G4 | |
To: Min | |
Subject to the Constraints: | |
H8 >= J8 | |
H9:H11 <= J9:J11 | |
B4:D4 = binary | |
E4:G4 = integer | |
Solving Method: Simplex LP | |
☑ Make Variables Non-Negative |
This means that factories will be built at Lake Charles and Mobile. Each of these will produce 19,000 units each year, and the total annual cost will be $1,757,000.
Numerous financial applications exist with 0–1 variables. A very common type of problem involves selecting from a group of investment opportunities. The following example illustrates this application.
The Houston-based investment firm of Simkin, Simkin, and Steinberg specializes in recommending oil stock portfolios for wealthy clients. One such client has made the following specifications: (1) at least two Texas oil firms must be in the portfolio, (2) no more than one investment can be made in foreign oil companies, and (3) one of the two California oil stocks must be purchased. The client has up to $3 million available for investments and insists on purchasing large blocks of shares of each company that he invests in. Table 10.4 describes various stocks that Simkin considers. The objective is to maximize annual return on investment subject to the constraints.
STOCK | COMPANY NAME | EXPECTED ANNUAL RETURN ($1,000s) | COST FOR BLOCK OF SHARES ($1,000s) |
---|---|---|---|
1 | Trans-Texas Oil | 50 | 480 |
2 | British Petroleum | 80 | 540 |
3 | Dutch Shell | 90 | 680 |
4 | Houston Drilling | 120 | 1,000 |
5 | Texas Petroleum | 110 | 700 |
6 | San Diego Oil | 40 | 510 |
7 | California Petro | 75 | 900 |
To formulate this as a 0–1 Integer Programming problem, Simkin lets be a 0–1 integer variable, where if stock i is purchased and if stock i is not purchased:
Solver Parameter Inputs and Selections | Key Formulas |
---|---|
Set Objective: I5 |
Copy I5 to I7:I10 |
By Changing cells: B4:H4 | |
To: Max | |
Subject to the Constraints: | |
I7 >= K7 | |
I8 <= K8 | |
I9 = K9 | |
I10 <= K10 | |
B4:H4 = binary | |
Solving Method: Simplex LP | |
☑ Make Variables Non-Negative |
The solution found using Solver in Excel 2016 is shown is Program 10.7.