Candidate: Shahroz Saleem Punjwani
Title:
A
Feasible
Lagrangian
Approach
with
Application
to
the
Generalized
Assignment
Problem.
Supervisors: Professors Samir Elhedhli and Fatma Gzara
Abstract:
Lagrangian relaxation is a widely used decomposition approach to solve difficult optimization problems that exhibit special structure. The relaxation provides a lower bound on the optimal objective function value of a for minimization problem leading to duality gap which can be closed using a branch-and-price methodology. On the other hand, an upper bound and good feasible solutions may be obtained by perturbing partial solutions generated by the Lagrangian subproblem.
In this thesis we aim to exploit the power of Lagrangian relaxation and propose an approach that makes use of information generated by the relaxation to tighten the lower bound and construct high quality feasible solutions. We enhance the Lagrangian approach around the idea that if the solution for the subproblem is pushed towards feasibility to the original problem, it may lead to improved lower bounds as well as good feasible solutions. Our proposed strategy is to solve the subproblem repeatedly at each iteration of the Lagrangian procedure and strengthen it with violated valid inequalities. The hope is to only generate optimality cuts and to find a feasible solution to the original problem at each iteration of the Lagrangian procedure leading to a feasible Lagrangian approach.
To test the feasible Lagrangian approach, we apply it to the Generalized Assignment Problem (GAP). We develop two main methodologies that make use of the minimal set covering inequalities and differ in how to make use of these inequalities. We test both methodologies on GAP instances from the literature and compare the lower bound to the Lagrangian bound and the feasible solution to the best solution in the literature. The results validate that the proposed feasible Lagrangian approach leads to improved lower bounds as well as good quality feasible solutions.