The Group-Theoretic Structure in the Fixed-Charge Transportation Problem

The multiparametric integer programming problem for the right-hand side is to minimize c′t subject to At = b(y), t ≧ 0, t = 0 (mod 1), where b(y) can be expressed in the form b(y) = b̄ + F(y), where F is a matrix of constant coefficients, and y is an integer vector parameter. The group problem associated with any integer programming problem may be viewed as a multiparametric integer programming problem. The purpose of this paper is to show that the group problem associated with the fixed-charge transportation problem can be viewed as a multiparametric integer programming problem having a totally unimodular constraint matrix.