Combining data reduction, MIP solver and iterated local search for generalized assignment

ABSTRACT

This work is motivated by a memory allocation problem (MAP) in an embedded system which is modeled as a generalized assignment problem (GAP) with side constraints. Thus, this paper aims to design a fast and sufficiently accurate method for GAP that will be used in future research to obtain a solution for MAP. Since this solution barely satisfies the conflict constraints, it will be repaired and then improved using local search . In the current research, the proposed method for GAP combines data reduction, a MIP solver, and iterated local search (ILS). The generic data reduction procedure is based on useful information provided by applying subgradient optimization to the Lagrangian relaxation of the knapsack constraints. In practice, it can eliminate up to $96\mathrm{\%}$ of GAP variables. The reduced GAP left by this procedure is small and sparse. Furthermore, its optimal solution can be easily extended to an optimal or near-optimal solution of GAP. An ILS metaheuristic is designed for solving the reduced GAP and the entire method is tested on a widely used benchmark of large and difficult instances. Its comparison with recently published methods shows that it is competitive in terms of solution quality; it is also by far the fastest.

KEYWORDS:

• Generalized assignment problem
• data reduction
• iterated local search
• MIP solver

AMS CLASSIFICATION:

• 90B35
• 90B40
• 90C27
• 90C59

Disclosure statement

No potential conflict of interest was reported by the author(s).