INFORMS journal on computing · 1998 · 82 citations · 16 references
Natural SciencesMathematicsCapacity PlanningDesign OptimizationOptimizationCombinatorial OptimizationConstrained OptimizationDiscrete OptimizationInteger ProgrammingNetwork FlowsOptimization TheoryInteger Programming RelaxationsLagrangian RelaxationLower BoundsMinimum Spanning Tree ProblemMixed-integer ProgrammingMulticommodity FlowNetwork Flow ProblemsSteiner Tree Problem
We use variable redefinition (see R. Martin, 1987. Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition, Operations Research 35, 820–831) to strengthen a multicommodity flow (MCF) model for minimum spanning and Steiner trees with hop constraints between a root node and any other node. Hop constraints model quality of service constraints. The Lagrangean dual value associated with one Lagrangean relaxation derived from the MCF formulation dominates the corresponding LP value. However, the lower bounds given after a reasonable number of iterations of the associated subgradient optimization procedure are, for several cases, still far from the theoretical best limit. Martin's variable redefinition technique is used to obtain a generalization of the MCF formulation whose LP bound is equal to the previously mentioned Lagrangean dual bound. We use a set of instances with up to 100 nodes, 50 basic nodes, and 350 edges for comparing an LP approach based on solving the LP relaxation of the new model with the equivalent Lagrangean scheme derived from MCF.
16
Validation of subgradient optimization
Michael Held, Philip Wolfe, Harlan Crowder · Mathematical Programming · 1974 · 1.4K citations
An algorithm for the resource constrained shortest path problem
J. E. Beasley, N.D. Christofides · Networks · 1989 · 317 citations