Knapsack problem

Note that if we relax the t binary variables by the inequalities 0 < y < 1, then (3-110) becomes a linear program with a (global) solution that is a lower bound to the MILP (3-110). There are specific MILP classes where the LP relaxation of (3-110) has the same solution as the MILP. Among these problems is the well-known assignment problem. Other MILPs that can be solved with efficient special-purpose methods are the knapsack problem, the set covering and set partitioning problems, and the traveling salesperson problem. See Nemhauser and Wolsey (1988) for a detailed treatment of these problems. 

The knapsack problem. We have n objects. The weight of the ith object is wi9 and its value is vf. Select a subset of the objects such that their total weight does not exceed W (the capacity of the knapsack) and their total value is a maximum. 

The problem of portfolio selection is easily expressed numerically as a constrained optimization maximize economic criterion subject to constraint on available capital. This is a form of the knapsack problem, which can be formulated as a mixed-integer linear program (MILP), as long as the project sizes are fixed. (If not, then it becomes a mixed-integer nonlinear program.) In practice, numerical methods are very rarely used for portfolio selection, as many of the strategic factors considered are difficult to quantify and relate to the economic objective function. 

Solve the Lagrangian dual problem with the latest values of A (by solving a set of integer reverse knapsack problems) to obtain the optimal objective function veilue, Z (x, A), for the given A. 

Martello, S., and Toth, P. (1990), Knapsack Problems Algorithms and Computer Implementations, John Wiley Sons, New York. 

NP-haid. Excellent bounds are obtained from La-grangean relaxations dutilizing = 1 constraints to leave a series of Knapsack problems. 

Keywords Subset-based ant colony optimisation High dimensional NP-hard problems Tournament selection Roulette wheel selection Knapsack problem... 

NP-hard combinatorial problems are an important class of problems in theoretical and real-world tasks. For these problems no algorithm can solve them in polynomial time. Examples of such problems in operations research are the bin packing problem and the knapsack problem. 

The following sections describe the implementation of the algorithm, experimentation with knapsack problems and multiple parameter settings, and concluding remarks. 

A traditional AGO topology-based approach would usually require variables and their selections to be optimised in a specific order (e.g. an ant will visit variable 1, then variable 2 etc. until the path through the topology is complete). However, subset selection based problems such as those in genomics where a small number of variables from the total number available should be selected, do not require this ordering of ant visitation. This is also the case for the well-known knapsack problem where the order of items in the bag is irrelevant in terms of fitness. 

The Knapsack problem was chosen for experimentation as it is an NP-hard combinatorial problem which has the required flexibility in terms of the munber of decision variables. This problem has been studied for more than a century (Mathews 1897) and it was introduced by the mathematician Tobias Dantzig (Dantzig 1930). 

In the Knapsack problem that was chosen for experimentation, each item s has two attributes ... 

The dataset describing the knapsack problem is saved on disc and the same dataset is used for aU the experiments. 

The results in Figs. 2, 3 and 4 show the dominance of the T-ACO approach for knapsack problems of this size. The size of the tournament clearly has an... 

The results in Fig. 5 show the effect of the number of ants for the T-ACO approach for knapsack problems of size 500,000 and the tournament selection of size 50. The highest fitness for 100 ants is better than the highest fitness for 50 or 20 ants. It is interesting noting that the highest fitness is better for 50 ants during the first 100,000 evaluations of the fitness function. For 100 ants, the pheromones are updated only every 100 evaluations of the fitness function that makes the convergence slower that with 50 ants. 

The results in Figs. 5 and 6 clearly show the number of ants and the size of the tournament are not independent in the T-ACO approach for knapsack problems of size 500,000. In this experimentation, the fitness is the highest for 50 ants and 500 items. 500 items is 0.1 % of the total number of items therefore 0.1 % of the total munber of items and 50 ants are the chosen parameters of the algorithm for further experiments. 

This experiment explores the potential for T-ACO to operate on lower dimensional problems. In this experiment, the roulette wheel and tournament selection of size 0.1 % are compared on the knapsack problem of sizes 50,000 and 5,000. An algorithm with 50 ants is used for this experiment. 

