The multidimensional multiple-choice knapsack problem (MMKP) is an extension of the 0-1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem but the core has not bee...
详细信息
The multidimensional multiple-choice knapsack problem (MMKP) is an extension of the 0-1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem but the core has not been developed for the MMKP so far. In this paper, we develop an approximate core for the MMKP and utilize it to solve the problem exactly. Computational results show that the algorithm can solve large uncorrelated instances (up to 100 classes and 100 items in each class) and correlated instances with small number of constraints (up to 5) efficiently. In particular, it solves recently published hard instances for the MMKP in less than a second. The algorithm consumes negligible memory, and compared with the best previous exact algorithm for the MMKP performs significantly faster. (C) 2010 Elsevier Ltd. All rights reserved.
The multidimensional multiple-choice knapsack Problem (MMKP) is an important NP-hard combinatorial optimization problem with many applications. We propose a new iterative pseudo-gap enumeration approach to solving MMK...
详细信息
The multidimensional multiple-choice knapsack Problem (MMKP) is an important NP-hard combinatorial optimization problem with many applications. We propose a new iterative pseudo-gap enumeration approach to solving MMKPs. The core of our algorithm is a family of additional cuts derived from the reduced costs constraint of the nonbasic variables by reference to a pseudo-gap. We then introduce a strategy to enumerate the pseudo-gap values. Joint with CPLEX, we evaluate our approach on two sets of benchmark instances and compare our results with the best solutions reported by other heuristics in the literature. It discovers 10 new better lower bounds on 37 well-known benchmark instances with a time limit of 1 hour for each instance. We further give direct comparison between our algorithm and one state-of-the-art "reduce and solve" approach on the same machine with the same CPLEX, experimental results show that our algorithm is very competitive, outperforming "reduce and solve" on 18 cases out of 37. (C) 2016 Elsevier B.V. All rights reserved.
Project portfolio selection problems are inherently complex problems with multiple and often conflicting objectives. Numerous analytical techniques ranging from simple weighted scoring to complex mathematical programm...
详细信息
Project portfolio selection problems are inherently complex problems with multiple and often conflicting objectives. Numerous analytical techniques ranging from simple weighted scoring to complex mathematical programming approaches have been proposed to solve these problems with precise data. However, the project data in real-world problems are often imprecise or ambiguous. We propose a fuzzy multidimensional multiple-choice knapsack Problem (MMKP) formulation for project portfolio selection. The proposed model is composed of an Efficient Epsilon-Constraint (EEC) method and a customized multi-objective evolutionary algorithm. A Data Envelopment Analysis (DEA) model is used to prune the generated solutions into a limited and manageable set of implementable alternatives. Statistical analysis is performed to investigate the effectiveness of the proposed approach in comparison with the competing methods in the literature. A case study is presented to demonstrate the applicability of the proposed model and exhibit the efficacy of the procedures and algorithms.
In a recent paper, the author and Curry solved the multidimensionalknapsack problem with generalized upper bound constraints by a critical-event tabu-search method which navigates both sides of the feasibility bounda...
详细信息
In a recent paper, the author and Curry solved the multidimensionalknapsack problem with generalized upper bound constraints by a critical-event tabu-search method which navigates both sides of the feasibility boundary with varied depth of oscillations. Efforts were made to explore the solution space near the feasibility boundary by using local swaps according to the objective function values (the resulting solutions are referred to as simple trial solutions). In this paper, a specialized tight-oscillation process is launched to intensify the search when the previous method finds good solutions or simple trial solutions near the feasibility boundary. Both feasibility changes and objective-function value changes are incorporated into the choice of moves process. This paper demonstrates the merits of using different choice rules at different stages of the heuristic. The balance of intensification and diversification is achieved by using two levels of strategic oscillation approaches together with tabu memory at the main heuristic stage and the trial solution stage. With the tight oscillation method, the heuristic is able to find high-quality solutions very efficiently. (c) 2004 Elsevier Ltd. All rights reserved.
As commercial nuclear power plants (NPPs) pursue extended plant operations in the form of Second License Renewals (SLRs), opportunities exist for these plants to provide capital investments to ensure long-term, safe, ...
详细信息
ISBN:
(纸本)9780791883747
As commercial nuclear power plants (NPPs) pursue extended plant operations in the form of Second License Renewals (SLRs), opportunities exist for these plants to provide capital investments to ensure long-term, safe, and economic performance. Several utilities have already announced their intention to pursue extended operations for one or more of their NPPs via SLR2. The goal of this research is to develop a risk-informed approach to evaluate and prioritize plant capital investments made in preparation for, and during the period of extended plant operations to support decisions in NPP operations. In order to prioritize project selection via a risk-informed approach we developed a single decision-making tool that integrates safety/reliability, cost, and stochastic optimization models to provide users with data analysis capabilities to more cost effectively manage plant assets. Both stochastic analysis methods such as Monte Carlo-based sampling strategies and multi-stage stochastic optimization strategies are employed to provide priority lists to decision-makers in support of risk-informed decisions. We applied the proposed method to a trial application of projected replacement/refurbishment expenditures for plant capital assets (i.e., structures, systems, and components [SSCs]). The objective is to optimize the SSC replacement/refurbishment schedule in terms of economic constraints, data uncertainties, and SSC reliability data, as well to generate a priority list for maximizing returns on investment.
暂无评论