Manifold relaxations for integer programming

Research output: Journal article publicationJournal articleAcademic researchpeer-review


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.
Original languageEnglish
Pages (from-to)557-566
Number of pages10
JournalJournal of Industrial and Management Optimization
Issue number2
Publication statusPublished - 2014


  • Integer programming
  • Integer basis
  • Stiefel manifold
  • Optimal control
  • Permutation matrix

ASJC Scopus subject areas

  • Business and International Management
  • Strategy and Management
  • Applied Mathematics
  • Control and Optimization


Dive into the research topics of 'Manifold relaxations for integer programming'. Together they form a unique fingerprint.

Cite this