ENMG 

604 
Deterministic Optimization Models

LP Formulation

Ali Yassine
Engineering Management Program
American University of Beirut
ali.yassine@aub.edu.lb

1. Production Planning – Single period (Resource allocation)

Example
P Q
Machines: A, B, C, D
Available t imes differ $90/unit $100/unit
100 unit/wk 40 unit/wk
Operating expenses
excluding raw materials:
$3000/week

D D
10 min/unit 15 min/unit

Purchase 
Part
$5/U
C C B
9 min/unit 6 min/unit 16 min/unit

A B A
20 min/unit 12 min/unit 10 min/unit

RM1 RM2 RM3

$20/U $20/U $20/U

1
Decision Variables
xP # of units of product P to produce per week
xQ # of units of product Q to produce per week
Formulation
max 45 x p + 60 x Q Objective Function
s.t. 20 x p + 10 x Q ≤ 1800 Structural
12 x p + 28 x Q ≤ 1440 constraints
15 xp + 6 xQ ≤ 2040
10 x p + 15 x Q≤ 2400
Xp ≤ 100, xQ ≤ 40 demand

Are we done?
Xp ≥ 0 xQ ≥ 0 g y
nonnegativity

Are the LP assumptions

valid for this problem?
Optimal
Solution
*
X
p
= 81.82 x *Q = 16.36

2. Multi-Period Production-Inventory Model

2
The objective function seeks to minimize the sum of the
production and end-of-month inventory costs.

3
Constraints

The complete model is:

4
3. Bank Loan Policy -- Financial Engineering

Bank has 12Millions

5
The objective function

Constraints

6
4. Currency Arbitrage -- Financial Engineering

Suppose that a company has a $5Millions that can be exchanged for

Euros, Pounds, Yen, and Dinars.

Can we maximize this $5Million from multiple

multiple, simultaneous
currency exchanges between the various currencies
(starting with $5Millions)?

Currency dealers set the following limits on the amount of any single transaction:
5 million Dollars, 3 million Euros, 3.5 million Pounds, 100 million Yen, and
2.8 million Dinars.

Typical spot
exchange rates

Define DVs as:

Our goal is to determine the maximum final dollar holdings, y, subject to the currency
flow restrictions and the maximum limits allowed for the different transactions.

7
Constraints

To conserve the flow of money from one currency to

another, each currency must satisfy the following
input-output equation:

8
9
5. Employee Scheduling

Macrosoft has a 24-hour-a-day 7-days-a-week toll free hotline

that is being set up to answer questions regarding a new
product. The following table summarizes the number of full
full-
time equivalent employees (FTEE’s) that must be on duty in
each time block.

Shift Time FTEE’s

1 0-4 15
2 4-8 10
3 8-12 40
4 12-16 70
5 16-20 40
6 20-0 35

10
 • Macrosoft may hire both full-time and part-time employees.
The former work 8-hour shifts and the latter work 4-hour
shifts, and their respective hourly wages are $15.20 and
$12.95. Employees may start work only at the beginning of
one of the six shifts.
shifts

• At least two thirds of the employees working at any one time

must be full-time employees.

• Part-time employees can only answer 5 calls in the time a

full-time employee can answer 6 calls. (i.e., a part-time
employee is only 5/6 ths of a full-time employee.)

Formulate an LP to determine how to staff the hotline at

minimum cost.

Decision Variables
xt = # of full-time employees that begin work in shift t
yt = # of part-time employees that work shift t

