Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
253
views
106
downloads
Cite This
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 specifically, 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 differences between algorithms of smooth optimization are in the calculation of search directions, line searches for finding 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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
E. Gündoğdu, “Exact decomposition algorithms for nonlinear location and hub location problems,” Ph.D. - Doctoral Program, Middle East Technical University, 2018.