Heurestics for my heurestics

[ace19wre]

Proposal: Using Known Answers to Debug Your Solver

Problem: Defining constraints is tough; you hit things like score traps and constraints that don't play nice or are just ill-defined.

The Idea: Use a problem instance (P) where you already have a high-quality solution (S*) as a benchmark to figure out and fix your solver.

Oracle-Guided Analysis (Figuring out why it's stuck):

When your solver gets stuck (like in the CH/LS phase), compare its current state to the known solution S*.
Use S* like a cheat sheet or "oracle" to diagnose why the solver isn't getting to that good state.
Identify the specific constraints or scoring parts that are stopping it from moving towards S*. (You're mostly looking at this after it runs, not trying to interfere live).

What it's good for: Pinpoints the exact constraints or score calculations that are causing problems when compared to the target solution you want.

Search Trajectory Analysis (Tracking the move-chains):

Log the sequence of moves your solver makes.
Compare the path the solver took to the path needed to reach S*.
Find the exact points where the solver's path deviates or goes off track from a path that would lead to S*.

What it's good for: Shows you how and when the search went wrong, highlighting bad heuristic choices or decision points (the failing move-chains).

Problem Reduction & State Comparison :

If you can reasonably reduce your problem P to a standard structure (like turning it into a Graph Colouring Problem G, where your solution S* is a target colouring C*), do that.
Track how your solver is "colouring" the graph G as it runs (call this state C(t)).
Compare the solver's current colouring C(t) to the target C* to see the differences and visualize the deviation.
Also, look at the structure of the graph G itself – maybe it gives you clues about the problem's difficulty or behaviour or use the structure to see how it evolves with problem size and how diffrent algorithms are able to colour it. Maybe this will reveal how a certain algortitm interact with certain graph structures.

What it's good for: Gives you a different view, might link the graph's structure to how hard the problem is, and gives a visual way to track how far off the solver is.

(Edited to be professional)