Litterature reference for auto scheduling

[matthieu-pa]

First thank you for this implementation of SA! Its flexibility allowed me to get really good results in a few hours on the Quadratic Knapsack Problem by implementing two simple moves.

I was wondering if the auto scheduling from below is something you came up on your own or something which can be found in the literature? If it is from the literature, could you give me the references?

https://github.com/perrygeo/simanneal/blob/951e7d89a8b7f19aeb05b64e7cc8b844a734af89/simanneal/anneal.py#L238

Thank you for your time.

[perrygeo]

Hi Matthieu,

The Annealer.auto method is a heuristic which assumes the ideal temperature schedule will start at 98% acceptance and proceed to 0% acceptance. And it uses empirical results to estimate it. There is no literature on the topic that I'm aware of, only code.

Speaking of which, would you be willing to open source (or blog about) your Quadratic Knapsack Problem solution? I'm very interested in seeing how simanneal is being used in real applications.

Take care,

Matt Perry

On Tue, Jan 26, 2021 at 10:14 PM Matthieu Parizy notifications@github.com wrote:

First thank you for this implementation of SA! Its flexibility allowed me to get really good results in a few hours on the Quadratic Knapsack Problem by implementing two simple moves.

I was wondering if the auto scheduling from below is something you came up on your own or something which can be found in the literature? If it is from the literature, could you give me the references?

https://github.com/perrygeo/simanneal/blob/951e7d89a8b7f19aeb05b64e7cc8b844a734af89/simanneal/anneal.py#L238

Thank you for your time.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/perrygeo/simanneal/issues/41, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAIZCNZXPGY2MZ7YCGVDIYLS36OK5ANCNFSM4WUT7JBA .

[matthieu-pa]

Thank you for your reply,

I am writing a paper on solving the Quadratic Knapsack Problem with different methods, one of them being SA. I will forward it to you once it is hopefully published.

The way I implemented the move() method was:

1. try to add a random item among those which would not violate the capacity constraint.
2. If no item adding is possible without violation the constraint, try to swap 2 random items until I find a pair which would satisfy the constraint.

To make the move "fast" I use np.dot() to evaluate in parallel capacity and profit of each variable if it were removed/added.

I haven't finished benchmarking but I setup Tmax to the maximum worse ΔE possible, e.g the maximum row(column) sum value between each variable in the symmetrized profit matrix, divided by 10. I repeat short burst of SA with steps between 500 and 1500 depending on the instance.