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

From MaRDI portal

Publication:3854926

Jump to:navigation, search

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 complexity integer programming polynomial time algorithm multiple choice dual simplex method surrogate constraints generalized upper bound linear programming knapsack problem convex 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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3854926&oldid=17464426"