Research Outputs

Permanent URI for this communityhttps://hdl.handle.net/20.500.14288/2

Browse

Search Results

Now showing 1 - 5 of 5
  • Placeholder
    Publication
    A kernel-based multilayer perceptron framework to identify pathways related to cancer stages
    (Springer International Publishing Ag, 2023) Mokhtaridoost, Milad; Department of Industrial Engineering; Soleimanpoor, Marzieh; Gönen, Mehmet; Department of Industrial Engineering; Graduate School of Sciences and Engineering; College of Engineering
    Standard machine learning algorithms have limited knowledge extraction capability in discriminating cancer stages based on genomic characterizations, due to the strongly correlated nature of high-dimensional genomic data. Moreover, activation of pathways plays a crucial role in the growth and progression of cancer from early-stage to latestage. That is why we implemented a kernel-based neural network framework that integrates pathways and gene expression data using multiple kernels and discriminates early- and late-stages of cancers. Our goal is to identify the relevant molecular mechanisms of the biological processes which might be driving cancer progression. As the input of developed multilayer perceptron (MLP), we constructed kernel matrices on multiple views of expression profiles of primary tumors extracted from pathways. We used Hallmark and Pathway Interaction Database (PID) datasets to restrict the search area to interpretable solutions. We applied our algorithm to 12 cancer cohorts from the Cancer Genome Atlas (TCGA), including more than 5100 primary tumors. The results showed that our algorithm could extract meaningful and disease-specific mechanisms of cancers. We tested the predictive performance of our MLP algorithm and compared it against three existing classification algorithms, namely, random forests, support vector machines, and multiple kernel learning. Our MLP method obtained better or comparable predictive performance against these algorithms.
  • Placeholder
    Publication
    Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis
    (Taylor & Francis Ltd, 2017) Department of Industrial Engineering; Yıldırım, Emre Alper; Faculty Member; Department of Industrial Engineering; College of Engineering; 28415
    Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, a linear optimization problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs as well as general mixed binary quadratic programs with a bounded feasible region.
  • Placeholder
    Publication
    Optimal recruitment in a Markovian manponver planning system
    (Eurosis, 2003) Kocaman, İbrahim; Department of Industrial Engineering; Özekici, Süleyman; Faculty Member; Department of Industrial Engineering; College of Engineering; 32631
    An important decision problem in manpower planning concerns the determination of the number of new recruits who should enter an organization in a given period. This decision must of course be based on various cost factors involved and the manpower requirements of the organization. Another important issue is that the decision maker should also consider the prevailing economic conditions. We propose an LP formulation to minimize the average cost per period in a Markovian model that also incorporates the effect of economic variations.
  • Placeholder
    Publication
    The approximability of multiple facility location on directed networks with random arc failures
    (Springer, 2020) Hassin, Refael; Ravi, R.; Segev, Danny; Department of Industrial Engineering; Salman, Fatma Sibel; Faculty Member; Department of Industrial Engineering; College of Engineering; 178838
    We introduce and study the maximum reliability coverage problem, where multiple facilities are to be located on a network whose arcs are subject to random failures. Our model assumes that arcs fail independently with non-uniform probabilities, and the objective is to locate a given number of facilities, aiming to maximize the expected demand serviced. In this context, each demand point is said to be serviced (or covered) when it is reachable from at least one facility by an operational path. The main contribution of this paper is to establish tight bounds on the approximability of maximum reliability coverage on bidirected trees as well as on general networks. Quite surprisingly, we show that this problem is NP-hard on bidirected trees via a carefully-constructed reduction from the partition problem. On the positive side, we make use of approximate dynamic programming ideas to devise an FPTAS on bidirected trees. For general networks, while maximum reliability coverage is (1-1/e+epsilon)-inapproximable as an extension of the maxk-cover problem, even estimating its objective value is #P-complete, due to generalizing certain network reliability problems. Nevertheless, we prove that by plugging-in a sampling-based additive estimator into the standard greedy algorithm, a matching approximation ratio of 1-1/e-epsilon can be attained.
  • Placeholder
    Publication
    Tractable cases of facility location on a network with a linear reliability order of links
    (Springer-Verlag Berlin, 2009) Hassin, Refael; Ravi, Ramamoorthi; Department of Industrial Engineering; Salman, Fatma Sibel; Faculty Member; Department of Industrial Engineering; College of Engineering; 178838
    In this paper we study the problem of locating k facilities to maximize the expected demand serviced in a network with unreliable links. Given a linear ordering of links, which models the dependencies among link failures, we assume that when a strong link fails, all weaker links with lower reliability also fail. This model is due to Gunnec and Salman [1], and for the single ordering case, an exact algorithm for maximizing expected serviced demand was provided in our earlier work [2] via a greedy method and dynamic programming. Our main result in this paper is to identify the boundary of hardness of the problem as we extend the model to have more than one disaster scenario and there is a different linear order in each scenario (defining the strength of the links in the scenario). We show that in the case with two disaster scenarios, the resulting facility location problem is polynomial time solvable by proving total unimodularity of a linear programming formulation. We also supply an alternate proof of this fact by the iterative relaxation method. In addition, for the two scenario case, we show that a version maximizing the expected demand served minus the sum of facility opening costs reduces to a bipartite matching problem. We then prove NP-hardness for the case with three orderings, even when all reliability values are one or zero (i.e., every scenario is deterministic, and we have three scenarios). Following the idea of the reduction, we show that the problem with an arbitrary number of orderings generalizes the maximum coverage problem, and hence affords a greedy approximation algorithm with performance ratio. We also consider the distance-bounded version of the problem where a demand point can be covered only if a facility exists within a distance limit, and show that the problem is NP-hard even for a single ordering and is equivalent to the maximum k-facility location problem. Our methods represent the first attempt at finding interesting tractable models of link failure for facility location planning for disasters. Our earlier results for the case of a single ordering [2] already showed the versatility of various techniques such as the Greedy method and a Dynamic Programming algorithm for addressing the many variants of the problem. This paper reveals an even richer structure for the polynomially solvable two-scenario case by showing non-trivial applications of total unimodularity, the iterative relaxation technique and weighted bipartite perfect matchings.