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

Shcherbina, O. A.

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.

MSC:

90C10	Integer programming
90C05	Linear programming
65K05	Numerical mathematical programming methods

Keywords:

integer linear programming; unimodular; computational experiments; local algorithm