A General Class of Greedily Solvable Linear Programs
A General Class of Greedily Solvable Linear Programs
复制标题
一类一般的贪心可解线性规划
DOI：
10.1287/moor.23.4.892
复制
发表时间：
1998
期刊：
影响因子：
2.5
通讯作者：
F. Tardella
中科院分区：
文献类型：
--
作者：
M. Queyranne;F. Spieksma;F. Tardella
贪心算法解决一对对偶线性规划问题，其中原始变量与有限乘积格的子格\(B\)的元素相关联，并且成本系数在\(B\)上定义了一个次模函数。这种方法联系并推广了两类众所周知的可贪心求解的线性规划。原始问题将满足蒙日条件（霍夫曼1963；贝因等人1995）的普通和多指标运输问题推广到禁止格点的情况，其中非禁止格点形成一个子格。对偶问题将次模多面体上的线性优化问题（洛瓦兹1983；藤重和富泽1983，它源于埃德蒙兹1970年关于多拟阵的工作）推广到任意有限乘积格。我们的模型和结果还涵盖了洛瓦兹1983年针对布尔代数特殊情况以及法伊格尔和克恩1996年针对所谓“有根森林”情况所定义的对偶线性规划及其贪心解。我们还讨论了蒙日性质和次模性之间的关系，并提出了一类在生产和物流中出现的具有次模成本的问题。
A greedy algorithm solves a dual pair of linear programs where the primal variables are associated to the elements of a sublattice B of a finite product lattice, and the cost coefficients define a submodular function on B. This approach links and generalizes two well-known classes of greedily solvable linear programs. The primal problem generalizes the ordinary and multi-index transportation problems satisfying a Monge condition Hoffman 1963; Bein et al. 1995 to the case of forbidden cells where the nonforbidden cells form a sublattice. The dual problem generalizes to an arbitrary finite product lattice the linear optimization problem over submodular polyhedra Lovasz 1983; Fujishige and Tomizawa 1983, which stemmed from the work of Edmonds 1970 on polymatroids. Our model and results also encompass the dual pairs of linear programs and their greedy solutions defined by Lovasz 1983 for the special case of the Boolean algebra, and by Faigle and Kern 1996 for the case of so-called "rooted forests." We also discuss relationships between Monge properties and submodularity, and present a class of problems with submodular costs arising in production and logistics.