A Cutting Plane Algorithm for the Linear Ordering Problem

摘要: The linear ordering problem is an NP-hard combinatorial optimization with a large number of applications including triangulation input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation individual preferences. In former paper, we have investigated the facet structure 0/1-polytope associated problem. Here report on new algorithm that based these theoretical results. main part cutting plane procedure using defining inequalities. This combined various heuristics branch bound techniques. Our computational results compare favorably existing codes. particular, could triangulate all size up to 60 × 60, available us within acceptable bounds.