(8*15.20) (4*12.95)
min 121.6(x1 + • • • + x6) + 51.8(y
51 8(y1 + • • • + y6)
5
s.t. x6 + x1 + 6
y1 ≥ 15
5
All shifts
x1 + x2 + 6
y2 ≥ 10 must be
5
x2 + x3 + 6
y3 ≥ 40 covered
5
x3 + x4 + 6
y4 ≥ 70
5
x4 + x5 + 6
y5 ≥ 40
5
x5 + x6 + 6
y6 ≥ 35

PT employee is 5/6 FT employee

11
 2
(x 6 + x 1 ) ≥ (x 6 + x 1 + y 1) At least 2/3
3
2
workers must
(x 1 + x 2 ) ≥ (x 1 + x 2 + y 2 ) b full
be f ll time
i
3
..
.
2
(x 5 + x 6 ) ≥ (x 5 + x 6 + y 6)
3

xt ≥ 0, yt ≥ 0 t =1,2, …,6

6. Energy Generation Problem (with piecewise linear objective)

Austin Municipal Power and Light (AMPL) would like to
determine optimal operating levels for their electric generators
and associated distribution patterns that will satisfy customer
demand. Consider the following prototype system

Demand requirements
1 4 MW
1

Plants 2 Demand 7 MW

2
3
6 MW

The two plants (generators) have the following (nonlinear) efficiencies:

Plant 1 [ 0, 6 MW] [ 6MW, 10MW]
Unit cost ($/MW) $10 $25
Plant 2 [ 0, 5 MW] [5MW, 11MW]
Unit cost ($/MW) $8 $28

12
 Formulate an LP that, when solved, will yield optimal power
generation and distribution levels.

Decision Variables

X 11 = power generated at plant 1 at operating level 1

X 12 ″ ″ ″ ″ 1 ″ ″ ″ 2
X 21 ″ ″ ″ ″ 2 ″ ″ ″ 1
X 22 ″ ″ ″ ″ 2 ″ ″ ″ 2

y 11 = power sent from plant 1 to demand sector 1

y 12 ″ ″ ″ ″ 1 ″ ″ ″ 2
y 13 ″ ″ ″ ″ 1 ″ ″ ″ 3
y 21 ″ ″ ″ ″ 2 ″ ″ ″ 1
y 22 ″ ″ ″ ″ 2 ″ ″ ″ 2
y 23 ″ ″ ″ ″ 2 ″ ″ ″ 3

Formulation

Min 10x 11 + 25x 12 + 8x 21 + 28x 22

s.t.
s t y11 + y12 + y13 = x11 + x12
y21 + y22 + y23 = x21 + x22
y11 + y21 = 4
y12 + y22 = 7
y13 + y23 = 6
0 ≤ x11 ≤ 6 0 ≤ x12 ≤ 4
0 ≤ x21 ≤ 5 0 ≤ x22 ≤ 6
y11, y12, y13, y21, y22, y23 ≥ 0
Note that we can model the nonlinear operating costs with an LP only because the
efficiencies have the right kind of structure. In particular the plant is less efficient (more
costly) at higher operating levels. Thus the LP solution will automatically select level 1
first.

13
 The above formulation can become cumbersome when there
are additional plants, demand sectors, and/or generation
levels. We can reformulate this model instance as a general
model using the Sets/Data/Decision Variables/ Formulation
Format.

Indices/Sets
i∈I plants
j∈J demand sectors
k∈K generation levels

Data

Cik = unit generation cost ($/MW) for plant i at level k

Uik = upper bound (MW) for plant i at level k
dj = demand (MW) in sector j

Decision Variables

xik = power (MW) generated at plant i at level k

yij = power (MW) sent from plant i to sector j

Formulation

min ∑∑ Cik xik

i∈I k∈K

s.t. ∑ yij =
∑ xik ∀ i∈I
j∈J K∈K

∑ yij = dj ∀ j ∈J
i∈I

0 ≤ xik ≤ Uik ∀ i∈I, k∈K 0 ≤ yij ∀ i∈I, j∈J

14
 7. Feed Mix Problem [Bazaraa, Jarvis and Sherali, 1990]
An agricultural mill produces three types of feed for cattle,
sheep, and chickens by mixing the following raw ingredients:
corn, limestone, soybeans, and fish meal.

These iingredients
Th di t contain
t i the
th following
f ll i nutrients:
t i t vitamins,
it i
protein, calcium, and crude fat in the following quantities:

Nutrient (k)
Vitamins Protein Calcium Crude Fat
Ingredient (i)
Corn 8 10 6 8
Limestone 6 5 10 6
Soybeans 10 12 6 6
Fish Meal 4 18 6 9

Quantity of nutrient k per kg of ingredient i: aik

The mill has (firm) contracts for the following demands

Demand (kg) Cattle Sheep Chicken

dj 10,000 6,000 8,000

There are limited availabilities of the raw ingredients

Supply (kg) Corn Limestone Soybeans Fish Meal

si 6,000 10,000 4,000 5,000

The different feeds have “quality” bounds per kilogram

Feed
eed Vitamins
ta s Protein
ote Calcium
Ca cu Crude
C ude Fat
at
min max min max min max min max
Cattle 6 -- 6 -- 7 -- 4 8
Sheep 6 -- 6 -- 6 -- 4 8
Chicken 4 6 6 -- 6 -- 4 8

Above values represent bounds: Ljk & Ujk

15
 Finally, the cost per kg of the raw ingredients is as
follows:
corn limestone soybeans fish meal
cost p
per kg
g 20
20¢ 12¢
2 24¢
2 12¢
2
ci
Formulate this as a linear program in order to
produce the desired feeds at minimum cost.

Indices/Sets
i∈I ingredients {corn, limestone, soybeans, fish meal}
j∈J products {cattle, sheep, chicken feeds}
k∈K nutrients {vitamins, protein, calcium, crude fat}

Data

dj demand for product j (kg)

si supply of ingredient i (kg)
Ljk lower bound on number of nutrients of type k
per kg of product j
Ujk upper bound on number of nutrients of type k
per kg of product j
ci cost per kg of ingredient i
aik number of nutrients k per kg of ingredient i

Decision Variables
xij amount (kg) of ingredient i used in producing
product j

16
 Formulation

min ∑∑ ci xij
i∈I j∈J

s.t. ∑ xij = dj ∀ j∈J

i∈I
∑ xij ≤ si ∀ i∈I
j∈J

∑ aik xij ≤ Ujk dj ∀ j∈J, k∈K

i∈I
∑ aik xij ≥ Ljkdj ∀ j∈J, k∈K
i∈I

xij ≥ 0 ∀ i∈I, j∈J

This feed mix problem is an example of a more general

class of mathematical programming models called
blending problems.

Raw Materials Qualities Blended

Commodities
corn, limestone, protein, vitamins, feed
soybeans, fish meal calcium, crude fat

Butane, catalytic Octane, volatility, gasoline

reformate, vapor pressure
heavy naphtha

Pig iron, Carbon, Metals

ferro-silicon, manganese,
carbide, various chrome content
alloys

≥ 2 raw ingredients ≥ 1 quality ≥ 1 commodity

17
8. Blending Problems

8. Blending Problems

18
8. Blending Problems - Continued

8. Blending Problems - Continued

19
8. Blending Problems - Continued

8. Blending Problems - Continued

6. Octane number (ON) for regular is at least 87:

20
9. Trim-Loss or Cutting Stock problem

Three special orders for rolls of paper have been placed at a

paper mill. The orders are to be cut from standard rolls of 10 ′
d 20′ widths
and idth (Length
(L th L).
L)
Desired
order width # Rolls
1 5′ 150
2 7′ 200
3 9′ 300

Goal: Throw away as little as possible

What is trim-loss?

21
What is trim-loss?

10 ′ 20 ′

5' L'
L
9' 5′

7′

Dec Variables xj = length of roll cut using pattern

j = 1,2, … ?

Patterns possible

10′ roll 20′ roll

x1 x2 x3 x4 x5 x6 x7 x8 x9

5′ 2 0 0 4 2 2 1 0 0
7′
7 0 1 0 0 1 0 2 1 0
9′ 0 0 1 0 0 1 0 1 2

Trim 0 3 1 0 3 1 1 4 2
Loss

min z = 10(x 1+x 2+x 3) + 20(x 4 +x5+x 6+x 7+x8+x9 )

st 2x1 + 4x4 + 2x 5 + 2x 6 + x 7 ≥ 150

x 2 + x 5 + 2x 7 + x8 ≥ 200

x3 + x6 + x8 + 2x 9 ≥ 300

xj ≥ 0, j = 1,2, …, 9

22
Alternative Formulation

min z = 3x 2 + x3 + 3x 5 + x 6 + x 7 + 4x 8 + 2x9

+ 5y1 + 7y 2 + 9y3

s.t. 2x 1 + 4 x4 + 2x 5 + 2x 6 + x 7 – y1 = 10,000

x2 + x 5 + 2x7 + x 8 – y2 = 30,000

x 3 + x 6 + x 8 + 2x 9 – y3 = 20,000

xj ≥ 0 j = 1, …, 9 y j ≥ 0 j = 1,2,3.

yi is overproduction of width i

23