IDEAS home Printed from https://ideas.repec.org/h/spr/spochp/978-3-030-28565-4_17.html
   My bibliography  Save this book chapter

A Nested Decomposition Approach for a Large Scale Set Covering Problem: A Model with a Variety of Applications in Industry 4.0

In: Optimization in Large Scale Problems

Author

Listed:
  • Maryam Radman

    (Sharif University of Technology)

  • Kourosh Eshghi

    (Sharif University of Technology)

Abstract

This chapter at first proposes a framework to solve set covering problems (SCPs) with block-angular structures through solving their sub-problems and then develop the method for solving general SCPs without this structure. The proposed framework generates a guaranteed solution for the SCPs with block-angular structure based on a theorem which relates the optimal solution of the original problem to the optimal solutions of its sub-problems. Therefore, since sub-problems involve much fewer constraints and variables than the original problem, the complexity to solve the original SCP is much reduced. In addition, a method to exploit the block-angular structure of SCPs is proposed, using constraint partitioning. The partitioning is based on the fact that the coefficient matrix of SCPs has low density (the number of 1’s is much less than the number of 0’s in the coefficient matrix), so by reordering the rows and the columns, block-angular structures can be created. Our experimental results demonstrate the ability of the proposed approach to exploit the block-angular structures and achieve optimal solutions on sample test problems. In addition, the development of the proposed method to solve SCPs without this structure is examined on benchmark instances of OR-Library.

Suggested Citation

  • Maryam Radman & Kourosh Eshghi, 2019. "A Nested Decomposition Approach for a Large Scale Set Covering Problem: A Model with a Variety of Applications in Industry 4.0," Springer Optimization and Its Applications, in: Mahdi Fathi & Marzieh Khakifirooz & Panos M. Pardalos (ed.), Optimization in Large Scale Problems, pages 165-177, Springer.
    • Handle: RePEc:spr:spochp:978-3-030-28565-4_17
    DOI: 10.1007/978-3-030-28565-4_17
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    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:spr:spochp:978-3-030-28565-4_17. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.