I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction. I have came across the Min-Conflicts Algorithm which proved to be rather efficient in the context of the problem. However, I have recently chanced upon the Coordinate Descent Algorithm and how strikingly it resembles the Min-Conflicts Algorithm. Probably the only difference is that in Min-Conflicts, a random variable is selected to be modified at each step whereas Coordinate Descent cycles through the variables.Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent? If so why are classified differently?
Similarity between Min-Conflicts and Coordinate Descent in CSPs?
optimization;constraint satisfaction
Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent? In the same sense that A* and BFS are essentially equivalent except for the choice of which node to visit next, yes.If so why are classified differently?There are some problems for which Min-Conflicts performs asymptotically faster (in the expected-time sense) than Coordinate Descent, and vice versa. Ditto, there are some problems where one (generally) converges and the other (generally) doesn't.