IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v6y2002i2d10.1023_a1013847510365.html
   My bibliography  Save this article

Simplicial Pivoting Algorithms for a Tractable Class of Integer Programs

Author

Listed:
  • H. Van Maaren

    (Delft University of Technology)

  • C. Dang

    (City University of Hong Kong)

Abstract

We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First we modify the existing algorithms in order to avoid the related recognition problem. Then we show that in order to solve these max-closed IP problems, simplicial path following methods can be used. This is important because these methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested.

Suggested Citation

  • H. Van Maaren & C. Dang, 2002. "Simplicial Pivoting Algorithms for a Tractable Class of Integer Programs," Journal of Combinatorial Optimization, Springer, vol. 6(2), pages 133-142, June.
    • Handle: RePEc:spr:jcomop:v:6:y:2002:i:2:d:10.1023_a:1013847510365
    DOI: 10.1023/A:1013847510365
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1013847510365
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1013847510365?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Robert M. Freund, 1984. "Variable Dimension Complexes Part II: A Unified Approach to Some Combinatorial Lemmas in Topology," Mathematics of Operations Research, INFORMS, vol. 9(4), pages 498-509, November.
    2. G. van der Laan, 1981. "Simplicial fixed point algorithms," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 35(1), pages 58-58, March.
    3. Masakazu Kojima, 1978. "Studies on Piecewise-Linear Approximations of Piecewise- C 1 Mappings in Fixed Points and Complementarity Theory," Mathematics of Operations Research, INFORMS, vol. 3(1), pages 17-36, February.
    4. Chuangyin Dang & Hans van Maaren, 1998. "A Simplicial Approach to the Determination of an Integer Point of a Simplex," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 403-415, May.
    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. Talman, Dolf & Yang, Zaifu, 2009. "A discrete multivariate mean value theorem with applications," European Journal of Operational Research, Elsevier, vol. 192(2), pages 374-381, January.
    2. C. Dang, 2001. "Computing an Integer Point of a Class of Convex Sets," Journal of Optimization Theory and Applications, Springer, vol. 108(2), pages 333-348, February.
    3. van der Laan, Gerard & Talman, Dolf & Yang, Zaifu, 2011. "Solving discrete systems of nonlinear equations," European Journal of Operational Research, Elsevier, vol. 214(3), pages 493-500, November.
    4. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2007. "Combinatorial Integer Labeling Thorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations," Other publications TiSEM 264c28a5-10b6-44e1-9694-4, Tilburg University, School of Economics and Management.
    5. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2005. "Computing Integral Solutions of Complementarity Problems," Other publications TiSEM b8e0c74e-2219-4ab0-99a2-0, Tilburg University, School of Economics and Management.
    6. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2007. "A vector labeling method for solving discrete zero point and complementarity problems," Other publications TiSEM 070869d0-4e42-4d34-85f9-b, Tilburg University, School of Economics and Management.
    7. Chuangyin Dang & Hans van Maaren, 1998. "A Simplicial Approach to the Determination of an Integer Point of a Simplex," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 403-415, May.
    8. Talman, A.J.J. & Yang, Z.F., 2004. "The Computation of a Coincidence of Two Mappings," Other publications TiSEM 9fbcc219-da4d-4564-b4e3-6, Tilburg University, School of Economics and Management.
    9. Eaves, C. & van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 1996. "Balanced Simplices on Polytopes," Other publications TiSEM 21c51445-984c-4466-9e6a-6, Tilburg University, School of Economics and Management.
    10. Ruys, P.H.M. & van der Laan, G., 1987. "Computation of an industrial equilibrium," Research Memorandum FEW 257, Tilburg University, School of Economics and Management.
    11. G. Laan & A. J. J. Talman & Z. Yang, 2010. "Combinatorial Integer Labeling Theorems on Finite Sets with Applications," Journal of Optimization Theory and Applications, Springer, vol. 144(2), pages 391-407, February.
    12. Talman, A.J.J. & Yamamoto, Y., 1986. "A globally convergent simplicial algorithm for stationary point problems on polytopes," Other publications TiSEM b4871efd-ccb8-4d02-b92b-d, Tilburg University, School of Economics and Management.
    13. Xiaotie Deng & Qi Qi & Amin Saberi & Jie Zhang, 2011. "Discrete Fixed Points: Models, Complexities, and Applications," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 636-652, November.
    14. van den Elzen, A.H. & van der Laan, G. & Talman, A.J.J., 1985. "Adjustment processes for finding equilibria on the simplotope," Other publications TiSEM 21421db2-1e09-461b-9a16-a, Tilburg University, School of Economics and Management.
    15. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2005. "Solving Discrete Zero Point Problems with Vector Labeling," Other publications TiSEM 9bd940ee-3fe6-4201-aede-7, Tilburg University, School of Economics and Management.
    16. Doup, T.M. & van der Laan, G. & Talman, A.J.J., 1984. "The (2n+1-2)-ray algorithm : A new simplicial algorithm to compute economic equilibria," Research Memorandum FEW 151, Tilburg University, School of Economics and Management.
    17. Yang, Z.F., 1994. "A simplicial algorithm for testing the integral properties of polytopes : A revision," Other publications TiSEM 72b67872-ca37-4bb5-8a13-7, Tilburg University, School of Economics and Management.
    18. Yang, Z.F., 1994. "A simplicial algorithm for testing the integral property of a polytope," Discussion Paper 1994-75, Tilburg University, Center for Economic Research.
    19. van der Laan, G. & Talman, A.J.J. & Van der Heyden, L., 1984. "Shortest paths for simplicial algorithms," Research Memorandum FEW 164, Tilburg University, School of Economics and Management.
    20. Viacheslav V. Kalashnikov & Adolphus J. J. Talman & Lilia Alanís-López & Nataliya I. Kalashnykova, 2018. "Extended Antipodal Theorems," Journal of Optimization Theory and Applications, Springer, vol. 177(2), pages 399-412, 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:spr:jcomop:v:6:y:2002:i:2:d:10.1023_a:1013847510365. 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: 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.