Integer Program Combination Optimization - Recitation Notes for Lattices II | Massachusetts Institute of Technology

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

2023
Views:

490

Pages:

3
Author:

brina84hlrxw

1 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 � Slide 1 λi hi i=1 • Mistake during the discussion in the previous recitation. 2 Integral Generating Set n C = {x ∈ R | x = � Slide 2 yi ai , yi ≥ 0, ∀i ∈ I} i∈I • Is it a pointed cone? • Is it a polyhedral cone? • Is it a rational cone? • Is it a cone or a recession cone? 3 Geometrical View Slide 3 Is this the cone / integral generating set we are seeking? What is wrong? 1 Slide 4 C = {x ∈ R n | x = � yi ai , yi ≥ 0, ∀i ∈ I} i∈I • C = {x ∈ Rn |x = � i∈I yi ai , yi ≥ 0, ∀i ∈ I} • ai are the blue vectors. Can we use ai as d in d� x ≤ �d� x∗ � ? 2 Slide 5 • Should we consider the pink vector? • x∗ integral ⇐⇒ h�i x∗ integral ∀i • Can we use vector c? 3.1 Comparison I Slide 6 As we apply the methods, does the cone we work with become bigger or smaller? 3.2 Comparison II Beneﬁts of using a integral generating set: Consider x∗ = (15.6, 15.3)� , both h1 = (1, 1)� and h2 = (3, 3)� are within the cone C. h1 : 15.6 + 15.3 = 30.9 h2 : 46.8 + 45.9 = 92.7 3 Slide 7