13
Arşivlenen Tez
0
DOI Atanmış
0%
DOI Oranı
Anabilim Dalı
Optimization models to identify key RNA regulatory modules in cancer
Micro RNAs (miRNAs) are known as the important components of RNA silencing and post-transcriptional gene regulation, and they interact with messenger RNAs (mRNAs) either by degradation or by translational repression. miRNA alterations have a significant impact on the formation and progression of human cancers. Additionally, finding primary tissue of tumors is a fundamental property of a precise treatment. Therefore, employing computational methods with the ability to identify both tissue-specific and cohort-specific miRNA-mRNA regulatory modules is fast becoming a crucial tool in cancer biology. In this thesis, we first identified regulatory modules of 32 cancer types using a sparse multivariate factor regression (SMFR) model on matched miRNA and mRNA expression profiles of more than 9,000 primary tumors. We used an algorithm that decomposes the coefficient matrix into two low-rank matrices with separate sparsity-inducing penalty terms on each. Although, our solution significantly outperformed another decomposition-based approach in terms of normalized root mean squared error, the interpretability of the algorithm was not satisfying, due to the low sparsity level of solutions. Therefore, we proposed a single task two-step framework to model miRNA-mRNA relationships and identify cancer-specific modules between miRNA and mRNA from their matched expression profiles. We first estimated the regulatory matrix between miRNA and mRNA expression profiles by solving multiple linear programming problems. We then formulated a unified regularized factor regression (RFR) model that simultaneously estimates the effective number of modules (i.e., latent factors) and extracts modules by decomposing regulatory matrix into two low-rank matrices. Our RFR model groups correlated miRNAs together and correlated mRNAs together, and controls sparsity levels of both matrices. These attributes lead to interpretable results with high predictive performance. To find the biological relevance of our approach, we performed functional gene set enrichment and survival analyses. A large portion of the identified modules are significantly enriched in Hallmark, PID and KEGG pathways/gene sets. To validate the identified modules, we also performed literature validation as well as validation using experimentally supported miRTarBase database. By applying proposed single-task algorithm on 32 independent cancer cohorts, interestingly we observed similar patterns in identified miRNAs and mRNAs, also in significance of certain gene sets for specific cohorts. Inspired with the previous results, we attempted to investigate the similarities between mechanism of miRNA-mRNA regulatory modules in different cancer cohorts from the same tissue to improve the predictive performance of the model and extract more detailed and informative solutions. Moreover, detecting commonalities of cohorts from the same tissue, can provide valuable information about the underlying tissue and cohort mechanisms. Hence, we established a multitask learning formulation to identify key tissue- and cohort-specific miRNA-mRNA regulatory modules from their matched expression profiles of tumors. To this end, we proposed a multitask learning sparse regularized factor regression (MSRFR) method to model the sparse relationship between miRNAs and mRNAs, extract tissue- and cohort-specific miRNA-mRNA regulatory modules separately and estimate the number of cohort-specific regulatory modules and shared modules (i.e., tissue-specific regulatory modules). As the validation process, we first performed literature survey to find the relationship of identified cohort-specific miRNAs and their corresponding cancer. We then applied experimentally supported validation of miRNA-mRNA interactions using miRTarBase database. Finally, to validate the performance of MSRFR model in distinguishing tissue- and cohort-specific regulatory modules, we explored the biological mechanism of identified key regulatory modules by checking their enriched pathways in PID and Hallmark collections. The overall result indicated that proposed model was able to effectively extract meaningful miRNA-mRNA regulatory modules and differentiate tissue- and cohort-specific modules.
MDP model for the preference-based appointment scheduling problem with multi-priority patients
This thesis consists of three parts that analyze various aspects of appointment scheduling procedures in healthcare facilities. In the first part, we study an outpatient clinic with multiple types of patients that contact with the clinic to schedule an appointment. The clinic dynamically decides on the set of appointment days offered to each patient. Patients have different utility weights for each day in the booking horizon. Based on these utility weights, they either select one of the appointment days offered in the set or they leave the system without making an appointment. We model this system using a periodically time-inhomogeneous Markov decision process and derive analytical results on the structure of the optimal policy. To develop a solution for the model, we implement a simulation-based booking limit improvement algorithm by approximating the value function. In the second part, we consider a primary care clinic with strategic patients who choose between making an appointment, with an indirect wait cost, and walking in, with an inconvenience cost and a risk of being rejected. We consider two types of patients, regular, and urgent, based on their indirect waiting cost. Considering the equilibrium behavior of patients, the clinic should determine the optimal number of slots reserved for walk-ins, to maximize expected revenues. We analyze the system under observable and unobservable indirect waiting time information and characterize the equilibrium patient behavior for both of the settings. Finally, in the third part, we consider a model that combines patients' walk-in, no-show and cancellation behavior and appointment day preferences. In this study, the clinic decides on the number of slots allocated for walk-in patients and the set of appointment days offered to a patient. Given the offered set, patients may select making an appointment for one of the offered days or walking in on a day that is not included in the set. Walk-in patients have a risk of not receiving service, which we call "blockage" and blockage probability of a patient depends on the other patients' walk-in behavior. Thus, patients consider the other patients' choices while making a walk-in decision, which results in endogenously determined walk-in rate. We formulate the problem with a deterministic fluid model to maximize the expected net profit. Furthermore, we characterize the structure of the optimal fluid solution and establish its asymptotic optimality.
Strategic customer behavior in service systems: Externalities, risk sensitivity and heterogeneity
This thesis considers the analysis of models of service systems where customers are strategic risk-averse and decide whether to join the service system or balk, by taking into account various uncertainties and externalities generated by other potential customers. First, we propose a game-theoretic framework for a static service system with strategic risk-averse customers where we ignore the dynamics of the service system such as random arrivals or random service times and seek capturing the equilibrium joining probabilities in the proposed framework by utilizing other attributes of the service system such as reward, externalities and risk-sensitivity. Next, the pricing problem is presented and analyzed. We then, present an M/M/1 queueing model where similar to the previous static framework, customers are risk-averse and strategic, and address the equilibrium joining behavior of customers in such a system. We also, come up with a pricing scheme for the service provider and social welfare maximizer. Interestingly, our results indicate the possibility of charging negative prices to achieve socially desired arrival rates with risk-averse strategic customers. Finally, we extend our results to the case where customers are heterogeneous in their risk-sensitivity degree in an M/M/1 model with strategic risk-averse customers.
Tramp shipment routing and scheduling with inventory and stowage constraints
Maritime transport has been a fundamental mode of transportation for centuries, enabling the transportation of heavy and bulky items in large quantities across oceans and seas. The use of ships has allowed for the efficient movement of goods and commodities and has been vital in facilitating global trade and commerce. In modern times, maritime transport has become even more critical with the exponential growth in global trade and the movement of goods, making it an essential component of the global economy. There are various types of operations involved in maritime transport, with liner, tramp, and industrial shipping being the three most commonly used. Liner shipping refers to the use of regularly scheduled services between designated ports, where ships follow a fixed timetable and transport a specific type of cargo. In contrast, tramp shipping operates on an ad hoc basis, with ships not following a fixed schedule but instead sailing according to the requirements of customers, and the ships are usually rented or leased. Industrial shipping, on the other hand, refers to the transportation of goods using ships that are owned by the supplier or customer. Tramp shipping alongside with the liner shipping is widely used in maritime transport, particularly for the transportation of bulk cargoes such as coal, iron, and grain. In this type of shipping, ships are chartered on a single voyage basis, and the cargo is loaded and transported according to the specific requirements of the customer. The ships used in tramp shipping are usually equipped with cranes to load and unload the cargo. In the tramp shipping problem considered in this study, the objective is to transport a set of cargoes from their origin ports to their respective destination ports using a homogeneous fleet of ships. The origin and destination ports of both the cargoes and the ships are predetermined. All of the cargoes are mandatory and have to be sent to their destination point within their respective deadline. If a cargo arrives at its destination point before the deadline, there will be a deduction from the cost as a reward. To minimize the sailing cost, inventory cost, and stowage cost, the problem is modeled as a mixed integer linear program, taking into account the stowage and inventory constraints that arise in real life applications. Stowage constraints are used to ensure the stability of the ship and to eliminate the loss of time when loading and unloading the cargoes. The ports have initial inventories of the cargoes, and their inventory value changes according to the amount shipped. Inventory constraints are developed to control the changes in inventory levels. Decisions must be made based on the routes and schedules of the ships, as well as the stowage and inventory constraints. The computational results obtained from 153 instances provides valuable insights for solving the tramp-shipping problem. The results show that while small-sized instances can be solved optimally, medium-sized and large-sized instances achieve gaps between 5-30% and 30-70%, respectively, depending on different problem characteristics. This gap is found by comparing the current solution to the best bound found in the problem. This study of the tramp shipping problem is designed to provide significant practical applications in the maritime transportation industry, as it can help shipping companies optimize their fleet utilization and reduce their transportation costs, leading to increased efficiency and profitability. Previous literature concerning the combination of these three maritime problems was limited, this study is designed to fill a significant gap in the literature and bring valuable insights for further research.
Advanced algorithms and solution techniques for U-shaped assembly line balancing problems
Assembly line balancing problems entail allocation of work content to different work stations, optimizing certain criteria like minimizing the number of stations, fair allocation of work content and cycle time minimization etc. The U type layout is known for its exceptional efficiency and flexibility for line balancing problems. It also provides workers with opportunities to enhance their skills and work experience through cooperation and continuous learning. However, most of the models in literature ignore the full potential of U-lines and focus on a few narrow aspects for line balancing. In this dissertation, we address the issue of assigning tasks to workstations in ways that offer more choices to line managers and workers. In the first part of this dissertation, we develop effective logic cuts that exploit the logical structure of the problems, to improve the performance of integer programming model in terms of computational time. Proposed logic cuts enable the model to utilize bin-packing bounds at each station. Moreover, idle time information, and the knowledge about combinations of task assignments to stations, that produce solutions dominated by alternative assignments, are also exploited. Computational experiments demonstrate that our enhanced model outperforms the previously developed integer programming models in solving U-type assembly line balancing problems In the second part, we present novel ways of assigning fair workload to stations. Our model is able to fulfill different fairness criteria like minimization of mean absolute deviation and sum of squared differences. We also develop a method for distributing certain types of workloads regularly along the assembly line. This way, work sharing and benefits of communication between the workers can be enhanced. Our approach also enables the decision makers to allocate appropriate idle time to certain groups of tasks. This third part deals with uncertain task times. We develop a new variance bounds based approach to deal with the stochastic U-line balancing problem. The variance based approach is considerably simpler to implement and solves the problems efficiently, outperforming other chance constrained models used for U-lines in literature. Overall, we present methods that can be adapted easily to more complex assembly line balancing problems and provide additional choices to managers, researchers and decision makers.
The empirical analysis of international climate policies for energy decisions
While the Paris Agreement enforces a radical transformation of energy systems to limit global temperature rise to below 1.5°C, market-based economic instruments, like the European Union Emissions Trading System (ETS) and the Carbon Border Adjustment Mechanism (CBAM), accelerates the internalization of carbon emission costs internationally. This pressure demands transparent, feasible, and comparable planning tools to safeguard supply security while controlling costs. However, significant gaps persist: data-intensive general equilibrium models fall short in responsiveness, and machine learning-based prediction models, as "black boxes", lack sufficient auditability and transparency for policymakers. This dissertation, comprising a complementary series of four papers, aims to fill the identified gap by developing a multi-layered hybrid methodology building on the global energy analysis covering 147 countries and extending it to national dynamics of Türkiye and electricity sector in detail. This study integrates computationally efficient partial equilibrium economics, multi-output machine learning, and optimization methods to provide a controllable trade-off between cost, carbon, and energy security under ETS/CBAM conditions across various carbon price scenarios. It proposes an innovative planning perspective that simultaneously tackles the carbon constraints of the Paris Agreement along with the goals of energy security and fiscal efficiency, through four consecutively structured papers spanning global, national, and sectoral scales. In the first paper, the partial equilibrium model replicates the fossil fuel share of 147 countries from 1997–2014 with an average absolute error of 0.28–0.34%, demonstrating that carbon tax-incentive packages align with the 2°C target without disrupting budget balance. The second paper models the governance update period (GUP) using multilevel machine learning, quantitatively determining an optimal policy cycle that further reduces the fossil share by 6 percentage points. The third paper, scaled to the national level, assesses Türkiye's electricity installed capacity for 2030 by comparing a parametric depreciation model with LSTM/GRU-based deep learning estimates, where the deep learning approach significantly reduces the normalized error rate in hydropower generation. The Green Growth scenario increases the renewable energy share from 56% to 79% while lowering carbon intensity to 160 kg CO₂/MWh. In the fourth paper, multiple output (MO) predictions are integrated with set-covering and two-stage grid-search optimization, reducing the total root mean square error (RMSE) to 0.587, boosting renewable energy capacity by 2.2 times compared to 2024, and enabling the grid-search method to achieve the lowest CO₂ emission profile. The collective findings from these four papers underscore the development of a multi-layered hybrid methodology that delivers three unique contributions: (i) it facilitates seamless integration of global modeling outputs with low computational overhead into national-level machine learning models; (ii) it directly models simultaneous relationships among diverse energy sources through its multi-output architecture; (iii) it employs optimization tools in bidirectional interaction with machine learning forecasts, enabling a holistic evaluation of decision-making, cost, and risk dimensions within a unified framework. Findings indicate that robust carbon pricing and data-driven capacity allocation, paired with a long-term planning perspective, can align carbon intensity with Paris Agreement targets while minimizing total system costs. Consequently, methodology developed in this dissertation equips policymakers with a scalable, auditable, and feasible decision-support tool within the ETS–CBAM environment.
Türk dağıtıcıların karşılaştığı zengin araç rotalama problemi için metasezgisel algoritmaların ve çözüm süreçlerinin araştırılması
Logistical challenges pose a substantial financial burden for distributors worldwide, particularly in light of escalating oil prices and evolving customer demands. This thesis addresses a Rich Vehicle Routing Problem (RVRP) encountered by a distributor in Turkey. The problem involves a multi-objective function that integrates road tariffs, specific customer constraints, and features observed in various VRP variants. Our study explores diverse solving approaches, including an exact method developed through a novel Mixed-Integer Linear Program, as well as non-exact solutions employing heuristic and metaheuristic algorithms. Notably, our findings highlight the efficacy of metaheuristic algorithms, particularly through a two-phase solving strategy: initially dividing and solving the problem into individual sub-problems, then integrating them comprehensively. The study concluded with a 5.13% reduction in operational costs compared to the distributor's existing plan, indicating significant potential for enhanced profitability while optimizing the daily scheduling of the vehicle fleet, and further expanding applications in operations research.
Sehir lojistiğinde yer seçimi–rotalama ve senkronizasyon problemleri
City logistics aims to improve urban freight transportation by considering the costs and benefits of public and private sectors, consolidating segmented freight shipments, and integrating the individual actors in a collaborative environment. This thesis studies network design problems in city logistics systems to address managerial challenges in urban freight transportation. We consider two network design schemes, namely the one and the two-echelon distribution networks, to formulate strategic and tactical level problems in urban freight transportation. In the single-echelon systems, freight is distributed from consolidation centers located on city boundaries to the customers inside the city. In the two-echelon systems, goods are unloaded at the intermediate facilities, called satellites, and consolidated into smaller vehicles suitable for the last-mile delivery in city centers. From an operational level perspective, we highlight the importance of synchronizing first and second echelon vehicles at the satellite locations and discuss the relation of the satellite synchronization problem to the network design problems. We propose mathematical programming formulations for the introduced strategic, tactical, and operational level problems in city logistics, and develop exact and heuristic solution approaches. The exact approaches use column generation to find optimal delivery routes efficiently. The heuristics are based on the hierarchical decomposition of the original problem into its basic decisions. Extensive computational studies in this thesis provide new insights into designing and implementing a practical city logistics system in real-world.
Afet sonrasında yolları açmak için çok-araçlı ayrıt rotalama problemleri
Doğal felaketlerden sonra köprüler ve viyadükler çökebilirken, yollar hasar görebilir veya enkazla kaplanabilir. Bu sık görülen tehlike bazı yol bölümlerinin kapanmasına ve hatta yol ağının bağlantısının kesilmesine neden olur. Afet müdahale aşamasında, çalışma ekipleri, yol ağını yeniden bağlamak ve ulaşıma açmak için yolların bir alt kümesini açmak üzere işe gönderilir. Kapalı bir yoldan, bir takım tarafından bu yol açılmadan geçilemez. Bu çalışmanın amacı, yol temizleme ekipleri için senkronize edilmiş bir çalışma programı üretecek etkin bir çözüm yöntemi sunmaktır. Bloke olmuş yolları temizlemek ve tekrar bağlantı sağlamak için gönderilen birden çok iş ekibinin rotalarını bulan iki ayrıt rotalama problemi ele alınmıştır. Birinci problemde amaç ağın tamamen yeniden bağlanması için gereken zamanı enküçüklemektir. İkinci problemde ise amaç, bağlantısı kesilen ağ bileşenlerini belirli bir süre içinde tekrar bağlayarak kazanılan toplam ödülü enbüyüklemektir. Her bir problem için tam sonuç veren bir karışık tam sayılı programlama (KTP) modeli geliştirilmiştir. İlk problem için KTP modelinin bir gevşetmesinden olurlu çözüm üreten bir mat-sezgisel önerilmiştir. Gevşetme çözümünün optimalite boşluğunun, K'nın takım sayısı olduğu durumda, gevşetilmiş modelden elde edilen alt sınırın en fazla K katı olduğu kanıtlanmıştır. İkinci problem için ise, bir mat-sezgisel yöntem geliştirilmiştir. Bu yöntem, tek araç problemlerini sırasıyla güncellenmiş ödüller ile çözer. Bir üst sınır elde etmek için, önce kesin formülasyondaki zamanlama unsurları gevşetilip, daha sonra Lagrange gevşetme yöntemi ile tek araç problemlerine dönüşen gevşetilmiş KTP çözülür. Önerilen yöntemlerin etkinliği, sistematik şekilde rasgele oluşturulan çeşitli büyüklüklerdeki Öklidyen veriler ve tahmini deprem senaryolarına göre üretilen üç farklı İstanbul yol ağı verisi üzerindeki hesaplamalı deneyler ile gösterilmiştir.
Fiyat dalgalanmalarının bulunduğu ortamlarda envanter yönetimi, fiyatlama ve risk azaltımı
Price uncertainties are among the most critical challenges that retailers and manufacturers have to face. For instance, companies whose operations require procuring from commodity markets are exposed to commodity price fluctuations which experience sharp movements frequently. Besides random nature of customer demand, due to this input and/or sales price volatility, there might be considerable variability in firms' profits. It is vital for these firms to consider price fluctuations in adjusting inventory control and pricing policies, and take a variety of risk management measures. In this dissertation, we consider such a firm where continuous price changes during the planning horizon affect both unit payoff from sales as well as customer arrivals. In a multi-period setting, we first investigate optimal price-dependent inventory control policies and numerically illustrate how continuous price fluctuations affect optimal controls and resulting payoffs. Then, we analyze optimal pricing policies assuming that sales prices are determined both by market-driven random prices and firm's markup decision. We show that level of price variability has a negative effect on firms' final profits. Finally, in a minimum-variance framework, we explore financial hedging strategies of the risk-sensitive firm. We assume that inherent price dynamics of the inventory item are correlated with prices of various products which are freely traded in financial markets. This presents an opportunity for the firm to invest in a financial portfolio of these products to manage its exposure to price and demand uncertainties by observing the current inventory, wealth and price levels. In this environment, we explicitly characterize dynamic variance-minimizing investment decisions of the firm using dynamic programming. We then explore the risk reduction effects of minimum-variance financial hedges through numerical examples and show that significant risk reductions may be possible by using the right hedge.
Navigasyon ve arama konusunda çeşitli çevirimiçi eniyileme problemlerinin analizi
Bu tezde, ağ yapıları üstünde navigasyon ve arama ile ilgili çeşitli çevrimiçi eniyileme problemleri üzerinde çalışılmıştır. Çevrimiçi problemlerde bilgiler adım adım açıklanır ve tüm bilgiler mevcut olmadan önce kararlar alınmalıdır. Tez kapsamında, afete müdahale, arama kurtarma, güvenlik ve savunma alanlarında uygulamaları olan birkaç çevrimiçi eniyileme problemi için eniyi stratejiler tasarlanıp bunların performansları teorik olarak analiz edilmiştir. Önerilen stratejilerin performanslarını analiz etmek için en kötü durumda, bilginin baştan elde olduğu (çevrimdışı) durumdaki en iyi çözüme göre, rekabetçi oranlar belirlenmiştir. İlk olarak, çevrimiçi k-Kanadalı Gezgin Problemi (k-KGP), ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenmiştir. Daha önce literatürde bu problem için bir eniyi rassal strateji verilmiştir. Bu çalışmada, bazı durumlarda bu stratejinin uygulanamaz olduğu gösterilerek, strateji her durumda uygulanabilir ve eniyi olacak şekilde değiştirilmiştir. Daha sonra çevrimiçi çok katılımcılı k-KGP ele alınmıştır. Bu problemin sınırlı ve sınırsız iletişimin olduğu iki durumuna bakılarak, literatürde verilen, deterministik stratejilerin rekabetçi oranına alt sınırı iyileştirilmiştir. Aynı iki durum, ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenerek, iki deterministik strateji geliştirilmiştir. Bunlardan bir tanesinin eniyi olduğu ispatlanmıştır. Problemin iletişimin olmadığı, sınırlı ve sınırsız iletişimin olduğu üç durumuna bakılarak, rassal stratejilerin rekabetçi oranına alt sınırlar geliştirilmiştir. Ayrıca iletişimli durumlar için rassal bir strateji geliştirilerek, bunun ayrıtları kesişmeyen yollara sahip çizgeler üzerinde eniyi olduğu ispatlanmıştır. Ayrıt belirsizliği olan çevrimiçi Minimum Gecikme Problemi de ele alınan bir başka problemdir. Bu problem için bir eniyi deterministik strateji geliştirilmiştir. Ayrıca, rassal stratejilerin beklenen rekabetçi oranına bir alt sınır bulunmuştur. Son olarak, çevrimiçi Ayrık Arama Problemi, yönlendirilmemiş çizgelerdeki seyahat ve arama maliyetleriyle incelenmiştir. Eniyi deterministik ve rassal stratejiler bulunmuştur.
Çeşitli konveks olmayan problemlerin kopozitif formulasyonlarının dıştan yaklaşımları üzerine
Copositive optimization is linear optimization over the convex cone of copositive or completely positive matrices. "The term copositive programming" was first introduced in 2000. In 2009, Burer showed that mixed binary quadratic optimization problems (MBQP), which comprises a rather large class of nonconvex and combinatorial problems, can be equivalently reformulated as a copositive optimization problem. This seminal work has greatly increased the interest in copositive optimization. It is not surprising, however, that since many combinatorial and nonconvex optimization problems can be reformulated as a copositive optimization problem, copositive programs are also NP-hard in general. The difficulty in the reformulation is entirely due to the conic constraint. For this reason, many researchers have proposed outer approximation hierarchies to the intractable completely positive cone. These approximation hierarchies are composed of a sequence of tractable cones that yield increasingly better approximations of the completely positive cone and are exact in the limit. By replacing the intractable cone by outer approximations in the copositive formulation of nonconvex and NP-hard minimization (resp. maximization) problems, a sequence of increasingly tighter lower (upper) bounds can be obtained for the original problem. This provides opportunities to obtain near-optimal solutions and improve the effectiveness of the algorithms for solving the original problem. In this thesis, we study outer approximations of the copositive reformulations of three classes of nonconvex and NP-hard optimization problems. We first study the class of mixed binary programs (MBPs). We compare the lower bounds arising from outer polyhedral approximations to the lower bound provided by the linear programming (LP) relaxation and establish that the lower bounds due to outer approximations are at least as good as that of LP relaxation. We establish various necessary or sufficient conditions under which the lower bound arising from the outer approximations matches that from the LP relaxation. Our results illustrate the weaknesses of polyhedral approximations. On the other hand, we show that the non-polyhedral doubly nonnegative (DNN) approximations, in general, yield tighter lower bounds. Secondly, we focus on the specific 0-1 knapsack problem (KP) in the class of MBPs. We study two different copositive formulations of the knapsack and compare the upper bounds arising from outer polyhedral approximations to the upper bound provided by the LP relaxation of (KP). We prove that upper bounds obtained from outer polyhedral approximations actually coincide with the upper bound provided by the LP relaxation until at least a certain and fairly large level of the hierarchy. On the other hand, we establish that if the LP relaxation has a non-integer unique solution, then the DNN relaxation gives a strictly better upper bound than the LP relaxation. Finally, we consider the standard quadratic programs (StQP) and investigate the instances of (StQP) for which the DNN relaxation is exact. We establish a complete algebraic characterization of the (StQP) instances that admit an exact DNN relaxation. We explicitly identify three different subsets of such (StQP) instances. Furthermore, we propose a recipe for constructing instances of (StQP) with an exact DNN relaxation. In summary, our results reveal that outer polyhedral approximations, in general, yield weak bounds for (MBP) and for the specific 0-1 knapsack problem, whereas doubly nonnegative relaxations usually give rise to tighter lower bounds.
Yoğun bakım ünitelerinde tekrar denemeli hasta kabul ve taburcu etme kontrollerin incelenmesi
Intensive Care Units (ICUs) are scarce resources and operate most of the time under high occupancy rates. When faced with limited bed availability, arriving patients are sometimes refused or admitted by discharging an existing patient early, which may result in both increased readmission rates and patient/hospital related costs. Yet, there is not a well-defined admission and discharge control policy to decrease such adverse consequences. In this thesis, we consider a conceptual ICU setting that serves multiple types of patients, which reflects the trade-offs between first-time and recurring patients, between different health stages as well as between the early-discharge and rejection decisions. To do this, we define a so-called readmission orbit whose population consists of patients who are to be readmitted after a previous ICU discharge. There are two major approaches available to represent and analyze such a model: Markov Decision Processes (MDPs) and fluid approximations. Since the conceptual model suffers from the curse of dimensionality, we first consider a simple version of the conceptual model with only one patient type and one health condition, by which we isolate the effects various admission and discharge decisions on readmissions. We present a discrete-time MDP formulation for the simple model and investigate the structure of the optimal admission and discharge control policy under such a model. Next, we present discrete-time MDP formulation for the conceptual model, which aims to develop a well-performing and implementable policy, rather than finding an optimal policy. Then, we develop a deterministic fluid model to control admissions and discharges in such an environment and show that the optimal control of the fluid model in the steady state can be obtained by solving a nonlinear problem. We derive a heuristic policy based on the solution of this nonlinear problem. Finally, we develop a discrete-event simulation platform that represents the ICU system. The platform is quite general, so that it can represent ICUs with different characteristics as well as a variety of control policies. We use this platform to benchmark the performance of the proposed heuristic policies, with those of the two state-of-the-art policies. Numerical results show that our proposed policies significantly outperform the the state-of-the-art policies.