Applications of Mathematics, Vol. 65, No. 6, pp. 755-775, 2020
Complete solution of tropical vector inequalities using matrix sparsification
Received December 28, 2019. Published online September 16, 2020.
Abstract: We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.