Ph.D. Theses
Permanent URI for this collection
Browse
Recent Submissions
Item Data-driven local search heuristics for bilevel network design problems(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022., 2022) Sevim, İsmail.; Aras, Necati.; Güler,In the Network Design Problem (NDP), one aims to design the configuration of a network by installing links between a set of given nodes and determine the flow of a set of commodities over these installed links. In this thesis, we work on two bilevel NDPs where the sequential process of decision making approach is inherited. In the first bilevel NDP we model the strategic flight NDP of a small airline carrier as a network interdiction problem to analyse the maximum possible disruption in its flight network in the wake of virtual attacks performed by a competitor. We call this problem the r - Interdiction Network Design Problem with Lost Demand (RI-NDPLD). In the second problem, namely Bilevel Optimization Model for the Reconfiguration of refugee camp network (BOpt-RRC), the readjustment of configurations of refugee camp network are studied under the case of new refugee flows and possible variations in the supply of public service providers. We implement a set of generic local search matheuristics to solve both problems. In the Tabu Search (TS) proposed for the RI- NDPLD, we enhance the generic implementation with bound based pruning and regression based candidate solution set generation procedures to reduce the computational burden of explicit evaluation of all neighboring solutions, and hence, enjoy better diversification. We also implement a generic TS to solve the BOpt-RRC and devise an adaptive neighborhood selection procedure to incorporate into this implementation. In addition to the generic TS, we also implement a Variable Neighborhood Search (VNS) matheuristic and devise an association rule based injection procedure to incorporate good solution components to initial solutions obtained by usual random shaking. Experimental studies reveal promising results for the proposed methods.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.Item Distance-based learning approaches for multiple instance learning(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022., 2022) Sivrikaya, Özgür Emre.; Baydoğan, Mustafa Gökçe.Multiple Instance Learning (MIL) is a weakly supervised approach that focuses on the labeling of a set of instances (i.e. bags) where the label information of in dividual instances is generally unknown. Many of the earlier MIL studies focus on certain assumptions regarding the relationship between the bag and instance labels and devise supervised learning approaches. With the ambiguity in instance labels, these studies fail to generalize to the MIL problems with complex structures. To avoid these problems, researchers focus on embedding instance- level information to learn bag representations. In this context, dissimilarity-based representations are known to gen eralize well. This thesis proposes a novel framework in which each bag is represented by its dissimilarities to the prototypes. The framework consists learning mechanisms that provide fast and competitive results compared to the existing distance-based ap proaches on extensive benchmark data sets. The first approach is a simple model that provides a prototype generator from a given MIL data set. We aim to find out prototypes in the feature space to map the collection of instances (i.e. bags) to a dis tance feature space and simultaneously learn a linear classifier for MIL. The second proposal is a tree-based ensemble learning strategy that avoids complex tuning pro cesses and heavy computational costs without sacrificing accuracy. The framework is enriched with the integration of the methods, parameter selection strategy, and en semble design. Furthermore, the proposed methods are extended to the regression domain, namely Multiple Instance Regression (MIR). MIR is a less commonly studied area where the bag labels are real valued data instead of classes. The experiments show that the performances of all proposals are better than the state-of-the art approaches in the literature.Item Classifier combination methods in pattern recognition(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2002., 2002.) Baykut, Alper.; Barbarosoğlu, Gülay.; Erçil, Aytül.This thesis studies methodologies to combine multiple classifiers to improve classification accuracy. Different classifiers, training methods and combination algorithms are covered throughout this study. The classifiers are extended to produce class probability estimates besides their class assignments to be able to combine them more efficiently. They are integrated in a framework to provide a toolbox for classifier combination. The leave-one-out training method is used and the results are combined using proposed weighted combination algorithms. The weights of the classifiers for the weighted classifier combination are determined based on the performance of the classifiers on the training phase. The classifiers and combination algorithms are evaluated using classical and proposed performance measures. It is found that the integration of the proposed reliability measure, improves the performance of classification. A sensitivity analysis shows that the proposed polynomial weight assignment applied with probability based combination is robust to choose classifiers for the classifier set and indicates a typical one to three per cent consistent improvement compared to a single best classifier of the same set.Item 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.Item 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.Item A new uniform order-based crossover operator for genetic algorithm applications to multi-component combinatorial optimization problems(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1997., 1997.) Sivrikaya-Şerifoğlu, Funda.; Ulusoy, Gündüz.In this thesis, a new uniform order-based crossover operator to be used in genetic algorithm applications to combinatorial optimization problems is presented. There are three pure types of combinatorial problems: assignment, sequencing and selection problems. Most real world combinatorial problems involve components from these three types at the same time. The new operator is applicable to multi-component combinatorial optimization problems which involve one sequencing and one or more selection components. Examples are in abundance and include communications network design problems, machine and project scheduling problems. The operator is called the multi-component uniform order-based crossover or MCUOX. MCUOX processes ordering and value information concurrently. It works within a natural and direct representation of the problems. It is both general and powerful by being able to effectively search all the components of the problem. It enhances building block propagation, never violates precedence constraints given the parents are precedence; feasible, and is able to deal with additional selection components without any significant overhead. The application and effectiveness of MCUOX is illustrated at the hand of three well known difficult problems: simultaneous scheduling of machines and automated guided vehicles, resource constrained project scheduling problem with discounted cash flows, and parallel machine scheduling with earliness and tardiness penalties.|Keywords: Crossover operators, genetic algorithms, combinatorial optimizationItem Implicit algebraic curves and surfaces for shape modeling and recognition(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Sciences and Engineering, 1997., 1997.) Çivi, Hakan.; Erçil, Aytül.Implicit algebraic 2D curves and 3D surfaces are among the most powerful shape representations. With this approach, objects in 2D images are described by their silhouettes (em surfaces in 3D) and then represented by 2D implicit. polynomial curves; objects in 3D data are represented by the implicit polynomial surfaces. Implicit polynomial degrees of 2nd and. greater are used, typically up to 18th for 2D curves and 12th for 3D surfaces. In the thesis four contributions are presented whose common theme is using implicit polynomials for 2D and 3D shape modeling and object recognition purposes. Through the proposed concepts and algorithms, we argue that implicit polynomials provide a fast, and low computational cost model for low-error indexing into shape databases in 2D and 3D. The first contribution finds algebraic invariants of implicit polynomials under projective, affine, and Euclidean transformations by using and extending the symbolic method of classical invariant theory and shows how the invariants can be used for object recognition in invariant spaces. The second contribution is a novel model-based explicit algebraic expression for 2D-2D coordinate transformation estimation for Euclidean, similarity, and non-uniform scale transformations. The proposed explicit algebraic pose estimation expressions involve only the implicit polynomial coefficients for an object in two positions, and are drawn from an observation of how the implicit polynomial object model transforms under coordinate transformations. The third contribution is a 3D version of the 3L algorithm and an investigation of the specific problems in applying the technique in 3D as opposed to 2D. Finally, the fourth contribution explores the problem of getting affine invariant fits based on the 3L fitting as the 3L algorithm is inherently Euclidean invariant, but not affine invariant.Item Numeric methods for stochastic disease spread models(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Yıldız, Zeynep Gökçe.; Hörmann, Wolfgang.Disease spread models are important in controlling the new infectious diseases that suddenly threaten the public health. Mathematical tools are especially impor tant to understand the spread of the disease since experiments are not possible in the area. This study focusses on a stochastic SIR (susceptible-infected-recovered) model for a finite population. We first assume a homogeneous population and study Markov modelling of disease spread for an exponential infectious period. We present the al gorithms that compute the expected duration of an epidemic, the final outbreak size distribution and the maximum number of simultaneously infected individuals distri bution. After stating the problems with exponential infectious period, we assume an Erlang distributed infectious period allowing us to use Markov chains. The Markov disease spread model proposed for it uses the remaining stages as state variables and treats the Erlang distributed infectious period as simply exponential. This enables us to compute the exact final outbreak size distribution for large populations efficiently. Moreover, we propose an approximation for the distribution of the maximum epidemic size using the exact distribution of the remaining stages. We also consider a mixture of Erlangs so that by using the first two moments of an infectious period one can fit a corresponding mixture. Furthermore, by considering a mixture of Erlangs distribution for the infectious period and assuming two types of infected individuals as symptomatic and asymptomatic, our proposed models are implemented with the parameters similar to those reported for COVID-19 spread. Finally, a stochastic SIR model for a non ho mogeneous population is considered. The notion of R0 for heterogeneous populations is discussed and individual R0 as the expected number of secondary cases produced by a unique given initially infected individual. We propose a general formula for individual R0 and use it for the assessment and development of the intervention methods.Item Evolutionary approaches to many-objective combinatorial optimization problems(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Şahinkoç, Hayrullah Mert.; Bilge, Ümit.Many-objective evolutionary approaches try to characterize and overcome the challenges posed by the large number of objectives and have been shown to be very e ective for achieving good Pareto approximations. Despite the growing interest, most of the existing studies work on well-de ned continuous objective functions with designed features, and studies on combinatorial problems are still rare. The proposed many-objective evolutionary algorithm is characterized by elitist nondominated sorting and reference set based sorting where the reference points are mapped onto a xed hyperplane obtained at the beginning of the algorithm by solving single-objective problems. All evolutionary mechanisms such as reference point guided path relinking, repair and local improvement procedures are designed to complement the reference set based sorting. Moreover, the reference set co-evolves simultaneously with the solution set, using both cooperative and competitive interactions to balance diversity and convergence, and adapts to the topology of the Pareto front in a self-adaptive parametric way. The proposed algorithm works successfully both under binary and permutation encoding, as well as for correlated objectives or objectives with di erent scales. Near optimal solutions can be used to construct the hyperplane without any signi cant deterioration in the quality of the Pareto approximation. Moreover, when an optimization problem under scenario-based uncertainty is modeled as a many-objective problem, the proposed algorithm can provide good solutions simultaneously for several robust measures. Numerical experiments demonstrate the success of the proposed algorithm compared to state-of-art approaches and con rm that it can be applied sustainably to a variety of many-objective combinatorial problems.Item 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 first 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 efficient and outperform a widely used commercial solver. In particular, branch-and-price implementation is capable to find 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 significantly less radiation in reasonable computation times.Item Multi-objective approaches for multi-target learning(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Adıyeke, Esra.; Baydoğan, Mustafa Gökçe.Multi-target datasets (MTD) require simultaneous prediction of several variables hence they are considered to be more challenging in terms of predictive tasks compared to single-target datasets. Mining of MTD requires handling of several problems. To exemplify, scale inconsistencies are widely encountered in the targets. Most of the existing approaches resolve this issue by transforming the targets to the same scale, yet those operations may change the statistical properties of the dataset. Besides, features' scale inconsistencies cause problems in semi-supervised learning (SSL) applications since distance-based calculations are required therein. Another issue with MTD is, to explore alternative ways of including the target relations in learning applications. In this thesis, I develop supervised learning (SL), SSL and feature ranking (FR) models for MTD to deal with aforementioned problems. Bene ting from multi-objective optimization concepts, I aim to propose learning strategies that are robust to the type of the variables processed and utilize the target relations at the same time. Speci cally, I propose a multi-objective extension for standard decision trees and a selective classi er chaining strategy for SL tasks. Experimental studies show that proposed models outperform their benchmark models. Besides, multi-objective trees extended to their semi-supervised version so that proposed form could result a competitive performance when the label information is not adequate. Performed experiments show a signi cant improvement of the proposed model over its benchmarks. In addition, since highdimesionality and irrelevance in features reduce the e ectiveness of a learning model, an embedded feature ranking (FR) procedure to semi-supervised trees is given to address this problem. Applications on several datasets show that, proposed FR procedure enhances the predictive performance compared to its benchmark approaches.Item Campaign planning under sequence dependent family setups and co-production in process industry(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Kalay, Serkan.; Taşkın, Zeki Caner.We investigate tactical level production planning problem in process industries, with float glass manufacturing being the specific application domain. Process industries are cost intensive, and as a result, efficient usage of capacity through planning is necessary. In the presence of high sequence dependent family setup costs, the need for planning production in batches, or campaigns as named in the float glass industry, arises. Campaign planning is determining timing and duration of each product family, which translates into setups. Moreover, availability of input data in different resolution, i.e. setup times in continuous time whereas customer demand forecast are available in discrete time, increases the complexity. Co-production is a phenomenon that exists in several industries including float glass manufacturing. Usually due to some special characteristic of the manufacturing process some products need to be produced by necessity. This is another challenge for efficient capacity usage as well as inventory management. We study the problem for different complexity levels. We start with single machine instance and develop two formulations. A novel branch-and-price algorithm is proposed for the parallel machine extension. Finally, we extend the problem to multiple product hierarchy levels and network structure including customer locations. We demonstrate the efficiency of our methods through extensive numerical experiments as well as some further tests to analyze the sensitivity of the cost components.Item A decomposition approach to solve the selective graph coloring problem(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018., 2018.) Şeker, Oylum.; Aşıcı, Tınaz Ekim.; Taşkın, Zeki Caner.Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two vertices that are linked by an edge receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the aim is to pick exactly one vertex per cluster so that, among all possible selections, the number of colors needed to color the vertices in the selection is minimum. In this study, we focus on a decomposition based exact solution framework for selective coloring, and apply it rst to some special graph families, and then to general graphs with no particular structure. The special classes of graphs that we consider are perfect graphs and some special subclasses of perfect graphs, which are permutation, generalized split, and chordal graphs. In order to test the performance of our solution approach, we need graph instances from these graph classes, which led us to concentrate on the generation of random graphs from the graph classes under consideration in the second part of this study. We then test the decomposition method on graphs with di erent sizes and densities that we have produced with our generation methods, present computational results and compare them with an integer programming formulation of the problem solved by CPLEX, and a state-of-the-art algorithm from the literature. Our computational experiments indicate that our decomposition approach signi cantly improves the solution performance, especially in low-density graphs in permutation and generalized split graphs, and regardless of the edge-density in the class of chordal graphs. For perfect graphs in their general form, our approach outperforms both of the other two methods. In the case of general graphs, however, further improvements are needed to make our method competitive with the alternative methods we compare with.Item Analysis of agent-based simulation models through metamodeling(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Edalı, Mert.; Yücel, Gönenç.In this thesis, we propose a three-stage analysis procedure to interpret input output relationships of agent-based simulation models. In the first stage, we use meta models of agent-based models to approximate the input-output dynamics by construct ing a functional relationship. For this purpose, we employ Support Vector Regression and Random Forest techniques from machine learning domain. Based on the results of an experimental analysis on Segregation and Traffic Basic models, we observe that Sup port Vector Regression stands as a promising technique only for output prediction while Random Forest is more appropriate when the main aim is to clearly depict input-output dynamics with a minimal loss of accuracy. In the second stage, we focus on efficient training of Random Forest metamodels. We observe that a sequential sampling strat egy considering feedbacks from the metamodel generates more accurate metamodels compared to metamodels trained on randomly selected input-output couples. Besides, the iterative training process of metamodels also gives valuable information about the dynamics of the model by depicting boundary points between different types of model behaviors and counterintuitive outcomes. In the last stage, we devise a rule extraction technique from Random Forest metamodels based on a set partitioning problem formu lation. Finally, we apply the three-stage analysis technique to an agent-based influenza epidemic model to analyze the effectiveness of different combinations of intervention strategies in the presence of various transmissibility scenarios of influenza.Item Network optimization models with fairness concern for disaster relief operations(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Erbeyoğlu, Gökalp.; Bilge, Ümit.Humanitarian logistics activities, which aim to alleviate the suffering of the population after a sudden and calamitous event, confront us with a large number of interrelated and challenging network optimization problems. This study focuses on the preparedness and response stages of the disaster life-cycle. Humanitarian network design decisions are of critical importance since they set the frame for all further post-disaster operations. Having an adequate number of strategically located storage and distribution centers for supplies is the key that enables effectiveness, efficiency and fairness when responding to a disaster. The preparedness model proposed in this study aims to find a robust relief network design that ensures the right mix of relief items can be supplied at the right time, and satisfies the demand for all given disaster scenarios. We propose a logic-based Benders decomposition approach to solve this problem to optimality. The numerical studies demonstrate that it is possible to obtain optimal or very good solutions to instances with realistic sizes for this NP hard problem. After disaster occurrence, it is critical to have a relief distribution plan that is efficient and effective while being equitable among the beneficiaries. For this purpose, a rich vehicle routing model along with alternative linear objective functions is presented in the second stage of the study. These objectives provide a balance between timely and fair response plans. Two heuristic methods are presented for the response stage problem. Although solution quality is comparable to the solver in smaller sized problem instances, the heuristic methods provide robust solution methods since they are able to find solutions for larger cases where the solver fails. The assumptions and the parameters used in the models are justified by authorities of humanitarian organizations. The benefit of using these two complementary models consecutively to achieve a better response is also demoItem Mathematical programming and statistical learning approaches for multiple instance learning(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018., 2018.) Lök, Emel Şeyma.; Baydoğan, Mustafa Gökçe.; Taşkın, Zeki Caner.Many real-world applications of classification require flexibility in representing complex objects to preserve the relevant information for class separation. Multiple instance learning (MIL) aims to solve classification problem where each object is rep resented with a bag of instances, and class labels are provided for the bags rather than individual instances. The aim is to learn a function that correctly labels new bags. In this thesis, we propose statistical learning and mathematical optimization methods to solve MIL problems from diversified application domains. We first present bag encoding strategies to obtain bag-level feature vectors for MIL. Simple instance space partition ing approaches are utilized to learn representative feature vectors for the bags. Our experiments on a large database of MIL problems show that random tree-based encod ing is scalable and its performance is competitive with the state-of-the-art methods. Mathematical programming-based approaches to MIL problem construct a bag-level decision function. In this context, we formulate MIL problem as a linear programming model to optimize bag orderings for correct classification. Proposed formulation com bines instance-level scores to return an estimate on the bag label. All instances are solved to optimality on various data representations in a reasonable computation time. At last, we develop a quadratic programming formulation that is superior to previous MIL formulations on underlying assumptions and computational difficulties. Proposed MIL framework models contributions of instances to the bag class labels, and provide a bag class decision threshold. Experimental results verify that proposed formulation enables effective classification in various MIL applications.Item 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 flow 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 flow problems with conflict constraints that prevent the simul taneous usage of some arc pairs to send flow. We particularly concentrate on four of them: the minimum cost noncrossing flow problem on layered networks, the minimum cost flow problem with conflicts, the maximum flow problem with conflicts and the assignment problem with conflicts. The minimum cost noncrossing flow 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 flow problem with conflicts on general networks are also pro vided. Moreover, polynomially solvable special cases for the minimum cost noncrossing flow problem on layered networks and the assignment problem with conflicts, 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 flow problem with conflicts and the maximum flow problem with conflicts taking ad vantage of the conflict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to find an initial feasible solution are defined. 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.Item Local constraint based analysis in resource constrained scheduling(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1991., 1991.) Özdamar, Linet.; Ulusoy, Gündüz.Resource constrained scheduling problems are generally solved by optimization techniques which cannot accomodate large size problems with respect to computation time. Yet, fast and near optimal schedules are required in actual dynamic environments. A method which has a quick response to dynamic conditions is the usage of dispatching rules which are tested and evaluated in simulation studies or against static optimal solutions. The disadvantage of heuristics lies in their performance dependence on problem characteristics. Constraint based analysis (CBA) approach employed here stands midway between the latter two methods. The performance criterion is imposed on the scheduling process as a constraint together with resource limitations. These constraints are considered as locally essential at each scheduling decision point and activities are sequenced in accordance with the constraints. In this research, the local essential conditions are explained in detail and the static and quasi-dynamic algorithms for resource constrained scheduling in which they are incorporated are conveyed. Static solutions for· the previously solved project scheduling test problems obtained employing local CBA are compared with well-known heuristics as well as with the optimal solutions. Furthermore, CBA results for static job-shop problems representing various shop cha~acteristics are compared with heuristics.Item Risk analysis and modeling of the maritime traffic in the strait of Istanbul(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018., 2018.) Özlem, Şirin.; Or, İlhan.The Istanbul Strait connecting Marmara and Black Sea is one of the narrowest waterways in the world with daily crowded local and transit vessel traffic. Other features such as currents, wind, fog and sharp turns in that narrow waterway lead to a high accident risk for transiting vessels. The most common accidents in the Istanbul Strait are collisions and groundings which have caused considerable amount of deaths and sea pollution so far. The main aim of this study is to measure the collision and grounding probabilities in Istanbul Strait based on mathematical models. A simulation model is built that mimicks the transit traffic pattern of the Istanbul Strait for seven years through a developed scheduling algorithm. The algorithm decides the entering vessel type and entrance times each day regarding past data and established maritime rules and regulations. In order to estimate the collision and grounding probabilities, the geometric probabilities (the vessel being on a collision or grounding course) and the causation probabilities (given that the vessel on a collision or grounding course, the inability to prevent accident) are multiplied. The geometric probability is estimated based on a physical model whereas the causation probability is estimated through created Bayesian networks. Effects of some vessel based and external factors on collision or grounding causation probability are investigated. The results show that having pilot service dramatically decreases the causation probability of collision and grounding. The number of accidents are estimated by integrating the probabilities with the simulation model and the results are compared with the actual number of accidents. Effects of some factors (such as sectors, season, day light, transiting vessel direction and type) on number of collisions are also investigated. For number of groundings, the factor analysis is also elaborated on transit traffic density, as well. The results show that most frequently dry cargo vessels collide and ground in the Istanbul Strait. Number of collisions and groundings increases at nights in model results and actual cases. Moreover, as the transit traffic density increases, number of groundings increases as well.