An example to demonstrate the importance of using ellipsoidal norm in lattice basis reduction for branching on hyperplane algorithms

Zhifeng Li*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The use of lattice basis reduction has been proposed in reformulating instances of hard integer programs. We construct integer programming instances showing that branching on hyperplane algorithms may benefit from using the geometrical information of the feasible set using an ellipsoidal approximation of the linear relaxation while using lattice basis reduction methods. Feasible as well as infeasible instances of these problems in four dimensions are given.

Original languageEnglish (US)
Pages (from-to)351-365
Number of pages15
JournalPacific Journal of Optimization
Volume5
Issue number2
StatePublished - May 1 2009

Keywords

  • Integer programming
  • Lattice basis reduction

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Control and Optimization

Fingerprint Dive into the research topics of 'An example to demonstrate the importance of using ellipsoidal norm in lattice basis reduction for branching on hyperplane algorithms'. Together they form a unique fingerprint.

Cite this