LP as a Global Search Heuristic Across Different Constrainedness Regions

Recent years have witnessed the emergence of a new area involving hybrid solvers integrating CP- and OR-based methods. The LP relaxation provides bounds on overall solution quality and can be used for pruning in a branch-and-bound approach, especially in domains where we have a combination of linear constraints, well-suited for linear programming (LP) formulations, and discrete constraints, suited for constraint satisfaction problem (CSP) formulations. However, in a

purely combinatorial

setting, so far it has been surprisingly difficult to integrate LP-based and CSP-based techniques.

We study the behavior of heuristics based on the LP relaxation with respect to the underlying constraindness of the problem. Our study focuses on the Latin square (or quasigroup) completion problem as a prototype for highly combinatorial problems. This problem is NP-hard and it exhibits an easy-hard-easy pattern in complexity, measured in the runtime (backtracks) to find a completion [1]. In our previous work [2] we report an interesting phase transition phenomenon in the

solution integrality

of the LP relaxation for this problem.

We find that simple techniques based on the LP relaxation of the problem provide satisfactory guidance for under- and over-constrained instances. In the critically constrained region, the performance of such simple techniques degrades, due to the inherit hardness of the problem. In this setting, we examine a technique that recomputes the LP relaxation every time a variable is set. This leads to a significant increase in performance, suggesting that carefully designed “one step at a time” LP-based heuristics could provide suitable guidance even for the hardest instances. We examine the quality of the guidance provided by the LP relaxation as a function of the structure of the problem, i.e., we characterize the performance of LP heuristics across different constraindness regions in the search space.