2014/06/12 by Paolo Detti, Detti, Paolo · 1 citation
Engineering · Mathematics · #90C10 #90C27 #90C57 #Advanced Combinatorial Mathematics #Birkhoff polytope #Combinatorics #Computer science #FOS: Mathematics #Geometry #Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Polytope #Regular polygon #graph theory and CDMA systems #math.OC #msc:90C10 #msc:90C27 #msc:90C57
paper · pdf · doi:10.48550/arxiv.1406.3131
published in arXiv (Cornell University) (Cornell University)
arxiv created 2014/06/12 · openalex publication_date 2014/06/12 · arxiv updated 2014/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Sequential Multiple Knapsack Problem is a special case of Multiple knapsack problem in which the items sizes are divisible. A characterization of the optimal solutions of the problem and a description of the convex hull of all the integer solutions are presented. More precisely, it is shown that a new formulation of the problem allows to generate a decomposition approach for enumerating all optimal solutions of the problem. Such a decomposition approach is used for finding the inequalities (defined by an inductive scheme) describing the Sequential Multiple Knapsack polytope.