In systems biology, the solution space for a broad range of problems is composed of sets of functionally associated biomolecules. Since connectivity in molecular interaction networks is an indicator of functional asso...
详细信息
ISBN:
(纸本)9783319079530;9783319079523
In systems biology, the solution space for a broad range of problems is composed of sets of functionally associated biomolecules. Since connectivity in molecular interaction networks is an indicator of functional association, such sets can be identified from connected induced subgraphs of molecular interaction networks. Applications typically quantify the relevance (e. g., modularity, conservation, disease association) of connected subnetworks using an objective function and use a search algorithm to identify sets of subnetworks that maximize this objective function. Efficient enumeration of connected subgraphs of a large graph is therefore useful for these applications, and many existing search algorithms can be used for this purpose. However, there is a lack of non-heuristic algorithms that minimize the total number of subgraphs evaluated during the search for subgraphs that maximize the objective function. Here, we propose and evaluate an algorithm that reduces the computations necessary to enumerate subgraphs that maximize an objective function given a monotonically decreasing bounding function.
There has long been a custom that game development is not the mainstream of engineering and its tardiness brings little or even no harm to this industry. Nowadays, the pendulum of industrial development has swung to a...
详细信息
There has long been a custom that game development is not the mainstream of engineering and its tardiness brings little or even no harm to this industry. Nowadays, the pendulum of industrial development has swung to another side. A game project may involve hundreds of developers, thousands of jobs, and millions of costs. Situations would be worse if jobs overlap with others. Any delay of a large game project can cause a heavy penalty. Consequently, in this study, we propose two scheduling algorithms to reduce the total tardiness of a game project. If the problem size is small, a branch-and-bound algorithm is employed to provide the optimal schedules;otherwise a genetic algorithm is used to generate near-optimal schedules. The experimental results show that the proposed algorithms reduce the total tardiness significantly.
This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well-known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear P...
详细信息
This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well-known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear Programming (ILP) model proposed by Dantzig, Fulkerson and Johnson is first presented, its classical (assignment, shortest spanning r-arborescence, linear programming) relaxations are derived, and the most effective branch-and-bound and branch-andcut algorithms are described. The polynomial ILP formulations proposed for the ATSP are then presented and analyzed. The considered algorithms and formulations are finally experimentally compared on a set of benchmark instances.
The paper discusses how the used norm and corresponding Lipschitz constant influence the speed of algorithms for global optimization. For this reason Lipschitz constants corresponding to different norms were estimated...
详细信息
The paper discusses how the used norm and corresponding Lipschitz constant influence the speed of algorithms for global optimization. For this reason Lipschitz constants corresponding to different norms were estimated. Different test functions for global optimization were solved using branch-and-bound algorithm for Lipschitz optimization with different norms. Experiments have shown that the best results are achieved when combination of extreme (infinite and first) and sometimes Euclidean norms is used. [ABSTRACT FROM AUTHOR]
Three heuristic search algorithms, called algorithms A, B, and C, are presented. Their performance, with the admlssib/hty condition relaxed, is compared using the following two criteria: (i) number of node expansions ...
详细信息
This paper considers the constrained two-dimensional cutting stock problem. Some properties of the problem are derived leading to the development of a new algorithm, which uses a very efficient branching strategy for ...
详细信息
This paper considers the constrained two-dimensional cutting stock problem. Some properties of the problem are derived leading to the development of a new algorithm, which uses a very efficient branching strategy for the solution of this problem. This strategy enables the early rejection of partial solutions that cannot lead to optimality. Computational results are given and compared with those produced by a leading alternative method. These results show that the new algorithm is far superior in terms of the computer time needed to solve such problems. International Federation of Operational Research Societies 2001.
暂无评论