Combinatorial Algorithm for Tropical Linearly Factorized Programming

The tropical semiring is an algebraic system with addition ``$\max$'' and multiplication ``$+$''. As well as in conventional algebra, linear programming in the tropical semiring has been developed. In this study, we introduce a new type of tropical optimization problem, namely, tropical linearly factorized programming. This problem involves minimizing the objective function given by a product of tropical linear forms divided by a tropical monomial, subject to tropical linear inequality constraints. As the objective function is equivalent to the dual of the transportation problem, it is convex in the conventional sense but not in the tropical sense, while the feasible set is convex in the tropical sense but not in the conventional sense. Our algorithm for tropical linearly factorized programming is based on the descent method. We first show that a feasible descent direction can be characterized in terms of a specific digraph, called a tangent digraph. Especially in non-degenerate cases, we present a simplex-like algorithm that updates the tree structure of tangent digraphs iteratively. Each iteration can be executed in $O(r_A+r_C)$ time, where $r_A$ and $r_C$ are the numbers of finite coefficients in the constraints and objective function, respectively. For integer instances, our algorithm finds a local optimum in pseudo-polynomial time.