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.

► Focuses to develop advance technique to solve large scale grid-based location problems. ► It proposes a relax-and-fix-based decomposition technique. ► Decomposition technique is implemented within a standard modeling language, AMPL and solved with the solver, CPLEX. ► Different large test-case grids are solved with the proposed method. ► Results show that our proposed decomposition technique is quite efficient.