The Set Covering and Other Problems: An Empiric Complexity Analysis Using the Minimum Ellipsoidal Width

Ivan Derpich, Juan Valencia and Mario Lopez ()
Additional contact information
Ivan Derpich: Industrial Engineering Department, Universidad de Santiago, Ave. Victor Jara 3769, Santiago 9170124, Chile
Juan Valencia: Industrial Engineering Department, Universidad de Santiago, Ave. Victor Jara 3769, Santiago 9170124, Chile
Mario Lopez: Industrial Engineering Department, Universidad de Santiago, Ave. Victor Jara 3769, Santiago 9170124, Chile

Mathematics, 2023, vol. 11, issue 13, 1-22

Abstract: This research aims to explain the intrinsic difficulty of Karp’s list of twenty-one problems through the use of empirical complexity measures based on the ellipsoidal width of the polyhedron generated by the constraints of the relaxed linear programming problem. The variables used as complexity measures are the number of nodes visited by the B & B and the CPU time spent solving the problems. The measurements used as explanatory variables correspond to the Dikin ellipse eigenvalues within the polyhedron. Other variables correspond to the constraint clearance with respect to the analytical center used as the center of the ellipse. The results of these variables in terms of the number of nodes and CPU time are particularly satisfactory. They show strong correlations, above 60%, in most cases.

Keywords: integer programming; branch and bound; combinatorial optimization; set covering problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/13/2794/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/13/2794/ (text/html)

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:gam:jmathe:v:11:y:2023:i:13:p:2794-:d:1176427

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().