Final published version, 2.02 MB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Research output: Thesis › Doctoral Thesis
Research output: Thesis › Doctoral Thesis
}
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 -