Exact decomposition algorithms for nonlinear location and hub location problems

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2018

Öğrenci: EMİNE GÜNDOĞDU

Danışman: SİNAN GÜREL

Özet:

Developing exact solution algorithms to solve difficult optimization problems is one of the most important subjects in the operations research literature. In this dissertation, we develop Benders decomposition based exact solution algorithms (BDTAs) for handling nonlinearity in three selected nonlinear integer location/hub location problems. The first and second problem include nonlinear capacity constraints, while in the last problem, both objective function and the capacity constraints are nonlinear. In our decomposition algorithms, we used problem specific, logic based feasibility and optimality cuts. In addition to BDTAs, we propose a MISOCP reformulation for solving the nonlinear integer model, which arises in wireless local area networks, to optimality by using commercial solvers. Our computational study demonstrates that the performance of MISOCP is better than that of Benders decomposition based algorithms. This reformulation is general for any convex objective function as long as the constraints have the same structure as those in the first problem that we studied in this dissertation. The second problem includes nonlinear constraints in which product of binary variables exist and we develop a branch-and-check algorithm with several enhancement steps. In the last problem, nonlinear terms in the objective function and constraints are handled in Benders decomposition scheme. Our computational study demonstrates that the performance of Benders decomposition type algorithm is better than that of commercial solvers for especially difficult instances.