Endüstri Mühendisliği Bölümü Koleksiyonu

Permanent URI for this collectionhttps://hdl.handle.net/20.500.11779/1942

Browse

Now showing 1 - 4 of 4

Citation - WoS: 26
Citation - Scopus: 26
An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks
(Elsevier, 2019) Güney, Evren
The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that converges to the current state-of-the-art 1-1/e bound asymptotically. Experimental analysis indicate that the new method is superior to the state-of-the-art in terms of solution quality and this is one of the few studies that provides approximate optimal solutions for certain real life social networks.
An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks (vol 503, Pg 589, 2019)
(Elsevier, 2020) Güney, Evren
The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program thatapproximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently,we propose a linear programming relaxation based method with a provable worst casebound that converges to the current state-of-the-art 1 − 1/e bound asymptotically. Experimental analysis indicate that the new method is superior to the state-of-the-art in termsof solution quality and this is one of the few studies that provides approximate optimalsolutions for certain real life social networks.
Citation - WoS: 16
Citation - Scopus: 18
Gradual Covering Location Problem With Multi-Type Facilities Considering Customer Preferences
(Elsevier, 2020) Küçükaydın, Hande; Aras, Necati
In this paper, we address a discrete facility location problem where a retailer aims at locating new facilities with possibly different characteristics. Customers visit the facilities based on their preferences which are represented as probabilities. These probabilities are determined in a novel way by using a fuzzy clustering algorithm. It is assumed that the sum of the probabilities with which customers at a given demand zone patronize different types of facilities is equal to one. However, among the same type of facilities they choose the closest facility, and the strength at which this facility covers the customer is based on two distances referred to as full coverage distance and gradual (partial) coverage distance. If the distance between the customer location and the closest facility is smaller (larger) than the full (partial) coverage distance, this customer is fully (not) covered, whereas for all distance values between full and partial coverage, the customer is partially covered. Both distance values depend on both the customer attributes and the type of the facility. Furthermore, facilities can only be opened if their revenue exceeds a certain threshold value. A final restriction is incorporated into the model by defining a minimum separation distance between the same facility types. This restriction is also extended to the case where a minimum threshold distance exists among facilities of different types. The objective of the retailer is to find the optimal locations and types of the new facilities in order to maximize its profit. Two versions of the problem are formulated using integer linear programming, which differ according to whether the minimum separation distance applies to the same facility type or different facility types. The resulting integer linear programming models are solved by three approaches: commercial solver CPLEX, heuristics based on Lagrangean relaxation, and local search implemented with 1-Add and 1-Swap moves. Apart from experimentally assessing the accuracy and the efficiency of the solution methods on a set of randomly generated test instances, we also carry out sensitivity analysis using a real-world problem instance.
Citation - WoS: 31
Citation - Scopus: 33
Large-Scale Influence Maximization Via Maximal Covering Location
(Elsevier, 2020) Güney, Evren; Ruthmair, Mario; Sinnl, Markus; Leitner, Markus
Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based on Benders decomposition is proposed and a relation between obtained Benders optimality cuts and submodular cuts for correspondingly defined subsets is established. We introduce preprocessing tests, which allow us to remove variables from the model and develop efficient algorithms for the separation of Benders cuts. Both aspects are shown to be crucial ingredients of the developed branch-and-cut algorithm since real-life social network instances may be very large. In a computational study, the considered variants of this branch-and-cut algorithm outperform the state-of-the-art approach for influence maximization by orders of magnitude.

Browse

Browsing Endüstri Mühendisliği Bölümü Koleksiyonu by Publisher "Elsevier"