Some popular heuristics for combinatorial optimisation start by constructing a feasible solution to a dual of the problem. We show that such dual-based heuristics can exhibit highly counter-intuitive behaviour. In particular, for some problem classes, solving the dual exactly invariably leads to much worse primal solutions than solving the dual with a simple greedy heuristic. We provide a tentative explanation for this phenomenon, based on the concept of primal degeneracy. We use the simple plant location and set covering problems as examples.
Citation
Working paper, Department of Management Science, Lancaster University, Lancaster LA1 4YX, UK.