Counting Solutions of Knapsack Constraints

DOI10.1007/978-3-540-68155-7_17MaRDI QIDQ5387631zbMATH OpenOpenAlexFDO

Authors Gilles Pesant, Claude-Guy Quimper

Publication date 27 May 2008

Published in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68155-7_17

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• Solution counting algorithms for constraint-centered search heuristics
• Solution Counting Algorithms for Constraint-Centered Search Heuristics
• Counting-based search: branching heuristics for constraint satisfaction problems
• Accelerating counting-based search
• More robust counting-based search heuristics with alldifferent constraints

Cites work

• A Class of Hard Small 0-1 Programs
• A dynamic programming approach for consistency and propagation for knapsack constraints
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Solution Counting Algorithms for Constraint-Centered Search Heuristics
• Solving a system of linear Diophantine equations with lower and upper bounds on the variables.

Cited in

(12)

• A dynamic programming approach for consistency and propagation for knapsack constraints
• Counting and enumerating feasible rotating schedules by means of Gröbner bases
• Solution counting algorithms for constraint-centered search heuristics
• Counting-based search: branching heuristics for constraint satisfaction problems
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• Recovering indirect solution densities for counting-based branching heuristics
• Solution Counting Algorithms for Constraint-Centered Search Heuristics
• Upper bounds on the number of solutions of binary integer programs
• More robust counting-based search heuristics with alldifferent constraints
• CSPs with counters: a likelihood-based heuristic
• The Accuracy of Search Heuristics: An Empirical Study on Knapsack Problems
• Faster integer-feasibility in mixed-integer linear programs by branching to force change

This page was built for publication: Counting Solutions of Knapsack Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387631)