IDEAS home Printed from https://ideas.repec.org/a/hin/complx/8405036.html
   My bibliography  Save this article

A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems

Author

Listed:
  • Nitish Das
  • P. Aruna Priya

Abstract

The many-to-many assignment problem (MMAP) is a recent topic of study in the field of combinatorial optimization. In this paper, a gradient-based interior-point method is proposed to solve MMAP. It is a deterministic method which assures an optimal solution. In this approach, the relaxation of the constraints is performed initially using the cardinality constraint detection operation. Then, the logarithmic barrier function (LBF) based gradient descent approach is executed to reach an accurate solution. Experiments have been performed to validate the practical implementation of the proposed algorithm. It also illustrates a significant improvement in convergence speed for the large MMAPs (i.e., if group size, ) over state-of-the-art literature.

Suggested Citation

  • Nitish Das & P. Aruna Priya, 2019. "A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems," Complexity, Hindawi, vol. 2019, pages 1-13, July.
    • Handle: RePEc:hin:complx:8405036
    DOI: 10.1155/2019/8405036
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/8503/2019/8405036.pdf
    Download Restriction: no
    File URL: http://downloads.hindawi.com/journals/8503/2019/8405036.xml
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2019/8405036?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Nikolaos Ploskas & Nikolaos Samaras, 2017. "Interior Point Methods," Springer Optimization and Its Applications, in: Linear Programming Using MATLAB®, chapter 0, pages 491-540, Springer.
    2. Yossi Hadad & Baruch Keren, 2016. "A revised method for allocating the optimum number of similar machines to operators," International Journal of Productivity and Performance Management, Emerald Group Publishing Limited, vol. 65(2), pages 223-244, February.
    3. Belik, Ivan & Jörnsten, Kurt, 2014. "A New Semi-Lagrangean Relaxation for the K-Cardinality Assignment Problem," Discussion Papers 2014/1, Norwegian School of Economics, Department of Business and Management Science.
    4. Walter Murray & Kien-Ming Ng, 2010. "An algorithm for nonlinear optimization problems with binary variables," Computational Optimization and Applications, Springer, vol. 47(2), pages 257-288, October.
    5. David G. Luenberger & Yinyu Ye, 2016. "Linear and Nonlinear Programming," International Series in Operations Research and Management Science, Springer, edition 4, number 978-3-319-18842-3, December.
    6. Paul Armand & Riadh Omheni, 2017. "A Mixed Logarithmic Barrier-Augmented Lagrangian Method for Nonlinear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 173(2), pages 523-547, May.
    7. Richard W. Cottle & Mukund N. Thapa, 2017. "Linear and Nonlinear Optimization," International Series in Operations Research and Management Science, Springer, number 978-1-4939-7055-1, 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. François Le Grand & Xavier Ragot, 2022. "Managing Inequality Over Business Cycles: Optimal Policies With Heterogeneous Agents And Aggregate Shocks," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 63(1), pages 511-540, February.
    2. Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2011. "A new class of functions for measuring solution integrality in the Feasibility Pump approach," DIS Technical Reports 2011-08, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    3. Sandra S. Y. Tan & Antonios Varvitsiotis & Vincent Y. F. Tan, 2021. "Analysis of Optimization Algorithms via Sum-of-Squares," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 56-81, July.
    4. Michael K. McWilliam & Antariksh C. Dicholkar & Frederik Zahle & Taeseong Kim, 2022. "Post-Optimum Sensitivity Analysis with Automatically Tuned Numerical Gradients Applied to Swept Wind Turbine Blades," Energies, MDPI, vol. 15(9), pages 1-19, April.
    5. Paul Armand & Ngoc Nguyen Tran, 2019. "An Augmented Lagrangian Method for Equality Constrained Optimization with Rapid Infeasibility Detection Capabilities," Journal of Optimization Theory and Applications, Springer, vol. 181(1), pages 197-215, April.
    6. Wenqiang Dai & Meng Zheng & Xu Chen & Zhuolin Yang, 0. "Online economic ordering problem for deteriorating items with limited price information," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    7. Kohei Hasui & Teruyoshi Kobayashi & Tomohiro Sugo, 2019. "Irreversible monetary policy at the zero lower bound," Discussion Papers 1906, Graduate School of Economics, Kobe University.
    8. repec:hal:wpspec:info:hdl:2441/4lhe3u3c38ojohjlcbfaupcjr is not listed on IDEAS
    9. Kurt Jörnsten & Andreas Klose, 2016. "An improved Lagrangian relaxation and dual ascent approach to facility location problems," Computational Management Science, Springer, vol. 13(3), pages 317-348, July.
    10. Javier Cano & Javier M. Moguerza & Francisco J. Prieto, 2017. "Using Improved Directions of Negative Curvature for the Solution of Bound-Constrained Nonconvex Problems," Journal of Optimization Theory and Applications, Springer, vol. 174(2), pages 474-499, August.
    11. Hedlund, Jonas, 2017. "Bayesian persuasion by a privately informed sender," Journal of Economic Theory, Elsevier, vol. 167(C), pages 229-268.
    12. Xiao Liu & Simge Küçükyavuz, 2018. "A polyhedral study of the static probabilistic lot-sizing problem," Annals of Operations Research, Springer, vol. 261(1), pages 233-254, February.
    13. Abdolmaleki, Mojtaba & Shahabi, Mehrdad & Yin, Yafeng & Masoud, Neda, 2021. "Itinerary planning for cooperative truck platooning," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 91-110.
    14. Wendel Melo & Marcia Fampa & Fernanda Raupp, 2014. "Integrating nonlinear branch-and-bound and outer approximation for convex Mixed Integer Nonlinear Programming," Journal of Global Optimization, Springer, vol. 60(2), pages 373-389, October.
    15. Janosch Rieger, 2021. "A Galerkin approach to optimization in the space of convex and compact subsets of $${\mathbb {R}}^d$$ R d," Journal of Global Optimization, Springer, vol. 79(3), pages 593-615, March.
    16. Rupaj Kumar Nayak & Nirmalya Kumar Mohanty, 2020. "Solution of boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 792-825, April.
    17. Azizipanah-Abarghooee, Rasoul & Golestaneh, Faranak & Gooi, Hoay Beng & Lin, Jeremy & Bavafa, Farhad & Terzija, Vladimir, 2016. "Corrective economic dispatch and operational cycles for probabilistic unit commitment with demand response and high wind power," Applied Energy, Elsevier, vol. 182(C), pages 634-651.
    18. Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2013. "A new class of functions for measuring solution integrality in the Feasibility Pump approach: Complete Results," DIAG Technical Reports 2013-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    19. Paul Armand & Ngoc Nguyen Tran, 2021. "Local Convergence Analysis of a Primal–Dual Method for Bound-Constrained Optimization Without SOSC," Journal of Optimization Theory and Applications, Springer, vol. 189(1), pages 96-116, April.
    20. Hajime Kawakami, 2015. "Reconstruction algorithm for unknown cavities via Feynman–Kac type formula," Computational Optimization and Applications, Springer, vol. 61(1), pages 101-133, May.
    21. Ma, Cheng & Zhang, Liansheng, 2015. "On an exact penalty function method for nonlinear mixed discrete programming problems and its applications in search engine advertising problems," Applied Mathematics and Computation, Elsevier, vol. 271(C), pages 642-656.

    More about this item

    Statistics

    Access and download statistics

    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:hin:complx:8405036. 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: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.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.