Relax‐and‐fix decomposition technique for solving large scale grid‐based location problems

Many problems in business, engineering, defence, resource exploitation, and even the medical sciences with location aspects can be expressed as grid‐based location problems (GBLPs), modeled as integer linear programming problems. Such problems are often very computationally complex to solve. We develop a relax‐and‐fix‐based decomposition approach to solve large‐scale GBLPs, which we demonstrate will significantly reduce solution runtimes while not severely impacting optimality. We also introduce problem‐specific logical restrictions, constraints that reduce the feasible region and the resulting branch‐and‐bound tree with minimal reductions in optimality.