A Fixed-Point Iterative Approach to Integer Programming and Distributed Computation
Chuangyin Dang
Department of Systems Engineering and Engineering Management
The City University of Hong Kong
Wednesday Aguust 17, 2011
4:30 - 5:30 PM
Y2E2 105
Abstract:
Integer programming is concerned with the minimization of a linear function over integer or mixed-integer points in a polytope, which is equivalent under binary search to determining whether there is an integer or mixed-integer point in a polytope. Integer programming is an NP-hard problem and has many applications in economics and management. By constructing an increasing mapping satisfying certain properties, we develop a fixed-point iterative method for integer programming. The self-dual embedding technique will be applied for a solution to a bounding linear program in the development. Given any polytope, within a finite number of iterations, the method either yields an integer or mixed-integer point in the polytope or proves no such point exists. As a very appealing feature for integer programming, the method can be easily implemented in a distributed way. Furthermore, the method can be applied to compute all integer or mixed-integer points in a polytope. Numerical results show that the method is promising.
Joint work with Yinyu Ye.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html