[go: up one dir, main page]
Scribd
Upload
1 views12 pages

MILP - Examples I - ST

The document discusses advanced process optimization techniques using Mixed Integer Linear Programming (MILP) with a focus on logical constraints and examples. It outlines methods for formulating constraints, systematic treatment of logic, and provides several problems related to ingredient selection, blending, food manufacturing, commercial allocation, and integer cuts. Key concepts include setting up indicator variables, deriving conjunctive normal forms, and maximizing profits through various optimization scenarios.

Uploaded by

symy9f95dw
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views12 pages

MILP - Examples I - ST

The document discusses advanced process optimization techniques using Mixed Integer Linear Programming (MILP) with a focus on logical constraints and examples. It outlines methods for formulating constraints, systematic treatment of logic, and provides several problems related to ingredient selection, blending, food manufacturing, commercial allocation, and integer cuts. Key concepts include setting up indicator variables, deriving conjunctive normal forms, and maximizing profits through various optimization scenarios.

Uploaded by

symy9f95dw
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

ADVANCED PROCESS OPTIMISATION CENG0023

Mixed Integer Linear Programming


Examples I

Department of Chemical Engineering


University College London
Recap on Integer programming
Logic inference via integer programming

Let xi be the proposition “yi=1”

Then
x1 Ú x2 is equivalent to y1 + y2 ³ 1
x1 • x2 y1 = 1, y2 = 1
~ x1 y1 = 0
x1 ® x2 y1 - y2 £ 0
x1 « x2 y1 - y2 = 0
Summary

• First example showed how to set up an INDICATOR variable so


that
x >1Þ y =1
,
To do this, find a suitable UPPER BOUND (M) on x, and use the
LOGICAL CONSTRAINT
x- M y £0
• Second example showed how to deal with
y =1Þ x > 0
To do this, find a THRESHOLD (m) for x and use the LOGICAL
CONSTRAINT
x - my ³ 0
Summary

• Using similar “tricks”


y =1Þ åajxj £ b
j
is guaranteed by
åa xj
j j + M y £ M +b

where M is a suitable upper bound on åa x


j
j j -b

Also, åa x
j
j j £ b Þ y =1

is handled by å a x - (m - e ) y ³ b + e
j
j j

where e is a TOLERANCE for the constraint and m is a lower


bound on åa xj
j j -b
Exercises

• Logical constraints
• Blending
• Food manufacture (revisited)
• Commercial allocation
• Integer cuts
Systematic Treatment of Logic
To go from arbitrary propositional logic statements into a set of mixed integer
constraints we need to derived their conjunctive normal form (CNF)

A CNF has the form: 𝑄! ∧ 𝑄" … ∧ 𝑄# , where 𝑄$ are


composite clauses.

How to obtain the CNF systematically?

Step 1: Replace any “implication” clause by the equivalent disjunction:


𝑃! ⇒ 𝑃" ⟺ ¬𝑃! ∨ 𝑃"

Step 2: Apply DeMorgan’s theorem to put the negations inward:


¬ 𝑃! ∧ 𝑃" ⇔ ¬𝑃! ∨ ¬𝑃"
¬ 𝑃! ∨ 𝑃" ⇔ ¬𝑃! ∧ ¬𝑃"

Step 3: Distribute logical operators OR/AND recursively using the


equivalence of:
𝑃! ∧ 𝑃" ∨ 𝑃% ⇔ 𝑃! ∨ 𝑃% ∧ 𝑃" ∨ 𝑃%

𝑄! ∧ 𝑄"
Problem 1: Logical constraints
A manufacturing company can purchase up to five ingredients: A, B, C, D and
E. Formulate the following cases as mixed integer linear programming
constraints:

i) Select up to three out of five ingredients.


ii) Select at least two ingredients.
iii) If ingredient E is selected then A or B should be chosen.
iv) If only one from B or C is chosen, then ingredient A should not be selected.
Problem 2: Blending
A blending company needs to purchase up to four out of five ingredients
A, B, C, D and E with unit costs (£/kg) 50, 80, 70, 60 and 90, respectively.
The company has a potential market for the final mixture up to 500 kg,
sold at 200 £/kg. If an ingredient is purchased then a minimum amount of
50 kg should be ordered. Also, due to technical limitations, ingredient A
should not be selected if only one B or C is chosen.
Formulate the above problem as a mixed integer linear programming
model, maximising the profit of the company.
Problem 3: Food Manufacture (revisited)

• Maximum capacities of refining are 200 tons of vegetable oils and


250 non-vegetable oils for each month
• It is possible to store up to 1000 tons of raw oil at the cost of
£5/ton/month
• Manufactured products cannot be stored
• At the beginning of January there are 500 tons of each type of raw
oil in storage, which should exist at end of June
• There is a quality measure called, hardness. Hardnesses of the raw
oils are as below:
VEG 1 8.8
VEG 2 6.1
NON-VEG 1 2.0
NON-VEG 2 4.2
NON-VEG 3 5.0

• Hardness blends linearly and the hardness of the final product must
lie between 3 and 6 9
Problem 3: Food Manufacture (revisited)

Determine:
• In each month, how much raw oils to purchase, used for food
manufacture and sold

So as to:
• Maximise the overall profit (case A)

BUT
• Case B: If an oil is used in a month at least 100 tons must be used
• Case C: The food can be made up to 2 oils in any month

What new variables/constraints are required for cases B and C?


10
Problem 4: Commercials Allocation

Given:
• The estimated impact of allocating zero,
one, two, or three spots to each product.
• This impact is measured in terms of the
profit (in units of millions of £) from the
additional sales that would result from the
spots, considering also the cost of
producing the commercial and purchasing
the spots.
• Note: pij: profit when j TV spots are used
for product i
Determine:
• allocation of five spots to the products

So as to: 11
• maximise the total profit.
Problem 5: Integer Cuts

Many optimisation problems involving integer variables are solved


iteratively (for example, Outer-Approximation solution procedure for
MINLP problems). Usually, one common step of these solution
algorithms is the introduction of an extra constraint (integer cut) at each
iteration in the master problem (0-1 programming problem) in order to
make infeasible the choice of binary vectors obtained from previous
iterations. Develop such an integer cut.

Apply the above constraint to the following Examples:


Yi 1 2 3 4 5
Ex 1 1 1 0 0 1
Ex 2 0 1 1 1 1

You might also like