IDEAS home Printed from https://ideas.repec.org/p/ags/eureia/272174.html
   My bibliography  Save this paper

Some Computational Experiments With A Primal-Dual Surrogate Simplex Algorithm

Author

Listed:
  • van Dam, Wim
  • Telgen, Jan

Abstract

Computational experiments were performed with a primal-dual algorithm, using surrogate objective functions to solve the linear programming problem. Three different rules for switching between the primal and the dual problem and seven different ways to construct the surrogate objective function were used to solve 28 LP problems. For the moment it seems that the sum of the infeasibilities is the best indicator for attacking either the primal or the dual problem and that the sum of the violated constraints is the best surrogate objective function, judging by the number of iterations. . On the other.hand this version is shown to be not necessarily finite, while the other switching rules yield finite procedures. However, in Oneral the primal-dual surrogate simplex method clearly outperforms the twophase simplex method.

Suggested Citation

  • van Dam, Wim & Telgen, Jan, 1978. "Some Computational Experiments With A Primal-Dual Surrogate Simplex Algorithm," Econometric Institute Archives 272174, Erasmus University Rotterdam.
    • Handle: RePEc:ags:eureia:272174
    DOI: 10.22004/ag.econ.272174
    as

    Download full text from publisher

    File URL: https://ageconsearch.umn.edu/record/272174/files/erasmus110.pdf
    Download Restriction: no
    File URL: https://ageconsearch.umn.edu/record/272174/files/erasmus110.pdf?subformat=pdfa
    Download Restriction: no
    File URL: https://libkey.io/10.22004/ag.econ.272174?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. A. M. Geoffrion, 1969. "An Improved Implicit Enumeration Approach for Integer Programming," Operations Research, INFORMS, vol. 17(3), pages 437-454, June.
    2. Stanley Zionts, 1969. "The Criss-Cross Method for Solving Linear Programming Problems," Management Science, INFORMS, vol. 15(7), pages 426-445, March.
    3. Fred Glover, 1965. "A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem," Operations Research, INFORMS, vol. 13(6), pages 879-919, December.
    4. Fred Glover, 1968. "Surrogate Constraints," Operations Research, INFORMS, vol. 16(4), pages 741-749, August.
    5. Egon Balas, 1967. "Discrete Programming by the Filter Method," Operations Research, INFORMS, vol. 15(5), pages 915-957, October.
    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. Jiang, Bo & Tzavellas, Hector, 2023. "Optimal liquidity allocation in an equity network," International Review of Economics & Finance, Elsevier, vol. 85(C), pages 286-294.
    2. Joseph, Anito & Gass, Saul I. & Bryson, Noel, 1998. "An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem," European Journal of Operational Research, Elsevier, vol. 104(3), pages 601-614, February.
    3. Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.
    4. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    5. Hasan Pirkul, 1987. "A heuristic solution procedure for the multiconstraint zero‐one knapsack problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(2), pages 161-172, April.
    6. Balev, Stefan & Yanev, Nicola & Freville, Arnaud & Andonov, Rumen, 2008. "A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 186(1), pages 63-76, April.
    7. Mohammadi Bidhandi, Hadi & Mohd. Yusuff, Rosnah & Megat Ahmad, Megat Mohamad Hamdan & Abu Bakar, Mohd Rizam, 2009. "Development of a new approach for deterministic supply chain network design," European Journal of Operational Research, Elsevier, vol. 198(1), pages 121-128, October.
    8. Hanif D. Sherali & J. Cole Smith & Antonio A. Trani, 2002. "An Airspace Planning Model for Selecting Flight-plans Under Workload, Safety, and Equity Considerations," Transportation Science, INFORMS, vol. 36(4), pages 378-397, November.
    9. Csizmadia, Zsolt & Illés, Tibor & Nagy, Adrienn, 2012. "The s-monotone index selection rules for pivot algorithms of linear programming," European Journal of Operational Research, Elsevier, vol. 221(3), pages 491-500.
    10. Fox, B. L. & Lenstra, J. K. & Rinnooy Kan, A. H. G. & Schrage, L. E., 1977. "Branching From The Largest Upper Bound: Folklore And Facts," Econometric Institute Archives 272158, Erasmus University Rotterdam.
    11. Yuji Nakagawa & Ross J. W. James & César Rego & Chanaka Edirisinghe, 2014. "Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models," Management Science, INFORMS, vol. 60(3), pages 695-707, March.
    12. Ma, Yanqin & Zhang, Lili & Pan, Pingqi, 2015. "Criss-cross algorithm based on the most-obtuse-angle rule and deficient basis," Applied Mathematics and Computation, Elsevier, vol. 268(C), pages 439-449.
    13. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    14. Alidaee, Bahram, 2014. "Zero duality gap in surrogate constraint optimization: A concise review of models," European Journal of Operational Research, Elsevier, vol. 232(2), pages 241-248.
    15. Ablanedo-Rosas, José H. & Rego, César, 2010. "Surrogate constraint normalization for the set covering problem," European Journal of Operational Research, Elsevier, vol. 205(3), pages 540-551, September.
    16. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    17. Asano, Makoto & Ohta, Hiroshi, 1999. "Single machine scheduling to meet due times under shutdown constraints," International Journal of Production Economics, Elsevier, vol. 60(1), pages 537-547, April.
    18. Satoshi Suzuki & Daishi Kuroiwa, 2020. "Duality Theorems for Convex and Quasiconvex Set Functions," SN Operations Research Forum, Springer, vol. 1(1), pages 1-13, March.
    19. Saïd Hanafi & Christophe Wilbaut, 2011. "Improved convergent heuristics for the 0-1 multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 183(1), pages 125-142, March.
    20. Adrienn Csizmadia & Zsolt Csizmadia & Tibor Illés, 2018. "Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied," 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. 26(3), pages 535-550, September.

    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:ags:eureia:272174. 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: AgEcon Search (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.html .

    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.