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

2023
Views:

107

Pages:

5
Author:

Brennen Kline

1 Outline Independence set systems and Matroids Slide 1 Strength of valid inequalities Nonlinear formulations 2 Independence set systems 2.1 Denition N nite set, I collection of subsets of N . (N I ) is an independence system if: (a) 2 I (b) if A B and B 2 I , then A 2 I . Combinatorial structures that exhibit hereditary properties 2.2 Examples Node disjoint paths G = (V E ), I1 collection of node disjoint paths in G. (E I1 ) is IS. Why? Acyclic subgraphs. I2 collection of acyclic subgraphs (forests) in G = (V E ). (E I2 ) is IS. Why? Linear independence A matrix N index set of columns of A I3 collection of linearly independent columns of A. (N I3 ) is IS. Why? Feasible solutions to packing problems. S = fx 2 f0 1gn j Ax bg, A 0, N = f1 2 : : : ng. For x 2 S , A(x) = fi j xi = 1g. I4 = x2S A(x). (N I4 ) is IS. Why? 2.3 Rank (N I ) independence system An independent set of maximal cardinality contained in T N is called a basis of T . The maximum cardinality of a basis of T , denoted by r(T ), is called the rank of T . S T jAj = r(T ): A \ S and A \ (T n S) are independent sets contained in S and T n S r(S) + r(T n S) jA \ S j + jA \ (T n S)j = jAj = r(T ): 1 Slide 2 Slide 3 Slide 4 2.4 Matroids (N I ) is a matroid if: Every maximal independent set contained in F has the same cardinality r(F ) for all F N . (E I1 ) (node disjoint paths in G). Is (E I1 ) a matroid? F = f(1 2) (2 3) (2 4), (4 5), (4 6)g. Maximal independent sets in F : f(1 2) (2 4), (4 5)g and f(1 2) (2 3) (4 5), (4 6)g. Is (E I2 ) of forests a matroid? (N I3 ) of linearly independent columns of A is a matroid. T N index of columns of A, AT = Aj ]j2T . r(T ) = rank(AT ): Is (N I4 ) of feasible solutions to packing problems a matroid? 2.5 Valid Inequalities Slide 5 Slide 6 C N a circuit in (N I ). maximize c0 x X xi jC j ; 1 for all C 2 C subject to i2C P x 2 f0 1gn : Rank inequality i2T xi r(T ) BW contains conditions for rank inequalities to be facet dening. For matroids, rank inequalities completely characterize convex hull. 3 Strength of valid inequalities S set of integer feasible vectors. Pi = fx 2 0 such that P1 P2 . P1 = fx 2 R j x 0g, P2 = fx 2 R j x 1g. Strength ? Slide 7 3.1 Characterization 3.1.1 Theorem P1 P2 if and only if for all c 0, Z2 Z1 where Zi = min c0 x: x 2 Pi . Proof If P1 P2 , then Z2 Z1 for all c 0. For converse, assume Z2 Z1 for all c 0, and there exists x0 2 P1 , but x0 2= P2 . By the separating hyperplane theorem, there exists c: c0 x0 < c0 x for all x 2 P2 , i.e., c0 x0 < Z2 . x0 2 P1, x0 = y0 , y0 2 P1 . Z1 c0 y0 , i.e., Z1 c0 x0 , and thus Z1 < Z2 . Contradiction. t(P1 P2 ) = supc0 ZZ12 : 2 Slide 8 3.1.2 Computation Pi = fx 2 0 with respect to P = fx 2 pij : 4.5.1 Formulation xij is one, if job j is assigned to machine i, and zero, otherwise. P P Cj = mi=1 xij pij + k j xik pik i minimize subject to cij = wj pij , x2ij = xij : X j 2J m X wj m X i=1 xij pij + xij = 1 i=1 xij 2 f0 1g: X k i j xik pik 8j 2 J 8 > <0 if i = 6 h or j = k d(ij) (hk) = > wj pik if i = h and k i j : wk pij if i = h and j i k ZCP = min 12 c0 x + 12 x0 (D + diag(c)) x s:t: m X i=1 xij = 1 0 xij 1: 5 8j 2 J ! Slide 17