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

Self-Regulating Artificial-Free Linear Programming Solver Using a Jump and Simplex Method

Author

Listed:
  • Rujira Visuthirattanamanee

    (Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 13300, Thailand)

  • Krung Sinapiromsaran

    (Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 13300, Thailand)

  • Aua-aree Boonperm

    (Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathumthani 12121, Thailand)

Abstract

An enthusiastic artificial-free linear programming method based on a sequence of jumps and the simplex method is proposed in this paper. It performs in three phases. Starting with phase 1, it guarantees the existence of a feasible point by relaxing all non-acute constraints. With this initial starting feasible point, in phase 2, it sequentially jumps to the improved objective feasible points. The last phase reinstates the rest of the non-acute constraints and uses the dual simplex method to find the optimal point. The computation results show that this method is more efficient than the standard simplex method and the artificial-free simplex algorithm based on the non-acute constraint relaxation for 41 netlib problems and 280 simulated linear programs.

Suggested Citation

  • Rujira Visuthirattanamanee & Krung Sinapiromsaran & Aua-aree Boonperm, 2020. "Self-Regulating Artificial-Free Linear Programming Solver Using a Jump and Simplex Method," Mathematics, MDPI, vol. 8(3), pages 1-15, March.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:3:p:356-:d:329058
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/3/356/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/3/356/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Arsham, Hossein & Adlakha, Veena & Lev, Benjamin, 2009. "A simplified algebraic method for system of linear inequalities with LP applications," Omega, Elsevier, vol. 37(4), pages 876-882, August.
    2. Syed Inayatullah & Nasir Touheed & Muhammad Imtiaz, 2015. "A Streamlined Artificial Variable Free Version of Simplex Method," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-28, March.
    3. Fred Hanssmann & Sidney W. Hess, 1960. "A Linear Programming Approach to Production and Employment Scheduling," Management Science, INFORMS, vol. 0(1), pages 46-51, January.
    4. Gao, Pei-wang, 2015. "Improvement and its computer implementation of an artificial-free simplex-type algorithm by Arsham," Applied Mathematics and Computation, Elsevier, vol. 263(C), pages 410-415.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Leonid B. Sokolinsky & Irina M. Sokolinskaya, 2023. "Apex Method: A New Scalable Iterative Method for Linear Programming," Mathematics, MDPI, vol. 11(7), pages 1-28, March.

    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. Holsapple, Clyde W. & Lee-Post, Anita, 2010. "Behavior-based analysis of knowledge dissemination channels in operations management," Omega, Elsevier, vol. 38(3-4), pages 167-178, June.
    2. Hax, Arnoldo C. & Meal, Harlan C., 1973. "Hierarchical integration of production planning and scheduling," Working papers 656-73., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    3. Gordon H. Lewis & Ashok Srinivasan & Eswaran Subrahmanian, 1998. "Staffing and Allocation of Workers in an Administrative Office," Management Science, INFORMS, vol. 44(4), pages 548-570, April.
    4. Li, Deng-Feng, 2011. "Linear programming approach to solve interval-valued matrix games," Omega, Elsevier, vol. 39(6), pages 655-666, December.
    5. Wang, Reay-Chen & Fang, Hsiao-Hua, 2001. "Aggregate production planning with multiple objectives in a fuzzy environment," European Journal of Operational Research, Elsevier, vol. 133(3), pages 521-536, September.
    6. Michael J. Fry & Michael J. Magazine & Uday S. Rao, 2006. "Firefighter Staffing Including Temporary Absences and Wastage," Operations Research, INFORMS, vol. 54(2), pages 353-365, April.
    7. Gomes da Silva, Carlos & Figueira, José & Lisboa, João & Barman, Samir, 2006. "An interactive decision support system for an aggregate production planning model based on multiple criteria mixed integer linear programming," Omega, Elsevier, vol. 34(2), pages 167-177, April.
    8. Mirzapour Al-e-hashem, S.M.J. & Baboli, A. & Sazvar, Z., 2013. "A stochastic aggregate production planning model in a green supply chain: Considering flexible lead times, nonlinear purchase and shortage cost functions," European Journal of Operational Research, Elsevier, vol. 230(1), pages 26-41.
    9. Dalalah, Doraid & Lev, Benjamin, 2009. "Duality of the improved algebraic method (DIAM)," Omega, Elsevier, vol. 37(5), pages 1027-1035, October.
    10. Black, Ben & Ainslie, Russell & Dokka, Trivikram & Kirkbride, Christopher, 2023. "Distributionally robust resource planning under binomial demand intakes," European Journal of Operational Research, Elsevier, vol. 306(1), pages 227-242.
    11. Krishna Kumar, C. & Sinha, Bani K., 1999. "Efficiency based production planning and control models," European Journal of Operational Research, Elsevier, vol. 117(3), pages 450-469, September.
    12. Andrea Borenich & Peter Greistorfer & Marc Reimann, 2020. "Model-based production cost estimation to support bid processes: an automotive case study," 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. 28(3), pages 841-868, September.
    13. Liu, Yanwu & Tu, Yan & Zhang, Zhongzhen, 2021. "The row pivoting method for linear programming," Omega, Elsevier, vol. 100(C).
    14. Karmarkar, Uday S. & Rajaram, Kumar, 2012. "Aggregate production planning for process industries under oligopolistic competition," European Journal of Operational Research, Elsevier, vol. 223(3), pages 680-689.
    15. Mirzapour Al-e-hashem, S.M.J. & Malekly, H. & Aryanezhad, M.B., 2011. "A multi-objective robust optimization model for multi-product multi-site aggregate production planning in a supply chain under uncertainty," International Journal of Production Economics, Elsevier, vol. 134(1), pages 28-42, November.
    16. Adlakha, Veena & Kowalski, Krzysztof & Lev, Benjamin, 2010. "A branching method for the fixed charge transportation problem," Omega, Elsevier, vol. 38(5), pages 393-397, October.
    17. Wu, Chia-Chin & Chang, Ni-Bin, 2004. "Corporate optimal production planning with varying environmental costs: A grey compromise programming approach," European Journal of Operational Research, Elsevier, vol. 155(1), pages 68-95, 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:8:y:2020:i:3:p:356-:d:329058. 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.