Submodularity and valid inequalities in capacitated fixed charge networks

DOI10.1016/0167-6377(89)90036-9zbMath0674.90027OpenAlexW2053930851MaRDI QIDQ1121763

Laurence A. Wolsey

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90036-9

zbMATH Keywords

network designcapacitated fixed charge networkscapacitated production planningvalid submodular inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Production models (90B30) Deterministic network models in operations research (90B10)

Related Items (20)

Sequence Independent Lifting for the Set of Submodular Maximization Problem ⋮ Theoretical challenges towards cutting-plane selection ⋮ Valid inequalities for mixed-integer programmes with fixed charges on sets of variables ⋮ Relating single-scenario facets to the convex hull of the extensive form of a stochastic single-node flow polytope ⋮ Minimum‐cost flow problems having arc‐activation costs ⋮ Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem ⋮ Supermodularity and valid inequalities for quadratic optimization with indicators ⋮ Fixed-charge transportation on a path: optimization, LP formulations and separation ⋮ On the transportation problem with market choice ⋮ Nonconvex, lower semicontinuous piecewise linear optimization ⋮ Multi-commodity variable upper bound flow models ⋮ Cutting planes in integer and mixed integer programming ⋮ Maximizing a class of submodular utility functions ⋮ Lifting, superadditivity, mixed integer rounding and single node flow sets revisited ⋮ More for less method to minimize the unit transportation cost of a capacitated transportation problem with bounds on rim conditions ⋮ Low earth orbit satellite based communication systems -- research opportunities ⋮ Capacitated facility location: Separation algorithms and computational experience ⋮ Submodular function minimization and polarity ⋮ Sequence independent lifting for a set of submodular maximization problems ⋮ Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints

Cites Work

• Valid inequalities and separation for uncapacitated fixed charge networks
• Valid inequalities for mixed 0-1 programs
• Valid inequalities and separation for capacitated economic lot sizing
• Valid inequalities and facets of the capacitated plant location problem
• Some facets of the simple plant location polytope
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Minimizing a Submodular Function on a Lattice
• On network flow functions

This page was built for publication: Submodularity and valid inequalities in capacitated fixed charge networks