We investigate the assignment of assets to tasks where each asset can potentially execute any of the tasks, but assets execute tasks with a probabilistic outcome of success. There is a cost associated with each possib...
详细信息
ISBN:
(纸本)9780819481610
We investigate the assignment of assets to tasks where each asset can potentially execute any of the tasks, but assets execute tasks with a probabilistic outcome of success. There is a cost associated with each possible assignment of an asset to a task, and if a task is not executed there is also a cost associated with the non-execution of the task. Thus any assignment of assets to tasks will result in an expected overall cost which we wish to minimise. We propose an approach based on the Random Neural Network (RNN) which is fast and of low polynomial complexity. The evaluation indicates that the proposed RNN approach comes at most within 10% of the cost obtained by the optimal solution in all cases.
The maximum-entropy sampling problem is the NP-hard problem of maximizing the (log) determinant of an order-s principal submatrix of a given order n covariance matrix C. Exact algorithms are based on a branch-and-boun...
详细信息
The maximum-entropy sampling problem is the NP-hard problem of maximizing the (log) determinant of an order-s principal submatrix of a given order n covariance matrix C. Exact algorithms are based on a branch-and-bound framework. The problem has wide applicability in spatial statistics and in particular in environmental monitoring. Probably the best upper bound for the maximum empirically is Anstreicher???s scaled ???linx??? bound. An earlier methodology for potentially improving any upper-bounding method is by masking, that is, applying the bounding method to C ??? M, where M is any correlation matrix. We establish that the linx bound can be improved via masking by an amount that is at least linear in n, even when optimal scaling parameters are used. We also extend an earlier result that the linx bound is convex in the logarithm of a scaling parameter, making a full characterization of its behavior and providing an efficient means of calculating its limiting behavior in all cases.
The NP-hard maximum-entropy sampling problem (MESP) seeks a maximum (log-)determinant principal submatrix, of a given order, from a positive-semidefinite input matrix C. We give an efficient dynamic-programming algori...
详细信息
The NP-hard maximum-entropy sampling problem (MESP) seeks a maximum (log-)determinant principal submatrix, of a given order, from a positive-semidefinite input matrix C. We give an efficient dynamic-programming algorithm for MESP when C (or its inverse) is tridiagonal. A mask M for MESP is a correlation matrix with which we pre-process C, by taking the Hadamard product M ◦C. Upper bounds on MESP with M ◦C give upper bounds on MESP with C. Most upper-bounding methods are much faster to apply, when the input matrix is tridiagonal, so we consider tridiagonal masks M (which yield tridiagonal M ◦ C). We analyze such tridiagonal masks, and develop a combinatorial local-search based upper-bounding method that takes advantage of fast computations on tridiagonal matrices.
In this paper, a two-level algorithm is proposed to solve the distribution network reconfiguration with an objective of minimum power loss. In the first level reconfiguration, switches of maximum power loss reduction ...
详细信息
In this paper, a two-level algorithm is proposed to solve the distribution network reconfiguration with an objective of minimum power loss. In the first level reconfiguration, switches of maximum power loss reduction are disconnected by the branch exchange (BE) algorithm. Based on the results, neighbourhoods of disconnected switches are constructed by the deterministic transform method in the second level. The variable neighbourhood search (VNS) algorithm keeps searching the neighbourhoods to obtain a better solution with a lower power loss. Simulations are carried out on IEEE33 and PG&69 distribution networks to verify the superiority of the proposed algorithm. The obtained results are compared with the other methods available in the paper. It can be concluded that the presented method has both high stability and rapidity.
Motivated by recent work on algorithmic theory for nonlinear and multicriteria matroid optimization, we have developed algorithms and heuristics aimed at practical solution of large instances of some of these difficul...
详细信息
Motivated by recent work on algorithmic theory for nonlinear and multicriteria matroid optimization, we have developed algorithms and heuristics aimed at practical solution of large instances of some of these difficult problems. Our methods primarily use the local adjacency structure inherent in matroid polytopes to pivot to feasible solutions, which may or may not be optimal. We also present a modified breadth-first-search heuristic that uses adjacency to enumerate a subset of feasible solutions. We present other heuristics and provide computational evidence supporting our techniques. We implemented all of our algorithms in the software package MOCHA.
暂无评论