In this paper, we study the hub location problem of an entrant airline that tries to maximize
its share in a market with already existing competing players. The problem is modelled as a nonlinear
integer program, which is intractable for off-the-shelf commercial solvers, like CPLEX and
Gurobi, etc. Hence, we propose four alternate approaches to solve the problem. The first among
them uses the Kellys cutting plane method, the second is based on a mixed integer second order
conic program reformulation, the third uses the Kellys cutting plane method within Lagrangian
relaxation, while the fourth uses second order conic program within Lagrangian relaxation. The
main contribution of this paper lies in the fourth approach, which along with refinements is the
most efficient. Many of the problem instances that were not solvable using standard techniques,
like the Kellys cutting plane method, have been solved in less than 2 hours of CPU time within
1% optimality gap.
