Home  About us  Contact
 

Knapsack Problem (knapsack + problem)

Distribution by Scientific Domains
Business, Economics, Finance and Accounting62%
Mathematics and Statistics37%

Selected Abstracts

Information technology capital budgeting using a knapsack problem

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 4 2006
Parag C. Pendharkar
Abstract In this paper, we describe an information technology capital budgeting (ITCB) problem, show that the ITCB problem can be modeled as a 0,1 knapsack optimization problem, and propose two different simulated annealing (SA) heuristic solution procedures to solve the ITCB problem. Using several simulations, we empirically compare the performance of two SA heuristic procedures with the performance of two well-known ranking methods for capital budgeting. Our results indicate that the information technology (IT) investments selected using the SA heuristics have higher after-tax profits than the IT investments selected using the two ranking methods. [source]

A mathematical programming approach for improving the robustness of least sum of absolute deviations regression

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 4 2006
Avi Giloni
Abstract This paper discusses a novel application of mathematical programming techniques to a regression problem. While least squares regression techniques have been used for a long time, it is known that their robustness properties are not desirable. Specifically, the estimators are known to be too sensitive to data contamination. In this paper we examine regressions based on Least-sum of Absolute Deviations (LAD) and show that the robustness of the estimator can be improved significantly through a judicious choice of weights. The problem of finding optimum weights is formulated as a nonlinear mixed integer program, which is too difficult to solve exactly in general. We demonstrate that our problem is equivalent to a mathematical program with a single functional constraint resembling the knapsack problem and then solve it for a special case. We then generalize this solution to general regression designs. Furthermore, we provide an efficient algorithm to solve the general nonlinear, mixed integer programming problem when the number of predictors is small. We show the efficacy of the weighted LAD estimator using numerical examples. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006 [source]

Resource allocation with lumpy demand: To speed or not to speed?

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 3 2004
Bintong Chen
Abstract In the classical EPQ model with continuous and constant demand, holding and setup costs are minimized when the production rate is no larger than the demand rate. However, the situation may change when demand is lumpy. We consider a firm that produces multiple products, each having a unique lumpy demand pattern. The decision involves determining both the lot size for each product and the allocation of resources for production rate improvements among the products. We find that each product's optimal production policy will take on only one of two forms: either continuous production or lot-for-lot production. The problem is then formulated as a nonlinear nonsmooth knapsack problem among products determined to be candidates for resource allocation. A heuristic procedure is developed to determine allocation amounts. The procedure decomposes the problem into a mixed integer program and a nonlinear convex resource allocation problem. Numerical tests suggest that the heuristic performs very well on average compared to the optimal solution. Both the model and the heuristic procedure can be extended to allow the company to simultaneously alter both the production rates and the incoming demand lot sizes through quantity discounts. Extensions can also be made to address the case where a single investment increases the production rate of multiple products. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004. [source]

Random walks on the vertices of transportation polytopes with constant number of sources

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2008
Mary Cryan
Abstract We consider the problem of uniformly sampling a vertex of a transportation polytope with m sources and n destinations, where m is a constant. We analyze a natural random walk on the edge-vertex graph of the polytope. The analysis makes use of the multicommodity flow technique of Sinclair [Combin Probab Comput 1 (1992), 351,370] together with ideas developed by Morris and Sinclair [SIAM J Comput 34 (2004), 195,226] for the knapsack problem, and Cryan et al. [SIAM J Comput 36 (2006), 247,278] for contingency tables, to establish that the random walk approaches the uniform distribution in time n. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

Optimisation and the selection of conservation contracts*

AUSTRALIAN JOURNAL OF AGRICULTURAL & RESOURCE ECONOMICS, Issue 1 2007
Stefan Hajkowicz
This paper explores alternative techniques for the selection of conservation contracts under competitive tendering programs. Under these programs, purchasing decisions are often based on the benefits score and cost for proposed projects. The optimisation problem is to maximise the aggregate benefits without exceeding the budget. Because the budget rarely permits all projects to be funded, there is a binary choice problem, known in the operations research published work as a knapsack problem. The decision-maker must choose which projects are funded and which are not. Under some circumstances, the knapsack problem can be unsolvable because computational complexity increases exponentially with the number of projects. This paper explores the use of several decision rules for solving the optimisation problem including the use of advanced meta-heuristics. It is shown that commonly applied techniques for project selection may not be providing the optimal solution. Improved algorithms can increase the environmental programs benefits and staying within budget. The comparison of algorithms is based on real data from the Western Australian Conservation Auction. [source]

Tight bounds for the identical parallel machine-scheduling problem: Part II

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2008
Mohamed Haouari
Abstract A companion paper introduces new lower bounds and heuristics for the problem of minimizing makespan on identical parallel machines. The objective of this paper is threefold. First, we describe further enhancements of previously described lower bounds. Second, we propose a new heuristic that requires solving a sequence of 0,1 knapsack problems. Finally, we show that embedding these newly derived bounds in a branch-and-bound procedure yields a very effective exact algorithm. Moreover, this algorithm features a new symmetry-breaking branching strategy. We present the results of computational experiments that were carried out on a large set of instances and that attest to the efficacy of the proposed algorithm. In particular, we report proven optimal solutions for some benchmark problems that have been open for some time. [source]

Sensitivity analysis of the knapsack sharing problem: perturbation of the profit of an item

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2008
T. Belgacem
Abstract In this paper, we study the sensitivity of the optimum of a max,min combinatorial optimization problem, namely the knapsack sharing problem, to the perturbation of the profit of an arbitrary item. We mainly establish the interval limits of each perturbed item by applying a reduction of the original problem into a series of single knapsack problems. We propose a solution procedure in order to establish these interval limits. The principle of the method is to stabilize the optimal solution in the perturbed problem, following two cases: (i) when the item belongs to an optimal class and (ii) when the item belongs to a non-optimal class. We also consider either the problem admits a unique or multiple optimal classes. Finally, we evaluate the effectiveness of the proposed method on several problem instances in the literature. [source]

A hybrid search combining interior point methods and metaheuristics for 0,1 programming

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 6 2002
Agnès Plateau
Our search deals with methods hybridizing interior point processes and metaheuristics for solving 0,1 linear programs. This paper shows how metaheuristics can take advantage of a sequence of interior points generated by an interior point method. After introducing our work field, we present our hybrid search which generates a diversified population. Next, we explain the whole method combining the solutions encountered in the previous phase through a path relinking template. Computational experiments are reported on 0,1 multiconstraint knapsack problems. [source]