2
$\begingroup$

If I want to try a greedy randomized adaptive search procedure for the generalized assignment problem (assign N tasks to N workers to minimize the total costs), the GRASP method requires 2 parts

  1. Solution construction
  2. Local search (Best-improving neighborhood search)

enter image description here

For my local search function N(S), what are some other methods to try instead of doing 2 random assignment swaps?

$\endgroup$
3
  • 1
    $\begingroup$ Please use syntax highlighting when necessary, it allows the code to show up during searches. Thanks. $\endgroup$
    – Rob
    Aug 2, 2022 at 1:33
  • $\begingroup$ @gameveloster, maybe this link by fontanf will be useful. $\endgroup$
    – A.Omidi
    Aug 2, 2022 at 6:31
  • 1
    $\begingroup$ @A.Omidi thanks for the mention. The local search algorithm implemented in my generalized assignment repository only relies on the shift neighborhood (not even the swap neighborhood) and is designed to be efficient for very large problems $\endgroup$
    – fontanf
    Aug 6, 2022 at 16:06

1 Answer 1

3
$\begingroup$

Shifts and swaps are already good neighborhoods for the Generalized Assignment Problems:

  • Shift: move a task to another worker
  • Swap: swap the workers of two tasks

Another neighborhood found in some good approaches for the Generalized assignment Problem based on local search is the ejection chain neighborhood.

An additional improvement is to reduce the size of the neighborhoods based on lagrangian multipliers.

For more details about these components, you can look at the following article:

  • Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. European Journal of Operational Research 169:548–569. https://doi.org/10.1016/j.ejor.2004.08.015

Note that a "raw" GRASP scheme is not likely to work very well for the Generalized Assignment Problem since finding a good solution requires a lot of moves and requires to often get out of local optima. If a full restart is performed at the first local optimum found, the initial solution might not have improved enough

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.