Linear programming based meta-heuristics for the weighted maximal planar graph

Linear programming based meta-heuristics for the weighted maximal planar graph

0.00 Avg rating0 Votes
Article ID: iaor20032024
Country: United Kingdom
Volume: 53
Issue: 10
Start Page Number: 1142
End Page Number: 1149
Publication Date: Oct 2002
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: facilities, programming: integer, programming: linear
Abstract:

The weighted maximal planar graph (WMPG) is practically important in the laying out of facilities in modern manufacturing environments. Given a weighted complete graph, the WMPG seeks to find a sub-graph such that it is planar – it can be embedded on the plane without any arcs intersecting, and it is maximal – no additional arc can be added to the sub-graph without destroying its planarity, and it also has the maximal sum of arc weights. In this paper, an integer linear programming (ILP) model is newly introduced for the problem. Two meta-heuristics are then derived from the ILP relaxation. The first meta-heuristic considers all variables with fractional values greater than half in the ILP relaxation to build an initial sub-graph from which a planar sub-graph is extracted using greedy random adaptive search procedure (GRASP) and augmented by triangulation of faces. The second meta-heuristic considers only arcs with integer values in the ILP relaxation. The remaining arcs are then sorted in descending order of their weights, for selection and insertion with a planarity testing procedure, to obtain a feasible solution using GRASP. Computational results are reported on a set of 100 test instances of size varying from 20 to 100 facilities. The computational results demonstrate the tightness of the new upper bound when compared to the classical one as well as the good performance of the proposed metaheuristics when compared to the best-known procedures in the literature in terms of solution quality and computational requirement. Finally, the paper presents a successful integration of GRASP with classical optimisation approaches and should be attempted for other optimisation problems.

Reviews

Required fields are marked *. Your email address will not be published.