Home > Research > Publications & Outputs > Combinatorial Optimisation

Associated organisational unit

Electronic data

  • 2022mansoorphd

    Final published version, 2.02 MB, PDF document

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

Text available via DOI:

View graph of relations

Combinatorial Optimisation: Relaxation, Duality and Heuristics

Research output: ThesisDoctoral Thesis

Published

Standard

Combinatorial Optimisation: Relaxation, Duality and Heuristics. / Mansoor, M Hasan.
Lancaster University, 2022. 134 p.

Research output: ThesisDoctoral Thesis

Harvard

APA

Vancouver

Mansoor MH. Combinatorial Optimisation: Relaxation, Duality and Heuristics. Lancaster University, 2022. 134 p. doi: 10.17635/lancaster/thesis/1708

Author

Bibtex

@phdthesis{9bded595c4cb4781ac4d75e84598d3a1,
title = "Combinatorial Optimisation: Relaxation, Duality and Heuristics",
abstract = "Relaxation and dual-based heuristics have been a part of research in combinatorial optimisation since the early 1970s. This thesis extends that strand of research into less popular forms of relaxations in particular surrogate relaxation, which is theoretically a tighter relaxation than the two most common relaxations (Linear Programming and Lagrangian relaxations). The aim is to show surrogate dual information can add to the performance of dual-based matheuristics. In chapter 2 we provide some theoretical results related to surrogate and group relaxation. We follow it up with an exact and a heuristic surrogate dual method along with computation results, in chapters 3 and 4 respectively.Finally, in chapter 5, we take a step back and seek to make an introductory empirical investigation into the value of good and better dual solutions in guiding primal heuristics using LP relaxation as an example.",
keywords = "Combinatorial optimisation, Matheuristics, Dual-based heuristics, multidimensional knapsack, Surrogate Relaxation",
author = "Mansoor, {M Hasan}",
year = "2022",
doi = "10.17635/lancaster/thesis/1708",
language = "English",
publisher = "Lancaster University",
school = "Lancaster University",

}

RIS

TY - BOOK

T1 - Combinatorial Optimisation

T2 - Relaxation, Duality and Heuristics

AU - Mansoor, M Hasan

PY - 2022

Y1 - 2022

N2 - Relaxation and dual-based heuristics have been a part of research in combinatorial optimisation since the early 1970s. This thesis extends that strand of research into less popular forms of relaxations in particular surrogate relaxation, which is theoretically a tighter relaxation than the two most common relaxations (Linear Programming and Lagrangian relaxations). The aim is to show surrogate dual information can add to the performance of dual-based matheuristics. In chapter 2 we provide some theoretical results related to surrogate and group relaxation. We follow it up with an exact and a heuristic surrogate dual method along with computation results, in chapters 3 and 4 respectively.Finally, in chapter 5, we take a step back and seek to make an introductory empirical investigation into the value of good and better dual solutions in guiding primal heuristics using LP relaxation as an example.

AB - Relaxation and dual-based heuristics have been a part of research in combinatorial optimisation since the early 1970s. This thesis extends that strand of research into less popular forms of relaxations in particular surrogate relaxation, which is theoretically a tighter relaxation than the two most common relaxations (Linear Programming and Lagrangian relaxations). The aim is to show surrogate dual information can add to the performance of dual-based matheuristics. In chapter 2 we provide some theoretical results related to surrogate and group relaxation. We follow it up with an exact and a heuristic surrogate dual method along with computation results, in chapters 3 and 4 respectively.Finally, in chapter 5, we take a step back and seek to make an introductory empirical investigation into the value of good and better dual solutions in guiding primal heuristics using LP relaxation as an example.

KW - Combinatorial optimisation

KW - Matheuristics

KW - Dual-based heuristics

KW - multidimensional knapsack

KW - Surrogate Relaxation

U2 - 10.17635/lancaster/thesis/1708

DO - 10.17635/lancaster/thesis/1708

M3 - Doctoral Thesis

PB - Lancaster University

ER -