Integer Program Combination Optimization - Recitation Notes for Duality I | Massachusetts Institute of Technology

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