Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 212 papers for “Continuous knapsack problem”

A Polyhedral Study of the Semi-Continuous Knapsack Problem

Ismael Regis, Ming Zhao · 2011

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem arises in a number of other contexts, e.g. it is a relaxation of general mixed-integer programming. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for problems with semi-continuous variables. To demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts, we present computational results on real instances of the unit commitment problem.

Cited by 0

Relaxation of the Equality Constrained Convex Continuous Knapsack Problem

Stefan M. Stefanov · RePEc: Research Papers in Economics

Abstract In this chapter, problem $$(C^=)$$ ( C = ) , defined by (6.1)–(6.3) in Chapter Six of Part Two, is considered again. Necessary and sufficient condition (characterization theorem) for problem $$(C^=)$$ ( C = ) is stated and proved in terms of a relaxed versionKnapsackproblemrelaxed (6.1)–(6.2) of this problem.

Cited by 0

The Stochastic Bilevel Continuous Knapsack Problem with Uncertain Follower’s Objective

Christoph Buchheim, Dorothee Henke, Jannik Irmai · Journal of Optimization Theory and Applications · 2022

Abstract We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack, while the follower chooses a feasible packing maximizing his own profit. The leader’s aim is to optimize a linear objective function in the capacity and in the follower’s solution, but with respect to different item values. We address a stochastic version of this problem where the follower’s profits are uncertain from the leader’s perspective, and only a probability distribution is known. Assuming that the leader aims at optimizing the expected value of her objective function, we first observe that the stochastic problem is tractable as long as the possible scenarios are given explicitly as part of the input, which also allows to deal with general distributions using a sample average approximation. For the case of independently and uniformly distributed item values, we show that the problem is #P-hard in general, and the same is true even for evaluating the leader’s objective function. Nevertheless, we present pseudo-polynomial time algorithms for this case, running in time linear in the total size of the items. Based on this, we derive an additive approximation scheme for the general case of independently distributed item values, which runs in pseudo-polynomial time.

Cited by 7Open access

The Stochastic Bilevel Continuous Knapsack Problem with Uncertain Follower's Objective

Buchheim, Christoph, Henke, Dorothee, Irmai, Jannik · arXiv (Cornell University) · 2021

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack, while the follower chooses a feasible packing maximizing his own profit. The leader's aim is to optimize a linear objective function in the capacity and in the follower's solution, but with respect to different item values. We address a stochastic version of this problem where the follower's profits are uncertain from the leader's perspective, and only a probability distribution is known. Assuming that the leader aims at optimizing the expected value of her objective function, we first observe that the stochastic problem is tractable as long as the possible scenarios are given explicitly as part of the input, which also allows to deal with general distributions using a sample average approximation. For the case of independently and uniformly distributed item values, we show that the problem is #P-hard in general, and the same is true even for evaluating the leader's objective function. Nevertheless, we present pseudo-polynomial time algorithms for this case, running in time linear in the total size of the items. Based on this, we derive an additive approximation scheme for the general case of independently distributed item values, which runs in pseudo-polynomial time.

Cited by 0Open access

Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities

Miao Bai, Carlos Cardonha · arXiv (Cornell University) · 2023

We study an extension of the cardinality-constrained knapsack problem wherein each item has a concave piecewise linear utility structure (CCKP), which is motivated by applications such as resource management problems in monitoring and surveillance tasks. Our main contributions are combinatorial algorithms for the offline CCKP and an online version of the CCKP. For the offline problem, we present a fully polynomial-time approximation scheme and show that it can be cast as the maximization of a submodular function with cardinality constraints; the latter property allows us to derive a greedy $(1 - \frac{1}{e})$-approximation algorithm. For the online CCKP in the random order model, we derive a $\frac{10.427}α$-competitive algorithm based on $α$-approximation algorithms for the offline CCKP; moreover, we derive stronger guarantees for the cases wherein the cardinality capacity is very small or relatively large. Finally, we investigate the empirical performance of the proposed algorithms in numerical experiments.

Cited by 0Open access

Pricing for customers with probabilistic valuations as a continuous knapsack problem

Michael Benisch, James Andrews, Norman Sadeh · Figshare · 2006

