Constraint relaxation for the discrete ordered median problem

Luisa I. Martínez-Merino (), Diego Ponce () and Justo Puerto ()
Additional contact information
Luisa I. Martínez-Merino: Universidad de Cádiz
Diego Ponce: Instituto de Matemáticas de la Universidad de Sevilla (IMUS)
Justo Puerto: Instituto de Matemáticas de la Universidad de Sevilla (IMUS)

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2023, vol. 31, issue 3, No 4, 538-561

Abstract: Abstract 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.

Keywords: Discrete ordered median problem; Branch-and-cut; Constraint relaxation; Row generation; 90-04; 90-08; 90B80; 90C10; 90C57 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-022-00651-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:31:y:2023:i:3:d:10.1007_s11750-022-00651-3

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-022-00651-3

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().