A decomposition scheme for matrices: Application to the resolution of linear integer programs

Recognizing a network matrix is known to define a polynomial problem. From a new characterization of these matrices, the paper deduces a decomposition scheme for general -matrices, and it shows how this scheme can be part of a resolution process for linear integer programs based upon the idea of transferring of integrality constraints from the original unknown vector to a somewhat smaller control vector.