<p>The problem of finding the largest cluster in an undirected simple bipartite graph with the maximum number of edges is known as Maximum Edge Bi-clique (MEB) problem. MEB has many applications in several fields like bioinformatics, social networks and data mining. Since the problem has been proved to be NP-complete, the Binary Linear Programming (BLP) is an interesting alternative for solving it. In this paper, a new BLP model is proposed which has fewer variables than previous models which finds a bi-clique with the given size, if exist. First, by identifying and removing redundant constraints from previous models, the BLP model becomes more compact, which in some cases allows it to find larger bi-cliques, improving the overall solution quality. Then, a more efficient quaternary search method is proposed to find the MEB. Afterward, a theorem is proved which helps to reduce the search space of the quaternary search and as a result to reduce the number of calls to the BLP model. Then another theorem is proved which helps to propose 3 models which we call it 3-Binary Linear Programming (3-BLP) procedure. 3-BLP is especially efficient for bipartite graphs in which the difference between the maximum degrees of nodes in two sides of the bipartite graph is large. The experimental results show the superiority of the proposed approaches in terms of speed and accuracy compared to the state of the art.</p>