Submodularity and valid inequalities in capacitated fixed charge networks

DOI10.1016/0167-6377(89)90036-9MaRDI QIDQ1121763zbMATH OpenOpenAlexFDO

Authors 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

capacitated fixed charge networkscapacitated production planningnetwork designvalid submodular inequalities

Mathematics Subject Classification ID

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

Review text

A family of valid submodular inequalities for the flow values in capacitated fixed charge networks is derived. The results can be used for some network design problems and capacitated production planning.

Recommendations

• Valid inequalities and separation for uncapacitated fixed charge networks
• Valid inequalities and separation for capacitated fixed charge flow problems
• Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
• Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems
• On capacitated network design cut-set polyhedra

Cites work

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

Cited in

(24)

• Valid inequalities and separation for uncapacitated fixed charge networks
• Low earth orbit satellite based communication systems -- research opportunities
• Capacitated facility location: Separation algorithms and computational experience
• Theoretical challenges towards cutting-plane selection
• Multi-commodity variable upper bound flow models
• More for less method to minimize the unit transportation cost of a capacitated transportation problem with bounds on rim conditions
• Valid inequalities and separation for capacitated fixed charge flow problems
• Submodular function minimization and polarity
• Sequence independent lifting for a set of submodular maximization problems
• 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
• Erratum: ``Submodularity and valid inequalities in capacitated fixed charge networks
• Fixed-charge transportation on a path: optimization, LP formulations and separation
• On the transportation problem with market choice
• Sequence Independent Lifting for the Set of Submodular Maximization Problem
• Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
• Maximizing a class of submodular utility functions
• Lifting, superadditivity, mixed integer rounding and single node flow sets revisited
• Minimum‐cost flow problems having arc‐activation costs
• Supermodularity and valid inequalities for quadratic optimization with indicators
• Constrained optimization of rank-one functions with indicator variables
• Cutting planes in integer and mixed integer programming
• Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints
• Nonconvex, lower semicontinuous piecewise linear optimization

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121763)