Interval global optimization problem in max-plus algebra

Consider the global optimization problem of minimizing the max-plus product A circle times x, where A is a given matrix and the constraint set is the set of column vectors x such that the sum of products kjxj is equal to c and cis a given positive real constant, kjare non-negative numbers with sum equal to 1. We show that the solvability of the given global optimization problem is independent of the number cif the components of the vector x can also be negative. From a practical point of view, we further consider the solvability of the global optimization problem with non-negative constraints. We propose an algorithm which decides whether a given problem is solvable, extend the problem to interval matrices and provide an algorithm to verify the solvability of interval global optimization problem. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.