Home > Research > Publications & Outputs > Integrating column generation in a method to co...

Electronic data

  • Accepted VersionPDF

    Rights statement: The final publication is available at Springer via http://dx.doi.org/10.1007/S10288-016-0336-9

    Accepted author manuscript, 482 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License


Text available via DOI:

View graph of relations

Integrating column generation in a method to compute a discrete representation of the non-dominated set of multi-objective linear programmes

Research output: Contribution to journalJournal articlepeer-review

E-pub ahead of print
<mark>Journal publication date</mark>23/12/2016
<mark>Journal</mark>4OR: A Quarterly Journal of Operations Research
Number of pages27
Publication StatusE-pub ahead of print
Early online date23/12/16
<mark>Original language</mark>English


In this paper we propose the integration of column generation in the revised normal boundary intersection (RNBI) approach to compute a representative set of non-dominated points for multi-objective linear programmes (MOLPs). The RNBI approach solves single objective linear programmes, the RNBI subproblems, to project a set of evenly distributed reference points to the non-dominated set of an MOLP. We solve each RNBI subproblem using column generation, which moves the current point in objective space of the MOLP towards the non-dominated set. Since RNBI subproblems may be infeasible, we attempt to detect this infeasibility early. First, a reference point bounding method is proposed to eliminate reference points that lead to infeasible RNBI subproblems. Furthermore, different initialisation approaches for column generation are implemented, including Farkas pricing. We investigate the quality of the representation obtained.
To demonstrate the efficacy of the proposed approach, we apply it to an MOLP
arising in radiotherapy treatment design. In contrast to conventional optimisation approaches, treatment design using column generation provides deliverable treatment plans, avoiding a segmentation step which deteriorates treatment quality. As a result total monitor units is considerably reduced. We also note that reference point bounding dramatically reduces the number of RNBI subproblems that need to be solved.

Bibliographic note

The final publication is available at Springer via http://dx.doi.org/10.1007/S10288-016-0336-9