Projects per year
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 language | English |
---|---|
Article number | 182 |
Journal | Fixed Point Theory and Applications |
Volume | 2015 |
Online published | 6 Oct 2015 |
DOIs | |
Publication status | Published - 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.Projects
- 1 Finished
-
GRF: An Interior-point Path-following Approach to the Determination of Perfect Equilibrium for a Finite n-Person Game in Normal Form
DANG, C. (Principal Investigator / Project Coordinator) & Ye, Y. (Co-Investigator)
1/01/14 → 13/12/17
Project: Research