Latticized Linear Optimization on the Unit Interval

This paper considers the latticized linear optimization (LLO) problem and its variants, which are a special class of optimization problems constrained by fuzzy relational equations or inequalities. We show that an optimal solution to such a problem can be obtained in polynomial time as long as the objective function is a max-separable function with continuous monotone components. We further show that the set of all optimal solutions is fully determined by one maximum optimal solution and a finite number of minimal optimal solutions. The maximum optimal solution can be constructed in polynomial time once the optimal objective value is known, while the detection of all minimal optimal solutions in an efficient manner remains as a challenging problem. The relation between LLO and max-separable optimization and related issues are also investigated.