100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Optimization Summary Part 2 $5.85
Add to cart

Summary

Optimization Summary Part 2

 6 views  0 purchase
  • Course
  • Institution

This detailed handwritten summary on Optimization covers key concepts and methods from both lecture notes and tutorial notes. It includes topics such as linear optimization models, simplex methods, duality in optimization, sensitivity analysis, integer linear optimization, and dynamic programming. ...

[Show more]

Preview 2 out of 15  pages

  • June 1, 2024
  • 15
  • 2023/2024
  • Summary
avatar-seller
* additional notes


Lecture 5 Integer Linear Optimization
1. ILo-models :
integer linear optimisation
max[cte Axb , x 0 , integers
>
integrality constraints : ' integer
integer point :
point whose
corresponding vector has integer-valued entries

*Lo-relaxation removing the integrality constraints from 120-model
:


maxEci Axeb <03 >Maxi Axeb xo x integer 1 , , ,




.
2 MILo-models : mixed integer linear optimisation
max (, x , + C2
S t . .
A , 34 + AzTz = D
30
>0 & integer
with A: myn , matrix
A2 : My He Matrix


similarly to 10-model ,
10-relaxation applies

.
3 Branch & Bound divide I conquer approach
1) start with solve the 10-relaxation &
(2) If solution is integer-valued then stop coptimal sol found) ·
-




else divide feasible region of 10-relaxation
,
Fo into 2 sub-regions
Flor & Floe

with Froi FloFlozE Flo
"
: E

Fro 1 1 Flor = 0 disjoint
10 sol. no longer feasible
i (FOUFO) FU Fo2 some
current sol. no longer in either #
v .


(F1L8 : U Filo2) =
FiLo all integer sol Still in either F
.




Fo
~

Flor FLOz all integer solutions
Still in either Foe/Froz

Since
omitted current solution excluded


* implicit enumeration of all integer solutions
* Branch
& cut :
cut constraints are added during the iterations of the branch bound
algorithm
to
yield better upper bounds on the optimal objective value
than branch & bound can provide alone

, example :
dairy corp.
M1 : max 10007 , + 700x2
S t
.
.
2072 :510
100x +
50x = 2425
Th , The 0
Tho =
[11 ,
2512] found graphically
z10 =
. 35
29
12 = 25 12726
L Y

M2 :
max 1000 , + 7001 Mz :
Max 1000, + 7007
S t .
.

2072 1510 S t .
.

2072 1510
10834 + 507 = 2425 10834 + 507 = 2425
12 =
25 T2 26
7 (20,
7 (20
,

T40 =
[11314, 25] infeasible ,
constraints 1d5 violate
zo =
29 25 .
each other

now branch on :
(11 ,
The 12


* problem is partioned if LP-feasible & fractional with better bound

zo ; = Z10 ; = Epst = E *0 = Evol

4.
integer knapsack problem

given are n type of items with value C & volume weight a
for j =
1, ....
n
find a selection of items with maximal value that fits knapsack
with capacity b
assume items are ordered S t . d , de .

,
Y . .
. On
an
- 1st item in the rank is the most valuable

: number of items selected of type ;
x =




max([
; [ = b , , 0 & integer Vi





&




.
5 Dinary knapsack problem

same layout as integer problem ,
but now :




Xi =
1 if item i is selected &O otherwise
max([i ; [ D Teso 13/ 3 =
,
,




6 continuous knapsack problem

same layout as
binary problem but ,
now :




max[[(j1; [jajj =b ,
0
< 1 fil

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller lucia2001. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $5.85. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

53068 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$5.85
  • (0)
Add to cart
Added