Optimization II

Part02a – modeling techniques

komarudin74@ui.ac.id
Topics and schedule
1. Day 01a – intro to optimization 4. Day 02b – Modeling in Python
and geometric analysis • Python review
• [Pre-test] • Python practice: Assignment and
• Types of optimization problems transportation
• Motivation and case studies 5. Day 03a – Modeling in Python
• Mathematical Notation • Python practice: Optimizer
2. Day 01b – Modeling techniques • [Assignment 3]
• Modeling in Excel 6. Day 03b – Wrap-up
• Excel practice: Assignment and • [Post-test]
transportation
• Case 1: Optimizer
• Modeling techniques (1)
• [Assignment 1]
3. Day 02a – Modeling in Excel
• Discussion on Case 1
• Modeling techniques (1)
• Case 2: gritting roads
• [Assignment 2]
Modeling Principles
1. Do not build a complicated model when a simple one can be used
2. Beware of modeling the problem to fit the technique
3. The deduction phase of modeling must be conducted rigorously
4. Models should be validated prior to implementation
5. A model should never be taken too literally
6. Beware of overselling the model
7. A model cannot be any better than the information that goes into it
8. Models cannot replace decision makers
 • Technique 1: Absolute value constraints
Table of • Technique 2: Maximin and minimax problems
Contents: • Technique 3: Maximin objective function
• Technique 4: Ratio constraints
Modeling • Technique 5: Yes or No
Techniques • Technique 6: Either Or
• Technique 7: Sequencing
• Technique 8: Fixed charge
non-linear constraints transformed into linear constraints

– Absolute value constraints, in which the absolute value of a linear combination

of decision variables is constrained

– Maximizing minimum constraints (and vice versa), in which we find the largest
value of a “min” function (taking the minimum value from a set), or find the
smallest value of a “max” function (taking the maximum value from a set)

– Ratio constraints, in which the constraint is non-linear due to fractional

coefficients

This is important since

linear programs are so
much easier to solve
than non-linear programs

3
 Absolute constraint (1)
Problem Statement
• A marketing problem, plus an absolute value constraint:

• min 500 x1 + 200 x2 + 250 x3 + 125 x4

s.t. 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000
0 ≤ x1 ≤ 20
0 ≤ x2 ≤ 15
0 ≤ x3 ≤ 10
0 ≤ x4 ≤ 15
|x1 + x2 – x3 – x4| ≤ 5

TV Radio Mail Newspaper

Audience Size 50,000 25,000 20,000 15,000
Cost/Impression $500 $200 $250 $125
Maximum # Ads 20 15 10 15

Task
• Solve with the added absolute value constraint (total number of ads in
electronic media is within 5 of the number in paper-based media), and solve
 Absolute constraint (2)
• There is a “trick” we can use to change the constraint |x1 + x2 – x3 – x4| ≤ 5
into a linear constraint
• |x1 + x2 – x3 – x4| ≤ 5 is equivalent to a combination of the following two
constraints:
• x1 + x 2 – x3 – x4 ≤ 5 and –x1 – x2 + x3 + x4 ≤ 5
• The new problem is linear, and still equivalent to the original non-linear
program:
• min 500 x1 + 200 x2 + 250 x3 + 125 x4
s.t. 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000
0 ≤ x1 ≤ 20, 0 ≤ x2 ≤ 15, 0 ≤ x3 ≤ 10, 0 ≤ x4 ≤ 15
x1 + x2 – x3 – x4 ≤ 5
–x1 – x2 + x3 + x4 ≤ 5

What do you
mean by The problems are equivalent I’m extinct… The set
equivalent? in the sense that any feasible of living dinosaurs is
The two solution for the non-linear equivalent to a linear
problems program is feasible for the program with no
look different linear program, and vice feasible solutions!
to me… versa. That is, the feasible
regions are exactly the
same 5
Absolute Value Constraints – later on EITHER OR
• We now know how to transform constraints of the form | ax1 +bx2 | ≤ c
• However, our trick will not work on absolute value constraints of the form
| ax1 +bx2 | ≥ c
– We can still transform this into two equivalent constraints, but the feasible region
will no longer be convex, meaning we can’t solve the LP by traditional methods
– For example, try out | x1 - x2 | ≥ 2:
• This is equivalent to x1 - x2 ≥ 2 OR -x1 + x2 ≥ 2, which can’t be made linear:

x2 • The feasible region is in yellow, and

it’s in two separate pieces

• Recall from class that a linear

programming feasible region is
always connected, and convex In
fact, it’s always convex: if two
points are feasible, then so is the
line segment joining the two points.

x1
6
 Maximin Problem (1)
