𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A new Lagrangian net algorithm for solving max-bisection problems

✍ Scribed by Fengmin Xu; Xusheng Ma; Baili Chen

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
211 KB
Volume
235
Category
Article
ISSN
0377-0427

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

A new Lagrangian dual global optimizatio
A new Lagrangian dual global optimization algorithm for solving bilinear matrix inequalities
✍ H. D. Tuan; P. Apkarian; Y. Nakashima πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 202 KB πŸ‘ 2 views

A new global optimization algorithm for solving bilinear matrix inequalities (BMI) problems is developed. It is based on a dual Lagrange formulation for computing lower bounds that are used in a branching procedure to eliminate partition sets in the space of complicating variables. The advantage of