Chapter 6Optimizing Models with Integer Variables

Binary variable: A binary variable is a 0-1 variable that must equal 0 or 1. Usually, a 0-1 variable corresponds to an activity that either is or is not undertaken. If the 0-1 variable is equal to 1, then the activity is undertaken; if it is equal to 0, the activity is not undertaken.

Examples discussed in this chapter

  • Capital budgeting models
  • Fixed-cost models
  • Conditional production quantity – Minimum production
  • Set-covering model – Hub location problem
  • Location-Assignment model
  • Manufacturing and distribution

Capital Budgeting Models

Example 6.1 Selecting Investments (CapitalBudgeting1.xls)

From the following seven investments select the best set of investments that maximizes NPV given only $15,000 of cash is available for investment. Each investment must be taken in full, no partial investment is allowed.

Investment / Cash required / NPV
1 / 5000 / 16000
2 / 2500 / 8000
3 / 3500 / 10000
4 / 6000 / 19500
5 / 7000 / 22000
6 / 4500 / 12000
7 / 3000 / 7500
Changing cells / Binary variable for each investment (1 = Invest, 0= do not invest)
Set target cell / Maximize sum of NPV of selected investments
Constraint / Total cash required <= $15,000

Sensitivity analysis:Solver table for budget from $15,000 to $25,000 in increments of $1000

Extensions:

Condition / Add constraint
At most two investments can be selected / Sum of 0-1 variables <= 2
If investment 2 is selected, then investment 1 must also be selected / 0-1 variable for investment 1 >= 0-1 variable for investment 2
Either investment 1, or 2 or both must be selected / Sum of the 0-1 variables for investment 1 and 2 >=1
Either investment 1 or 2, but not both must be selected / Sum of the 0-1 variables for investments 1 and 2 =1

Two-Period Capital Budgeting Model (CapitalBudgeting2.xls)

The following table shows investments when cash is required over two years. The available budget for year 1 is $14,000 and for year 2 is $4,500.

Investment / Cash required in year 1 / Cash required in year 2 / NPV
1 / 5000 / 2000 / 16000
2 / 2500 / 1500 / 8000
3 / 3500 / 2000 / 10000
4 / 6500 / 0 / 20000
5 / 7000 / 500 / 22000
6 / 4500 / 1500 / 12000
7 / 3000 / 0 / 8000

The only change to the previous model required is an additional budget constraint for year 2.

Fixed Cost Models

Fixed cost is incurred if an activity is chosen. In addition there will be variable cost that varies with the level of the activity.

Example 6.2Textile manufacturing (FixedCostMfg.xls)

The company manufactures five products. Each requires a machine to be rented if it is chosen for production. In addition, there is labor cost, cloth cost, and other variable cost for each unit produced. The data is given in the table below.

Rental cost / Labor Hours / Cloth (Sq. yd) / Sales price / Unit Variable cost
Shirts / 1500 / 2 / 3 / 35 / 20
Shorts / 1200 / 1 / 2.5 / 40 / 10
Pants / 1600 / 6 / 4 / 65 / 25
Skirts / 1500 / 4 / 4.5 / 70 / 30
Jackets / 1600 / 8 / 5.5 / 110 / 35

Resource available:4000 hours of labor and 4500 square yards of cloth

Changing cells /
  • Binary variable for each product (1 = Produce, 0= do not produce)
  • Production quantity for each product

