IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v53y2002i10d10.1057_palgrave.jors.2601391.html
   My bibliography  Save this article

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

Author

Listed:
  • I H Osman

    (American University of Beirut)

  • M Hasan

    (Kuwait University)

  • A Abdullah

    (University of Kent at Canterbury)

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.

Suggested Citation

  • I H Osman & M Hasan & A Abdullah, 2002. "Linear programming based meta-heuristics for the weighted maximal planar graph," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(10), pages 1142-1149, October.
  • Handle: RePEc:pal:jorsoc:v:53:y:2002:i:10:d:10.1057_palgrave.jors.2601391
    DOI: 10.1057/palgrave.jors.2601391
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601391
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1057/palgrave.jors.2601391?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:53:y:2002:i:10:d:10.1057_palgrave.jors.2601391. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.