A general class of greedily solvable linear programs

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 unifies 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., 1992) to the case of forbidden cells. The dual problem generalizes the linear optimization problem over submodular polyhedra (Lovasz, 1983; Fujishige and Tomizawa, 1983), which stemmed from the work of Edmonds (1970) on polymatroids to an arbitrary finite product lattice. We also discuss relationships between Monge properties and submodularity, and present a class of problems with submodular costs arising in production and logistics.