Multi-start and path relinking methods to deal with multiobjective knapsack problems

This paper deals with a multiobjective combinatorial optimization problem called Extended Knapsack Problem. By applying multi-start search and path relinking we rapidly guide the search toward the most balanced zone of the Pareto-optimal front. The Pareto relation is applied in order to designate a subset of the best generated solutions to be the current efficient set of solutions. The max-min criterion with the Hamming distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. The performance of our approach is compared with several state-of-the-art MOEAs for a suite test problems taken from the literature.     

Fractional knapsack problems

The fractional knapsack problem to obtain an integer solution that maximizes a linear fractional objective function under the constraint of one linear inequality is considered. A modification of the Dinkelbach's algorithm [3] is proposed to exploit the fact that good feasible solutions are easily obtained for both the fractional knapsack problem and the ordinary knapsack problem. An upper bound of the number of iterations is derived. In particular it is clarified how optimal solutions depend on the right hand side of the constraint; a fractional knapsack problem reduces to an ordinary knapsack problem if the right hand side exceeds a certain bound.     

Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems

New variants of greedy algorithms, called advanced greedy algorithms, are identified for knapsack and covering problems with linear and quadratic objective functions. Beginning with single-constraint problems, we provide extensions for multiple knapsack and covering problems, in which objects must be allocated to different knapsacks and covers, and also for multi-constraint (multi-dimensional) knapsack and covering problems, in which the constraints are exploited by means of surrogate constraint strategies. In addition, we provide a new graduated-probe strategy for improving the selection of variables to be assigned values. Going beyond the greedy and advanced greedy frameworks, we describe ways to utilize these algorithms with multi-start and strategic oscillation metaheuristics. Finally, we identify how surrogate constraints can be utilized to produce inequalities that dominate those previously proposed and tested utilizing linear programming methods for solving multi-constraint knapsack problems, which are responsible for the current best methods for these problems. While we focus on 0–1 problems, our approaches can readily be adapted to handle variables with general upper bounds.     

Hybrid rounding techniques for knapsack problems

We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and more powerful ways of rounding. Moreover, we present a linear-storage polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. These linear complexity bounds give a substantial improvement of the best previously known polynomial bounds [A. Caprara, et al., Approximation algorithms for knapsack problems with cardinality constraints, European J. Oper. Res. 123 (2000) 333-345].     

Multi-constrained matroidal knapsack problems

We consider multi-constrained knapsack problems where the sets of elements to be selected are subject to combinatorial constraints of matroidal nature. For this important class of NP-hard combinatorial optimization problems we prove that Lagrangean relaxation techniques not only provide good bounds to the value of the optimum, but also yield approximate solutions, which are asymptotically optimal under mild probabilistic assumptions.Partially supported by research projects Analisi e progetto di algoritmi and Modelli ed algoritmi per l'ottimizzazione of the Italian Ministry of Education (MPI 40%), and by NATO Grant RG 85/0240. Orally presented at the 12th International Symposium on Mathematical Programming, Boston, August 1985.     

On equivalent knapsack problems

The objective function and constraint of the knapsack problem are aggregated and an equivalent knapsack problem is formed. The equivalent problem is solved in a new algorithm as a dynamic programming recursion. This new formulation then leads to a solution of the knapsack problem by the corner polyhedron and group knapsack approaches. The result is a second algorithm that differs from current algorithms and may have certain computational advantages over them.     

Quadratic bottleneck knapsack problems

In this paper we study the quadratic bottleneck knapsack problem (QBKP) from an algorithmic point of view. QBKP is shown to be NP-hard and it does not admit polynomial time ?-approximation algorithms for any ?>0 (unless P=NP). We then provide exact and heuristic algorithms to solve the problem and also identify polynomially solvable special cases. Results of extensive computational experiments are reported which show that our algorithms can solve QBKP of reasonably large size and produce good quality solutions very quickly. Several variations of QBKP are also discussed.     

Pointwise error estimates for discontinuous Galerkin methods with lifting operators for elliptic problems

In this article, we prove some weighted pointwise estimates for three discontinuous Galerkin methods with lifting operators appearing in their corresponding bilinear forms. We consider a Dirichlet problem with a general second-order elliptic operator.

     

