Some computationally relevant group theoretic structures of fixed charge problems

Among the most commonly occurring mixed-integer problems in operations research are linear programs with fixed charge objective functions. In this paper special structures of the equivalent form of such problems obtained from optimal solutions to their continuous relaxations are characterized and exploited in a series of penalty procedures for branch-and-bound type algorithms. The selection, construction, and solution of such penalty problems are discussed, and computational experience with the procedures is presented.