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

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