Optimizing linear functions over novel fuzzy relation equations: Structure, feasibility, and global solutions

We investigate the linear objective function optimization problem constrained by a new system of fuzzy relationequations, utilizing the minimum t-norm for fuzzy compositions. Our findings reveal that the feasible region ischaracterized as a finite union of closed convex cells. We provide necessary and sufficient conditions to determinethe problem’s feasibility. To streamline optimization, seven novel rules are proposed, on which an algorithm is basedto achieve a global optimum. Notably, a specific instance of our problem is shown to be equivalent to the well-knownminimal vertex cover problem. The efficacy of our algorithm is demonstrated through a concrete example.

Keywords:

linear optimization , Fuzzy relational equations , minimal vertex covering