Integer Program Combination Optimization - Ideal Formulations I | Massachusetts Institute of Technology

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

2023
Views:

381

Pages:

6
Author:

Russell Velez

1 Outline Slide 1 Total unimodularity Dual Methods 2 Total unimodularity Slide 2 S = fx 2 Z+n j Ax bg, A 2 Z m�n and b 2 Z m . P = fx 2 <+n j Ax bg. When P = conv(S) for all integral vectors b? 2.1 Cramer's rule Slide 3 A 2 0 j 2 N ( )S y c N: S f S y X subject to ck+1 j S ::: 2 N N: cn . S j = f1 : : : j g for S j= x ( j ) ; f (S j;1 ) 0 c y x is integer, for 1 j k for j > k: for S = S j 1 j < k for S = S k otherwise : f S 8 j; < S= : 0k c Slide 18 j+1 c j0 x 5 Slide 20 j 2 N , and X j2T j = x X ; fj j j2T jkg ; X fj j j2T jkg ( j ) ; f (S j;1 ) f S ( j \ T ) ; f (S j;1 \ T ) f S = f (S k \ T ) ; f () f (T ) ; f () = f (T ): y is dual feasible because X fS j j2Sg S 0 and y S = ySj + + ySk = cj y X fS j j2Sg Primal objective value: Dual objective value: Pk S = 0 cj y k if j > k: ; j j;1 j=1 cj f (S ) ; f (S ) k;1 X k ; X j=1 j=1 (cj ; cj+1 )f (S j ) + ck f (S k ) = if j c j f (S j ) ; f (S j;1 ) : 3.5 Matroids (N I ) independence system, r(T ) = maxfjS j : X maximize cj xj subject to j2N X xj r (S ) j2S xj 2 f0 1g: 8 S S 2 I S T g: Slide 21 N Theorem: (N I ) independence system. It is a matroid if and only if its rank function r(S ) = maxfjS j : S 2 I S T g is submodular. 3.6 Greedy algorithm 1. Given a matroid (N I ), and weights cj for j 2 N , sort all elements of N cj . Let J = k = 1. in decreasing order of cj : cj1 cj2 2. For k = 1 : : : m, if J fjk g is an independent set, let J = J fjk g 3. An optimum solution is given by the set J . n 6 Slide 22