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 
Issue Date: 2014
Source: Journal of industrial and management optimization, 2014, v. 10, no. 2, p. 557-566
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.
Keywords: Integer programming
Integer basis
Stiefel manifold
Optimal control
Permutation matrix
Publisher: American Institute of Mathematical Sciences
Journal: Journal of industrial and management optimization 
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 Sep 17, 2020

Page view(s)

234
Last Week
0
Last month
Citations as of Sep 20, 2020

Google ScholarTM

Check

Altmetric


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