An improved linearization technique for a class of quadratic 0-1 programming problems

Xiaozheng He, Anthony Chen, Wanpracha A. Chaovalitwongse, Henry X. Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

The recent research on linearization techniques for solving 0-1 quadratic programming problems focuses on providing concise models and tightening constraint bounds. In this paper, we propose a computational enhancement for a linearization technique to make the linearized model much faster to solve. We investigate the computational performance of the proposed approach, by comparing it with other linearization techniques on a class of 0-1 quadratic programming problems. We can further speed up the proposed technique by heuristically tightening the constraint bounds, as demonstrated by solving the uncapacitated single allocation p-hub median problem using the Civil Aeronautics Board data.
Original languageEnglish
Pages (from-to)31-41
Number of pages11
JournalOptimization Letters
Volume6
Issue number1
DOIs
Publication statusPublished - 1 Jan 2012
Externally publishedYes

Keywords

  • Binary quadratic programming problem
  • Hub location problem
  • Linearization technique

ASJC Scopus subject areas

  • Control and Optimization

Cite this