I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions.

This means I need different ways of creating neighbours of my current solution. The obvious method is to pick some object and toggle its state (pack if not packed and vise versa). I can not think of any other method though and wonder if its just me missing anything or if there is genuinely no other way to get a sensible neighbourhood.

My demands to this operation to create a neighbourhood are that they must be able to create all possible solutions after a finite amount of iterations. So by toggling any object a finite amount of time on the finite list of objects, for example, I can obviously create all possible solutions (feasible or not) for the knapsack problem. So any offered operator must be able to at least procure all feasible and may also create unfeasible solutions to the instance.

Can you think of any such operators except for the toggling of some object in the solution?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.