Binary programs for asymmetric betweenness problems and relations to the quadratic linear ordering problem

Abstract

We present and compare novel binary programs for linear ordering problems that involve the notion of asymmetric betweenness and expose relations to the quadratic linear ordering problem and its linearization. While two of the binary programs prove particularly superior from a computational point of view when many or all betweenness relations shall be modeled, the others arise as natural formulations that resemble important theoretical correspondences and provide a compact alternative for sparse problem instances. A reasoning for the strengths and weaknesses of the different formulations is derived by means of polyhedral considerations with respect to their continuous relaxations.

Keywords

• Linear ordering problem
• Betweenness problem
• Facility layout problem
• Mixed-integer programming
• Binary quadratic programming