Optimization Online


Generation of Feasible Integer Solutions on a Massively Parallel Computer

Utku Koc (utku.koc***at***mef.edu.tr)
Sanjay Mehrotra (mehrotra***at***northwestern.edu)

Abstract: We present an approach to parallelize generation of feasible solutions of mixed integer linear programs in distributed memory high performance computing environments. The approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. The proposed approach runs multiple FP instances with different starting so- lutions concurrently, while allowing them to share information. The starting solutions for multiple subroutines are created by rounding the most fractional k variables of an optimal solution of the continuous relaxation. Our compu- tational results on COR@L, MIPLIB 2003, and MIPLIB 2010 test sets suggest that the improvement resulting from parallelization using our approach is statistically significant. Furthermore, running multiple short FP algorithms in parallel can significantly outperform running a single long version even if both algorithms are given the same amount of CPU time. This suggest that the benefits of parallelization are also due to information sharing.

Keywords: Mixed Integer Programming, Parallel Optimization, Feasibility Pump

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 02/19/2016
Entry Accepted: 02/19/2016
Entry Last Modified: 07/18/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society