Endüstri Mühendisliği
Permanent URI for this community
Browse
Browsing Endüstri Mühendisliği by Author "Ahat, Betül."
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Integer programming formulations and benders decomposition for maximum induced matching problem(Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2016., 2016.) Ahat, Betül.; Taşkın, Zeki Caner.; Ekim, Tınaz.In this thesis, we investigate Maximum Induced Matching problem (MIM), nding an induced matching having the largest cardinality. The problem is NP-hard for general graphs. We develop a binary integer programming formulation with less decision variables compared to other formulations in the literature. Then, we extend the problem for vertex-weighted graphs and introduce Maximum Vertex-Weighted Induced Matching problem (MVWIM). We introduce edge-weighted version of MIM and call it Maximum Edge-Weighted Induced Matching problem (MEWIM). We adapt formulations found in the literature and our formulation to solve MVWIM and MEWIM instances. In generalized version of Maximum Weighted Induced Matching problem (MWIM), we assume both vertices and edges have weights, and give a binary integer programming formulation for it. Since it has many decision variables and constraints, we implement Benders decomposition approach to partition the problem into smaller problems. Then, we add some valid inequalities to our formulation to improve the e ciency of our algorithm. To test the performance of our methodology, we generate random graphs with di erent densities. By looking at computational results, it can be seen that our approach solves instances with medium and large densities signi cantly faster than other methods in the literature.Item 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.