Back to search

University of Waterloo

A Feasible Lagrangian Approach with Application to the Generalized Assignment Problem

Abstract

dc:description.abstract

Lagrangian relaxation is a widely used decomposition approach to solve difficult optimization problems that exhibit special structure. It provides a lower bound on the optimal objective of a minimization problem. On the other hand, an upper bound and quality feasible solutions may be obtained by perturbing solutions of the subproblem. In this thesis, we enhance the Lagrangian approach by using information at the subproblem to push for feasibility to the original problem. We exploit 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 valid inequalities. As cuts are added to the subproblem, it inevitably becomes harder to solve. We propose to solve it under a time limit and adjust the Lagrangian bound accordingly. Two variants of the approach are explored that we call a Modified Lagrangian approach and a Feasible Lagrangian approach. We use the Generalized Assignment Problem for testing. We develop two methodologies based on minimal covering inequalities. The first solves the subproblem repeatedly for a given number of iterations and generates minimal cover inequalities that are either discarded or passed on to subsequent Lagrangian iterations. The second starts with initial multipliers and repeatedly solves the subproblem until a feasible solution is attained. At that point, the regular Lagrangian approach is used to find a lower bound. We test on GAP instances from the literature and compare the lower bound to the Lagrangian bound and the feasible solution to the best known solution in the literature. The results demonstrate that the proposed feasible Lagrangian approach leads to improved lower bounds and good quality feasible solutions.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Punjwani, Shahroz
Advisors dc:contributor.advisor
  • Gzara, Fatma
  • Elhedhli, Samir

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/14441

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Punjwani, Shahroz. A Feasible Lagrangian Approach with Application to the Generalized Assignment Problem. University of Waterloo, 2019. http://hdl.handle.net/10012/14441