IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i13p2794-d1176427.html
   My bibliography  Save this article

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

Author

Listed:
  • Ivan Derpich

    (Industrial Engineering Department, Universidad de Santiago, Ave. Victor Jara 3769, Santiago 9170124, Chile
    These authors contributed equally to this work.)

  • Juan Valencia

    (Industrial Engineering Department, Universidad de Santiago, Ave. Victor Jara 3769, Santiago 9170124, Chile
    These authors contributed equally to this work.)

  • Mario Lopez

    (Industrial Engineering Department, Universidad de Santiago, Ave. Victor Jara 3769, Santiago 9170124, Chile)

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.

Suggested Citation

  • Ivan Derpich & Juan Valencia & Mario Lopez, 2023. "The Set Covering and Other Problems: An Empiric Complexity Analysis Using the Minimum Ellipsoidal Width," Mathematics, MDPI, vol. 11(13), pages 1-22, June.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:13:p:2794-:d:1176427
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/13/2794/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/13/2794/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Elhedhli, Samir & Naoum-Sawaya, Joe, 2015. "Improved branching disjunctions for branch-and-bound: An analytic center approach," European Journal of Operational Research, Elsevier, vol. 247(1), pages 37-45.
    2. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    3. Ivan Derpich & Carlos Herrera & Felipe Sepúlveda & Hugo Ubilla, 2021. "Complexity indices for the multidimensional knapsack problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(2), pages 589-609, June.
    4. Belloni, Alexandre & Freund, Robert M, 2007. "A Geometric Analysis of Renegar's Condition Number, and its Interplay with Conic Curvature," Working papers 37303, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    5. Matteo Fischetti & Michele Monaci, 2014. "Exploiting Erraticism in Search," Operations Research, INFORMS, vol. 62(1), pages 114-122, February.
    6. Frank Benda & Roland Braune & Karl F. Doerner & Richard F. Hartl, 2019. "A machine learning approach for flow shop scheduling problems with alternative resources, sequence-dependent setup times, and blocking," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(4), pages 871-893, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    2. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    3. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    4. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    5. Liang Chen & Wei-Kun Chen & Mu-Ming Yang & Yu-Hong Dai, 2021. "An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron," Journal of Global Optimization, Springer, vol. 81(3), pages 659-689, November.
    6. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    7. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    8. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    9. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    10. Jaykrishnan, G. & Levin, Asaf, 2024. "Scheduling with cardinality dependent unavailability periods," European Journal of Operational Research, Elsevier, vol. 316(2), pages 443-458.
    11. Sanchari Deb & Kari Tammi & Karuna Kalita & Pinakeswar Mahanta, 2018. "Review of recent trends in charging infrastructure planning for electric vehicles," Wiley Interdisciplinary Reviews: Energy and Environment, Wiley Blackwell, vol. 7(6), November.
    12. Kenneth J. Arrow & Timothy J. Kehoe, 1994. "Distinguished Fellow: Herbert Scarf's Contributions to Economics," Journal of Economic Perspectives, American Economic Association, vol. 8(4), pages 161-181, Fall.
    13. Kubale, Marek, 1996. "Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors," European Journal of Operational Research, Elsevier, vol. 94(2), pages 242-251, October.
    14. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    15. Danny Nguyen & Igor Pak, 2020. "The Computational Complexity of Integer Programming with Alternations," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 191-204, February.
    16. William Cook & Thomas Rutherford & Herbert E. Scarf & David F. Shallcross, 1991. "An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming," Cowles Foundation Discussion Papers 990, Cowles Foundation for Research in Economics, Yale University.
    17. Egor Ianovski, 2022. "Electing a committee with dominance constraints," Annals of Operations Research, Springer, vol. 318(2), pages 985-1000, November.
    18. Sascha Kurz & Nikolas Tautenhahn, 2013. "On Dedekind’s problem for complete simple games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 411-437, May.
    19. Alberto Caprara & Andrea Lodi & Michele Monaci, 2005. "Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 150-172, February.
    20. D. V. Gribanov & D. S. Malyshev & P. M. Pardalos & S. I. Veselov, 2018. "FPT-algorithms for some problems related to integer programming," Journal of Combinatorial Optimization, Springer, vol. 35(4), pages 1128-1146, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:13:p:2794-:d:1176427. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.