Set target cell / Maximize total profit
Constraints /
  • Labor hours used < Labor hours available
  • Square yards of cloth used <= Square yards of cloth available
  • Unit produced <= Logical upper limit (0 if the product is not selected, otherwise limited by the smaller of labor hours and cloth availability.

Extension:

At least three types of clothing is produced at positive level of at least 100 / Sum of 0-1 variables>= 3
A logical minimum production level of 100 for each type of clothing

Example 6.3Manufacturing at Dorian Auto (EitherOrManufacturing.xls)

The company produces three types of cars and two types of minivans. Each automobile has a minimum production level if it is chosen for production.

Vehicle type / Steel (tons)/unit / Labor hours/unit / Minimum production (if any) / Profit contribution/unit
Compact car / 1.5 / 30 / 1000 / 2000
Midsize car / 3 / 25 / 1000 / 2500
Large car / 5 / 40 / 1000 / 3000
Midsize minivan / 6 / 45 / 200 / 5500
Large minivan / 8 / 55 / 200 / 7000

Resources available: 6500 tons of steel and 65,000 hours of labor.

Changing cells /
  • Binary variable for each vehicle (1 = Produce, 0= do not produce)
  • Production quantity for each vehicle

Set target cell / Maximize total profit
Constraints /
  • Labor hours used < Labor hours available
  • Tons of steel used <= Tons of steel available
  • Unit produced <= Logical upper limit (0 if the product is not selected, otherwise limited by the smaller of labor hours and steel availability.
  • Units produced >= Logical lower limit (0 if the vehicle is not chosen, given minimum value if chosen

Set-Covering and Location-Assignment Models

Determine the minimum number of offices or service centers required and their respective locations such that all the service areas are covered. Fixed costs, operating costs, and transportation costs are considered.

Example 6.4Hub location at Western Airlines (LocatingHubs1.xls)

The airlines wishes to locate minimum number of hubs to serve cities within 1000 miles.

City / Cities within 1000 miles
AT / AT, CH, HO, NO, NY, PI
BO / BO, NY, PI
CH / AT, CH, NY, NO, PI
DE / DE, SL
HO / AT, HO, NO
LA / LA, SL, SF
NO / AT, CH, HO, NO
NY / AT, BO, CH, NY PI
PI / AT, BO, CH, NY PI
SL / DE, LA SL, SF, SE
SF / LA, SL, SF, SE
SE / SL, SF, SE

Example 6.5Locating and Assigning Service Centers at United Copiers

(LocatingServiceCenters1.xls)

United Copiers sells copy machines in 11 cities. Service center must be located in 3 of these 11 cities and each city must be assigned to one of the three service centers. Set target cell is to minimize total distance traveled from service centers to cities annually.

Given data:Table of distances and number of service trips required at each city

Changing cells /
  • Binary variable for each city (1 = Selected for service center, 0= not selected)
  • Binary variable for assigning each city to one of the potential service centers i.e. all 11 cities (1 = assigned, 0= not assigned)

Set target cell / Minimize annual distance traveled = distance between a city and the service center to which the city is assigned times number of trips per year
Constraints /
  • Total cities selected for service center <= 3
  • Number of service centers to which a given city is assigned = 1
  • A city can be assigned to a service center in a city only if a service center is located in that city

Sensitivity:How will the annual distance traveled vary if the number of service centers is anywhere between 1 and 11?

Example 6.6 Manufacturing and Distributing Fertilizer at Green Grass

(FixedCostTransportation.xls)

Given data: Customer order bids (quantity and price), and distances between each pair of cities.

Assume plant capacity of 2500 pounds per month. Fixed cost operating a plant is $60,000. Production cost is $10.25 per pound. Shipping cost is $0.02 per pound per mile.

Changing cells /
  • Binary variable for each city (1 = Selected for production, 0= not selected)
  • Binary variable for assigning each customer order to one of the potential plants i.e. all 8 cities (1 = assigned, 0= not assigned)

Set target cell / Maximize monthly profit = Sum of bid prices accepted – Production cost x Quantity produced – Shipping cost x quantity shipped x distance – Fixed operating cost of number of plants selected for production
Constraints /
  • Number of plants to which a given customer order is assigned <= 1 (Note: “<=” allows for an order to be not fulfilled)
  • A customer order can be assigned to a plant in a city only if a plant is selected for production

Sensitivity: How much larger Miami’s bid would need to be before it is accepted?