A unimodular problem of integer programming. (English. Russian original) Zbl 0629.90061

U.S.S.R. Comput. Math. Math. Phys. 26, No. 4, 88-90 (1986); translation from Zh. Vychisl. Mat. Mat. Fiz. 26, No. 7, 1096-1099 (1986).
An applied problem (the so-called reservation model) of integer linear programming with boolean variables is considered. It is shown that the matrix for this problem is unimodular if the bounding matrix is a Petrie matrix. An easy procedure for inverse matrix calculation is proposed. Then, results of computational experiments with a local algorithm in connection with the simplex method for solving unimodular problems of reservation are discussed.


90C10 Integer programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
Full Text: DOI