The max‐bisection problem is an NP‐hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max‐bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large‐scale G‐set problems show that the proposed method can find a better optimal solutions.
