SEMI-ANALYTICAL APPROXIMATION OF THE SET PARTITION PROBLEM USING THE HOMOTOPY ANALYSIS METHOD

Abstract

The Set Partition Problem (SPP) is a classical NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, cryptography, and operations research. In this work, a semi-analytical framework based on the Homotopy Analysis Method (HAM) is developed for approximating solutions of the SPP. The discrete partitioning problem is first reformulated as a constrained continuous optimization problem using Lagrange multipliers. A homotopy is then constructed between an initial guess and the full nonlinear system, and a Padé $[1, 1]$ series representation is employed to obtain approximate analytical solutions. The resulting algebraic equations are solved up to second order in the homotopy parameter, and the explicit Taylor-series derivation of these equations is given, together with a discussion of the conditions under which the resulting linear system for the Padé coefficients becomes degenerate. A numerical example involving a six-element set is investigated, and the influence of the convergence-control parameter on a constraint-violation residual is analyzed statistically over multiple random initial guesses, using a statistically motivated outlier criterion. The results show that the residual varies non-monotonically with the convergence-control parameter, with no clearly defined convergence region, and that the rounded partition assignments obtained from the second-order Padé approximation fail to satisfy the exact partition condition for the tested samples. The study illustrates the potential and, in its present second-order form, the significant limitations of semi-analytical homotopy techniques when applied to NP-hard combinatorial optimization problems. Furthermore, it identifies higher-order approximations and pole-avoidance strategies as necessary directions for improvement.