A note of the knapsack problem with special ordered sets

The knapsack problem with special ordered sets and arbitrarily signed coefficients is shown to be equivalent to a standard problem of the same type but having all coefficients positive. Two propositions are proven which define an algorithm for the linear programming relaxation of the standard problem that is a natural generalization of the Dantzig solution to the problem without special ordered sets/ Several properties of the corvex hull of the associated zero-one polytope are derived.     

A surrogate relaxation based algorithm for a general quadratic multi-dimensional knapsack problem

In this paper, we develop a framework to solve a General Quadratic Multi-dimensional Knapsack Problem using surrogate relaxation. This paper exploits the fact that a continuous single constraint quadratic knapsack problem can be solved by inspection by the procedure given by Mathur et al. [6]. A preliminary computational study indicates that the proposed algorithm is much more efficient than some of the alternate procedures.     

A note on upper bounds to the robust knapsack problem with discrete scenarios

We consider the knapsack problem in which the objective function is uncertain, and given by a finite set of possible realizations. The resulting robust optimization problem is a max–min problem that follows the pessimistic view of optimizing the worst-case behavior. Several branch-and-bound algorithms have been proposed in the recent literature. In this short note, we show that by using a simple upper bound that is tailored to balance out the drawbacks of the current best approach based on surrogate relaxation, computation times improve by up to an order of magnitude. Additionally, one can make use of any upper bound for the classic knapsack problem as an upper bound for the robust problem.     

Greedy algorithm for the general multidimensional knapsack problem

In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item’s aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as “hard” MDKP and no computationally efficient heuristic is available to treat such problems. Supported in part by the NSF grant DMI 9812994.     

A note on existence, uniqueness and continuous dependence for a non-linear heat conduction problem

^** Email: cimatti{at}dm.unipi.it Using the Levy–Caccioppoli global inversion theorem, aresult of existence, uniqueness and continuous dependence isproved for a non-linear problem of heat conduction.     

A new lower bound for the linear knapsack problem with general integer variables

It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature.     

A note on the solution of group knapsack problems

Using the Nicholson principle the algorithm of Shapiro for solving group knapsack problems is improved. An approximation method is derived and numerical results are presented. The solution of the approximation method will be characterized.     

A note on maximizing a submodular set function subject to a knapsack constraint

In this paper, we obtain an (1−e⁻¹)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n⁵) function value computations.     

A polynomial algorithm for a continuous bilevel knapsack problem

In this note, we analyze a bilevel interdiction problem, where the follower’s program is a parametrized continuous knapsack. Based on the structure of the problem and an inverse optimization strategy, we propose for its solution an algorithm with worst-case complexity $O\left(n^2\right)$.     

A note on a problem of Apollonius

Degenerate cases of the problem of Apollonius, to construct a circle tangent to each of three given circles, are discussed and exhaustively classified for proper circles (finite and non-zero radius). Singular cases are considered, and an outline of the extension of the problem to higher dimensions given. Amusing alternative interpretations of the results are obtained.     

A note on a nonlinear eigenvalue problem

Summary In this paper a necessary and sufficient condition for the existence of negative eigenvalues for the problem-u – u=(x)¦u¦^p–2u in u¦=0 is given. Here Rⁿ is supposed a smooth bounded domain, 0 a bounded nonnegative function, (₁, ₂), ₁ and ₁ being the first and the second eigenvalue of - in with zero Dirichlet boundary data, p2 and, if n 3, p < 2n¦(n–2). Moreover in the linear case (p=2) a uniqueness result is proved.Work supported by G.N.A.F.A. and by M.P.I, of Italy Fondi 40% Equazioni Differenziali e Calcolo delle Variazioni and Fondi 60% Analisi matematica.     

A note on a problem of Brocard-Ramanujan

The Brocard-Ramanujan problem pertains to the Diophantine equation n!+1=m ². Using the quadratic reciprocity law, we prove the existence of many infinite families of positive integers n such that n!+1 is not a perfect square, and we give several simple criteria for n!+1 to be a non-square.      

A note on a journal selection problem

This note explores the convergence properties of certain sequences of conditional probabilities arising in a journal selection problem, where the probabilities of interest are decreasing in either a deterministic or stochastic fashion. We prove the convergence to a nonextreme value of the probability of an eventual event for any choice of problem parameters within the open unit interval. Computational results illustrate the convergence properties.     

A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem

In this paper we address two major challenges presented by stochastic discrete optimisation problems: the multiobjective nature of the problems, once risk aversion is incorporated, and the frequent difficulties in computing exactly, or even approximately, the objective function. The latter has often been handled with methods involving sample average approximation, where a random sample is generated so that population parameters may be estimated from sample statistics—usually the expected value is estimated from the sample average. We propose the use of multiobjective metaheuristics to deal with these difficulties, and apply a multiobjective local search metaheuristic to both exact and sample approximation versions of a mean-risk static stochastic knapsack problem. Variance and conditional value-at-risk are considered as risk measures. Results of a computational study are presented, that indicate the approach is capable of producing high-quality approximations to the efficient sets, with a modest computational effort.     

A generalized knapsack problem with variable coefficients

The ordinary knapsack problem is to find the optimal combination of items to be packed in a knapsack under a single constraint on the total allowable resources, where all coefficients in the objective function and in the constraint are constant.In this paper, a generalized knapsack problem with coefficients depending on variable parameters is proposed and discussed. Developing an effective branch and bound algorithm for this problem, the concept of relaxation and the efficiency function introduced here will play important roles. Furthermore, a relation between the algorithm and the dynamic programming approach is discussed, and subsequently it will be shown that the ordinary 0–1 knapsack problem, the linear programming knapsack problem and the single constrained linear programming problem with upper-bounded variables are special cases of the interested problem. Finally, practical applications of the problem and its computational experiences will be shown.