• The next constraint we will make linear appears when we maximize the
value of a min function, which looks like min {3x - 2, -2x + 2}
2 -2x + 2
Problem Statement
1
• maximize min {3x - 2, -2x + 2}
s.t. 0≤x≤4 x
0
1
Task -1 3x - 2

• Turn this into an LP -2

• To start, we can look at the graph of the

2 -2x + 2
problem shown above, and identify the
minimum value of the two functions for every 1
value of x (shown here in blue):
0 x
1
-1 3x - 2

-2 7
 Maximin Problem (2)
• Looking at these minimum values, we then find the maximum value of the
blue line (shown as a yellow dot) to solve the problem

• The max of the min has a value of 2/5 at x = 4/5:

2 -2x + 2

0 x
1
-1 3x - 2

-2

8
Maximin objective function (1)
Problem Statement
• Begin with the same marketing problem as seen in Tutorial 02, but with a
new objective function:
• max min {50x1, 25x2, 20x3, 15x4}
s.t. 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000
0 ≤ x1 ≤ 20
0 ≤ x2 ≤ 15
0 ≤ x3 ≤ 10
0 ≤ x4 ≤ 15

• The minimum of {50x1, 25x2, 50x3, 15x4} is the smallest number of persons
reached by one of the four media (in 1000’s)

Task
Try to figure this out
• Formulate this as an LP whose
yourself before looking at
solution will find the maximum the answer!
value of z such that each medium
reaches at least 1000z people
9
Maximin objective function (2)
• Now, we want to maximize z subject to the constraint that z is at most the
number of ads seen for each media
• z is upper bounded by each expression in the min function, which we can
represent with the constraints:
• z ≤ 50x1
z ≤ 25x2
z ≤ 20x3
z ≤ 15x4
• Then, we can maximize z to get our final LP:
• max z
s.t. 50 x1 + 25 x2 + 20 x3 + 15 x4 ≥ 1,500
0 ≤ x1 ≤ 20, 0 ≤ x2 ≤ 15, 0 ≤ x3 ≤ 10, 0 ≤ x4 ≤ 15
z ≤ 50x1, z ≤ 25x2, z ≤ 20x3, z ≤ 15x4

• Note: This technique works whenever you need to maximize the minimum
(“maximin”) of linear functions. A similar trick works whenever you want to
minimize the maximum (“minimax”) of linear functions

10
 Ratio Constraints
Problem Statement
• Consider the Marketing Problem again
• Suppose that we wanted to add the ratio constraint that at least 20% of all
ads had to be by mail:
• x1 / (x1 + x2 + x3 + x4) ≥ .2
Task
• Formulate this as an LP

• The “trick” here is to multiply by the denominator so that the constraint

becomes linear:
• x1 ≥ .2 (x1 + x2 + x3 + x4)
• .8x1 - .2 x2 - .2 x3 - .2 x4 ≥ 0

• Note: You can only do this if you know that the denominator’s value is
positive for all possible x
– If you multiply both sides of an inequality by a negative number, the direction of
the inequality reverses
– The new constraint is valid if x = 0, so we don’t need to consider that case 11
Yes or No decisions – binary variable

Example 1: 0-1 Knapsack Problem

Consider n items to be carried. Item j (𝑗 = 1,2, . . , 𝑛) has a value 𝑐𝑗 and

a weight 𝑎𝑗 . The limited weight that can be carried is K. The problem
is to select the items so as to maximize the total value.

1 if item 𝑗 is chosen
Decision variable: 𝑥𝑗 = ቊ
0 otherwise

The IP model: Maximize σ𝑛𝑗=1 𝑐𝑗 𝑥𝑗

s.t. σ𝑛𝑗=1 𝑎𝑗 𝑥𝑗 ≤ 𝐾
𝑥𝑗 = 0 or 1 ∀𝑗
Either-Or Problem

Consider an IP in which one and only one of the following two constraints
holds

σ𝑗 𝑎1𝑗 𝑥𝑗 ≤ 𝑏1 or σ𝑗 𝑎2𝑗 𝑥𝑗 ≤ 𝑏2

This type of constraint can be reformulated by introducing a 0-1 variable y

and sufficiently large number M such that:
σ𝑗 𝑎1𝑗 𝑥𝑗 − 𝑏1 ≤ 𝑀𝑦 (1)
σ𝑗 𝑎2𝑗 𝑥𝑗 − 𝑏2 ≤ 𝑀 1 − 𝑦 (2)
Note that:
• If 𝑦 = 0 : (2) becomes redundant
• If 𝑦 = 1 : (1) becomes redundant
Either-Or Problem – more constraints

In general, if we have 𝑚 constraints 𝑔𝑖 𝑥 ≤ 0 (𝑖 = 1,2, … , 𝑚) and we

