Properties of Some Combinatorial Optimization Problems and Their Effect on the Performance of Integer Programming and Constraint Logic Programming

Abstract

The comparative performance of Integer Programming (IP) and Constraint Logic Programming (CLP) is explored by examining a number of models for four different combinatorial optimization applications. Computational results show contrasting behavior for the two approaches, and an analysis of performance with respect to problem and model characteristics is presented. The analysis shows that tightness of formulation is of great benefit to CLP where effective search reduction results in problems that can be solved quickly. In IP, if the linear feasible region does not identify the corresponding integer polytope, the problem may be difficult to solve. The paper identifies other characteristics of model behavior and concludes by examining ways in which IP and CLP may be incorporated within hybrid solvers.