Integer Program Optimization: Lattices I Notes - Edubirdie

University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

272

Pages:

2
Author:

i2m4ags3

1 Cones 1.1 Deﬁnition A.1 • Cone: subset C of Rn closed under conic combinations, i.e. ∀x, y ∈ C and λ, µ ≥ 0, λx + µy ∈ C. Slide 1 • A cone C is polyhedral if it is ﬁnitely generated, i.e. there exists a ﬁnite set V = {v 1 , . . . , v k } ⊆ Rn such that � C= n y∈R |y= k � � i λi v , λ1 , . . . , λk ≥ 0 i=1 If C is generated by V, we write C = cone(V). • If V ⊆ Qn , cone(V) is called rational. • A cone C is pointed if there exists a hyperplane a� x ≤ 0 such that {0} = {x ∈ C | a� x ≤ 0} 1.2 Observations Slide 2 • Any cone must contain the origin. Why? • A pointed cone does not contain a line. Can a cone contain a line? • Every rational cone polyhedral cone C = cone(V) with V ⊆ Qn can also be represented as C = {x ∈ Rn | Ax ≤ 0} where A ∈ Qm×n . • Recession cones 2 Integral Generating Set Let S ⊆ Z n . Set H ⊆ S is integral generating set if for every x ∈ S, there exists hi ∈ H and λi ∈ Z+ such that x= t � λi hi i=1 • Is an integral generating set hard to deﬁne? • Integral basis: minimal H. • Pointed rational polyhedral cone C, S = C ∩ Z n has a unique integral basis H (Theorem 8.2) and it is ﬁnite (Theorem 8.1). Every point in S can be written as a nonnegative integral combination of at most 2n1 elements of H (Theorem 8.3). 1 Slide 3 3 Theorem 8.5 3.1 Geometrical View Slide 4 max s.t. c� x Ax = b 0≤x≤u x ∈ Zn n Given above, a feasible solution x is optimal if and only if for every h ∈ ∪2j=1 H j either of the following conditions holds: 1. c� h ≤ 0 2. c� h > 0 and x + h not ∈ S j H is integral generating set of C j ∩ Z n , C j = {x ∈ Oj | Ax = 0}, Oj denote all orthants in Rn . 4 Integral Basis Method Slide 5 Uploaded on server. 2

Related Documents

Integer Program Optimization: Lattices I Notes

Integer Program Optimization: Lattices I Notes - Page 1

Integer Program Optimization: Lattices I Notes - Page 2

of 2

Recommended Documents

The Balance Sheet and the Recording of Transactions

The Balance Sheet and the Recording of Transactions

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

The Accounting Process

The Accounting Process

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Intro to Financial & Managerial Accounting Set 2

Intro to Financial & Managerial Accounting Set 2

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Transactions - William's Merchandize Distribution Answers

Transactions - William's Merchandize Distribution Answers

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Financial Statements - the Annual Report

Financial Statements - the Annual Report

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

The Classified Balance Sheet

The Classified Balance Sheet

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Tabular analysis of the effects of various

Tabular analysis of the effects of various

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Mapping the Telecom Value Chain - A Roadmap for Communications Networks

Mapping the Telecom Value Chain - A Roadmap for Communications Networks

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Constructive Conflict, Uncertainty and Real Options

Constructive Conflict, Uncertainty and Real Options

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Strategic Management and Consulting Proseminar Strategic Questions Lufthansa

Strategic Management and Consulting Proseminar Strategic Questions Lufthansa

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Advanced Corporate Risk Management: MW Petroleum (B)

Advanced Corporate Risk Management: MW Petroleum (B)

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Communication for Managers Active Listening Exercise

Communication for Managers Active Listening Exercise

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

New Documents from this Course

Intro to Financial & Managerial Accounting Set 3

Intro to Financial & Managerial Accounting Set 3

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Introduction to Financial and Managerial Accountin Problem Set 2

Introduction to Financial and Managerial Accountin Problem Set 2

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Intro to Financial & Managerial Accounting Set 1

Intro to Financial & Managerial Accounting Set 1

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Introduction to Financial and Managerial Accountin Problem Set 1

Introduction to Financial and Managerial Accountin Problem Set 1

Massachusetts Institute of Technology 15.501/516 | Accounting

Answer Key

Midterm 2 Review Notes

Midterm 2 Review Notes

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note

Marketable Securities (Deferred Taxes)

Marketable Securities (Deferred Taxes)

Massachusetts Institute of Technology 15.501/516 | Accounting

Lecture Note