  This paper compares different exact approaches to solve the Discrete Ordered
Median Problem (DOMP). In recent years, DOMP has been formulated using set
packing constraints giving rise to one of its most promising formulations. The
use of this family of constraints, known as strong order constraints (SOC), has
been validated in the literature by its theoretical properties and because
their linear relaxation provides very good lower bounds. Furthermore, embedded
in branch-and-cut or branch-price-and-cut procedures as valid inequalities,
they allow one to improve computational aspects of solution methods such as CPU
time and use of memory. In spite of that, the above mentioned formulations
require to include another family of order constraints, e.g., the weak order
constraints (WOC), which leads to coefficient matrices with elements other than
{0,1}. In this work, we develop a new approach that does not consider extra
families of order constraints and furthermore relaxes SOC -- in a
branch-and-cut procedure that does not start with a complete formulation -- to
add them iteratively using row generation techniques to certify feasibility and
optimality. Exhaustive computational experiments show that it is advisable to
use row generation techniques in order to only consider {0,1}-coefficient
matrices modeling the DOMP. Moreover, we test how to exploit the problem
structure. Implementing an efficient separation of SOC using callbacks improves
the solution performance. This allows us to deal with bigger instances than
using fixed cuts/constraints pools automatically added by the solver in the
branch-and-cut for SOC, concerning both the formulation based on WOC and the
row generation procedure.
