Computation of Atomic Fibers of Z-Linear Maps

الأصل · EN

For given matrix A∈ᵈ× ⁿ, the set Pⁱₐ,b={z:Az=b,z∈ⁿ+} describes the preimage or fiber of b∈ᵈ under the -linear map fₐ:ⁿ+→ᵈ, x Ax. The fiber Pⁱₐ,b is called atomic, if Pⁱₐ,b=Pⁱₐ,b₁+Pⁱₐ,b₂ implies b=b₁ or b=b₂. In this paper we present a novel algorithm to compute such atomic fibers. An algorithmic solution to appearing subproblems, application to integer programming, and computational examples are included as well.