Ph.D. Theses

Permanent URI for this collection

https://digitalarchive.library.bogazici.edu.tr/handle/123456789/11650

Browse

Now showing 1 - 12 of 12

Competitive learning with additional information for solving multi-facility weber problem
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2007., 2007.) Özkısacık, Kerem Can.; Altınel, İ. Kuban.
It is possible to remark that the mathematical formulation of clustering analysis problem is similar to a certain class of location problems. Known as the multi{facility Weber problem, it is a non{convex continuous optimization problem where a prede- termined number of facilities are located on the plane such that demand weighted summation of distances between each customer and its closest facility is minimized. With further investigation, we pointed out that the clustering analysis formula- tion is a special case of this facility location problem mentioned above. Motivated by this relation, we revised two algorithms of competitive learning, namely vector quanti- zation and Kohonen type networks, to use additional information and applied them to solve the Weber problem. The results obtained with the new techniques are superior than those reported previously in the literature. In the second part of the study, we investigated the probabilistic version of the Weber problem. In this version, customer locations are not ¯xed and they are assumed to be distributed randomly. Methods proposed previously are revised to handle probabilistic case as well. To the best of our knowledge, ¯rst experimental results are reported for this type of the problem and traditional techniques are compared with newly proposed methods. Furthermore, we proposed an approximation scheme for dealing with more general probability distributions.
Controlled sink mobility and wireless sensor network lifetime maximization
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2014., 2014.) Keskin, M. Emre.; Altınel, İ. Kuban.
The design of a Wireless sensor network (WSN) involves the optimal deployment and activity scheduling of the sensors as well as optimal deployment or routing of sinks and optimal routing of data flows. In this thesis, we first attempt to reflect the limited nature of the mobile sink by considering nonzero sink travel times and taking the data accumulated during the sink travel time into account. The total sink travel time is considered as a part of the network lifetime. We provide two mixed integer linear programming (MILP) models that are flexible enough to handle multiple sink tours as well as a hop limited data routing protocol in which data is routed from sensors towards the sink through the shortest paths including at most a predefined number of hops. We propose heuristic procedures for the solution of the MILP models and show the importance of considering nonzero sink travel times by numerical experiments. An extension to these MILP models that possess a framework with multiple mobile sinks is also developed and it is demonstrated that sink travel times can be neglected for multiple sinks. Later on, we develop several MILP models which integrate sensor placement, activity scheduling and data routing issues with the static sink placement or mobile sink routing design issues. The breadth of the integration changes from the integration of the sink routing problem with the data routing problem to the integration of the sensor placement, activity scheduling, sink routing problems with data routing problems. We study the effect of the integration ofWSN design issues by comparing the objective value of the models on a large set of randomly generated problem instances. We also devise heuristics and a branch-and-price algorithm for the solution of the proposed MILP models and empirically test their accuracy and efficiency on a large set of test instances.
Coverage, sink location and routing problems in wireless sensor networks
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009., 2009.) Güney, Evren.; Altınel, İ. Kuban.; Aras, Necati.
Recent advances in electronics and telecommunications have enabled the development of low-cost, low-power multifunctional sensor devices that are powered by batteries and communicating through wireless channels over small distances. When a large number of these devices work collaboratively for certain purposes, they form a network which is called a wireless sensor network (WSN). Due to their benefits and inherent characteristics, WSNs give rise to a broad-range of many real-life applications. There are various design issues in the construction of WSNs. In this study, we focus on three important classes of problems, which are Point Coverage, Sink Location and Data Routing Problems. We propose a Binary Integer Programming (BIP) formulation to model the coverage problem and develop various heuristics to solve it. Both the Routing Problem (RP), which involves finding the most energy efficient sensor-tosink routes and Sink Location Problem (SLP), which is determining the optimal sink locations are important design issues to extend the lifetime of a WSN. However, the joint optimization of these two problems results in a more efficient network design, so we develop several Mixed Integer Linear Programming (MILP) formulations and propose optimum solution techniques and heuristics to solve them. Finally, we solve the complete integrated model, which consists of the coverage, sink location and data routing problems simultaneously. We call this hard problem as the Coverage, Location and Routing Problem (CLRP) and develop new mathematical programming formulations. We propose a nested solution procedure, where in the first level of this approach, good sensor locations are sought by using some metaheuristics. In the second level, we solve the remaining sink location and routing problem using efficient heuristics.
Leader-follower games for influence spread in social networks
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Tanınmış, Kübra.; Aras, Necati.; Altınel, İ. Kuban.
Influence Maximization Problem involves nding a set of individuals in a social network to trigger an in uence/information spread, i.e., a seed set, such that the maximum possible number of individuals are in uenced. In this thesis, two competitive variants of the Influence Maximization Problem where two players make decisions sequentially in the form of a Stackelberg game are introduced. In the Influence Maximization with Deactivation the objectives of the leader and the follower are maximization and minimization of the spread, respectively. While the Misinformation Spread Minimization Problem has a reverse situation, in both problems the leader takes the follower's optimal response into account. Both problems are formulated as mixed-integer bilevel linear programs with a two-stage stochastic program in the lower level, by enumerating the diffusion scenarios due to the well known Linear Threshold model. In the solution phase, firstly several matheuristic methods are proposed where the follower's optimal decisions are approximated via Sample Average Approximation method. For the MSMP, additionally a state-of-the art in uence maximization method is integrated into the developed algorithms. The proposed methods are evaluated on small instances where an optimal solution can be found via complete enumeration as well as larger instances where the algorithms are compared to each other. Then, a branch-and-cut algorithm for mixed-integer bilevel problems is enriched with a variable bound update procedure for the Influence Maximization with Deactivation which is shown to increase the time effciency. An exact algorithm for bilevel interdiction problems is improved substantially, tested on various problem types including the Misinformation Spread Minimization Problem and yields signi cantly better results.
Location-allocation problems with multi-commodity flows: exact and approximate solution methods
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2011., 2011.) Akyüz, Mehmet Hakan.; Altınel, İ. Kuban.; Öncan, Temel.
A multi-commodity and capacitated extension of the Multi-facility Location-Allocation Problem, namely the Multi-commodity Capacitated Multi-facilityWeber Problem (MCMWP) is considered, and exact and approximate solution methods are proposed. The MCMWP is new in the literature and aims to locate new facilities on the plane in order to meet the demand of customers for multiple types of products. The objective is to minimize total transportation costs, which are proportional to the distances measured with lr-norm for 1 · r < 1 between the facilities and customers, while satisfying the demand and capacity restrictions. The MCMWP has a non-convex objective function and it is difficult to solve. In the first part of this work, approximate solution methods are suggested. The first one of them is based on the Cooper's alternate location-allocation (ALA) heuristic and both contin- uous and discrete variants of the ALA heuristics are developed for the MCMWP. The second approximate solution method employs Discrete Approximation (DA) strategies. When the location of facilities are selected from a finite set of candidate sites it is possible to obtain approximate solutions of the MCMWP. The proposed DA strategies enable to obtain not only upper bounds but also lower bounds on the MCMWP. The third approximate solution method employs a Lagrangean Relaxation (LR) scheme. The MCMWP is relaxed such that the LR subproblems are variants of Multi-facility Weber Problems (MWP) with no capacity restrictions. The last approximate solution method produces confidence intervals for the optimal solution of the MCMWP using the Fisher-Tippett's theorem. In the second part of this work, exact solution methods are developed for both the Capacitated MWP (CMWP) and MCMWP. In particular, two different branch-and-bound (BB) algorithms, which partition allocation and location spaces, are suggested to exactly solve the CMWP and MCMWP. Lastly, a beam search heuristic using the location space based BB algorithm is implemented.
Network flows with conflict constraints
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Şuvak, Zeynep.; Altınel, İ. Kuban.; Aras, Necati.
It is a commonly used approach to model real life problems as network ﬂow prob lems and they appear in a wide range of areas including telecommunication, wireless networks, transportation, healthcare and scheduling. Our focus in this thesis is on an extension of network ﬂow problems with conﬂict constraints that prevent the simul taneous usage of some arc pairs to send ﬂow. We particularly concentrate on four of them: the minimum cost noncrossing ﬂow problem on layered networks, the minimum cost ﬂow problem with conﬂicts, the maximum ﬂow problem with conﬂicts and the assignment problem with conﬂicts. The minimum cost noncrossing ﬂow problem on layered networks, which emerges from the quay crane scheduling problem in container terminals, is proven to be NP-hard. Further complexity results including the strong NP-hardness and the non-existence of polynomial time approximation algorithm for the the minimum cost ﬂow problem with conﬂicts on general networks are also pro vided. Moreover, polynomially solvable special cases for the minimum cost noncrossing ﬂow problem on layered networks and the assignment problem with conﬂicts, which is known to be NP-hard, are explored. Similarly, the conditions which limit the number of feasible solutions with a polynomial number are indicated for the minimum cost ﬂow problem with conﬂicts and the maximum ﬂow problem with conﬂicts taking ad vantage of the conﬂict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to ﬁnd an initial feasible solution are deﬁned. Exact solution algorithms in cluding a branch-and-bound algorithm enriched with the subroutines that exploit the special structure of the considered problem, an improved Russian doll search algorithm and a Benders decomposition with strengthened cuts are proposed. The methods are tested on a large set of test instances and they are shown to be superior than solving the underlying mathematical formulations with a commercial optimization solver.
New neurocomputational approaches for estimating road travel distances and for solving the euclidean traveling salesman problem
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1999., 1999.) Aras, Necati.; Altınel, İ. Kuban.
Neural networks are among the most rapidly developing new scientific tools. There are numerous publications reporting their success in estimation and optimization. This work concentrates on both of these aspects and applies neural networks for solving two problems from operations research. One of the problems is the distance estimation problem, which mainly deals with the estimation of the length of the shortest road connecting two points on the earth surface. First, multilayer perceptrons have been adopted. Then, a neural clustering strategy which uses the principle of vector quantization has been utilized prior to the estimation. Thr results are superior than those reported in the literature. The other problem is the well-known Euclidean traveling salesman problem. It tries to determine the shortest tour passing throgh the cities of a given set by visiting aech city exactly once. A new adaptive scheme has been developed in order to solve this problem. The new approach incorporates explicit statistical information obtained from the city coordinates into the adaptation mechanism of Kohonen's self-organizing map. Results obtained for different problems are better than the previous ones. The new approach is then adapted to the solution of the Euclidean Hamiltonian path problem whose combination with the decomposition philosophy resulted in a highly all-neural Eulidean traveling salesman problem algorithm.
On unidirectional cyclic layouts, Hamiltonian circuits, capacitated vehicle routes and minimal spanning trees
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2004., 2004.) Öncan, Temel.; Altınel, İ. Kuban.
This thesis consists of four major parts. The first part is on the Unidirectional Cyclic Layout Problem (UCLP). First, new efficient heuristics for the UCLP are proposed based on the ideas originally proposed for two well-known combinatorial optimization problems: The Asymmetric Traveling Salesman Problem (ATSP) and the Linear Ordering Problem (LOP). Then, we particularly consider the balanced case of the UCLP's satisfying the additional conservation of flow assumption: the material flow is conserved at every workstation and we develop a Branch and Bound algorithm for the Balanced UCLP (BUCLP). In the second part, we propose new extended ATSP formulations with O(n3) constraints and we analyze the strengths of their linear programming (LP) relaxation both analytically and experimentally. It is shown that the LP relaxation of one of the new formulations can have optimal objective value larger than the LP relaxation of the ATSP's multi-commodity flow formulations. In addition, we also propose new extended ATSP formulations with O(n2) constraints and compare their strengths with the ones of known ATSP formulations with O(n2) constraints. Finally, in the third and fourth parts, a new enhancement of the Clarke and Wright's savings heuristic for the Capacitated Vehicle Routing Problem and new enhancements of the Esau and Williams' savings heuristic for the Capacitated Minimal Spanning Tree Problem are respectively proposed.
Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2010., 2010.) Türkoğulları, Yavuz Boğaç.; Altınel, İ. Kuban.; Aras, Necati.
A wireless sensor network consists of distributed autonomous tiny electronic devices called sensors. They have limited energy and capability for sensing, data processing and communication, but they can collectively behave to provide an effective network that monitors a region, and transmit information to gateway nodes called sinks. In most of the applications, the network must operate for long periods of time, so the available energy resources of the sensors must be managed efficiently. In this thesis we first develop mixed-integer linear programming models to maximize network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data routes and activity schedules of the deployed sensors over a finite planning horizon subject to coverage, flow conservation, energy consumption and budget constraints. Then, we propose valid inequalities, which we use with a new branch-and-price algorithm to solve the problem exactly. Although they provide stronger linear programming relaxations and thus increase the quality of the formulation, the size of the networks for which the model can be solved exactly is very limited. Hence, we develop approximate solution heuristics using techniques such as the Lagrangean relaxation, column generation and a greedy selection criterion. Based on the computational experiments we can say that they are accurate and efficient. The minimum cost coverage problem, which consists of the deployment of sensors over a sensor field modeled as a set of finite points so that total cost is minimized subject to the coverage requirements, generalizes the famous set covering problem. We provide a polyhedral analysis of this general problem, which has not been studied very much previously. We develope a procedure that generates valid inequalities and a sufficient condition for facet definition, and a cutting plane. Experiments show that the proposed valid inequality cuts of the fractional optimum and improve considerably the linear programming relaxation lowerbound. Finally, we revise the convergence proof of the deflected subgradient algorithm that uses conditional subgradients and suggest some refinements.
Optimal server placement, service deployment, and resource allocation in next-generation computer network
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022., 2022) Ahat, Betül.; Aras, Necati.; Altınel, İ. Kuban.
With the expansion of mobile devices and new trends in mobile communication technologies, there is an increasing demand for diversified services. To accommodate a large number of services on a common network, it becomes crucial for an operator to optimize resource allocation decisions to satisfy the service requirements in an economical way. In this thesis, the computation architecture design problem is considered first where server placement, service deployment, and task assignment decisions are optimized to maximize the revenue of the operator. The problem is modeled as a mixed-integer linear programming (MILP) formulation and a Lagrangian relaxation- based heuristic algorithm is proposed. Then, the concept of network slicing, which partitions a single physical network into multiple isolated slices, is examined. In the deterministic network slicing problem, the capacities of the computational resources are partitioned into slices each of which is customized for a particular service type. An MILP formulation is presented that takes the delay requirements of services into account. Additionally, two algorithms based on Benders decomposition are devised along with some valid inequalities and cut generation techniques. The problem definition is also extended to consider the stochastic behavior of the service requests. A two-stage stochastic integer programming model is constructed which is then converted into a large-scale MILP model by defining a set of scenarios for the random parameters. A similar decomposition approach is also applied to the stochastic network slicing problem. In our computational study on randomly generated test instances, the validity of our models is assessed and the effectiveness of the proposed solution approaches is demonstrated.
Optimally locating facilities with variable characteristics
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2011., 2011.) Küçükaydın, Hande.; Altınel, İ. Kuban.; Aras, Necati.
Facility location problems aim at optimally locating facilities like plants, warehouses, convenience stores, shopping malls etc. They can have di erent objectives such as maximizing the pro t gained from the customers or minimizing the costs of locating facilities and serving the customers. In this thesis, we mainly focus on competitive facility location problems which constitute a special family. In a competitive facility location problem, a rm or franchise is concerned with installing new facilities to serve customers in a market where existing facilities with known locations and attractiveness levels compete for increasing their market share and pro t. We can classify these problems into two groups: those with non-reactive competition and those with reactive competition. Three di erent types of competitive facility location models are proposed in order to determine the locations and attractiveness levels of the new facilities to maximize the pro t in this thesis. The rst one belongs to the former class, where the last two models fall into the latter one. We formulate the rst one as a mixed-integer nonlinear programming problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and a branch-and-bound method with nonlinear programming relaxation. The computational results obtained on a set of problem instances show that the branch-and-bound method using nonlinear programming relaxation is the most e cient and accurate solution method in order to solve the proposed problem. We consider next an extension of this model by relaxing the assumption that the competitor in the market does not react to the opening of new facilities. In other words, the competitor can react by adjusting the attractiveness levels of its existing facilities with the objective of maximizing its own pro t. To this end, a bilevel mixed-integer nonlinear programming model is formulated. We transform this bilevel model into an equivalent one-level mixed-integer nonlinear program and solve it by a global optimization method. For this problem, we also consider a scenario in which the new entrant rm ignores the reaction of the competitor. The experimental results indicate that anticipating the competitor's reaction by including this into his optimization problem increases the pro t of the new entrant rm, whereas the competitor's pro t is decreased. The last competitive facility location model relaxes the limitation about the competitor's reaction: now the competitor can also open new facilities, close existing ones and/or adjust their attractiveness. This also formulates a bilevel mixed-integer nonlinear programming problem which we try to solve by combining tabu search with global optimization algorithms. We develop three di erent tabu search methods and the computational results on a set of problem instances for comparing the performance of the solution methods show that the third tabu search method is the most accurate one, while the second tabu search method is the most e cient solution procedure. Finally, we consider a di erent facility location problem which takes the customer preferences into account. The facilities are not necessarily identical and customers visit di erent types of facilities according to some given probability distribution and the maximum distance which they are willing to travel. We formulate a binary linear programming problem and solve it by three procedures that include a Lagrangean heuristic whose solution is improved further using a local search method. Based on the experimental results carried out on a set of problem instances the third solution method is the most e cient one. However, a statistical analysis on the quality of the solutions states that there is no signi cant di erence between the three solution procedures.
The determination of treatment plans for volumetric modulated ARC therapy
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Dursun, Pınar.; Altınel, İ. Kuban.; Taşkın, Zeki Caner.
Volumetric modulated arc therapy is the state-of-the-art technique for external radiation therapy treatment, where radiation can be delivered continuously during the rotation of the linear accelerator’s gantry. This property makes this technique power ful in obtaining high conformal plans requiring short treatment times. However, the multileaf collimator system shapes the radiation beam continuously, thus the resulting apertures are interdependent due to leaf motion limitations, which makes treatment planning hard. In this thesis, we ﬁrst propose two mixed integer linear programming formulations minimizing total radiation delivered to the patient subject to the geo metrical and clinical requirements. Then, we develop exact solution algorithms that combine Benders decomposition with certain acceleration strategies and implement branch-and-price method where pricing subproblem is decomposable by rows of mul tileaf collimator and can be solved as a shortest path problem. We investigate their performance on a large set of test instances obtained from an anonymous real prostate cancer data. The computational results reveal that they are eﬃcient and outperform a widely used commercial solver. In particular, branch-and-price implementation is capable to ﬁnd optimal solutions for larger problem instances. However, they cannot provide realistic plans for real clinical problems because of their large size. In order to address this issue, we develop a two-phase column generation based heuristic that tunes the parameters of dose-volume requirements and yields an automated treatment planning environment, which does not require any human intervention. We test its performance on real prostate data sets and compare the quality of the generated plans with those obtained by a widely used commercial treatment planning system. Results show that it can obtain medically acceptable plans requiring signiﬁcantly less radiation in reasonable computation times.

Browse

Browsing Ph.D. Theses by Author "Altınel, İ. Kuban."

Results Per Page

Sort Options