A Revisit to the Generalized Assignment Problem: An ascending hyper-plane approach through network flows

Abstract

This paper presents an ascending hyperplane approach for solving the generalized assignment problem (GAP). The GAP model is first relaxed to form a transportation model which is easier to handle than the original model. This relaxed model is then formulated as a Minimum-Cost Network Flow Problem (MCNFP) and an efficient network simplex method applied to solve the relaxed problem. The optimal solution of the relaxed model gives a lower bound (LB) to the given GAP. The LB becomes an optimal solution to the GAP, if all resource constraints are satisfied. However, if any resource constraint is not satisfied, that violation is used to determine the new (LB), which is greater than the previous one and hence the ascending hyper-plane approach. These violated resource constraints in the given GAP model and are used to modify the MCNFP diagram before resolving the flow problem. This procedure is repeated until all resource constraints are satisfied in the original GAP model. The proposed method is efficient for the generalized assignment problem. Keywords : Generalized assignment problem, Transportation model, Minimum-cost-network flows, Network algorithm.

View PDF