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

  • Guu, Sy-Ming (PI)

Project: National Science and Technology CouncilNational Science and Technology Council Academic Grants

Project Details


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 IDs

Project ID:PB10507-1733
External Project ID:MOST105-2221-E182-052
Effective start/end date01/08/1631/07/17


  • Fuzzy relational


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.