4 ms·
Multi-policy-based annealer to solving real combinatorial optimization problems
- whatever1 4y agoMy greedy cheapest first heuristic also solves hard combinatorial problems super fast. It’s only when you check for goodness of solution that you realize that their scope is pretty limited. And dangerous, because you have no clue of how bad your solution is.
- ttul 4y agoAnnealing is such a useful technique. One of my favorite projects from engineering school was in a fourth year VLSI course. The task was to lay out and characterize a simple component using standard cells. Most people chose something pretty small like an AND gate that they could lay out by hand. My partner and I chose to build a relatively monstrous CRC-32, because why not? To generate the layout, I wrote a C++ program that laid out all the standard cells in a random order in one big line, connecting the cells with wires as required to implement the CRC-32 logic. The program used reduced the total wire length by gradually moving cells closer together if they were connected to each other, resulting in a layout with a shorter overall wire length. In VLSI designs, long wires produce high capacitance, delaying signal propagation and causing interference. So you want to keep related things close together. The simple annealing approach worked so incredibly well. We ended up with a weird looking structure [1] that implemented the CRC-32 algorithm to perfection with reasonable capacitance. The professor was puzzled by our design. He thought we laid it out by hand and gave us a poor mark initially, if I recall correctly. This was in the 90s, so we only had stone tools to work with. 1. https://www.dropbox.com/s/2ae2jtu1smo4fxx/crc8layout.eps?dl=0 https://www.dropbox.com/s/2ae2jtu1smo4fxx/crc8layout.eps?dl=...