Optimization Online


Learning to Project in Multi-Objective Binary Linear Programming

Alvaro Sierra-Alltamiranda(amsierra***at***mail.usf.edu)
Hadi Charkhgard(hcharkhgard***at***usf.edu)
Iman Dayarian(idayarian***at***cba.ua.edu)
Ali Eshragh(ali.eshragh***at***newcastle.edu.au)
Sorna Javadi(javadis***at***mail.usf.edu)

Abstract: In this paper, we investigate the possibility of improving the performance of multi-objective optimization solution approaches using machine learning techniques. Specifically, we focus on multi-objective binary linear programs and employ one of the most effective and recently developed criterion space search algorithms, the so-called KSA, during our study. This algorithm computes all nondominated points of a problem with p objectives by searching on a projected criterion space, i.e., a (p-1)-dimensional criterion apace. We present an effective and fast learning approach to identify on which projected space the KSA should work. We also present several generic features/variables that can be used in machine learning techniques for identifying the best projected space. Finally, we present an effective bi-objective optimization based heuristic for selecting the best subset of the features to overcome the issue of overfitting in learning. Through an extensive computational study over 2000 instances of tri-objective Knapsack and Assignment problems, we demonstrate that an improvement of up to 12% in time can be achieved by the proposed learning method compared to a random selection of the projected space.

Keywords: Multi-objective optimization, machine learning, binary linear program, criterion space search algorithm, learning to project

Category 1: Other Topics (Multi-Criteria Optimization )

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

Category 3: Other Topics (Other )


Download: [PDF]

Entry Submitted: 01/29/2019
Entry Accepted: 01/29/2019
Entry Last Modified: 01/29/2019

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