Exact Counting and Sampling of Optima for the Knapsack Problem.

Jakob Bossek Aneta Neumann Frank Neumann

Published in: CoRR (2021)

Keyphrases

knapsack problem
optimal solution
combinatorial optimization problems
dynamic programming
optimization problems
test problems
exact algorithms
np hard

evolutionary algorithm
heuristic solution
linear programming relaxation
multidimensional knapsack problem
random sampling
implicit enumeration
exact solution
optimization algorithm

np hard problems
cost function
greedy algorithm
bicriteria
metaheuristic
global optimum
linear programming
objective function

greedy heuristic
upper bound
feasible solution
tabu search
lower bound
genetic algorithm
continuous relaxation