Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/13925
Title: Manifold relaxations for integer programming
Authors: Feng, Z
Yiu, KFC 
Keywords: Integer programming
Integer basis
Stiefel manifold
Optimal control
Permutation matrix
Issue Date: 2014
Publisher: American Institute of Mathematical Sciences
Source: Journal of industrial and management optimization, 2014, v. 10, no. 2, p. 557-566 How to cite?
Journal: Journal of industrial and management optimization 
Abstract: In this paper, the integer programming problem is studied. We introduce the notion of integer basis and show that a given integer set can be converted into a fixed number of linear combinations of the basis elements. By employing the Stiefel manifold and optimal control theory, the combinatorial optimization problem can be converted into a continuous optimization problem over the continuous Stiefel manifold. As a result, gradient descent methods can be applied to find the optimal integer solution. We demonstrate by numerical examples that this approach can obtain good solutions. Furthermore, this method gives new insights into continuous relaxation for solving integer programming problems.
URI: http://hdl.handle.net/10397/13925
ISSN: 1547-5816
EISSN: 1553-166X
DOI: 10.3934/jimo.2014.10.557
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

41
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.