Capital budgeting appeared to be an on-going management challenge for not-for-profits hospitals and multihospital healthcare systems in the United States. also reported a MIP formulation designed to select projects for inclusion in a R&D portfolio, this model taking the form of a MKP with other generalized constraints. One of their contributions was to propose a new scenario-based capital budgeting model which includes the MKP as a subproblem coupled with generalized upper bound (GUB) constraints. investigated more realistic approaches combining capital budgeting models with novel, real techniques for project evaluation. Following the seminal paper of Lorie and Savage, MKP modeling has been investigated intensively in capital budgeting and project selection applications. The MKP is one of the most well-known constrained integer programming problem, and the large domain of its applications has greatly contributed to its fame.
both problems have the same feasible solutions. Moreover, any MKP having at least one of these entries a ij equal to 0, can be replaced by an equivalent MKP with positive entries, i.e. More precisely, it can be assumed, without loss of generality, that c j>0, b i>0, 0⩽ a ij⩽ b i and ∑ j=1 n a ij> b i for all j∈ N and for all i∈ M (since otherwise some or all of the variables can fixed to 0 or 1). By its nature, all entries are nonnegative. The goal is to find a subset of items that yields maximum profit without exceeding the resource capacities. Each item j∈ N requires a ij units of resource consumption in the ith knapsack ( i=1,2,…, m) and yields c j units of profit upon inclusion. ∑ j=1 n a ij x j ⩽b i, i∈M=,where n is the number of items and m is the number of knapsack constraints with capacities b i ( i=1,2,…, m).
Basically, the MKP is a resource allocation model which can be stated as max z=∑ j=1 n c j x j s. Historically, the first examples have been exhibited by Lorie and Savage and by Manne and Markowitz as a capital budgeting model. Several names have been mentioned in the literature for the MKP: m-dimensional knapsack problem, multidimensional knapsack problem, multiknapsack problem, multiconstraint 0–1 knapsack problem, etc… We choose to refer to the name coined first by Weingartner and Ness, which means without ambiguity that MKP is a generalization of the standard 0–1 knapsack problem ( m=1). The multidimensional 0–1 knapsack problem (MKP) is a special case of general linear 0–1 programs.
0 kommentar(er)
