We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n item...
详细信息
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments for 99% of the instances reported in the literature. On many of the harder instances, our algorithm is orders of magnitude faster, which enabled it to solve 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n item...
详细信息
ISBN:
(纸本)9783031327254;9783031327261
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. On many of the harder instances, our algorithm is hundreds of times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.
Colorectal carcinoma is one of the most common types of malignancy and a leading cause of cancer-related death. Although clinicopathological parameters provide invaluable prognostic information, the accuracy of progno...
详细信息
Colorectal carcinoma is one of the most common types of malignancy and a leading cause of cancer-related death. Although clinicopathological parameters provide invaluable prognostic information, the accuracy of prognosis can be improved by using molecular biomarker signatures. Using a large dataset of immunohistochemistry-based biomarkers (n = 66), this study has developed an effective methodology for identifying optimal biomarker combinations as a prognostic tool. Biomarkers were screened and assigned to related subsets before being analysed using an iterative algorithm customised for evaluating combinatorial interactions between biomarkers based on their combined statistical power. A signature consisting of six biomarkers was identified as the best combination in terms of prognostic power. The combination of biomarkers (STAT1, UCP1, p-cofilin, LIMK2, FOXP3, and ICOS) was significantly associated with overall survival when computed as a linear variable (chi(2) = 53.183, p < 0.001) and as a cluster variable (chi(2) = 67.625, p < 0.001). This signature was also significantly independent of age, extramural vascular invasion, tumour stage, and lymph node metastasis (Wald = 32.898, p < 0.001). Assessment of the results in an external cohort showed that the signature was significantly associated with prognosis (chi(2) = 14.217, p = 0.007). This study developed and optimised an innovative discovery approach which could be adapted for the discovery of biomarkers and molecular interactions in a range of biological and clinical studies. Furthermore, this study identified a protein signature that can be utilised as an independent prognostic method and for potential therapeutic interventions.
This study presents experimental results from assessing fault orientation using triangulation and a combinatorial algorithm. We constructed two geological surfaces with vertical and inclined faults. These surfaces wer...
详细信息
This study presents experimental results from assessing fault orientation using triangulation and a combinatorial algorithm. We constructed two geological surfaces with vertical and inclined faults. These surfaces were documented by boreholes and represented by triangulated surfaces. We first calculated orientations for a small sample of triangles genetically related to faults that were also members of the Delaunay triangulation. To reduce the epistemic uncertainty regarding the true fault strike, we applied a combinatorial algorithm that allowed us to investigate the orientation distribution of all planes genetically related to the fault. The experiment revealed three unintuitive effects that require further studies: 1) greater concentration of observations about the true dip direction;2) the same dip direction for different triangles;and 3) triangles that dip in the opposite direction to the fault. To conduct spatial clustering within surfaces, we suggest considering a broader interval of orientations related to faults. This broader interval serves to honor the observation that orientations can be genetically related to faults, even if they indicate a relatively high directional within-dissimilarity. We suggest statistical methods for circular data to investigate the resulting distributions. The computer code associated with this study is open source and freely available.
Purpose–Over the past decade,the cost of product development has increased drastically,and this is due to the inability of most enterprises to locate suitable and optimal collaborators for knowledge ***,knowledge sha...
详细信息
Purpose–Over the past decade,the cost of product development has increased drastically,and this is due to the inability of most enterprises to locate suitable and optimal collaborators for knowledge ***,knowledge sharing is a mechanism that helps people find the best collaborators with relevant ***,a new approach for locating optimal collaborators with relevant knowledge is needed,which couldhelp enterprisein reducingcost andtime ina *** aimsto discuss these ***/methodology/approach–One unique challenge in the domain of knowledge sharing is that collaborators do not possess the same number of events resident in the knowledge available for *** this paper,the authors present a new approach for locating optimal collaborators in knowledge-sharing environment using the combinatorial algorithm(CA-KSE).Findings–The proposed pattern-matching approach implemented in Java is considered efficient for solving the issue peculiar to collaboration in knowledge-sharing *** authors benchmarked the proposed approach with its semi-global pairwise alignment and global alignment counterparts through scores comparison and the receiver operating characteristic *** results obtained from the comparisons showedthat CA-KSEis a perfect test havinganarea undercurveof 0.9659,comparedto the other *** limitations/implications–The paper has proposed an efficient algorithm,which is considered better than related methods,for matching several collaborators(more than two)in KS *** method could be deployed in medical field for gene analysis,software organizations for distributed development and academics for knowledge ***/value–One sign of strength of this approach,compared to most sequence alignment approaches that can only match two collaborators at a time,is that it can match several collaborators at a faster rate.
We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the Onotation suppresses poly(loglog) factors. This improves the pr...
详细信息
We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the <^> Onotation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in (O) over cap (n(3)/log(3)n) time. Our algorithm generalizes the divide- and- conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the "easy parts" of a given instance efficiently, we can solve the whole problem faster than n(3). (C) 2018 Elsevier Inc. All rights reserved.
We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the Onotation suppresses poly(loglog) factors. This improves the pr...
详细信息
ISBN:
(纸本)9783662476710
We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the <^> Onotation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in (O) over cap (n(3)/log(3)n) time. Our algorithm generalizes the divide- and- conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the "easy parts" of a given instance efficiently, we can solve the whole problem faster than n(3). (C) 2018 Elsevier Inc. All rights reserved.
The typical median subtree problem on trees is to locate a (continuous) tree-shaped facility (the leaves of this facility are not necessary vertices) with a specified length to minimize the total weighted distance of ...
详细信息
The typical median subtree problem on trees is to locate a (continuous) tree-shaped facility (the leaves of this facility are not necessary vertices) with a specified length to minimize the total weighted distance of all vertices to the new facility. In this paper, each vertex weight can be any value within an interval and the total deviation of weights is limited within a threshold. We want to find a subtree that minimizes the median function in the worst-case scenario. This is the so-called minmax robust median subtree problem on trees. In order to solve the problem, we first consider the minmax robust 1-median problem on trees and solve the problem in O(nlog n) time. Then, the nestedness property is coined, i.e., any optimal subtree must contain a robust 1-median in the tree. Based on this property, we develop a greedy algorithm that solves the corresponding problem in O(n(4)) time.
This article considers a combinatorial algorithm for finding the best set of generalized variables to construct a unified structure of models of objects being classified from given data sets on the basis of the princi...
详细信息
This article considers a combinatorial algorithm for finding the best set of generalized variables to construct a unified structure of models of objects being classified from given data sets on the basis of the principles of the group method of data handling (GMDH). A classifier giving the best representation of characteristics of the objects being classified is proposed to be constructed in the parameter space of the found structure of models.
暂无评论