RT journal article
T1 Constraint relaxation for the discrete ordered median problem
A1 Ponce, Diego
A1 Martínez Merino, Luisa Isabel
A1 Puerto, Justo
A2 Estadística e Investigación Operativa
K1 Branch-and-cut
K1 Constraint relaxation
K1 Discrete ordered median problem
K1 Row generation
AB 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.
PB Springer
SN 1134-5764
YR 2022
FD 2022-12-18
LK http://hdl.handle.net/10498/29389
UL http://hdl.handle.net/10498/29389
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 11-nov-2026