IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v274y2019i1d10.1007_s10479-018-2926-8.html
   My bibliography  Save this article

Total dual integrality of the linear complementarity problem

Author

Listed:
  • Hanna Sumita

    (Tokyo Metropolitan University)

  • Naonori Kakimura

    (Keio University)

  • Kazuhisa Makino

    (Kyoto University)

Abstract

In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of defining the notion is to propose the LCP with orientation, a variant of the LCP whose feasible complementary cones are specified by an additional input vector. Then we naturally define the dual problem of the LCP with orientation and total dual integrality of the LCP. We show that if the LCP is totally dual integral, then all basic solutions are integral. If the input matrix is sufficient or rank-symmetric, and the LCP is totally dual integral, then our result implies that the LCP always has an integral solution whenever it has a solution. We also introduce a class of matrices such that any LCP instance having the matrix as a coefficient matrix is totally dual integral. We investigate relationships between matrix classes in the LCP literature such as principally unimodular matrices. Principally unimodular matrices are known that all basic solutions to the LCP are integral for any integral input vector. In addition, we show that it is coNP-hard to decide whether a given LCP instance is totally dual integral.

Suggested Citation

  • Hanna Sumita & Naonori Kakimura & Kazuhisa Makino, 2019. "Total dual integrality of the linear complementarity problem," Annals of Operations Research, Springer, vol. 274(1), pages 531-553, March.
    • Handle: RePEc:spr:annopr:v:274:y:2019:i:1:d:10.1007_s10479-018-2926-8
    DOI: 10.1007/s10479-018-2926-8
    as

    Download full text from publisher

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

    for a different version of it.

    References listed on IDEAS

    as
    1. William H. Cunningham & James F. Geelen, 1998. "Integral Solutions of Linear Complementarity Problems," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 61-68, February.
    2. EDMONDS, Jack & GILES, Rick, 1977. "A min-max relation for submodular functions on graphs," LIDAM Reprints CORE 301, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Joseph T. Howson, Jr., 1972. "Equilibria of Polymatrix Games," Management Science, INFORMS, vol. 18(5-Part-1), pages 312-318, January.
    4. C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
    5. R. Chandrasekaran & S. N. Kabadi & R. Sridhar, 1998. "Integer Solution for Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 390-402, May.
    6. M. Seetharama Gowda & Jong-Shi Pang, 1992. "On Solution Stability of the Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 77-83, February.
    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. Gerard van der Laan & Dolf Talman & Zaifu Yang, 2005. "Computing Integral Solutions of Complementarity Problems," Tinbergen Institute Discussion Papers 05-006/1, Tinbergen Institute.
    2. Hanna Sumita & Naonori Kakimura & Kazuhisa Makino, 2015. "The Linear Complementarity Problems with a Few Variables per Constraint," Mathematics of Operations Research, INFORMS, vol. 40(4), pages 1015-1026, October.
    3. S. R. Mohan, 1997. "Degeneracy Subgraph of the Lemke Complementary Pivot Algorithm and Anticycling Rule," Journal of Optimization Theory and Applications, Springer, vol. 94(2), pages 409-423, August.
    4. Meijia Han & Wenxing Zhu, 2023. "Nonnegative partial s-goodness for the equivalence of a 0-1 linear program to weighted linear programming," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-37, July.
    5. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    6. Zaifu Yang, 2008. "On the Solutions of Discrete Nonlinear Complementarity and Related Problems," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 976-990, November.
    7. Ting Zhang & Yong Wang & Zheng-Hai Huang, 2024. "Projected fixed-point method for vertical tensor complementarity problems," Computational Optimization and Applications, Springer, vol. 89(1), pages 219-245, September.
    8. 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.
    9. M. Seetharama Gowda, 2019. "Weighted LCPs and interior point systems for copositive linear transformations on Euclidean Jordan algebras," Journal of Global Optimization, Springer, vol. 74(2), pages 285-295, June.
    10. Christian Bidard, 2015. "An oddity property for cross-dual games," Working Papers hal-04141427, HAL.
    11. Prasenjit Mondal, 2018. "Completely mixed strategies for single controller unichain semi-Markov games with undiscounted payoffs," Operational Research, Springer, vol. 18(2), pages 451-468, July.
    12. Senlai Zhu & Jie Ma & Tianpei Tang & Quan Shi, 2020. "A Combined Modal and Route Choice Behavioral Complementarity Equilibrium Model with Users of Vehicles and Electric Bicycles," IJERPH, MDPI, vol. 17(10), pages 1-18, May.
    13. N. Krishnamurthy & S. K. Neogy, 2020. "On Lemke processibility of LCP formulations for solving discounted switching control stochastic games," Annals of Operations Research, Springer, vol. 295(2), pages 633-644, December.
    14. R. B. Bapat & S. K. Neogy, 2016. "On a quadratic programming problem involving distances in trees," Annals of Operations Research, Springer, vol. 243(1), pages 365-373, August.
    15. Rahul Savani & Bernhard von Stengel, 2016. "Unit vector games," International Journal of Economic Theory, The International Society for Economic Theory, vol. 12(1), pages 7-27, March.
    16. Mohan, S.R. & Talman, A.J.J., 1998. "Refinement of solutions to the linear complimentarity problem," Other publications TiSEM e54c1f99-3de9-475d-a8e5-7, Tilburg University, School of Economics and Management.
    17. Christian Bidard, 2010. "Complementarity Problems and General Equilibrium," Working Papers hal-04140923, HAL.
    18. K. Ahmad & K. R. Kazmi & N. Rehman, 1997. "Fixed-Point Technique for Implicit Complementarity Problem in Hilbert Lattice," Journal of Optimization Theory and Applications, Springer, vol. 93(1), pages 67-72, April.
    19. Jugal Garg & Ruta Mehta & Vijay V. Vaziranic, 2018. "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 996-1024, August.
    20. Christian Bidard, 2014. "The Ricardian rent theory two centuries after," Working Papers hal-04141289, HAL.

    More about this item

    Keywords

    ;
    ;
    ;

    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:spr:annopr:v:274:y:2019:i:1:d:10.1007_s10479-018-2926-8. 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.