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

  • Large-Scale Optimization
  • Grid-Based Location Problems (GBLPs)
  • Relax-and-Fix-Based Decomposition (RFBD)
  • Partition-and-Fix-Based Decomposition (PFBD)
  • Integer linear Programming (ILP)

• Graduation date

  Spring 2013

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3WW5S

• 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.