Suppose that the polytope P = { x ∣ A x ≤ b } is totally dual integral (TDI), and that the inequality a ~ T x ≤ b ~ is satisfied at every point of P. Does this imply that the system { A x ≤ b , a ~ T x ≤ b ~ } is TDI?

Question

Suppose that the polytope   P  =  {  x  ∣  A  x  ≤  b  } is totally dual integral (TDI), and that the inequality               a      ~        T    x  ≤      b    ~   is satisfied at every point of   P. Does this imply that the system   {  A  x  ≤  b  ,                    a      ~        T    x  ≤      b    ~    } is TDI?

zwichtsu · Accepted Answer

Total dual integrality is a property of a system and not of a polyhedron. For every rational polyhedron   P there exists a TDI system   A  x  ≤  b such that   P  =  {  x  ∈        R    n       :     A  x  ≤  b  }. You need b to be integral in order to be able to deduce that   P is integral.Adding a redundant inequality to a TDI system results to a TDI system. Consider the primal problem with an integral   c                    max                            .                 c        x                            s        .        t        .                             A        x        ≤        b            Since the Primal system before adding the redundant inequality is TDI there exists an integral optimal solution       u    ′   for the corresponding Dual Problem.Now consider the dual problem                    max        .        u        b                            +        v                        b          ¯                                    s        .        t        .        u        A                            =        c        ,                                     v                        a          ¯                                    =        c        ,                            u        ≥        0        ,                             v        ≥        0            To prove that the Primal system is TDI we have to construct an optimal integer solution u∗ for the Dual problem. Notice that adding a redudant inequality does not change the optimal value of the Primal problem. Then the solution       u    ∗    =  (      u    ′    ,  0  ) is a feasible optimal integral solution for the Dual.Nevertheless adding redundant inequalities to systems which are not TDI may result to a TDI system. The following system is clearly non TDI.                              (                                                    1                                            1                                                                    1                                            −                1                                              )                          (                                                                      x                  1                                                                                                      x                  2                                                              )                ≤                  (                                                    0                                                                    0                                              )                    Still we can produce a TDI system for the same polyhedron by adding a redudant inequality to obtain the TDI system                              (                                                    1                                            1                                                                    1                                            −                1                                                                    1                                            0                                              )                          (                                                                      x                  1                                                                                                      x                  2                                                              )                ≤                  (                                                    0                                                                    0                                                                    0                                              )

Suppose that the polytope P = <mo fence="false" stretchy="false">{ x ∣<!-- ∣

Answered question

Answer & Explanation

New Questions in Algebra I