Variable Neighborhood Descent Branching applied to the Multi-Way Number Partitioning Problem | Zendy

Alexandre Frias Faria | Zendy; Sérgio Ricardo de Souza | Zendy; Elisangela Martins de Sá | Zendy; Carlos Alexandre Silva | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Variable Neighborhood Descent Branching applied to the Multi-Way Number Partitioning Problem

Author(s) -

Alexandre Frias Faria,

Sérgio Ricardo de Souza,

Elisangela Martins de Sá,

Carlos Alexandre Silva

Publication year - 2019

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2019.08.039

Subject(s) - disjoint sets , descent (aeronautics) , mathematics , branching (polymer chemistry) , mathematical optimization , variable (mathematics) , interval (graph theory) , sequence (biology) , algorithm , combinatorics , mathematical analysis , materials science , biology , engineering , composite material , genetics , aerospace engineering

This paper presents an application of the Variable Neighborhood Descent Branching method to solve the Multi-Way Number Partitioning Problem. This problem consists of distributing the elements of a given sequence into k disjoint subsets such that the sums of each subset elements fit in the shortest interval. It shows a new method to decompose the MWNPP in n−1 subproblems using local branching constraints. This decomposing justifies the neighborhood structure used in the proposed algorithm. The study of parameter settings defines the operation of the proposed algorithm. The results shows that there is no statistically significant difference of objective value between proposed algorithm and mathematical model solved by CPLEX, but the time used by both methods are significantly different.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research