In this paper, we examine the problem of choosing discriminatory prices for customers with probabilistic valuations and a seller with indistinguishable copies of a good. We show that under certain assumptions this problem can be reduced to the continuous knapsack problem (CKP). We present a new fast ε-optimal algorithm for solving CKP instances with asymmetric concave reward functions. We also show that our algorithm can be extended beyond the CKP setting to handle pricing problems with overlapping goods (e.g.goods with common components or common resource requirements), rather than indistinguishable goods.We provide a framework for learning distributions over customer valuations from historical data that are accurate and compatible with our CKP algorithm, and we validate our techniques with experiments on pricing instances derived from the Trading Agent Competition in Supply Chain Management (TAC SCM). Our results confirm that our algorithm converges to an ε-optimal solution more quickly in practice than an adaptation of a previously proposed greedy heuristic.

Cited by 18Open access

Pricing for customers with probabilistic valuations as a continuous knapsack problem

Michael Benisch, et al. · 2006

In this paper, we examine the problem of choosing discriminatory prices for customers with probabilistic valuations and a seller with indistinguishable copies of a good. We show that under certain assumptions this problem can be reduced to the continuous knapsack problem (CKP). We present a new fast ǫ-optimal algorithm for solving CKP instances with asymmetric concave reward functions. We also show that our algorithm can be extended beyond the CKP setting to handle pricing problems with overlapping goods (e.g.goods with common components or common resource requirements), rather than indistinguishable goods. We provide a framework for learning distributions over customer valuations from historical data that are accurate and compatible with our CKP algorithm, and we validate our techniques with experiments on pricing instances derived from the Trading Agent Competition in Supply Chain Management (TAC SCM). Our results confirm that our algorithm converges to an ǫ-optimal solution more quickly in practice than an adaptation of a previously proposed greedy heuristic.

Cited by 0

Pricing for customers with probabilistic valuations as a continuous knapsack problem

Benisch, Michael, Andrews, James, Sadeh, Norman · KiltHub Repository · 2018

Abstract: "In this paper, we examine the problem of choosing discriminatory prices for customers with probabilistic valuations and a seller with indistinguishable copies of a good. We show that under certain assumptions this problem can be reduced to the continuous knapsack problem (CKP). We present a new fast [epsilon]-optimal algorithm for solving CKP instances with asymmetric concave reward functions. We also show that our algorithm can be extended beyond the CKP setting to handle pricing problems with overlapping goods (e.g. goods with common components or common resource requirements), rather than indistinguishable goods. We provide a framework for learning distributions over customer valuations from historical data that are accurate and compatible with our CKP algorithm, and we validate our techniques with experiments on pricing instances derived from the Trading Agent Competition in Supply Chain Management (TAC SCM). Our results confirm that our algorithm converges to an [epsilon]-optimal solution more quickly in practice than an adaptation of a previously proposed greedy heuristic."

Cited by 0Open access

Variable fixing method by weighted average for the continuous quadratic knapsack problem

Hsin‐Min Sun, Yujuan Sun · Numerical Algebra Control and Optimization · 2021

<p style='text-indent:20px;'>We analyze the method of solving the separable convex continuous quadratic knapsack problem by weighted average from the viewpoint of variable fixing. It is shown that this method, considered as a variant of the variable fixing algorithms, and Kiwiel's variable fixing method generate the same iterates. We further improve the algorithm based on the analysis regarding the semismooth Newton method. Computational results are given and comparisons are made among the state-of-the-art algorithms. Experiments show that our algorithm has significantly good performance; it behaves very much like an <inline-formula><tex-math id="M1">\begin{document}$ O(n) $\end{document}</tex-math></inline-formula> algorithm with a very small constant.</p>

Cited by 0Open access

The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective

Christoph Buchheim, Dorothee Henke · Journal of Global Optimization · 2022

Abstract We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower’s problem. More precisely, adopting the robust optimization approach and assuming that the follower’s profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower’s reaction from the leader’s perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader’s objective function.

Cited by 9Open access

The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective

Buchheim, Christoph, Henke, Dorothee · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · 2022

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower’s problem. More precisely, adopting the robust optimization approach and assuming that the follower’s profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower’s reaction from the leader’s perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader’s objective function.

Cited by 0Open access