want 𝑘 constraints out of 𝑚 to hold (𝑘 < 𝑚) then we can introduce 𝑚
0-1 variables 𝑦1 , 𝑦2 , …, 𝑦𝑚 and a very large numbers 𝑀 such that:

𝑔𝑖 𝑥 ≤ 𝑀𝑦𝑖 (𝑖 = 1,2, … , 𝑚)
𝑦1 + 𝑦2 +. . +𝑦𝑚 = 𝑚 − 𝑘
𝑦𝑖 = 0 or 1 (𝑖 = 1,2, … , 𝑚)
 Modeling OR: 2 possible values
A variable takes on one of two values.
OR Constraint: x1 = 5 OR 8

MIP Constraints: x1 = 5 w1 + 8 (1 ‐ w1)

w1 ∈ {0, 1}

6
Modeling OR: 3 or more possible values
A variable takes on one of 3 or more values.
OR Constraint: x1 = 5 OR 8 OR 17 OR 99

MIP Constraints: x1 = 5 w1 + 8 w2 + 17 w3 + 99 w4
w1 + w2 + w3 + w4 = 1
wj ∈ {0, 1} for j = 1, 2, 3, 4

7
 Modeling OR: x = 0 OR L ≤ x ≤ U
A variable is 0 or it is between two bounds.
“OR Constraint”: x2 = 0 OR 4 ≤ x2 ≤ 9 .

Equivalent constraint: if x2 > 0, then 4 ≤ x2 ≤ 9

MIP Constraints: 4 w5 ≤ x2 ≤ 9 w5
w5 ∈ {0, 1}

8
Sequencing Problem

Consider the problem in which the optimal processing sequence of 𝑛

jobs on a machine is determined. Assume that the machine can only
process one job at a time.
Denote 𝑝𝑖 : processing time of job 𝑖
𝑡𝑖 : start time of job 𝑖
For a pair of jobs (𝑖, 𝑗) there are only two options:
1. Job 𝑖 starts before job 𝑗 or: 𝑡𝑗 ≥ 𝑡𝑖 + 𝑝𝑖
2. Job 𝑗 starts before job 𝑖 or: 𝑡𝑖 ≥ 𝑡𝑗 + 𝑝𝑗
Sequencing Problem using binary variable

Introduce a very large number 𝑀 and 0-1 variables 𝑦𝑖𝑗 in which 𝑦𝑖𝑗 =
1 if job 𝑖 is processed before job 𝑗, 𝑦𝑖𝑗 = 0 otherwise. The above
options can be described as follows:

𝑀𝑦𝑖𝑗 + 𝑡𝑖 − 𝑡𝑗 ≥ 𝑝𝑗
𝑀 1 − 𝑦𝑖𝑗 + 𝑡𝑗 − 𝑡𝑖 ≥ 𝑝𝑖
𝑦𝑖𝑗 = 0 or 1
Fixed charge - Warehouse Location Problem

Consider the decision to open a number of warehouses at potential sites.

Denote:

𝑦𝑖 : 0-1 variable; =1 if a warehouse is opened at site i, =0 otherwise

𝑓𝑖 : fixed operation cost of the warehouse at site i, if opened
𝑥𝑖𝑗 : amount of goods to be shipped from warehouse at site i, if
opened, to customer j,
𝑐𝑖𝑗 : operation & transportation cost per unit from warehouse at
site i to customer j
𝑑𝑗 : demand of customer j
𝑠𝑖 : supply capacity of warehouse at site i, if opened
Fixed charge - Warehouse Location Problem

The problem can be formulated as a mixed IP:

Min Cost = σ𝑚 𝑛 𝑚
𝑖=1 σ𝑗=1 𝑐𝑖𝑗 𝑥𝑖𝑗 + σ𝑖=1 𝑓𝑖 𝑦𝑖
s.t. σ𝑛𝑗=1 𝑥𝑖𝑗 ≤ 𝑠𝑖 𝑦𝑖 ∀𝑖
σ𝑚
𝑖=1 𝑥𝑖𝑗 ≥ 𝑑𝑗 ∀𝑗
𝑥𝑖𝑗 ≥ 0 ∀𝑖, 𝑗
 Fixed charge problems
• In a fixed charge problem, in order to produce a
positive amount, the production process must be
set up first at a fixed cost.
• After the setup, the cost of production is linear.
• Note: you are permitted to pay for the setup even
if production is 0, even though this would not be
optimal.
22
 Modeling fixed charges
cost
y1 = 0 if x1 = 0
24
20 y1 = 4 + 4x1 if x1 > 0
16
12 Assume 0 ≤ x1 ≤ 100
8
4
0 x1
0 2 4 6 8 10

No cost for no production

Fixed cost for s e l l i n g up production facilities
or a fixed cost for having goods delivered or ….
23
 Modeling the fixed charge

