Download the full-sized PDF of Advanced Integer Linear Programming Techniques for Large Scale Grid-Based Location ProblemsDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Advanced Integer Linear Programming Techniques for Large Scale Grid-Based Location Problems Open Access


Other title
Grid-Based Location Problems (GBLPs)
Relax-and-Fix-Based Decomposition (RFBD)
Integer linear Programming (ILP)
Large-Scale Optimization
Partition-and-Fix-Based Decomposition (PFBD)
Type of item
Degree grantor
University of Alberta
Author or creator
Alam, Md. Noor-E-
Supervisor and department
John Doucette, Dept. of Mechanical Engineering
Examining committee member and department
Askari-Nasab, Hooman (Dept. of Civil Engineering)
Secanell, Marc (Dept. of Mechanical Engineering)
Doucette, John (Dept. of Mechanical Engineering)
Lipsett, Mike (Dept. of Mechanical Engineering)
Xue, Deyi (Dept. of Mechanical and Manufacturing Engineering, University of Calgary)
Department of Mechanical Engineering
Engineering Management
Date accepted
Graduation date
Doctor of Philosophy
Degree level
Many real-world facility location problems can be approximated by a grid-based system of small sized cells, which can then be used to model a heterogeneous demand distribution. We can also relate an amount of supply for each cell from its supply distribution relationships with the various potential facility locations in other cells. Based on these demand distributions and supply relationships, we can determine the optimal capacities and locations to place facilities while fulfilling certain objectives. Here, these types of location problems are referred to as grid-based location problems (GBLPs). In the GBLPs we address herein, we seek the optimum number, location(s), and size(s) of facilities to place. The applications of GBLPs are wide ranging, and include problems in business, engineering, defense, resource exploitation, and medical science. To make such complex decisions, we need to develop mathematical models in the form of integer linear programming (ILP) problems, and associated procedures to solve them. To model a real-world GBLP, we must generally consider a large number of discrete variables, complex demand and supply distributions, and fixed costs. Combinations of these considerations conspire to produce large-scale ILP problems, which are often not scalable and often become intractable even for small instances. In this research, we propose a number of GBLP ILP models for two real-world applications: a light post location problem and a wireless transmitter location problem. Our experimental results show that our ILP models are efficient in solving moderately-sized problems but are computationally difficult to solve for large-scale instances. As a result, we develop two decomposition techniques to solve these large-scale instances. To reduce the solution time further, we also propose integration of logical restrictions and valid inequalities. Our experiments demonstrate that the proposed approaches outperform the exact solution method, significantly reducing solution runtimes while not severely impacting optimality. The results of this work is expected to have a significant impact in solving large-scale GBLP ILP models that result from real-world business, engineering, and science problems.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
Md. Noor-E-Alam, Andrew Ma, John Doucette, “Integer Linear Programming Models for Grid-Based Light Post Location Problem”, European Journal of Operational Research, vol. 222, pp. 17-30, October, 2012.Md. Noor-E-Alam and John Doucette, “Relax-and-Fix-Based Decomposition Technique for Solving Large Scale GBLPs”, Computers and Industrial Engineering, vol. 63, pp. 1062-1073, December, 2012.Md. Noor-E-Alam, John Doucette, “Solving Large Scale Fixed Cost Integer Linear Programming Models for Grid-Based Location Problems with Heuristic Techniques”, Computers & Operations Research, 2012. (in review)Md. Noor-E-Alam, Brody Todd and John Doucette, “Integer Linear Programming Model for Grid-Based Wireless Transmitter Location Problems”, International Journal of Operational Research, 2012. (in review)

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 4468271
Last modified: 2015:10:12 21:21:01-06:00
Filename: Alam_Md. Noor-E-_Spring 2013.pdf
Original checksum: ee43564e4c3c9fa35c39dc255285f460
Well formed: true
Valid: true
Status message: Too many fonts to report; some fonts omitted. Total fonts = 1129
Page count: 257
Activity of users you follow
User Activity Date