Exact decomposition algorithms for nonlinear location and hub location problems

Download

index.pdf

Date

2018

Author

Gündoğdu, Emine

Metadata

Show full item record

Item Usage Stats

303
views

116
downloads

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.

Subject Keywords

Operations research., Decomposition method., Programming (Mathematics)., Mathematical optimization., Computer algorithms.

URI

http://etd.lib.metu.edu.tr/upload/12622840/index.pdf
https://hdl.handle.net/11511/27814

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Derivative free algorithms for large scale non-smooth optimization and their applications Tor, Ali Hakan; Karasözen, Bülent; Department of Mathematics (2013) In this thesis, various numerical methods are developed to solve nonsmooth and in particular, nonconvex optimization problems. More speciﬁcally, three numerical algorithms are developed for solving nonsmooth convex optimization problems and one algorithm is proposed to solve nonsmooth nonconvex optimization problems. In general, main diﬀerences between algorithms of smooth optimization are in the calculation of search directions, line searches for ﬁnding step-sizes and stopping criteria. However, in nonsmoo...
Optimum design of steel frames using stochastic search techniques based on natural phenomena: A review Saka, M. P. (2007-09-21) Recent developments in optimization techniques that deal with finding the solution of combinatorial optimization problems has provided steel designers with new capabilities. These new optimization techniques use nature as a source of inspiration to develop new procedures for solving complex engineering problems. Among these, evolutionary algorithms mimic evolutionary biology and make use of the principle of the survival of the fittest to establish a numerical search algorithm. In the immune system algorithm...
Effective optimization with weighted automata on decomposable trees Ravve, E. V.; Volkovich, Z.; Weber, Gerhard Wilhelm (Informa UK Limited, 2014-01-02) In this paper, we consider quantitative optimization problems on decomposable discrete systems. We restrict ourselves to labeled trees as the description of the systems and we use weighted automata on them as our computational model. We introduce a new kind of labeled decomposable trees, sum-like weighted labeled trees, and propose a method, which allows us to reduce the solution of an optimization problem, defined in a fragment of Weighted Monadic Second Order Logic, on such a tree to the solution of effec...
Optimising a nonlinear utility function in multi-objective integer programming Ozlen, Melih; Azizoğlu, Meral; Burton, Benjamin A. (2013-05-01) In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective i...
Multi-objective integer programming: A general approach for generating all non-dominated solutions Oezlen, Melih; Azizoğlu, Meral (Elsevier BV, 2009-11-16) In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical epsilon-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical epsilon-constraint method on the bi-objective integer programming problem for the sake of comple...

Citation Formats

E. Gündoğdu, “Exact decomposition algorithms for nonlinear location and hub location problems,” Ph.D. - Doctoral Program, Middle East Technical University, 2018.