An implementation of exact knapsack separation

DOI10.1007/s10898-015-0294-3zbMath1355.90051OpenAlexW1965789645MaRDI QIDQ330511

Maurizio Boccia, Saïd Hanafi, Igor' Leonidovich Vasilyev

Publication date: 26 October 2016

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-015-0294-3

zbMATH Keywords

generalized assignment problemknapsack problemcutting planecapacitated \(p\)-median problemcapacitated network location problemexact separationmultilevel generalized assignment problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (4)

Knapsack polytopes: a survey ⋮ An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron ⋮ Mathematical Models and Search Algorithms for the Capacitated p-Center Problem ⋮ Directed fixed charge multicommodity network design: a cutting plane approach using polar duality

Uses Software

• OR-Library
• Knapsack
• Concorde
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the exact separation of mixed integer knapsack cuts
• An exact method with variable fixing for solving the generalized assignment problem
• A computational study of exact knapsack separation for the generalized assignment problem
• Computational experience with general cutting planes for the set covering problem
• A computational evaluation of a general branch-and-price framework for capacitated network location problems
• An exact algorithm for the capacitated facility location problems with single sourcing
• Tabu search for the multilevel generalized assignment problem
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• Logic cuts for multilevel generalized assignment problems.
• Two exact algorithms for the capacitated \(p\)-median problem
• A column generation approach to capacitated \(p\)-median problems
• Heuristic solution methods for the multilevel generalized assignment problem
• A cutting plane method for knapsack polytope
• A cut and branch approach for the capacitated \(p\)-median problem based on Fenchel cutting planes
• A convex-analysis perspective on disjunctive cuts
• Separation algorithms for 0-1 knapsack polytopes
• Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable
• A Branch-and-Price Algorithm for the Multilevel Generalized Assignment Problem
• Generating Fenchel Cutting Planes for Knapsack Polyhedra
• Fenchel Cutting Planes for Integer Programs
• A Minimal Algorithm for the 0-1 Knapsack Problem
• A Branch-and-Price algorithm for the Single Source Capacitated Plant Location Problem
• A branch‐and‐price algorithm for the capacitated p‐median problem
• On the Convergence of Fenchel Cutting Planes in Mixed-Integer Programming
• Benchmarking optimization software with performance profiles.
• A new method for solving capacitated location problems based on a set partitioning approach

This page was built for publication: An implementation of exact knapsack separation