Reconsider the California Manufacturing Co$.$ example

presented in Sec. $12\mathrm{.}1.$ The mayor of San Diego now has con

tacted the company$$s president to try to persuade him to build a factory and perhaps a warehouse in that city. With the tax incen

tives being offered the company, the president$$s staff estimates

that the net present value of building a factory in San Diego

would be $$7$ million and the amount of capital required to do this

would be $$4$ million. The net present value of building a ware

house there would be $$5$ million and the capital required would

be $$3$ million. $($This option would be considered only if a factory

also is being built there.$)$

The company president now wants the previous OR study

revised to incorporate these new alternatives into the overall

problem. The objective still is to find the feasible combination of

investments that maximizes the total net present value, given that

the amount of capital available for these investments is $12\mathrm{.}1$ PROTOTYPE EXAMPLE

The CALIFORNIA MANUFACTURING COMPANY is considering expansion by

building a new factory in either Los Angeles or San Francisco, or perhaps even in both

cities. It also is considering building at most one new warehouse, but the choice of loca

tion is restricted to a city where a new factory is being built. The net present value $($total

profitability considering the time value of money$)$ of each of these alternatives is shown

in the fourth column of Table $12\mathrm{.}1.$ The rightmost column gives the capital required

$($already included in the net present value$)$ for the respective investments, where the total

capital available is $$10$ million. The objective is to find the feasible combination of

alternatives that maximizes the total net present value.

The BIP Model

Although this problem is small enough that it can be solved very quickly by inspection

$($build factories in both cities but no warehouse$),$ let us formulate the IP model for illus

trative purposes. All the decision variables have the binary form

xj $=$

Let

$\{10$

if decision j is yes,

if decision j is no$,$

$($ j $=1,2,3,4).$

Z $=$ total net present value of these decisions.

If the investment is made to build a particular facility $($so that the corresponding decision

variable has a value of $1),$ the estimated net present value from that investment is given

in the fourth column of Table $12\mathrm{.}1.$ If the investment is not made $($so the decision vari

able equals $0),$ the net present value is $0.$ Therefore, using units of millions of dollars,

Z $=9$x$1+5$x$2+6$x$3+4$x$4.$

The bottom of the rightmost column of Table $12\mathrm{.}1$ indicates that the amount of

capital expended on the four facilities cannot exceed $$10$ million. Consequently, continu

ing to use units of millions of dollars, one constraint in the model is

$6$x$1+3$x$2+5$x$3+2$x$4<=10.$

Because the last two decisions represent mutually exclusive alternatives $($the company

wants at most one new warehouse$),$ we also need the constraint

x$3+$ x$4<=1.$

$462$

CHAPTER $12$ INTEGER PROGRAMMING

$$ TABLE $12\mathrm{.}1$ Data for the California Manufacturing Co$.$ example

Decision

Number

$1$

$2$

$3$

$4$

Yes$-$or$-$No

Question

Build factory in Los Angeles?

Build factory in San Francisco?

Build warehouse in Los Angeles?

Decision

Variable

Net Present

Value

x$1$

x$2$

x$3$

Build warehouse in San Francisco?

x$4$

$$9$ million

$$5$ million

$$6$ million

$$4$ million

Capital

Required

$$6$ million

$$3$ million

$$5$ million

$$2$ million

Capital available: $$10$ million

Furthermore, decisions $3$ and $4$ are contingent decisions, because they are contingent on

decisions $1$ and $2,$ respectively $($the company would consider building a warehouse in a

city only if a new factory also were going there$).$ Thus, in the case of decision $3,$ we require

that x$3=0$ if x$1=0.$ This restriction on x$3($when x$1=0)$ is imposed by adding the constraint

x$3<=$ x$1.$

Similarly, the requirement that x$4=0$ if x$2=0$ is imposed by adding the constraint

x$4<=$ x$2.$

Therefore, after we rewrite these two constraints to bring all variables to the left$-$hand

side, the complete BIP model is

Maximize

subject to

Z $=9$x$1+5$x$2+6$x$3+4$x$4,$

$6$x$1+3$x$2+5$x$3+2$x$4<=10$

x$3+$ x$4<=1$

$$x$1$

$+$ x$3$

$$ x$2$

and

xj is integer,

$<=$

$0$

$+$ x$4<=0$

xj $<=1$

xj $>=0$

for j $=1,2,3,4.$

Equivalently, the last three lines of this model can be replaced by the single restriction

xj is binary,

for j $=1,2,3,4.$