A discrete filled function algorithm for approximate global solutions of max-cut problems |
| |
Authors: | Ai-Fan Ling Cheng-Xian Xu Feng-Min Xu |
| |
Institution: | aDepartment of Mathematics, Faculty of Science, Xi’an Jiaotong University, Xi’an 710049, PR China;bSKLMSE Lab., Xi’an Jiaotong University, PR China |
| |
Abstract: | A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut problems, the parameters in proposed filled function need not be adjusted. This greatly increases the efficiency of the filled function method. By combining a procedure that randomly generates initial points for minimization of the filled function, the proposed algorithm can greatly reduce the calculation cost and be applied to large scale max-cut problems. Numerical results on different sizes and densities test problems indicate that the proposed algorithm is efficient and stable to get approximate global solutions of max-cut problems. |
| |
Keywords: | Combinatorial optimization Global optimization Filled function Max-cut problem Neighborhood local search |
本文献已被 ScienceDirect 等数据库收录! |