Manifold relaxations for integer programming

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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

Keywords

  • 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

Cite this