A new algorithm for minimizing a linear objective function with fuzzy relation equation constraints (Q835216)

The paper is concerned with the following optimization problem \[ \text{Min\,}Z({\mathbf x})= \sum^m_{j=1} c_j{\mathbf x}_j\tag{1} \] \[ \text{subject to }A\circ{\mathbf x}^T={\mathbf b}^T,\tag{2} \] where \(A= [a_{ij}]\), \(i= 1,2,\dots, n\); \(j= 1,2,\dots, m\); \({\mathbf x}= [x_1x_2\cdots x_m]\), \({\mathbf b}= [b_1 b_2\cdots b_n]\) with \(\circ\) being the max-min composition and \(a_{ij}\), \(x_j\), \(b_i\in [0,1]\) while \(0< c_1\leq c_2\leq\cdots\leq c_m\); \(b_1\geq b_2\geq\cdots\geq b_n\geq 0\). The optimal solution to the above problem is among the minimal solutions to the system of fuzzy relational equation (2). In contrast to the two main alternatives encountered in the literature (viz. (i) enumeration and (ii) 0-1 integer programming), the approach presented in the study is based on algebraic manipulation. A complete algorithm is provided. Constructed is a space of k-form chained solutions and it is shown that the optimal solution can be found as an element of this space. Two illustrative examples are presented.