Integer Program Optimization: Duality I Notes - Edubirdie

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

2023
Views:

54

Pages:

2
Author:

Rebecca Chaney

1 Lattices 1.1 Objectives Slide 1 max s.t. � cx Ax = b 0≤x≤u x ∈ Zn • What if A is fulldimensional? • Solvable in polynomial time when n is ﬁxed! • Exploit discrete character of solution space vs. continuous relaxation in earlier chapters • Geometrical picture 1.2 Deﬁnitions B ∈ Rn×d matrix with linearly independent column vectors Slide 2 L = L(B) := {y ∈ Rn | y = Bv, v ∈ Z d } L(B): lattice generated by B B: basis of L(B) • See diagram of lattice • Closed under addition of its elements (elements = column vectors) • A full column rank: S = {x ∈ Z n |Ax = b} �= ∅ if and only if b ∈ L(A) 1.3 Integer Normal Form • Deﬁnition 6.2: A ∈ Z m×n of full row rank is in integer normal form if it is of the form [B, 0] where A ∈ Z m×n is invertible and is lower triangular. Slide 3 • Theorem 6.3: A ∈ Z m×n of full row rank: 1. A can be brought into integer normal form using elementary column op erations. 2. ∃ unimodular U such that [B, 0] = AU 1.4 Theorem 6.4 Slide 4 n S = {x ∈ Z |Ax = b} [B, 0] = AU 1. S is nonempty if and only if B−1 b ∈ Z n−m . 1 2. If S = � ∅, every solution of S is of the form x = U1 B−1 b + U2 z, z ∈ Z n−m , where U1 , U2 are submatrices of U, such that U = [U1 , U2 ]. 3. L = {x ∈ Z n | Ax = 0} is a lattice and the column vectors of U2 constitute a basis of L. 1.5 Theorem 6.5 Slide 5 Integral Farkas Lemma 1. S = ∅ if and only if there exists a y ∈ Qm , such that y� A ∈ Z m and y� b is not in Z m 2. S = ∅ if and only if there exists a y ∈ Qm , such that y ≥ 0, y� A ∈ Z m and y� b is not in Z m 2

Related Documents

Integer Program Optimization: Duality I Notes

Integer Program Optimization: Duality I Notes - Page 1

Integer Program Optimization: Duality 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