knapsack problem

Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

  • Viswanath Nagarajan
  • Vahab S. Mirrokni
  • Maxim Sviridenko
  • Jon Lee
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more

    New Turnpike Theorems for the Unbounded Knapsack Problem

  • Ping H. Huang
  • Thomas L. Morin
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more

    Tractable algorithms for chance-constrained combinatorial problems

  • Olivier Klopfenstein
    • Categories Combinatorial Optimization, Robust Optimization, Stochastic Programming Tags , , , , ,

    This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0-1 problems. Furthermore, its tractability is highlighted. Then, an optimization … Read more

    Separation Algorithms for 0-1 Knapsack Polytopes

  • Konstantinos Kaparis
  • Adam N. Letchford
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We show that the separation problems for the so-called extended cover and weight inequalities can be solved exactly in O(nb) … Read more

    A Computational Study of Exact Knapsack Separation for the Generalized Assignment Problem

  • Pasquale Avella
  • Maurizio Boccia
  • Igor Vasilyev
    • Categories 0-1 Programming Tags , ,

    The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are based on Branch-and-Price, with lower bounds computed by Dantzig-Wolfe reformulation and column generation. In this paper we propose a … Read more

    Sequence independent lifting for 0-1 knapsack problems with disjoint cardinality constraints

  • Jean-Philippe P. Richard
  • Bo Zeng
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    In this paper, we study the set of 0-1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP). This set is a generalization of the traditional 0-1 knapsack polytope and the 0-1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its … Read more

    MW: A Software Framework for Combinatorial Optimization on Computational Grids

  • Wasu Glankwamdee
  • Jeff Linderoth
    • Categories Combinatorial Optimization, Parallel Algorithms Tags , , ,

    Our goal in this paper is to demonstrate that branch-and-bound algorithms for combinatorial optimization can be effectively implemented on a relatively new type of multiprocessor platform known as a computational grid. We will argue that to easily and effectively harness the power of computational grids for branch-and-bound algorithms, the master-worker paradigm should be used to … Read more

    A GRASP algorithm for the multi-objective knapsack problem

  • José Elias Arroyo
  • Dalessandro Vianna
    • Categories Meta Heuristics Tags ,

    In this article, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) to generate a good approximation of the efficient or Pareto optimal set of a multi-objective combinatorial optimization problem. The algorithm is applied for the 0/1 knapsack problem with r objective functions. This problem is formulated as r classic 0/1 knapsack problems. n items, … Read more

    Facets of a polyhedron closely related to the integer knapsack-cover problem

  • Leslie A. Hall
  • David R. Mazur
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , ,

    We investigate the polyhedral structure of an integer program with a single functional constraint: the integer capacity-cover polyhedron. Such constraints arise in telecommunications planning and facility location applications, and feature the use of general integer (rather than just binary) variables. We derive a large class of facet-defining inequalities by using an augmenting technique that builds … Read more

    A Polyhedral Study of the Cardinality Cosntrained Knapsack Problem

  • Ismael de Farias
  • George L. Nemhauser
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more