Introduce a 0-‐1variable w1. Min y1 + …

w1 = 1 if there is a setup, s.t. y1 = 4w1 + 4x1
24
= 0 otherwise 0 ≤ x1 ≤ 100 w1
w1 = 0 ⇒ x1 = 0 …

Assume 0 ≤ x1 ≤ 100 w1 ∈ {0,1}

 A subtlety in modeling fixed charges

s.t. y1 = 4w1 + 4x1

0 ≤ x1 ≤ 100 w1
w1 ∈ {0,1}

It is permitted that w1 = 1 and x1 = 0. But it is never optimal.

We do not need to forbid this possibility.
 Contoh 1: Capital Budgeting Allocation
StockCompany is considering 6 investments. The cash required from each
investment as well as the NPV of the investment is given. The cash available
for the investments is $14,000. Stockco wants to maximize its NPV. What is
the optimal strategy?
An investment can be selected or not. One cannot select a fraction of an
investment.

Investment 1 2 3 4 5 6

Cash Required
(1000s) $5 $7 $4 $3 $4 $6

NPV added
(1000s) $16 $22 $12 $8 $11 $19
 How to model (additional) “logical” constraints

• Exactly 3 stocks are selected.

• Ans : add constraint → x1 + x2 + x3 + x4 + x5 + x6 = 3
• If stock 2 is selected, then so is stock 1.
• Ans : add constraint → x2 ≤ x1
• If stock 1 is selected, then stock 3 is not selected.
• Ans : add constraint → x1 ≤ (1 – x3) → x1 + x3 ≤ 1
• Either stock 4 is selected or stock 5 is selected, but not
both.
• Ans : add constraint → x4 + x5 = 1
Contoh 2: California Manufacturing Company

• The California Manufacturing Company is a diversified company with

several factories and warehouses throughout California, but none yet
in Los Angeles or San Francisco.
• A basic issue is whether to build a new factory in Los Angeles or San
Francisco, or perhaps even both.
• Management is also considering building at most one new
warehouse, but will restrict the choice to a city where a new factory
is being built.

Question: Should the California Manufacturing Company expand with

factories and/or warehouses in Los Angeles and/or San Francisco?
 Data for California Manufacturing

Net Present Capital

Decision Yes-or-No Decision Value Required
Number Question Variable (Millions) (Millions)
1 Build a factory in Los Angeles? x1 $8 $6
2 Build a factory in San Francisco? x2 5 3
3 Build a warehouse in Los Angeles? x3 6 5
4 Build a warehouse in San Francisco? x4 4 2
Capital Available: $10 million
Binary Decision Variables

Decision Decision Possible Interpretation Interpretation

Number Variable Value of a Value of 1 of a Value of 0
Build a factory in Do not build
1 x1 0 or 1
Los Angeles this factory
Build a factory in Do not build
2 x2 0 or 1
San Francisco this factory
Build a
Do not build
3 x3 0 or 1 warehouse in
this warehouse
Los Angeles
Build a
Do not build
4 x4 0 or 1 warehouse in
this warehouse
San Francisco
 Algebraic Formulation
Let x1 = 1 if build a factory in L.A.; 0 otherwise
x2 = 1 if build a factory in S.F.; 0 otherwise
x3 = 1 if build a warehouse in Los Angeles; 0 otherwise
x4 = 1 if build a warehouse in San Francisco; 0 otherwise

Maximize NPV = 8x1 + 5x2 + 6x3 + 4x4 ($millions)

subject to
Capital Spent: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10 ($millions) Resource Availability
Max 1 Warehouse: x3 + x4 ≤ 1 Mutually exclusive decisions
Warehouse only if Factory: x3 ≤ x1
x4 ≤ x2 Contingent decisions
and
x1, x2, x3, x4 are binary variables.
Contoh 3: Fixed Charge and Facility Example

• Which of six farms should be purchased that will meet current

production capacity at minimum total cost, including annual
fixed costs and shipping costs?
• Data: Plant
Available
Capacity
(tons,1000s)
A 12
Farms Annual Fixed Projected Annual B 10
Costs Harvest (tons, 1000s) C 14
($1000)
1 405 11.2
2 390 10.5 Shipping cost per tons
3 450 12.8 Plant
4 368 9.3 Farm A B C
5 520 10.8
6 465 9.6 1 18 15 12
2 13 10 17
3 16 14 18
4 19 15 16
5 17 19 12
6 14 16 12
Fire Station Problem
Set Covering Problem

Locate fire stations so that

each district has a fire
1 2 3 station in it, or next to it.

5 6
7
4 Minimize the number of
8 9 fire stations needed.

11 12 13
10
14 15 16
Optimization II

Part02a – modeling techniques

komarudin74@ui.ac.id