A fixed point iterative approach to integer programming and its distributed computation

Chuangyin Dang*, Yinyu Ye

*Corresponding author for this work

    Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

    15 Citations (Scopus)
    68 Downloads (CityUHK Scholars)

    Abstract

    Integer programming is concerned with the determination of an integer or mixed-integer point in a polytope. It is an NP-hard problem and has many applications in economics and management. Although several popular methods have been developed for integer programming in the literature and extensively utilized in practices, it remains a challenging problem and appeals for more endeavors. By constructing an increasing mapping satisfying certain properties, we develop in this paper an alternative method for integer programming, which is called a fixed point iterative method. Given a polytope, the method, within a finite number of iterations, either yields an integer or mixed-integer point in the polytope or proves no such point exists. As a very appealing feature, the method can easily be implemented in a distributed way. Furthermore, the construction implies that determining the uniqueness of Tarski’s fixed point is an NP-hard problem, and the method can be applied to compute all integer or mixed-integer points in a polytope and directly extended to convex nonlinear integer programming. Preliminary numerical results show that the method seems promising.
    Original languageEnglish
    Article number182
    JournalFixed Point Theory and Applications
    Volume2015
    Online published6 Oct 2015
    DOIs
    Publication statusPublished - 2015

    Research Keywords

    • fixed point iterative method
    • increasing mapping
    • integer or mixed-integer point
    • integer programming
    • linear programming
    • polytope
    • self-dual embedding technique
    • Tarski’s fixed point theorem

    Publisher's Copyright Statement

    • This full text is made available under CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/

    Fingerprint

    Dive into the research topics of 'A fixed point iterative approach to integer programming and its distributed computation'. Together they form a unique fingerprint.

    Cite this