Tools › Operations Research › Optimization › Linear Programming › Example
Hillier and Lieberman: California Manufacturing Co. factory and warehouse decisions (binary IP)
| Tool | Linear Programming |
| Source | Hillier, F. S., and Lieberman, G. J. (2015). Introduction to Operations Research, 10th ed. McGraw-Hill, New York. Sections 12.1 and 12.6. |
| Level | Undergraduate |
Problem
California Manufacturing may build a factory in Los Angeles (x1, NPV 9, cost 6) or San Francisco (x2, 5, 3) and at most one warehouse (x3 in LA, 6, 5; x4 in SF, 4, 2), a warehouse only where a factory is built, with 10 million available. Which yes/no decisions maximize the total net present value?
Inputs to Enter
- max 9 x1 + 5 x2 + 6 x3 + 4 x4
- 6 x1 + 3 x2 + 5 x3 + 2 x4 <= 10 ; x3 + x4 <= 1
- -x1 + x3 <= 0 ; -x2 + x4 <= 0
- bin x1, x2, x3, x4
Answers
- LP relaxation: Z = 16.5 at x1 = 5/6, x2 = 1, x3 = 0, x4 = 1
- Integer optimum by branch and bound: Z = 14 at x1 = 1, x2 = 1, x3 = 0, x4 = 0 (both factories, no warehouse)
- Relative gap (16.5 − 14)/14 = 17.9 %
Notes
Type the model with the 'bin' line in place of the default problem; the branch-and-bound tree is printed. Not the default case.