Optimization Online


A Feasibility Pump and Local Search Based Heuristic for Bi-objective Pure Integer Linear Programming

Aritra Pal (aritra1***at***mail.usf.edu)
Hadi Charkhgard (hcharkhgard***at***usf.edu)

Abstract: We present a new heuristic algorithm to approximately generate the nondominated frontier of bi-objective pure integer linear programs. The proposed algorithm employs a customized version of several existing algorithms in the literature of both single objective and bi-objective optimization. Our proposed method has two desirable characteristics: (1) There is no parameter to be tuned by users other than the time limit; (2) It can naturally exploit parallelism. An extensive computational study shows the efficacy of the proposed method on some existing standard test instances in which the true frontier is known, and also some large randomly generated instances. We show that even a basic version of our algorithm can significantly outperform NSGA-II (Deb et al. 2002), and the sophisticated version of our algorithm is competitive with MDLS (Tricoire 2012). We also show the value of parallelization on the proposed approach.

Keywords: Bi-objective integer linear programming, feasibility pump, local search, the perpendicular search method, parallelization

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 03/10/2017
Entry Accepted: 03/14/2017
Entry Last Modified: 07/21/2017

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