Simplex-Like Algorithm for Solving Large Scale Linear Optimization Problems with Addition-Min Constraints

In this research project, we continue our study on an optimization problem of minimizing a linear function subject to fuzzy relational inequalities with the addition-min composition. This optimization problem has m decision variables and n constraints of nonlinear inequalities. This optimization setting has recently been proposed to model the network congestion issue when a BitTorrent-like Peer-to-Peer (P2P) file sharing system is used for data transmission. In a 2014 paper, a pseudo-minimal index (PMI) based approach was proposed to search for an optimal solution. It turns out the PMI-based approach may require to solve several to many linear programming problems in order to get an optimal solution. Note that our previous study required only one single linear program to generate an optimal solution for the original optimization problem. Although our single linear program approach is interesting, it still has two disadvantages. First, this LP approach induces mn+m decision variables as well as n+m+2mn linear inequality constraints, which obviously increases the numbers of decision variables and constraints very much. Hence, for large scale case, we need to solve for a very big linear program. Secondly, the decision maker may need to apply a costly commercial solver for solving the linear program problem. In this research project, we plan to develop a Simplex-like algorithm for solving the original optimization problem. Therefore, our new method will handle the problem without inducing many new variables and constraints. Our method would be helpful for those decision makers who do not have the budget to get a commercial solver.

Project ID:PB10507-1733
External Project ID:MOST105-2221-E182-052