A o(n logn) algorithm for LP knapsacks with GUB constraints

DOI10.1007/BF01588255zbMath0421.90050MaRDI QIDQ3854926

Fred Glover, Darwin D. Klingman

Publication date: 1979

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

computational complexityinteger programmingpolynomial time algorithmmultiple choicedual simplex methodsurrogate constraintsgeneralized upper boundlinear programming knapsack problemconvex screening of variables

Mathematics Subject Classification ID

Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Boolean programming (90C09)

Related Items

Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms, The knapsack problem with generalized upper bounds, A dual approach for the continuous collapsing knapsack problem, On maintenance scheduling of production units, Optimal sequential inspection policies, A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints, AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints, An O(n) algorithm for the multiple-choice knapsack linear program, Minmax linear knapsack problem with grouped variables and gub, Continuous maximin knapsack problems with GLB constraints, The integer programming background of a stochastic integer programming algorithm of dentcheva‐prékopa‐ruszczyński, LP relaxation of the two dimensional knapsack problem with box and GUB constraints, A branch and bound algorithm for solving the multiple-choice knapsack problem, An O(n) algorithm for the linear multiple choice knapsack problem and related problems, The linear multiple choice knapsack problem, Solution techniques for some allocation problems

Cites Work

• The 0-1 knapsack problem with multiple choice constraints
• Convexity cuts for multiple choice problems
• Resolution of the 0–1 knapsack problem: Comparison of methods
• Surrogate Constraint Duality in Mathematical Programming
• The Multiple-Choice Knapsack Problem
• A Branch Search Algorithm for the Knapsack Problem
• Surrogate Mathematical Programming
• An integer programming approach to a class of combinatorial problems