Stochastic on-line knapsack problems

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value isO(log^3/2 n). An(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.Corresponding author.Partially supported by the Basic Research Action of the European Communities under Contract 3075 (Alcom).Partially supported by research project Models and Algorithms for Optimization of the Italian Ministry of University and Scientific and Technological Research (MURST 40%).     

Shortest path algorithms for knapsack type problems

The group knapsack and knapsack problems are generalised to shortest path problems in a class of graphs called knapsack graphs. An efficient algorithm is described for finding shortest paths provided that arc lengths are non-negative. A more efficient algorithm is described for the acyclic case which includes the knapsack problem. In this latter case the algorithm reduces to a known algorithm.     

Local minima for indefinite quadratic knapsack problems

We consider the complexity of finding a local minimum for the nonconvex Quadratic Knapsack Problem. Global minimization for this example of quadratic programming is NP-hard. Moré and Vavasis have investigated the complexity of local minimization for the strictly concave case of QKP; here we extend their algorithm to the general indefinite case. Our main result is an algorithm that computes a local minimum in O(n(logn)²) steps. Our approach involves eliminating all but one of the convex variables through parametrization, yielding a nondifferentiable problem. We use a technique from computational geometry to address the nondifferentiable problem.Supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, Department of Energy, under contract W-31-109-Eng-38, in part by a Fannie and John Hertz Foundation graduate fellowship, and in part by Department of Energy grant DE-FG02-86ER25013.A000.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.     

Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

Cover inequalities are commonly used cutting planes for the 0–1 knapsack problem. This paper describes a linear-time algorithm (assuming the knapsack is sorted) to simultaneously lift a set of variables into a cover inequality. Conditions for this process to result in valid and facet-defining inequalities are presented. In many instances, the resulting simultaneously lifted cover inequality cannot be obtained by sequentially lifting over any cover inequality. Some computational results demonstrate that simultaneously lifted cover inequalities are plentiful, easy to find and can be computationally beneficial.     

On the complexity of sequentially lifting cover inequalities for the knapsack polytope

The well-known sequentially lifted cover inequality is widely employed in solving mixed integer programs.However,it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover(Gu et al.(1999)).We show that this problem is N P-hard,thus giving a negative answer to the question.     

On two-stage stochastic knapsack problems

In this paper we study a particular version of the stochastic knapsack problem with normally distributed weights: the two-stage stochastic knapsack problem. Contrary to the single-stage knapsack problem, items can be added to or removed from the knapsack at the moment the actual weights become known (second stage). In addition, a chance-constraint is introduced in the first stage in order to restrict the percentage of cases where the items chosen lead to an overload in the second stage. To the best of our knowledge, there is no method known to exactly evaluate the objective function for a given first-stage solution. Therefore, we propose methods to calculate the upper and lower bounds. These bounds are used in a branch-and-bound framework in order to search the first-stage solution space. Special interest is given to the case where the items have similar weight means. Numerical results are presented and analyzed.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

A branch-and-bound algorithm for hard multiple knapsack problems

The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP branch-and-bound search space. In addition, we integrate the ??bound-and-bound?? upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound-and-bound, significantly outperforms previous solvers on some classes of hard problem instances.     

An exact algorithm for large multiple knapsack problems

The Multiple Knapsack Problem (MKP) is the problem of assigning a subset of n items to m distinct knapsacks, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several applications in naval as well as financial management. A new exact algorithm for the MKP is presented, which is specially designed for solving large problem instances. The recursive branch-and-bound algorithm applies surrogate relaxation for deriving upper bounds, while lower bounds are obtained by splitting the surrogate solution into the m knapsacks by solving a series of Subset-sum Problems. A new separable dynamic programming algorithm is presented for the solution of Subset-sum Problems, and we also use this algorithm for tightening the capacity constraints in order to obtain better upper bounds. The developed algorithm is compared to the mtm algorithm by Martello and Toth, showing the benefits of the new approach. A surprising result is that large instances with n=100 000 items may be solved in less than a second, and the algorithm has a stable performance even for instances with coefficients in a moderately large range.