Endüstri Mühendisliği Bölümü Koleksiyonu
Permanent URI for this collectionhttps://hdl.handle.net/20.500.11779/1942
Browse
2 results
Search Results
Article Citation - WoS: 3Citation - Scopus: 5Qubo Formulations and Characterization of Penalty Parameters for the Multi-Knapsack Problem(IEEE-Inst Electrical Electronics Engineers Inc, 2025) Guney, Evren; Ehrenthal, Joachim; Hanne, ThomasThe Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using Quadratic Unconstrained Binary Optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants-the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)-and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.Article Citation - WoS: 12Citation - Scopus: 19Minimizing the Misinformation Spread in Social Networks(Taylor and Francis, 2019-11-21) Güney, Evren; Kuban, İ. Kuban Altınel; Tanınmış, Kübra; Aras, Necati; Altinel, I. KubanThe Influence Maximization Problem has been widely studied in recent years, due to rich application areas including marketing. It involves finding k nodes to trigger a spread such that the expected number of influenced nodes is maximized. The problem we address in this study is an extension of the reverse influence maximization problem, i.e., misinformation minimization problem where two players make decisions sequentially in the form of a Stackelberg game. The first player aims to minimize the spread of misinformation whereas the second player aims its maximization. Two algorithms, one greedy heuristic and one matheuristic, are proposed for the first player’s problem. In both of them, the second player’s problem is approximated by Sample Average Approximation, a well-known method for solving two-stage stochastic programming problems, that is augmented with a state-of-the-art algorithm developed for the influence maximization problem.