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

  • Author / Creator
    Alam, Md. Noor-E-
  • 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.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
  • Specialization
    • Engineering Management
  • Supervisor / co-supervisor and their department(s)
  • Examining committee members and their departments
    • Xue, Deyi (Dept. of Mechanical and Manufacturing Engineering, University of Calgary)
    • Secanell, Marc (Dept. of Mechanical Engineering)
    • Doucette, John (Dept. of Mechanical Engineering)
    • Askari-Nasab, Hooman (Dept. of Civil Engineering)
    • Lipsett, Mike (Dept. of Mechanical Engineering)