UNIT-V: DYNAMIC PROGRAMMING

When formulating LP‟s we often found that, strictly, certain variables should have been regarded as
taking integer values but, for the sake of convenience, we let them take fractional values reasoning
that the variables were likely to be so large that any fractional part could be neglected. While this is
acceptable in some situations, in many cases it is not, and in such cases we must find a numeric
solution in which the variables take integer values.
Problems in which this is the case are called integer programs (IP's) and the subject of solving such
programs is called integer programming (also referred to by the initials IP).
IP's occur frequently because many decisions are essentially discrete (such as yes/no, do/do not) in
that one or more options must be chosen from a finite set of alternatives.
An IP in which all variables are required to be integers is called a pure IP problem.
If some variables are restricted to be integer and some are not then the problem is a
mixed IP problem.
The case where the integer variables are restricted to be 0 or 1 comes up surprising often. Such
problems are called pure (mixed) 0-1 programming problems or pure (mixed) binary IP problems.
For any IP we can generate an LP by taking the same objective function and same constraints but with
the requirement that variables are integer replaced by appropriate continuous constraints:
“xi ≥ 0 and integer” can be replaced by xi ≥ 0
“xi = 0 or 1” can be replaced by xi ≥ 0 and xi ≤ 1
The LP obtained by omitting all integer or 0-1 constraints on variables is called LP Relaxation of the
IP (LR).
FORMULATING IP

Practical problems can be formulated as IPs. For instance budgeting problems, knapsack problems,
fixed charge production and location problems, set covering problems, etc.
Budgeting Problems Example

CapitalBudgeting
(Winston 9.2, p. 478 – modified)
Stock is considering four investments
Each investment yields a determined NPV ($8,000, $11,000, $6,000, $4,000) Each investment
requires at certain cash flow at the present time ($5,000, $7,000,
$4,000, $3,000)
Currently Stock has $14,000 available for investment.

88

1 www.jntufastupdates.com
 Formulate an IP whose solution will tell Stock how to maximize the NPV obtained from the
four investments.
Answer
Begin by defining a variable for each decision that Stockco must make. In this case, we will use a
0-1 variable xj for each investment:
If xj is 1 then Stock will make investment j. If it is 0, Stock will not make the investment. This
leads to the 0-1 programming problem:
max z = 8x1 + 11x2 + 6x3 + 4x4
s.t.5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xj = 0 or 1 (j = 1,2,3,4)
Comment
Now, a straightforward “bang for buck” (taking ratios of objective coefficient over
constraint coefficient) suggests that investment 1 is the best choice.
Ignoring integrality constraints, the optimal linear programming solution is:
x1 = x2 = 1, x3 = 0.5, and x4 = 0 for a value of $22K Unfortunately, this solution is not
integral. Rounding x3 down to 0:
x1 = x2 = 1, x3 = x4 = 0 for a value of $19K
There is a better integer solution (optimal solution):
x1 = 0, x2 = x3 = x4 = 1 for a value of $21K
This example shows that rounding does not necessarily give an optimal value.
Example 1.b. Multiperiod
There are four possible projects, which each run for three years and have the following
characteristics: Which projects would you choose in order to maximize the total return?
Capital requirements
Answer
We will use a 0-1 variable xj for each project:
xj is 1 if we decide to do project j;
xj is 0 otherwise (i.e. not do project j). This leads to the 0-1 programming problem: max 0.2 x1 +
0.3 x2 + 0.5 x3 + 0.1 x4
s.t.0.5 x1 + 1x2 + 1.5 x3 + 0.1 x4 ≤ 3.1

0.3 x1 + 0.5 x2 + 1.5 x3 + 0.4 x4 ≤ 2.5

0.2 x1 + 0.2 x2 + 0.3 x3 + 0.1 x4 ≤ 0.4
xj = 0 or 1 j = 1, … 4

89

2 www.jntufastupdates.com
Example 1.c. Capital Budgeting Extension
There are a number of additional constraints Stock might want to add. Logical restrictions can be
enforced using 0-1 variables:
Stock can only make two investments
x1 + x2 + x3 + x4 ≤ 2
Any choice of three or four investments will have x1 + x2 + x3 + x4 ≥ 3 If investment 2 is made,
investment 4 must also be made
x2 < x4 or x2 – x4 ≤ 0
If x2 is 1, then x4 is also 1 as Stock desires; if x2 is 0, then there is no restriction for x4 (x4 is 0 or 1)
If investment 1 is made, investment 3 cannot be made
x1 + x3 ≤ 1
If x1 is 1, then x3 is 0 as Stock desires; if x1 is 0, then there is no restriction for
x3 (x3 is 0 or 1)
Either investment 1 or investment 2 must be done
x1 + x2 = 1
If x1 is 1, then x2 is 0 (only investment 1 is done); if x1 is 0, then x2 is 1 (only investment 2 is done)

Knapsack Problems

Any IP that has only one constraint is referred to as a knapsack problem. Furthermore, the coefficients
of this constraint and the objective are all non-negative. The traditional story is that: There is a
knapsack. There are a number of items, each with a size and a value. The objective is to maximize the
total value of the items in the knapsack.
Knapsack problems are nice because they are (usually) easy to solve.
Example 2. Knapsack
For instance, the following is a knapsack problem:
Maximize8 x1 + 11 x2 + 6 x3 + 4 x4
Subject to5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14
xj = 0 or 1j = 1, … 4

Fixed Charge Problems

There is a cost associated with performing an activity at a nonzero level that does not depend on the
level of the activity.
An important trick can be used to formulate many production and location problems involving the
idea of a fixed charge as IP.

90

3 www.jntufastupdates.com
 Example 3.a. Gandhi
(Winston 9.2, p. 480)
Gandhi Co makes shirts, shorts, and pants using the limited labor and cloth described below.
In addition, the machinery to make each product must be rented.
Shirts Shorts Pants Total Avail.
Answer
Let xj be number of clothing produced.
Let yj be 1 if any clothing j is manufactured and 0 otherwise.
Profit = Sales revenue – Variable Cost – Costs of renting machinery For example the profit from
shirts is
z1 = ( 12 – 6 ) x1 – 200 y1
Since supply of labor and cloth is limited, Gandhi faces two constraints.
To ensure xj > 0 forces yj = 1, we include the additional constraints
xj ≤ Mj yj
From the cloth constraint at most 40 shirts can be produced (M1=40), so the additional constraint for
shirts is not an additional limit on x1 (If M1 were not chosen large (say M1=10), then the additional
constraint for shirts would unnecessarily restrict the value of x1).
From the cloth constraint at most 53 shorts can be produced (M2=53) From the labor constraint at
most 25 pants can be produced (M3=25) We thus get the mixed (binary) integer problem:
Max 6 x1 + 4 x2 + 7 x3 – 200 y1 – 150 y2 – 100 y3
s.t.3 x1 + 2 x2 + 6 x3 ≤ 150(Labor constraint)
4 x1 + 3 x2 + 4 x3 ≤ 160(Cloth constraint)
x1 ≤ 40 y1(Shirt production constraint)
x2 ≤ 53 y2(Short production constraint)
x3 ≤ 25 y3(Pant production constraint)
x1, x2, x3 ≥ 0 and integer
y1, y2, y3 = 0 or 1
Example 3.b. Lockbox
(Winston 9.2, p. 483)
Consider a national firm that receives checks from all over the United States.
There is a variable delay from when the check is postmarked (and hence the customer has met her
obligation) and when the check clears (the firm can use the money).
It is in the firm's interest to have the check clear as quickly as possible since then the firm can use the
money.
To speed up this clearing, firms open offices (lockboxes) in different cities to handle the checks.
Suppose firm receives payments from four regions (West, Midwest, East, and South). The average
daily value from each region is as follows: $70,000 from the West,
91

4 www.jntufastupdates.com
 $50,000 from the Midwest, $60,000 from the East, and $40,000 from the South. Firm is considering
opening lockboxes in L.A., Chicago, New York, and/or Atlanta. Operating a lockbox costs $50,000
per year.
Assume that each region must send all its money to a single city. Also assume that investment rate is
20%.
Which lockboxes should firm open? (Formulate an IP that firm can use to minimize the sum of costs
due to lost interest and lockbox operations.)
Answer
First we must calculate the losses due to lost interest for each possible assignment. For instance, if the
West sends to New York, then on average there will be $560,000 (=8×$70.000) in process on any
given day. Assuming an investment rate of 20%, this corresponds to a yearly loss of $112,000.
We can calculate the losses for the other possibilities in a similar fashion to get the following table:
Let yj be a 0-1 variable that is 1 if lockbox j is opened and 0 if it is not. Let xij be 1 if region i sends to
lockbox j; and 0 otherwise.
Our objective is to minimize our total yearly costs. This is: 28 x11 + 84 x12 + … + 50 y1 + 50 y2 +
50 y3 + 50 y4
One set of constraint is that each region must be assigned to one lockbox:
∑j xij = 1 for all i
(∑j should be read as "sum over all integer values of j from 1 to n inclusive")
A region can only be assigned to an open lockbox:
x1j + x2j + x3j + x4j ≤ M yj
M is any number that should be at least 4 as there are four regions.
(Suppose we do not open LA lockbox; then y1 is 0, so all of x11, x21, x31, and x41 must also be 0. If
y1 is 1, then there is no restriction on the x values.)
Min 28 x11 + 84 x12 + 112 x13 + 112 x14+ 60 x21 + 20 x22 + 50 x23 + 50 x24+ 96 x31 + 60 x32 +
24 x33 + 60 x34+ 64 x41 + 40 x42 + 40 x43 + 16 x44+ 50 y1 + 50 y2 + 50 y3 + 50 y4
s.t. x11 + x12 + x13 + x14 = 1 x21 + x22 + x23 + x24 = 1 x31 + x32 + x33 + x34 = 1 x41 + x42 +
x43 + x44 = 1
x11 + x21 + x31 + x41 ≤ 4y1 x12 + x22 + x32 + x42 ≤ 4y2 x13 + x23 + x33 + x43 ≤ 4y3 x14 + x24 +
x34 + x44 ≤ 4y4
All xij and yj = 0 or 1

92

5 www.jntufastupdates.com
Membership in Specified Subsets

Using decision variables that equal 1 if an object is part of a solution and 0 otherwise, set covering,
set packing, and set partitioning models formulate problems where the core issue is membership in
specifed subsets.
Many applications in areas such as location problems (fire/police station, warehouse, facility),
scheduling (crew, airline, truck, bus), political districting
•Set covering constraints
Require that at least one member of subcollection J belongs to a solution:
∑jJ xj ≥ 1
•Set packing constraints
Require that at most one member of subcollection J belongs to a solution:
∑jJ xj ≤ 1
•Set partitioning constraints
Require that exactly one member of subcollection J belongs to a solution:
∑jJ xj = 1
Set Covering Problems
Each member of a given set (call it set 1) must be “covered” by an acceptable member of some set
(call it set 2).
The objective of a set-covering problem is to minimize the number of elements in set 2 that are
required to cover all the elements in set 1.
Example 4. Fire Station
A county is reviewing the location of its fire stations. The county is made up of a number of cities:
A fire station can be placed in any city.
It is able to handle the fires for both its city and any adjacent city (any city with a non- zero border
with its home city).
How many fire stations should be built and where?
Answer
We can create one variable xj for each city j (1 if we place a station in the city, 0 otherwise):
Each constraint should state that there must be a station either in city j or in some adjacent city.
The jth column of the constraint matrix represents the set of cities that can be served by a fire station
in city j.
We are asked to find a set of such subsets j that covers the set of all cities in the sense that every city
appears in the service subset associated with at least one fire station
Min x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11
s.t. x1 + x2 + x3 + x4 ≥ 1 (city 1)
x1 + x2 + x3 +x5 ≥ 1 (city 2)

93

6 www.jntufastupdates.com
x1 + x2 + x3 + x4 + x5 + x6≥ 1 (city 3)
x1+ x3 + x4+ x6 + x7≥ 1 (city 4)
x2 + x3+ x5 + x6+ x8 + x9≥ 1 (city 5)
x3 + x4 + x5 + x6 + x7 + x8≥ 1 (city 6)
x4+ x6 + x7 + x8≥ 1 (city 7)
x5 + x6 + x7 + x8 + x9 + x10≥ 1 (city 8)
x5+ x8 + x9 + x10 + x11≥ 1 (city 9)
x8 + x9 + x10 + x11x9 + x10 + x11≥ 1 (city 10)
≥ 1 (city 11)
All xj = 0 or 1
Either-Or Constraint
Given two constraints
f(x1, x2,…, xn) ≤ 0(1)
g(x1, x2,…, xn) ≤ 0(2)
ensure that at least one is satisfied (1 or 2) by adding either-or-constraints:
f(x1, x2,…, xn) ≤ M y
g(x1, x2,…, xn) ≤ M (1 – y)
Here y is a 0-1 variable, and M is a number chosen large enough to ensure that both constraints are
satisfied for all values of decision variables that satisfy the other constraints in the problem:If y = 0,
then (1) and possibly (2) must be satisfied.
If y = 1, then (2) and possibly (1) must be satisfied.

Example 5. Fire Station

Suppose 1.5 tons of steel and 30 hours of labor are required for production of one compact car.
At present, 6,000 tons of steel and 60,000 hours of labor are available.
For an economically feasible production, at least 1,000 cars of compact car must be produced.
•Constraint:x ≤ 0 or x ≥ 1000
Sign restriction: x ≥ 0 and Integer
Answer
For f(x) = x; g(x) = 1000 – x
We can replace the constraint by the following pair of linear constraints:
x≤My
1000 – x ≤ M (1 – y)
y = 0 or 1
M = min (6.000/1.5, 60.000/30) = 2000

94

7 www.jntufastupdates.com
If-Then Constraints
Suppose we want to ensure that
a constraint f(x1, x2,…, xn) > 0 implies the constraint g(x1, x2,…, xn) ≥ 0
Then we include the following constraints in the formulation:
–g(x1, x2,…, xn) ≤ M y(1)
f(x1, x2,…, xn) ≤ M (1 – y) (2)
Here y is a 0-1 variable, and M is a large positive number, chosen large enough so that f<M and –
g<M hold for all values of decision variables that satisfy the other constraints in the problem.
If f > 0, then (2) can be satisfied only if y = 0. (1) implies –g ≤ 0 or g ≥ 0, which is the desired result
Example 6. Modified Lockbox
(Winston 9.2, p. 490)
Suppose we add the following constraint
If customers in region 1 send their payments to city 1, no other customers may send their payments to
city 1:
If x11 = 1, then x21 = x31 = x41 = 0 
If x11 > 0, then x21 + x31 + x41 ≤ 0
Answer
For f = x11 and g = – x21 – x31 – x41
We can replace the implication by the following pair of linear constraints:
x21 + x31 + x41 ≤ My x11 ≤ M (1 – y)
y = 0 or 1
–g and f can never exceed 3, we can choose M as 3.

95

8 www.jntufastupdates.com