Generation of feasible integer solutions on a massively parallel computer using the feasibility pump

Utku Koc*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We present an approach to parallelize generation of feasible mixed integer solutions of mixed integer linear programs in distributed memory high performance computing environments. This approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. It runs multiple FP instances with different starting solutions concurrently, while allowing them to share information. Our computational results suggest that the improvement resulting from parallelization using our approach is statistically significant.

Original languageEnglish (US)
Pages (from-to)652-658
Number of pages7
JournalOperations Research Letters
Volume45
Issue number6
DOIs
StatePublished - Nov 2017

Keywords

  • Feasibility pump
  • Mixed integer programming
  • Parallel optimization

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Generation of feasible integer solutions on a massively parallel computer using the feasibility pump'. Together they form a unique fingerprint.

Cite this