CODEWITHSUNDEEP
searchoptimizationcplexneighbours
A321
A321

Reputation: 17

Application of Neighborhood search in CPLEX

I implemented a mixed integer problem directly in CPLEX. My problem is that it takes to long for my purposes to find a optimum solution. I set a time limit oF 10 minutes. So after 10 minutes I get a feasible solution but I don´t how far it is away from the optimum. Now I read about a Variable Neighborhood Search, which makes optimization a lot faster while "promising" a near optimum solution. As far as I know, CPLEX does not directly offer VNS, but it is able to perform a Relaxed Induced Neighborhood Search (RINS). Two question about this:

  1. How do I apply it?
  2. Does it have the same effect as the VNS (find near optimal solutions in short time)

Thanks a lot! Sincerely

Upvotes: 0

Views: 253

Answers (1)

TimChippingtonDerrick
TimChippingtonDerrick

Reputation: 2072

For various types of neighbourhood search, you are largely on your own in that there isn't much that works well built into any of the big commercial solvers. However at one level it is really very easy to experiment with it.

Assume that you already have a feasible solution to your problem. Then you can create a new smaller problem by re-solving your original problem but with most of the variables in your model fixed to the values from your known solution - you might choose to fix 90%, 95% or 99% of your variable values. That will leave a much smaller number of variables for the solver to find values and it will typically find an optimal solution to your 'sub-problem' in a few seconds, and it can sometimes find a better set of values for those variables that you didn't fix or freeze in your model. You can safely replace the values of those variables in your current best known solution with their new values because you are guaranteed that those values are compatible with the rest of your solution. Then choose a different set of variables to fix/freeze and do it again, and keep repeating this process.

The art and craft of making this work well for your problem is how you choose which variables to fix/freeze and which to re-solve. The more variables that you leave un-fixed, the larger the 'neighborhood' around your previous solution and the more opportunities there are for finding an improvement, but each sub-problem takes longer to solve. There will be some sweet spot of sub-problem size that works well, but you will have to experiment to see what works. Similarly it helps to leave related variables un-fixed in your sub-problem. You could just choose them at random and the process will still converge but it will be slower; it is better to think about your problem structure, e.g. relax and re-solve one day's worth of variables in a schedule, or the variables for one or more resource, or whatever. Again it depends on your problem.

Upvotes: 1

Related Questions