This paper presents an algorithm aiming to compute an upper bound set for a multi-objective linear optimisation problem with binary variables (p-01LP). Inspired by the well known « Feasibility Pump » algorithm in single objective optimisation, it belongs to the class of primal heuristics. The proposed algorithm, named « Gravity Machine », aims to deal with generic p-01LP. In that sense, it does not exploit any information coming from the combinatorial structure of the problem. Sober in memory and computational resources, and given a time limit, the algorithm explores a p-01LP problem in order to discover a tight upper bound set, without guarantee of returning such a set. The paper describes the current version of the proposed algorithm. It reports numerical results obtained on instances of set partitioning problem available on the OR-library, extended to two objectives.
Citation
Proc. of the 1st Multi-Objective Decision Making Workshop (MODeM 2021), Hayes, Mannion, Vamplew (eds.), July 14-16, 2021, Online, http://modem2021.cs.nuigalway.ie. 2021.