Figures and 8 show the results of these experiments. For the experiment solving the knapsack problem with 5,000 items only the variation of the highest fitness during the first 500,000 evaluations of the fitness function is presented. This because no variation arises after the 500,000 first evaluations of the fitness function.

Fig. 8. Variation of the highest fitness highestfit found throughout the run, over 10 runs, with 5 the size of the tournament and 50 ants for a knapsack problem of 5,000 items.

A feasible solution is any solution that satisfies the constraints C(x). For the 0/1-knapsack problem, any assignment of values to the x S that satisfies constraints (a) and (b) above is a feasible solution. An optimal solution is a feasible solution that results in an optimal (maximum in the case of the 0/1-knapsack problem) value for the optimization function. There are many interesting and important optimization problems for which the fastest algorithms known are impractical. Many of these problems are, in fact, known to be NP-hard. The following are some of the common strategies adopted when one is unable to develop a practically useful algorithm for a given optimization ... 

For most NP-hard problems, the problem of finding fc-absolute approximations is also NP-hard. As an example, consider problem NP2 (011-knapsack). From any instance (Pi, Wi,l feasible solutions as the old. However, the values of the feasible solutions to the new instance are multiples of k + l. Consequently, every k-absolute approximate solution to the new instance is an optimal solution for both the new and the old instance. Hence, -absolute approximate solutions to the 0/1-knapsack problem cannot be found any faster than optimal solutions. 

The earliest proposed public key systems were based on NP-complete problems such as the knapsack problem, but these were quickly found to be insecure. Some variants are still considered secure, but are not efficient enough to be practical. The most widely used public key cryptosystems, the RSA and El Gamal systems, are based on number theoretic and algebraic properties. Some newer systems are based on elliptic curves and lattices. Recently, Ronald Cramer and Victor Shoup developed a public key cryptosystem that is both practical and provably secure against adaptive chosen ciphertext attacks, the strongest kind of attack. The RSA system is described in detail below. 

Clearly, this class of problems requires a triple optimisation, so-called integrated optimisation, at the same time allocating available resources to each production line, production line sequencing and production line scheduling. It is a multidimensional, precedence-constrained, knapsack problem. The knapsack problem is a classical NP-hard problem, and it has been thoroughly studied in the last few decades [2]. 

Zou D, Gao L, Li S, Wu J (2011) Solving 0-1 knapsack problem by a novel global harmony search algorithm. Appl Soft Comput 11 1556-1564... 

Indivisible Bids. Now, suppose that bidders specify all-or-nothing constraints on the bids and state that the bids are indivisible. In addition, suppose that the bidders also submit multiple bids with an XOR bidding language. Let Mi denote the number of bids from supplier i, and N denote the number of suppliers. The winner determination problem can be formulated as a knapsack problem, introducing xij 0,1 to indicate that bid j from bidder i is... 

The special case where each bidder has a single bid reduces to a knapsack problem which is NP-hard [61]. In order to write this as a knapsack problem use the transformation yij = 1 — Xij and rewrite the formulation as a maximization problem. 

A special case of this formulation where each interval in the schedule is a point interval reduces to the multiple choice knapsack problem which is NP-hard [61]. Once again the we need to use a change of variables yij = 1 — xij to get the canonical maximization form. 

Recently, Kothari et al. [56] have proposed a fully polynomial-time approximation scheme (FPTAS) for a variation on this price-schedule problem in which the cost functions are piecewise and marginal-decreasing and each supplier has a capacity constraint. The approach is to construct a 2-approximation to a generalized knapsack problem, which can then be used to scale a dynamicprogramming algorithm and compute an (1 + e) approximation in worst-case time T = 0 nc) /e), for n bidders and with a maximum of c pieces in each bid. ... 

However, if the bids are indivisible then the winner determination problem reduces to a knapsack problem and becomes NP-hard. The winner determination problem can be written as follows ... 

Silvano Martello and Paulo Toth. Knapsack Problems. Wileylnter-sciences Series in Discrete Mathematics and Optimization, 1980. 

Jacobson, S., Kobza, J. Easterling, A. 2001. A Detection Theoretic approach to Modeling Aviation Security Problems using the Knapsack Problem. HE... 

---