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.     

On the continuous quadratic knapsack problem

We introduce a new algorithm for the continuous bounded quadratic knapsack problem. This algorithm is motivated by the geometry of the problem, is based on the iterative solution of a series of simple projection problems, and is easy to understand and implement. In practice, the method compares favorably to other well-known algorithms (some of which have superior worst-case complexity) on problem sizes up ton = 4000.     

Description of 2-integer continuous knapsack polyhedra

In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems.     

The continuous center set of a network

The continuous radius of a network N is the minimum for all points of N (i.e., vertices or points on edges) of the maximum distance from x to any other point y of N.

Any point of N remote from any other point of a distance not exceeding the continuous radius is a continuous center. The continuous center set of N is the union of all continuous centers.

Properties of the continuous center set are studied and an algorithm is given to determine it, which requires O(m²log m) time and O(m) space in the worst case, m being the number of edges of N.     

A library for continuous convex separable quadratic knapsack problems

The Continuous Convex Separable Quadratic Knapsack problem (CQKnP) is an easy but useful model that has very many different applications. Although the problem can be solved quickly, it must typically be solved very many times within approaches to (much) more difficult models; hence an efficient solution approach is required. We present and discuss a small open-source library for its solution that we have recently developed and distributed.     

A faster algorithm for the continuous bilevel knapsack problem

We construct a fast algorithm with time complexity $O(nlogn)$ for a continuous bilevel knapsack problem with interdiction constraints for $n$ items. This improves on a recent algorithm from the literature with quadratic time complexity $O\left(n^2\right)$.     

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)$.     

Breakpoint searching algorithms for the continuous quadratic knapsack problem

We give several linear time algorithms for the continuous quadratic knapsack problem. In addition, we report cycling and wrong-convergence examples in a number of existing algorithms, and give encouraging computational results for large-scale problems.      

A dual approach for the continuous collapsing knapsack problem

We formulate and solve a dual version of the Continuous Collapsing Knapsack Problem using a geometric approach. Optimality conditions are found and an algorithm is presented. Computational experience shows that this procedure is efficient.     

The linking set problem: a polynomial special case of the multiple-choice knapsack problem

We consider the linking set problem, which can be seen as a particular case of the multiple-choice knapsack problem. This problem occurs as a subproblem in a decomposition procedure for solving large-scale p-median problems such as the optimal diversity management problem. We show that if a non-increasing diference property of the costs in the linking set problem holds, then the problem can be solved by a greedy algorithm and the corresponding linear gap is null.     

n-step mingling inequalities: new facets for the mixed-integer knapsack set

The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n?=?2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.     

On a nonseparable convex maximization problem with continuous knapsack constraints

We develop a polynomial-time algorithm for a class of nonseparable convex maximization problems with continuous knapsack constraints based on an analysis of the Karush-Kuhn-Tucker optimality conditions and the special problem structure. This problem class has applicability in areas such as production and logistics planning and financial engineering.     

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.     

The poisson set of cracks in an elastic continuous medium

The method of effective (self-consistent) field is used for solving the problem of a random set of interacting cracks in an elastic medium. Construction of the first moment of solution is shown on the example of a medium containing Poisson set of plane elliptic cracks. Effective elastic constants of a medium with cracks are determined and the results obtained in the plane case are compared with published experimental data.     

On the complexity of the continuous unbounded knapsack problem with uncertain coefficients

In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates for these coefficients are known. This improves the previously known bound of time for this optimization problem.     

Sweeping by a continuous prox-regular set

The evolution problem known as sweeping process is considered for a class of nonconvex sets called prox-regular (or ?-convex). Assuming, essentially, that such sets contain in the interior a suitable subset and move continuously (w.r.t. the Hausdorff distance), we prove local and global existence as well as uniqueness of solutions, which are continuous functions with bounded variation. Some examples are presented.     

The multiple-choice multi-period knapsack problem

This paper introduces the multiple-choice multi-period knapsack problem in the interface of multiple-choice programming and knapsack problems. We first examine the properties of the multiple-choice multi-period knapsack problem. A heuristic approach incorporating both primal and dual gradient methods is then developed to obtain a strong lower bound. Two branch-and-bound procedures for special-ordered-sets type 1 variables that incorporate, respectively, a special algorithm and the multiple-choice programming technique are developed to locate the optimal solution using the above lower bound as the initial solution. A computer program written in IBM's APL2 is developed to assess the quality of this lower bound and to evaluate the performance of these two branch-and-bound procedures.